For C++ STL containers such as vector and list, the complexity of finding elements and inserting or removing them is self-explanatory. However, for the map container, even though I know from my reading that the access and insertion complexity/performance is O(log(n)), I can't work out why. I clearly don't understand maps as much as I need to, so some enlightenment on this topic would be very much appreciated.
Asked
Active
Viewed 5,682 times
11
Ed King
- 1,833
- 1
- 15
- 32
-
1have you seen this? http://stackoverflow.com/a/222674/1025391 – moooeeeep Jun 27 '12 at 21:19
2 Answers
13
The elements of a map or set are contained in a tree structure; every time you examine a node of the tree, you determine if the element you're trying to find/insert is less than or greater than the node. The number of times you need to do this (for a properly balanced tree) is log2(N) because each comparison throws out half of the possibilities.
Mark Ransom
- 299,747
- 42
- 398
- 622
-
-
@EdKing, take a look at [red-black trees](http://en.wikipedia.org/wiki/Red_black_tree). They're usually used to implement std::map. – Matt Kline Jun 27 '12 at 21:59
1
As slavik262 points, maps are usually implemented with red-black-trees, which are self-balanced. Check the complexity of a red-black-tree for example in the wikipedia I don't know any implementation of a map with a binary tree; if Mark Ransom knows one, I'd be pleased to know which one.
dgutson
- 11
- 1
-
2I think it's fair to say that a red-black tree *is* a binary tree, just with some invariants on the shape of the tree and re-balancing operations to maintain these during insertion and deletion. – Dale Hagglund Oct 31 '13 at 00:30