STL标准模板库

一.STL的六大组件

STL（Standard Template Library，标准模板库）是为了建立数据结构和算法的一套标准，并且降低它们之间的耦合关系，以提升各自的独立性、弹性、交互操作性。STL包含容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器六大组件。

STL的优点：

1. 被内建在编译器内部，无需额外安装。
2. 将数据和操作分离。数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当连接的桥梁，以使算法可以和容器交互运作。
3. 高可重用性，高性能，高移植性，跨平台的优点

---

1.1 容器

容器（Containers）存放的是各种数据结构，如vector、list、deque等；而从实现角度讲，STL容器就是一种 class template。

根据数据在容器中的排列特性，容器可分为序列式容器和关联式容器：

• 序列式容器：强调值的排序，序列式容器中的每个元素均有固定位置，除非用插入或删除操作改变这个位置。
• 关联式容器：是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器的显著特点：它是以键值的方式来保存数据。

此外还有容器适配器：适配器是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制。

---

1.2 算法

算法（Algorithms）是什么，算法就是步骤。算法就是解决特定逻辑问题及数学问题的有限步骤的合集。

算法具有五大基本特性：输入输出、有穷性、确定性、可行性。

STL 收录的算法是经过了无数程序人在实践中证明极具复用价值的合集。算法大致可以分为：

• 质变算法：运算中会更改区间内元素的内容。如拷贝，替换，删除等。
• 非质变算法：运算中不会更改区间内的元素内容。如查找、计数、遍历等。

---

1.3 迭代器

迭代器（Iterators）是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。

《Design Patterns》中 iterator 模式定义如下：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

迭代器的分类：

迭代器	功能	描述
输入迭代器	提供数据的只读访问	只读
输出迭代器	提供数据的只写访问	只写
前向迭代器	提供数据的读写操作并能向前推进推进操作	读写
双向迭代器	提供数据的读写操作并能向前和向后推进操作	读写
随机访问迭代器	提供数据的读写操作并能随机跳跃访问容器任意位置数据	读写

---

1.4 仿函数

仿函数（Functors）是行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了 operator() 的 class 或者class template

---

1.5 适配器（配接器）

适配器（Adapters）是使一事物的行为类似于另一事物的行为的一种机制。容器适配器是让一种已存在的容器类型采用另一种不同的抽象类型的工作方式来实现的一种机制。它实质还是一个容器，只是它不依赖于具体的标准容器类型，可以理解为容器的模版；或者理解为容器的接口，适配器具体采用哪种容器类型去实现，在定义适配器的时候决定。

---

1.6 配置器

配置器（Allocators）是负责空间的配置与管理。从实现角度看配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte。

STL六大组件关系交错：

容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，而适配器可以修饰仿函数。

---

二.STL常用容器类

STL常用容器类包括如下：

string、vector、deque、list、forward_list、stack、queue、priority_queue、map、multimap、set、multiset、unordered_map 、unordered_multimap、unordered_set、unordered_multiset。

标准容器类的分类及其特点：

1. 顺序式容器

名称	特点
array	大小是固定的，无法动态的扩展或收缩
vector	从后面快速插入与删除元素，可直接访问任何元素
deque	从前面或者后面插入与删除元素，可直接访问任何元素
list	双向链表，可从任意地方快速插入与删除
forward_list	单链表，可从任意地方快速插入与删除

2. 容器适配器

名称	特点
stack	后进先出（LIFO）
queue	先进先出（FIFO）
priority_queue	最高优先级总是第一个出列

3. 关联式容器

名称	特点
map	一对多映射，基于关键字快速查找，不允许重复值
multimap	一对多映射，基于关键字快速查找，允许重复值
set	快速查找，不允许重复值
multiset	快速查找，允许重复值

4. 无序关联式容器

名称	特点
unordered_map	无序
unordered_multimap	无序
unordered_set	无序
unordered_multiset	无序

---

2.1 string 类

string 是 C++ 标准库中一个重要的容器，实际上它是一个类，而不是一个容器模板。

C语言字符串（以空字符结尾的字符数组）太过复杂难于掌握，不适合大程序的开发，所以C++标准库定义了一种 string 类，定义在 头文件当中。string 类是 STL 中 对 basic_string 模板实例化得到的模板类。其定义如下：

typedef basic_string string;

---

2.2 array 容器

是 C++ 11 标准中新增的顺序容器，它就是在 C++ 普通数组的基础上，添加了成员函数和全局函数。

