我们可以通过提供提示来优化 'std：：map：：find' 的性能吗？-解网

问：

该方法允许我们通过提供一个“提示”迭代器来优化性能，我们希望该迭代器非常接近放置项目的位置。当您快速连续放置多个项目时，这可能是最有用的。std::map::emplace_hintstd::map::emplace

我正在编写一些代码，我希望需要调用这些代码才能快速连续地获取大量值。我希望钥匙彼此靠近，但不一定是相邻的。没有，但是有没有办法使用标准库中的现有方法做类似的事情？基本上，我只想通过提供一个靠近键的迭代器来加快速度。findstd::map::find_hintfind

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

C++ 优化 stdmap c++-标准库

如果您知道下一个元素就在附近，您可以让迭代器从第一次调用开始并自己递增吗？如果循环中增量并不总是下一个迭代器。一般来说，如果你在到达下一个有趣的元素之前增加的时间少于次数，这应该会更快，否则会更慢。findlog(n)

0赞 sasquires 5/20/2023

@Yksisarvinen 是的，这是有道理的。我可能需要向前或向后迭代，但很容易分辨出正确的方向，因为容器是分类的。谢谢！

2赞 Homer512 5/20/2023

附议改用 .性能差异往往是惊人的。如果您需要对其他一些操作进行排序访问，甚至可以将 a 和 an 放在一起（可能与的包含迭代器一起），只是为了更好的查找速度unordered_mapmapunordered_mapunordered_mapmap

答：

0赞 273K 5/20/2023 #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

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

Can we optimize the performance of `std::map::find` by providing a hint?

评论

评论