1

我有一个测试即将进行，似乎有些问题涉及 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，插入单个项目需要恒定的时间。我想这是因为 list 是一个动态的双链循环链。

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

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

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

4

2 回答 2

3

以下是一些注意事项：

  • 正如您所建议的，插入 astd::list需要O(1)时间。
  • 正如您所建议的，插入 astd::vector将需要将向量的所有剩余元素向后移动一个空格，这需要O(n)时间。
  • 该标准不要求 deques 的特定实现，但它确实要求插入到前面和后面需要O(1)时间。
  • 但是，如果您插入容器的中间，则双端队列不需要插入时间。O(1)
  • O(1)顺便说一句，如果您在容器的末尾插入，向量只会提供插入时间。
  • cppreference给出了关于它认为是双端队列的常见实现方法的评论。它说常见的实现是一系列固定长度的数组。所以我们有可以存储，比如说 16 个元素的数组，并且我们有一个std::list（或多或少）这些数组。
  • 据我所知，实现可以std::deque与sd::list. 但是，不这样做可以提高性能。如果一个特定的实现这样做了，那么在双端队列中间插入将是 O(1)。但是，这不是必需的。
  • Astd::deque不能实现为 a std::list，因为它提供了一个随机访问迭代器。这意味着deque::at(4)需要在恒定时间内提供该迭代​​器。Astd::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)。

于 2013-04-30T04:20:58.083 回答
1

如果您想将单个项目插入向量中，由于您提到的原因，它仍然需要线性时间。

deque 实现是特定于实现者的。但是，插入不在前面或后面的位置很可能是线性时间（不是恒定时间）。

于 2013-04-30T04:20:19.147 回答