std::map 范围内的二进制搜索比整个地图的 map::find() 搜索慢

Question

背景知识：我是 C++ 新手。我有一个 std::map 并且正在尝试按键搜索元素。

问题：性能。当地图变大时，map::find() 函数变慢。

首选方法：我经常大致知道元素应该在地图中的哪个位置；我可以提供一个 [first,last) 的搜索范围。这个范围总是很小的 w.r.t。地图中的元素数量。我有兴趣编写一个带有边界提示的简短二进制搜索实用程序函数。

尝试：我从https://en.cppreference.com/w/cpp/algorithm/lower_bound偷了下面的函数并做了一些粗略的基准测试。对于大地图和小地图，此函数似乎比 map::find() 慢得多，无论提供的范围提示的大小或位置如何。我用随机 ints 的比较替换了比较语句 (it->first < value) 并且减速似乎已经解决，所以我认为减速可能是由 it->first.[= 的取消引用引起的21=]

问题：取消引用是问题吗？或者是否正在进行某种不必要的 copy/move 操作？我想我记得读过地图不会按顺序将它们的元素节点存储在内存中，所以我只是得到了一堆缓存未命中？减速的可能原因是什么，我将如何解决它？

/* @param first     Iterator pointing to the first element of the map to search. 
 * @param distance  Number of map elements in the range to search.
 * @param key       Map key to search for. NOTE: Type validation is not a concern just yet.
 */    
template<class ForwardIt, class T>
ForwardIt binary_search_map (ForwardIt& first, const int distance, const T& key) {
    ForwardIt it = first;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = distance;  
          
    while (count > 0) {
        it = first;
        step = count/2;
        std::advance(it, step);
        if (it->first < value) {
            first = ++it;
            count -= step + 1;
        }
        else if (it->first > value)
            count = step;
        else {
            first = it; 
            break; 
        }
    }
    return first;
}

Answer 1

std::map::find() 存在是有原因的。该实现已经进行了二分搜索，因为 std::map 有一个平衡二叉树作为实现。

您的二分搜索实现速度要慢得多，因为您无法利用该二叉树。如果你想获取地图的中间，你可以从 std::advance 开始，它获取第一个节点（位于树的叶子）并通过几个指向你认为是中间的指针导航。之后，您再次需要从这些叶节点之一转到下一个。再次遵循很多指示。

结果：除了更多的循环之外，还有很多缓存未命中，尤其是当地图很大时。

如果您想改进地图中的查找，我建议您使用不同的结构。当顺序不重要时，您可以使用 std::unordered_map。当顺序很重要时，您可以使用排序的 std::vector<std::pair<Key, Value>>。如果您有可用的提升，这已经存在于名为 boost::container::flat_map.

的 class 中

std::map 范围内的二进制搜索比整个地图的 map::find() 搜索慢

Binary search of range in std::map slower than map::find() search of whole map

c++

optimization

iterator

stdmap

binary-search