Re: Portability of comparing pointers to void
Matthias Hofmann wrote:
"Jiri Palecek" <jpalecek@web.de> schrieb im Newsbeitrag
news:fg2lrn$2sar$1@ns.felk.cvut.cz...
Matthias Hofmann wrote:
template <> struct strict_weak_less<int>
{
bool operator()( int a, int b )
{
// Define any two elements
// to be incomparable unless
// they are equal.
return a != b;
No. What you have written is not a strict weak ordering, because it lacks
antisymmetry (you say "a is less then b whenever they are not equal").
What
you have in mind would probably mean "return false" here.
With "return false", I end up with only a single element in the set: 2.
That's OK. The set considers 2 and 4 equal if they are incomparable,
and "return false" renders any two integers incomparable.
int main()
{
std::set<int, strict_weak_less<int> > intset;
intset.insert( 2 );
intset.insert( 4 );
return 0;
}
This creates a set where all elements are incomparable with each other.
(I
If you created such a set, it would only consist of one element (in this
example, 2, AFAIK).
I just learned that my program crashes with 'a != b'. It seems like a
This is because "a!=b" is not a strict weak ordering, not even a partial
ordering at all.
strict weak ordering cannot be implemented, only a total ordering.
Otherwise, how do you create a set of elements that are both distinct and
incomparable?
You cannot. A set considers two incomparable elements as equal, although you
can distinguish them. For example, if you take a pair of integers and
define less by "a.first<b.first". This is not a total ordering (because
(1,2) and (1,3) are incomparable) but is a strict weak ordering. So if you
insert these two incomparable entities in a set, only one will remain
there. And this is exactly what map does.
have searched for a real life example for a strict weak ordering that is
not
a total ordering, but I have not found any. Does anyone know an
example?)
Sure. For example, ordering of strings or sets by their sizes. Note, that
if
you take your strict-weakly-ordered universe and partition it to classes
induced by the "incomparability" relation, you always get a linearly
ordered universe.
But ordering strings is a total ordering, isn't it? Because for strings,
if neither x < y nor y < x, the strings are equal. What about defining the
Well, there are many orderings of strings. For example, lexicographic (which
is total), prefix ordering "strstr(a, b)==a" and substring
ordering "strstr(a, b)!=0" (which are both partial, but not strict weak
orderings) and finally, you can order them by their
sizes "strlen(a)<strlen(b)" which is a strict weak ordering (and not
total), and this was what I referred to.
relation "<" as "is a descendant of" in a familiy tree? It satisfies the
condition that if x is incomparable with y and y is incomparable with z,
then x is incomparable with z. In other words, if x and y are siblings and
y and z are siblings, then x and z are siblings. It's also not a total
ordering because being siblings does not mean being equal.
This is not a strict weak ordering, because I am incomparable with my aunt,
my aunt is incomparable with my mother, which would imply I am incomparable
with my mother, and that is a contradiction. (no incest, please :-) )
2.) Why does the standard require a strict weak ordering for associative
containers, but guarantee a total ordering for std::less<T*> in
20.3.3/8? In
a strict weak ordering, the relation "neither a < b nor b < a" is
transitive, but does not mean equality. Incomparability only means
equality in a total ordering, but doesn't an associative container need
to
know whether two elements are equal in order to determine whether the
No, the containers treat such two elements as equal, without calling
operator==.
Yes, it uses operator< to find out wether two elements are equal. But
that's just my point: In a strict weak ordering, the relation "neither a <
b nor b < a" does not mean equality. Equality requires a total ordering,
But it does define an equivalence.
so how come the standard requires only a strict weak ordering for
associative containers?
It's useful, because it means there's only one function to be implemented
and only 1.5 tests are needed in order to descend one level in a binary
tree, it's useful because it lets you define equivalence used by the
container even if it's different from operator==, and it is sufficient to
implement any algorithm which requires a total ordering.
Please, note once again that for every strict weak ordering on a set S,
there is an equivalence ~ on S and S/~ (S factored by ~) is totally
ordered. And conversely, for every set S, equivalence on S ~ and totally
ordered set T of cardinality equal to S/~, if you take a bijection f
between T and S/~ and define an ordering on S: a<b iff f([a]_~)<f([b]_~)
then you'll get a strict weak ordering (much, MUCH better to draw the
images than describe with the words). So, strict weak orderings do not
really add a new quality beyond total orderings, it is just a convenience.
Regards
Jiri Palecek
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]