顺序容器:vector,deque,list

时间:2022-11-13 04:19:11

1.顺序容器:vector,deque,list

容器类共享公共接口,只要学会其中一种类型就能运用另一种类型。每种容器提供一组不同的时间和功能这种方案,通常不需要修改代码,秩序改变类型声明,每一种容器类型替代另一种容器类型,就可以优化程序的性能。容器值定义了少量操作,大多数额外的操作有算法库提供。

2.为了使用顺序容器,要包含头文件:

#include<vector>
#include<list>
#include<deque>

3.所有容器都是类模板,要定义某种容器要,要在容器明后加一对尖括号,尖括号里放元素类型:

vector<string> vec;
list<int> lis;
deque<string>;

所有容器类型都定义了默认的构造函数,用于创建制定类型的空容器对象。默认的构造函数都不带参数。

注:当元素类型为容器类型时,尖括号和元素类型之间要加空格

vector< vector<int> > vec;

 4.容器的初始化

初始化

解释

试用范围

C<T> c

创建一个名为c的空容器

所有容器

C<T> c(c2)

创建容器c2的副本cc2c必须具有相同的容器类型,并存放相同类型的元素

所有容器

C<T> c(b,e)

创建c,其元素是迭代器be标示范围内的元素的副本,be可以是具有相同元素类型的其他容器类型

所有容器

C<T> c(n,t)

用于创建n个值为t的容器ct必须为T类型或可转换为该类型的值

顺序容器

C<T> c(n)

创建有n个初始化元素的容器c

顺序容器

vector<int> vec(10,1);
vector<int> vec1(vec);   //OK
list<int> l(vec);       //error,此种初始化方式要求容器类型和元素类型都相同
list<int> l(vec.begin(),vec.end());  //ok,可以通过迭代器间接实现具有相同元素类型的不同容器间的赋值                                                                              

5.元素类型的约束

最低要求:

  • 元素类型必须支持赋值运算
  • 元素类型的对象必须可以复制

引用不能做元素类型,因为引用不支持一般意义的赋值运算

标准输入输出(I/O)不能做元素类型,因为不支持复制或赋值运算,但其他标准库类型可以

一些容器操作对元素类型还有特殊要求,我们可以定义该类型的容器,但不能使用这些对元素类型有要求的操作。假设类Foo没有默认的构造函数,但提供了一个int型形参的构造函数,现有以下声明:

vector<Foo> vec;   //ok,不需要初始化元素
vector<Foo> vec(10);  //error,创建有10个初始化元素的容器vec,但Foo没有默认的构造函数
vector<Foo> vec(10,1);  //ok,Foo提供了int型形参的构造函数。

注:当创建的容器包含元素的初始化时,该元素类型必须能够提供相应的构造函数。

6.迭代器

同容器类型一样,所有迭代器具有相同的接口,当一种迭代器支持某种操作时,那么支持这种操作的其他迭代器会以相同的方式支持这种操作

 

常用的迭代器操作:

操作

解释

适用范围

*it

返回迭代器所指向的元素的引用

所有容器

it->mem

it进行解引用,获取mem,等效(*it).mem

所有容器

++it , it++

it1,指向容器下一元素

所有容器

--it , it--

it1,指向容器前一元素

所有容器

it1==it2

比较两个迭代器是否相等,当两个迭代器指向同一容器里的同一元素,或超出末端的下一位置时,两个迭代器相等

所有容器

it1!=it2

>,<

<=,>=

当一个迭代器指向的元素在容器中的位置位于另一个迭代器指向的元素指向,则前一个迭代器小于后一个迭代器

vector,deque

 

vectordeque容器的迭代器支持迭代器算数运算,以及所有的关系运算;因为只有这两种容器支持元素的快速、随机访问,因而可以有效的实现算数和关系运算。

注:list的迭代器不支持算数运算和除==,!=之外的关系运算

7.容器定义的类型别名

size_type

无符号整形

iterator

此容器类型的迭代器

const_itreator

元素的只读迭代器

reverse_iterator

按逆序寻址元素的迭代器

congst_reverse_iterator

元素的只读逆序迭代器

difference_type

存储两个迭代器差值的有符号整型

