STL中支持插入删除与高效第k大查询的数据结构选型

问题分析 #

你需要的整数存储结构需支持以下核心操作：

• 插入、删除：O(logN)时间复杂度
• 查询前20个元素：近似O(1)时间
• 查询第k大元素：性能优于O(k)（目标O(logN)）

std::set虽能覆盖前两项需求，但第k大查询依赖std::advance遍历k步，最坏场景（如中位数查询）会达到O(N)，无法满足性能要求。

推荐方案 #

1. GNU政策型数据结构：ordered_set（带排名支持） #

这是GCC扩展的非标准STL结构，在Linux/类Unix环境及支持GCC的开发场景中广泛可用，完美匹配所有需求：

• 插入/删除：调用insert()/erase()，时间复杂度O(logN)
• 查询前20个元素：从begin()迭代取前20个，O(20)≈O(1)
• 查询第k大元素：使用find_by_order(k-1)（索引从0开始），直接返回目标元素迭代器，时间复杂度O(logN)
• 额外能力：order_of_key(x)可快速查询小于x的元素数量，同样O(logN)

使用前需引入相关头文件并定义类型：

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

using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

示例代码片段：

ordered_set<int> os;
os.insert(5);
os.insert(2);
os.insert(8);

// 获取第2大元素（对应索引1）
auto target = os.find_by_order(1); // 指向元素5
// 查询元素3的排名（小于3的元素总数）
int rank = os.order_of_key(3); // 返回1

2. 标准STL组合方案：std::map + 计数统计（折中方案） #

若无法使用GNU扩展，可通过std::map<int, int>统计每个整数的出现次数，实现近似高效的第k大查询：

• 插入/删除：map[key]++或map[key]--（计数为0时调用erase），时间复杂度O(logM)（M为不同元素数量）
• 查询前20个元素：从map.begin()取前20个，O(20)≈O(1)
• 查询第k大元素：遍历map累加计数直到总和≥k，最坏时间复杂度O(M)，适合不同元素数量远小于总元素数的场景。

方案对比 #

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