在已有 C++ 尤其是 C++ 模板的基础上，从本节开始，我们开始系统地学习 STL 标准模板库，首先来了解什么是 STL，以及学习 STL 有什么用？
STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

Vector数组

对比起数组固定性，Vector绝对是写数组的更方便的选择，Vector数组的创建删除插入等操作对比起数组绝对是更加方便的存在。

Vector数组的创建

Vector数组要包含头文件，并引入std命名空间
1
2
#include <vector>
using namespace std;

创建Vector数组

vector<类型>标识符;
vector<类型>标识符(最大容量);
vector<类型>标识符(最大容量,初始所有值);
vector<vector<int> > v;//二维vector，这里最外的<>要有空格，否则较旧的编译器下无法通过(会识别成位运算)
//用向量b给向量a赋值，a的值完全等价于b的值
vector<int>a(b);
//将向量b中从0-2（共三个）的元素赋值给a，a的类型为int型
vector<int>a(b.begin(),b.begin+3);
 //从数组中获得初值
int b[7]={1,2,3,4,5,6,7};
vector<int> a(b,b+7）;

Vector数组的初始化

a.assign();
//b为向量，将b的0-2个元素赋值给向量a
a.assign(b.begin(),b.begin()+3);
//a含有4个值为2的元素
a.assign(4,2);

Vector数组的使用

//返回a的最后一个元素
a.back();
//返回a的第一个元素
a.front();
//返回a的第i元素,当且仅当a存在
a[i];
//清空a中的元素
a.clear();
//判断a是否为空，空则返回true，非空则返回false
a.empty();
//删除a向量的最后一个元素
a.pop_back();
//删除a中第一个（从第0个算起）到第二个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+3（不包括它）结束
a.erase(a.begin()+1,a.begin()+3);
//在a的最后一个向量后插入一个元素，其值为5
a.push_back(5);
//在a的第一个元素（从第0个算起）位置插入数值5,
a.insert(a.begin()+1,5);
//在a的第一个元素（从第0个算起）位置插入3个数，其值都为5
a.insert(a.begin()+1,3,5);
//b为数组，在a的第一个元素（从第0个元素算起）的位置插入b的第三个元素到第5个元素（不包括b+6）
a.insert(a.begin()+1,b+3,b+6);
//返回a中元素的个数
a.size();
//返回a在内存中总共可以容纳的元素个数
a.capacity();
//将a的现有元素个数调整至10个，多则删，少则补，其值随机
a.resize(10);
//将a的现有元素个数调整至10个，多则删，少则补，其值为2
a.resize(10,2);
//将a的容量扩充至100，
a.reserve(100);
//b为向量，将a中的元素和b中的元素整体交换
a.swap(b);
//b为向量，向量的比较操作还有 != >= > <= <
a==b;

几个常用的函数

#include<algorithm>
//对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
sort(a.begin(),a.end());
//对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
reverse(a.begin(),a.end());
//把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素
copy(a.begin(),a.end(),b.begin()+1);
//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置
find(a.begin(),a.end(),10);

Set容器

set也是STL中比较常见的容器。set集合容器实现了红黑树的平衡二叉检索树的数据结构，它会自动调整二叉树的排列，把元素放到适当的位置。set容器所包含的元素的值是唯一的，集合中的元素按一定的顺序排列。
我们构造set集合的目的是为了快速的检索，不可直接去修改键值。

set容器的创建

照例先引入头文件
1
2
#include<set>
using namespace std;
创建set容器的方法和创建vector函数的方法大同小异
1
set<类型>标识符;

set容器的操作

insert() //在集合中插入元素
erase() //删除集合中的元素
clear() //清除所有元素
size() //集合中元素的数目
swap() //交换两个集合变量
begin() //返回指向第一个元素的迭代器
end() //返回指向最后一个元素之后的迭代器
count() //返回某个值元素的个数
find() //返回一个指向被查找到元素的迭代器
empty() //如果集合为空，返回true(真）
max_size() //返回集合能容纳的元素的最大限值

其实set的大部分操作是与vector类似的，不过set不支持随机访问，必须要使用迭代器去访问。由于set放入一个元素就会调整这个元素的位置，把它放到合适的位置，所以set中只有一个insert插入操作。

Pair容器

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。 pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，所以可以直接使用pair的成员变量。

pair容器的创建

1
2

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。

pair容器的操作

pair<int ,double> p1;
p1.first = 1;
p1.second = 2.5;
cout<<p1.first<<' '<<p1.second<<endl;
//输出结果：1 2.5

p1 = make_pair(1,2);//可以利用make_pair创建新的pair对象

Map容器

map是STL的一个关联容器，它提供一对一的hash。
第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
第二个可能称为该关键字的值(value)；

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的，后边我们会见识到有序的好处。比如一个班级中，每个学生的学号跟他的姓名就存在著一对一映射的关系。

map容器的创建

#include <map>
using namespace std;

map<int,int> m1;
map<vector<int>,int> m2;
//……

map容器的操作

begin()         //返回指向map头部的迭代器
clear(）        //删除所有元素
count()         //返回指定元素出现的次数
empty()         //如果map为空则返回true
end()           //返回指向map末尾的迭代器
equal_range()   //返回特殊条目的迭代器对
erase()         //删除一个元素
find()          //查找一个元素
get_allocator() //返回map的配置器
insert()        //插入元素
key_comp()      //返回比较元素key的函数
lower_bound()   //返回键值>=给定元素的第一个位置
max_size()      //返回可以容纳的最大元素个数
rbegin()        //返回一个指向map尾部的逆向迭代器
rend()          //返回一个指向map头部的逆向迭代器
size()          //返回map中元素的个数
swap()           //交换两个map
upper_bound()    //返回键值>给定元素的第一个位置
value_comp()     //返回比较元素value的函数

map应用实例

洛谷P1360 [USACO07MAR]Gold Balanced Lineup G

题解如下:

#include<bits/stdc++.h>
using namespace std;
map<vector<int>,int>f;
int ans;
int main(){
    int n,m;scanf("%d%d",&n,&m);
    vector<int>now(m);
    f[now]=0;
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        for(int j=0;j<m;j++)
            if(x&(1<<j))now[j]++;
        if(x&1)for(int j=0;j<m;j++)now[j]--;
        if(f.count(now))ans=max(ans,i-f[now]);
        else f[now]=i;
    }
    printf("%d",ans);
    return 0;
}