寻求支持对数插入与计数的C++ STL数据结构或算法

为什么std::set无法满足需求 #

std::set基于红黑树实现，插入操作和upper_bound查找都是O(logn)复杂度，但它的迭代器是双向迭代器而非随机访问迭代器，调用distance(iter, set.begin())需要遍历元素，时间复杂度为O(n)，无法达到对数时间的统计要求。

基于STL组件实现自定义结构 #

你可以通过**树状数组（Fenwick Tree）**结合STL的std::vector来实现需求，核心是利用树状数组的前缀和特性，实现O(logM)的插入和统计操作（M为元素取值范围或离散化后的索引范围）。

适用场景与实现步骤 #

• 有限取值范围：若元素的取值范围已知且不大，可直接用树状数组映射取值与计数。
• 任意取值范围：先对所有待插入元素做离散化（排序去重后分配索引），再用树状数组操作。

示例代码 #

#include <vector>
#include <algorithm>

class FenwickTree {
private:
    std::vector<int> tree;
public:
    explicit FenwickTree(int size) : tree(size + 1, 0) {}

    // 插入元素（对应索引位置计数+1）
    void insert(int idx) {
        while (idx < tree.size()) {
            tree[idx]++;
            idx += idx & -idx;
        }
    }

    // 统计小于value的元素数量（通过离散化索引的前缀和计算）
    int count_less(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & -idx;
        }
        return sum;
    }
};

int main() {
    std::vector<int> elements = {5, 3, 7, 3, 9};
    
    // 离散化处理
    std::vector<int> sorted_unique = elements;
    std::sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(std::unique(sorted_unique.begin(), sorted_unique.end()), sorted_unique.end());

    FenwickTree ft(sorted_unique.size());

    // 插入元素3
    int insert_idx = std::lower_bound(sorted_unique.begin(), sorted_unique.end(), 3) - sorted_unique.begin() + 1; // 树状数组从1开始索引
    ft.insert(insert_idx);

    // 统计小于7的元素数量
    int query_idx = std::lower_bound(sorted_unique.begin(), sorted_unique.end(), 7) - sorted_unique.begin();
    int count = ft.count_less(query_idx); // 此时count为2（已插入的3和后续插入的5）
    
    return 0;
}

总结 #

STL原生容器没有直接提供同时支持O(logn)插入和O(logn)小于值计数的结构，但通过std::vector实现树状数组，并配合离散化处理任意取值范围的元素，即可满足需求。

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