【C++】 STL（上）STL简述、STL容器

简述

STL是“Standard Template Library”的缩写，中文译为“标准模板库”。STL是C++标准库的一部分，位与各个C++的头文件中，即他并非以二进制代码的形式提供，而是以源码的形式提供。STL体现了泛型编程的思想，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或近似的方式处理各种不同情形，为我们提供了一个可扩展的应用框架，高度体现了程序的可复用性。STL的一个重要特点是数据结构和算法的分离。

STL的头文件都不加扩展名，且打开std命名空间。

包含了六大组件：

STL容器

主要分为两大类：

序列性容器：序列容器保持插入元素的原始顺序。允许指定在容器中插入元素的位置。每个元素都有固定位置，取决于插入时机和地点，和元素值无关，如：链表（list），向量（vector），双端队列（deque）。

关联性容器：元素位置取决于特定的排序规则和插入顺序无关，map、hash-map、set。容器类自动申请和释放内存，无需new和delete操作。

list链表

STL链表是序列性容器的模板类，它将其元素保持在线性排列中，链式结构，并允许在队列中的任何位置进行有效的插入和删除。

特点：list在任何指定位置动态的添加删除效率不变，时间复杂度为O(1)，操作相比于vector比较方便。但其查找效率为O(n)，若想访问、查看、读取数据使用vector。

双向循环链表：

require：#include using namespace std;

构造链表的几种方式

空链表：

list<int> lst;

构建指定长度的链表，且有默认的初始值

list<int> lst(3);

构建了指定长度的链表，手动指定初始值

list<int> lst(3, 4);

使用初始化列表进行构建 类似new int[3]{1,2,3};

list<int> lst{ 2,3,4 };

链表中的一些方法

1. begin()：获取头节点的迭代器。end()：获取尾节点的迭代器。
2. front()：返回头节点里的值。back()：返回尾节点里的值。
3. clear()：清空链表。
4. size()：返回链表的长度、元素的数量。
5. bool empty()，链表是否为空。
6. erase()：删除指定迭代器位置的节点，返回的是删除节点的下一个节点的迭代器。insert()：指定迭代器位置插入一个元素，返回的是插入的元素的迭代器。

insert()：

	list<int>::iterator ite = lst.insert(lst.begin(), 1);  //在指定位置之前for (int v : lst) {cout << v << "  ";}cout << endl;cout << "ite = " << *ite << endl;  //返回的是增加的

erase()：

	ite++;ite = lst.erase(ite);//返回的是删除的下一个for (int v : lst) {cout << v << "  ";}cout << endl;if (ite != lst.end()) {  cout << "ite = " << *ite << endl;    //ite=3}

注意：如果我们删除的是最后一个值，那么ite返回的就是尾节点，但是尾节点中没有元素，强行获取元素就会崩，所以要加一个判断

7. push_back()、push_front()、pop_back()、pop_front()：链表头尾添加、删除。
8. remove(const Type&_Val)：将值为val的所有节点删除。

将值为4的所有节点移除：

lst.remove(4);

9. unique()：对连续而相同的节点移除只剩一个。

	lst.push_back(0);lst.push_back(0);lst.push_back(1);lst.push_back(2);lst.push_back(0);lst.unique();  //连续且相同，移除只剩一个for (int v : lst) {cout << v << "  ";}cout << endl;

10. sort()：对链表元素进行排序，默认升序。如果要指定排序规则，需要指定排序规则函数。bool func(Type,Type);或greater()降序，less()升序。

默认：

	lst2.sort();  //默认升序for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;

指定规则：

bool rule(int a, int b) {return a > b;
}lst2.sort(&rule); //指定规则for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;

greater/less（降序/升序）

	lst2.sort(less<int>()/*greater<int>()*/);   for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;

11. reverse()：链表进行翻转。

	lst2.reverse();   //翻转链表for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;

12. **剪切拷贝整个链表：**splice(iterator Where,list& Right)：将Right链表整个结合到另一个链表Where位置之前，这是一个剪切操作，Right链表将为空。

	list<int> lst3{ 1,10,5 };ite = lst2.begin();::advance(ite, 3);   //ite+=3lst2.splice(ite, lst3);  //将lst3 整个链表放到 3位置之前 ，剪切操作for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;cout << "size = " << lst3.size() << endl;  //size = 0

