Which standard container provides average constant-time lookup by key?
Correct answer A. std::unordered_map
Explanation
std::unordered_map is a hash table, so find, insert and erase are O(1) on average, degrading to O(n) only with many hash collisions. std::map is usually a balanced binary search tree with O(log n) operations but keeps keys sorted. Searching an unsorted std::vector or std::list by value is O(n). Choose unordered_map when ordering does not matter.
Answer checked How we write and check questions
Discussion