C+中STL用法详解二_常用容器用法介绍

熟悉容器的使用是掌握STL的基本步骤。
许多容器都支持empty()、size()、front()、back()、begin()、end()等方法，这是因为算法进行了封装。

1. 序列式容器

序列容器以线性序列的方式存储元素。元素在序列中的顺序与存储的顺序相同，没有对元素进行排序。

vector的基本用法
长度可变序列，但只能在序列的末尾高效地增加或删除元素。

vector<类型>T;  //构建
T.push_back(x); //尾部新增一个元素x
T.insert(iterator it, int x); //在it指向的元素前新增一个x
T.insert(iterator it, int n, int x); //在it指向元素前插入n个x
T.erase(iterator it); //删除it指向的元素
T.erase(iterator first, iterator last); //删除[last,first)中元素
T.pop_back(); //删除最后一个元素
T.empty(); //判断是否为空
T.size(); //返回元素个数
T.at(index); //返回index编号元素
reverse(T.begin(), T.end()); //反转T中元素
T.begin(); //返回首元素指针
T.end(); //返回最后一个元素+1的指针
T.front(); //返回首元素引用
T.back(); //返回尾元素引用
sort(T.begin(), T.end()); //排序

deque的基本用法
以双端队列形式组织元素，在尾部和头部插入删除迅速，在中间插入删除元素则比较费时，因为必须移动中间其它元素。

deque<类型>T； //声明一个双端队列
deque<类型>T(size,value); //声明具有size个value默认值的双端队列
T.push_front(x); //在头部插入x
T.push_back(x); //在尾部插入x
T.pop_front(); //弹出头部的一个元素
T.pop_back(); //弹出尾部的一个元素
T.front(); //返回第一个元素的引用
T.back(); //返回最后一个元素的引用
T.begin();
T.end();
T.size();
T.at(index);
T.insert(it, x);

list的基本用法
list实现的是双向链表，与vector比它允许快速的插入和删除，但随机访问比较慢。

list<类型>T; // 构建
T.push_back(x);
T.push_front(x);
T.pop_back();
T.pop_front();
T.front();
T.back();
T.begin();
T.reverse();
T.sort();
T.end();
T.insert(x);
T.remove(x);

2. 关联式容器

map的基本用法
map是关联容器的一种，通过键值对来存储。map内部自建一颗红黑树(平衡二叉树)，这棵树具有对数据的自动排序功能（按照键值排序，当键值是不可比较元素时需指定比较仿函数）。
map容器有4中，每一种都由类模板定义，因为修改键会扰乱容器中元素的顺序，每种map容器模板都有不同的特性：

map：唯一<key,value>对应，默认按键值从小到大排序。
mutlimap：允许使用重复的键。
unordered_map：元素的顺序并不是直接由键值确定的，而是由键值的哈希值决定的。

unordered_multimap：通过哈希值确定对象的位置，允许有重复的键。

map< int,string > T; //构建
T.insert(make_pair<int,string>(1, "student_one")); //插入
T.empty();
T.size();
T.erase(key); //根据key删除，返回删除元素的数量
T.erase(iterator it); //删除迭代器指向位置的键值对，并返回指向下一个元素的迭代器
T.at(key); // 根据key获取对应value值
T.find(key); //返回指向键值key的迭代器指针
T.count(key);

2.mutlimap的基本用法
mutlimap容器保存的是有序的键值对，键值可以重复。

1	//操作与map类似

3.set的基本用法
set搜索、移除、插入都是对数复杂度，以红黑树实现。set内的元素会被自动排序，set中的元素即是键值又是实值，set不允许两个元素有相同的值。不能通过set的迭代器去修改set元素，当对容器中的元素进行插入或删除时，操作之前的所有迭代器在操作之后依然有效。
定义set容器的模板如下：

set：容器保存 T 类型的对象，而且保存的对象是唯一的。其中保存的元素是有序的，默认用 less 对象比较。
multiset：容器保存 T 类型对象的方式相同，但它可以保存重复的对象。
unordered_set：容器保存 T 类型的对象，而且对象是唯一的。元素在容器中的位置由元素的哈希值决定。
unordered_mutliset：容器保存 T 类型对象的方式和 unorderd_set 相同，但它可以保存重复的对象。
1
2
3
4
5
set<类型>T; //构建
T.insert(x);
T.count(x);
T.find(x);
T.erase(x);

4.mutliset的基本用法

1	//操作与set类似

3. 容器适配器

stack的基本用法
实现类似于栈的功能（后进先出）：

stack <类型> T; //构建
T.empty();
T.push(item);
T.pop();
x = T.top();
int size = T.size();

queue的基本用法
实现类似于队列的功能（先进先出）：

queue <类型> T; //构建
T.push(item);  //push到队列尾部
T.pop();   //弹出队首
x = T.front();
y = T.back();
T.size();
T.empty();

prority_queue的基本用法
priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。它和queue不同的是我们可以自定义其中数据的优先级，让优先级高的排在队列前面，优先出队。
但是如何定义“优先级”完全取决于我们自己。如果一个优先级队列记录的是医院里等待接受急救的病人，那么病人病情的严重性就是优先级。如果队列元素是银行的借贷业务，那么借记可能会优先于信贷。

prority_queue <类型> T; //构建
priority_queue <int,vector<int>,greater<int> > q; //升序序列
priority_queue <int,vector<int>,less<int> > q; //降序序列
T.push(x); //按优先级push到合适位置
T.pop();
T.top();
T.size();
T.empty();