"James Kuyper Jr." <kuyper@wizard.net> writes:

> Bernd Strieder wrote:
> ...
> > In essence, I don't expect from a foreign class that a=b has a==b as a
> > postcondition.
>
> Agreed; you don't know that unless the they are also EqualityComparable.
>
> > ... Consequently, I cannot expect that a and b show the same
> > behaviour after assignment. ...
>
> I don't think your "Consequently" is correct. There's no relationship
> between those properties. Not quite true: the combination of "a and b
> have the same behavior" and EqualityCompable would imply "a==b" as a
> special case. However, without EqualityComparable, "a and b have the
> same behavior" and "a==b" are logically independent.
>
> > ... I do expect this from int, from vector<int>,
> > because I know they fulfill it.
>
> If you're implementing a template with a type parameter T that is
> required to be Assignable, I believe you'll be just as justified in
> expecting "same behavior" after copy assignment for T, as you would be
> for 'int'. If, for instance, a seperate requirement calls for func(t) to
> be a function with no side effects that returns an integer, a conforming
> implementation of that template could set t_copy=t, and then arbitrarily
> check whether func(t)==func(t_copy).

template<class T>
 int func(T const& t)
{
  assert(sizeof int >= sizeof pointer);
  return (int)&t;
}

Now, this function is certainly side-effect free and returns an
integer. However, the check would always fail. Therefore according to
your interpretation, there are no Assignable types.

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Nicola Musatti <objectway@divalsim.it> writes:

> After reading this thread I came to the conclusion that "equivalence" is
> proving difficult to define because the use of the term in mathematics
> is misleading. The problem is that mathematical equivalence is defined
> between immutable entities, which of course C++ objects are not. In
> other words equivalence is a propriety of the state of the objects and
> not of the objects themselves.

Maybe the problem can be solved by looking at equivalence relations in
greater detail.

Mathematically, if you have a set M, then you can immediatly define
two equivalence relations. The first one, which I'll call "trivial
equivalence relation" (possibly it's even officially called such, but
I don't know), is given by M x M (x denoting the cartesian cross),
that is, every element of M is equivalent to every other element of M.
The other immediate equivalence relation is equality: {(x,x): x in M}.
Now, it can be easily seen that every equivalence relation on M is a
subset of the trivial equivalence relation (because all relations
are), and equality is a subset of every equivalence relation (because
for each equivalence relation, we have x~x for all x). More important,
if one equivalence relation ~ is a subset of another equivalence
relation ~', then if a~b then also a~'b.

Now let's look at C++ again.

std::vector in itself doesn't have any requirement except for
Assignable and CopyConstructible. Therefore there's nothing to
determine what equivalence relation has to be used. Consequently,
vector has to work with _any_ equivalence relation.

Now let's look at some algorithm which uses EqualityComparable in
addition to Assignable. Here, EqualityComparable defines a certain
equivalence relation. However, this by itself doesn't give any
relation to the equivalence relation used by assignable. Now, the idea
is of course that the Assignable equivalence relation still holds for
copies; that is, the Assignable equivalence relation must be a
_subset_ of the EqualityComparable equivalence relation. It doesn't
need to be the same, and it doesn't need to be "maximum
equivalence". We just must have a~b implies a==b.

The same is true for templates using a strict weak order, which
defines an equivalence relation through !(a<b)&&!(b<a). The Assignable
equivalence relation must be a subset of this.

In addition, the Assignable and CopyConstructible equivalence
relations should certainly the same.

Now, those are relations between _two_ equivalence relations, which
come into play whereever _both_ are demanded. Maybe one should add
something like "Whereever an equivalence relation can be derived from
other requirements on the type, the Assignable equivalence relation
must be a subset of this other equivalence relation."

>
> I'd say that two objects t and u are equivalent at a certain point of
> execution if in the first subsequent expression that involves t it is
> possible to substitute t with u without changing the program's
> semantics.

That's a bad definition IMHO. For a start, if two values a and b are
considered equivalent should not depend on the point of execution.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Christopher Eltschka wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> writes:
>
> > Bernd Strieder wrote:
....
> > If you're implementing a template with a type parameter T that is
> > required to be Assignable, I believe you'll be just as justified in
> > expecting "same behavior" after copy assignment for T, as you would be
> > for 'int'. If, for instance, a seperate requirement calls for func(t) to
> > be a function with no side effects that returns an integer, a conforming
> > implementation of that template could set t_copy=t, and then arbitrarily
> > check whether func(t)==func(t_copy).
>
> template<class T>
>  int func(T const& t)
> {
>   assert(sizeof int >= sizeof pointer);
>   return (int)&t;
> }
>
> Now, this function is certainly side-effect free and returns an
> integer. However, the check would always fail. Therefore according to

I have already admitted elsewhere that pointers cause problems with this
concept. Pointers to the object, or any sub-object will cause problems,
as will, recursively, any sub-object that is itself a pointer or
reference. I haven't figured out a clean way to re-state the concept so
as to avoid that problem. Can you come up with an example that doesn't
depend upon pointers or references?

