如何通过索引访问C++ std::map的键？求支持键访问与有序索引只读访问的类map结构

刚好我之前碰到过类似的需求，给你几个实用的解决方案：

1. GCC专属扩展：Policy-Based Data Structures（PBDS）有序树 #

GCC提供了一个非标准但非常好用的扩展库，里面的tree结构完美契合你的要求——它既像std::map一样支持按键的O(log n)查找、插入、删除，还能通过**排序后的位置（排名）**进行O(log n)的随机访问。

快速上手示例 #

首先得引入对应的头文件：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

然后定义你的自定义map类型，指定启用order statistic功能：

// 定义和std::map<int, std::string>功能一致，但支持按排名访问的结构
template<typename Key, typename Value>
using ordered_map = tree<
    Key, 
    Value, 
    std::less<Key>,  // 键的排序规则，和std::map一致
    rb_tree_tag,     // 底层用红黑树，和std::map相同
    tree_order_statistics_node_update  // 启用排名统计功能
>;

核心操作演示 #

int main() {
    ordered_map<int, std::string> my_map;
    my_map[1] = "one";
    my_map[3] = "three";
    my_map[2] = "two";

    // 和std::map完全一样的按键访问，O(log n)
    std::cout << my_map[2] << std::endl; // 输出 "two"

    // 按排序后的位置访问（从0开始计数），O(log n)
    // 排序后键的顺序是1、2、3，索引1对应的是键2
    auto it = my_map.find_by_order(1);
    std::cout << it->first << ": " << it->second << std::endl; // 输出 "2: two"

    // 反过来，查询某个键在排序后的位置（前面有多少个更小的键），O(log n)
    int rank = my_map.order_of_key(3);
    std::cout << "键3的排名是：" << rank << std::endl; // 输出 "键3的排名是：2"

    return 0;
}

这个结构底层就是红黑树，和std::map的性能特性完全一致，只是多了排名访问的能力，完全满足你的需求。

2. 纯标准库的折中方案（无扩展依赖） #

如果你的项目不能依赖GCC扩展，那只能用标准库组件自己组合，但要做好性能取舍：

• 如果你是读多写少的场景：可以同时维护一个std::map<Key, Value>和一个排序后的std::vector<std::pair<Key, Value>>。每次修改map后，重新生成vector（O(n log n)），查询时用map做按键访问，用vector做随机访问。这种方式简单，但修改操作耗时较高。
• 如果需要修改操作也是O(log n)：那得自己实现一个支持order statistic的平衡二叉树，每个节点维护子树的大小，这样就能通过排名快速定位节点。不过这个实现起来比较繁琐，需要自己处理红黑树或AVL树的旋转、子树大小更新等逻辑。

3. 第三方库选项 #

比如Boost库中的boost::intrusive::rbtree，可以自定义节点结构，添加子树大小字段，从而实现排名访问的功能。不过这需要你熟悉Boost的侵入式容器用法，相对来说学习成本高一点。

总结 #

如果可以用GCC扩展，PBDS的tree结构绝对是最优解，完全匹配你要的所有特性：

• 支持[]运算符按键O(log n)访问值
• 支持按排序位置的O(log n)只读随机访问
• 和std::map性能一致

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