The Hidden Risk in C++ Maps

#	User	Rating
1	tourist	3947
2	jiangly	3734
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	ecnerwala	3581
8	Geothermal	3569
8	cnnfls_csy	3569
10	ksun48	3479

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	nor	157
4	atcoder_official	156
4	cry	156
6	-is-this-fft-	155
7	maroonrk	154
7	adamant	154
9	Petr	146
9	djm03178	146

Inspiration

When I first started with C++, I made a common mistake: I used mp[x] > 0 to check if a key existed in a map. I didn’t realize that this method actually adds new entries to the map if the key isn’t already there. This caused confusing bugs and unexpected results in my code. From this experience, I learned how important it is to use the right methods to check for key existence. In this blog, I’ll explain why this happens and show you better ways to check if a key is in the map without changing it.

Understanding map and unordered_map

In C++, map and unordered_map are containers that store key-value pairs. The main difference is that map keeps the keys in a specific order (usually ascending), while unordered_map stores keys in no particular order, using a hash function.

The Common Mistake

Wrong Approach

map<int, int> mp;
mp[1] = 10;
if (mp[2] > 0) { // This will insert the key '2' with a default value of 0
    // Do something
}
cout << mp.size(); // Output will be 2, not 1

While it seems like a good idea, it actually causes a problem. When you use mp[x], the map tries to find the value for x. If x isn’t in the map, it insert x in the map as key with a default value (like 0 for integers). So, checking mp[x] > 0 actually adds a new entry to the map, increasing its size.

Right Approach

Approach 1

// Using mp.find(x) != mp.end()
// The find() method returns an iterator to the element if it exists, or mp.end() if it doesn’t.

if (mp.find(x) != mp.end()) {
    // Key 'x' exists in the map
} else {
    // Key 'x' does not exist
}

// This method doesn’t modify the map, so the size remains unchanged.
// find() gives you access to the value directly if needed.
// Time Complexity same as (mp[x] > 0)

Approach 2

// The count() method returns the number of occurrences of the key x in the map (which is either 0 or 1 in map and unordered_map).

if (mp.count(x) == 1) {
    // Key 'x' exists in the map
} else {
    // Key 'x' does not exist
}

// Like find(), this method checks for the existence of a key without inserting it, thus avoiding unintended side effects.
// count() is more straightforward if you only need to check for existence and don’t need the value.
// Time Complexity same as (mp[x] > 0)

Demonstrating the Impact

All in one

map<int, int> mp;
mp[1] = 10;
cout << "Initial size: " << mp.size(); // Output: 1
if (mp[2] > 0) {
    // This will insert key '2' with value 0
}
cout << "Size after mp[2] > 0: " << mp.size(); // Output: 2

if (mp.find(3) != mp.end()) {
    // This will not insert key '3'
}
cout << "Size after mp.find(3): " << mp.size(); // Output: 2

if (mp.count(4) == 1) {
    // This will not insert key '4'
}
cout << "Size after mp.count(4): " << mp.size(); // Output: 2

As shown, using mp[2] > 0 increases the map’s size, while find() and count() do not.

Conclusion

Use mp.find(x) != mp.end() or mp.count(x) == 1. These methods are safer and won’t change the map’s size. They also make debugging easier by avoiding unexpected changes to the map, helping you understand and fix issues more easily.

Happy coding!