value_type

元素类型

reference

元素的左值类型,是value_type&的同意

const_reference

const value_type

 

8.容器的成员函数

 

成员函数

含义

返回值

c.begin()

指向容器第一个元素

迭代器

c.end()

指向容器最后一个元素的下一位置

迭代器

c.rbegin()

指向容器最后一个元素

逆序迭代器

c.rend()

指向第一个元素前面的位置

逆序迭代器

c.push_back(t)

在容器尾部插入元素t

void

c.push_front(t)

在容器前端插入元素t;只适用于

list,deque

void

c.insert(p,t)

在迭代器p所指向的元素前面插入值为t的新元素

指向新元素的迭代器

c.insert(p,n,t)

在迭代器p所指向的元素前面插入n个值为t的新元素

void

c.insert(p,b,e)

在迭代器p所指向的元素前面插入由迭代器be标记的范围内的元素

void

c.size()

返回容器的实际元素个数

容器元素个数

c.max_size()

返回容器c可容纳的最多元素个数

最多元素个数

c.capacity()

返回容器的大小,>=c.size();获取在容器需要分配更多的存储空间之前可以存储的元素总数

 

c.reserve()

容器预留的空间,在预留的空间用完之前,不会重新分配新的空间。

 

c.empty()

判读容器是否为空

bool

c.resize(n)

调整容器长度,当n<c.size(),则删除多余的元素,否则,添加采用值初始化的新元素

void

c.resize(n,t)

调整容器c的大小,当n>c.size()时,新添加的元素值为t

void

c.back()

返回最后一个元素的引用,若容器为空,则该操作未定义

最后一个元素的引用

c.front()

返回第一个元素的引用,若容器为空,则该操作未定义

第一个元素的引用

c[n]

返回下标为n的元素的引用,只适用于deque,vector

越界,运行出错

下标为n的元素的引用

c.at[n]

返回下标为n的元素的引用,只适用于deque,vector

越界,运行出错,并抛出异常

下标为n的元素的引用

c.erase(p)

删除迭代器p所指向的元素,返回一个迭代器,指向被删除元素后面的元素,如指向最后一个元素,则返回的迭代器指向超出容器末端的下一位置。若p本身指向超出容器末端的下一位置,则该操作未定义

返回一个迭代器

c.erase(b,e)

删除迭代器be所标记的范围内所有的元素,不包括e指向的元素

返回一个迭代器(迭代器要求同上)

c.clear()

删除c内的所有元素

void

c.pop_back()

删除c的最后一个元素

void

c.pop_front()

删除c的第一个元素,只适用于listdeque容器

void

find(b,e,val)

 

查找迭代器be范围内的元素val,返回指向找到的第一个元素的迭代器,若没有找到,则返回指向容器末端下一位置的迭代器;使用find必须包括

#include<algorithm>

指向第一个元素的迭代器

count(b,e,val)

在迭代器be范围内查找值为val的元素个数,使用count必须包括#include<algorithm>

返回元素个数

c1=c2

删除容器c1中的所有元素,然后将c2的元素复制到c1.c1c2类型必须相同

 

c1.swap()

交换迭代器存放的元素,迭代器不会失效

void

c.assign(b,e)

重置c的元素,将迭代器be标记范围内的元素复制到c中。be不能是指向c中元素的迭代器,因为在重置时会先删除c中的内容

void

c.assign(n,t)

c容器的内容重置为nt

void

注:capacityreseve区别,capacity在插入新元素的过程中,即使还有剩余空间可能会增加,但当用reseve设定预留空间后,在该空间没有满之前,capacity不会继续增加,通常reseve和capacity同时使用,避免使用容器过程中多次分配空间带来的消耗;

 

9.迭代器失效

insert

vector,deque中插入元素,指向新插入元素后面的迭代器失效

resize

resize压缩了容器,则已删除的元素迭代器失效

赋值操作c1=c2

做操作数的所有迭代器失效

assign

所有迭代器失效

注:swap不会是迭代器失效

 

10.容器的选用

vecetordeque支持随机访问,但在eraseinsert元素时会移动元素

list不支持随机访问,但插入删除元素时不用移动元素