问题标签 [stddeque]

我正在实现的算法具有以下结构：

重要的是循环 e 的每次迭代都是随机选择的（以均匀的概率）。

理想情况下select，append和remove步骤都是 O(1)。

如果我理解正确，使用std::listandappend步骤remove将是 O(1) 但随机选择将是 O(n) （例如，std::advance在此解决方案中使用）。

并且似乎有互补的 O(1) 和 O(n) 操作std::deque。std::vector

我猜这std::set会引入一些 O(log n) 复杂性。

是否有任何 stl 容器支持我在恒定时间（或摊销恒定时间）内需要的所有三个操作？

以下是导致问题的示例：

如果双端队列以前从未包含任何元素，则添加到空双端队列的迭代器似乎是一个问题。

我很好奇这是否是 STL 中的错误，或者我只是以一种导致未定义行为的方式使用它。我只在使用 Xcode（GUI 和命令行）编译时遇到这个问题。我也在 Linux 上使用 GCC 版本 6.2.0 进行了尝试，但问题似乎并不存在。

我正在尝试遍历 std::deque 并删除其所有内容。我可以一路做到：

或者我可以myDeque.clear()在循环结束后做。我想知道我应该使用哪种方式？谢谢！

我知道 std::queue 默认使用 std::deque 作为其内部容器。我找不到 TBB 的相同信息。

我有一个遗留的多线程应用程序，它当前使用围绕 std::queue<void*, std::list<void*>> 的线程安全包装器来存储相对较大的对象（58 个字节）。我目前正在寻找更好的替代方案来提高性能。

一种选择是摆脱链表并使用默认的 std::deque 作为内部容器，并从指针到对象切换到按值存储对象。分块分配的 std::deque 将在内存方面更好地扩展，因为没有。的元素增加。从缓存的角度来看，也有一些连续的元素会有所帮助。

另一种选择是使用 TBB 的 concurrent_bounded_queue。但是我没有足够的信息来知道将我的对象存储为值是否是一个可行的选择。

也欢迎任何替代建议。

我知道 std::vector 不会减少它的容量，但是由于 std::deque 是按块分配的，我希望它至少可以释放一些不再使用的块。

从我搜索的内容来看，我很困惑，因为答案似乎是“不”或“也许”。有人有具体的答案吗？

如果它不释放它的块，有没有人知道这样做的其他实现？

我正在为当前使用链表但性能不佳的应用程序重新设计集思广益，这就是我考虑使用双端队列的原因。挑战是我的应用程序应该运行一整天，它会有大量的双端队列，每个都可能变得很长，因此我不能忽视双端队列或向量的存储使用。

我试图了解 STL 双端队列是如何在 libcxx 中实现的。

据我了解，libcxx STL 双端队列被实现为包含指向其他向量的指针的向量。这个包含指向其他向量的向量的名称为__map_并且类型为__split_buffer。现在这__split_buffer显然不是 a vector，因为它具有 a没有的push_front功能vector。我的问题是：这个push_front功能的效率如何？这是该push_front函数的源代码：

似乎它使用了move_backward根据 cppreference 标准实现简单地移动数组中的每个元素的函数，这在我看来效率极低。我假设它正在使用一些聪明的 O(1) move_backward 实现，但是我不知道如何找到它正在使用的实现。但是我想它可能真的使用了 O(n) 实现，并且每次调用只调用一次push_front它，将成本摊销到 O(1)，但最坏的情况仍然是 O(n)。

在第一种情况下，看起来整个数组首先__d移动__end_了__d? 这是否意味着该__end_变量会增加它与 之间的全部差异__end_cap()？

在第二种情况下，它看起来首先分配了__split_buffer两倍于 current 容量的a __split_buffer，然后它调用了__construct_at_end可能将整个 current 复制到新分配__map_的END__split_buffer的函数，这似乎是明智的，但也令人惊讶。这是明智的，因为您当然希望该push_front函数有多余的空间来添加新元素。但也令人惊讶，因为您为什么要添加到末尾而不是新分配__split_buffer函数的中间？这不会立即导致新分配__split_buffer的大小再次翻倍吗？

总而言之，我对该函数的理解是，push_front当前面没有更多空闲空间时调用__map_可能会导致以下两种情况之一发生：

1. 分配了一个新__split_buffer的，其大小是旧的两倍，原始内容被复制到新的末尾__split_buffer（这肯定会导致新__split_buffer的大小立即翻倍？）
2. 当前内容移动到__split_buffer. __split_buffer在必须重新分配之前，此操作只能发生一次。

我的理解正确吗？

std::deque与访问随机位置的元素相比，其缺点是性能较慢std::vector，并且存储数据的内存块具有预定义的固定大小。

是否有替代（甚至在 STL 之外）容器类允许：

• 在构造函数中设置所有块的块大小，或
• 为每个块设置不同的块大小。
• 防止大多数索引访问必须执行两次指针取消引用；例如，一旦我访问某个内存块中的元素，同一内存块中的以下访问应该具有std::vector相似的性能。

注意：我对与访问元素相关的性能感兴趣，而不是它们的插入/删除。

我正在尝试Leetcode 问题 239（最大滑动窗口）。
考虑两个实现，Sol1 和 Sol2。溶胶1：

溶胶2：

Sol2 在以下方面与 Sol1 不同：

• deque的back()方法已更改为front()，反之亦然。
• deque的push_front()方法已更改为push_back()，反之亦然。
• deque的pop_front()方法已更改为pop_back()，反之亦然。从逻辑上讲，这两种实现方式是相似的。

根据C++ 双端队列实现，

deques上常见操作的复杂度（效率）如下：

• 随机访问 - 常数 O(1)
• 在末尾或开头插入或删除元素 - 常量 O(1)
• 插入或删除元素 - 线性 O(n)

但我观察到这些实现所消耗的时间和内存存在显着差异。我试图用几个编译器检查，差异仍然存在。

用于测试的结果和整个代码可以在这个gist中找到。为什么两种实现（Sol1 和 Sol2）之间存在差异？当我们使用不同的编译器时也有区别。我无法弄清楚这一点。任何帮助表示赞赏。