|
stl容器包括顺序式容器和关联式容器
顺序式容器包括vector，list，deque，queue，priority_queue,stack等
关联式容器包括set，multiset，map，multimap等
一、vector和list
数组有静态数组和动态数组两种类型，vector是stl的动态数组，可以节约空间也不易出错，需要时能改变数组大小。删除和插入操作少，访问元素频繁。
vector < int> a 定义a的初始化数组
vector < int> a(100,6) 定义a数组有100个值为6的元素
通过相同形式还可以定义字符串型数组和结构体数组
常用操作：
a.push_back(100); 在尾部添加元素
a.size(); 计算数组大小
a.empty(); 判断数组是否为空
a.insert(a.begin()+i,k); 插入功能，在第i个元素前插入k
a.insert(a.end(),10,5); 在尾部插入10个元素5
a.pop_back(); 删除尾部元素
a.erase(a.begin()+i,a.begin()+j); 删除功能，删除区间【i，j-1】的元素
a.resize(n); 调整数组大小
reverse(a.begin(),a.end()); 翻转数组
list是双向链表，它可以在任意地方插入和删除，随机访问较少，因此和vector的应用场景不同
list < int> a 定义a的初始化链表
list < int> a(5) 创建有5个元素的链表
常用操作：
a.begin(); 返回指向第一个元素的迭代器
a.back(); 返回最后一个元素
a.push_back(100) ; 向末尾添加一个元素
a.push_front(100) ; 向头部添加一个元素
a.empty(); 判断链表是否为空
a.pop_back(); 删除尾部元素
a.remove(); 删除元素
a.remove_if(); 按条件删除链表元素
a.resize(n); 调整链表大小
reverse(); 翻转链表
例题：hdu4841 圆桌判断好人坏人
先通过for的循环给动态数组a初始化，将圆桌取余处理，删除数组部分元素。
通过a.erase()进行的删除会减少数组大小但不会改变数组容量，之后通过if（元素是否还等于初始值）来判断出好人坏人
二、栈和队列
栈的特点是先进后出，把东西放进最底层最后再拿出来。
stack <数据类型> s 定义栈
常用操作：
s.push(100); 将元素放入栈顶
s.top(); 返回顶部元素
s.size(); 返回栈内元素个数
s.empty(); 判断栈是否为空
队列有三种类型：deque，queue和priority_queue
deque：双向队列，前后都可插入删除元素，可以直接访问任何元素
queue：队列，先进先出，排队完成事情后先出
priority_queue：优先队列，有排序功能，最高优先级元素第一个出列，设定数据小的优先级最高，因此能够完成从小到大的排序。
队列常用操作：
a.puch(100); 将元素插入队列
a.front(); 返回队首元素
a.pop(); 删除队首元素或其他队列不同的优先删除方法
a.back(); 返回队尾元素
a.size(); 返回队列大小
例题：hdu1062 翻转字符串
定义栈，通过判断空格分块翻转字符串，运用栈先进后出的原理将字符串读入栈后输出栈顶并清除栈顶，输出完成翻转。
三、set和map
关联式容器
set：集合，快速查找，不允许重复值。
map：基于关键字快速查找，不允许重复值
二者加上multi后可允许重复值
set <数据类型>x 定义set
常用操作：
x.insert(item); 把item放进set
x.erase(item); 删除元素item
x.find(k); 返回迭代器，指向键值k
x.lower_bound(k); 返回迭代器，指向键值不小于k的第一个元素
x.upper_bound(k); 返回迭代器，指向键值大于k的第一个元素
map <string,int>m 定义map
常用操作：
m.insert(a); 向其中插入一个元素a
m.erase(a); 移除键值为a的元素
m.erase(pos); 移除迭代器上所有的元素
m[key]=value; 直接元素存取
例题：hdu2094 产生冠军
定义集合A，B，将所有人放入集合A，失败记录放进集合B，只要满足A.size()-B.size()==1则存在冠军
map可以很好的查找键到值的映射，具有较高效率。student [“Tom”] =15将Tom当成数组下标使用，找到它的值，可以用于搜索学生id得出成绩等操作。
|