1 STL 线性数据结构容器

没有选 C++ 的课，自学 C++ 是为了打 CSP 更方便。C++ 提供的一些模版和方法可以极大地减少我的代码量和思维量，做题时更加高效。

数组类容器 vector¶

vector 的创建¶

需要包含<vector>头文件，创建方式例如

std::vector<int> vec1; // 空 vector
std::vector<int> vec2(5); // [0,0,0,0,0]
std::vector<int> vec3(5,114); // [114,114,114,114,114]
std::vector<int> vec4 = {1,2,3};

常用的方法例如

std::vector vec;
vec.push_back(114); // 在末尾添加元素
vec.pop_back(); // 删除末尾元素
vec.front(); // 第一个元素，vec 为空则发生错误
vec.back(); // 最后一个元素，vec 为空则发生错误
vec.size(); // 当前含有元素个数

其中，对于空的vector进行pop_back()是未定义行为，应先检查是否为空。

vector 的访问¶

vector支持下标访问，即可以采用和数组类似的方法进行访问。同时 vector 还支持迭代器访问。通过begin()方法可以获取指向其首部（第一个元素）的迭代器，通过end()方法获取指向其尾部（最后一个元素的下一个）的迭代器。

front(),back()和begin(),end()的区别

对于下面的声明：

std::vector<int> vec; 

vec.front()和vec.back()返回的是vec中元素的引用，类型为int；vec.begin()和vec.end()返回的是迭代器，类型为std::vector<int>::iterator。
迭代器有点像指针，实际上*(vec.begin())的结果和vec.front()的结果是一样的。

逆序迭代器和常迭代器

begin()和end()返回的是正序迭代器，与之对应地有逆序迭代器rbegin()和rend()。一张图形象展示：

若vec为std::vector<int>类型，那么逆序迭代器都是std::vector<int>::reverse_iterator类型。
实际上与这四个方法对应，还有四个产生只读迭代器（常迭代器）的方法，即cbegin()，cend()，crbegin()和crend()。他们所产生迭代器的类型为std::vector<int>::const_interator或者std::vector<int>::const_reverse_iterator。
常迭代器的特点是，不可通过它们修改vector中对象的值。

所以我们可以这样访问一个vector：

std::vector<int> vec;
/* 对 vec 进行一些插入操作 */
for(auto it = vec.begin();it != vec.end();it++){
    std::cout << (*it) << std::endl;
}
// 或者也可以用增强的 for 循环
for(auto it : vec){
    std::cout << (*it) << std::endl;
}

vector 的插入、删除和反转¶

插入用insert()函数。vector中有很多重载的insert()函数，介绍可能常用的两种：

std::vector<int> vec = {1,2};
// insert(pos,elem) 表示在迭代器 pos 所指位置前插入一个 elem
vec.insert(vec.begin(),3); // [3,1,2]
// insert(pos,n,elem) 表示在迭代器 pos 所指位置插入 n 个 elem
vec.insert(vec.begin() + 1,2,4) // [3,4,4,1,2]

删除用erase()函数。vector中有很多重载的erase()函数，介绍可能常用的两种：

std::vector<int> vec = {1,1,4,5,1,4};
// erase(pos) 表示删除迭代器 pos 所指位置的元素
vec.erase(vec.begin() + 2); // [1,1,5,1,4]
// erase(begin,end) 表示删除迭代器 begin 到迭代器 end 之间（依然是左闭右开）的元素
vec.erase(vec.begin() + 1,vec.begin() + 4); // [1,4]

删除满足特定条件的元素

删除元素时，大多不能提前知道要删除元素的位置在哪里，可能需要先遍历一下。比如要删除所有值为 $3$ 的元素：

std::vector<int> vec = {1,1,3,7,4,2,3};
for(auto it = vec.begin();it != vec.end();it++)
    if(*it == 3)
        vec.erase(it);

上面的代码存在问题，当it遍历到 $3$ 这个元素时，it被擦除变成野指针，不能使用了。此时it++继续遍历会造成问题。可以利用erase()本身的返回值：

std::vector<int> vec = {1,1,3,7,4,2,3};
for(auto it = vec.begin();it != vec.end();)
    if(*it == 3)
        it = vec.erase(it);
    else it++;

反转可能很少用到，可以通过vec.reverse(vec.begin(),vec.end())实现。

栈容器 stack¶

栈自己手写其实并不难，但既然有现成的模版，也没必要动这个脑子，对吧。

需要包含<stack>头文件，常用的方法有

std::stack<int> s;
s.push(114); // 在栈顶添加元素
s.top(); // 返回栈顶元素的引用，但不移除它
s.pop(); // 移除栈顶元素，无返回值
s.empty(); // 检查栈顶是否为空，返回 bool
s.size(); // 返回栈中元素数量

其中

对于空的stack进行pop()或者top()都是未定义行为，应先检查是否为空。
stack容器不提供随机访问方法，栈容器本身的特点就是只能访问、修改栈顶元素。

队列容器¶

普通队列容器 queue¶

队列自己写起来就稍微有些麻烦了，耗时且不能保证总是写对。使用容器的常数代价大，但是工作量小。

需要包含<queue>头文件，常用的方法有

std::queue<int> q;
q.push(114); // 在队尾添加元素
q.pop(); // 移除队首元素
q.front(); // 返回队首元素的引用
q.back(); // 返回队尾元素的引用
q.empty(); // 检查队列是否为空
q.size(); // 返回队列中的元素数量

优先队列¶

大顶堆¶

优先队列是非常重要的一个工具，其本质是包装好的堆，在实现优化的 Dijkstra 算法中有巨大意义。
创建一个优先队列需要包含头文件<queue>。下面的代码默认创建的是大顶堆：

std::priority_queue<int> pq;

创建的优先队列具有和stack类似的方法，即

pq.empty(); pq.size(); // 分别为判空和获取元素个数
pq.top(); // 返回堆的顶端结点，不删除
pq.pop(); // 移除这个顶端结点
pq.push(114); // 向堆中加入一个结点

其中后二者的时间复杂度应是 $O(\log n)$。

自定义优先级¶

通过这样的方式可以构造一个自定义优先级的优先队列：

std::priority_queue<int, std::vector<int>, compare> pq;

其中第一个模版参数表示队列中存储的元素为int类型，第二个模版参数指出了优先队列的底层容器，第三个参数compare是一个通过仿函数自定义优先级的结构体。比如可以使用下面的结构体构造小根堆：

struct compare {
    bool operator()(int a, int b) {
        return a > b; // 注意这里的比较逻辑，使得较小的整数具有更高的优先级
    }
};

对于仿函数的这两个参数a和b，仿函数返回true意味着a的优先级低于b。
有时候我们觉得专门创建一个这样的结构体重载运算符()不是优雅，也有解决办法。

普通方法使用匿名函数的方法

bool cmp(const int &a,const int &b) {
    return a > b; // 是小顶堆
}
std::priority_queue<int,std::vector<int>,decltype(&cmp)> pq(cmp);

auto cmp = [](const int &a,const int &b) {
    return a > b; // 也是小顶堆
};
std::priority_queue<int,std::vector<int>,decltype(cmp)> pq(cmp);