顺序容器
0、标准库中定义了三种顺序容器的类型:
vector、list、和deque,它们的差别在于访问元素的方式以及添加或删除元素相关操作的运行代价。
1、顺序容器和适配器
顺序容器
vector //支持快速随机访问
list //支持快速插入/删除
deque //双端队列顺序容器适配器
stack //栈
queue //队列
priority_queue //有优先级管理的队列
2、容器元素的初始化
//适用于所有容器
C c; //创建空容器c,C是容器类型名,T是元素类型
C c(c2); //创建容器c2的副本c,c和c2必须具有相同的容器类型,并存放相同类型的元素
C c(b,e); //创建c,其元素是迭代器b和e标示范围内元素的副本
//适用于顺序容器
C c(n,t); //用n个值为t的元素创建容器c
C c(n); //创建有n个值初始化元素的容器c
容器元素类型必须满足以下两个约束条件:
1)元素类型必须支持赋值运算
2)元素类型的对象必须可以复制,由于IO库类型不支持赋值或复制,因此不能创建存放IO类型对象的容器。
3、访问元素
1)容器可以用迭代器访问。
vector::iterator = vec.begin();
vector和deque迭代器支持算术运算(加法和减法)和关系运算(、=),list迭代器不支持算术和关系运算,只提供自增自减以及相等不等的运算。
2)其他操作
c.back() //返回容器c最后一个元素的引用
c.front() //返回容器c第一个元素的引用
//以下适用于vector和deque容器
c[n] //返回下标为n的元素的引用
c.at[n] //返回下标为n的元素的引用
4、顺序容器的操作
1)begin和end成员
c.begin() //返回一个迭代器,指向容器c的第一个元素
c.end() //返回一个迭代器,指向容器c的最后一个元素的下一个位置
c.rbegin() //返回一个逆序迭代器,指向容器c的最后一个元素
c.rend() //返回一个逆序迭代器,指向容器c的第一个元素的前一个位置
2)在顺序容器中添加元素的操作
//适用于所有容器
c.push_back(t) //在容器c尾部添加值为t的元素,返回void类型
c.insert(p,t) //在迭代器p所指向的元素的前面插入值为t的元素,返回指向新添加元素的迭代器
c.insert(p,n,t) //在迭代器p所指向的元素的前面插入n个值为t的元素,返回void类型
c.insert(p,b,e) //在迭代器p所指向的元素的前面插入由迭代器b和e标记的范围内的元素,返回void类型
//适用于list和deque容器类型
c.push_front(t) //在容器c前端添加值为t的元素,返回void类型
任何insert和push操作都可能导致迭代器失效,当编写循环将元素插入容器中时,必须确保迭代器在每次循环后都得到更新。避免存储end操作返回的迭代器。因为添加或删除元素都会导致迭代器失效。
3)在顺序容器中删除元素的操作
c.erase(p) //删除迭代器p所指向的元素
c.erase(b,e) //删除迭代器b和e所标记的范围内所有的元素
c.clear() //删除容器c中的所有元素
c.pop_back() //删除容器c的最后一个元素
//适用于list和deque容器
c.pop_front() //删除容器c的第一个元素
4)顺序容器的赋值操作
c1 = c2 //删除容器c1的所有元素,然后将c2的元素复制给c1,c1和c2的元素类型必须相同。
c1.swap(c2) //c1存放c2的元素,c2存放c1的元素,该函数的执行速度通常比将c2的元素复制到c1的操作快
c.assign(b,e) //将迭代器b和e标记的范围内所有元素复制到c中。b和e必须不是指向c中元素的迭代器,因为assign操作首先删除容器中原来存储的元素,所以传递给assign函数的迭代器不能指向该函数的容器内的元素。
c.assign(n,t) //将容器c重新设置为存储n个值为t的元素
5、容器的选用
1)vector中的元素是以连续的方式存放的,支持对其元素实现高效的随机访问。但是除容器首尾部外,其他任何位置的插入或删除操作都将要求移动被插入删除元素右边的所有元素。
2)list容器表示不连续的内存区域,允许向前向后逐个遍历元素,任何位置都可以高效地插入和删除一个元素,不需要移动操作。但是list不支持随机访问,访问某个元素要求遍历所涉及到的其他元素。
3)deque容器拥有更加复杂的数据结构,从deque队列两端插入和删除元素都非常快,在容器中间插入删除元素代价更高。但deque支持随机访问。通常来说,除非找到选择使用其他容器的更好理由,否则vector容器都是最佳选择。