如何高效获取std::map中指定元素的索引？

背景 #

你使用std::map存储数据，需求是保持键的有序性且支持频繁插入/删除，但std::map的迭代器是双向迭代器，不支持随机访问，无法直接O(1)获取元素的索引（即该元素在有序序列中的位置）。以下是两种可行方案：

方案1：直接使用std::distance（适合偶尔调用场景） #

std::distance可以计算两个迭代器之间的元素个数，对于双向迭代器来说，它会从起始迭代器遍历到目标迭代器，时间复杂度为O(n)。如果只是偶尔需要获取索引，这种方法最简单直接：

#include <map>
#include <iterator> // 包含std::distance

int main() {
    std::map<int, int> a;
    for (int i = 0; i < 10; ++i) a[i] = i;
    a.erase(1);
    
    auto it = a.find(2);
    if (it != a.end()) {
        int index = std::distance(a.begin(), it); // index = 1，符合预期
    }
    return 0;
}

方案2：使用支持顺序统计的有序容器（适合频繁高效获取索引） #

如果需要**O(logn)**时间复杂度获取索引，同时保留有序性和高效增删能力，可以使用GCC扩展的策略性数据结构（Policy-Based Data Structures）中的tree。这个结构本质是红黑树，支持order_of_key（获取键的排名/索引）和find_by_order（根据索引获取元素）操作：

代码示例 #

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>

using namespace __gnu_pbds;

// 定义一个支持顺序统计的有序映射，键和值均为int，用红黑树实现
template<typename Key, typename Value>
using ordered_map = tree<
    std::pair<Key, Value>, 
    std::less<std::pair<Key, Value>>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

int main() {
    ordered_map<int, int> a;
    for (int i = 0; i < 10; ++i) {
        a.insert(std::make_pair(i, i));
    }
    a.erase(std::make_pair(1, 1));
    
    // 直接通过键获取索引
    int index = a.order_of_key(std::make_pair(2, 2)); // 返回1，符合预期
    
    // 如果已有迭代器，也可以通过迭代器计算（不过order_of_key更高效）
    auto it = a.find(std::make_pair(2, 2));
    if (it != a.end()) {
        int index_from_it = a.order_of_key(*it); // 同样返回1
    }
    
    std::cout << index << std::endl;
    return 0;
}

说明 #

• tree_order_statistics_node_update是用于支持顺序统计的策略，让容器能够维护每个节点的子树大小，从而实现O(logn)的排名查询。
• 这个扩展是GCC特有的，如果你需要跨编译器兼容，可能需要自己实现支持顺序统计的平衡树，但复杂度较高。

不推荐的方案：手动维护索引映射 #

如果尝试用额外的std::map<Key, int>来记录每个键的索引，在插入或删除元素时，需要更新所有受影响的键的索引（比如删除一个键后，所有比它大的键的索引都要减1），这会导致增删操作的时间复杂度退化为O(n)，完全违背了使用std::map追求高效增删的初衷，因此不建议使用。

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