Mircea Neacsu wrote:
>
> I know that trying to find the why's behind the C++ standard is difficult
> but maybe someone can shed some light:
>
> Why is there a requirement for objects stored in any container to have a
> lexicographical order. It seems to me that there is nothing wrong with
> puting objects that have inherent ordering relation into a conatiner (what
> is a natural total ordering relation between threads?).

I assume you meant "have NO inherent ordering relation" ?

Assume you have a class template Container<T>. It meets the standard's
requirements in table 65 for a container with a value_type of T. Assume

 Container<T> a, b;

Then, if at some point your code says:

 if(a < b)

then there is a prerequisite: "< is defined for values of type T. < is a
total ordering relationship." However, that pre-requisite applies only
if you use one of these operators (directly or indirectly):

 a < b
 a > b
 a <= b
 a >= b

If you never use one of them, then T can be a type for which '<' doesn't
define a total ordering relationship. T could be a type for which '<'
isn't even defined.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I know that trying to find the why's behind the C++ standard is difficult
but maybe someone can shed some light:

Why is there a requirement for objects stored in any container to have a
lexicographical order. It seems to me that there is nothing wrong with
puting objects that have inherent ordering relation into a conatiner (what
is a natural total ordering relation between threads?).

Mircea Neacsu
mailto:mircea@videotron.ca

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Mircea Neascu write:

> Why is there a requirement for objects stored in any container to have a
> lexicographical order. It seems to me that there is nothing wrong with
> puting objects that have inherent ordering relation into a conatiner (what
> is a natural total ordering relation between threads?).

It looks like you are mixing concepts here. There no need for stored objects
to exhibit some sorting behavior, unless this is needed either by the
internal structure of the container (like set or map) or you use some
sorting algorithm or some algorithm requiring a sorted sequence in the first
place (like lower_bound).

Lexicographical ordering is yet another story. It is a mathematical way of
extending an order relation on elements to an order relation on a sequence
of elements, the same way the natural ordering of single characters may be
used to sort whole words in a dictionary.

Total ordering is still something else. It is an additional requirement you
can put on an order relation, asking that any two given elements may be
compared against each other. Note that although it may seem quite natural,
this is not strictly required to be able to put some items in a so-called
topological order. This is not very usual, because most every day objects we
are dealing with are very near to either integer numbers or strings, both of
which have a natural total ordering. Whole numbers have even a strict total
ordering, meaning that two numbers obey exactly one of the three following
properties:

x < y, x > y or x is exactly the same as y. Note that if two items are not
comparable, than neither of the above holds.

For string, the natural order is precisely given by the lexicographical
extension mentionned above, and because underlying characters are very close
to integers, they also have a natural total ordering from which the string
ordering may be derived.

Now, if for some technical reason you absolutely need an order relation (for
example to put threads in a set container), you can always use some
artificial integer id (for example the thread or process id) to impose an
order relation satisfying the requirements. Of course, it is then not
possible to give a business meaning to the order relation. It is mainly
introduced for technical purposes.

What the standard actually requires when using elements with a set or
map-like container, is a strict weak total ordering, and this is yet another
subtly different requirement than the above. Strict means that the used
relation must behave like '<' and not like '<='. Total means that any two
items should be comparable, i.e. the ordering function shiould return the
same answer every time it is invoked with the same argument, and that answer
should be boolean (true or false, but not some kind of #NA or NULL like in
SQL). This excludes non-deterministic functions. Weak ordering it the subtle
part. Contrarily to the usual order relation on integers, you cannot
conclude that x not being < than y is automatically equivalent to y < x! The
weak ordering offers place for a third solution: x not being smaller than y
and y not being smaller than x at the same time, although both are actually
different objects that don't compare ==! Let see it in mathematical form for
better clarity:

! (x < y ) && ! (y < x)

Items satifying the above property may be regarded as equivalent (though not
equal). Equivalent is meant here in the mathematical sense of an equivalence
relation partitioning the set of all elements in disjoint equivalence
classes. The purpose of the equal-range algorithm of the standard library is
precisely to extract an equivalence class of a sorted container. Let's take
a concrete exemple to illustrate the above:

Suppose you have a person object, containing, among other data, a first name
and a last name. When storing them in say a multi-set container, you could
decide to sort them according to the last name, forgetting the first name
for the moment. You can achieve this with some ordering function simply
comparing the last name members with the usual string comparison (our
induced lexicographical order from above, do you remembter ?). What happens
now with two different people having the same (last) name, but different
first names ? They will be regarded as equivalent by the container, i.e.
they will be stored in no particular order. Worse: if you put them in a set
instead of a multi-set, they will be regarded as the same person, hence the
second instance won't even be inserted in the set. So lets consider a
multi-set instead. Now if you ask for an equal_range, you'll obtain an
equivalence class, i.e. the range of all persons with the same last name
(and different first names, in no particular order). Would you like to
obtain the same information, but sorted by first name, you can resort to the
following trick:

- Build the container with an order relation based on both last name and
first name (some primitive kind of lexicographical extension, BTW)
- When asking for an equal_range, provide the other order relation, basing
only on last name. This requires that you use the external algorithm, not
the one offered by the container itself, which will use order relation
provided at container construction.

This trick is perfectly legal, portable, etc., because it relies strictly on
the mathematical properties of the order relations. It is even one of the
reasons why the requirements are defined in such a subtle way in the first
place.

So, I hope I shed some light on that complicated topic.

Jean-Daniel Nicolet
Software Consultant
Geneva
Switzerland


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]