为什么 std::queue 使用 std::dequeue 作为底层默认容器? [英] Why does std::queue use std::dequeue as underlying default container?

问题描述

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

As read on cplusplus.com, std::queue is implemented as follows:

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

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:

......

标准容器类 deque 和 list 满足这些要求要求.默认情况下，如果没有指定容器类特定队列类实例化，标准容器 deque 是用过.

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(这是一个双重-链表).

I am confused as to why deque (a double-ended-queue on steroids) is used as a default here, instead of list (which is a doubly-linked list).

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

It seems to me that std::deque is very much overkill: It is a double-ended queue, but also has constant-time element access and many other features; being basically a full-featured std::vector bar the 'elements are stored contiguously in memory' guarantee.

作为一个普通的 std::queue 只有很少可能的操作，在我看来双向链表应该更有效，因为需要的管道要少得多发生在内部.

As a normal std::queue only has very few possible operations, it seems to me that a doubly-linked list should be much more efficient, as there is a lot less plumbing that needs to happen internally.

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

Why then is std::queue implemented using std::deque as default, instead of std::list?

推荐答案

别再把 list 想成这个用起来很别扭，而且缺少一堆有用的功能，所以它一定是最好的当我不需要这些功能时的选择".

Stop thinking of list as "This is awkward to use, and lacks a bunch of useful features, so it must be the best choice when I don't need those features".

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

list is implemented as a doubly-linked list with a cached count. There are a narrow set of situations where it is optimal; when you need really, really strong reference/pointer/iterator stability. When you erase and insert in the middle of a container orders of magnitude more often than you iterate to the middle of a container.

就是这样.

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

The std datatypes were generally implemented, then their performance and other characteristics analyzed, then the standard was written saying "you gotta guarantee these requirements". A little bit of wiggle room was left.

所以当他们编写 queue 时，可能有人分析了 list 和 deque 的执行情况并发现了 deque 是，所以默认使用 deque.

So when they wrote queue, someone probably profiled how list and deque performed and discovered how much faster deque was, so used deque by default.

在实践中，有人可能会发布一个性能很差的 deque(例如，MSVC 的块大小很小)，但却比 std::list 所需的更差 会很棘手.list 基本上要求每个元素一个节点，这使得内存缓存哭泣.

In practice, someone could ship a deque with horrible performance (for example, MSVC has a tiny block size), but making it worse than what is required for a std::list would be tricky. list basically mandates one-node-per-element, and that makes memory caches cry.

这篇关于为什么 std::queue 使用 std::dequeue 作为底层默认容器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！