当前位置：文江博客话题详情

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

发布于 2024-09-26 04:46:21 字数 91 浏览 5 评论 0原文

什么是容器/适配器？我有 C++ 及其子主题（例如（类/模板/STL））的基本知识。

谁能用通俗易懂的语言解释一下，并给我一个容器/适配器应用的实际例子？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

枯寂 2024-10-03 04:46:21

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

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

序列容器

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

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

关联容器

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

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

容器适配器

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

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

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

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.

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 vector is 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 list is 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 set is a container with unique elements. You can only add one of each element to a set; any other additions are ignored.
A multiset is 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 multimap is 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 stack is 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 queue is 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_queue is 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.

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

回复收藏 0 原文

秋凉 2024-10-03 04:46:21

C++ 是技术性的，很难理解:-D

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

示例：vector 作为动态数组

适配器是 STL 中的数据类型，可调整容器以提供特定接口。

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

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

回复收藏 0 原文

痴者 2024-10-03 04:46:21

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

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

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

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