C++之STL简易食用指南

一、何为STL

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。
————摘自C语言中文网

二、容器

以下代码中的T可以是任何一中数据类型,可以是自定义类型，甚至可以嵌套。

1、栈

#include<stack>

//声明：
stack<T>mystack;

//常用方法：
void mystack.push(T elem); //压栈
void mystack.pop(); //出栈
T mystack.top(); //返回栈顶的元素
int mystack.size(); //返回栈中元素个数
bool mystack.empty(); //判断栈是否为空

2、队列

#include<queue>

//声明
queue<T>myqueue;

//常用方法
void myqueue.push(T elem); //入队
T myqueue.front(); //返回队头元素
T myqueue.back(); //返回队尾元素
void myqueue.pop(); //出队
int myqueue.size(); //返回队列中元素个数
bool myqueue.isempty(); //判断队列是否为空

双端队列deque

双端队列可以在队列的两端进行存取操作，包含在头文件deque中，声明方法与普通队列类似。
接下来使用表格形式来展示部分常用的方法

方法名	用处
front()	返回第一个元素
back()	返回最后一个元素
push_back()	在序列的尾部添加一个元素
push_front()	在序列的头部添加一个元素
pop_back()	移除容器尾部的元素
pop_front()	移除容器头部的元素

deque和vector的作用十分类似，但实际上deque更适合频繁的入队、出队操作。

优先队列priority_queue

普通的队列是一个先进先出的序列，而优先队列会在队内根据优先级对元素进行排序，是一种先进最高级先出的队列。其本质上是一个堆,每次出队时，会将队列内优先级最高的元素弹出。

方法名	用处
top	访问队头元素
empty	队列是否为空
size	返回队列内元素个数
push	插入元素到队尾 (并排序)
pop	弹出队头元素

除了front改为top外，其他方法没有什么区别。
优先队列比较复杂的是声明操作,其定义为：
priority_queue<Type, Container, Functional>
Type是模板类型，Container是容器，Functional是仿函数（一般写为greater或less）

#include<queue>
//下面这个声明新建一个将int从小到大排序的优先队列
priority_queue <int,vector<int>,greater<int> > pq1;
//下面这个声明新建一个将int从大到小排序的优先队列
priority_queue <int,vector<int>,less<int> > pq2;
//！！！注意，部分编译器会将“>>”认成右移运算符，所以需要加一个空格以区分

在优先队列中使用自定义类

在实际运用中很经常遇到的情况是对含有多个属性的记录进行排序，这时候就要使用自定义类（结构体）。而如果直接将上述代码中的int改为自定义结构体，实际上是会报错的。因为我们并没有为结构体定义如何比较他们的大小（也就是优先级），两个学生，谁的优先级更高，到底是由身高、体重还是成绩决定呢？
所以，在使用自定义类（结构体）时，需要先进行运算符重载（只需要重载小于号）：

class Student
{
    int grade,height;
    Student(int grade, int height)
    {
        this.grade=grade;
        this.height=height;
    }
    //下面是重载运算符的部分
    bool operator < (const Student& a) const
    {
        //若成绩一样就用身高
        if(this.grade==a.grade)
            return this.height<a.height;
        else return this.grade<a.grade;
    }
}

[...]

priority_queue <int,vector<int>,less<int> > pq1;

这样就可以声明一个优先队列，队列优先弹出成绩高的学生，若成绩一样，就优先弹出身高高的学生。
当然，也可以通过自定义仿函数的方法来定义优先级，本着实用主义的原则，会其中一种方法就可以，这里不再赘述。

3、映射map

map的定义类似python中的字典，是一个键值对映射，包含两个模板参数key和value。map的内部实现是一棵红黑树，所以key必须定义小于号运算符。map也可以被当做哈希表使用。由于map内部已经定义“[]”运算符，所以元素的存取可以通过下标来实现，十分方便。
举个最常用的例子：统计单词重复出现的次数

//健是字符串，值是整型
map<string,int>words;
[...]
string article[101];
for(int i=1;i<=n;i++)
{
    map[article[i]]++;
}

需要注意的是，当使用“[]”操作没有找到对应的键时，map会自动创建一个值为0的键值对，积累之后，可能会产生大量的无意义记录，占用空间，并且影响运行速度。所以建议在使用下标获取值之前，事先使用map.find()找到该元素（该方法返回一个迭代器，若不存在，则会返回map.end()）。

二、算法

算法在上一篇《C语言的上机小技巧》已经说的差不多了，这里不再赘述。