带提示的std::map::insert/assign元素已存在时的时间复杂度及疑问

针对你提出的两个疑问，我结合C++标准和实际使用经验来解答：

1. 元素已存在时，带提示的insert/assign的时间复杂度 #

首先明确：当元素已存在时，std::map::insert（带提示参数的重载）不会执行插入操作，只会返回指向已存在元素的迭代器和false（表示未插入）。

关于时间复杂度，核心在于你传入的提示位置是否准确：

• 如果提示位置恰好是该元素实际所在的位置（也就是lower_bound(key)返回的位置），那么只需要常数次键比较就能确认元素已存在，时间复杂度为O(1)（均摊常数）。
• 如果提示位置偏离了实际位置，容器需要在红黑树中遍历查找该键的真实位置，最坏情况下时间复杂度为O(log n)，和不带提示的insert操作一致。

CPP参考手册里提到的emplace_hint的时间复杂度描述，其实也完全适用于带提示的insert——毕竟emplace_hint是直接构造元素，而带提示的insert是拷贝/移动元素，两者的位置查找逻辑是一致的。当元素已存在时，只要提示位置精准，就能做到常数时间的检查。

2. 提示位置应当用lower_bound还是upper_bound？ #

结论是：优先使用lower_bound(key)作为提示位置，原因如下：

• lower_bound(key)返回的是std::map中第一个不小于key的元素位置：
  • 如果key已存在，这个位置就是该元素的迭代器；
  • 如果key不存在，这个位置就是key应该插入的位置。
    无论哪种情况，这个位置都是最“精准”的提示，能让insert/emplace_hint直接定位到目标位置，确保常数时间的操作。
• 而upper_bound(key)返回的是第一个大于key的元素位置：
  • 当key不存在时，它和lower_bound(key)返回的位置相同，此时用它做提示没问题；
  • 但当key已存在时，它指向的是key对应元素的下一个位置，这时候容器需要从该位置往前遍历确认元素已存在，可能会丢失常数时间的优势，最坏退化为O(log n)。

简单来说，lower_bound是“通用型”的最优提示位置，不管元素是否存在都能完美适配；upper_bound只在元素不存在时和lower_bound效果一致，元素存在时就不合适了。

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