8

在cplusplus.com上阅读，std::queue实现如下：

队列被实现为容器适配器，它们是使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。元素被推入特定容器的“后部”并从其“前部”弹出。

底层容器可能是标准容器类模板之一或其他一些专门设计的容器类。该底层容器应至少支持以下操作：

……

标准容器类deque和list满足这些要求。默认情况下，如果没有为特定队列类实例指定容器类，则使用标准容器双端队列。

我很困惑为什么在这里使用deque（类固醇上的双端队列）作为默认值，而不是list（这是一个双向链表）。

在我看来这std::deque太过分了：它是一个双端队列，但也具有恒定时间元素访问和许多其他特性；基本上是一个功能齐全的 std::vector 条，“元素连续存储在内存中”保证。

由于正常情况std::queue下只有很少的可能操作，在我看来双向链表应该更有效率，因为内部需要进行的管道更少。

那么为什么std::queue使用std::deque默认实现，而不是std::list？

4

2 回答 2

8

不要再想list“这很难用，而且缺少一堆有用的功能，所以当我不需要这些功能时，它一定是最好的选择”。

list实现为具有缓存计数的双向链表。在少数情况下它是最佳的；当您需要非常非常强大的引用/指针/迭代器稳定性时。当您在容器中间擦除和插入时，比您迭代到容器中间的次数要高出几个数量级。

这就是它。

通常实现数据类型，然后std分析它们的性能和其他特征，然后编写标准说“你必须保证这些要求”。留下了一点回旋的余地。

所以当他们写的时候queue，有人可能会分析如何list和deque执行并发现速度有多快deque，因此deque默认使用。

在实践中，有人可能会deque以糟糕的性能发布 a （例如，MSVC 的块大小很小），但是让它比 a 所需的更差std::list将是棘手的。 list基本上要求每个元素一个节点，这使得内存缓存哭泣。

于 2016-12-12T14:44:16.593 回答
4

原因是 deque 比 list 快几个数量级。List 分别分配每个元素，而 deque 分配大块元素。

list的好处是可以删除中间的元素，但是队列不需要这个特性。

于 2016-12-12T14:08:51.933 回答