标准模板库总结

一、容器

1、容器分类

STL容器分成三大类：序列容器、关联容器和容器适配器。

（1）序列容器：提供顺序表的表示和操作

vector：向量。可以随机访问序列中的单个元素，在序列尾快速插入和删除元素。如果在序列中插入和删除元素，则时间与序列长度成正比。

deque：双向队列。随机访问序列中的单个元素，可以在序列头或尾快速插入和删除元素。如果在序列中插入和删除元素，则时间与序列长度成正比。

list：双向链表。用动态链式存放数据，可以从任何位置快速插入和删除元素。

（2）关联容器：提供集合和映像的表示和操作

set：集合。无重复值元素，可以快速查找。

multiset：集合。允许重复值元素，可以快速查找。

map：映射。一对一映射，无重复值元素，实现基于关键字的快速查找。

multimap：映射。一对多映射，允许重复值元素，实现基于关键字的快速查找。

（3）容器适配器：特殊顺序表

stack（堆栈）：后进先出表，只能在表头插入和删除元素。

queue（队列）：先进先出表，只能在表头删除元素，在表尾插入元素。

priority_queue（优先队列）：优先级最高的元素总是第一个出列。

2、容器的接口

（1）容器的共同操作

Container c   //默认构造空容器

Container c（beg,end）   //以地址beg开始，到地址end的数据序列为初值构造容器

Container c1（c2）   //构造容器c2的副本

c.~Container（）   //析构容器对象

c1=c2   //对象赋值

c1.swap（c2）   //交换同类型容器中的数据

c1 op c2   //容器的关系运算，其中op可以为==，!=，<，>，<=，>=

c.size（）   //返回容器的元素个数

c.empty（）   //判断容器是否为空

c.max_size（）   //返回容器可容纳元素的最大数量

Container<T>::iterator iter   //定义容器迭代器对象iter

c.begin（）   //返回指向首元素的迭代器

c.end（）   //返回指向尾元素下一位置的迭代器

c.rbegin（）   //返回指向逆向首元素的迭代器

c.rend（）   //返回指向逆向尾元素下一位置的迭代器

c.insert（pos,elem）   //在迭代器pos所指位置前插入元素elem

c.erase（pos）   //删除迭代器pos所指元素

c.erase（beg,end）   //删除以地址beg开始，到地址end结束的数据元素

c.clear（）   //删除容器中所有元素

（2）序列容器的操作

c.front（）   //访问容器首元素数据

c.back（）   //访问容器尾元素数据

c.push_back（）   //在容器末端插入数据elem

c.pop_back（）   //删除容器末端数据

c.[i]   //访问容器第i个元素

c.at（i）   //返回索引（下标）i的元素

例：vector向量操作

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    unsigned int i;
    vector<int>V(10,0);   //实例化长度为10的vector向量V，置元素初始值为0
    for(i=0;i<10;i++)
    V[i]=i;   //使用重载运算符函数operator[]对元素赋值
    V.push_back(10);   //在表尾追加一个元素
    V.insert(V.begin()+3,33);   //在第三个位置插入一个元素
    cout<<"size of V is :";
    cout<<V.size()<<endl;   //输出表长
    cout<<"The elements of V are :";
    for(i=0;i<V.size();i++)   //输出表元素
    cout<<V[i]<<" ";
    cout<<endl;
    cout<<"The 6th element is :";
    cout<<V.at(5)<<endl;   //输出索引（下标）为5的元素
    cout<<"The first element(use begin()) is :";
    cout<<*(V.begin())<<endl;   //输出第一个元素
    cout<<"The last element(use rbegin()) is :";
    cout<<*(V.rbegin())<<endl;   //输出最后一个元素
    cout<<"The last element(use end()) is :";
    cout<<*(V.end()-1)<<endl;   //输出最后一个元素
    cout<<"The first element(use rend()) is :";
    cout<<*(V.rend()-1)<<endl;   //输出第一个元素
    vector<int>L;   //说明第2个向量
    for(i=0;i<V.size();i++)   //对L的元素赋值
    L.push_back(V[i]);
    if(V==L)
    cout<<"V==L"<<endl;   //对两个向量判等
    else
    cout<<"V!=L"<<endl;
}

