473,587 Members | 2,321 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

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

Aug 2 '06 #1
16 5050
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
Aug 2 '06 #2
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

Aug 2 '06 #3
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
Aug 2 '06 #4
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

Aug 3 '06 #5
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).
Aug 3 '06 #6
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

Aug 3 '06 #7

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.

Aug 3 '06 #8
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

Aug 3 '06 #9
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.
Aug 3 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

26
1514
by: Michael Klatt | last post by:
I am trying to write an iterator for a std::set that allows the iterator target to be modified. Here is some relvant code: template <class Set> // Set is an instance of std::set<> class Iterator { public : typedef typename Set::value_type T; typedef typename Set::iterator SetIterator; Iterator(Set& container, const SetIterator& it);
5
6035
by: Exits Funnel | last post by:
I've got this code: //Begin foo.cpp #include <utility> #include <bits/stl_function.h> typedef std::pair<int, int> int_pair_t; template<> struct std::less<int_pair_t> { };
5
1833
by: Vinu | last post by:
Hi I am facing a problem in compilation the error is like this In constructor xServices::CServices<TImp>::StHoldClientList::StHoldClientList(std::set<TImp*, std::less<TImp*>, std::allocator<TImp*> >&)': : error: expected `;' before "pos" : error: `pos' undeclared (first use this function) : error: (Each undeclared identifier is reported...
10
7541
by: danibe | last post by:
I never had any problems storing pointers in STL containers such std::vector and std::map. The benefit of storing pointers instead of the objects themselves is mainly saving memory resources and performance (STL containers hold *copies* of what's passed to them via the insert() method). However, I am not sure how to accomplish that using...
4
3062
by: Gernot Frisch | last post by:
Hi, is the sorting order of std::set / std::map defined? i.e. is the *begin() of std::set<int> always smaller than *(--end()) ? -- -Gernot int main(int argc, char** argv) {printf ("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}
12
3501
by: Marcus Kwok | last post by:
I am not sure if this is something that is covered by the Standard, or if it's an implementation detail of my Standard Library. I am reading in a large amount of data into a std::set. There is an overload for std::set::insert() that takes in an iterator as a hint as to where the new value should be inserted, and my implementation...
5
8178
by: Austin | last post by:
Here is my program: class Test { private: int _num; }; int main() { set<TestaSet;
33
5536
by: desktop | last post by:
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is a pointer to an element can be done in amortized constant time. I guess that is not worst case since std::set is practically a red-black tree where insert/delete takes O(lg n) time. Or are there some other explanation for this complexity?
7
5756
by: Renzr | last post by:
I have a problem about the std::set<>iterator. After finding a term in the std::set<>, i want to know the distance from the current term to the begin(). But i have got a error. Please offer me help, thank you. I am a freshman about the STL. The following is the code. #include <set> #include <iostream> #include <vector> int main() {
0
7843
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
8206
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8340
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7967
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
8220
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6621
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5713
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3840
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
2353
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.