c++ - 在 STL 类模板中插入操作

Question

我有一个测试即将进行，似乎有些问题涉及 STL 类模板函数。许多处理算法的复杂性，所以我试图降低基本操作的复杂性。令我感到困惑的一个是插入操作。插入操作采用给定的容器，允许从迭代器指向的某个位置开始插入:

vector<int> vector1;

for (int i=1; i<6; i++) vector1.push_back(i);

vector<int>::iterator it;

it = vector1.begin();

vector1.insert(it+2,10);

现在，我认识到对于大多数插入操作而言，插入操作将花费线性时间。但是，如果我要插入单个项目，这仍然需要线性时间吗？我问这个是因为对于列表 STL，插入单个项目需要常数时间。我认为这是因为列表是一个动态的双链接循环链。

vector 是一个动态的、连续的存储结构，那么这是否意味着对于 vector[size-1] 之前的任何插入，插入之后的所有项目都必须向上移动一个单位？

现在，对于双端队列。我将双端队列 STL 视为一个由数组中的指针指向的单链系统；它是否正确？如果是这种情况，单次插入双端队列，而不是在前面或后面，会是 O(1) 吗？

谢谢，抱歉问了这么多问题。

Answer 1

这里有一些注意事项:

• 正如您所建议的，插入 std::list 需要 O(1) 时间。
• 正如您所建议的，对 std::vector 的插入将需要将 vector 的所有剩余元素向后移动一个空格，这需要 O(n) 时间.
• 该标准不要求双端队列的特定实现，但确实要求插入到前端和后端花费 O(1) 时间。
• 但是，如果您将双端队列插入到容器中间，则双端队列不需要O(1) 插入时间。
• 顺便说一句，如果您在容器的末尾插入， vector 仅提供 O(1) 插入时间。
• cppreference给出了一个关于感觉是双端队列的常见实现方法的评论。它说常见的实现是一系列固定长度的数组。所以我们有可以存储 16 个元素的数组，并且我们有这些数组的 std::list(或多或少)。
• 据我所知，一个实现 可以以与 sd::list相同的方式实现 std::deque。但是，不这样做可以提高性能。 如果一个特定的实现做到了这一点，那么在双端队列中间插入将是 O(1)。然而，这不是必需的。
• A std::deque 不能作为 std::list 实现，因为它提供了一个随机访问迭代器。这意味着 deque::at(4) 需要在恒定时间内提供该迭代​​器。 std::list 做不到这一点。

---

关于为什么通用 deque::insert 会是 O(n) 的评论，这是我的想法。假设我们使用 cppreference 的双端队列实现。

让我们创建一个包含 10 个元素的双端队列。一个接一个插入。我们假设双端队列是由 4 个元素的数组实现的。

因此，当前的双端队列实现为:

[ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, _, _ ]

让我们在后面插入一个元素。

[ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ]

让我们在前面插入一个元素

[ _, _, _, E] <-> [ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ]

所有这些操作都说明了它们如何以 O(1) 的方式工作。

如果我们在数组的中间插入一个元素会怎么样。

[ _, _, _, E] <-> [ E, E, E, E ] <-> [ E, E, E, E ] <-> [ E, E, E, _ ]
                                      ^ I want to insert here!

为此，我需要将 7 个元素移开。这就是为什么这个操作可能是 O(n)。