c++ - 如何以对数时间访问 C++ std::set 中的第 k 个元素？

Question

我有一个数字列表，其中我需要支持两种类型的多个查询:我可以删除一个元素，或者我需要在剩余列表中找到第 k 个最小的(每个查询中的 k 可以不同)元素。

因为如果我使用自平衡 BST，这两个都可以在对数时间内得到支持，并且由于 std::set 是在自平衡 BST 上实现的，所以应该有一个 API 用于访问第 k 个元素在对数时间使用它。如果没有这样的方法:

i) 为什么？这对我来说似乎是一个常见的用例。

ii) 实现自平衡树是我唯一的希望，还是我可以使用其他方法让它工作？

Answer 1

您需要使用基于策略的数据结构。

To delete you can use : erase(T elementToerase)
To find the kth element : find_by_order(int k) where k is 0 based indexing
                          it returns iterator to kth element.

这两个操作都是O(logn)

更多详情:https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html