它使用比普通数组更安全，且效率相当。array 容器的大小是固定的，无法动态的扩展或收缩，因此它只允许访问或者替换存储的数据元素。

---

2.3 vector 容器

vector 称为向量容器，是一种线性顺序结构。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将 vector 看作动态数组。

在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小由 capacity() 函数的返回值确定。当存储的数据超过分配的空间时 vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：

1. 首先，vector 申请一块更大的内存块；

2. 其次，将原来的数据拷贝到新的内存块中；

3. 然后，销毁掉原内存块中的对象（调用对象的析构函数）；

4. 最后，将原来的内存空间释放掉。

注：vector 容器更擅长在尾部插入或删除元素而不擅长在容器头部或者中部插入或删除元素。

#include <vector> // 头文件引用
vector<int> vec;  // 创建
vec.push_back(x); // 添加 o(1)
vec.pop_back();   // 删除 o(1)
vec[i]            // 访问 o(1)

---

2.4 deque 容器

deque 是 double-ended queue 的缩写，又称双端队列。

deque 容器和 vector 容器的相同点：

1. deque 容器也擅长在序列尾部添加或删除元素，而不擅长在序列中间添加或删除元素；

2. deque 容器也可根据需要修改自身的容量和大小。

#include <deque> //引用头文件
deque<int> deq;  // 创建
// 添加 o(1)
deq.push_front();
deq.push_back();
// 删除 o(1)
deq.pop_front();
deq.pop_back();
// 访问 o(1)
deq.front();
deq.back();

---

2.5 list 容器

list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。

---

2.6 forward_list 容器

forward_list 容器是 C++ 11 新加入的容器，其底层实现和 list 容器一样，采用的也是链表结构，但是 forward_list 使用的是单链表，而 list 使用的是双向链表。

---

2.7 stack 容器

stack 是限定仅在表尾进行插入删除操作的线性表，又称为后进先出（LIFO）的线性表。它不允许遍历，任何时候外界只能访问 stack 顶部的元素，只有在移除 stack 顶部的元素后，才能访问下方的元素。默认情况下，stack 使用 deque 作为底层容器。stack 容器应用广泛，如编辑器中的 undo （撤销操作）机制。

#include <stack> //引用头文件
stack<int> stk;  // 创建
stk.push(x);     // 添加 o(1)
stk.pop();       // 删除 o(1)
stk.top();       // 访问 o(1)

---

2.8 queue 容器

queue 是限定表的一端进行插入操作，表的另一端进行删除操作的线性表，队列又称为先进先出（FIFO）的线性表。

#include <queue> //引用头文件
queue<int> que;  // 创建
que.push();      // 添加 o(1)
que.pop();       // 删除 o(1)
que.front();     // 访问 o(1)

---

2.9 priority_queue 容器

priority_queue 的本质是大顶堆。priority_queue 在内部维护一个基于二叉树的大顶堆数据结构，在这个数据结构中，最大的元素始终位于堆顶部，只有堆顶部的数据元素（max heap element）才能被访问获取。当然，也可以通过自定义模板参数中的 class Compare 实现一个小顶堆。相比于 queue（普通队列）的先进先出（FIFO），priority_queue 实现最高优先级先出。

#include <queue>       //引用头文件
priority_queue<int> q; // 创建
q.push(x);             // 添加 o(logn)
q.pop();               // 删除 o(logn)
q.top();               // 访问 o(1)

---

2.10 map 容器

map 通过底层的红黑树数据结构将所有的数据元素按照 key 的相对大小进行排序，所实现的排序效果也是严格弱序特性。map 支持在一个子集合上进行直接迭代器访问，因为 map 中的元素是被有序组织的。

#include <map>      //引用头文件
map<string, int> m; // 创建
m[str] = x;         // 添加 o(logn)
m.erase(it);        // 删除 o(logn)
// 访问 o(logn)
m.count(str);
m[str];

---

2.11 multimap 容器

multimap 是关联式容器，是使用红黑树对记录型的元素数据,按元素键值的比较关系，进行快速的插入、删除和检索操作，所不同的是 multimap 允许将具有重复键值的元素插入容器。

multimap 按照特定顺序来存储键值对 <key、value> ，其中多个键值对之间的 key 可以重复；键 key 通常用于排序及唯一标识元素，值 value 则存储与键 key 关联的内容。

---

2.12 set 容器

set 就是集合，是利用二叉树实现，集合中的每个元素只出现一次(参照数学中集合的互斥性)，并且是排好序的（默认按键值升序排列）。

