是否有任何数据结构或算法可以像 O(1) 或 O(log(n)) 那样高效地将元素插入数组的任意位置复杂？在 C++ 中有一个链表数据结构，它可以在 O(1) 的复杂度中高效地在 iterator 位置插入一个元素，但是要得到iterator 到那个位置需要 O(n)，这是非常昂贵的。那么有没有任何数据结构可以支持这个函数 void insert(int pos, int val) 在位置 pos 之前插入一个元素 val 和这个函数复杂度小？
最佳答案
一些支持快速“插入到位置”操作的数据结构。
Rope或类似的自平衡树数据结构。
引擎盖下:一个自平衡树，每个节点都包含其子树的“大小”。
插入复杂度:
O(logn)。C++ 实现:SGI STL有一个绳索实现作为扩展。
Skip list或修改。
引擎盖下:
O(logn)链接列表，其节点引用底层列表的元素，允许跳过下面列表中的元素插入复杂度:
O(logn)。C++ 实现:https://codereview.stackexchange.com/questions/116345/skip-list-implementation
SQRT decomposition technique 基于链表的数据结构(不知道有没有名字)。
底层:带有索引数组的双向链表。索引数组有
O(sqrt(n))个元素引用列表的元素，允许一次跳过O(sqrt(n))个元素。 插入复杂度:O(sqrt(n))。
关于c++ - 如何高效地将元素插入到数组的任意位置？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44540230/