c++ - 如何高效地将元素插入到数组的任意位置？

Question

是否有任何数据结构或算法可以像 O(1) 或 O(log(n)) 那样高效地将元素插入数组的任意位置复杂？在 C++ 中有一个链表数据结构，它可以在 O(1) 的复杂度中高效地在 iterator 位置插入一个元素，但是要得到iterator 到那个位置需要 O(n)，这是非常昂贵的。那么有没有任何数据结构可以支持这个函数 void insert(int pos, int val) 在位置 pos 之前插入一个元素 val 和这个函数复杂度小？

Answer 1

一些支持快速“插入到位置”操作的数据结构。

1. Rope或类似的自平衡树数据结构。

   

   引擎盖下:一个自平衡树，每个节点都包含其子树的“大小”。

   插入复杂度:O(logn)。

   C++ 实现:SGI STL有一个绳索实现作为扩展。

2. Skip list或修改。

   

   引擎盖下:O(logn) 链接列表，其节点引用底层列表的元素，允许跳过下面列表中的元素

   插入复杂度:O(logn)。

   C++ 实现:https://codereview.stackexchange.com/questions/116345/skip-list-implementation

3. SQRT decomposition technique 基于链表的数据结构(不知道有没有名字)。

   

   底层:带有索引数组的双向链表。索引数组有 O(sqrt(n)) 个元素引用列表的元素，允许一次跳过 O(sqrt(n)) 个元素。插入复杂度:O(sqrt(n))。