How does std::set stay unique with only std::less?

[Cory Nelson]

Does anyone know how std::set prevents duplicates using only std::less?

I've tried looking through a couple of the STL implementations and
their code is pretty unreadable (to allow for different compilers, I
guess).

 

[Andrey Tarasevich]

Does anyone know how std::set prevents duplicates using only std::less?
...

And? What exactly is the problem here, in your opinion? If you have a 'less'
operation, then equality can be easily defined through it as follows:

'a equals b' is true if and only if neither 'a less than b' nor 'b less than
a' is true.

 

[Clark S. Cox III]

Does anyone know how std::set prevents duplicates using only std::less?

It just checks to make sure each element is less than the one it precedes.

 

[Cory Nelson]

And? What exactly is the problem here, in your opinion? If you have a 'less'
operation, then equality can be easily defined through it as follows:

'a equals b' is true if and only if neither 'a less than b' nor 'b less than
a' is true.

And what? I was just hoping it used some other way than that. That
type of comparison might be rather inefficient if the pred needs to do
a lot of work.

 

[Kai-Uwe Bux]

And what? I was just hoping it used some other way than that. That
type of comparison might be rather inefficient if the pred needs to do
a lot of work.

The test for equality is not used at all in a straight forward implemtation
of std::set. Instead you use a search tree and std::less will tell you
whether a new values should be inserted to the left or to the right of the
current node under consideration. Thus, a more efficient test for equality
would not buy you anything.


Best

Kai-Uwe Bux

 

[StepNRazor]

If you are useing non standard type's 'ie' YourObj classes inYourObj
class you need to overload operator<() and provide a parameterless
ctor.

Blow is overloaded< and paramless ctor

class LaDeDah
{
//class attributes used for set comparison checks.
int setCmpItem;

//Someother data
double doh;

public:

//Required paramless ctor
LaDeDah() { setCmpItem = 0; doh = 0.0;}

//Single param
LaDeDah(int key) { setCmpItem = key; doh = 0.0;}

//Multiple params
LaDeDah(int key, double someData) { setCmpItem = key; doh = someData;}

//Accessors
int GetCmpItem();
double GetData();
};

//Required overloaded operator<() compare left hand side and right hand
side objets of LaDeDah
bool operator<(LaDeDah lhs, LaDeDah rhs)
{
return lhs->GetCmpItem() < rhs->GetCmpItem();
}

int LaDeDah::GetCmpItem()
{
return setCmpItem;
}

double LaDeDah::GetData()
{
return doh;
}

Joe

 

[Greg]

Does anyone know how std::set prevents duplicates using only std::less?

I've tried looking through a couple of the STL implementations and
their code is pretty unreadable (to allow for different compilers, I
guess).

The less than operator is all that is needed relative ordering of two
types. Consider:

a > b (greater than) a < b
a == b (equality) not (a < b) and not (b < a)
a != b (inequality) a < b or b < a
a >= b (greater or equal) not (a < b)
a <= b (less than or equal) not (b < a)

Greg

 

[=?iso-8859-1?q?Kirit_S=E6lensminde?=]

If you are useing non standard type's 'ie' YourObj classes inYourObj
class you need to overload operator<() and provide a parameterless
ctor.

You don't need to overload operator < to use it in a map. You should
only overload operator < if it makes sense for your class, i.e. it is
properly comparable in that way. It doesn't even have to be a member
though - a global operator < does just as well so long as it can be
seen.

If operator < doesn't make sense for your class then you should
implment a comparator functor class that implements
std::binary_function< X, X, bool > where X is the thing you want to put
into the map or set or whatever.

The default one that set and map uses is std::less<> which makes use of
the operator < on the type X. Also available is std::greater<> that
uses the other operator. You can define a whole host of your own
functor classes for different situations without dirtying the design of
the class you are putting into the set or map.


K

PS There's a rule about not top-posting.

 

[Kai-Uwe Bux]

You don't need to overload operator < to use it in a map. You should
only overload operator < if it makes sense for your class, i.e. it is
properly comparable in that way. It doesn't even have to be a member
though - a global operator < does just as well so long as it can be
seen.

If operator < doesn't make sense for your class then you should
implment a comparator functor class that implements
std::binary_function< X, X, bool > where X is the thing you want to put
into the map or set or whatever.

The default one that set and map uses is std::less<> which makes use of
the operator < on the type X.

Unless you provide a specialization.

Also available is std::greater<> that
uses the other operator. You can define a whole host of your own
functor classes for different situations without dirtying the design of
the class you are putting into the set or map.

In this case (there is no intrinsic meaning of "<" for our_class), one could
also consider specializing std::less<our_class> provided one can define a
strict order for our_class. The advantage compared to defining a comparison
function with an arbitrary name is that standard containers will resolve
automatically. This does not only go for std::set. If you use your class in
a vector, and if std::less is defined for your class, a reasonable
definition is automatically derived for std::vector<our_class>. There is
also precedence for this practice in the standard library: std::complex.



Best

Kai-Uwe Bux

 

[Andrey Tarasevich]

And what? I was just hoping it used some other way than that. That
type of comparison might be rather inefficient if the pred needs to do
a lot of work.
...

I'm not saying that it is actually used in exactly that way. All I'm
saying is that potentially the information about the equality is
_available_ from 'std::less' alone. How it is obtained in practice -
directly (as described above) or in a more indirect, tricky and
efficient way - is a different story.

