2023.1.2 STL

对之前的两篇文章进行了汇总和修改，方便大家阅读

1. 常用的 STL 汇总
2. 再遇 STL

STL Outline

1. c++ 基础语法
   1. 输入输出
   2. 重载运算符
   3. for each 语法
2. 补充内容
   1. string 类型
   2. sort() 排序
3. STL
   1. 基础概念：迭代器 （指示某一个元素）
   2. STL 容器
      1. vector ***
      2. deque
         1. stack
         2. queue
      3. priority_queue ***
      4. set
      5. map ***
      6. pair
   3. 查找
      1. lower_bound
      2. upper_bound

前言

STL是C++标准库的一部分，中文翻译为“标准模板库”，其中包含了一些常用的算法与数据结构，他们通常存储在<algorithm>以及对应的头文件中，或者是直接使用<bits/stdc++.h>。
下面将补充一些基础内容并简单介绍几种常用的STL容器，内容以概括汇总为主，并不涉及很多原型以及特殊用法。
如无特殊说明，以下默认使用x作为变量，使用it指代迭代器

补充内容

学校第一学期开授的程序设计课程使用的为 C 语言，因此在正式介绍 STL 之前会简单的介绍一下竞赛中基础的 C++ 知识。（ C++ 的最大特性应当是它的面向对象，但是竞赛选手很少使用它的面向对象，所以也戏称我们使用的是 C with STL）

新类型 string

C 中我们常常使用 char 数组配合 scanf("%s",str) 读入字符串，但是在 C++ 中封装了更为便捷的 string 类型。

访问指定字符 以及 输入输出

string 和字符数组十分类似，可以直接通过下标运算符 [] 访问指定的字符，并且可以通过赋值的方式修改当前字符。换句话说，你可以将 string 类型的字符串看做一个更加便捷的字符数组。

string 的读入和字符数组的读入规则是类似的，当遇到“空格”“换行”时会自动断开。在 C 中我们会使用 gets() 进行处理，但是 gets() 在 C++ 中已经被废弃了，所以使用 getline() 处理读入一行的操作。

string str;
// 正常读入，遇到空格或者换行结束
cin>>str;
cout<<str;
// 读入一行，遇到空格不结束，换行结束
getline(cin,str);
cout<<str<<endl;
// 输出第 0 位的字符
cout<<str[0]<<endl;

被重载运算符 以及 常用的方法

string 对常用的 + += = 以及比较运算符 > < 等进行了重载，从而可以进行更为便捷的拼接、复制、比较操作，不需要再依赖 strcat() strcpy() 等函数。

除此之外，string 还有封装好的一些方法可以调用，对其方法的调用和结构体访问成员类似，均使用成员运算符 . ：

运算符/方法名	方法效果
+	当 + 两侧均为字符串或字符时（可以为字符串常量或者 char 类型）可以将其拼接
=	将 str 右侧的字符串赋值给左侧字符串，是深拷贝，而非复制的引用
> >= < <=	按照字典序比较字符串大小，因为比较运算符被重载了，因此可以直接调用 sort() 进行排序
size()	返回字符串的实际长度，效果和 strlen() 相同。
substr(begin, length)	传入开始位置(从0开始)以及要截取的长度，返回截取的字符串

string str1, str2;
cin >> str1;
for (int i = 0; i < str1.size(); i++)
{
    cout << str1[i];
}
cout << endl;

cin >> str2;
cout << str1 + " " + str2 << endl;
cout << str1 + " not " + str2 << endl;
cout<<str2.substr(0,3);

运行示例：

string str1, str2;
cin >> str1>> str2;
if(str1 > str2)
{
    cout<<str1<<" bigger than "<<str2<<endl;
}else{
    cout<<str1<<" smaller than "<<str2<<endl;
}

运行示例：

sort()

在 c++ 中想要实现快速的排序，不需要再手动实现排序函数，只需要调用 sort() 函数即可。

sort() 可以对数组进行排序，也可以对 STL 中的 vector 进行排序，默认为从小到大排序。其参数列表包含两个必选参数和一个可选参数： sort(begin, end, cmp)。

sort() 的调用

参数	是否必选	参数意义
begin	是	传入一个指针或者迭代器，表示要排序的开始位置
end	是	传入一个指针或者迭代器，表示要排序的结束位置
cmp	否	排序的规则，默认为从小到大排序

