目录
前言
大家好呀！我是爱敲代码的小🐟儿。
?
从今天起，我就要正式开始学习c++的stl库了。学习呢自然不能光看别人写的，自己也要尝试动手写写，于是我打算将我学的知识以笔记的形式记录下来，方便大家共同学习😊
STL是什么？
先上个很官方的定义：STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。
怎么样，是不是没听懂，其实官方的我也没看太懂😅。咱先看一张图！
?通常认为，STL?是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，它们各自的含义如表 1 所示。
| STL的组成 | 含义 |
|---|---|
| 容器 | 一些封装数据结构的模板类，例如 vector 向量容器、list 列表容器等。 |
| 算法 | STL 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件 <algorithm> 中，少部分位于头文件 <numeric> 中。 |
| 迭代器 | 在?C++?STL 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。 |
| 函数对象 | 如果一个类将 () 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。 |
| 适配器 | 可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。 |
| 内存分配器 | 为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。 |
?对于我们初学者来说，STL的具体结构我们只用了解就行，比较对于我们大多数人来说，我们会用stl便捷的刷题就行，我们其实不太需要搞懂stl背后的复杂原理，嘻嘻🤣😂😍。
不管stl中还是有两个概念需要我们稍微理解一下的——容器和迭代器😅
- STL容器就是将运用最广泛的一些数据结构实现出来。容器用来管理某类对象。常用的数据结构：数组(array) , 链表(list), tree(树)，栈(stack), 队列(queue), 集合(set),映射表(map)。（其实，容器就是类似数组的单元，可存储 若干个值，且STL容器是同质的，即存储的值类型相同）
- 迭代器能够用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针；
可能你对这些概念还不是太理解，没关系以后在STL中我们经常会用到它们的，在用的过程中你对这些容器和迭代器慢慢就会有深刻的理解的。
为什么要学习STL?
?
在实际的开发过程中，合理组织数据的存取与选择处理数据的算法同等重要，存取数据的方式往往会直接影响到对它们进行增删改查操作的复杂程度和时间消耗。事实上，当程序中存在对时耗要求很高的部分时，数据结构的选择就显得尤为重要，有时甚至直接影响程序执行的成败。
大家在平时学数据结构的时候是不是经常要重复的写诸如链表、集合等等这些常见的数据结构😅，这些代码使用起来往往都十分类似，只是为了适应不同数据的变化，可能需要在一些细节上做不同的处理。
那么大家有没有想过，是不是可以重复利用那些已有的实现来完成当前的任务呢😁？当然是可行的，我相信有很多同学已经亲自编写并实现了动态数组类、链表类、集合类等程序，并精心维护着。但其实，STL?中提供了专家级的几乎我们所需要的各种容器，功能更好，复用性更高。有这样性价比更高的数据结构实现方法，我们为啥不学着去用呢😂？
?
?
为了让大家更清楚地了解 STL 是什么，使用 STL 编程有哪些优势，这里举一个使用 STL 的例子。
以 C++ 定义数组的操作为例，在 C++ 中如果定义一个数组，可以采用如下方式：
int a[n];
这种定义数组的方法需要事先确定好数组的长度，即 n 必须为常量，这意味着，如果在实际应用中无法确定数组长度，则一般会将数组长度设为可能的最大值，但这极有可能导致存储空间的浪费😅。
所以除此之外，还可以采用在堆空间中动态申请内存的方法，此时长度可以是变量：
int *p = new int[n];
这种定义方式可根据变量 n 动态申请内存，不会出现存储空间浪费的问题。但是，如果程序执行过程中出现空间不足的情况时，则需要加大存储空间，此时需要进行如下操作：
新申请一个较大的内存空间，即执行?int * temp = new int[m];
将原内存空间的数据全部复制到新申请的内存空间中，即执行?memecpy(temp, p, sizeof(int)*n);
将原来的堆空间释放，即执行?delete [] p; p = temp;
————————————
而完成相同的操作，如果采用 STL 标准库，则会简单很多??，因为大多数操作细节将不需要程序员关心😍。下面是使用向量模板类 vector 实现以上功能的示例：
vector <int> a; //定义 a 数组，当前数组长度为 0，但和普通数组不同的是，此数组 a 可以根据存储数据的数量自动变长。
//向数组 a 中添加 10 个元素
for (int i = 0; i < 10 ; i++)
a.push_back(i)
//还可以手动调整数组 a 的大小
a.resize(100);
a[90] = 100;
//还可以直接删除数组 a 中所有的元素，此时 a 的长度变为 0
a.clear();
//重新调整 a 的大小为 20，并存储 20 个 -1 元素。
a.resize(20, -1)当然了，上述代码中有一些是我们还未介绍的，大家只用大概了解代码功能即可，有关代码中涉及到具体知识，后续的学习笔记会做详细介绍😉。
容器详解
我们常见的大多都是序列容器😎
所谓序列容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。
需要注意的是，序列容器只是一类容器的统称，并不指具体的某个容器，序列容器大致包含以下几类容器：
- array<T,N>（数组容器）：表示可以存储?N 个 T 类型的元素，是?C++?本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
- vector<T>（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
- deque<T>（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
- list<T>（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list<T> 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
- forward_list<T>（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。
?
?
怎么样，是不是被指向概念整蒙了。没关系，在这里，大家只要对这些概念有个大致印象就行，在接下来的博客中，我会给大家详细的说这些容器的用法的?
注意，其实除此之外，stack<T> 和 queue<T> 本质上也属于序列容器，只不过它们都是在 deque 容器的基础上改头换面而成，通常更习惯称它们为容器适配器，有关它们的介绍，会放到以后的学习笔记中😉😊。
?上面所说容器的区别如图所示(●'?'●)
每一个容器都有大量的成员函数，下表只列出了一些最常用的函数?😅
| 函数成员 | 函数功能 | array<T,N> | vector<T> | deque<T> |
|---|---|---|---|---|
| begin() | 返回指向容器中第一个元素的迭代器。 | 是 | 是 | 是 |
| end() | 返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。 | 是 | 是 | 是 |
| size() | 返回实际元素个数。 | 是 | 是 | 是 |
?比如定义一个vector型的容器，就可以这样写😍：
vector<int> v; //定义了一个整形的vector容器v
你会写其他容器的定义吗 ？😎
迭代器详解
迭代器和?C++?的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。
我们常用的迭代器主要有以下几种😂：
1) 前向迭代器（forward iterator）
假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。
2) 双向迭代器（bidirectional iterator）
双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。
3) 随机访问迭代器（random access iterator）
随机访问迭代器具有双向迭代器的全部功能😎。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
- p+=i：使得 p 往后移动 i 个元素。
- p-=i：使得 p 往前移动 i 个元素。
- p+i：返回 p 后面第 i 个元素的迭代器。
- p-i：返回 p 前面第 i 个元素的迭代器。
- p[i]：返回 p 后面第 i 个元素的引用。
此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。另外，表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。
不同的容器要用到不同的迭代器😊
| 容器 | 对应的迭代器类型 |
|---|---|
| array | 随机访问迭代器 |
| vector | 随机访问迭代器 |
| deque | 随机访问迭代器 |
| list | 双向迭代器 |
| set / multiset | 双向迭代器 |
| map / multimap | 双向迭代器 |
| forward_list | 前向迭代器 |
| unordered_map / unordered_multimap | 前向迭代器 |
| unordered_set / unordered_multiset | 前向迭代器 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
啊！好多，记不住怎么办，嘻嘻又没说让你现在马上记住，用的多了常用的自然就有印象了
?
再告诉你个更恐怖的事，它们的定义方法也不太一样😅🐟
| 迭代器定义方式 | 具体格式 |
|---|---|
| 正向迭代器 | 容器类名::iterator? 迭代器名; |
| 常量正向迭代器 | 容器类名::const_iterator? 迭代器名; |
| 反向迭代器 | 容器类名::reverse_iterator? 迭代器名; |
| 常量反向迭代器 | 容器类名::const_reverse_iterator? 迭代器名; |
注意，以上 4 种定义迭代器的方式，并不是每个容器都适用。有一部分容器同时支持以上 4 种方式，比如 array、deque、vector；而有些容器只支持其中部分的定义方式，例如 forward_list 容器只支持定义正向迭代器，不支持定义反向迭代器。
通过定义以上几种迭代器，就可以读取它指向的元素，*迭代器名(可以把迭代器类别为c语言中的指针）就表示迭代器指向的元素。其中，常量迭代器和非常量迭代器的分别在于，通过非常量迭代器还能修改其指向的元素。另外，反向迭代器和正向迭代器的区别在于：
- 对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
- 而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素；
我们那stl中很常用的vector容器来举例吧！
vector容器所对应的是随机访问迭代器。假设p是一个随机访问迭代器，p的定义格式大致是
容器类名::iterator? 迭代器名;
#include<iostream>
#include<vector> //vector容器包含在该头文件中
using namespace std;
int main() {
// 定义一个包含5个整型元素的容器
vector<int> v = { 1, 2, 3, 4, 5, 6};
//定义该容器对应的迭代器
vector<int>::iterator i;
//第一种遍历方式，v类似普通数组
for (int i = 0; i < v.size(); ++i) {
cout << v[i] << " ";
}
cout << endl;
// 第二种遍历方式
i = v.begin(); //将迭代器指向容器的第一个元素
for (; i != v.end(); ++i) { //用!=比较两个迭代器
cout << *i << " ";
}
cout << endl;
//第三种遍历方式
i = v.begin();
for (; i < v.end(); i += 2)// 随机访问器支持“+=”整数的操作
cout << *i << " ";
return 0;
}?
?关于STL呢，咱们今天只是大概讲一下，接下来的博客我会详细的讲解每个容器的用法和注意事项😁
自己最近才开始写博客，内容有很多不足之处，希望大家多多包涵😉
下期预告：为什么说C++array是普通数组的升级版？