如何在透明比较的std::map中插入不存在的兼容键？

针对你的需求，我们可以利用std::map::lower_bound实现单次查找+按需构造T的目标，完美规避现有两种方案的缺陷：

// 以K=std::string、KK=std::string_view、T=int为例
auto it = map.lower_bound(key);
if (it != map.end() && !(map.key_comp()(key, it->first))) {
    // 键已存在，返回对应值
    return it->second;
} else {
    // 键不存在，构造K类型键并插入默认构造的T，返回新值
    it = map.emplace_hint(it, K(key), T{});
    return it->second;
}

为什么这个方法更优？ #

• 仅一次查找：lower_bound只执行一次二叉树查找，找到插入位置后，emplace_hint会直接在该位置插入元素，不会再次遍历树结构，避免了方案二的两次查找开销。
• 按需构造T：只有确认需要插入新元素时，才会构造T{}，解决了方案一中无论是否需要都构造T的性能浪费问题。

关键细节说明 #

• 因为使用了std::less<>作为比较器，它支持KK与K类型的异序比较（比如std::string_view和std::string），所以lower_bound可以直接传入KK类型的key。
• 判断键是否存在时，不能直接用it->first == key（KK和K可能不支持==运算符），必须借助map的key_comp()比较器：结合lower_bound返回“第一个不小于key的元素”的特性，!(map.key_comp()(key, it->first))就能确认当前迭代器指向的元素与key等价。
• emplace_hint接受迭代器作为插入位置提示，当提示准确时，插入操作的均摊时间复杂度为O(1)，进一步提升效率。

现有方案的缺陷回顾 #

• 方案一：insert(std::pair<KK, T>{key, T{}})——无论key是否存在，都会提前构造T{}，若T的构造代价较高，会造成不必要的性能损耗。
• 方案二：先find再insert——find和insert各自执行一次查找，当map元素较多时，两次二叉树遍历的开销会被放大。

内容的提问来源于stack exchange，提问作者Bolpat