"strict weak ordering" requirement of compare argument for std::set
in [C++]
|
Prev: string::find() behaviour searching for an empty string
Next: C++0x two Unicode proposals. A correction one and a different one
From: Ulrich Eckhardt on 17 Jan 2008 16:46 Jochen Eisinger wrote: > if I'm not mistaken, the compare parameter of the std::set template has > to fulfill the "strict weak ordering" requirement. In contrast to a > "total ordering", two objects might just not be comparable by a strict > weak ordering, i.e. neither x < y nor y < x although x != y. Right. > So using a "strict weak ordering", std::set can't determine whether an > element is already in the set or not, just whether an element of the > same class wrt. the compare parameter is already in the set. True. The set treats equality according to its comparator. > In fact, if you instantiate std::set as implemented with gcc with a > not-total ordering, you can't insert two different elements, which > cannot be ordered. > > So my question is: should the compare object actually fulfill a total > ordering requirement, or should a set be seen as a container containing > one representant per equivalence class? This depends on your application logic. Also consider multiset as alternative, though using that you can insert elements that are completely equal. Lastly, you can create a set using elements that are not equality-comparable, i.e. that don't have an operator==. This allows you to use a custom comparator that only compares a certain facet of the objects. Uli -- Sator Laser GmbH Gesch�ftsf�hrer: Michael W�hrmann, Amtsgericht Hamburg HR B62 932 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Matti Rintala on 17 Jan 2008 17:11 Jochen Eisinger wrote: > if I'm not mistaken, the compare parameter of the std::set template has > to fulfill the "strict weak ordering" requirement. In contrast to a > "total ordering", two objects might just not be comparable by a strict > weak ordering, i.e. neither x < y nor y < x although x != y. True. > So my question is: should the compare object actually fulfill a total > ordering requirement, or should a set be seen as a container containing > one representant per equivalence class? The latter. Associative containers work on equivalence classes defined by the strict weak ordering of the comparison. In fact, it's very useful. For example, it allows sets where only part of the data is used as a key. -- ------------- Matti Rintala ------------ matti.rintala(a)tut.fi ------------ Painting is the art of inclusion. Photography is an art of exclusion. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Alberto Ganesh Barbati on 17 Jan 2008 18:09
Jochen Eisinger ha scritto: > Hi, > > if I'm not mistaken, the compare parameter of the std::set template has > to fulfill the "strict weak ordering" requirement. In contrast to a > "total ordering", two objects might just not be comparable by a strict > weak ordering, i.e. neither x < y nor y < x although x != y. > > So using a "strict weak ordering", std::set can't determine whether an > element is already in the set or not, just whether an element of the > same class wrt. the compare parameter is already in the set. > > In fact, if you instantiate std::set as implemented with gcc with a > not-total ordering, you can't insert two different elements, which > cannot be ordered. > > So my question is: should the compare object actually fulfill a total > ordering requirement, or should a set be seen as a container containing > one representant per equivalence class? > The latter, as clearly stated in 23.1.2/3 of the C++ Standard: "The phrase ��equivalence of keys�� means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false." HTH, Ganesh -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |