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]

Cory Nelson wrote:

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.

--
Best regards,
Andrey Tarasevich

[Clark S. Cox III]

On 2006-08-02 17:38:06 -0400, "Cory Nelson" <ph*****@gmail. comsaid:

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.
--
Clark S. Cox, III
cl*******@gmail .com

[Cory Nelson]

Andrey Tarasevich wrote:

Cory Nelson wrote:

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.

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.

--
Best regards,
Andrey Tarasevich

[Kai-Uwe Bux]

Cory Nelson wrote:

Andrey Tarasevich wrote:

>Cory Nelson wrote:

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.

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<(LaDeD ah lhs, LaDeDah rhs)
{
return lhs->GetCmpItem() < rhs->GetCmpItem() ;
}

int LaDeDah::GetCmp Item()
{
return setCmpItem;
}

double LaDeDah::GetDat a()
{
return doh;
}

Joe
Cory Nelson wrote:

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).

[Greg]

Cory Nelson wrote:

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

[Kirit Sælensminde]

StepNRazor wrote:

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_fun ction< 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<th at
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.

[Andrey Tarasevich]

Cory Nelson wrote:

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.

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.

--
Best regards,
Andrey Tarasevich

[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

Kirit Sælensminde wrote:

StepNRazor wrote:

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_fun ction< 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<th at
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.