1. 数组排序
   可以采用数组名+偏移量的方式设置排序范围：sort(arr, arr + 10);
2. vector 排序
   与数组类似，但是可以直接使用 begin() end 获取首尾迭代器，从而对整个容器进行排序：
3. 带 cmp 参数的排序
   想要实现自定义排序有两种方式：
   1. 自定义 cmp 函数
   2. 使用 greater less

sort(arr, arr+10);//数组排序
sort(arr.begin(), arr.end());// vector 排序
sort(arr,arr+10,cmp);// 自定义 cmp 函数
sort(arr,arr+10,greater<int>()); // 使用 greater 

通常我们的 cmp 函数都是这样的：

int cmp(int a, int b)
{
    return a > b;
}

实际上自定义的 cmp 和 greater less 是一样的，本质上都是比较规则作出了规定。

return a>b 实际上是返回了一个布尔值，a 表示前一个元素，b表示后一个元素。上述示例的 cmp 函数的作用就是当前一个元素大于后一个元素的时候返回 true ，等效于使用 greater。

运算符的重载

在使用结构体时我们需要进行运算符的重载（overload）才能够正常的使用 sort() 以及一些容器。
除了像上面使用 cmp 对运算规则进行定义以外，更常用的是在结构体中进行重载。

语法如下：

struct node
{
    int x, y;
    bool operator<(const node &o) const
    {
        if (x == o.x)
        {
            return y < o.y;
        }
        return x < o.x;
    }
};

对于运算规则的定义，可以直接在 bool operator<(const node &o) const 中进行修改。

基本概念

迭代器 iterator

STL中存在迭代器的概念，它类似指针操作，指向容器中的某个元素。同样可以使用“*”解除引用，在不同的STL中还分为“随机访问迭代器”和“双向访问迭代器”，两者在使用上有所不同。

随机访问迭代器

代表容器:vector

有类似指针的操作，可以对迭代器进行加减从而实现移动；也可以两个迭代器相减获得两个元素的位置。
以vector为例,遍历并输出：

vector <int> a;
for(vector<int>::iterator i=a.begin();i!=a.end();i++)
{
    cout<<*i<<" ";
}
//或者是：
for(int i=0;i<a.size();i++)
{
    cout<<it[i];
}

双向访问迭代器

代表容器：set

只能对迭代器进行++或者–操作，不能像随机访问迭代器一样跳跃访问或者是赋值。
像set这样内部有序的容器，++和–操作代表的是按照排序规则的上一个元素或者是下一个元素。

容器	对应的迭代器类型
array	随机访问迭代器
vector	随机访问迭代器
deque	随机访问迭代器
list	双向迭代器
set / multiset	双向迭代器
map / multimap	双向迭代器
forward_list	前向迭代器
unordered_map / unordered_multimap	前向迭代器
unordered_set / unordered_multiset	前向迭代器
stack	不支持迭代器
queue	不支持迭代器

通用操作

以下是所有容器都支持的操作，之后将不再列出这两个操作:

a.size();//返回容器中元素的数量
a.empty();/如果容器为空返回true，否则返回false

以下一些成员函数经常出现，并且功能类似，这里提前进行介绍，在之后的内容中不再详述:

a.begin();//返回容器首元素的迭代器
a.end();//返回容器最后一个元素之后的迭代器，a.end()-1才是最后一个元素的迭代器
a.clear();//清空容器
a.push(x);//向容器中添加一个元素，类似的还有push_back和push_front
a.pop();//将容器中的元素弹出，类似的还有pop_back和pop_front

vector向量/动态数组

vector实现的是基于倍增的思想。

一般声明的数组长度是固定的，如果使用链表储存，不断动态申请内存会降低程序运行的效率，并且程序的编写会变得更加复杂，因此我们常使用vector来当作动态数组。

在底层实现中，vector也是通过动态申请内存的方式来实现动态存储。当vector被存满的时候会进行扩容操作，基本的过程如下：

1. 重新申请一个更大的空间。
2. 将原数据存入新空间。
3. 释放原有空间。

因为扩容后数据存储到了一个新空间中，因此原有的迭代器、指针和引用有可能会失效，同时为了避免反复申请空间，不同的编译器会申请不同的额外空间，通常是之前数据的两倍。

将所有数据放入新空间的操作尽管花费了更多的时间，但是可以保证内存空间的连续性，这也是为什么vector可以支持随机访问。

常用的成员函数

