免费网站建站 网页/宁波网络推广产品服务

        在C++编程里面，STL 是必不可少的，我们先列出来常用的几种容器：

      vector，list，Map，set，deque，queue

+ vector

        vector是一种动态数组，其内容在内存中是连续存放的，正是由于这种特征，决定了vector 的代表特征：

        随机访问速度很快，插入和删除效率较低。

        其内存分配 是按照 1、2、4、8、16…指数倍增长的（有效避免反复的内存分配和释放），内存增长示意图如下：

        

        先来看vector的几种初始化方式：

/** 初始化 - 方法1*/
vector<int> vec1;
for(int i=1;i<6;i++); // 通过push_backvec1.push_back(i);
/** 初始化 - 方法2*/
vector<int> vec2(5); // 或者 vec2(5,0)赋初值
for(int i=1;i<6;i++);   // 通过下标访问vec2[i]=i;
/** 初始化 - 方法3*/
int a[5] = {1,2,3,4,5};
vector<int> vec3(a,a+5); // 通过数组拷贝
/** 初始化 - 方法4*/
vector<int> vec4 {1,2,3,4,5}; // c++11新方法

        vector支持swap方式交换内存，这在两个vector之间进行数据交换时能够极大的提高效率：

/** vec2到vec1的赋值*/
if( !vec2.empty() )vec1.swap(vec2);
vec2.clear(); // 清空数据

        vector支持三种对象删除方式，pop_back，迭代器删除，remove。

/** 删除 - 方法1*/
vec1.pop_back(i); // 通过pop_back删除尾部元素
/** 删除 - 方法2*/
vec2.erase( vec2.begin() );  // 通过erase删除
/** 删除 - 方法3*/
remove( vec3.begin(),vec3.end() ); // 通过remove删除

        这里有个关键的问题要注意， 在通过erase进行删除时，会导致迭代器无效，这种情况下我们通常有两种解决方案，一是使用返回erase的返回值指向下一个元素（方法1），二是通过 ite++ 提前记录下一个元素（方法2），但我们不去比较这两种方法优劣。

vector<int> ite = vec1.begin();
/** 方法1 - 利用返回ite*/
while ( ite != vec1.end() )
{if (*ite > 3)ite = a.erase(ite);else++ite;
}
/** 方法2 - 利用ite++*/
ite = vec2.begin();
for( ;ite!=vec2.end(); )
{if(*ite > 3)ite = a.erase(ite++);else++ite;
}

        相信vector是我们在编程中应用最多的容器，没有之一，当然他还有很多优势等待我们去挖掘。

+ list

        list 是双向链表，内存不连续存放，因此不支持 [ ] 下标操作，与vector刚好相反，其 插入和删除速度非常快，但是访问速度比较慢。

        

        我们直接列出来 list的常用方法：

/** 初始化相关*/
listlist1; // 空链表
listlist2(5); // 初始化元素，or list2(5,0)
listlist3( list2.begin (),list2.end () ); // 内容拷贝
list1.assign(5,0); // 通过assign给list赋值/** 访问相关*/
begin() // 返回指向第一个元素的迭代器 
end() // 返回末尾的迭代器
rbegin() // 返回指向第一个元素的逆向迭代器
rend() // 返回指向末尾的逆向迭代器
front() // 返回第一个元素
back() // 返回最后一个元素/** 插入相关*/
push_back() // 在list的末尾添加一个元素 
push_front() // 在list的头部添加一个元素 
insert() // 插入一个元素到list中/** 删除相关*/
pop_back() // 删除最后一个元素 
pop_front() // 删除第一个元素 
erase() // 删除一个元素 
clear() // 删除所有元素
remove() // 从list删除元素 - 算法/** 判断及操作*/
empty() // 如果list是空的则返回true
size() // 返回list中的元素个数
resize() // 改变list的大小
sort() // 给list排序
merge() // 合并两个list
swap() // 交换两个list
reverse() // 把list的元素倒转

        关于 list 的遍历删除问题与 vector 一致（ 同样要注意迭代器失效的问题），这里我们不再赘述。

+ map (set)

        与前面vector与list不同之处在于，map 是<key,value>型容器，key用作关键字索引，value保存值，set只有一个key（没有value），其他都与map一致。

        map (set) 底层采用红黑树实现，感兴趣的同学可以了解下 红黑树（一种高效的平衡二叉树）。

        

        来看下map的关键代码：

#include <map>
#include <string>
#include <iostream>
using namespace std;/** 初始化及插入*/
map<int,string> names;
names.insert( pair<int,string>(1,"Linol Zhang") );
names.insert( make_pair<int,string>(2,"Hello World!") );/** 访问*/
cout<<names[1]; // 输出Linol Zhang
map<int,string>::iterator ite = names.find(2); // 通过find查找
if( ite!=names.end() )cout<<ite->second; // 输出Hello World!
map<int,string>::iterator ite1 = names.begin();
for( ;ite1!=names.end(); ++ite1 )
{cout<<ite1->second; // 输出
}/** 删除*/
for(ite1=names.begin(); ite1!=names.end(); )
{if(“Hello World!”==ite1->second)ite1 = list.erase(ite1);else++ite1;
}

        注意map的下标访问方式，因为map类已经对[]操作符进行了重载，因此能够对下标进行查找，如果查找到key直接调用（对应value进行修改），查找不到就会创建一个，因此 用下标进行访问不会失败。

        map用在快速访问（按主键访问）的情况较多，其 查询时间复杂度是 O(logN)。

+ deque

        deque 是一个双端队列，支持随即访问（也就是[ ]操作符），也支持两端操作（push、pop）_back | _front，deque 是基础容器类，已知的 statck、queue 底层都是用dequeue来实现。

        deque 的一个典型应用场合就是 Command模式，其优点就在于应对这种双端顺序访问的情况（Command模式会在后续章节介绍到）。

        看一下deque常用的代码段：

/** 初始化*/  
deque<int> dq1;
deque<int> dq2(5); // 初始化分配元素or dq2(5,0)初始值为0 
deque<int; dq3(d2); // 通过拷贝构造deque对象
int a[]={1,2,3,4,5};
deque<int> dq4(a,a+5); // 数组拷贝/** 元素删除 尾部删除用pop_back();头部删除用pop_front();*/
/** 任意迭代位置或迭代区间上的元素删除用 erase(&pos) | erase(&first, &last)；删除所有元素用clear();*/
cout<<dq4.pop_front()<<endl;

        关于stack、queue的说明：

stack: stack 是一个先进后出队列（FILO），栈顶插入，栈顶弹出。

queue: queue 是一个先进先出队列（FIFO），队尾插入，队首删除。