为什么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 :: deque 而不是 std :: list 来实现 std :: queue ?

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屋！