Lookup in std::map [duplicate]

Thi开发者_运维知识库s question already has answers here: Closed 11 years ago.

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.

---

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.

---

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)

---

You are looking for std::hash_map.