二、迭代器

1、迭代器的分类

双向迭代器：可以双向行进，以递增运算前进或以递减运算后退，可以用==和！=比较。

list、set和map提供双向迭代器

随机存取迭代器：除了具备双向迭代器的所有属性，还具备随机访问能力。

可以对迭代器增加或减少一个偏移量、处理迭代器之间的距离或者使用<和>之类的关系运算符比较两个迭代器。

vector、deque和string提供随机存取迭代器

2、迭代器的基本操作

*   //返回当前位置上的元素值。如果该元素有成员，可以通过迭代器以operator->取用

++   //将迭代器前进至下一元素

==和！=   //判断两个迭代器是否指向同一位置

=   //为迭代器赋值（将所指元素的位置赋值过去）

三、STL容器

1、vector

（1）vector总述

vector模拟动态数组

vector的元素可以是任意类型T，但必须具备赋值和拷贝能力（具有public拷贝构造函数和重载的赋值操作符）

必须包含的头文件#include<vector>

vector支持随机存取

vector的大小（size）和容量（capacity）

（2）构造、拷贝和析构

vector<T> c	产生空的vector
vector<T> c1(c2)	产生同类型的c1，并将复制c2的所有元素
vector<T> c(n)	利用类型T的默认构造函数和拷贝构造函数生成一个大小为n的vector
vector<T> c(n,e)	产生一个大小为n的vector，每个元素都是e
vector<T>c(beg,end)	产生一个vector，以区间[beg,end]为元素初值
~vector<T>()	销毁所有元素并释放内存。

c.size()	返回元素个数
c.empty()	判断容器是否为空
c.max_size()	返回元素最大可能数量（固定值）
c.capacity()	返回重新分配空间前可容纳的最大元素数量
c.reserve(n)	扩大容量为n
c1==c2	判断c1是否等于c2
c1!=c2	判断c1是否不等于c2
c1<c2	判断c1是否小于c2
c1>c2	判断c1是否大于c2
c1<=c2	判断c1是否大于等于c2
c1>=c2	判断c1是否小于等于c2

（4）赋值操作

c1 = c2	将c2的全部元素赋值给c1
c.assign(n,e)	将元素e的n个拷贝赋值给c
c.assign(beg,end)	将区间[beg,end]的元素赋值给c
c1.swap(c2)	将c1和c2元素互换
swap(c1,c2)	同上，全局函数

（5）元素提取

at(idx)	返回索引idx所标识的元素的引用，进行越界检查
operator [](idx)	返回索引idx所标识的元素的引用，不进行越界检查
front()	返回第一个元素的引用，不检查元素是否存在
back()	返回最后一个元素的引用，不检查元素是否存在

（6）迭代器相关函数

begin()	返回一个迭代器，指向第一个元素
end()	返回一个迭代器，指向最后一个元素之后
rbegin()	返回一个逆向迭代器，指向逆向遍历的第一个元素
rend()	返回一个逆向迭代器，指向逆向遍历的最后一个元素

（7）安插（insert）元素

c.insert(pos,e)	在pos位置插入元素e的副本，并返回新元素位置
c.insert(pos,n,e)	在pos位置插入n个元素e的副本
c.insert(pos,beg,end)	在pos位置插入区间[beg,end]内所有元素的副本
c.push_back(e)	在尾部添加一个元素e的副本

（8）移除（remove）元素

c.pop_back()	移除最后一个元素但不返回最后一个元素
c.erase(pos)	删除pos位置的元素，返回下一个元素的位置
c.erase(beg,end)	删除区间[beg,end]内所有元素，返回下一个元素的位置
c.clear()	移除所有元素，清空容器
c.resize(num)	将元素数量改为num（增加的元素用defalut构造函数产生，多余的元素被删除）
c.resize(num,e)	将元素数量改为num（增加的元素是e的副本）