In fact it is indeed a different story with 'std::set<>'. The efficiency
requirements imposed on 'std::set<>' by the standard library
specification dictate an implementation based on some ordered data
structure (like a tree, for example). To build such a structure
'std::less' is perfectly enough (anything more is just unnecessary) and
the equivalent elements get detected and grouped together just "by
itself", as a side effect of the ordering, without explicit 'a less than
b' and 'b less than a' comparisons.

 

[StepNRazor]

The question was about a set not a map.
My reference is from :
Herbert Schildt'sSTL programming from the ground up.
Chapter storeing Class objects in a set.
What I read is that for an object to be stored in a set the class must
overload the operator < as well as provide a parameterless constructor.
Note this book is 1999 so the info might be dated.

Joe

 

[Andrey Tarasevich]

The question was about a set not a map.
My reference is from :
Herbert Schildt'sSTL programming from the ground up.
Chapter storeing Class objects in a set.
What I read is that for an object to be stored in a set the class must
overload the operator < as well as provide a parameterless constructor.
Note this book is 1999 so the info might be dated.
...

Firstly, please, don't top-post.

Secondly, you can take a look a the reviews for Herbert Schildt's books
on http://accu.org. This is not exactly the author to trust when it
comes to C++, to put it mildly.

Thirdly, in order to store an object in an associative STL container
(map, list, doesn't matter) it has to be assignable and
copy-constructible. There are no other hard requirements.

There's no requirement for a "parameterless constructor" (default
constructor).

There's no unconditional requirement to provide the < operator, since
associative containers don't use it directly. Associative containers use
comparison predicate (which you supply) to compare elements. Only if you
fail to supply your own the comparison predicate, 'std::less' will be
used by default, which does indeed use operator < to perform comparison.

 

[Kai-Uwe Bux]

StepNRazor wrote:
[top-posting fixed]

The question was about a set not a map.
My reference is from :
Herbert Schildt'sSTL programming from the ground up.
Chapter storeing Class objects in a set.
What I read is that for an object to be stored in a set the class must
overload the operator < as well as provide a parameterless constructor.
Note this book is 1999 so the info might be dated.

a) Please do not top-post.

b) The book is wrong, std::set *and* std::map (and std::multiset and
std::multimap) use std::less, not <.

c) The book might be dated, however, these provisions were already part of
the 1998 draft version of the c++ standard.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

StepNRazor wrote:
[top-posting fixed]

The question was about a set not a map.
My reference is from :
Herbert Schildt'sSTL programming from the ground up.
Chapter storeing Class objects in a set.
What I read is that for an object to be stored in a set the class must
overload the operator < as well as provide a parameterless constructor.
Note this book is 1999 so the info might be dated.

a) Please do not top-post.

b) The book is wrong, std::set *and* std::map (and std::multiset and
std::multimap) use std::less, not <.

That should read: ... use std::less as the default comparison method unless
the client provides a different one.

c) The book might be dated, however, these provisions were already part of
the 1998 draft version of the c++ standard.

Best

Kai-Uwe Bux

 

[Bernd Strieder]

Hello,

And what? I was just hoping it used some other way than that. That
type of comparison might be rather inefficient if the pred needs to do
a lot of work.

There are 3 different results from the comparision, a<b, a>b, or
neither. You need two comparisions with < to find it out. The
algorithms used for STL need only one comparision for the inner nodes
of the binary search tree used internally, but the left neighbour of
the final position in the tree and the new key will have to be compared
in both ways to avoid duplicates. So there is only one additional
comparision to what the tree traversal already uses.

If an equivalence relation were required additionally to the order
relation, then the interface of the STL classes would be a lot more
difficult, and in general, an equivalence predicate would cost about
the same as the order predicate. To distinguish the three cases we
would need evaluating the order and the equivalence pred each once. So
there is no win to be expected. In more complicated cases the
equivalence predicate cannot be equality, because equality is something
the whole object should be looked at for, where ordering is naturally
done using only a part of the attributes. So the equivalence relation
would have to be something new with no sensible default.

The only chance to really improve something would be some kind of three-
or four-valued logic, i.e. an order function returning
<,>,=,incomparable. But this has the disadvantage, that it would be
overhead for the simple cases, that are to be expected to be the
majority.

Regards,

Bernd Strieder

 

[StepNRazor]

Firstly, please, don't top-post.
ok

Secondly, you can take a look a the reviews for Herbert Schildt's books
on http://accu.org. This is not exactly the author to trust when it
comes to C++, to put it mildly.

I looked on amazon for a STL book this one was 4 stars out of 24
rateing. I am suprised that it has invalid information on useing user
defined objects in sets.
I've read past containers and algorithms and in to Function objects,
binders negators, and function adaptors, and now wondering how much of
the information I read in this book is incorrect.
sigh.

 

[red floyd]

I looked on amazon for a STL book this one was 4 stars out of 24
rateing. I am suprised that it has invalid information on useing user
defined objects in sets.
I've read past containers and algorithms and in to Function objects,
binders negators, and function adaptors, and now wondering how much of
the information I read in this book is incorrect.
sigh.

Ignore Amazon ratings, at least for computer books. Schildt's book is
one of the few books that I have violated my own policy of "never throw
out a book" for.