C++学习笔记第九章（顺序容器）

一、 顺序容器类型

顺序容器

vector 支持快速随机访问，相当于数组

list       支持快速插入和删除，相当于链表

deque  双端队列

顺序容器适配器

statck  后进先出（LIFO）堆栈

queue  先进先出（FIFO）队列

priority_queue  有优先级管理的队列

二、头文件

#include

#include

#include

所用容器都是类模版

vector svec;

list            ilist;

deque item;

三、初始化

1、将一个容器初始化另一个容器的副本。

vector ives;

vector ivec2(ivec);

将一个容器负责给另一个容器时，类型必须匹配：容器类型和元素类型都必须匹配。

2、不能直接将一种容器内的元素复制给另一种容器，可以通过传递一对迭代器间接实现该功能。

list slist(svec.begin(), svec.end());

3、查找容器的中间点

vector::iterator mid = svec.begin() + svec.size()/2;

4、初始化front队列，采用svec的前半部分，不包括*mid

deque front(svec.begin(), mid);

5、初始化back，采用svec的后半部分。

deque back(mid, svec.begin());

6、分配和初始化指定数目的元素

const list::size_type list_size = 64;

list slist(list_size "eh");

四、容器类元素的类型约束

1、元素类型必须支持赋值运算。

2、元素类型的对象必须可以复制。

引用不支持一般意义的赋值运算，因为没有元素是引用类型的容器。

五、容器中的容器

vector< vector > //注意<> 中间需要使用空格，表示这是两个分开的符号，否则、

系统会认为 >> 是单个符号，为右移操作符。

六、迭代器和迭代器的范围

常用迭代器运算

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

++iter

--iter

iter != iter2

verctor 和 deque 支持 iter + n 操作，list为链表形式不支持 + n 操作。

list容器既不支持算法运算（加减法），也不支持关系运算（<=,>=）,只支持自增和自减、相等

不等运算。

七、容器的begin和end操作

c.begin()  返回一个迭代器，指向容器c的第一个元素    

c.end()     返回一个迭代器，指向容器c最后一个元素的下一个位置    

c.rbegin()  返回给一个逆序迭代器，指向容器c的最后一个元素

c.rend()     返回给一个逆序迭代器，它指向容器c的第一个元素的前面的位置

八、在顺序容器中添加元素

关键概念：容器元素都是副本，在容器中添加元素时，系统是将元素值复制到容器中。

c.push_back(t)  在容器的尾部添加值为t的元素，返回void类型

c.push_front(t)  在容器c的前端添加值为t的元素，返回vod类型，只适用list和deque类型。

c.insert(p,t)    在迭代器p所指向的元素前面插入值为t的新元素，返回指向新添加元素的迭代器。

c.insert(p, n, t) 在迭代器p所指向的元素插入n个值为他、的新元素，返回void类型

cinsert(p, b, e) 在迭代器p所指向的元素前面插入由迭代器b和e标记的范围内的元素，返回void类型。

九、顺序容器的大小操作

c.size()  返回容器c中的元素个数，返回类型为c::size_type

c.max_size()  返回容器c可容纳的最多元素个数，返回类型为c::size_type

c.empty 返回标记容器大小是否为0的布尔值。

c.resize(n) 调整容器c的长度大小，使其能容纳n个元素，如果 n < c.size()，则删除多出来的元素。否则

采用初始值添加新元素。

c.resize(n, t) 调整容器c的长度大小， 使其能容纳n个元素， 所有新添加的元素值都为t。

十、访问顺序容器内元素的操作

c.back()    返回容器c的最后一个元素的引用，如果c为空，则该操作未定义

c.front()    返回容器c的第一个元素的引用，如果c为空，则该操作未定义

c[n] 返回下标为n的元素的引用，只适用于vector和deque

c.at(n) 返回下标为n的元素的引用，只适用于vector和deque

十一、删除元素

c.erase(p) 删除迭代器p所指向的元素，返回一个迭代器，它指向被删除元素后面的元素，如果p指向

容器内的最后一个元素，则返回迭代器所指向容器的超出末端的下一位置。

c.erase(b, e) 删除迭代器b和e所标记的范围内所有元素

c.clear() 删除容器c内的所有元素。返回void

c.pop_back()  删除容器c的最后一个元素。返回void，如果c为空容器，则该操作未定义

c.pop_front() 删除容器c的第一个元素、返回void。只适用于list或者deque容器。

十二、赋值与swap操作

赋值操作为先删除左操作数容器中的所有元素，然后将右操作数容器的所有元素inserts到左边容器中。

c1 = c2 删除容器c1的所有元素，然后将c2的元素复制给c1.

c1.swap(c2) 

c.assign(b, e)

c.assign(n ,t)

十三、vector容器的自增长

 

vector容器由于是顺序存储了，为了避免新增元素时，需要重新分配内存，在初次分配时会分配一个较大的内存空间，在后面当内存不够时，会采用加倍当前容量的分配策略实现重新分配。

 

十四、容器的选择

list容器表示不连续的内存区域，允许向前和向后逐个遍历元素。在任何位置都可高效插入和删除元素。但是不支持随机访问。

 

1、程序如果要求随机访问，则使用vector或deque

2、如果程序必须在容器的中间插入或删除元素，则应采用list元素。

3、如果程序不是在容器的中间位置，而是在容器的首部或尾部插入或删除元素。则应采用deque容器。