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。键和值相等，键唯一，元素默认按升序排列。