这里我们了解到了一个函数：advance();它可以用来偏移迭代器，正常我们只能通过++来偏移，如果想偏移多个就要用循环，而不能用+=，那么我们就可以用这个方法

**剪切拷贝链表某个节点：**splice(iterator Where,list& Right,iterator First)：将Right链表的First位置节点结合到this链表的Where位置之前，这是一个剪切操作。this和Right可以为同一个链表。

	lst2.splice(ite, lst3, lst3.begin());for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;for (ite = lst3.begin(); ite != lst3.end(); ite++) {cout << *ite << "  ";}cout << endl;

**剪切拷贝链表的某一段节点：**splice(iterator Where,list& Right,iterator First,iterator Last)：将Right链表的First位置到Last位置的一段元素[First,Last)，不包含Last，结合到this链表的Where位置之前，这是一个剪切操作。this和Right可以为同一个链表，但Where不能位于[First,Last)内。

	lst2.splice(ite, lst3, lst3.begin(), --lst3.end());for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;for (ite = lst3.begin(); ite != lst3.end(); ite++) {cout << *ite << "  ";}cout << endl;

13. merge(list& Right,Traits Comp)：将Right链表合并到this链表上，this和Right必须经过排序，两者或都为递增、或都为递减，Comp描述了递增合并还是递减合并，bool func(Type,Type);或greater()降序，less()升序。这是一个剪切操作，Right将为空链表。

升序：

	lst2.sort();lst3.sort();lst2.merge(lst3);   //合并 剪切操作for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;cout << "size = " << lst3.size() << endl;

降序：

	lst2.sort(greater<int>());lst3.sort(greater<int>());lst2.merge(lst3,greater<int>());for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;cout << "size = " << lst3.size() << endl;

14. swap(list& Rigth)：交换两个链表。

	lst2.swap(lst3);for (ite = lst2.begin(); ite != lst2.end(); ite++) {cout << *ite << "  ";}cout << endl;for (ite = lst3.begin(); ite != lst3.end(); ite++) {cout << *ite << "  ";}cout << endl;

vector向量

vector的行为类似于数组（array），但是其容量会随着需求自动增长（动态数组）向量在尾部的push和pop操作时间是恒定的.在向量的中间insert或erase元素需要线性时间在序列结尾插入、删除操作比开始位置性能要优越。

当向量元素增加超过当前的存储容量时，会发生重新分配操作。重载了[]操作符，就意味着它可以像数组一样使用[下标]访问元素。

特点：数据的存储访问比较方便，可以像数组一样使用[index]访问或修改值，适用于对元素修改和查看比较多的情况，对于insert或erase比较多的操作，很影响效率，不建议使用vector。

构造向量

require：#include using namespace std;

vector(size_type Count)。vector(size_type Count,const Type& Val)。构造函数，构造指定长度的向量并设定初始值。有默认值。

空向量：

vector<int> vec;

指定向量的容量，默认值为0：

vector<int> vec(3);

指定向量的容量，并且指定默认值：

vector<int> vec(3, 1);

初始化列表初始化向量：

vector<int> vec{ 1,2,3 };

向量中的方法：

1. begin()，end()，返回向量头尾元素的迭代器。
2. front()，back()，返回头尾元素中的值。
3. size()，返回向量的使用量，capacity()，返回向量的容量。
4. push_back()，pop_back()，在向量尾部添加删除，当用push_back向vector尾部加元素的时候，如果当前的空间不足，会重新申请一块更大的空间。pop_back删除时，使用量减少，但容量不会减少。不同于list，并没有提供push_front()和pop_front()。
5. insert(const_iterator Where,const Type& Val)，向量的某个位置之前插入指定值。insert(const_iterator Where,size_type Count,const Type& Val)。向量的某个位置之前插入count个指定值。 返回插入元素的迭代器，size会增加。

ite = vec.insert(vec.begin(), 0);

6. erase(count_iterator Where)，删除迭代器指向的元素，返回的是删除元素的下一个元素的迭代器。size减少，capacity不变。

	ite = vec.begin() + 3;//ite += 3;ite = vec.erase(ite);

向量中的迭代器可以有+，+=操作

