寻找特殊的C++数据结构

Question

我正在寻找符合以下标准的数据结构(或数据结构组合)的C++实现:

• 以与std :: vector相同的方式访问项目
• 提供随机访问迭代器(以及迭代器比较<,>)
• 平均项目访问(:查找)时间最O(log(n))复杂
• 项目按照与添加到容器中相同的顺序进行迭代
• 给定一个迭代器,我可以找出容器中指向的项的序数位置,最糟糕的是O(log(n))复杂性
• 提供项目插入和移除在最复杂的特定位置O(log(n))
• 删除/插入项目不会使先前获得的迭代器无效

提前感谢您的任何建议

DALIBOR

(编辑)答案:

我选择的答案描述了满足所有这些要求的数据结构.然而,正如Maxim Yegorushkin所建议的那样,boost :: multi_index提供的功能非常接近上述功能.

(编辑)未正确指定某些要求.他们根据更正修改(:原创)

(编辑)我发现了接受的答案中描述的数据结构的实现.到目前为止,它按预期工作.它被称为计数器树

(编辑)考虑使用sp2danny建议的AVL-Array

Answer 1

让我们来看看这些...

• 平均项目查找时间最坏的复杂度为 O(log(n))
• 删除/插入项目不会使先前获得的迭代器失效
• 提供最坏 O(log(n)) 复杂度的项目插入和删除

那几乎尖叫着“树”。

• 提供随机访问迭代器（以及迭代器比较 <,> ）
• 给定一个迭代器，我可以找出容器中指向的项目的序号位置，最坏的复杂度为 O(log(n))
• 项目按照添加到容器中的顺序进行迭代

我假设您为随机访问迭代器提供的索引是按插入顺序排列的，因此[0]将是容器中最旧的元素，[1]将是下一个最旧的元素，等等。这意味着，在删除时，对于迭代器为了有效，迭代器内部不能存储索引，因为它可能会在没有通知的情况下发生更改。因此，仅使用map键作为插入顺序的 a 是行不通的。

鉴于此，树的每个节点除了其通常的成员之外，还需要跟踪每个子树中有多少元素。这将允许随着时间的推移进行随机访问O(log(N))。我不知道有一套现成的代码，但子类化std::rb_tree将std::rb_node是我的起点。