What is the map data structure in C++

Question

What is the data structure used for following line of code in C++?

map <char, int> dict;

Is it a hash table?

score 6 · Accepted Answer · answered Aug 31 '12 at 01:09

6

std::unordered_map uses hashing to store its objects.

answered Aug 31 '12 at 01:09

Rapptz

20,187
4
71
86

score 4 · Answer 2 · answered Aug 31 '12 at 01:35

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.

Chris Dargis · Answer 3 · 2012-08-31T01:42:13.633

0

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.

edited Aug 31 '12 at 01:42

answered Aug 31 '12 at 01:03

Chris Dargis

5,541
4
37
61

4

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. – TJD Aug 31 '12 at 01:15

score 0 · Answer 4 · answered Aug 31 '12 at 05:19

0

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.

answered Aug 31 '12 at 05:19

FrostNovaZzz

780
3
8
22

What is the map data structure in C++

4 Answers4

Linked