这个问题问得特别实用！毕竟STL的std::set作为关联容器，本身只提供了按键访问的接口，没有直接给元素索引的功能——但咱们确实能通过一些技巧实现低于O(n)的时间复杂度，下面我详细拆解两种主流方案，再补充几个可行思路：

核心原理 #

std::set里的元素是严格有序的，所以一个元素的“索引”本质上就是集合中比它小的元素的个数。我们可以通过离散化给每个元素分配唯一的排名ID，再用Fenwick树（也就是二叉索引树）来高效维护和查询这个“比它小的元素数量”，从而得到索引。

步骤拆解 #

1. 离散化处理：如果元素是任意类型（比如自定义结构体、范围很大的整数），先收集所有可能插入的元素，排序去重后给每个元素分配一个唯一的ID（从1开始，方便Fenwick树操作）。如果元素是已知范围的小整数，这一步可以跳过。
2. 同步维护Fenwick树：每次向set插入元素时，在Fenwick树对应ID的位置+1；删除元素时则-1，用来实时统计元素的数量分布。
3. 查询索引：对目标元素，先用二分查找找到它的离散化ID，再查询Fenwick树中[1, ID-1]的前缀和——这个和就是该元素在set中的索引（从0开始计数）。

代码示例 #

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

// 实现一个简单的Fenwick树
class FenwickTree {
private:
    std::vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 1, 0) {}

    // 给idx位置加上delta（插入+1，删除-1）
    void update(int idx, int delta) {
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }

    // 查询[1, idx]的前缀和
    int query(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
};

int main() {
    std::set<int> s;
    // 假设我们已知所有可能插入的元素（实际场景可以动态收集）
    std::vector<int> all_elements = {5, 2, 8, 3, 1};
    std::sort(all_elements.begin(), all_elements.end());
    // 去重得到唯一元素列表
    all_elements.erase(std::unique(all_elements.begin(), all_elements.end()), all_elements.end());
    FenwickTree ft(all_elements.size());

    // 封装插入操作：同步更新set和Fenwick树
    auto insert_element = [&](int val) {
        s.insert(val);
        // 找到val对应的离散化ID（从1开始）
        int id = std::lower_bound(all_elements.begin(), all_elements.end(), val) - all_elements.begin() + 1;
        ft.update(id, 1);
    };

    // 插入几个测试元素
    insert_element(5);
    insert_element(2);
    insert_element(8);

    // 查询元素2的索引：比它小的元素有0个，所以索引是0
    int target = 2;
    int target_id = std::lower_bound(all_elements.begin(), all_elements.end(), target) - all_elements.begin() + 1;
    int index = ft.query(target_id - 1);
    std::cout << "Index of " << target << " is " << index << std::endl; // 输出0

    // 查询元素5的索引：比它小的元素有1个（2），所以索引是1
    target = 5;
    target_id = std::lower_bound(all_elements.begin(), all_elements.end(), target) - all_elements.begin() + 1;
    index = ft.query(target_id - 1);
    std::cout << "Index of " << target << " is " << index << std::endl; // 输出1

    return 0;
}

时间复杂度分析 #

• 插入/删除：set的操作是O(logn)，Fenwick树的更新是O(logm)（m是离散化后的元素总数，最坏等于n），总时间O(log²n)。
• 查询索引：二分查找ID是O(logm)，Fenwick树查询前缀和是O(logm)，总时间O(log²n)。

核心原理 #

PBDS是GCC编译器提供的扩展数据结构库，其中的ordered_set在std::set的红黑树基础上，额外维护了每个子树的节点数量，因此可以直接提供order_of_key（获取元素索引）和find_by_order（按索引找元素）的接口，时间复杂度都是O(logn)。

步骤拆解 #

1. 引入头文件：需要包含PBDS的关联容器和树策略头文件。
2. 定义ordered_set类型：默认不允许重复元素，如果要存重复元素，可以用pair（第二个元素用唯一标识）或者修改排序规则。
3. 直接调用接口：用order_of_key(x)获取x的索引，用find_by_order(k)获取第k个元素的迭代器。

代码示例（无重复元素） #

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

// 使用PBDS的命名空间
using namespace __gnu_pbds;

// 定义ordered_set：键类型int，无映射值，按升序排序，红黑树实现，维护节点统计信息
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ordered_set<int> os;

    // 插入测试元素
    os.insert(5);
    os.insert(2);
    os.insert(8);
    os.insert(3);

    // 获取元素3的索引：比3小的元素有1个（2），所以索引是1
    int index = os.order_of_key(3);
    std::cout << "Index of 3 is " << index << std::endl; // 输出1

    // 获取索引为2的元素：集合中第3个元素（从0开始）是5
    auto it = os.find_by_order(2);
    std::cout << "Element at index 2 is " << *it << std::endl; // 输出5

    return 0;
}

处理重复元素的方案 #

如果需要存储重复元素，可以用pair<T, int>，其中第二个元素是唯一的自增ID，确保每个键的唯一性：

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

using namespace __gnu_pbds;

template<typename T>
using ordered_multiset = tree<std::pair<T, int>, null_type, less<std::pair<T, int>>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ordered_multiset<int> oms;
    int unique_id = 0;

    // 插入两个2，用不同的unique_id区分
    oms.insert(std::make_pair(2, unique_id++));
    oms.insert(std::make_pair(2, unique_id++));
    oms.insert(std::make_pair(5, unique_id++));

    // 查询第一个2的索引：0
    int index1 = oms.order_of_key(std::make_pair(2, 0));
    std::cout << "Index of first 2 is " << index1 << std::endl; // 输出0

    // 查询第二个2的索引：1
    int index2 = oms.order_of_key(std::make_pair(2, 1));
    std::cout << "Index of second 2 is " << index2 << std::endl; // 输出1

    return 0;
}

时间复杂度分析 #

所有操作（插入、删除、查询索引、按索引查找）都是O(logn)，因为底层红黑树的每个节点维护了子树大小，计算排名时可以在遍历树的过程中累加子树大小，无需额外遍历。

1. 自定义红黑树：自己实现红黑树，给每个节点添加subtree_size字段，在插入、删除时维护这个值，这样就能在O(logn)时间内计算元素的排名。但这种方法需要编写大量底层代码，不如直接用PBDS高效。
2. 有序向量+二分查找（仅适合查询密集场景）：用std::vector存储元素，每次插入时用lower_bound找到位置并插入（O(n)时间），查询索引时用lower_bound直接得到（O(logn)时间）。这种方法插入删除效率低，但实现简单，适合修改少、查询多的场景。

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