STL模板库

# STL 模板库 ## 1. 顺序容器 ### 1.1 VECTOR #### 1.1.1 定义 `vector` 本意为向量，是一种基本的动态数组顺序存储容器，是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。 `vector` 是同一种类型的对象的集合,每个对象都有一个对应的整数索引值。 和 `string` 对象一样,标准库将负责管理与存储元素相关的内存。我们把 `vector` 称为容器,是因为它可以包含其他对象，能够存放任意类型的动态数组，增加和压缩数据。一个容器中的所有对象都必须是同一种类型的。 `vector` 是一个类模板(class template)。使用模板可以编写一个类定义或函数定义,而用于多个不同的数据类型。因此,我们可以定义保存 `string` 对象的 `vector`,或保存 `int` 值的 `vector`,又或是保存自定义的类类型对象的 `vector`。 `vector` 不是一种数据类型,而只是一个类模板,可用来定义任意多种数据类型。`vector` 类型的每一种都指定了其保存元素的类型。 #### 1.1.2 声明 为了可以使用 `vector`，必须在你的头文件中包含下面的代码： ```cpp #include<vector> using namespace std; ``` 声明 `vector` 时的格式如下： ```cpp //vector < Type > Name; vector <int> v; vector <int> v1(v);//将v赋值给v1 vector <vector <int>> vec; vector <pair<int,int>> vec; vector <int> v(len,num);//长度为len，每个元素均为num vector <int> :: iterator it;//迭代器，用于调用 ``` #### 1.1.3 使用 ```cpp v.push_back(a);//插入a v.pop_back();//删除最后一个元素 v.size();//返回大小 v.clear();//清除所有数据 v.empty()//判断是否为空 v.erase(pos);//删除pos v.erase(bigin,end);//删除 [begin,end) v.resize(len);//重定义长度 v.reverse(len);//保留长度 v.front(); v.back();//返回第一个或最后一个数据 ``` 除此之外，`vector` 像普通数组一样，支持下标访问。不同的是，动态数组还支持迭代器访问。迭代器可以理解为地址。 ```cpp vector <int> v; vector <int> ::iterator it; for(it=v.begin();it!=v.end();it++) cout<<*it<<" "; ``` ### 1.2 LIST #### 1.2.1 定义 `list` 可以理解为 [双向循环链表](https://baike.baidu.com/item/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/2968731?fr=aladdin)，即每个节点有两个指针指向前驱和后继结点，且最后一个节点的后继为头结点、头结点的前驱为尾结点。 `list` 的特色是在集合的任何位置增加或删除元素都很快，但是不支持随机存取。 在编程语言中 `List` 是标准类库中的一个类，可以简单视之为双向链表，以线性列的方式管理物件集合。`list` 的特色是在集合的任何位置增加或删除元素都很快，但是不支持随机存取。`list` 是类库提供的众多容器之一，除此之外还有 `vector`、`set`、`map`等等。`list` 以模板方式实现(即泛型)，可以处理任意型别的变量，包括使用者自定义的资料型态例如：它可以是一个放置整数（`int`）型态的 `list`、也可以是放置字串（`char 或 string`）型态的 `list`、或者放置使用者自定类别的 `list`。 有序的 `collection`（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。 与 `vector`的区别: 参考 `list` 是双向循环链表，，每一个元素都知道前面一个元素和后面一个元素。在 STL 中，list 和 vector一样，是两个常被使用的容器。和 vector 不一样的是，list 不支持 **对元素的任意存取**。list 中提供的成员函数与 vector 类似，不过 list 提供对表首元素的操作，这是 vector 不具备的。和 vector 另一点不同的是，list 的迭代器不会存在失效的情况，他不像 vector 会保留备份空间，在超过容量额度时重新全部分配内存，导致迭代器失效；list 没有备份空间的概念，出入一个元素就申请一个元素的空间，所以它的迭代器不会失效。 #### 1.2.2 声明 格式与 vector 类似。 ```cpp #include<list> using namespace std; list <Type> Name; list <Type> :: iterator Name; ``` #### 1.2.3 使用 ```cpp v.push_back(a);//插入a v.pop_back();//删除第一个元素 v.push_front//插入a v.pop_front/删除第一个元素 v.size();//返回大小 v.clear();//清除所有数据 v.empty()//判断是否为空 v.erase(pos);//删除pos v.erase(bigin,end);//删除 [begin,end) v.resize(len);//重定义长度 v.reverse(len);//保留长度 v.front(); v.back();//返回第一个或最后一个数据 ``` ### 1.3 DEQUE 略（可视为 vector + list）。 ## 2.关联式容器 ### 2.1 SET $\cdots$ ### 2.2 MAP $\cdots$