CODEWITHSUNDEEP
c++data-structuresset
DoReMi
DoReMi

Reputation: 221

What is data structure based for set

In C++, map is based on a black-red tree, thus, insert/delete function will cost O(logn), and hash_map is based on a hash.

But I'm wandering that what data structure is set based?

Set is sorted as map does, so, is set also based on a black-red tree?

How its key and value stored in that tree?

And if so, what's data structure for unorder_set? Thanks!

Upvotes: 16

Views: 808

Answers (4)

Ben S.
Ben S.

Reputation: 1143

As others have said, there doesn't seem to be any guarantee of a specific implementation in the standard. However, the standard does make certain performance guarantees, such as insertion in O(log n) time for sets, which seems to be the real question that you are asking.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373392

The set and map types can be implemented pretty much however you'd like as long as it conforms to the time complexity requirements of the C++ specification, which bases the time complexities on a balanced binary search tree's time complexities. Although red/black trees are common for map and set, they're not the only options. You could have them implemented with AVL trees, B-trees, AA-trees, etc.

Hope this helps!

Upvotes: 9

Dietmar Kühl
Dietmar Kühl

Reputation: 154035

The ordered associative containers, i.e, std::set<...> and std::map<...> and their "multi" versions, are node-based and have worst-case O(ln n) complexity. This implies that a balanced tree is used. In addition to the complexity neither pointers nor iterators are invalidated when the tree is mutated (except, of course, pointers or iterators to erase()d objects).

A B-tree sadly doesn't have the right iterator invalidation properties (and for maps requires duplicate storage of the key to get most of the advantage due to the force representation using a std::pair<Key, Value>). In practise it seems red/black trees are most effective but there are other possible balancing strategies, e.g., AVL trees. A skip list might also have the necessary properties. In either case, the standard doesn't mandate the exact implementation strategy.

Upvotes: 7

bstamour
bstamour

Reputation: 7776

There's no guarantee. The only thing that the standard mandates is the cost of the operations, so implementers are free to use whatever data structures they want. Typically std::set and std::map are balanced binary trees.

Also, std::unordered_set and std::unordered_map are hash tables. This I believe is actually guaranteed by the standard because you are allowed to specify the hashing function manually.

Upvotes: 19

Related Questions