使用std::distance获取std::map元素索引时性能低下原因咨询

问题复现 #

业务中使用std::map存储数据，遍历过程中需要同时获取元素的键、值和顺序索引，初始实现代码如下：

void run(const std::map <key, value>& myMap) {
    std::map <key, value>::const_iterator iter;
    for (iter = myMap.begin(); iter != myMap.end(); ++iter) {
        const auto& myKey = iter->first;
        const auto& myValue = iter->second;
        const auto index = std::distance(myMap.begin(), iter);
        // 后续业务处理逻辑
    }
}

该实现功能正常但执行速度慢，通过IgProf性能剖析得到如下结果：

Rank    % total       Self       Self / Children   Function
[39]        8.2       9.06       0.69 / 8.37       run(const std::map <key, value>& myMap)
            5.6  .........       6.16 / 6.17         std::_Rb_tree_increment(std::_Rb_tree_node_base*) [clone .localalias.2] [54]
            1.4  .........       1.50 / 1.50         some process here [175]
            0.3  .........       0.36 / 0.36         std::_Rb_tree_increment(std::_Rb_tree_node_base const*) [428] 
            0.3  .........       0.34 / 0.83         _init [232] 

剖析结果显示红黑树迭代器自增函数std::_Rb_tree_increment占用了极高的时间开销。将循环内的std::distance调用替换为手动维护索引变量++index后，性能得到大幅提升，优化后剖析结果如下：

Rank    % total       Self       Self / Children   Function
[148]       2.3       2.42       0.60 / 1.81       run(const std::map <key, value>& myMap)
            1.7  .........       1.77 / 1.77         some process here [165]
            0.0  .........       0.03 / 0.04         std::_Rb_tree_increment(std::_Rb_tree_node_base*) [clone .localalias.2] [1268]
            0.0  .........       0.01 / 0.37         _init [420]

实际业务中还需要支持获取任意迭代器对应索引的能力，和std::distance提供的能力等价。

性能低下的根本原因 #

std::map底层基于红黑树实现，其迭代器属于双向迭代器，不支持随机访问：

• 对于std::vector、std::array这类使用随机访问迭代器的容器，std::distance的实现是直接计算两个迭代器的指针偏移，时间复杂度为O(1)，几乎没有额外开销。
• 对于双向迭代器，std::distance没有办法直接计算两个迭代器的距离，只能从起始迭代器开始，反复调用迭代器自增操作（也就是性能剖析中看到的std::_Rb_tree_increment，红黑树迭代器自增的底层实现），逐节点移动直到抵达目标迭代器，累计移动的步数得到距离值，时间复杂度为O(n)。

原写法在遍历到第i个元素时，每次都要从容器起始位置重新走i步计算索引，整个遍历流程的时间复杂度从正常遍历的O(n)退化为O(n²)，数据量越大性能损耗越明显，这就是std::_Rb_tree_increment占比异常高的核心原因。手动维护索引的写法全程只需要单次遍历移动n次迭代器，时间复杂度保持O(n)，因此性能会出现量级提升。

任意迭代器查索引的可选方案 #

如果业务确实需要随时获取任意迭代器对应的顺序索引，不要直接对std::map迭代器调用std::distance，可以根据自身业务的读写频率选择适配方案：

• 若场景以查询为主、容器内容修改频率低：可以在每次容器增删操作完成后，单次全量遍历构建key到索引的哈希映射（用std::unordered_map<key, size_t>存储），查询索引时直接查哈希表，时间复杂度O(1)，仅需在容器变更时同步更新映射即可。
• 若场景增删操作频繁、同时需要按序访问和索引查询：替换底层容器为支持顺序统计的平衡树结构（比如顺序统计树），这类结构可以在O(logn)时间复杂度下完成元素增删、任意元素的索引查询，不会出现O(n²)的性能陷阱。
• 若仅在顺序遍历过程中需要使用索引：直接使用手动维护递增索引变量的写法即可，无额外开销，性能最优。

内容的提问来源于stack exchange，提问作者Godly Wolf