O(1) lookup in C++

Question

Is there a data structure in C++ with O(1) lookup?

A std::map has O(log(n)) lookup time (right?).

I'm looking from something in std preferably (so not Boost pls). Also, if there is, how does it work?

EDIT: Ok, I wasn't clear enough I guess. I want to associate values, kind of like in a map. So I want something like std::map<int,string>, and find and insert should take O(1).

Answer 1

Arrays have O(1) lookup. Hashtable (std::unordered_map) for c++11 has O(1) lookup. (Amortized, but more or less constant.)

I would also like to mention that tree based data structures like maps come with great advantages and are only log(n) which is more often than not sufficient.

Answer to your edit -> You can literally associate an index of an array to one of the values. Also hash tables are associative but perfect hash (each key maps to exactly 1 value) is really difficult to get.

One more thing worth mentioning: Arrays have great cache performance (due to locality, aka. elements being right next to each other so they can be prefetched to cache by the prefecthing engine). Trees, not so much. With reasonable amount of elements, hash performance can be more critical than asymptotic performance.