我们可以通过提供提示来优化 `std::map::find` 的性能吗？

Question

方法

std::map::emplace_hint

允许我们通过提供一个“提示”迭代器来优化

std::map::emplace

的性能，我们希望它非常接近放置项目的位置。当您快速连续放置许多物品时，这可能是最有用的。

我正在编写一些代码，我希望在其中调用

find

以快速连续获取大量值。我希望按键彼此靠近但不一定相邻。没有

std::map::find_hint

，但是有没有办法使用标准库中的现有方法来做类似的事情？基本上，我只是想通过提供一个接近键的迭代器来加速

find

。

当然，这个问题可能更广泛地适用于大多数已排序的 C++ 标准库容器，但今天我特别感兴趣

std::map

.

Answer 1

不，我们不能。这是完整的

std::map

手册。

如果您非常确定下一个要查找的键可以在不到

std::find_if()

迭代器的后续步骤中到达，则可以使用

log_2(map.size())

算法。

#include <algorithm>
#include <iostream>
#include <map>

int main() {
  std::map<int, int> m{{1, 1}, {2, 2}};

  auto it = m.find(1);
  if (it != m.end())
    std::cout << it->second << " ";

  int k = 2;  // next key to find
  it = std::find_if(it, m.end(),
    [k](const auto& v) { return v.first == k; });
  if (it != m.end())
    std::cout << it->second << "\n";
}

// Output: 1 2