TITLE: partial vs total ordering for STL sets (Newsgroups: comp.lang.c++.moderated, 3 Jan 97) SACHS: Jay Sachs >> Am I right in surmising that [elements of an STL set] should have >> less-than semantics? LIBLIT: Ben Liblit >You don't need less-than semantics specifically, but you do need some >sort of ordering relationship. The pertinent section of the April '95 >draft working paper is 23.1.2.2 [lib.associative.reqmts], which states >in part: > > All [associative containers, including set<>] are parameterized on > Key and an ordering relation Compare that induces a total ordering > on elements of Key. BUCK: jbuck@Synopsys.COM (Joe Buck) I've discovered that many STL programmers get themselves in trouble because they don't understand that phrase "total ordering". To be clear, the ordering relation has to have four properties or else your associative container won't work properly. Let's call the ordering relation "comes_before". Antisymmetric: for any keys x and y, if comes_before(x,y) is true, then comes_before(y,x) is always false. Transitive: for any keys x, y, and z, if comes_before(x,y) is true and comes_before(y,z) is true, then comes_before(x,z) is always true. Irreflexive: if x and y are the same key (or equal keys), then comes_before(x,y) is always false. With the above three properties we have a partial order; some pairs of keys may be incomparable in that neither comes before the other. To get a total order, we add the rule that, for any x and y, if both comes_before(x,y) and comes_before(y,x) are false, then the keys are equal. (This is how STL determines that it has found the right key). Numerical comparisons are total orders, so are lexicographic comparisons. If you've defined an ordering relation and find that your container isn't working properly, check the above properties and see which ones aren't satisfied. If any are not, you may find that lookups fail, that sets get duplicate members, etc. One annoying thing about STL is that it often makes sense to define an operator< that is only a partial order. For example, in a project scheduling application we might want to define bool operator<(const Task& a, const Task& b) { return a.mustBeCompletedBeforeStarting(b); } but this is only a partial order (distinct tasks may have no precedence constraints) so a is broken (though set would work). Either the programmer of Task must avoid using operator< for partial orders or s/he must carefully document this and warn against any other programmer using associative containers with this operator.