#include <set> //引用头文件
set<int> s;    // 创建
s.insert(x);   // 添加 o(logn)
s.erase(it);   // 删除 o(logn)
s.count(x);    // 访问 o(k+logn)

---

2.13 multiset 容器

1. multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的；
2. 元素的 value 会识别它组成的键值对，multiset 元素的值不能在容器中进行修改，但可以插入和删除；
3. multiset 在内部按照特定的严格弱排序准则进行排序；
4. multiset 容器通过 key 访问单个元素比 unordered_multiset 容器慢，但当使用迭代器遍历的时候，会得到一个有序序列；
5. multiset 的底层是二叉搜索树（红黑树）。

---

2.14 unordered_map 容器

1. unordered_map 是一个将 key 和 value 关联起来的容器，可以根据单个 key 键高效查找对应 value 值；
2. key 键是唯一的，key 键和 value 值的数据类型可以不同；
3. unordered_map 存储是无序的，是根据 key 键的哈希值将元素存储在指定位置，并且根据 key 键查找单个value 值时非常高效；
4. unordered_map 查询单个 key 键效率比 map 高，但是查询某一范围内的 key 键时比 map 效率低；
5. 可以使用 [ ] 操作符来访问 key 键对应的 value 值。

注：如果需要内部元素自动排序，使用map，不需要排序使用unordered_map。

#include <unordered_map>      //引用头文件
unordered_map<string, int> m; // 创建
m[str] = x;                   // 添加 o(1) / o(n)
m.erase(it);                  // 删除 o(1) / o(n)
// 访问 o(1) / o(n)
m.count(str);
m[str];

---

2.15 unordered_multimap 容器

unordered_multimap 是一个封装哈希表的无序容器。容器中每个元素都是键值对 <key、value> ，每个 key 键可重复出现。

---

2.16 unordered_set 容器

unordered_set 是一种不按特定顺序存储唯一元素的容器，允许根据元素的值快速检索单个元素。unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而unordered_set 容器不会。

几大特性：

1. 不以键值对 <key、value>的形式存储数据，而是直接存储数据的值；
2. 容器内部存储的各个元素的值都互不相等，且不能被修改；
3. 不对内部存储的数据进行排序。

#include <unordered_set> //引用头文件
unordered_set<int> s;    // 创建
s.insert(x);             // 添加 o(1) / o(n)
s.erase(it);             // 删除 o(1) / o(n)
s.count(x);              // 访问 o(1) / o(n)

---

2.17 unordered_multiset 容器

unordered_multiset 容器可同时存储多个相同值的元素，且这些元素会存储到哈希表中（本质就是链表）。

它有如下特性：

• 不以键值对 <key、value>的形式存储数据，而是直接存储数据的值；
• 该类型容器底层采用的也是哈希表存储结构，它不会对内部存储的数据进行排序；
• 容器内部存储的元素值不能被修改。

---

三.C++的一些函数使用

3.1 algorithm头文件

algorithm 头文件是C++的标准算法库，它主要应用在容器上。此头文件常用的函数有：

1. max()、min()、abs() 函数
2. swap() 函数
3. reverse() 函数
4. sort() 函数
5. find() 函数
6. upper_bound()、lower_bound() 函数
7. fill() 函数
8. count() 函数
9. _gcd() 函数求最大公约数
10. set_intersection()、set_union()、set_difference() 函数

---

3.2 转换和判定函数

stoi(const string *str);	//
atoi(const char *ch);		//	
atol(const char *str);		//

islower(char c);	//是否为小写字母
isuppper(char c);	//为大写字母
isdigit(char c);	//是否为数字
isalpha(char c);	//是否为字母
isalnum(char c); 	//是否为字母或者数字
toupper(char c); 	//字母小转大
tolower(char c); 	//字母大转小

---

3.3 pair & tuple 容器

std::pair 和 std::tuple 不是STL容器库中的容器，由于经常用到，顺便整理。pair 相当于 tuple 的特例。

• pair 是将2个数据组合成一个数据，当需要这样的需求时就可以使用pair，如STL中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择 pair。pair 的实现是一种结构体，主要的两个成员变量是 first , second。
• tuple是C++11新标准里的类型。它是一个类似 pair 类型的模板。pair 类型是每个成员变量各自可以是任意类型，但是只能有俩个成员，而 tuple 与 pair 不同的是它可以有任意数量的成员。但是每个确定的 tuple 类型的成员数目是固定的。

---