什么是容器/适配器？C++

What are Containers/Adapters? C++

提问by Pavitar

What are containers/adapters?

什么是容器/适配器？

Someone please explain in layman's language.

有人请用通俗的语言解释一下。

I have tried to look up on the internet but the definitions and explanations are too technical and hard to understand.

我试图在互联网上查找，但定义和解释太技术性且难以理解。

I have basic knowledge of C++ and its sub-topics like (class/templates/STL).

我对 C++ 及其子主题（如（类/模板/STL）有基本的了解。

EDIT 1:

编辑 1：

Can anyone please give me a practical example of the application of containers/adapters?

谁能给我一个容器/适配器应用的实际例子？

Just for better understanding :-)

只是为了更好地理解:-)

Thank you.

谢谢你。

回答by Platinum Azure

A container is a specific data structure that contains data, usually in an unbounded amount. Each container type has limitations on how to access, add, or remove data efficiently.

容器是包含数据的特定数据结构，通常是无限数量的。每种容器类型在如何有效访问、添加或删除数据方面都有限制。

Below are a few examples of containers using STL classes.

下面是一些使用 STL 类的容器示例。

Sequence Containers

序列容器

Here are the sequence containers, meaning the data is reliably ordered (that is, there is a front and a back to them. I do NOT mean that they automatically sort themselves!).

这是序列容器，这意味着数据是可靠排序的（也就是说，它们有正面和背面。我不是说它们会自动排序！）。

• A vectoris a bit like a flexibly-sized array. Vectors are random-access, meaning you can access any element with integer index in constant time (just like an array). You can add or remove from the back of the vector in amortized constant time as well. Anywhere else, though, and you're probably looking at having to recopy potentially all of the elements.
• A deque, or double-ended queue, is like a vector but you can add to the front or the back in amortized constant time. You can still access elements in constant time, but deque elements are not guaranteed to be contiguous in memory like vectors or arrays.
• A listis a linked list, meaning data which are linked together by pointers. You have constant-time access to the beginning and the end, but in order to get anywhere in the middle you need to iterate through the list. You can add elements anywhere in the list in constant time, though, if you already have a pointer to one of the nearby nodes.

• 甲矢量是有点像灵活大小的数组。向量是随机访问的，这意味着您可以在恒定时间内访问任何具有整数索引的元素（就像数组一样）。您也可以在摊销的恒定时间内从向量的后面添加或删除。但是，在其他任何地方，您可能正在考虑必须重新复制所有元素。
• 一个双端队列，或双端队列，就像是一个载体，但可以添加到前面或在固定的时间里回来。您仍然可以在恒定时间内访问元素，但不能保证双端队列元素像向量或数组一样在内存中是连续的。
• 甲列表是一个链表，这意味着其通过指针链接在一起的数据。您可以恒定时间访问开头和结尾，但为了到达中间的任何位置，您需要遍历列表。但是，如果您已经拥有指向附近节点之一的指针，则可以在恒定时间内在列表中的任何位置添加元素。

Associative Containers

关联容器

These are associative containers, meaning that elements are no longer ordered but instead have associations with each other used for determining uniqueness or mappings:

这些是关联容器，这意味着元素不再是有序的，而是相互关联，用于确定唯一性或映射：

• A setis a container with unique elements. You can only add one of each element to a set; any other additions are ignored.
• A multisetis like a set, but you can put more than one of an element in. The multiset keeps track of how many of each kind of element are in the structure.
• A map, also known as an associative array, is a structure in which you insert key-value pairs; then you can look up any value by supplying the key. So it's a bit like an array that you can access with a string index (key), or any other kind of index. (If you insert another key-value pair and the key already exists, then you just overwrite the value for the original key.)
• A multimapis a map that allows for insertion of multiple values for the same key. When you do a key lookup, you get back a container with all the values in it.

• 甲集是具有独特的元件的容器。您只能将每个元素中的一个添加到集合中；任何其他添加都将被忽略。
• 一个多集就像是一组，但你可以把以上的元素之一，多集跟踪多少的各种元素都在的结构。
• 甲地图，也称为关联数组，是在其中插入键-值对的结构; 然后您可以通过提供密钥来查找任何值。所以它有点像一个数组，您可以使用字符串索引（键）或任何其他类型的索引来访问它。（如果您插入另一个键值对并且键已经存在，那么您只需覆盖原始键的值。）
• 多映射是一种允许为同一个键插入多个值的映射。当您进行键查找时，您会返回一个包含所有值的容器。

Container Adapters

容器适配器