Let me clarify what it is I'm claiming. I'm not denying the user-defined
nature of "equivalence" for Assignability in general. In general, it's
the responsibility of the user to resolve how equivalence is to be
defined in cases where pointers muddy the waters, and to make sure that
copy assignment preserves that definition. It could even be appropriate
for a user to define that the addresses must be equal after assignment
(if he's overriden operator&() in a way that makes that possible).

However, for each template, if it places any other requirements on a
type in addition to Assignable, and if those requirements can be
converted into a test for equivalence after assignment, then the type
must pass that test (at least for the values that are passed to the
template, and intermediate values that might come up during operation of
the template). That's the purpose of making Assignable a requirement for
that template; to allow it to freely use the copy in place of the
original, while exercising those other requirements.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Christopher Eltschka wrote:
[...some reasonable thoughts about the application of equivalence in the
mathematical sense to concepts]
> >
> > I'd say that two objects t and u are equivalent at a certain point of
> > execution if in the first subsequent expression that involves t it is
> > possible to substitute t with u without changing the program's
> > semantics.
>
> That's a bad definition IMHO. For a start, if two values a and b are
> considered equivalent should not depend on the point of execution.

Note that I didn't say "values", I said "objects". Assignment operates
on objects and it is on objects that the equivalence requirement is
expressed. The problem is that when objects are taken into account,
equivalence can only be defined in a context depending way (for
instance, it might hold as long as the objects' states do not change,
and we're back to your definition).

Cheers,
Nicola Musatti

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrea Ferro wrote:
[...]
> So far I agree.
>
> > In
> > other words equivalence is a propriety of the state of the objects and
> > not of the objects themselves.
>
> I'm not sure about that. I would say that equivalence is whatever the
> user expects to be mantained among different copies of the object. It
> may be everithing (but the object adress which is never mantainable) or
> even nothing at all. This may probably be "a property of the state of
> the object" in the sense that it is "whatever the user expects from the
> state of the object".

The problem is trying to express in objective terms the fact that
equivalence is whatever that means to the user, when he/she has the
power to define both the operation that has "equivalence" as a
postcondition and what that postcondition is. The only objective element
is the fact that we have a notion of how the operation (assignment in
our case) is defined by default and what kind of equivalence the default
operation supports.

> > I'd say that two objects t and u are equivalent at a certain point of
> > execution if in the first subsequent expression that involves t it is
> > possible to substitute t with u without changing the program's
> > semantics.
>
> If you mean that the program semantics are what the programmer want the
> program to do (or accepts that the program does), yes. However using t
> or u MAY change the program *behaviour* (what it does or the results it
> gives). Of course as far as this is what the programmer expects.

Let's go back to our original context, that is, standard containers.
Containers provide a way to store and retrieve objects. In this context
equivalence means that whenever the user stores an object and later
retrieves it, the container is free to return an object that is obtained
by assigning the original object to another object of the same type
(let's assume that storing and retrieving takes place by reference or
pointer, so that copying doesn't come into play).

Again, the user is free to define things in such a way that the
equivalence property holds only in specific portions of the code. This
is what I was trying to say with my definition.

Cheers,
Nicola Musatti

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Mon, 14 Jan 2002 15:59:08 GMT, "Andrea Ferro" <AndreaF@UrkaDVD.it>
wrote:

>"Andrea Griffini" <agriff@tin.it> wrote in message
>news:3c3fe0fd.2891372@news.interbusiness.it...
>....
>> But *why* are we trying to define equivalence for user defined
>> types ??? In my opinion this added complexity isn't worth the
>> effort.
>
>ROTFL.
>
>Actually you are the OP who started the thread!

I tried to explain my point of view in a longer message
that somewhat didn't make it to this newsgroup (i tried
twice, with no errors or refusal notices from moderators
but without seeing my message appearing).

Anyway while it's true that it was my posting stating
that "equivalent" was an undefined and not obvious term
in that context, this doesn't mean that the solution is
to define clearly the term.

In my opinion it would be better to actually *drop*
the "Assignable" and "CopyConstructible" fuzzy concept
from the language, specifying instead the actual
behaviour constraint we need in the single cases... and
telling that library implementers may use any
combination of destruction/copy construction, assignment
and std::swap to "move" elements around.

What does this really mean for a class it's not a
problem of the library.

What need "protection" are just algoritms in which
for example "movement" and "comparision" are used at
the same time, if it's a problem for the algorithm
to be able to promise anything otherwise (sort comes
to mind).

>We can *define* "equivalence" for user defined types saying it is
>"whatever the user considers the value bearing part of the type"
>(payload?).

What does such a requirement really add ? I think
the standard should describe something tied to
a program text, not to the *meaning* one may give to
a program text. So either it's defined what happens
putting a specific type in a container, or it's not
defined. This can't IMO be dependent on what one
*thinks* is the meaning of the program.

>But we cannot *specify* what that is unless we are in the context of the
>class. That is only in the context of the class semantic this have a
>sense. Therefore the generic specification must be as fuzzy as "whatever
>have sense in the context of the class semantic specification".

This would IMO just add smoke to the confusion.

I think it would be better to not cover this
area at all. In my longer post I elaborated a
bit a couple of other possibilities (defining
object equivalence using code equivalence - the
proposal you made in our italian newsgroup -
and defining equivalence using operator==
in the same way operator= defines assignment)
but seems to me that a less invasive and better
solution would be just avoiding this fight.

Andrea


======================================= MODERATOR'S COMMENT:

I approved two long articles from you earlier today. It can take as
long as 48 hours from when you submit an article until it appears
at your news server.
---
Steve Clamage, stephen.clamage@sun.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrea Ferro wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3C40C4B5.27A4B8EB@wizard.net...
...
> > In general, "equivalence" may be a fairly fuzzy concept. I think of it
> > in recursive terms: t and t_copy are equivalent, if for any arbitrary
> > expression involving t (which I'll represent metaphorically as
> func(t)),
> > func(t) is equivalent to func(t_copy). This seems to get us nowhere,
> but
> > the recursion terminates if it reaches a type that is
> > EqualityComparable. In that case, equivalence is ensured if "=="
> returns
> > true.
>
> You cannot define equivalence in that way. Unless func(t) returns a copy
> of t (and if so you are eating your own tail). Most probably func(t)
> returns a completelly different type. And the definition of equivalence
> for that type may be different than the one for T.

That's the whole point. func(t) will in general produce a different type
than t, and the definition of equivalence for the new type (if there is
one) will contrain the definition of equivalence for the orginal type.
The key is to repeat this recursively until you come to an
EqualityComparable type, for which 'a is equivalent to b' corresponds to
'a==b', a testable requirement.

...
> > Also, if the object contains a
> > pointer member, it's debatable whether equivalence requires that
> t_copy
> > must contain a copy of that pointer, or a pointer to a copy of the
> > pointed-at object.
>
> It is debatable that ANY member should be the same. Not only pointer
> members.

If a template's requirements specify one or more of the members that a
type must possess, then those members, at least, must have equivalent
values.

...
> > My point is that for any expression that is permitted, I think a
> > template is allowed to spontaneously test it for equivalent behavior,
> > even if such a test is not part of the definition of the template.
> > Complexity requirements might prohibit such a test (as in
> > std::replace<>), but otherwise it should be OK.
>
> But you must restrict it pretty much. Is operator< on vectors a
> "permitted expression"? THe answer is *no* in the contect of vector. The
> implementation of vector cannot instantiate it's operator<. That is
> another template.

'<' is a permitted operation on the elements of a vector, at least if
it's used from within the function that is invoked by the expression
'a<b', where 'a' and 'b' are vectors.

> Whenever the standard requires Assignable only or CopyConstructible only
> or both of these and nothing else than there's some concept of
> equivalence of instances of T behind the scenes. Still the template
> cannot access anything about those instances but the instances themself
> and their adresses. There's no possible spontaneous test it can make.

That depends upon what other requirements there are on the template.
It's not true in general. For instance, output iterators are not only
required to be Assignable, they're also required to support all of the
other expressions defined for output iterators - any template that takes
an OutputIterator argument is allowed to depend upon that. One of the
arguments for std::replace<> is not only required to be Assignable, but
it's required to support either pred(*i)==old_value, or *i==old_value,
depending upon which form you use. The Key type for associative
containers is not only supposed to be Assignable, it's also required to
allow comp(k1,k2). The types used by the Generalized Numeric Alogorithms
defined in 26.4 are not only required to be Assignable, but also to
support the non-generic forms of those operations.

It's possible to insert a spontaneous test of equivalence into any of
those, except for std::replace<>(), where the complexity requirement
interferes.

[re: standard containers]
> > Yes, but if Assignable and CopyConstructible are both required, then
> the
> > two requirements can be used together. For this particular pair of
> > requirements, the consequence is that any arbitrary sequence of copy
> > assignment and copy constructor calls is required to result in an
> object
> > equivalent to the original.
>
> Sure. But the question is exactly this: what does "equivalent" mean.
> Note that there's absolutely no way for the template to test that
> equivalence.

Yes there is, inside the implementation of "a<b".

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Bernd Strieder" <strieder@rhrk.uni-kl.de> wrote in message
news:a1l50m$718$1@news.uni-kl.de...
> James Kuyper Jr. wrote:
....
> I understood same behaviour as stricter than equality, i.e. equality
is
> implied, that's my "consequently".

Disagreed. Equality is not implied by "Same behavior". You can define
equality in different ways. You could say that equality is the C++
operator== or that equality is defined in terms of the c++ < operator
(that is the equality the standard defines for ordered stuff and is
based on an ordering relation instead of an equvalence relation.

In any case let's give a symbol to "Same behavior" and say $ is a binary
"Same behavior" operator.

That is a type is Assignable iff after "a=b" (assigning b to a) it holds
that "a$b" is true.

By definition we have that "a$a" is always true.

Can we say something about the relationship between $ and == ?
Absolutely not.

First of all $ is always defined for all types, while == is not. There
are assignable types that do not support operator== at all. And there
need not even be an ordering relation on them nor it must be defined
operator <.

Even if operator== is defined, you cannot assume that a$b => a==b. As a
matter of fact not for all types a==a is true. But a$a is. By
definition.

> Same behaviour is far too weakly defined
> in this discussion,

The discussion is about how to define it. And my position is that it
cannot be defined a-priori. It is really dependent on the semantics of
the class.

> and I have no clear idea how to define it reasonably.

exactly.

> >> Perhaps it's worth defining levels of Object Equality Guarantees
for
> >> composed objects. How do the equality of the components and the
whole
> >> object interact in the course of copy c'tor calls and assignments.

IMO it can be defined and can be usefull to document it in the class.
But it has nothing to do with "Same behavior". As I told you
"equivalence" in the way used by the standard when definining
assignable, is different and unrelated to equality as implemented by
operators.

An object can be assignable (and hence the copy equivalent to the
original) and still have one or more members that return different
results if called on the copy or on the original. Of course those
members must not be related to the part of the object that has something
to do with it being "equivalent" to another instance of the same class.

> The levels are sufficient to characterize the different possibilities,
> those where equality after assignment/copy is enforced, those where no
> equality is enforced and those where it depends on other factors. Most
of
> the stuff in the std library will depend on the level of the types
passed
> in as template parameters. The builtin-types enforce equality, and
there
> might be user-defined types enforcing equality as well as not
maintaining
> equality. With those three levels it is possible to describe the
guarantees
> of the std classes in terms of the types passed in using only a few
words
> each.

I can agree on this. Defining and documenting what happens is always
desirable.

> 1. What happens to std::sort if in the course of moving the items
around
> some important equivalence e.g. equality is not maintained? I have
seen
> optimized implementations of sorting algorithms that would crash. Most
sort
> algorithms do not need testing equality of the items, so in general
there
> is no equivalence corresponding to equality.

Correct. But you've lost the original meaning of "equivalence".
Equivalence (English word) can mean meny things. Equality is *one kind*
of equivalence. Your own words "some important equivalence" mean there
are many kind of. But the equivalence we were discussing (at least the
one intended by the OP) was the one the standard requires for
"Assignable". If copying objects around equality is not mantained this
does not (generally) mean that the objects were assignable and are not.
Either the objects were not assignable (and therefore a copy would not
be equivalent to the original to begin with) even if a given pair of
them compared equal, or they were assignable (and a copy will be
equivalent to the original) even if the copy does not compare equal to
the original (the original could even fail to compare equal to itself
and still be assignable).

> 2. What happens to std::vector<T>::operator== if T::operator= does not
> maintain equality? It would just return false, where somebody would
have
> expected true. But in this case this is defined behaviour, given T as
> implemented.

If operator= does not mantain equality then not much you can say of
std::vector<T>::operator==. But again we are not discussing equality. We
are discussing equivalence in the meaning it has in the definition of
assignable. The fact that the objects do not mantain equality does not
imply they are not assignable.

> ad 1. std::sort requires items of level 1 in terms of the item type
and the
> comparision function used, i.e. after being assigned or copied
> corresponding items must have the same comparision result. Using items
of
> level 3 gives undefined behaviour of std::sort.

So what? How does this relate to the objects bein assignable and a copy
being equivalent to the original?

> ad 2. The std::vector<T> template is of level 2 in terms of T, i.e. it
has
> the same level as T. The actual type will be either level 1 or level
3.
> I.e. copying the vector will maintain equality if and only if copying
T
> objects does so. Some people use vector::operator==, others
> std::binary_search with T::operator< only in some concrete cases. What
is
> the essential equivalence of the type T used as an Assignable in both
cases?

Good question. The type T can be assignable independent of the results
of T::operator== (not to mention the result of vector<T>::operator==).
That's exactly why equivalence as intended in the definition of
assignable has no relation to operator== (and equality).

> As far as I understand, somebody tried to include this equivalence
stuff
> into Assignable to no have to write down something at many places
where
> Assignable is used. To be able to write it once for many the precision
has
> to be dropped. The problem is clearly, that there is real code, where
that
> equivalence is not computable or not of interest.

Equivalence is related to Assignable. Equality is not. Computability if
equality and interest in equality has no relation to equivalence (again:
the meaning of equivalence in the definition of Assignable). Equivalence
may or may not be computable and may or may not be of interest, but it
IS of interest if the type is to be assignable.

> The honest objective of mentioning the equivalence was to remember
that
> there often is an important relation between Assignable and some
> equivalence in many standard containers and algorithms.

Correct. *Some* equivalence. The subject is exactly this: what is object
equivalence? My answer, so far, is: whatever makes sense in the context
(by the semantics) of the class. Nothing more can be specifyed without
knowing the semantics of the class.

> It is not nice to culminate that many notions of equivalence in some
> mysterious wording in Assignable. It should be removed from
Assignable,
> which is the problem this thread is about, that imprecise
"equivalence" at
> that place, where nobody can understand it easily.

If I undestand you correctly you mean that the term "equivalence" can be
somewhat too much overloaded of meaning to be usefull in the definition
of Assignable. I can buy this easily. But of course to change the
definition of assignable and use some other term, we must first answer
this question: what is the meaning of "equivalence" in the context of
the definition of assignable? This (reworded) question is what the OP
asked. And I see no way to specify it any better than "whatever makes
sense" (as I wrote above).

--

Andrea Ferro

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3C3E4E0D.451B4AE8@wizard.net...
> Andrea Ferro wrote:
....
> Keep in mind that "same behavior" is only my interpretation of what
the
> standard means by "equivalent". The standard does not define the term
in
> this context.

Ok so far. I was also intending "same behavior" as the meaning of
"equivalent" the standard intends when defining Assignable. The standard
does not define the term exactly as you (we) are not defining "Same
Behavior". And for the same reason: there's no way to do it without
knowing more about the actual class.

Note that if "equivalent" is somewhat fuzzy as a requirement and pretty
open to interpretations much more stict than actually required, so is
"Same bevavior".

> You may wish to use a standard template, with a fairly lax
> interpretation of "equivalent" as "producing the same behavior in some
> contexts, but not in others". However, I think an implementation would
> be entirely within it's rights interpret "equivalent" as requiring
"same
> behavior in all contexts".

Yes, I could use a standard template (more specifically a standard
container, that is when Assingnable is required) with fairly lax
interpretation of "equivalent" (or "same behavior").

However NO. The implementation (the container implementation, to be
specific) cannot require same bevavior in all contexts. Only in contexts
that are part of the template specification. In other words you know in
advance what methods will be called by the implementation and what the
implementation expect them to do. As far as Assignable is concerned the
only method is operator=. The containers require Assignable and
CopyConstructible. If operator= is the only function (member or not)
related to Assiggnable, CopyConstructible is concerned with the copy
constructor (must be working with both const and not const
initializers), the destructor and the adress of operator.

The standard is actually even more restrictive than this. Only the
specific expressions are required to make sense and give the requred
results (&v must be the adress, all the rest is defined in term of
"equivalence"). Therefore the template implementation cannot use
anything but those expressions.

Therefore you can be sure that a conforming implementation will not call
nor rely on any member but those you eventually call and rely upon to
make those expressions work.

Note, for example, that not even the default constructor can be called
from within the template implementation. It must be defined only if you
(it's you upon calling, not the implementation) make use of the default
values defined for of some of the container methods. The implementation
CANNOT call those methods relying on the defaults.

When you say:

> > > for 'int'. If, for instance, a seperate requirement calls for
func(t)
> > to
> > > be a function with no side effects that returns an integer, a
> > conforming
> > > implementation of that template could set t_copy=t, and then
> > arbitrarily
> > > check whether func(t)==func(t_copy). It could do so, whether or
not
> > such
> > > a check was part of the specification of that template, so long as
> > > complexity requirements allowed an extra call to func().

you are correct only if func itself does not make use of anything exept
what is required by Assignable and CopyConstructible. That is, of
course, that whatever that integer comes from it does not come from your
object because the only information that can be taken from your object
and can influence the value of that integer is the object address. And
by itself the address changes if you do a copy. Also accessing anything
withing the object memory from that adress (beside the fact that you
could be going into undefined stuff if you do) gives no guarantee. Each
and every bit in the object can change at any time and the object still
would be assignable and valid for the container.

> The approach you're suggesting means that the only way an implementor
> can know whether he's implemented the template correctly, is by
checking
> with each potential user to find out what definition of "same
behavior"
> that user is planning to use. I doubt that this was the intent of the
> standard.

Nope. The only way an implementor can know whether he's implemented the
template correctly, is by checking with the standard. And verifying that
he does not operate on the object(s) with any other expression but the
ones the standard requires on the object (see above) and still satisfy
all the requirements for each and every member of the template.

--

Andrea Ferro

---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info http://www.brainbench.com/transcript.jsp?pid=2522556

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Nicola Musatti" <objectway@divalsim.it> wrote in message
news:3C3EBF26.1C54EFA9@divalsim.it...
> After reading this thread I came to the conclusion that "equivalence"
is
> proving difficult to define because the use of the term in mathematics
> is misleading. The problem is that mathematical equivalence is defined
> between immutable entities, which of course C++ objects are not.

So far I agree.

> In
> other words equivalence is a propriety of the state of the objects and
> not of the objects themselves.

I'm not sure about that. I would say that equivalence is whatever the
user expects to be mantained among different copies of the object. It
may be everithing (but the object adress which is never mantainable) or
even nothing at all. This may probably be "a property of the state of
the object" in the sense that it is "whatever the user expects from the
state of the object".

> I'd say that two objects t and u are equivalent at a certain point of
> execution if in the first subsequent expression that involves t it is
> possible to substitute t with u without changing the program's
> semantics.

If you mean that the program semantics are what the programmer want the
program to do (or accepts that the program does), yes. However using t
or u MAY change the program *behaviour* (what it does or the results it
gives). Of course as far as this is what the programmer expects.

--

Andrea Ferro

---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info http://www.brainbench.com/transcript.jsp?pid=2522556

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Fri, 11 Jan 2002 12:09:42 CST, Nicola Musatti
<objectway@divalsim.it> wrote:

>After reading this thread I came to the conclusion that "equivalence" is
>proving difficult to define because the use of the term in mathematics
>is misleading. The problem is that mathematical equivalence is defined
>between immutable entities, which of course C++ objects are not. In
>other words equivalence is a propriety of the state of the objects and
>not of the objects themselves.

Immutable ? Just add in another variable (let's invent a nice
name for it... hmmm... "t" should do ;) ) and problem is solved.

>I'd say that two objects t and u are equivalent at a certain point of
>execution if in the first subsequent expression that involves t it is
>possible to substitute t with u without changing the program's
>semantics.

You're hiding the problem behind another fuzzy word (semantics).

Unless of course you mean with that the observable behaviour
and equivalence of code that's somewhat clearly defined... but
this would make std::string and std::vector (and tons of other
quite useful classes) not "assignable" nor "copyconstructible".

But *why* are we trying to define equivalence for user defined
types ??? In my opinion this added complexity isn't worth the
effort.

Andrea

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrea Ferro wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3C3E4E0D.451B4AE8@wizard.net...
> > Andrea Ferro wrote:
...
> Note that if "equivalent" is somewhat fuzzy as a requirement and pretty
> open to interpretations much more stict than actually required, so is
> "Same bevavior".

In general, "equivalence" may be a fairly fuzzy concept. I think of it
in recursive terms: t and t_copy are equivalent, if for any arbitrary
expression involving t (which I'll represent metaphorically as func(t)),
func(t) is equivalent to func(t_copy). This seems to get us nowhere, but
the recursion terminates if it reaches a type that is
EqualityComparable. In that case, equivalence is ensured if "==" returns
true.

I'll freely admit that the presence of pointers and references presents
problems for this approach: if you were to allow &t as the testing
expression, nothing would qualify as equivalent to the original, except
the original (or a reference to it). Also, if the object contains a
pointer member, it's debatable whether equivalence requires that t_copy
must contain a copy of that pointer, or a pointer to a copy of the
pointed-at object.

...
> However NO. The implementation (the container implementation, to be
> specific) cannot require same bevavior in all contexts. Only in contexts
> that are part of the template specification. In other words you know in

Agreed - the only thing a template can actually test is the behavior of
expressions containing instances of the type, which are known from the
requirements on that template to be valid expressions. For instance,
"a<b", where 'a' and 'b' have the type std::vector<T>, is allowed to
test "t1<t2" for equivalent behavior, because the validity of that
expression is implied by the standard's definition of "a<b". However,
it's not allowed to test "t1>t2", because that's not guaranteed to be a
valid expression.

My point is that for any expression that is permitted, I think a
template is allowed to spontaneously test it for equivalent behavior,
even if such a test is not part of the definition of the template.
Complexity requirements might prohibit such a test (as in
std::replace<>), but otherwise it should be OK.

> advance what methods will be called by the implementation and what the
> implementation expect them to do. As far as Assignable is concerned the
> only method is operator=. The containers require Assignable and
> CopyConstructible. If operator= is the only function (member or not)
> related to Assiggnable, CopyConstructible is concerned with the copy
> constructor (must be working with both const and not const
> initializers), the destructor and the adress of operator.

Yes, but if Assignable and CopyConstructible are both required, then the
two requirements can be used together. For this particular pair of
requirements, the consequence is that any arbitrary sequence of copy
assignment and copy constructor calls is required to result in an object
equivalent to the original.

> When you say:
>
> > > > for 'int'. If, for instance, a seperate requirement calls for
> func(t)
> > > to
> > > > be a function with no side effects that returns an integer, a
> > > conforming
> > > > implementation of that template could set t_copy=t, and then
> > > arbitrarily
> > > > check whether func(t)==func(t_copy). It could do so, whether or
> not
> > > such
> > > > a check was part of the specification of that template, so long as
> > > > complexity requirements allowed an extra call to func().
>
> you are correct only if func itself does not make use of anything exept
> what is required by Assignable and CopyConstructible. That is, of

Incorrect; I specified that the validity of func() was mandated by one
of the other requirements on this template. A template's implementation
may rely simultaneously on all of the requirements specified for that
template, not just on each one seperately.

> course, that whatever that integer comes from it does not come from your
> object because the only information that can be taken from your object
> and can influence the value of that integer is the object address. And

Not if the template's requirements state what func(t) is supposed to
mean.

> by itself the address changes if you do a copy. Also accessing anything
> withing the object memory from that adress (beside the fact that you
> could be going into undefined stuff if you do) gives no guarantee. Each
> and every bit in the object can change at any time and the object still
> would be assignable and valid for the container.

If an additional requirement on the template is that func(t) must be a
valid expression, then func(t_copy) must also be a valid expression,
with equivalent value. Any other interpretation of "equivalent" seems
nonsensical to me.

...
> > The approach you're suggesting means that the only way an implementor
> > can know whether he's implemented the template correctly, is by
> checking
> > with each potential user to find out what definition of "same
> behavior"
> > that user is planning to use. I doubt that this was the intent of the
> > standard.
>
> Nope. The only way an implementor can know whether he's implemented the
> template correctly, is by checking with the standard. And verifying that
> he does not operate on the object(s) with any other expression but the
> ones the standard requires on the object (see above) and still satisfy
> all the requirements for each and every member of the template.

That is insufficient to guarantee safe behavior. Unless the equivalence
required by Assignable and CopyConstructible means that func(t) produces
the same result as func(t_copy), then the template is not free to copy
any value. It would only be able to work on the originals, because if it
worked on a copy, it might get different results. The number of standard
templates where Assignable is required, that can actually do what
they're supposed to without ever performing copy-assignment, is 0.
That's not a coincidence.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3C40C4B5.27A4B8EB@wizard.net...
> Andrea Ferro wrote:
> >
> > "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> > news:3C3E4E0D.451B4AE8@wizard.net...
> > > Andrea Ferro wrote:
> ...
> > Note that if "equivalent" is somewhat fuzzy as a requirement and pretty
> > open to interpretations much more stict than actually required, so is
> > "Same bevavior".
>
> In general, "equivalence" may be a fairly fuzzy concept. I think of it
> in recursive terms: t and t_copy are equivalent, if for any arbitrary
> expression involving t (which I'll represent metaphorically as func(t)),
> func(t) is equivalent to func(t_copy). This seems to get us nowhere, but
> the recursion terminates if it reaches a type that is
> EqualityComparable. In that case, equivalence is ensured if "==" returns
> true.
>
> I'll freely admit that the presence of pointers and references presents
> problems for this approach: if you were to allow &t as the testing
> expression, nothing would qualify as equivalent to the original, except
> the original (or a reference to it). Also, if the object contains a
> pointer member, it's debatable whether equivalence requires that t_copy
> must contain a copy of that pointer, or a pointer to a copy of the
> pointed-at object.

I would say that equivalence in this context means that the user of the
template shouldn't care whether we keep the copy or the original. What it is
that determines whether or not the user cares is up to them. However, in the
case of operations that the standard template is required to perform upon
the objects, the user _is_ the standard template, and in this case
equivalence implies that the operation should yield the same result if
either the copy or the original is used.

Note that equivalence is a requirement placed on the type _by_ the standard
template, with the statement that the template behaviour is undefined if the
type is not equivalent. Therefore if the user provides a type for which
copies are not equivalent _for their needs_, then they cannot expect
anything meaningful from the standard template.

> ...
> > However NO. The implementation (the container implementation, to be
> > specific) cannot require same bevavior in all contexts. Only in contexts
> > that are part of the template specification. In other words you know in
>
> Agreed - the only thing a template can actually test is the behavior of
> expressions containing instances of the type, which are known from the
> requirements on that template to be valid expressions. For instance,
> "a<b", where 'a' and 'b' have the type std::vector<T>, is allowed to
> test "t1<t2" for equivalent behavior, because the validity of that
> expression is implied by the standard's definition of "a<b". However,
> it's not allowed to test "t1>t2", because that's not guaranteed to be a
> valid expression.
>
> My point is that for any expression that is permitted, I think a
> template is allowed to spontaneously test it for equivalent behavior,
> even if such a test is not part of the definition of the template.
> Complexity requirements might prohibit such a test (as in
> std::replace<>), but otherwise it should be OK.

Agreed --- unless the standard places limits on the number of copies, or the
number of times an expression is evaluated by a template, the code can
perform any additional copies and evaluations of expressions required to
validate equivalence from the point of view of the template.

> > advance what methods will be called by the implementation and what the
> > implementation expect them to do. As far as Assignable is concerned the
> > only method is operator=. The containers require Assignable and
> > CopyConstructible. If operator= is the only function (member or not)
> > related to Assiggnable, CopyConstructible is concerned with the copy
> > constructor (must be working with both const and not const
> > initializers), the destructor and the adress of operator.
>
> Yes, but if Assignable and CopyConstructible are both required, then the
> two requirements can be used together. For this particular pair of
> requirements, the consequence is that any arbitrary sequence of copy
> assignment and copy constructor calls is required to result in an object
> equivalent to the original.

Agreed.

Basically it boils down to this (IMHO):

Objects t1 and t2 of type T are equivalent when used in a given context if
any expression involving t1 that is required to be valid for the given
context would yield an equivalent result with if t2 was substituted for t1.

When a type is used with a Standard Library template, that requires
equivalence of a certain class of values of that type (such as Assignable
requires that values are equivalent after t1=t2), the context is all valid
operations implied by all requirements for the use of that template, and any
additional user-specified conditions. If they user requires that func(t1)
and func(t2) return the same result for t1 and t2 to be equivalent, but
there is no requirement placed on func() by the standard library template,
then the standard library cannot check for this notion of equivalence, and
the user can expect undefined behaviour if they use a type with the template
for which func(t1) and func(t2) do not return the same result in those
contexts where the template requires equivalent values.

Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optical Components Ltd
The opinions expressed in this message are not necessarily those of my
employer



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

James Kuyper Jr. wrote:

> Bernd Strieder wrote:
> Assignable is what you use to justify a template's use of the expression
> "a=b" in a meaningful way - the requirement tells the implementor what
> the operation is required to mean, which is otherwise completely
> arbitrary. EqualityComparable serves the same purpose for "a==b",
> LessThanComparable does it for "a<b", CopyConstructible does it for
> "a(b)", and DefaultConstructible does it for "T()". That strikes me as a
> quite reasonable, clean, concrete, and independent set of requirements,
> that can be mixed and matched as needed. I don't see your levels as
> serving anywhere near as clear a purpose. To the extent that they are
> useful, I think that they correspond to particular combinations of the
> existing requirements.

It was not my intention to replace these concepts, but to specify their
relations, where appropriate. Those concepts themselves are not appropriate
places, but wherever they are used, there is enough information.

IMO mentioning "equivalence" in the description of Assignable does not help
anybody, so it should be removed. There is no specific, reasonable "object
equivalence" of an Assignable. There are methods, e.g. many operator==,
reasonability relying on some equivalence relation additionally maintained
by an Assignable during assigment. Assigment itself does not need this
equivalence relation. Somebody not calling the other methods would never
care about it. This is the freedom I mentioned in an earlier post, no
requirement to any specific behaviour.

Wherever assignment or copying might interact with other methods of a type
in the standard, it should be mentioned. std::vector<T>::operator== depends
on the relation of T::operator= to T::operator== after
std::vector<T>::operator= has been called. std::sort<RandomIterator>
depends on the relation of RandomIterator::value_type::operator< to
RandomIterator::value_type::operator=. There, the equivalence relations
(important for users of objects) to be maintained by Assignables are hidden
in. They are not a property of the concepts Assignable,
EqualityComparable, LessThanComparable or whatever. I don't want to replace
these concepts, but describe some relations, which are not a property of
any single one of them. It should be mentioned in what cases of fulfilling
some equivalence relation, or not, there is undefined behaviour, correct,
but somewhat unexpected behaviour, and, finally, just correct behaviour.

Find a uniform way to describe these situations, find a reasonable place to
write it down, make it to be usable in user-defined code as well as the C++
standard, and I will stop arguing about it, forever. I'm sure that the
levels of object equivalence guarantees I have mentioned could be it after
some clarifying rework.

Bernd Strieder

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3C40C4B5.27A4B8EB@wizard.net...
> Andrea Ferro wrote:
> >
> > "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> > news:3C3E4E0D.451B4AE8@wizard.net...
> > > Andrea Ferro wrote:
> ...
> > Note that if "equivalent" is somewhat fuzzy as a requirement and
pretty
> > open to interpretations much more stict than actually required, so
is
> > "Same bevavior".
>
> In general, "equivalence" may be a fairly fuzzy concept. I think of it
> in recursive terms: t and t_copy are equivalent, if for any arbitrary
> expression involving t (which I'll represent metaphorically as
func(t)),
> func(t) is equivalent to func(t_copy). This seems to get us nowhere,
but
> the recursion terminates if it reaches a type that is
> EqualityComparable. In that case, equivalence is ensured if "=="
returns
> true.

You cannot define equivalence in that way. Unless func(t) returns a copy
of t (and if so you are eating your own tail). Most probably func(t)
returns a completelly different type. And the definition of equivalence
for that type may be different than the one for T.

> Also, if the object contains a
> pointer member, it's debatable whether equivalence requires that
t_copy
> must contain a copy of that pointer, or a pointer to a copy of the
> pointed-at object.

It is debatable that ANY member should be the same. Not only pointer
members.

> My point is that for any expression that is permitted, I think a
> template is allowed to spontaneously test it for equivalent behavior,
> even if such a test is not part of the definition of the template.
> Complexity requirements might prohibit such a test (as in
> std::replace<>), but otherwise it should be OK.

But you must restrict it pretty much. Is operator< on vectors a
"permitted expression"? THe answer is *no* in the contect of vector. The
implementation of vector cannot instantiate it's operator<. That is
another template.

Whenever the standard requires Assignable only or CopyConstructible only
or both of these and nothing else than there's some concept of
equivalence of instances of T behind the scenes. Still the template
cannot access anything about those instances but the instances themself
and their adresses. There's no possible spontaneous test it can make.

> > advance what methods will be called by the implementation and what
the
> > implementation expect them to do. As far as Assignable is concerned
the
> > only method is operator=. The containers require Assignable and
> > CopyConstructible. If operator= is the only function (member or not)
> > related to Assiggnable, CopyConstructible is concerned with the copy
> > constructor (must be working with both const and not const
> > initializers), the destructor and the adress of operator.
>
> Yes, but if Assignable and CopyConstructible are both required, then
the
> two requirements can be used together. For this particular pair of
> requirements, the consequence is that any arbitrary sequence of copy
> assignment and copy constructor calls is required to result in an
object
> equivalent to the original.

Sure. But the question is exactly this: what does "equivalent" mean.
Note that there's absolutely no way for the template to test that
equivalence.

My opinion is that it means "whatever makes sense in the context of T
semantics". That is: it is part of the definition of the type T.

> > When you say:
> >
> > > > > for 'int'. If, for instance, a seperate requirement calls for
> > func(t)
> > > > to
> > > > > be a function with no side effects that returns an integer, a
> > > > conforming
> > > > > implementation of that template could set t_copy=t, and then
> > > > arbitrarily
> > > > > check whether func(t)==func(t_copy). It could do so, whether
or
> > not
> > > > such
> > > > > a check was part of the specification of that template, so
long as
> > > > > complexity requirements allowed an extra call to func().
> >
> > you are correct only if func itself does not make use of anything
exept
> > what is required by Assignable and CopyConstructible. That is, of
>
> Incorrect; I specified that the validity of func() was mandated by one
> of the other requirements on this template. A template's
implementation
> may rely simultaneously on all of the requirements specified for that
> template, not just on each one seperately.

Whenever there's a separate requirement that is a separate requirement.
If the elements must satisfy, say, EqualityComparable, than the standard
is explicitely saying you that this relation must be part of the
equivalence. But the concept of equivalence is still there even if no
specific requirement is involved.

Let's rephrase the subject:
What is object "equivalence" in the context of deciding if
std::vector<T> is valid? s.o. in a context when only CopyConstructible
and Assignable are requirements.

> If an additional requirement on the template is that func(t) must be a
> valid expression, then func(t_copy) must also be a valid expression,
> with equivalent value. Any other interpretation of "equivalent" seems
> nonsensical to me.

Yes. If there are additional requirements. Many of these can be seen as
"restrictions" on the "equivalence" itself. That is if an additional
requirement is in place, it must be part of the "behavior" in "same
behavior" if we say that the original and the copy are equivalent iff
they have the "same behavior".

Still "equivalnece" (and therefore "same behavior") exist even when
there are no other requirements. To put instances of T into a vector
"equivalence" is required but there's no specific "third function"
specifyed. So there's no restriction on what "equivalent" means. Still
it must hold.

--

Andrea Ferro

---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info http://www.brainbench.com/transcript.jsp?pid=2522556

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Andrea Griffini" <agriff@tin.it> wrote in message
news:3c3fe0fd.2891372@news.interbusiness.it...
....
> But *why* are we trying to define equivalence for user defined
> types ??? In my opinion this added complexity isn't worth the
> effort.

ROTFL.

Actually you are the OP who started the thread!

In any case IMO:

We can *define* "equivalence" for user defined types saying it is
"whatever the user considers the value bearing part of the type"
(payload?).
But we cannot *specify* what that is unless we are in the context of the
class. That is only in the context of the class semantic this have a
sense. Therefore the generic specification must be as fuzzy as "whatever
have sense in the context of the class semantic specification".

--

Andrea Ferro

---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info http://www.brainbench.com/transcript.jsp?pid=2522556

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3C3E5632.4F35E501@wizard.net...
> Bernd Strieder wrote:
> >
> > James Kuyper Jr. wrote:
> >
> > > Bernd Strieder wrote:
> ...
> > I understood same behaviour as stricter than equality, i.e. equality
is
> > implied, that's my "consequently". Same behaviour is far too weakly
defined
>
> Well, if you define "same behavior" that way, of course that's true.
> However, I don't see that as a reasonable definition. "same behavior"
> merely implies that when you apply the "==" operator, you must get the
> same result with the copy as with the original. That doesn't place any
> restriction what the original's behavior was. If "t==a" returns false,
> then "same behavior" merely requires that "a==t", "t==t", and "a==a"
> must also return false.

Yes. I was also thinking that. In terms of my answer to James, given $
as the "same behavior" operator, you are saying that after  a$b =>
(a==b) == (a==a) == (b==b).
But I must disagree (at least in teory).

My reasoning is that there may be a type T that is assignable but for
wich not all data members are the same after the assignement and not all
the methods return the same result if called for the copy or for the
original. Still the type itself is assignable. Therefore, why should
operator== be different? Why cannot it be one of the members that return
a different result?

In theory, therefore, I must disagree with you. It really depends on how
equality is defined and how equivalence is defined. And they are
different things.

--

Andrea Ferro

---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info http://www.brainbench.com/transcript.jsp?pid=2522556

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Tue,  8 Jan 2002 17:02:52 GMT, joe.hotchkiss@baesystems.com wrote:

>The comparison function in question would probably be '<', so this is
>probably the same as !(k1 < k2) && !(k2 < k1)
>A similar definition presumably applies to any other uses of the word
>'equivalent' when applied to other values.

I don't think this can be the requirement. There is no
required order relation on elements you place in a
std::vector unless you pretend (for example) sorting it.
Not being forced to provide features you don't need
(like an order relation) is in my opinion important
for usability and I think it was part of the reasons
a few template rules are written as we know them.
It also required some efforts by compiler designers
(I suppose so: old versions of VC++ for example
suffered of this problem).

The equality operator (==) that James Kuyper cites was
of course my first thought... but I agree with him that
even requiring a definition of it just for containment
is too much.

Options to give a meaning to "equivalent" could be:

 - Recursive member-wise equality until you reach a
   fundamental type like integer

   I think this wouldn't be useful, as for example any
   standard container or even a non-COW string class
   wouldn't be usable in containers

 - Recursive member-wise equality until you reach a
   fundamental type UNLESS there is a bool operator==
   const accepting a const reference.

   This is probably viable solution, but to be
   in my opinion reasonable (coherent) this view
   should also be supported by a default synthesis
   of operator== for classes that don't provide one
   so that the requirement could be just about
   result of operator== on the two copies.
   There also would be a couple of little problems
   about the fact that "usual" operator== is symmetric
   and that both a freestanding operator== or a member
   operator== may be defined.

   I honestly can't think this is what was meant
   in that phrase, but I thin it would somewhat mimic
   current support of operator=.

 - Anything that would guarantee equivalent behaviour
   of use of the two objects

   I got a similar reply in our italian C++ newsgroup,
   but I think that's not a viable option. First of all
   to be able to consider it there should be rules
   about operator& (the unary one) otherwise even
   integers aren't "assignable".
   More important it would be in my opinion a way too
   stringent condition (the "as-if" rule is heavier
   that it may seem at first): for example I've not
   seen any std::vector implementation for which
   assignment also copies capacity() (in my opinion
   the implementation *cannot* copy capacity given
   current description of reserve()) and surely
   std::vectors of different capacities behave
   differently in an observable manner! (why otherwise
   introducing reserve() at all ?)

   Does this mean that std::vector<std::vector<...> >
   or std::vector<std::string> shouldn't be acceptable ?
   I think the last one is among the most used C++
   containers around... (with std::map<std::string,...>
   that would be invalid too).

There is already in the standard a description of
"equality comparable", needed by algorithms like
find, count or replace. That is a specific context,
however, and rules are stated clearly (even if I
think they're quite permissive: can == be non-const ?
can the result change if the test is repeated ? ...
there's no concept of "pure function" in C++ but I
think that if we want to tie a meaning to a
notation this is a part that can't be ignored).

So I'm still on the confused position of having no
(reasonable) idea of what equivalent means in the
Assignable and CopyConstructible definitions.

I think that probably would be better to just drop
the definitions going around the problem, by citing
(for example) that containers may use any
combination of:

 - assignment
 - copy construction
 - std::swap (with its default implementation
   or any user-provided specialization)

to move/copy things around without having the
standard trying to describe the meaning of those
operations on a user-defined data type (like it
doesn't try to describe what operator+ does on them).

Probably special guarantees should be required just
when things like ordering/comparisions are required
and when object copies/moves are required at the
same time (I mean that the undefined behaviour daemon
could be invoked if specific conditions aren't met:
sorting can be problematic if result of comparision
of two elements may change if repeated).

Andrea

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

James Kuyper Jr. wrote:

> Bernd Strieder wrote:
>> After t=u one could say that t is the same as u. The same in what sense?
>>
>> * Same behaviour, all methods produce the same results?
>> * t==u returns true
>> * t=u maintains an equivalence relation in the mathematical sense
>>
>> >From these possibilities only the last one is an option leaving enough
>> freedom. The problem is howto specify an equivalence relation without
>
> Enough freedom for what? I believe that the reason why any given
> template is specified as requiring an Assignable type, is so the
> template can use assignment freely to copy values around. "Same
> behavior" is precisely what I'd want to be sure of, before using t=u to
> make a copy of u. I don't think a requirement that allowed more freedom
> than "Same behavior" would do the job.

It is up to the concrete classes to define what "same behaviour" (which is
an equivalence relation itself) or the equivalence relation are. This
cannot be part of Assignable.

At the places where Assignable is used the expectations to it can be
specified more precisely. E.g. container items often have the
EqualityComparable requirement (used for find), using that it is easy to
express the equivalence relation. Another example might be std::sort which
requires an ordering on the items, which the equivalence relation the sort
algorithm relies on to be maintained by the assignment operator of the
items can be based upon.

It is difficult to define the semantics of assignment with nothing else
around, and in general there is nothing. Assignable is in the first place a
requirement that operator= is there. Whoever implements it should have to
specify more precisely what kind of equivalence is expected, and, more
interesting, how it relates to operator==.

There are classes representing real world objetcs where semantical equality
is algorithmically difficult or even impossible. So the only chance to
define some reasonable equality (a subset of the real equality) is
restricting to a syntactic level. This might satisfy requirements imposed
by e.g. EqualityComparable for container classes. It could be possible that
assignment causes changes at that syntactic level (e.g. changing orders of
sequences not influencing the semantics of that object).

In essence, I don't expect from a foreign class that a=b has a==b as a
postcondition. Consequently, I cannot expect that a and b show the same
behaviour after assignment. I do expect this from int, from vector<int>,
because I know they fulfill it.

Perhaps it's worth defining levels of Object Equality Guarantees for
composed objects. How do the equality of the components and the whole
object interact in the course of copy c'tor calls and assignments.

1. The strong guarantee: Assignment or copy of the whole must fail, given
that after copying whole::operator== does not return true, or for at least
one pair of corresponding components component::operator does not return
true.

2. The weak guarantee: Assignment or copy of the whole will produce objects
that whole::operator== returns true iff all component::operator== return
true on the corresponding pairs of components.

3. No guarantee: Assignment and copy of the whole object have no
implication on the results of operator==

The builtin types are trivially level 1, the standard container classes are
level 2, putting items of level 1 into objects of level 2 again produces
level 1.

Shallow assignment or copying almost automatically gives level 1, deep
copying level 2.

Similar levels could be done for every binary predicate of a composed
class. The terminology could be as handy in describing binary predicates as
the levels of exception safety are in describing the behaviour in the face
of exceptions. The most important point, that equivalence stuff could be
moved out of Assignable, and moved where it belongs, i.e. to the places
where Assignable is used and is implemented, resp.

Description of std::vector<T>
...
requirements: T is a model of Assignable,...
...
guarantees: weak object equality guarantee in terms of all those T objects
the range [begin(),end()) denotes.
...

> No; the reader can learn everything about equivalence relations that is
> needed for understanding the C++ standard, by looking as the definition
> of the EqualityComparable requirement.

Then there should be a reference everywhere the word equivalent comes up?

Bernd Strieder

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bernd Strieder wrote:
...
> In essence, I don't expect from a foreign class that a=b has a==b as a
> postcondition.

Agreed; you don't know that unless the they are also EqualityComparable.

> ... Consequently, I cannot expect that a and b show the same
> behaviour after assignment. ...

I don't think your "Consequently" is correct. There's no relationship
between those properties. Not quite true: the combination of "a and b
have the same behavior" and EqualityCompable would imply "a==b" as a
special case. However, without EqualityComparable, "a and b have the
same behavior" and "a==b" are logically independent.

> ... I do expect this from int, from vector<int>,
> because I know they fulfill it.

If you're implementing a template with a type parameter T that is
required to be Assignable, I believe you'll be just as justified in
expecting "same behavior" after copy assignment for T, as you would be
for 'int'. If, for instance, a seperate requirement calls for func(t) to
be a function with no side effects that returns an integer, a conforming
implementation of that template could set t_copy=t, and then arbitrarily
check whether func(t)==func(t_copy). It could do so, whether or not such
a check was part of the specification of that template, so long as
complexity requirements allowed an extra call to func(). Then, if the
check failed, the template itself could fail, for no other reason than
the fact that you passed it a type that wasn't actually Assignable. For
various complicated reasons, however, this is a possibility with little
practical significance.

> Perhaps it's worth defining levels of Object Equality Guarantees for
> composed objects. How do the equality of the components and the whole
> object interact in the course of copy c'tor calls and assignments.

Multiple levels are needed only if you're going to assign different
levels of requirements on different templates. Can you give an example
of two different standard templates where you'd want to specify
different levels of equality requirements?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3C3D2B40.BF399F3@wizard.net...
> Bernd Strieder wrote:
> ...
....
> > ... I do expect this from int, from vector<int>,
> > because I know they fulfill it.
>
> If you're implementing a template with a type parameter T that is
> required to be Assignable, I believe you'll be just as justified in
> expecting "same behavior" after copy assignment for T, as you would be
> for 'int'. If, for instance, a seperate requirement calls for func(t)
to
> be a function with no side effects that returns an integer, a
conforming
> implementation of that template could set t_copy=t, and then
arbitrarily
> check whether func(t)==func(t_copy). It could do so, whether or not
such
> a check was part of the specification of that template, so long as
> complexity requirements allowed an extra call to func(). Then, if the
> check failed, the template itself could fail, for no other reason than
> the fact that you passed it a type that wasn't actually Assignable.
For
> various complicated reasons, however, this is a possibility with
little
> practical significance.

Disagreed. Totally. The template should be able to do so ONLY if the
fact that the returned value of func() is preserved as part of the
meaning of "Same behavior". However the specific definition of "Same
behavior" could say that the original and the copy give same return
values form a set of members or other caracteristics that do not include
func(). It really depends on what func() does on the parameter. It
really depends if the returned value depends only on caracteristics of
the parameter that are preserved by whatever the definition of "Same
behaviour" is for that specific type and the semantics the type
implements (or is supposed to).

--

Andrea Ferro

---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info http://www.brainbench.com/transcript.jsp?pid=2522556

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

James Kuyper Jr. wrote:

> Bernd Strieder wrote:
> ...
>> In essence, I don't expect from a foreign class that a=b has a==b as a
>> postcondition.
>
> Agreed; you don't know that unless the they are also EqualityComparable.
>
>> ... Consequently, I cannot expect that a and b show the same
>> behaviour after assignment. ...
>
> I don't think your "Consequently" is correct. There's no relationship
> between those properties. Not quite true: the combination of "a and b
> have the same behavior" and EqualityCompable would imply "a==b" as a
> special case. However, without EqualityComparable, "a and b have the
> same behavior" and "a==b" are logically independent.

I understood same behaviour as stricter than equality, i.e. equality is
implied, that's my "consequently". Same behaviour is far too weakly defined
in this discussion, and I have no clear idea how to define it reasonably.
It is clear that the standard when changed to give this definition and
using it in combination with Assignable, then a lot of existing code would
be broken by definition, without need. It is possible to write correct code
without that definition.

>
>> ... I do expect this from int, from vector<int>,
>> because I know they fulfill it.
>
> If you're implementing a template with a type parameter T that is
> required to be Assignable, I believe you'll be just as justified in
> expecting "same behavior" after copy assignment for T, as you would be
> for 'int'.

No, this is not justified IMO, see above

>          If, for instance, a seperate requirement calls for func(t) to
> be a function with no side effects that returns an integer, a conforming
> implementation of that template could set t_copy=t, and then arbitrarily
> check whether func(t)==func(t_copy). It could do so, whether or not such
> a check was part of the specification of that template, so long as
> complexity requirements allowed an extra call to func(). Then, if the
> check failed, the template itself could fail, for no other reason than
> the fact that you passed it a type that wasn't actually Assignable. For
> various complicated reasons, however, this is a possibility with little
> practical significance.

This is why I introduced those levels, see below.

>
>> Perhaps it's worth defining levels of Object Equality Guarantees for
>> composed objects. How do the equality of the components and the whole
>> object interact in the course of copy c'tor calls and assignments.
>
> Multiple levels are needed only if you're going to assign different
> levels of requirements on different templates. Can you give an example
> of two different standard templates where you'd want to specify
> different levels of equality requirements?

The levels are sufficient to characterize the different possibilities,
those where equality after assignment/copy is enforced, those where no
equality is enforced and those where it depends on other factors. Most of
the stuff in the std library will depend on the level of the types passed
in as template parameters. The builtin-types enforce equality, and there
might be user-defined types enforcing equality as well as not maintaining
equality. With those three levels it is possible to describe the guarantees
of the std classes in terms of the types passed in using only a few words
each.

Some more examples:

1. What happens to std::sort if in the course of moving the items around
some important equivalence e.g. equality is not maintained? I have seen
optimized implementations of sorting algorithms that would crash. Most sort
algorithms do not need testing equality of the items, so in general there
is no equivalence corresponding to equality.

2. What happens to std::vector<T>::operator== if T::operator= does not
maintain equality? It would just return false, where somebody would have
expected true. But in this case this is defined behaviour, given T as
implemented.

ad 1. std::sort requires items of level 1 in terms of the item type and the
comparision function used, i.e. after being assigned or copied
corresponding items must have the same comparision result. Using items of
level 3 gives undefined behaviour of std::sort.

ad 2. The std::vector<T> template is of level 2 in terms of T, i.e. it has
the same level as T. The actual type will be either level 1 or level 3.
I.e. copying the vector will maintain equality if and only if copying T
objects does so. Some people use vector::operator==, others
std::binary_search with T::operator< only in some concrete cases. What is
the essential equivalence of the type T used as an Assignable in both cases?

As far as I understand, somebody tried to include this equivalence stuff
into Assignable to no have to write down something at many places where
Assignable is used. To be able to write it once for many the precision has
to be dropped. The problem is clearly, that there is real code, where that
equivalence is not computable or not of interest.

The honest objective of mentioning the equivalence was to remember that
there often is an important relation between Assignable and some
equivalence in many standard containers and algorithms.

It is not nice to culminate that many notions of equivalence in some
mysterious wording in Assignable. It should be removed from Assignable,
which is the problem this thread is about, that imprecise  "equivalence" at
that place, where nobody can understand it easily.

Bernd Strieder

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrea Ferro wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3C3D2B40.BF399F3@wizard.net...
> > Bernd Strieder wrote:
> > ...
> ....
> > > ... I do expect this from int, from vector<int>,
> > > because I know they fulfill it.
> >
> > If you're implementing a template with a type parameter T that is
> > required to be Assignable, I believe you'll be just as justified in
> > expecting "same behavior" after copy assignment for T, as you would be
> > for 'int'. If, for instance, a seperate requirement calls for func(t)
> to
> > be a function with no side effects that returns an integer, a
> conforming
> > implementation of that template could set t_copy=t, and then
> arbitrarily
> > check whether func(t)==func(t_copy). It could do so, whether or not
> such
> > a check was part of the specification of that template, so long as
> > complexity requirements allowed an extra call to func(). Then, if the
> > check failed, the template itself could fail, for no other reason than
> > the fact that you passed it a type that wasn't actually Assignable.
> For
> > various complicated reasons, however, this is a possibility with
> little
> > practical significance.
>
> Disagreed. Totally. The template should be able to do so ONLY if the
> fact that the returned value of func() is preserved as part of the
> meaning of "Same behavior". However the specific definition of "Same
> behavior" could say that the original and the copy give same return
> values form a set of members or other caracteristics that do not include
> func(). It really depends on what func() does on the parameter. It
> really depends if the returned value depends only on caracteristics of
> the parameter that are preserved by whatever the definition of "Same
> behaviour" is for that specific type and the semantics the type
> implements (or is supposed to).

Keep in mind that "same behavior" is only my interpretation of what the
standard means by "equivalent". The standard does not define the term in
this context. You may wish to use a standard template, with a fairly lax
interpretation of "equivalent" as "producing the same behavior in some
contexts, but not in others". However, I think an implementation would
be entirely within it's rights interpret "equivalent" as requiring "same
behavior in all contexts".

The approach you're suggesting means that the only way an implementor
can know whether he's implemented the template correctly, is by checking
with each potential user to find out what definition of "same behavior"
that user is planning to use. I doubt that this was the intent of the
standard.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bernd Strieder wrote:
>
> James Kuyper Jr. wrote:
>
> > Bernd Strieder wrote:
...
> I understood same behaviour as stricter than equality, i.e. equality is
> implied, that's my "consequently". Same behaviour is far too weakly defined

Well, if you define "same behavior" that way, of course that's true.
However, I don't see that as a reasonable definition. "same behavior"
merely implies that when you apply the "==" operator, you must get the
same result with the copy as with the original. That doesn't place any
restriction what the original's behavior was. If "t==a" returns false,
then "same behavior" merely requires that "a==t", "t==t", and "a==a"
must also return false.

> in this discussion, and I have no clear idea how to define it reasonably.
> It is clear that the standard when changed to give this definition and
> using it in combination with Assignable, then a lot of existing code would
> be broken by definition, without need. It is possible to write correct code
> without that definition.

Could you give me an example? The standard requires a type to be
Assignable in only a few places, and in every place it's required, for
various reasons I've been unable to come up with code that is otherwise
well-formed, where the difference between our points of view on this
issue matters. Otherwise, I would have posted such an example already.
It's quite frustrating, actually. In each case there's just a single
minor change in the standard that would have made such an example
possible.

...
> >> Perhaps it's worth defining levels of Object Equality Guarantees for
> >> composed objects. How do the equality of the components and the whole
> >> object interact in the course of copy c'tor calls and assignments.
> >
> > Multiple levels are needed only if you're going to assign different
> > levels of requirements on different templates. Can you give an example
> > of two different standard templates where you'd want to specify
> > different levels of equality requirements?
>
> The levels are sufficient to characterize the different possibilities,

Assignable is what you use to justify a template's use of the expression
"a=b" in a meaningful way - the requirement tells the implementor what
the operation is required to mean, which is otherwise completely
arbitrary. EqualityComparable serves the same purpose for "a==b",
LessThanComparable does it for "a<b", CopyConstructible does it for
"a(b)", and DefaultConstructible does it for "T()". That strikes me as a
quite reasonable, clean, concrete, and independent set of requirements,
that can be mixed and matched as needed. I don't see your levels as
serving anywhere near as clear a purpose. To the extent that they are
useful, I think that they correspond to particular combinations of the
existing requirements.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

After reading this thread I came to the conclusion that "equivalence" is
proving difficult to define because the use of the term in mathematics
is misleading. The problem is that mathematical equivalence is defined
between immutable entities, which of course C++ objects are not. In
other words equivalence is a propriety of the state of the objects and
not of the objects themselves.

I'd say that two objects t and u are equivalent at a certain point of
execution if in the first subsequent expression that involves t it is
possible to substitute t with u without changing the program's
semantics.

Cheers,
Nicola Musatti

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

James Kuyper Jr. wrote:

> Andrea Griffini wrote:
>>        Assignable requirements:
>>
>>        Expression: t=u
>>        Return type: T&
>>        Post-condition: t is equivalent to u
>>
>> What does "equivalent" mean in this phrase ?
>     [...]                                               One option
> would be to interpret "t is equivalent to u" as meaning that the
> expression "t==u" must have a value of "true". However, I think the
> authors intended something both less restrictive, and more so. I think
> they did not intend to require that an Assignable type define "t==u".

An Assignable not fulfilling this would be quite surprising, but only in
the cases operator== is given at all. The problem is to not mix up
EqualityComparable and Assignable. These concepts are split, although in
90% of the cases they interact strongly in the sense we expect.

After t=u one could say that t is the same as u. The same in what sense?

* Same behaviour, all methods produce the same results?
* t==u returns true
* t=u maintains an equivalence relation in the mathematical sense

>From these possibilities only the last one is an option leaving enough
freedom. The problem is howto specify an equivalence relation without
having a predicate defined. Only the programmer knows how to define it. The
standard could require that this predicate must exist. In fact, it does,
but very silently. BTW, does a reader of a C++ standard have to know about
equivalence relations?

There are similar problems with copy constructors, clone()-methods and
other Factory-methods that copy objects. The equivalence relation
maintained might even change in the course of time in a running system. So
in general this equivalence relation is difficult to handle, it might even
be non-recursive. It is clear that it is in the responsibility of the
programmers. It is not possible to describe the Post-Condition of assigning
an Assignable without deep knowledge about the actual type.

After all, my opinion is that the standard should not mention this
equivalence. This belongs into the "annotations", i.e. some textbook, or
more important into documentation of actual code. Using an entity without a
chance to define it properly to at least an interesting extent gives
confusing results.

Bernd Strieder

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"James Kuyper Jr." wrote:
> You're right, the standard does not define what is meant by "equivalent=
"
> in this case. Therefore, we have to fall back on ordinary english (or a=
t
> least, mathematical english, which isn't quite "ordinary"). One option
> would be to interpret "t is equivalent to u" as meaning that the
> expression "t=3D=3Du" must have a value of "true". However, I think the
> authors intended something both less restrictive, and more so. I think
> they did not intend to require that an Assignable type define "t=3D=3Du=
".
> However, I think that did intend to require that the value of 't' must
> be useable wherever the value of 'u' is, and if so used, it must have
> exactly the same effect.

>From the C++ standard:

23.1.2 Associative containers

3 The phrase =91=91equivalence of keys=92=92 means the equivalence relati=
on
imposed by the comparison and not the operator=3D=3D on keys. That is, tw=
o
keys k1 and k2 are considered to be equivalent if for the comparison
object comp,
      comp(k1, k2) =3D=3D false && comp(k2, k1) =3D=3D false.

The comparison function in question would probably be '<', so this is
probably the same as !(k1 < k2) && !(k2 < k1)
A similar definition presumably applies to any other uses of the word
'equivalent' when applied to other values.

Also,

25.3 Sorting and related operations

6 In the descriptions of the functions that deal with ordering
relationships we frequently use a notion of equivalence to describe
concepts such as stability. The equivalence to which we refer is not
necessarily an operator=3D=3D, but an equivalence relation induced by the
strict weak ordering. That is, two elements a and b are considered
equivalent if and only if !(a < b) && !(b < a).

which is a much clearer statement of what is meant by equivalence of
values.  I get the impression that '=3D=3D' would be expected to compare
more (all?) data members of two objects than '<', which may only look at
a few data members.

--=20
Regards,

Joe Hotchkiss,                      joe.hotchkiss@baesystems.com
Systems and Processing Group,       Tel: +44-20-8420-3523
Sensor Systems Division,            Fax: +44-20-8420-3960
BAE SYSTEMS Avionics Limited,
The Grove, Warren Lane,
Stanmore, Middlesex.
HA7 4LY, England.

http://joe.hotchkiss.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

joe.hotchkiss@baesystems.com wrote:
>
> "James Kuyper Jr." wrote:
> > You're right, the standard does not define what is meant by "equivalent"
> > in this case. Therefore, we have to fall back on ordinary english (or at

The key words there are "in this case".

...
> >From the C++ standard:
>
> 23.1.2 Associative containers
>
> 3 The phrase ??equivalence of keys?? means the equivalence relation


Which is a different case. That definition is specific to "equivalence
of keys" a phrase not used in the definition of the Assignable
requirement.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Bernd Strieder wrote:
>
> James Kuyper Jr. wrote:
...
> >     [...]                                               One option
> > would be to interpret "t is equivalent to u" as meaning that the
> > expression "t==u" must have a value of "true". However, I think the
> > authors intended something both less restrictive, and more so. I think
> > they did not intend to require that an Assignable type define "t==u".
>
> An Assignable not fulfilling this would be quite surprising, but only in
> the cases operator== is given at all. The problem is to not mix up
> EqualityComparable and Assignable. These concepts are split, although in
> 90% of the cases they interact strongly in the sense we expect.

I agree - that's why I don't think they intended to impose "t==u". If T
is not EqualityComparable, you may have u==u returning false for a
particular u. However, T could still be Assignable, in which case I
believe that t==u  and t==t must also return false.

> After t=u one could say that t is the same as u. The same in what sense?
>
> * Same behaviour, all methods produce the same results?
> * t==u returns true
> * t=u maintains an equivalence relation in the mathematical sense
>
> >From these possibilities only the last one is an option leaving enough
> freedom. The problem is howto specify an equivalence relation without

Enough freedom for what? I believe that the reason why any given
template is specified as requiring an Assignable type, is so the
template can use assignment freely to copy values around. "Same
behavior" is precisely what I'd want to be sure of, before using t=u to
make a copy of u. I don't think a requirement that allowed more freedom
than "Same behavior" would do the job.

...
> but very silently. BTW, does a reader of a C++ standard have to know about
> equivalence relations?

No; the reader can learn everything about equivalence relations that is
needed for understanding the C++ standard, by looking as the definition
of the EqualityComparable requirement.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Discussing and reading about std::sort and wether it must,
it can or it cannot call a user-defined specialization
of std::swap I've read something in the standard that
confuses me (well... just another thing that confuses me :D)

       lib.container.requirements

       ...

       Assignable requirements:

       Expression: t=u
       Return type: T&
       Post-condition: t is equivalent to u


What does "equivalent" mean in this phrase ?

I think I understand what is the equivalence of code
fragments (that is... the "as if" rule, that in my opinion
doesn't really get much because there are so many observable
behaviours in C++); but this context-free equivalence
of user-defined types is something that I can't imagine.

TIA
Andrea

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Andrea Griffini wrote:
>
> Discussing and reading about std::sort and wether it must,
> it can or it cannot call a user-defined specialization
> of std::swap I've read something in the standard that
> confuses me (well... just another thing that confuses me :D)
>
>        lib.container.requirements
>
>        ...
>
>        Assignable requirements:
>
>        Expression: t=u
>        Return type: T&
>        Post-condition: t is equivalent to u
>
> What does "equivalent" mean in this phrase ?
>
> I think I understand what is the equivalence of code
> fragments (that is... the "as if" rule, that in my opinion
> doesn't really get much because there are so many observable
> behaviours in C++); but this context-free equivalence
> of user-defined types is something that I can't imagine.

It's not the types that are required to be equivalent; 't' and 'u' have
the same type, so requiring that they have equivalent types would be
unnecessary. What are required to be equivalent are the values of 't'
and 'u'.

You're right, the standard does not define what is meant by "equivalent"
in this case. Therefore, we have to fall back on ordinary english (or at
least, mathematical english, which isn't quite "ordinary"). One option
would be to interpret "t is equivalent to u" as meaning that the
expression "t==u" must have a value of "true". However, I think the
authors intended something both less restrictive, and more so. I think
they did not intend to require that an Assignable type define "t==u".
However, I think that did intend to require that the value of 't' must
be useable wherever the value of 'u' is, and if so used, it must have
exactly the same effect.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]