1

Possible Duplicate:
STL like container with O(1) performance.

I always thought that std::map is a hashed list. In that case shouldn't lookup be O(1). The documentation says it's O(logn). What's an appropriate data structure in STL that mimics a hashed map the best with O(1) insertion and lookup.

Community
  • 1
  • 1
shreyasva
  • 13,126
  • 25
  • 78
  • 101
  • No, it is not a hashed list but it is rather implemented as a tree. At least with Visual Studio 2010. – Benoit Apr 04 '11 at 14:33
  • 1
    @Benoit: the standard imposes algorithmic complexity on containers. It basically *has* to be a red-black tree. – André Caron Apr 04 '11 at 14:36
  • @Andre: Thats what I saw in my linux box - the stl::map is implemented using a red-black tree. – yasouser Apr 04 '11 at 14:41

3 Answers3

6

std::map is implemented as a binary search tree. So lookups are not O(1). TR1 and C++0x are adding a hash map to the STL called an unordered_map. See http://en.wikipedia.org/wiki/Unordered_map_(C%2B%2B)

Depending on your compiler, you might have unordered_map or possible hash_map in the STL.

Jon Benedicto
  • 10,492
  • 3
  • 28
  • 30
  • I looked at the implementation of map in my linux box and it uses a red-black tree and not a binary search tree. – yasouser Apr 04 '11 at 14:40
  • Just to clarify, although the complexity requirements pretty much limits the implementation to a BST, the standard does not mandate which data structure a container must be implemented as. – pepsi Apr 04 '11 at 14:43
  • A red-black tree is a binary search tree, with the additional feature that it is balanced. – swegi Apr 04 '11 at 14:43
  • @yasourser: A RB tree is an specific type of binary search tree (in particular a variant of *balanced* binary search tree). The standard requires (through the complexity requirements) that `std::map` is implemented as a *balanced binary search tree*. – David Rodríguez - dribeas Apr 04 '11 at 14:44
2

There is no official STL container with constant lookup. However, several library implementations provide a non-standard hash_map container which does O(1) lookups (http://www.sgi.com/tech/stl/hash_map.html)

pepsi
  • 6,785
  • 6
  • 42
  • 74
-1

You are looking for std::hash_map.

Jon
  • 428,835
  • 81
  • 738
  • 806
  • Actually it will be `unordered_map` and `unordered_set` in C++0x unless I'm mistaken. – Mark B Apr 04 '11 at 14:41
  • @MarkB: The link I give states exactly that in the first two lines. Do you feel I should repeat it here? – Jon Apr 04 '11 at 14:42