c++ - 我可以将元素插入 map 的给定迭代器吗？

Question

我有一个std::map。我找到一个键的下限并确保该键未在 map 中使用。我可以将元素插入 map 的给定迭代器吗？如果是怎么办？

map<int, double> m;
int key = 1;
auto itr = m.lower_bound(key);
if (itr == m.end() || itr->first != key)
    m.insert(itr, make_pair(key, 3.14)); // how is the performance? Any better way?

Answer 1

关联容器要求关于 emplace_hint 和相关操作，复杂度“通常是对数的，但如果元素恰好插入到 p 之前，则摊销常数”(其中p 是提示迭代器)。

因此，如果您只使用正确的提示，那么复杂度是摊销常数，与 map 的大小无关。 (当然，您仍然需要执行初始查找的成本。)