What is the data structure used for following line of code in C++?
map <char, int> dict; Is it a hash table?
Add a comment |
4 Answers
std::unordered_map uses hashing to store its objects.
Comments
The standard does not impose any specific implementation on std::map. It only gives the required operations and their complexity. Those factors lead to the actual implementation choice which is usually a Red-black Tree.
The chapter listing the requirements for std::map is 23.2.4 Associative Containers in C++11.
Comments
It is usually implemented with a self-balancing BST. Implementation is actually compiler specific.
std::map<char, int> dict; A char is the key while an int is the corresponding value.
1 Comment
TJD
I don't think there is any requirement for it to be Red-Black tree implementation. It could be anything under the hood if the semantics are followed.
It uses Red-Black Tree to organize keys in order.
That's why you can iterate it in ascending order, and the key object has to have operator< overloaded.
