12

I wanted to know , how is the MAP available in C++ , not MultiMap just simple Map , implemented internally .

What i could best think of is :

For Integer Mapping : A Balanced Binary Search Tree could be used .

For String Mapping : Compressed Trie or something similar could be used .

I am really curious , how is it really implemented in STL Map .Is some hashing function employed or is it something totally different from this .

Improve this question
7
  • why not just looking into the source code? Commented Jul 23, 2013 at 14:09
  • @ogni42: Where can i find it ? Commented Jul 23, 2013 at 14:10
  • 1
    I believe std::map is commonly implemented using a Red-black tree and std::unordered_map is a Hash table. Commented Jul 23, 2013 at 14:10
  • 1
    since it is a template, the source code must be available to the compiler. You find it in the header <map> - where that is, depends on your compiler and installation. Commented Jul 23, 2013 at 14:11
  • 3
    You can't use hashing for map, since the keys must be ordered. Binary search trees are common; specifically, the GNU and (I think) MS implementations use a red-black tree. Hashing is used for unordered_map (or hash_map, as it was known in the prehistoric STL). Commented Jul 23, 2013 at 14:14

3 Answers 3

Reset to default
9

The ordered containers, including std::map are implemented as balanced binary trees (usually RB trees, but any other balanced tree would fit the requirements).

For this type of questions, the most important piece of information you need is the complexity requirements of each one of the operations in the container, which is what the standard mandates. That is also, the most important answer, that is, as long as the complexity requirements are met, the actual implementation does not really matter.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

6

std::map is based on Balanced Binary Search Tree, example, AVL Tree and Red Black Tree. Worst Case Complexity of searching an element is O(log(n)). During the insertion of keys, comparison is done in balanced binary search tree to find the correct position of key. As the tree is balanced, maximum comparisons done during insertions would be maximum height of tree which is O(log(n)).

std::unordered_map is based on Hash Table. Average Case complexity of searching an element is O(1) but worst case complexity is still O(n) because collisions can happen if multiple keys mapped to same location in Hash Table.

Improve this answer

Comments

3

std::map in c++ are implemented using Red-Black Tree.

Internally, class 'map' inherits '__Tree' class publicly which gives an implementation for Red-Black Tree. See this snipped of 'class map' from <map.h>

This __Tree class is used for map/multimap/set/multiset. See this snippet from 'class __Tree' from <xtree.h>

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.