c++ - 在位置 i 插入元素并根据第 i 个元素返回信息

Question

假设我有一个整数列表:

2, 1, 3, 1, 4, 2, 5, 3, 2

我希望能够在位置 i 处插入一个新的整数.所以假设i是 4，我想插入数字 7。结果将是:

2, 1, 3, 7, 1, 4, 2, 5, 3, 2

插入后，我想根据位置 i 处的数字接收一些信息和更低。例如，第一个 i 的总和数字。在这种情况下，它将是 2 + 1 + 3 + 7 = 13 .

我希望能够一遍又一遍地重复这个过程。

我用 C++ 编写了一个使用 std::list 的程序.这是插入 n 的作用在位置i进入List然后返回 i 的总和第一个数字:

1. 比较最后插入位置k与 i .如果更低，计算sum[j]对于每个 j: k < j < i像这样:sum[j] = sum[j-1] + List[j] - O(n)
2. 查找位置 i - O(n)
3. 插入 n在位置i , 商店 k = i - O(1)
4. 计算并返回sum[i] = sum[i-1] + n - O(1)

这是否可以更有效地完成，也许使用不同的数据结构？在 O(logn) 也许吧？如果是那么怎么办？

Answer 1

如果您想要一个开箱即用的解决方案而不使用新的数据结构或使用第三方库，std::vector 将是您的最佳选择。算法复杂度为:

1. 将最后插入位置k 与i 进行比较。如果较低，计算总和:O(n)
2. 查找位置 i:O(1) 或 O(n) 如果它涉及某种搜索。如果涉及搜索，它仍然比 std::list 快得多。
3. 在位置i处插入n:O(n)
4. 计算并返回sum[i] = sum[i-1] + n:O(1)

从算法/可扩展性的角度来看，这似乎并没有更好，但我们通常不会因为算法的复杂性而看到显着的性能改进。这是由于引用的位置(特别是空间位置)。

机器可以非常快速地顺序浏览连续数据，因为可以在从缓存行中逐出之前访问多个相邻元素。 std::vector 确实有这方面的优势，我们最终受益于它对上述所有 4 种情况的快速、连续、顺序访问。

std::list，当与 std::allocator 一起使用时(尤其是在并非所有节点都被同时分配的上下文中)，往往会调用很多cache-misses 因为它缺乏空间局部性(也部分是由于列表指针的开销减少了可以放入缓存行的元素数量，并且在这种特殊情况下，主要是因为我们每个需要两个列表指针可怜的整数)。

请注意，在针对您的特定问题调整的标准库之外冒险时，可能存在更优化的解决方案，如另一个不错的答案中所述。深入研究低级细节的另一个角度是寻找您自己的自定义分配器，它可以真正帮助任何类型的链接结构。这个答案侧重于 Vanilla C++。在处理顺序容器时，vector 通常是您最好的选择(除非给出其他强有力的理由)，因为它具有连续的、缓存友好的表示形式。