7. clear()，清空向量元素，size使用量为0，capacity不变。
8. empty()，向量是否为空，描述的是使用量（size）。
9. resize(size_type Newsize)，resize(size_type _Newsoze,Type _Val)。为向量指定新的使用量，如果使用量减少，元素按顺序截取，但容量不变；如果使用量增加，则会有默认值0；如果使用量增加大于原容量，则扩展容量，有默认值，也可以指定新的扩展元素的值。
10. swap(vector& Right)，交换两个向量的元素。

	vector<int>  v1(3);vec.swap(v1);

可以利用交换将向量中的使用量和容量都清零

vector<int>().swap(vec);

对比 list 和 vector ：

1. vector是连续性空间，是顺序存储，list是链式结构体，链式存储。
2. vector在非尾部插入、删除节点会导致其他元素的拷贝移动，list则不会影响其他节点元素。
3. vector一次性分配好内存，使用量不够时，申请内存重新分配。list每次插入新节点时都会申请内存。
4. vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。
5. vector具有容量和使用量的概念，而list只有使用量（即长度）概念。

deque双端队列

deque没有容量的观念。它是动态以分段连续空间组合而成，一旦有必要在deque的前端和尾端增加新空间，串接在整个deque的头端或尾端，deque的迭代器不是普通的指针，其复杂度比vector复杂的多。除非必要，我们应该尽量选择使用vector而非deque。

deque是一种双向开口的连续性空间，可在头尾两端分别做元素的插入和删除操作。

deque模型图：

构造双端队列：

require:#include using namespace std;

deque(size_type Count)，deque(size_type_Count,const Type& Val)，构造函数，构造指定长度的向量并设定初始值。有默认值。

同样也是有三种构造方法（指定元素个数给定默认值，手动给值，初始化参数列表）。

deque<int> de{ 1,2,3,4 };

方法：

1. push_back()、push_front()、pop_back()、pop_front()。
2. begin()、end()、back()、front()、erase()、insert()。
3. size()、empty()、clear()，支持[]下标访问，所以可以使用下标遍历。

双端队列的几种遍历方法：

下标：

	for (int i = 0; i < de.size(); i++) {cout << de[i] << "  ";}cout << endl;

增强的范围for：

	for (int v : de) {cout << v << "  ";}cout << endl;

迭代器遍历：

	deque<int>::iterator ite = de.begin();while (ite != de.end()) {cout << *ite << "  ";ite++;}

map映射表

Map的特性是，所有元素都会根据元素的键值自动被排序，map的所有元素都是pair，同时拥有键值（key）和实值（value）。pair的第一元素被视为键值，第二元素被视为实值。Map不允许两个元素拥有相同的键值，Map的键值关系到Map的元素排列规则，任意改变Map的元素键值将严重破坏Map的组织。所以不可以通过Map的迭代器来改变Map的键值。但可以通过迭代器来修改元素的实值。

查找效率：O(log2(n))，内部实现红黑树。

map模型图：

构造：

require：#include

map<char, int>  mm{ {'d',1},{'f',2},{'b',3} };

可以直接使用key值增加元素：

mm['c'] = 4;

方法：

1. begin()、end()，支持迭代器遍历。

	map<char, int> ::iterator ite = mm.begin();while (ite != mm.end()) {cout << ite->first << "-" << ite->second << "  ";ite++;}cout << endl;

2. pair<iterator,bool>insert(value_type& Val)，插入一个元素，如果key值重复，则插入失败。iterator erase(iterator Where)，返回删除的下一个。（没有push和pop的插入删除）。

插入：

	pair<map<char, int> ::iterator,bool> pr =  mm.insert(pair<char, int>('a', 5));  //插入成功，返回true，迭代器指向新增的元素if (pr.second) {cout << "插入成功" << endl;   //插入成功}else {cout << "插入失败" << endl;}cout << pr.first->first << "--" << pr.first->second << endl;  pr = mm.insert(pair<char, int>('a', 6));  //插入失败，返回false，迭代器指向的是已存在的元素if (pr.second) {cout << "插入成功" << endl;}else {cout << "插入失败" << endl;  //插入失败}cout << pr.first->first << "--" << pr.first->second << endl;

