By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,903 Members | 1,304 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,903 IT Pros & Developers. It's quick & easy.

STL Set question

P: n/a
How does the STL "set" class ensure uniqueness ? Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?

TIA

Oct 24 '05 #1
Share this Question
Share on Google+
8 Replies


P: n/a
vk02720 wrote:
How does the STL "set" class ensure uniqueness ?
Implementation-defined.

However, a set is usually implemented as a tree and trees are sorted by
essence. Inserting a value implies going down the tree until you find
where to put it. Identical values will always map to the same node in
the tree, so if this node already exists, std::set::insert() will fail.
Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?


By default, std::set sorts its elements using operator<, so yes, the
element type must implement that operator. It is possible to specify
the comparison operator used by supplying a second template argument.

std::set<int, std::greater<int> > coll;

sorts the element using operator>.
Jonathan

Oct 24 '05 #2

P: n/a

vk02720 wrote:
How does the STL "set" class ensure uniqueness ? Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?

TIA


look it up.

Oct 24 '05 #3

P: n/a
puzzlecracker wrote:
vk02720 wrote:
How does the STL "set" class ensure uniqueness ? Does the contained
type need to implement a certain method or override a certain
operator ( != or < ) ?

TIA


look it up.


Not exactly helpful from someone who asks a _lot_ of questions here. From
now on, if you ask a question such as "is it possible to call nonconst
member function on an unnamed temprary?", I take it you'll be satisfied with
the response "look it up" (in the standard).

DW
Oct 24 '05 #4

P: n/a
Jonathan Mcdougall wrote:
vk02720 wrote:
How does the STL "set" class ensure uniqueness ?

Implementation-defined.

However, a set is usually implemented as a tree and trees are sorted by
essence. Inserting a value implies going down the tree until you find
where to put it. Identical values will always map to the same node in
the tree, so if this node already exists, std::set::insert() will fail.

Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?

By default, std::set sorts its elements using operator<, so yes, the
element type must implement that operator. It is possible to specify
the comparison operator used by supplying a second template argument.

std::set<int, std::greater<int> > coll;

sorts the element using operator>.
Jonathan

If you're really interested, it's often implemented as a Red Black tree.
This is because the tree can be kept reasonably balanced without
requiring too much overhead in processing time. Naturally this holds
true for both adding and deleting items. The worst case that can occur
is for 1 branch of the tree to be twice the depth of its neigbour.

Reference : "Introduction to algorithms"
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest

ISBN : 0-262-53091-0

Please note this is not the latest edition of this book.
Oct 24 '05 #5

P: n/a

vk02720 wrote:
How does the STL "set" class ensure uniqueness ? Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?


By default std::set uses std::less to sort its items which in turn
relies on less than comparisons for generic types. So if instances of
the std::set's type can be compared to each other with the less-than
operator then std::set fully supports that type.

An interesting question in the case of a type that does not support
less-than comparisons is whether the client must overload the <
operator to be compatible with std::less - or whether the client may
specialize std::less for a particular type.

Ordinarily the std namespace is off limits to client code, but it is
permissible to specialize a std namespace template as long as two
conditions are met: first, the specialized type must be a
client-defined type and second, the specialized template must meet all
of the requirements that apply to the general template. [17.4.3.1]

Greg

Oct 24 '05 #6

P: n/a

n2xssvv g02gfr12930 wrote:
Jonathan Mcdougall wrote:
vk02720 wrote:
How does the STL "set" class ensure uniqueness ?

Implementation-defined.

However, a set is usually implemented as a tree and trees are sorted by
essence. Inserting a value implies going down the tree until you find
where to put it. Identical values will always map to the same node in
the tree, so if this node already exists, std::set::insert() will fail.

Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?

By default, std::set sorts its elements using operator<, so yes, the
element type must implement that operator. It is possible to specify
the comparison operator used by supplying a second template argument.

std::set<int, std::greater<int> > coll;

sorts the element using operator>.
Jonathan

