当前课程知识点:C++语言程序设计进阶 > 第十章 泛型程序设计与C++标准模板库 > 顺序容器 > 顺序容器的特征
顺序容器:向量、双端队列、列表、单向链表、数组
向量(Vector)
容量(capacity):实际分配空间的大小
s.capacity() :返回当前容量
s.reserve(n):若容量小于n,则对s进行扩展,使其容量至少为n
一个可以扩展的动态数组
随机访问、在尾部插入或删除元素快
在中间或头部插入或删除元素慢
特点
向量的容量
双端队列(deque)
在两端插入或删除元素快
在中间插入或删除元素慢
随机访问较快,但比向量容器慢
特点
先按照从大到小顺序输出奇数,再按照从小到大顺序输出偶数。
// 头部分省略 int main() { istream_iterator<int> i1(cin), i2; //建立一对输入流迭代器 vector<int> s1(i1, i2); //通过输入流迭代器从标准输入流中输入数据 sort(s1.begin(), s1.end()); //将输入的整数排序 deque<int> s2; //以下循环遍历s1 for (vector<int>::iterator iter = s1.begin(); iter != s1.end(); ++iter) { if (*iter % 2 == 0) //偶数放到s2尾部 s2.push_back(*iter); else //奇数放到s2首部 s2.push_front(*iter); } //将s2的结果输出 copy(s2.begin(), s2.end(), ostream_iterator<int>(cout, " ")); cout << endl; return 0; }
特点
在任意位置插入和删除元素都很快
不支持随机访问
接合(splice)操作
s1.splice(p, s2, q1, q2):将s2中[q1, q2)移动到s1中p所指向元素之前
// 头部分省略 int main() { string names1[] = { "Alice", "Helen", "Lucy", "Susan" }; string names2[] = { "Bob", "David", "Levin", "Mike" }; //用names1数组的内容构造列表s1 list<string> s1(names1, names1 + 4); //用names2数组的内容构造列表s2 list<string> s2(names2, names2 + 4); //将s1的第一个元素放到s2的最后 s2.splice(s2.end(), s1, s1.begin()); list<string>::iterator iter1 = s1.begin(); //iter1指向s1首 advance(iter1, 2); //iter1前进2个元素,它将指向s1第3个元素 list<string>::iterator iter2 = s2.begin(); //iter2指向s2首 ++iter2; //iter2前进1个元素,它将指向s2第2个元素 list<string>::iterator iter3 = iter2; //用iter2初始化iter3 advance(iter3, 2); //iter3前进2个元素,它将指向s2第4个元素 //将[iter2, iter3)范围内的结点接到s1中iter1指向的结点前 s1.splice(iter1, s2, iter2, iter3); //分别将s1和s2输出 copy(s1.begin(), s1.end(), ostream_iterator<string>(cout, " ")); cout << endl; copy(s2.begin(), s2.end(), ostream_iterator<string>(cout, " ")); cout << endl; return 0; }
单向链表每个结点只有指向下个结点的指针,没有简单的方法来获取一个结点的前驱;
未定义insert、emplace和erase操作,而定义了insertafter、emplaceafter和erase_after操作,其参数与list的insert、emplace和erase相同,但并不是插入或删除迭代器p1所指的元素,而是对p1所指元素之后的结点进行操作;
不支持size操作。
array是对内置数组的封装,提供了更安全,更方便的使用数组的方式
array的对象的大小是固定的,定义时除了需要指定元素类型,还需要指定容器大小。
不能动态地改变容器大小
STL所提供的顺序容器各有所长也各有所短,我们在编写程序时应当根据我们对容器所需要执行的操作来决定选择哪一种容器。
如果需要执行大量的随机访问操作,而且当扩展容器时只需要向容器尾部加入新的元素,就应当选择向量容器vector;
如果需要少量的随机访问操作,需要在容器两端插入或删除元素,则应当选择双端队列容器deque;
如果不需要对容器进行随机访问,但是需要在中间位置插入或者删除元素,就应当选择列表容器list或forward_list;
如果需要数组,array相对于内置数组类型而言,是一种更安全、更容易使用的数组类型。
大家好
欢迎回来继续学习
C++语言程序设计
这一节我们来学习
顺序容器的特性
首先我们看一下向量的特点
向量
它是一个可以扩展的动态数组
我们可以对向量进行随机访问
在向量的尾部插入
或者删除元素
速度比较快
但是在向量的中间
或者头部插入删除元素的时候
这个就比较慢了
效率就比较低了
向量它有容量
所谓向量的容量
就是实际分配给这个向量对象
它的空间的大小
调用它的可capacity函数
就可以返回当前的容量
我们还可以用reserve这个函数
对它的容量进行扩展
如果当前这个容量小于n的话
经过扩展
使它的容量至少达到n
双端队列呢
它的特点是
在队列的两端插入
或者删除元素的话
速度会比较快
如果在队列的中间插入
和删除元素呢
速度就比较慢
对双端队列中的元素
进行随机访问
也还是比较快的
但是比向量容器的速度
就要慢一些
下面这个例子呢
就演示了双端队列的应用
这是一个奇偶排序的例子
这里
首先建立了一对输入流迭代器
i1用cin作为参数构造的
表示从标准输入设备输入
i1 是默认构造的
表示输入流的结束位置
这样我们通过这一对输入流
迭代器作为参数
来构造一个向量对象s1
也就是从
标准输入流输入一系列整数
存放到向量s1里面
那接下来呢
再调用sort这个函数
对整数的序列进行排序
从向量的起始位置的迭代器
到结束位置的迭代器
也就是说对
向量里面存放的全部元素
进行排序
这样排序好了以后呢
我们再构造一个双端队列对象s2
接下来在这个for循环中
我们遍历s1
看这个遍历的开始呢
是s1.begin返回的迭代器
也就是指向了向量s1的开始位置
结束位置是s1.end
返回的迭代器
也就是指向向量的结束位置
好 那在这个循环中
我们要判别一下
当前这个迭代器所指向的对象
它是不是偶数
如果是偶数呢
就调用push_back
放到双端队列的尾部
如果是奇数呢
就放到双端队列的首部
这样就达到了
奇偶排序的效果
最后用这个copy函数
将s2双端队列里面的结果输出
列表的特点呢
就是在任意位置插入和删除元素
速度都很快
但是它不支持随机访问
列表还有一个很有用的接合操作
也可以认为就是拼接
它的作用是将s2里面的区间
从q1到q2的元素
移动到s1中p所指向的元素之前
下面这个例题呢
就演示了列表的拼接操作
这里首先定义两个string数组
names1和names2用作素材
然后接下来我们来看
用names1数组的内容
来构造了这个list
也就是列表s1
然后用names2数组的内容呢
构造了列表s2
接下来呢
我们就来验证一下
这个拼接的操作
首先呢
我们调用这个拼接的函数
将s1的第一个元素
放到s2的最后的位置
然后我们定义一个迭代器对象
iter1
让它指向s1的开始位置
这个advance函数呢
是使这个迭代器前进的意思
这里呢
我们调用advance函数
让这个iter1这个迭代器
前进两个元素
于是它就指向了s1的第三个元素
然后再定义一个iter2
让它指向了s2的开始位置
那接下来用这种自增的运算
也是可以让这个迭代器向前进的
所以让它向前走一个元素
于是他就指向了s2的第二个元素
接下来呢
再定义一个iter3
也是个迭代器
让它跟iter2指向同一个位置
所以用iter2来初始化iter3
在这个之后呢
再一次调用advance
使iter3再前进两个元素
于是它指向了s2的第四个元素
现在呢
我们就用iter2和iter3
来界定一个范围
将这个范围内的结点
拼接到s1里面
iter1所指向的结点之前
像这样拼接完了以后呢
我们再分别调用copy
输出s1和s2
验证一下
的确这是我们拼接的效果
单向链表的每个结点中
只有一个指向后继结点的指针
所以在单向列表中
是没有简单的方法
可以获得一个结点的前驱结点的
所以呢
我们在list里面定义的
像insert emplace
和erase操作呢
都不能作用于单向链表
单向链表自己定义了
特殊的相关操作
insert_after emplace_after
和erase_after操作
这几个操作
它的参数
跟list里面对应的insert emplace
和erase操作的参数
都是相同的
但是它的差别在于
并不是插入或者删除
迭代器参数所指的那个元素
而是对迭代器参数
所指的元素之后的结点
进行操作
还有单向链表
它不支持size操作
数组是对内置数组的一个封装
它提供了更安全
更方便的使用数组的方式
跟内置数组一样
array它的对象大小也是固定的
所以在定义的时候
除了要指定
它其中元素的类型以外
还需要指定这个容器的大小
一旦定义好了
就不能动态改变这个容器大小了
所以 这个array
就是一个更好用
更方便的数组而已
各种顺序容器呢 各有长短
各具特色
我们编程序的时候
该如何去选择使用哪种容器呢
这就要看
我们程序功能的需求了
看我们程序中
需要对容器中的元素
进行什么样的操作
根据需求
我们来选择该用哪种容器
如果我们需要
执行大量的随机访问操作
而且当扩展容器的时候
只需要向容器尾部
添加新元素的时候
就应当选择向量容器
vector
如果需要少量的随机访问
需要在容器的两端插入
和删除元素
那么就应当选择双端队列容器
deque
如果我们不需要对容器
进行随机访问
但是需要在容器中间位置
插入或者删除元素
那么就应当选择列表容器list
或者单链表forward_list
如果我们需要使用数组
这个array相对于内置数组而言
它是一种更安全
更容易使用的数组类型
所以需要数组的时候
我们可以选择array
-导学
--导学
-继承的基本概念和语法
-第七章 继承与派生--继承的基本概念和语法习题
-继承方式
-第七章 继承与派生--继承方式
-基类与派生类类型转换
-第七章 继承与派生--基类与派生类类型转换
-派生类的构造和析构
--派生类的构造函数
--派生类的析构函数
--第七章 继承与派生--派生类的构造和析构
-派生类成员的标识与访问
--虚基类
-第七章 继承与派生--派生类成员的标识与访问
-小结
--小结
-综合实例
--第七章综合实例
-实验七
--实验七
-导学
--导学
-第八章 多态性--导学
-运算符重载
--运算符重载的规则
-第八章 多态性--运算符重载
-虚函数
--虚函数
--虚析构函数
--虚表与动态绑定
-第八章 多态性--虚函数
-抽象类
--抽象类
--第八章 多态性--抽象类
-override与final
-第八章 多态性--override与final
-小结
--第八章小结
-综合实例
--第八章综合实例
-实验八
--实验八
- 第八章讲义
-导学
--导学
-模板
--函数模板
--类模板
-第九章 模板与群体数据--模板
-线性群体
--线性群体的概念
-第九章 模板与群体数据--线性群体
-数组
--数组类模板
-链表
--链表类模板
-第九章 模板与群体数据--链表
-栈
--栈类模板
--栈类模板课后习题
--例9-9 栈的应用课后习题
-队列
--队列类模板
-第九章 模板与群体数据--队列
-排序
--排序概述
--插入排序
--选择排序
--交换排序
-第九章 模板与群体数据--排序
-查找
--查找
--查找课后习题
-小结
--小结
-综合实例
--综合实例
-实验九
--实验九
- 第九章讲义
-导学
--导学
-泛型程序设计及STL的结构
--STL简介
-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构
-迭代器
--迭代器
-第十章 泛型程序设计与C++标准模板库--迭代器
-容器的基本功能与分类
-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类
-顺序容器
--顺序容器的特征
--第十章 泛型程序设计与C++标准模板库--顺序容器
-关联容器
--集合
--映射
-第十章 泛型程序设计与C++标准模板库--关联容器
-函数对象
--函数对象
--函数适配器
-算法
--算法
-小结
--第十章小结
-综合实例
--综合实例
-实验十
--实验十
- 第十章讲义
-导学
--导学
-I/O流的概念及流类库结构
-第十一章 流类库与输入/输出--I/O流的概念及流类库结构
-输出流
--输出流概述
--向文本文件输出
--向二进制文件输出
--向字符串输出
-第十一章 流类库与输入/输出--输出流
-输入流
--输入流概述
--输入流应用举例
--从字符串输入
-第十一章 流类库与输入/输出--输入流
-输入/输出流
--输入/输出流
-第十一章 流类库与输入/输出--输入/输出流
-小结
--小结
-综合实例
--综合实例
-实验十一
--实验十一
- 第十一章讲义
-导学
--第12章导学
-异常处理的思想与程序实现
-第十二章 异常处理--异常处理的思想与程序实现
-异常处理中的构造与析构
-第十二章 异常处理--异常处理中的构造与析构
-标准程序库异常处理
-第十二章 异常处理--标准程序库异常处理
-小结
--第12章小结
-综合实例
--综合实例
-实验十二
--实验十二
- 第十二章讲义