Menu
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!
845
A Set data structure allows to add data to a container. A Set is a collection of objects or primitive types (strings, numbers or booleans), and you can think of it as a Map where values are used as map keys, with the map value always being a boolean true.
In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set.
Representation of Sets Sets can be represented in two ways, one is known as the Roster form and the other is famous as the Set-Builder form, these two forms can be used to represent the same data, just the style varies in both cases.
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.
107
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
