C++双端队列与向量和 C++地图与集合
有人可以告诉我向量和双端队列之间有什么区别吗？我知道C++中向量的实现，但不知道双端队列。另外，map 和 set 的界面对我来说似乎很相似。两者有什么区别以及何时使用其中之一。
Can some one please tell me what is the difference between vector vs deque. I know the implementation of vector in C++ but not deque. Also interfaces of map and set seem similar to me. What is the difference between the two and when to use one.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
std::vector：动态数组类。内部内存分配确保它始终创建一个数组。当数据大小已知并且不会经常更改时很有用。当您想要随机访问元素时，它也很好。
std::deque：双端队列可以充当堆栈或队列。适合当您不确定元素的数量以及始终以串行方式访问数据元素时。从前端和尾部添加/删除元素时速度很快，但从中间添加/删除元素时则不然。
std::list：双链表可用于创建数据“列表”。列表的优点是可以从列表的任何部分插入或删除元素，而不会影响指向列表成员（并且删除后仍然是列表成员）的迭代器。当您知道元素会经常从列表的任何部分删除时很有用。
std::map：映射一个字典“价值”的“关键”。对于索引不是整数的“数组”等应用程序很有用。基本上可用于创建名称到元素的映射列表，例如存储名称到小部件关系的映射。
std::set：“唯一的”列表' 数据值。例如，如果插入 1, 2, 2, 1, 3，则列表将仅包含元素 1, 2, 3。请注意，此列表中的元素始终是有序的。在内部，它们通常被实现为二叉搜索树（如地图）。
std::vector: A dynamic-array class. The internal memory allocation makes sure that it always creates an array. Useful when the size of the data is known and is known to not change too often. It is also good when you want to have random-access to elements.
std::deque: A double-ended queue that can act as a stack or queue. Good for when you are not sure about the number of elements and when accessing data-element are always in a serial manner. They are fast when elements are added/removed from front and end but not when they're added/removed to/from the middle.
std::list: A double-linked list that can be used to create a 'list' of data. The advantage of a list is that elements can be inserted or deleted from any part of the list without affecting an iterator that is pointing to a list member (and is still a member of the list after deletion). Useful when you know that elements will be deleted very often from any part of the list.
std::map: A dictionary that maps a 'key' to a 'value'. Useful for applications like 'arrays' whose index are not an integer. Basically can be used to create a map-list of name to an element, like a map that stores name-to-widget relationship.
std::set: A list of 'unique' data values. For e.g. if you insert 1, 2, 2, 1, 3, the list will only have the elements 1, 2, 3. Note that the elements in this list are always ordered. Internally, they're usually implemented as binary search trees (like map).
有关完整详细信息，请参阅此处：
标准的复杂性保证是什么容器？
向量与双端队列
双端队列与向量相同，但具有以下附加功能：
这意味着双端队列与向量相同，但提供以下附加保证：
set 与 map
Map 是“配对关联容器”，而 set 是“简单关联容器”，
这意味着它们完全相同。不同之处在于，map 保存项目对（键/值）而不仅仅是一个值。
See here for full details:
What are the complexity guarantees of the standard containers?
vector Vs deque
A deque is the same as a vector but with the following addition:
This means that deque is the same as a vector but provides the following additional gurantees:
set Vs map
A map is a "Pair Associative Container" while set is a "Simple Associative Container"
This means they are exactly the same. The difference is that map holds pairs of items (Key/Value) rather than just a value.
std::vector
您的默认顺序容器应该是 std::vector。一般来说，std::vector 将为您提供性能和速度的适当平衡。 std::vector 容器类似于 C 风格的数组，可以在运行时增长或收缩。底层缓冲区是连续存储的，并保证与 C 风格数组兼容。
如果满足以下条件，请考虑使用 std::vector：
您需要将数据连续存储在内存中
对于 C 风格 API 兼容性特别有用
您在编译时不知道大小
您需要有效地随机访问元素 (O(1))
您将从末尾添加和删除元素
您想要以任意顺序迭代元素
如果出现以下情况，请避免使用 std::vector：
您将经常在序列的前面或中间添加或删除元素
缓冲区的大小是恒定的并且提前已知（首选 std::array）
请注意 std::vector 的特殊化：从 C++98 开始，std::vector 已被特殊化，使得每个元素仅占用一位。当访问单个布尔元素时，运算符返回用该位的值构造的布尔值的副本。
std::array
std::array 容器最像内置数组，但提供额外的功能，例如边界检查和自动内存管理。与 std::vector 不同，std::array 的大小是固定的，在运行时不能更改。
如果满足以下条件，请考虑使用 std::array：
您需要将数据连续存储在内存中
对于 C 风格 API 兼容性特别有用
数组的大小是预先知道的
您需要有效地随机访问元素 (O(1))
您想要以任意顺序迭代元素
如果出现以下情况，请避免使用 std::array：
您需要插入或删除元素
您在编译时不知道数组的大小
您需要能够动态调整数组的大小
std::双端队列
std::deque 容器的名称源自“双端队列”的缩写。当将项目附加到队列的前面或后面时，std::deque 容器是最有效的。与 std::vector 不同，std::deque 不提供保留缓冲区的机制。也不保证底层缓冲区与 C 风格数组 API 兼容。
如果
您需要在序列的前面和后面插入新元素（例如在调度程序中）， 请考虑使用 std::deque
您需要有效地随机访问元素 (O(1))
您希望内部缓冲区在元素被删除时自动收缩
您想要以任意顺序迭代元素
如果出现以下情况，请避免使用 std::deque：
您需要保持与 C 风格 API 的兼容性
需要提前预留内存
您需要频繁地从序列中间插入或删除元素
在 std::deque 中间调用 insert 会使所有迭代器和对其元素的引用无效
std::list
std::list 和 std::forward_list 容器实现链表数据结构。其中 std::list 提供双向链表，而 std::forward_list 仅包含指向下一个对象的指针。与其他顺序容器不同，列表类型不提供对元素的有效随机访问。每个元素必须按顺序遍历。
请考虑使用 std::list
如果您需要存储许多项目但数量未知，
您需要从序列中的任意位置插入或删除新元素
您不需要有效访问随机元素
您希望能够在容器内或不同容器之间移动元素或元素集
您想要实现节点式内存分配方案
如果出现以下情况，请避免使用 std::list：
您需要保持与 C 风格 API 的兼容性
您需要有效地访问随机元素
您的系统使用缓存（首选 std::vector 以减少缓存未命中）
数据的大小是预先知道的，并且可以通过 std::vector 进行管理
std::vector
Your default sequential containers should be a std::vector. Generally, std::vector will provide you with the right balance of performance and speed. The std::vector container is similar to a C-style array that can grow or shrink during runtime. The underlying buffer is stored contiguously and is guaranteed to be compatible with C-style arrays.
Consider using a std::vector if:
You need your data to be stored contiguously in memory
Especially useful for C-style API compatibility
You do not know the size at compile time
You need efficient random access to your elements (O(1))
You will be adding and removing elements from the end
You want to iterate over the elements in any order
Avoid using a std::vector if:
You will frequently add or remove elements to the front or middle of the sequence
The size of your buffer is constant and known in advance (prefer std::array)
Be aware of the specialization of std::vector: Since C++98, std::vector has been specialized such that each element only occupies one bit. When accessing individual boolean elements, the operators return a copy of a bool that is constructed with the value of that bit.
std::array
The std::array container is the most like a built-in array, but offering extra features such as bounds checking and automatic memory management. Unlike std::vector, the size of std::array is fixed and cannot change during runtime.
Consider using a std::array if:
You need your data to be stored contiguously in memory
Especially useful for C-style API compatibility
The size of your array is known in advance
You need efficient random access to your elements (O(1))
You want to iterate over the elements in any order
Avoid using a std::array if:
You need to insert or remove elements
You don’t know the size of your array at compile time
You need to be able to resize your array dynamically
std::deque
The std::deque container gets its name from a shortening of “double ended queue”. The std::deque container is most efficient when appending items to the front or back of a queue. Unlike std::vector, std::deque does not provide a mechanism to reserve a buffer. The underlying buffer is also not guaranteed to be compatible with C-style array APIs.
Consider using std::deque if:
You need to insert new elements at both the front and back of a sequence (e.g. in a scheduler)
You need efficient random access to your elements (O(1))
You want the internal buffer to automatically shrink when elements are removed
You want to iterate over the elements in any order
Avoid using std::deque if:
You need to maintain compatibility with C-style APIs
You need to reserve memory ahead of time
You need to frequently insert or remove elements from the middle of the sequence
Calling insert in the middle of a std::deque invalidates all iterators and references to its elements
std::list
The std::list and std::forward_list containers implement linked list data structures. Where std::list provides a doubly-linked list, the std::forward_list only contains a pointer to the next object. Unlike the other sequential containers, the list types do not provide efficient random access to elements. Each element must be traversed in order.
Consider using std::list if:
You need to store many items but the number is unknown
You need to insert or remove new elements from any position in the sequence
You do not need efficient access to random elements
You want the ability to move elements or sets of elements within the container or between different containers
You want to implement a node-wise memory allocation scheme
Avoid using std::list if:
You need to maintain compatibility with C-style APIs
You need efficient access to random elements
Your system utilizes a cache (prefer std::vector for reduced cache misses)
The size of your data is known in advance and can be managed by a std::vector
映射通常称为关联数组，通常使用二叉树（例如）来实现。双端队列是双端队列，是链表的某种形式。
这并不是说容器库的实际实现使用了这些概念 - 容器库只会为您提供一些关于如何访问容器以及以什么（摊销）成本的保证。
我建议您看一下参考资料，其中详细介绍了这些保证的内容。如果我没记错的话，Scott Meyers 的书“Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library”应该稍微讨论一下这些内容。除此之外，C++ 标准显然是一个不错的选择。
我真正想说的是：容器实际上是由它们的属性来描述的，而不是由底层实现来描述的。
A map is what is often refered to as an associative array, usually implemented using a binary tree (for example). A deque is a double-ended queue, a certain incarnation of a linked list.
That is not to say that the actual implementations of the container library uses these concepts - the containr library will just give you some guarantees about how you can access the container and at what (amortized) cost.
I suggest you take a look at a reference that will go into detail about what those guarantees are. Scott Meyers book "Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library" should talk a bit about those, if I remember correctly. Apart from that, the C++ standard is obviously a good choice.
What I really want to say is: containers really are described by their properties, not by the underlying implementation.
set：保存唯一值。将“a”放入两次，则集合中有一个“a”。
map：将键映射到值，例如 'name' => '弗雷德', '年龄' => 40. 你可以查找“name”，然后你会找到“fred”。
出队，就像向量一样，但只能在末尾添加/删除。中间没有插入物。 http://en.wikipedia.org/wiki/Deque
编辑：缺少我的出队描述，请参阅下面的评论进行更正
set: holds unique values. Put 'a' in twice, the set has one 'a'.
map: maps keys to values, e.g. 'name' => 'fred', 'age' => 40. You can look up 'name' and you'll get 'fred' out.
dequeue, like a vector but you can only add/remove at the ends. No inserts into the middle. http://en.wikipedia.org/wiki/Deque
edit: my dequeue description is lacking, see comments below for corrections