c++ - 提示错误时的 emplace_hint 性能

Question

我正在尝试确定是否应该使用 emplace_hint 将 key 插入 multimap(与常规 emplace 相对)。我已经在较早的操作中(在同一个键上)计算了键的范围:

range = multimap.equal_range(key); 

我应该使用 range.first、range.second 还是什么都不作为插入键值对的提示？如果范围为空怎么办？

Answer 1

Should I use range.first, range.second, or nothing as a hint to insert the key, value pair?

作为std::multimap::emplace_hint()状态:

Inserts a new element into the container as close as possible to the position just before hint.

(重点是我的)你应该使用范围内的 second 迭代器，它应该使插入更有效率:

Complexity

Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before hint.

至于空范围，使用 second 迭代器仍然没问题，因为它应该始终指向大于元素或在最后一个元素之后(如果不存在的话)。