具有快速插入和索引的容器？

Question

我正在寻找一个C++容器类,它被编入索引std::vector,但具有快速插入,删除和索引.例如,vector使用底层平衡树实现的接口也将具有O(logN)插入/删除和O(logN)索引.

要明确:我不是在寻找std::map<int, T>.在索引处插入元素N应该增加数组中所有后续元素的索引,而不是这种情况std::map<int, T>.

我找到了AVL Array,它完全符合我的要求.它有正确的界面,但我想看看是否还有其他选择.

你知道其他任何(生产质量)实现吗？也许更流行的东西(提升有什么类似的东西？).内存占用较少的东西？(在我的机器上,在AVL阵列中保存指针的节点是64字节.)

Answer 1

考虑过使用 SkipLists 了吗？基本上它是一个链接列表，顶部添加了多个级别的快捷方式，这些快捷方式被组织为树。没有节点的洗牌，只有一些指针更新。这些快捷方式使您可以更快地迭代列表。我最喜欢的之一。