6

我deque::insert()从 C++ 标准 2003（第 23.2.1.3 章）中了解了如下的复杂性：

在最坏的情况下，将单个元素插入双端队列所需的时间与从插入点到双端队列开头的距离和从插入点到双端队列末尾的距离的最小值呈线性关系。

我总是将 stl deque 的实现理解为内存块的集合。因此，插入只会影响与插入位置相同的内存块中的元素。我的问题是，“从插入点到双端队列开头的距离和从插入点到双端队列末尾的距离的最小值线性”是什么意思？

我的理解是因为 C++ 标准没有强制执行双端队列的特定实现。复杂性通常只针对最坏的情况。然而，在编译器的实际实现中，它与内存块中元素的数量成线性关系，这可能因元素大小而异。

另一个猜测可能是，由于insert()会使所有迭代器失效，所以 deque 需要更新所有迭代器。因此它是线性的。

4

4 回答 4

8

std::deque 通常（总是？）实现为内存块的集合，但它通常不会插入一个全新的块，只是为了让您在集合中间插入一个新元素。因此，它会查找插入点是否更靠近开头或结尾，并打乱现有元素以为现有块中的新元素腾出空间。它只会在集合的开头或结尾添加一块新的内存。

于 2011-09-27T16:35:20.613 回答
3

我认为图表会更好地为您服务……让我们来玩 ASCII 艺术吧！

一个双端队列通常是一个内存块数组，但除了前内存块和后内存块外，其他所有内存块都是满的。这是必要的，因为双端队列是一个 RandomAccessContainer，并且要获得对任何容器的 O(1) 访问权限，您不能拥有无限数量的容器来读取大小：

bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; }

T& operator[](size_t i) {
  if (i < first.size) { return first[SIZE - i]; }

  size_t const correctedIndex = i - first.size;
  return buckets[correctedIndex / SIZE][correctedIndex % SIZE];
}

由于乘法/除法，这些操作是 O(1)！

在我的示例中，我假设一个内存块在包含 8 个元素时已满。在实践中，没有人说大小应该是固定的，只是所有内部桶都应该具有相同的大小。

 // Deque
 0:       ++
 1: ++++++++
 2: ++++++++
 3: ++++++++
 4: +++++

现在假设我们要在索引 13 处插入。它位于标记为 2 的存储桶中的某个位置。我们可以考虑以下几种策略：

  • 扩展存储桶 2（仅）
  • 在 2 之前或之后引入一个新的桶，并且只打乱几个元素

但是这两种策略会违反所有“内部”存储桶具有相同数量的元素的不变量。

因此，在我们的例子中，我们只能在开始或结束（以更便宜的那个为准）周围改组元素：

 // Deque
 0:      +++
 1: ++++++++
 2: +O++++++
 3: ++++++++
 4: +++++

请注意存储桶 0 是如何增长的。

这种洗牌意味着，在最坏的情况下，您将移动一半的元素：O(N/2)。

deque虽然在开头或结尾都有 O(1) 插入，因为只需在正确的位置添加元素或（如果桶已满）创建一个新桶。

还有其他容器在随机索引处具有更好的插入/擦除行为，基于B+ Trees。在索引 B+ 树中，您可以代替“键”（或并行）在内部维护某个位置之前的元素计数。有多种技术可以有效地做到这一点。最后你会得到一个容器：

  • O(1)：空，大小
  • O(log N)：在、插入、擦除

您可以检查blistPython 中的模块，该模块实现了由这种结构支持的类似 Python 列表的元素。

于 2011-09-27T18:13:27.033 回答
2

你的猜想是……99.9% 正确。一切都取决于实际的实现是什么。标准规定的是实现者（如果不符合规范则不能声称是标准）和用户（如果编写独立于实现的代码，则不能期望“更好的性能”）的最低要求。

规范背后的想法是一块（a == one）未初始化的内存，其中元素被分配在中心周围......直到它们有空间。插入中间意味着移位。在前端或末端插入意味着就地构建。（当不存在空间时，完成重新分配）索引和迭代器在修改后不能被信任，因为我们不能假设已经移动了什么以及朝哪个方向移动。

更高效的实现不使用单个块，而是使用多个块来重新分配“移位”问题并从底层系统以恒定大小分配内存（从而限制重新分配和碎片）。如果您针对其中之一，您可以期待更好的性能，否则您最好不要假设任何结构优化。

于 2011-09-27T16:46:10.047 回答
1

与插入的元素数量呈线性关系（复制构造）。另外，根据特定的库实现，额外的线性时间最多可达位置和双端队列的一端之间的元素数量。 参考...

于 2011-09-27T16:42:09.193 回答