如阅读 cplusplus.com , std::queue
实现如下:
queues are implemented as containers adaptors, which are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements. Elements are pushed into the "back" of the specific container and popped from its "front".
The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:
......
The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.
我很困惑为什么这里默认使用 deque(类固醇的双端队列),而不是 list(这是一个双端队列)链表)。
在我看来,std::deque
有点矫枉过正:它是一个双端队列,但也具有常量时间元素访问和许多其他功能;基本上是一个功能齐全的 std::vector 栏,“元素连续存储在内存中”保证。
作为一个普通的 std::queue
只有很少的可能操作,在我看来双向链表应该更有效,因为需要的管道要少得多发生在内部。
为什么 std::queue
默认使用 std::deque
而不是 std::list
实现?
最佳答案
不要再将 list
想成“这使用起来很笨拙,而且缺少一堆有用的功能,所以当我不需要这些功能时,它一定是最好的选择”。
list
被实现为一个带有缓存计数的双向链表。在少数情况下它是最佳的;当您真正需要非常强大的引用/指针/迭代器稳定性时。当您在容器中间删除和插入的次数比迭代到容器中间的次数多几个数量级。
就是这样。
一般实现std
数据类型,然后分析它们的性能和其他特性,然后编写标准说“你必须保证这些要求”。留有一点回旋余地。
因此,当他们编写 queue
时,可能有人分析了 list
和 deque
的执行情况,并发现了 deque
的速度有多快> 是,所以默认使用 deque
。
在实践中,有人可以发布性能糟糕的 deque
(例如,MSVC 的 block 大小很小),但比 std::list 所需的更糟糕
会很棘手。 list
基本上要求每个元素一个节点,这会让内存缓存崩溃。
关于c++ - 为什么 std::queue 使用 std::dequeue 作为底层默认容器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41102465/