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

Question

什么是容器/适配器？我对 C++ 及其子主题(类/模板/STL)有基本的了解。

谁能用外行的语言解释一下，给我一个容器/适配器应用的实际例子吗？

Answer 1

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

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

序列容器

这里是序列容器，这意味着数据是可靠排序的(也就是说，它们有一个正面和一个背面。我并不是说它们会自动排序!)。

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

关联容器

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

• set 是具有独特元素的容器。您只能将每个元素中的一个添加到集合中；任何其他添加都将被忽略。
• multiset 类似于集合，但您可以将多个元素放入其中。multiset 跟踪结构中每种元素的数量。
• map，也称为关联数组，是一种在其中插入键值对的结构；然后您可以通过提供 key 来查找任何值。所以它有点像一个数组，您可以使用字符串索引(键)或任何其他类型的索引来访问它。 (如果您插入另一个键值对并且该键已经存在，那么您只需覆盖原始键的值。)
• multimap 是允许为同一个键插入多个值的映射。当您进行键查找时，您会返回一个包含所有值的容器。

容器适配器

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

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

见 this reference page了解更多信息，包括每个操作的时间复杂度以及每个容器类型的详细页面的链接。