a.push_back(x);
a.pop_back();
a.clear();
a.push();
a.pop();
a.begin();
a.end();

常用用法

1. 使用下标进行访问元素
2. 存储邻接表
3. hash的拉链法
4. 当做动态数组使用

deque双端队列

参考：C++ STL deque容器底层实现原理（深度剖析） (biancheng.net)

deque 和vector有些类似，都是通过动态申请空间实现。

不同的是deque存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。然后使用一个map数组记录每一段的地址，由此保证整体有序。
当要在队首或者队尾插入新的数据时，只需要新申请一段空间，然后将其地址存入map数组中。
当map数组存满以后使用类似vector的方式重新申请空间并转移数据。

常用的成员函数

q.push_back(x);
q.push_front(x);
q.pop_back();
q.pop_front();
q.front();//返回队首元素
q.back();//返回队尾元素
q.clear();
q.begin();
q.end();

常用用法

stack、list、queue的底层均使用了deque实现。

stack栈

栈是一种基础的数据结构，也被称为FILO表（先进后出），底层使用deque实现。
常用的成员函数

s.push(x);
s.pop();//弹出栈顶元素
s.top();//返回栈顶元素的引用

注意，栈并没有提供迭代器可以遍历所有元素，也没有提供clear来快速清空。

queue队列

队列是一种基础数据结构，也被称为FIFO表（先进先出），底层使用deque实现。
常用的成员函数

q.push(x);
q.pop();
q.front();//返回队首元素
q.back();//返回队尾元素

常用用法

1. 在进行广度优先搜索时会使用到queue，有些算法可能会使用到堆优化，则需要使用下面的priority_queue.

priority_queue优先队列

优先队列底层通过vector实现，并在其内部维护了一个堆，因此可以保证top的元素为最大（最小）。
我们在大多数情况下可以使用优先队列来代替堆。

声明方式

priority_queue <int> q;//默认大根堆
priority_queue <int,vector<int>,greater<int>> q;//声明小根堆
priority_queue <int,vector<int>,less<int>> q;//声明大根堆

对于大根堆和小根堆，还可以通过结构体的重载运算符实现，但如果不存储结构体变量，上述的声明方式更加简洁.

常用的成员函数

q.push(x);
q.pop();
q.top();//返回堆顶元素，也就是最大值（最小值）

常用用法

1. 代替堆
2. 需要维护最大或者最小值的情况
3. 优先队列优化算法

扩展操作：懒惰删除法

相比于自己手写的堆，STL的灵活性并没有那么高，不能进行单点修改、单点删除等。为此我们可以使用懒惰删除法。
我们采取的策略是额外记录删除信息，当我们从堆顶取出来的时候再判断元素是否已经被删除，也就是说删除操作要在堆顶进行。

set/multiset集合

这两个容器维护的是一个集合，前者不允许集合中存在相同的元素，后者允许相同的元素存在。
在集合中的元素都是有序的（默认从小到大，可以重载运算符）。

常用的成员函数

s.clear();
s.begin();
s.end();
s.insert(x);//插入一个元素
s.find(x);//查找等于x的元素并返回他的迭代器，如果不存在则返回s.end();
s.lower_bound(x);//查找大于等于x的元素中最小的一个，并返回指向他的迭代器
s.upper_bound(x);//查找大于x的元素中最小的一个，并返回指向他的迭代器
s.erase(it);//删除it指向的元素
s.erase(x);//删除所有等于x的元素（multiset）
s.count(x);//计算集合中x的数量（multiset）

关于lower_bound和upper_bound

这两个函数的区别在于是否取到等于号，也常被用在二分中。
同时也可以作为一个独立的函数调用。

map/multimap映射

该容器存储一个键值对（key-value）
常用的成员函数

m.clear();
m.begin();
m.end();
m.insert(make_pair(key,value));
m.erase(it);
m.erase(key);//以上和set功能类似
m.find(key);//查找到key所在的二元组并返回迭代器，如果不存在则返回m.end()

[ ]操作符
该容器也可以使用[ ]来访问元素，但索引不是下标，而是key值（类似PHP中Array的键值对），同时可以对其进行复制操作改变value

常用用法

1. 当做hash表使用。
2. 需要统计的时候

参考内容

[1]李煜东．算法竞赛进阶指南．
[2]C语言中文网：C语言程序设计门户网站(入门教程、编程软件) (biancheng.net)