我正在寻找一种存储元素数组并支持这些操作的数据结构:
数组在 O(1) 中执行第一个操作，但第二个操作需要 O(n)，而链表则相反。有中间层数据结构吗？说，可以在 O(lg n) 或 O(n^epsilon) “最坏情况”时间进行两种操作的东西？
请注意，我不是要求平衡二叉搜索树。每次添加/删除新元素时，这里的键(索引)都会更改和移动。例如，删除最小元素会将所有其他元素的索引减少 1。
最佳答案
有“AVL-Array”，一种 STL 风格的容器
在 中执行这两个操作O(log n) .
它建立在 AVL-Tree 之上，但它仍然不是
一个关联容器，但顺序。
支持索引访问[]与 vector语义。
请注意，AVL-Array 没有实现 搜索 树，
而是一个顺序容器
碰巧以树的形式出现。索引、迭代、插入
和删除都做你想做的
期待 vector去做。
你可以找到它here
关于data-structures - 快速插入/删除的数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42469129/