C++常用容器
C++ 有两类常用容器，分别是顺序容器和关联容器，顺序容器例如vector，list，queue，关联容器例如map，set。
一、顺序容器
1.vector
vector是C++中最常用的容器之一。
vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。
由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。
vector有多个构造函数，默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的，即内存空间增长是按照1，2，4，8.....增长的，在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。
1）vector的定义与初始化
vector<int> vec1; //默认初始化，vec1为空
vector<int> vec2(vec1); //使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end());//使用vec1初始化vec2
vector<int> vec4(10); //10个值为0的元素
vector<int> vec5(10,4); //10个值为4的元素
2）vector常用操作方法
vec1.push_back(100); //尾部添加元素
int size = vec1.size(); //元素个数
int capacity=vec1.capacity() //vector的容量，这与元素个数不同，大小是一个2的次幂。
bool isEmpty = vec1.empty(); //判断是否为空
cout<<vec1[0]<<endl; //取得第一个元素,或者vec1.front()获得第一个元素的引用
cout<<vec1.back()<<endl; /取得最后一个元素，但不可以用*vec1.end()来取
vec1.insert(vec1.end(),5,3); //从vec1.back位置插入5个值为3的元素,该方法的第一个参数应该是一个位置指针，可以写成
//vec1.insert(vec1.begin()+2,1,10);
//这时会发生内存地址的变换，因为数组的大小变了，如果要遍历数组，需要重新定位begin和end
vec1.pop_back(); //删除末尾元素
vec1.erase(vec1.begin(),vec1.begin()+2);//删除vec1[0]-vec1[2]之间的元素，不包括vec1[2]其他元素前移
cout<<(vec1==vec2)?true:false; //判断是否相等==、！=、>=、<=...
vector<int>::iterator iter = vec1.begin(); //获取迭代器首地址
vector<int>::const_iterator c_iter = vec1.begin(); //获取const类型迭代器
vector<int>::reverse_iterator r_iter //获取反向迭代器
vec1.clear(); //清空元素
vec1.rbegin;
vec1.rend; //获取前向指针(用于逆序输出数组)
3） vector遍历方法
//用迭代器的方法遍历
vector<int>::iterator iter = vec1.begin();
for(;iter != vec1.end();iter++)
{
cout<<*iter;
}
下标遍历就不说了
4）vector的内存泄漏问题
vector.clear()可以用来删除vector内的元素，但并不能释放vector的内存（这有点类似cin的输入流），正确的vector内存释放应该通过swap函数来解决，swap()是交换函数，使vector离开其自身的作用域，从而强制释放vector所占的内存空间。应该这样写：
vector <string>v(10000,1);
vector<string>(v).swap(v); //这样来释放内存
5）vector排序问题
vector没有自带的sort函数，但可以调用<algorithm>库中的sort函数
#include<algorithm>
sort(v.beign(),v.end());
还可以使用<algorithm>库中的reverse函数来翻转数组
reverse(v.begin(),v.end());
6）vector remove指定元素
需要调用<algorithm>库中的remove函数
remove(v.begin(),v.end(),10) //删除v内所有为10的元素
ret=remove(v.begin(),v.end(),10)
v.erase(ret,v.end()) //这样才真正remove了这些元素
需要将remove和erase联合起来使用
2.list
list是stl实现的双向链表，与向量vector想比，它允许快速的插入和删除，但是随机访问却是比较慢，需要添加头文件#include<list>
list用法基本和vector相似，不同的是：
1)list特殊之处
lst1.remove(2); //相同的元素全部删除
lst1.sort(); //排序
lst1.unique(); //删除相邻重复元素
lst1.reverse(); //反转list
list可以直接实现一些vector需要外界函数实现的功能
2)list元素访问
list只能通过迭代器指针来访问元素，这不同于vector
3.deque
deque是一个双向队列，它支持从队首插入和队首弹出，这区别于vector
deque.push_front();
deque.pop_front();
4.stack
堆栈stack，其操作比较简单
stack<int>S;
s.push()
s.pop()
s.size()
s.empty()
s.top() //返回栈顶的元素
二、关联容器
1.map
map会根据key进行自动排序，因此查找时效率为log（n）
1)定义和初始化
初始化一个map
map<int,string> map1;
插入元素，或定义元素
map1[0] = "Saniya"; //添加元素
map1.insert(map<int,string>::value_type(2,"Diyabi"));//插入元素
map1.insert(pair<int,string>(1,"Siqinsini"));
map1.insert(make_pair<int,string>(4,"V5"));
2) 从map中取元素
map<int,string>::iterator iter_map = map1.begin();//取得迭代器首地址
int key = iter_map->first; //取得key
string value = iter_map->second; //取得value
3）一些常用用法
map1.erase(iter_map); //删除迭代器数据
map1.erase(3); //根据key删除value
map1.size(); //元素个数
map1.empty(); //判断空
map1.clear(); //清空所有元素
2.set
set的含义是集合，它是一个有序的容器，里面的元素都是排序好的支持插入、删除、查找等操作，就像一个集合一样，所有的操作都是严格在logn时间内完成，效率非常高。set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同，set默认是自动排序的，使用方法类似list。键和值相等，键唯一，元素默认按升序排列。
