C++: Access a Non-existent Key in std::map or std::unordered_map

Note: I have been asked this question by a Google Recruiter in the early stage of Interview Process e.g. Screening.

In C++, when you access a non-existent key in std::map, the behavior depends on how you access it:

Using the subscript operator []

If the key does not exist, std::map will automatically insert an element with that key and assign it a default value based on the type. For example, if the value type of the map is int, it will insert the key with a value of 0.

Example:

1
2

std::map<int, int> myMap;
int value = myMap[10]; // If key 10 does not exist, it will insert myMap[10] = 0

std::map<int, int> myMap;
int value = myMap[10]; // If key 10 does not exist, it will insert myMap[10] = 0

Using the at() method

If the key does not exist, at() will throw a std::out_of_range exception.

Example:

1
2
3
4
5
6

std::map<int, int> myMap;
try {
    int value = myMap.at(10); // If key 10 does not exist, an exception will be thrown
} catch (const std::out_of_range& e) {
    std::cout << "Key not found!" << std::endl;
}

std::map<int, int> myMap;
try {
    int value = myMap.at(10); // If key 10 does not exist, an exception will be thrown
} catch (const std::out_of_range& e) {
    std::cout << "Key not found!" << std::endl;
}

Using the find() method

find() does not modify the map. It returns an iterator. If the key does not exist, it will return map.end().

Example:

1
2
3
4
5
6
7

std::map<int, int> myMap;
auto it = myMap.find(10);
if (it == myMap.end()) {
    std::cout << "Key not found!" << std::endl;
} else {
    std::cout << "Value: " << it->second << std::endl;
}

std::map<int, int> myMap;
auto it = myMap.find(10);
if (it == myMap.end()) {
    std::cout << "Key not found!" << std::endl;
} else {
    std::cout << "Value: " << it->second << std::endl;
}

Comparing std::map vs std::unordered_map

std::unordered_map behaves similarly to std::map when accessing a non-existent key, but with a few differences related to how the internal data structure works.

• Order: std::map is ordered (implemented as a balanced tree), so elements are stored in a sorted order based on the keys. std::unordered_map, on the other hand, is not ordered and uses a hash table for internal storage, so elements have no particular order.
• Performance: std::unordered_map generally has faster average access time (O(1) on average due to hashing), while std::map has O(log n) time complexity due to the tree structure. However, the worst-case time complexity for unordered_map can be O(n) if there are many hash collisions.

std::unordered_map and std::map have similar behavior in terms of handling non-existent keys for [], at(), and find(), but they differ in ordering and performance characteristics.

Summary: Access a Non-existent Key in C++ Maps

• When accessing with [], if the key does not exist, the map will insert a new element with the default value.
• When accessing with at(), if the key does not exist, an exception will be thrown.
• Using find() allows you to check if the key exists without modifying the map.

–EOF (The Ultimate Computing & Technology Blog) —