问题标签 [deque]

两者有什么区别？我的意思是方法都是一样的。因此，对于用户而言，它们的工作方式相同。

那是对的吗？？

刚才，我正在阅读 Josuttis 的 STL 书。

据我所知——c++ 向量是一个可以重新分配的 c 数组。所以，我明白了，为什么在 push_back() 之后所有的迭代器和引用都会变得无效。

但我的问题是关于 std::deque。据我所知，它是大块数组（c-array of c-arrays）。因此 push_front() 在开头插入元素，如果没有空间，则 deque 分配新块，并将元素放在分配块的末尾。

在中间的 insert() 之后，所有引用和迭代器都变得无效，我明白为什么——所有元素都被移动了。但我真的误解了短语“......在 push_back() 和 push_front() 之后所有引用都保持有效，但迭代器没有”（可以在 @standard:23.2.2.3 找到相同的短语）

这是什么意思？！如果引用有效，则 deque 无法重新分配（== 移动）其元素。那么为什么迭代器会变得无效呢？为什么我不能在插入非移动元素后使用它们？或者这句话的意思是，我不能确定迭代器是否等于 begin() 或 end() 并溢出？

另外，我想提一下，在 erase() 之后，所有迭代器和引用都保持有效（除了被擦除的 :-)）。

PS：请不要以“标准”形式回答：“不能使用，因为标准这么说”。我想了解为什么，会发生什么。

Referring to article Gotw 54 by HerbSutter, he explains about

1. The Right Way To "Shrink-To-Fit" a vector or deque and

2. The Right Way to Completely Clear a vector or deque

Can we just use container.resize() and container.clear() for the above task or am I missing something?

这需要无锁，因为它必须在 SMP 系统的中断处理程序中运行。我不能拿锁。

我有一个包含一些值的连续数组。此数组中的某些条目是“空闲的”，它们未被占用。我想列出这些条目，以便我可以快速分配一个。但是，我有时不得不分配一个任意条目。

因此，我认为以下是一种不错的处理方式：连续数组不仅保存值，还保存左右指针，从而形成双端队列。只有自由值具有有效的左/右指针。我可以快速访问任意节点，因为它只是对双端队列的索引访问。

现在，问题的关键是：是否有一个不错的无锁双端队列算法，它相对有效并且可以支持删除任意节点？

我有以下场景：我有一个线程应该用整数对（本质上是任务描述）填充容器，并且我有大量工作线程（8-16）应该从中获取元素容器并执行一些工作。

我认为这个问题可以通过阻塞队列轻松解决——例如，在删除项目时，线程同步对队列的访问，如果没有可用数据则休眠。

我（也许是错误的）假设这样的东西应该存在于 STL 或 boost 中，但我找不到任何东西。

我真的必须自己实现那个东西吗？这似乎是一个常见的场景......

在 Java 中，有一个名为Deque的类，我想在 .NET (C#) 中找到类似的东西。

我需要这个的原因是因为我需要查看集合中的最后一项，然后将集合中的第一项出列。

谢谢，AJ 拉文迪兰。

我究竟做错了什么？

使用http://www.cppreference.com/wiki/stl/deque/insert作为参考，我将值插入到特定位置的双端队列中。

例如，如果双端队列 A 是：

使用指向 d 的迭代器，我可以：

并且 iter 仍然指向 d。但是，当 iter 指向 g 时，最后一个元素：

但现在 iter 指向 f!!

我目前的解决方法是：

我没有再次测试过这个或任何东西，花了这么多时间跟踪一个错误，只是为了在所有地方发现 insert() 的不一致行为，这很烦人。

与在任何其他位置相比，为什么 insert() 在最后的行为不同？还是我做错了什么？

我有一个围绕 std::deque 的包装器，我用它来排队音频数据（如果重要的话，通过 libavcodec 进入块）。

这是获取 16 位数据缓冲区并将其添加到双端队列的函数

锁定/解锁的定义：

我的问题是，当代码中包含 data_buffer_.insert 语句时，该函数所在的线程将执行一次然后锁定。如果我删除代码，它可以工作。我尝试用 src 数据的手动迭代替换插入，为每个元素调用 push_back()，这也导致线程锁定。

这是将数据附加到双端队列的有效方法吗？我在一个测试程序中尝试过，它似乎工作正常，文档似乎暗示它没问题。为什么这会导致我的线程死亡？

更新信息：添加了锁定/解锁失败时的错误消息，它们都成功了。我对它们进行了检测以验证它们是成对执行的，而且确实如此。一定是 deque::insert 调用搞砸了，我可以删除它，然后事情又开始了。

更新：我发现了问题，我重构了代码并错过了一个常量，所以出队总是检查为满，导致循环 =(

我在玩 Python 的 collection.deque 并编写了以下基准：

这将从具有各种大小的列表/双端队列中弹出（0）/popleft（）。结果是：

我的问题是：为什么小型双端队列和列表（约 1000 个元素）的性能几乎相同？