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

Question

什么是容器/适配器？我有C++语言的基本知识，如（类/模板/STL）。

请问有人能用通俗易懂的语言解释并给出一个容器/适配器应用的实际示例吗？

- Pavitar

---

我很难理解你所说的“实际例子”，更难想象在什么情况下不使用容器（无论是STL中的容器，还是来自Boost或自己实现的容器）。几乎任何时候，当你有一组对象时，你都会使用容器... - James McNellis

@James McNellis - 我所说的实际例子是指任何应用它的环境的示例。但无论如何，是的，我明白了你的意思。也许我表达问题不太准确。谢谢。 - Pavitar

Answer 1

一个容器是一种特定的数据结构，通常包含大量数据。每种容器类型都有其访问、添加或删除数据的限制。

以下是使用STL类的几个容器示例。

序列容器

这里是序列容器，意味着数据可靠地排序（即它们具有前面和后面。我不是指它们会自动排序！）。

• vector有点像一个大小可变的数组。向量是随机访问的，意味着您可以通过整数索引在常数时间内访问任何元素（就像数组一样）。您还可以在平摊常数时间内从向量的后面添加或删除。但是，在其他任何地方，您可能需要重新复制潜在的所有元素。
• deque 或双端队列，类似于向量，但您可以在平均常数时间内从前面或后面添加。您仍然可以在常数时间内访问元素，但deque元素不能像vector或数组那样保证在内存中连续。
• list 是一个链表，即通过指针链接在一起的数据。您可以在常数时间内访问开头和结尾，但是为了到达中间的任何位置，您需要遍历列表。但如果您已经有一个指向附近节点之一的指针，则可以在列表中的任何位置以常数时间添加元素。

关联容器

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

• set是带有唯一元素的容器。您只能将每个元素添加到集合中一次；任何其他添加都会被忽略。
• multiset类似于set，但是您可以放置一个元素以上。 multiset跟踪结构中每种元素的数量。

一个映射，也称为关联数组，是一种结构，其中您插入键值对;然后可以通过提供键来查找任何值。因此，它类似于可以使用字符串索引（键）或任何其他类型的索引访问的数组。 （如果插入另一个键值对且该键已经存在，则只需覆盖原始键的值。）

multimap是一种允许为相同键插入多个值的映射。当您执行键查找时，将返回一个包含其中所有值的容器。

容器适配器

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

• 堆栈是提供后进先出（LIFO）访问的容器。基本上，您以与插入它们相反的顺序删除元素。很难访问中间的任何元素。通常这放在一个双端队列之上。
• 队列是提供先进先出（FIFO）访问的容器。您以插入它们的相同顺序删除元素。很难访问中间的任何元素。通常这放在一个双端队列之上。
• 优先队列是提供对元素的排序访问的容器。您可以以任何顺序插入元素，然后随时检索其中的“最低”值。 C ++ STL中的优先队列内部使用堆结构，堆结构本质上是支持数组; 因此，通常这放在一个向量之上。

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

- Platinum Azure

---

一个（LIFO）栈放在向量上面不是更有意义吗？因为它只在一端增长和缩小，而不是在双端增长和缩小的双端队列。 - veganaiZe

@veganaiZe 你说得没错，这样可能更有意义。我的假设是，大多数双端队列的实现可能比向量更快地增加大小。不过我也不确定。 - Platinum Azure

你也没错！在文档中，你提到的deque是很常见的。虽然它甚至可以被实现为单向链表。但是，动态数组似乎是最有效的选择，同时仍然以连续序列提供元素。 - veganaiZe

当您声明容器适配器时，您可以选择指定哪些序列容器形成底层容器。 - Cătălina Sîrbu

Answer 2

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

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

例如：vector 是动态数组

适配器是来自 STL 的数据类型，它们可以使容器提供特定的接口。

例如：在所选择的容器上提供堆栈接口的 stack

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

- Šimon Tóth

Answer 3

"容器"的技术定义来自The SGI STL documentation，非常好:

容器是存储其他对象(其元素)的对象，并具有访问其元素的方法。特别地，每个作为容器模型的类型都有一个关联的迭代器类型，可用于遍历容器的元素。

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

容器适配器是提供容器子集功能的类，但可能提供附加功能，使得更容易将容器用于某些场景。例如，您可以轻松地使用std::vector或std::deque作为堆栈数据结构，并调用push_back，back和pop_back作为堆栈接口；std::stack提供了一个接口，可以使用std::vector或std::deque或其他序列容器，但提供更标准的push，top和pop成员函数来访问成员。

- James McNellis