Quick Q: data structure with O(1) search time complexity in c++
Quick A: The unordered_* containers have average O(1) complexity.
Recently on SO:
data structure with O(1) search time complexity in c++
What you want is C++11's std::unordered_map, with an average access time of O(1) and a worst case of O(n).