c++ - 在 map 中搜索 : Member vs. 非成员 lower_bound

Question

我需要在 std::map 中查找两个元素。由于我的 map 是稀疏的，我可能没有每个键的条目，所以我使用 lower_bound 进行查找。为了简单起见，让我们假设我总能找到这样的两个元素，并且它们总是不同的。

最快的解决方案当然是:

auto it1 = my_map.lower_bound(k1);
auto it2 = my_map.lower_bound(k2);

但是，我知道索引 k2 处的元素位于 begin 和索引 k1 处的元素之间。因此，我正在考虑使用 std::lower_bound 进行第二次查找，以避免再次搜索整个范围:

auto it1 = my_map.lower_bound(k1);
auto it2 = std::lower_bound(begin(my_map), it1, k2);

对第二种解决方案有什么意见吗？复杂性方面它应该更好，但它看起来比原始代码更不愉快，我想知道它是否值得打扰。此外，由于我在第二次调用中使用非成员 lower_bound，我是否应该预料到任何缺点？

Answer 1

主要缺点是非成员 std::lower_bound 必须依赖 map 提供的双向迭代器。因此，虽然它能够执行 O(log(n)) 比较，但它仍然必须执行 O(n) 迭代。

另一方面，成员 lower_bound() 知道 map 的内部结构，通常是某种二叉树。这意味着它能够以标准算法无法实现的方式进行遍历。