STL Set question

[vk02720]

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

 

[Jonathan Mcdougall]

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

 

[puzzlecracker]

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.

 

[David White]

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

 

[n2xssvv g02gfr12930]

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.




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.

 

[Greg]

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

 

[Greg]

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

 

[n2xssvv g02gfr12930]

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/SiliconValley/Network/1854/Rbt.html

JFJB

 

[n2xssvv g02gfr12930]

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/SiliconValley/Network/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