If you're really interested, it's often implemented as a Red Black tree.
This is because the tree can be kept reasonably balanced without
requiring too much overhead in processing time. Naturally this holds
true for both adding and deleting items. The worst case that can occur
is for 1 branch of the tree to be twice the depth of its neigbour.


Or did you mean that the longest branch in the tree is no more than
twice the depth of the shortest? Otherwise, if each branch is allowed
to be twice the length of its neighbor, the tree could be extremely
unbalanced it would seem to me.

Greg

Oct 24 '05 #7

P: n/a
Greg wrote:
n2xssvv g02gfr12930 wrote:
Jonathan Mcdougall wrote:
vk02720 wrote:
How does the STL "set" class ensure uniqueness ?
Implementation-defined.

However, a set is usually implemented as a tree and trees are sorted by
essence. Inserting a value implies going down the tree until you find
where to put it. Identical values will always map to the same node in
the tree, so if this node already exists, std::set::insert() will fail.

Does the contained
type need to implement a certain method or override a certain operator
( != or < ) ?
By default, std::set sorts its elements using operator<, so yes, the
element type must implement that operator. It is possible to specify
the comparison operator used by supplying a second template argument.

std::set<int, std::greater<int> > coll;

sorts the element using operator>.
Jonathan


If you're really interested, it's often implemented as a Red Black tree.
This is because the tree can be kept reasonably balanced without
requiring too much overhead in processing time. Naturally this holds
true for both adding and deleting items. The worst case that can occur
is for 1 branch of the tree to be twice the depth of its neigbour.

Or did you mean that the longest branch in the tree is no more than
twice the depth of the shortest? Otherwise, if each branch is allowed
to be twice the length of its neighbor, the tree could be extremely
unbalanced it would seem to me.

Greg

Thanks for the correction.

To be exact, the longest path to an end node will never be more than
twice as long as the shortest path to an end node, assuming the start
node as 2 children, and an end node doesn't have any children.

See this site for animated example and brief explanation

http://www.geocities.com/SiliconVall.../1854/Rbt.html

JFJB
Oct 24 '05 #8

P: n/a
n2xssvv g02gfr12930 wrote:
Greg wrote:
n2xssvv g02gfr12930 wrote:
Jonathan Mcdougall wrote:

vk02720 wrote:
> How does the STL "set" class ensure uniqueness ?

Implementation-defined.

However, a set is usually implemented as a tree and trees are sorted by
essence. Inserting a value implies going down the tree until you find
where to put it. Identical values will always map to the same node in
the tree, so if this node already exists, std::set::insert() will fail.

> Does the contained
> type need to implement a certain method or override a certain operator
> ( != or < ) ?

By default, std::set sorts its elements using operator<, so yes, the
element type must implement that operator. It is possible to specify
the comparison operator used by supplying a second template argument.

std::set<int, std::greater<int> > coll;

sorts the element using operator>.
Jonathan
If you're really interested, it's often implemented as a Red Black tree.
This is because the tree can be kept reasonably balanced without
requiring too much overhead in processing time. Naturally this holds
true for both adding and deleting items. The worst case that can occur
is for 1 branch of the tree to be twice the depth of its neigbour.


Or did you mean that the longest branch in the tree is no more than
twice the depth of the shortest? Otherwise, if each branch is allowed
to be twice the length of its neighbor, the tree could be extremely
unbalanced it would seem to me.

Greg

Thanks for the correction.

To be exact, the longest path to an end node will never be more than
twice as long as the shortest path to an end node, assuming the start
node as 2 children, and an end node doesn't have any children.

See this site for animated example and brief explanation

http://www.geocities.com/SiliconVall.../1854/Rbt.html

JFJB

Correction if the shortest path is length n then the longest path will
never be a length more than 2n + 1.

JFJB

Only 2 reasons for being late or in a hurry:

1) The original planning was rubbish
2) The unexpected has happened
Oct 25 '05 #9

This discussion thread is closed

Replies have been disabled for this discussion.