Container adapters, on the other hand, are interfaces created by limiting functionality in a pre-existing container and providing a different set of functionality. When you declare the container adapters, you have an option of specifying which sequence containers form the underlying container. These are:

另一方面，容器适配器是通过限制预先存在的容器中的功能并提供一组不同的功能而创建的接口。当您声明容器适配器时，您可以选择指定哪些序列容器构成底层容器。这些是：

• A stackis a container providing Last-In, First-Out (LIFO) access. Basically, you remove elements in the reverse order you insert them. It's difficult to get to any elements in the middle. Usually this goes on top of a deque.
• A queueis a container providing First-In, First-Out (FIFO) access. You remove elements in the same order you insert them. It's difficult to get to any elements in the middle. Usually this goes on top of a deque.
• A priority_queueis a container providing sorted-order access to elements. You can insert elements in any order, and then retrieve the "lowest" of these values at any time. Priority queues in C++ STL use a heap structure internally, which in turn is basically array-backed; thus, usually this goes on top of a vector.

• 甲堆栈是提供后进先出（LIFO）访问的容器。基本上，您以与插入元素相反的顺序删除元素。很难到达中间的任何元素。通常这是在deque之上。
• 甲队列是提供先入，先出（FIFO）的访问的容器。您可以按照插入元素的相同顺序删除元素。很难到达中间的任何元素。通常这是在deque之上。
• 甲priority_queue是提供对元素排序顺序访问的容器。您可以按任何顺序插入元素，然后随时检索这些值中的“最低”值。C++ STL 中的优先级队列在内部使用堆结构，而堆结构基本上是数组支持的；因此，通常这在vector之上。

See this reference pagefor more information, including time complexity for each of the operations and links to detailed pages for each of the container types.

有关更多信息，请参阅此参考页面，包括每个操作的时间复杂度以及每个容器类型的详细页面链接。

回答by ?imon Tóth

<joke>C++ is technical and hard to understand :-D</joke>

<joke>C++ 是技术性的，很难理解 :-D</joke>

Containers are data types from STL that can contain data.

容器是来自 STL 的可以包含数据的数据类型。

Example: vectoras a dynamic array

示例：vector作为动态数组

Adapters are data types from STL that adapt a container to provide specific interface.

适配器是来自 STL 的数据类型，用于适应容器以提供特定接口。

Example: stackproviding stack interface on top of the chosen container

示例：stack在所选容器的顶部提供堆栈接口

(side note: both are actually templates not data types, but the definition looks better this way)

（旁注：两者实际上都是模板而不是数据类型，但这样定义看起来更好）

回答by James McNellis

The technical definition of "container" from The SGI STL documentationis pretty good:

SGI STL 文档中“容器”的技术定义非常好：

A Container is an object that stores other objects (its elements), and that has methods for accessing its elements. In particular, every type that is a model of Container has an associated iterator type that can be used to iterate through the Container's elements.

Container 是一个存储其他对象（其元素）的对象，并且具有访问其元素的方法。特别是，作为 Container 模型的每个类型都有一个关联的迭代器类型，可用于迭代 Container 的元素。

So, a container is a data structure that holds ("contains") a collection of objects of some type. The key idea is that there are different types of containers, each of which stores objects in a different way and provides different performance characteristics, but all of them have a standard interface so that you can swap one out for another easily and without modifying too much of the code that uses the container. The idea is that the containers are designed to be interchangeable as much as possible.

因此，容器是一种数据结构，它保存（“包含”）某种类型的对象集合。关键思想是有不同类型的容器，每个容器以不同的方式存储对象并提供不同的性能特征，但它们都有一个标准的接口，以便您可以轻松地将一个换出另一个，而无需进行太多修改使用容器的代码。这个想法是容器被设计为尽可能可互换。

The container adapters are classes that provide a subset of a container's functionality but may provide additional functionality that makes it easier to use containers for certain scenarios. For example, you could easily use std::vectoror std::dequefor a stack data structure and call push_back, back, and pop_backas the stack interface; std::stackprovides an interface that can use a std::vectoror std::dequeor other sequence container but provides the more standard push, top, and popmember functions for accessing members.

容器适配器是提供容器功能子集的类，但可能会提供附加功能，以便在某些情况下更容易使用容器。例如，可以很容易地使用std::vector或std::deque用于堆的数据结构和呼叫push_back，back以及pop_back作为堆栈接口; std::stack提供了可以使用的接口std::vector或std::deque或其他序列容器，但提供更标准的push，top和pop成员函数用于访问成员。