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

Question

我正在寻找满足以下条件的数据结构(或数据结构的组合)的 C++ 实现:

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

提前感谢您的任何建议

达利博尔

(编辑)答案:

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

(编辑)一些要求没有正确指定。它们是根据更正(:original)

修改的

(编辑)我找到了已接受答案中描述的数据结构的实现。到目前为止，它按预期工作。它叫做counter tree

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

Answer 1

根据您的要求，使用两个索引的 boost::multi_index 就可以了。

第一个索引是ordered index .它允许 O(log(n)) 插入/查找/删除。第二个索引是 random access index .它允许随机访问，并且元素按插入顺序存储。对于这两个索引，当其他元素被删除时，迭代器不会失效。从一个迭代器转换为另一个迭代器是 O(1) 操作。