删除：

	ite = ++mm.begin();ite = mm.erase(ite);for (pair<char, int> pr : mm) {cout << pr.first << "-" << pr.second << "  ";}cout << endl;if (ite != mm.end()) {cout << ite->first << "-" << ite->second << endl;}

3. clear()、size()、empty()
4. iterator find(const Key& Key)、按键值查找，未匹配到返回end()，count(const Key& Key)，按键值统计元素，返回1或0。

通过键值查找删除元素：

	ite = mm.find('d');if (ite != mm.end()) {  //如果找到了元素，则删除ite = mm.erase(ite);}for (pair<char, int> pr : mm) {cout << pr.first << "-" << pr.second << "  ";}cout << endl;

5. upper_bound(const Key& Key)、返回大于该键值的map的迭代器。lower_bound(const Key& Key)，返回该键值或者大于该键值的map的迭代器。

	map<char,int>::iterator ite = mm.upper_bound('b');cout << ite->first << "-" << ite->second << endl;  //c-4

	ite = mm.lower_bound('b');cout << ite->first << "-" << ite->second << endl;  //b-3

如果upper_bound和lower_bound返回的迭代器相同，那么代表元素不存在

	char e = 'e';if (mm.upper_bound(e) == mm.lower_bound(e)) { //元素不存在cout << e << "不存在" << endl;}else {cout << e << "存在" << endl;}

set集合

所有元素都会根据元素的键值自动被排序，Set的元素Map那样可以同时拥有实值和键值，Set元素的简直就是实值，实值就是键值。Set不允许两个元素有相同的键值，因为Set元素值就是其键值，关系到Set元素的排列规则。如果任意改变Set的元素值，会严重的破坏Set组织。

查找效率：O(log2(n))，内部实现红黑树。

构造：

require：#include using namespace std;

set<int> st{ 4,1,6,3 };

因为没有实值键值的区分了，所以不能像map一样用[]去添加了

方法：

1. begin()、end()，支持迭代器遍历。

	set<int>::iterator ite = st.begin();while (ite != st.end()) {cout << *ite << "  ";ite++;}cout << endl;

2. pair<iterator,bool>insert(const value_type& Val)，插入一个元素，如果key值重复，则插入失败。iterator erase(iterator Where)，返回删除的下一个。

	pair<set<int>::iterator,bool> pr = st.insert(6);if (!pr.second) {cout << "插入失败" << endl;}cout << *pr.first << endl;

3. clear()、size()、empty()。
4. iterator find(const Key& Key)、按键值查找，未匹配到返回end()，count(const Key& Key)，按键值统计元素，返回1或0。

	ite = st.find(44);if (ite == st.end()) {cout << "没找到" << endl;}

5. upper_bound(const Key& Key)、返回大于该键值的set的迭代器。lower_bound(const Key& Key)，返回该键值或者大于该键值的set的迭代器。

hash_map哈希表

基于hash table（哈希表），数据的存储和查找效率非常高，几乎可以看作常量时间，相应的代价是消耗更多的内存。使用一个较大的数组来存储元素，经过算法，使得每个元素与数组下标有唯一的对应关系，查找时直接定位。

查找效率O(1)。

构造：

require：#include<hash_map> using namespace std;

若高版本需要 #define _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS 来去除error，或使用<unordered_map>

#include<unordered_map>
using namespace std;

	unordered_map<string, int>  mm;mm["aa"] = 1;mm["ff"] = 2;mm["oo"] = 3;mm["cc"] = 4;

方法：

1. begin()、end()，返回头、尾节点的迭代器。支持迭代器遍历。

	unordered_map<string, int>::iterator ite = mm.begin();while (ite != mm.end()) {cout << ite->first << "-" << ite->second << "  ";ite++;}cout << endl;

遍历结果为无序的

2. pair<iterator,bool> insert(const value_type& Val)，插入一个元素，如果key值重复，则插入失败。iterator erase(iterator Where)，返回删除的下一个。
3. iterator find(const Key& _Key)，按照key值进行查找， 注意：查找速度，数据量，内存使用。

	ite = mm.find("cc");ite = mm.erase(ite);for (pair<string, int> pr : mm) {cout << pr.first << "-" << pr.second << "  ";}cout << endl;cout << ite->first << "-" << ite->second << endl;