2、map/multimap

（1）map/multimap总述

使用平衡二叉树管理元素

元素包含两部分（key，value），key和value可以是任意类型

必须包含的头文件#include<map>

根据元素的key自动对元素排列，因此根据元素的key进行定位很快，但根据元素的value定位很慢

不能直接改变元素的key，可以通过operator[]直接存取元素值

map中不允许key相同的元素，multimap允许key相同的元素

（2）构造、拷贝和析构

map c	产生空的map
map c1(c2)	产生同类型的c1，并复制c2的所有元素
map c(op)	以op为排序准则产生一个空的map
map c(beg,end)	以区间[beg,end]内的元素产生一个map
map c(beg,end,op)	以op为排序准则，以区间[beg,end]内的元素产生一个map
~ map()	销毁所有元素并释放内存。

（3）非变动性操作

c.size()	返回元素个数
c.empty()	判断容器是否为空
c.max_size()	返回元素最大可能数量
c1==c2	判断c1是否等于c2
c1!=c2	判断c1是否不等于c2
c1<c2	判断c1是否小于c2
c1>c2	判断c1是否大于c2
c1<=c2	判断c1是否大于等于c2
c1>=c2	判断c1是否小于等于c2

（4）赋值

c1 = c2	将c2的全部元素赋值给c1
c1.swap(c2)	将c1和c2的元素互换
swap(c1,c2)	同上，全局函数

（5）特殊搜寻操作

count(key)	返回”键值等于key”的元素个数
find(key)	返回”键值等于key”的第一个元素，找不到返回end
lower_bound(key)	返回”键值大于等于key”的第一个元素
upper_bound(key)	返回”键值大于key”的第一个元素
equal_range(key)	返回”键值等于key”的元素区间

（6）迭代器相关函数

begin()	返回一个双向迭代器，指向第一个元素
end()	返回一个双向迭代器，指向最后一个元素之后
rbegin()	返回一个逆向迭代器，指向逆向遍历的第一个元素
rend()	返回一个逆向迭代器，指向逆向遍历的最后一个元素

（7）安插（insert）元素

c.insert(pos,e)	在pos位置为起点插入e的副本，并返回新元素位置（插入速度取决于pos）
c.insert(e)	插入e的副本，并返回新元素位置
c.insert(beg,end)	将区间[beg,end]内所有元素的副本插入到c中

（8）移除（remove）元素

c.erase(pos)	删除迭代器pos所指位置的元素，无返回值
c.erase(val)	移除所有值为val的元素，返回移除元素个数
c.erase(beg,end)	删除区间[beg,end]内所有元素，无返回值
c.clear()	移除所有元素，清空容器

3、set/multiset

（1）set/multiset总述

（2）操作及效果

begin()	返回指向第一个元素的迭代器
clear()	清除所有元素
count()	返回某个值元素的个数
empty()	如果集合为空，返回true
end()	返回指向最后一个元素的迭代器
equal_range()	返回集合中与给定值相等的上下限的两个迭代器
erase()	删除集合中的元素
find()	返回一个指向被查找到元素的迭代器
get_allocator()	返回集合的分配器

insert()	在集合中插入元素
lower_bound()	返回指向大于（或等于）某值的第一个元素的迭代器
key_comp()	返回一个用于元素间值比较的函数
max_size()	返回集合能容纳的元素的最大限值
rbegin()	返回指向集合中最后一个元素的反向迭代器
rend()	返回指向集合中第一个元素的反向迭代器
size()	集合中元素的数目
swap()	交换两个集合变量
upper_bound()	返回大于某个值元素的迭代器
value_comp()	返回一个用于比较元素间的值的函数

4、pair模板

用于生成key-value对

四、Algorithm（算法）