C++ - 以对数读取列表，在给定位置插入

Question

我正在寻找行为类似于列表的数据结构，我们可以在任何给定位置插入一个元素，然后在任何给定位置读取一个元素，其中插入和读取应该以对数时间进行。标准库中是否有类似的东西，或者我可能不得不自己编写它(我知道它可以作为树实现)？

Answer 1

std::multiset 表现得非常像对数 std::list你正在寻找

• 迭代是双向的
• 插入/读取是O(log N)

但是请注意(正如@SergeRogatch 所指出的)您为O(log N) 支付的“价格”查找(而不是 O(N) 为 list ) multiset将在插入元素时对其进行排序。这与 std::list 不同.这也意味着您的元素需要使用 std::less<> 进行比较或者您需要提供自己的比较器。

另一种方法是使用 std::unordered_multiset (即哈希表)，其中有 amortized O(1)元素访问，但也没有确定性顺序。但同样，您的元素需要与 std::hash<> 一起使用或者您需要编写自己的哈希函数。