46 Intermediate The Hundred
The Two Keys That Became One
two spellings go in, one comes out
struct CaseInsensitive {
bool operator()(const std::string& a, const std::string& b) const {
return std::lexicographical_compare(
a.begin(), a.end(), b.begin(), b.end(), [](char x, char y) {
return std::tolower(static_cast<unsigned char>(x)) <
std::tolower(static_cast<unsigned char>(y));
});
}
};
int main() {
std::map<std::string, int, CaseInsensitive> stock;
stock.insert({"Apple", 5});
stock.insert({"APPLE", 9}); // a different string, a different entry... right?
std::cout << "entries: " << stock.size() << "\n";
for (const auto& [name, n] : stock)
std::cout << name << " -> " << n << "\n";
}
Run it. What does it print?
Why¶
A std::map never asks whether two keys are ==. It asks the comparator twice, and if
comp(a, b) and comp(b, a) are both false the keys are equivalent — the only
notion of "same key" the container has. CaseInsensitive calls neither "Apple" nor
"APPLE" smaller, so the second insert finds an existing element and declines to
overwrite it (entry 43), returning a false the snippet throws away. The first spelling
survives because a map key is const; operator[] is no safer, as stock["APPLE"] = 9;
leaves the key Apple and swaps only the value. Lookup obeys the same rule, so
stock.at("apple") returns 5 and stock.erase("APPLE") erases it. Nothing here is
broken — this is a valid strict weak ordering (break that and you get entry 83) — so
-Wall -Wextra have nothing to say.
The fix¶
Make the comparator agree with your real notion of identity, or normalize keys on the way in so the stored spelling can't surprise you:
std::map<std::string, int> stock; // spellings differ → entries: 2
stock.insert({to_lower(name), n}); // or: one canonical spelling per key
if (!stock.insert({name, n}).second) { /* already present — decide what that means */ }
Takeaway: a comparator doesn't just order a std::map — it defines what "same key" means.
Try it: g++ -std=c++17 main.cpp -o demo && ./demo