STL容器分类「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

容器（container）是装有其他对象的对象。容器里面的对象必须是同一类型，该类型必须是可拷贝构造和可赋值的，包括内置的基本数据类型和带有公用拷贝构造函数和赋值操作符的类。典型的容器有队列、链表和向量等。

在标准C++中，容器一般用模版类来表示。不过STL不是面向对象的技术，不强调类的层次结构，而是以效率和实用作为追求的目标。所以在STL并没有一个通用的容器类，各种具体的容器也没有统一的基类。

容器可以视为是数组的推广，即对象的数组（广义数组），其中的元素（对象）可以用下标（索引）来访问。

容器的设计有两条准则：一是在各个容器的设计中，提供尽可能大的自由度；二是使各种容器能够向用户呈现出一个公共的界面/接口。目的是，使容器的实现能达到最佳效率，同时也使用户能写出不依赖于所使用的特定容器类型的通用代码。容器的设计通常只能满足这两条中的一条，但是STL却提供了一个同时具有通用性和执行效率的解决方案。

标准C++的STL框架中的容器主要有两大类：

l         序列容器（sequence container顺序容器）—— 将一组具有相同类型T的对象，以严格的线性形式组织在一起。序列容器可以视为数组和链表的推广。STL中的序列容器有3种：

n         vector<T>（向量）——提供对变长序列的快速随机访问 （即对第i个元素的访问时间，是与i无关的常量），对序列末尾的插入和删除操作的时间是分摊常量；（似变长数组）（对应于vector类，定义在<vector>头文件中）；

n         deque<T>（double-ended queue双端队列）—— 提供对变长序列的快速随机访问，对序列头尾的插入和删除操作的时间都是分摊常量；（似双向变长数组）（对应于deque类，定义在<deque>头文件中）；

n         list<T>（表）—— 提供对变长序列的线性时间访问（O(N)，N为序列的当前长度），但是在序列的任意位置的插入和删除操作均为常量时间。（似双向链表）（对应于list类，定义在<list>头文件中）。

l         关联容器（associative container联合容器）—— 关联容器的特点是（键）有序的，即元素是按预定义的键顺序（如升序）插入的。关联容器具有从基于键的集合中快速提取对象的能力，其中集合的大小在运行时是可变的。关联容器可以视为关联数组、映射或字典的推广，它们保存的都是值的对偶，给定了其中的一个被称为键（key）的值，就可以快速访问与其对偶的另一个被称为映射值（mapped value）的值。STL中的关联容器有4种：

n         set<Key>（集合）—— 支持唯一键值，并提供对键本身的快速检索；例如set<long>：{学号}（对应于set类，定义在<set>头文件中）；

n         multiset<Key>（多重集合）—— 支持可重复键值，并提供对键本身的快速检索；例如set<string>：{姓名}（可能有同名的）（对应于multiset类，也定义在<set>头文件中）；

n         map<Key, T>（映射/映像）—— 支持唯一Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map<long, string>：{(学号, 姓名)}、{(电话号码, 姓名)}等（对应于map类，定义在<map>头文件中）；

n         multimap<Key, T>（多重映射）—— 支持可重复Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map<string, string>：{(姓名, 地址)}、{(姓名, 年龄)}等（对应于multimap类，也定义在<map>头文件中）。

为了改进搜索的时间，有些编译器(包括VC2005)增加了4种对应的散列（hash）关联容器类型：

n         hash_set<Key, H>（散列集）（对应于hash_set类，定义在<hash_set>头文件中）

n         hash_multiset<Key, H>（散列多集）（对应于hash_multiset类，也定义在<hash_set>头文件中）

n         hash_map<Key, T, H>（散列映射）（对应于hash_map类，定义在<hash_map>头文件中）

n         hash_multimap<Key, T, H>（散列多映射）（对应于hash_multimap类，也定义在<hash_map>头文件中）

除了这两大类容器外，STL还有另外两大类容器：

l         容器适配器（container adapter）—— 不是独立的容器，只是某种容器的变种，它提供原容器的一个专用的受限接口。特别是，容器适配器不提供迭代器。在STL中有3种容器适配器：

n         stack<T>（栈）—— 只支持top()（读取栈顶元素）、push()（在栈顶处加入新元素）和pop()（取出栈顶元素）操作（先入后出）的一种序列容器。可以是对任意一种序列容器（缺省为双端队列deque）的限制实现：删除非栈操作，将原来序列容器的标准操作back()、push_back()和pop_back()重新命名为top()、push()和pop()。（对应于stack类，定义在<stack>头文件中）；

n         queue<T>（队列）—— 与stack类似，queue也是对序列容器（缺省也为双端队列deque）的限制实现。与栈相比，队列也支持back()（读取队尾处的元素）和push_back()（在队尾处插入新元素）操作，但是不再支持pop_back()（取出队尾处的元素）操作。不过，队列却允许front()（读取队首处的元素）和pop_front()（取出队首处的元素）操作（前出后入）。由于矢量vector容器不支持pop_front()操作，所以不能作为队列queue的基础容器。与前后都可出入的双端队列deque相比，队列queue缺少push_front()和pop_back()操作。（对应于queue类，定义在<queue>头文件中）；

n         priority_queue<T>（优先队列）—— 也是一种队列queue，不过其中的每个元素都被给定了一个优先级，用来控制元素到达队首top()的顺序。默认情况下，优先队列简单地使用运算符<进行元素比较，top()返回最大的元素。注意，优先队列，并不要求其全部元素都是有序的，而只要求其第一个元素是最大的。（对应于priority_queue类，也定义在<queue>头文件中）。

l         似容器（almost container拟容器）—— 在许多情况下可视为容器，但是又缺乏标准容器界面的某些方面和特性，不能与开发完全的容器进行全面互换。除了内置数组外，STL中的似容器有3种：

n         string（串）—— 是实例化模版类basic_string<char>的类型定义typedef（另一个常用的wstring类，则是实例化模版类basic_string<wchar_t>的类型定义typedef）。基本串basic_string提供下标操作、随机访问迭代器和其他序列容器的几乎所有功能，但是它不像容器那样支持广泛的元素类型选择，而且它还为作为字符串使用而进行了优化，所以其典型使用方式与容器有着显著差异。（对应于string类，定义在<string>头文件中）。有关string的更详细内容，会在本节后面的4.3）中介绍；

n         valarray<T>（值数组）—— 是为数值计算而进行了优化的向量，并不是一个具有通用性的容器。valarray提供了许多有用的数值运算和常用的数学函数，但是它只提供了标准容器操作中的size()和下标操作，此外，其中元素的指针是一种随机迭代器。（对应于valarray类，定义在<valarray>头文件中）；

n         bitset<N>（位集）—— 是标志位字段的扩展，它通过提供在N个二进制位的集合（下标0~N-1）上的各种操作，使对标志位的运算更为方便。bitset可视为一个N位的二进制数，位取值0/1代表真假或开关，每一位从低位向高位进行编号。（对应于bitset类，定义在<bitset>头文件中）。