当前课程知识点:C++语言程序设计进阶 > 第十章 泛型程序设计与C++标准模板库 > 顺序容器 > 顺序容器的插入迭代器与适配器
用于向容器头部、尾部或中间指定位置插入元素的迭代器
包括前插迭代器(frontinserter)、后插迭代器(backinsrter)和任意位置插入迭代器(inserter)
例:
list<int> s; back_inserter iter(s); *(iter++) = 5; //通过iter把5插入s末尾
以顺序容器为基础构建一些常用数据结构,是对顺序容器的封装
栈(stack):最先压入的元素最后被弹出
队列(queue):最先压入的元素最先被弹出
优先级队列(priority_queue):最“大”的元素最先被弹出
栈模板
template <class T, class Sequence = deque<T> > class stack;
队列模板
template <class T, class FrontInsertionSequence = deque<T> > class queue;
栈可以用任何一种顺序容器作为基础容器,而队列只允许用前插顺序容器(双端队列或列表)
s1 op s2 op可以是==、!=、<、<=、>、>=之一,它会对两个容器适配器之间的元素按字典序进行比较
s.size() 返回s的元素个数
s.empty() 返回s是否为空
s.push(t) 将元素t压入到s中
s.pop() 将一个元素从s中弹出,对于栈来说,每次弹出的是最后被压入的元素,而对于队列,每次被弹出的是最先被压入的元素
不支持迭代器,因为它们不允许对任意元素进行访问
栈的操作
s.top() 返回栈顶元素的引用
队列操作
s.front() 获得队头元素的引用
s.back() 获得队尾元素的引用
//10_7.cpp, 省略头部分 int main() { stack<char> s; string str; cin >> str; //从键盘输入一个字符串 //将字符串的每个元素顺序压入栈中 for (string::iterator iter = str.begin(); iter != str.end(); ++iter) s.push(*iter); //将栈中的元素顺序弹出并输出 while (!s.empty()) { cout << s.top(); s.pop(); } cout << endl; return 0; } 运行结果如下: congratulations snoitalutargnoc
优先级队列也像栈和队列一样支持元素的压入和弹出,但元素弹出的顺序与元素的大小有关,每次弹出的总是容器中最“大”的一个元素。
template <class T, class Sequence = vector<T> > class priority_queue;
优先级队列的基础容器必须是支持随机访问的顺序容器。
支持栈和队列的size、empty、push、pop几个成员函数,用法与栈和队列相同。
优先级队列并不支持比较操作。
与栈类似,优先级队列提供一个top函数,可以获得下一个即将被弹出元素(即最“大”的元素)的引用。
一种细胞在诞生(即上次分裂)后会在500到2000秒内分裂为两个细胞,每个细胞又按照同样的规律继续分裂。
// 10.8.cpp, 头部分省略 const int SPLIT_TIME_MIN = 500; //细胞分裂最短时间 const int SPLIT_TIME_MAX = 2000; //细胞分裂最长时间 class Cell; priority_queue<Cell> cellQueue; class Cell { //细胞类 private: static int count; //细胞总数 int id; //当前细胞编号 int time; //细胞分裂时间 public: Cell(int birth) : id(count++) { //birth为细胞诞生时间 //初始化,确定细胞分裂时间 time = birth + (rand() % (SPLIT_TIME_MAX - SPLIT_TIME_MIN))+ SPLIT_TIME_MIN; } int getId() const { return id; } //得到细胞编号 int getSplitTime() const { return time; } //得到细胞分裂时间 bool operator < (const Cell& s) const //定义“<” { return time > s.time; } void split() { //细胞分裂 Cell child1(time), child2(time); //建立两个子细胞 cout << time << "s: Cell #" << id << " splits to #" << child1.getId() << " and #" << child2.getId() << endl; cellQueue.push(child1); //将第一个子细胞压入优先级队列 cellQueue.push(child2); //将第二个子细胞压入优先级队列 } }; int Cell::count = 0; int main() { srand(static_cast<unsigned>(time(0))); int t; //模拟时间长度 cout << "Simulation time: "; cin >> t; cellQueue.push(Cell(0)); //将第一个细胞压入优先级队列 while (cellQueue.top().getSplitTime() <= t) { cellQueue.top().split(); //模拟下一个细胞的分裂 cellQueue.pop(); //将刚刚分裂的细胞弹出 } return 0; } /* 运行结果如下: Simulation time: 5000 971s: Cell #0 splits to #1 and #2 1719s: Cell #1 splits to #3 and #4 1956s: Cell #2 splits to #5 and #6 2845s: Cell #6 splits to #7 and #8 3551s: Cell #3 splits to #9 and #10 3640s: Cell #4 splits to #11 and #12 3919s: Cell #5 splits to #13 and #14 4162s: Cell #10 splits to #15 and #16 4197s: Cell #8 splits to #17 and #18 4317s: Cell #7 splits to #19 and #20 4686s: Cell #13 splits to #21 and #22 4809s: Cell #12 splits to #23 and #24 4818s: Cell #17 splits to #25 and #26 */
大家好
欢迎回来继续学习
C++语言程序设计
这一节我们来学习
顺序容器的插入迭代器
和适配器
顺序容器的插入迭代器呢
是用于像容器头部 尾部
或者中间指定位置
插入元素用的迭代器
包括前插迭代器
后插迭代器
和任意位置插入迭代器
我们看这个例子
这个例子中呢
利用这个迭代器iter
把5插入到list对象s的末尾了
实际上我们看起来
就像指针运算一样
确实
在这里呢
我们用这个list对象s
作为参数去构造了一个
后插入迭代器back_inserter
那么这个后插入迭代器呢
就可以用来将数据插入到
s的末尾
那么插入以后
它自己应该再自增
因为它准备着
可以下一次再把新的数据
继续插入到末尾
那么插入的过程呢
就像我们指针运算一样
用指针运算符
然后用赋值运算
就可以把元素
插到列表里面了
非常的方便
在顺序容器的基础上呢
我们可以配合一些适配器
构建出更多的数据结构
比如说栈和队列
它实际上呢就是
存取操作受限制的线性表
于是呢
我们就可以用适配器
在已有容器的基础之上
构成栈 队列
和优先队列
栈是一种后进先出的结构
队列是先进先出的
优先队列是最大的元素
最先被弹出
那么这个大是加引号的
什么是大呢
我们可以在使用的时候去定制
这里给出了栈模板
和队列模板
栈可以用任何一种顺序容器
作为基础容器
基础容器配合栈适配器
就构成了一个栈
而队列呢
只允许用前插顺序容器
比如说双端队列
或者列表作为基础容器
栈和队列呢
支持一些共同的操作
这里列出了
它们能够支持的共同操作
比如说进行比较
还有可以返回元素个数
返回是否空
还有将元素压到栈
或队列中去
从栈和队列中弹出一个元素
栈和队列呢
都是不支持迭代器的
因为它们不允许对任意元素
进行访问
栈和队列呢
还有各自特殊的操作
比如说返回栈顶元素的引用
top函数
队列上呢
可以使用front函数和back函数
获得队头元素的引用
获得队尾元素的引用
下面这个例子呢
就是利用栈来实现反向输出单词
程序一开始呢
定义一个栈对象
这个栈对象里面存储的元素
都是字符
也就是说
它是一个由单个字符组成的栈
然后我们从键盘读入一个字符串
接下来呢就利用
字符串这个类
它本身的迭代器
去遍历字符串的内容
那么
它初始化为字符串的开头位置
也就是字符串类的
它的begin函数返回的
就是指向头的迭代器
然后每执行一次循环呢
迭代器增1
也就是走向下一个元素
用这个迭代器跟end函数
返回的这个迭代器进行比较
就是比较它是否达到了
字符串的尾
也就是
是否全部的字符串里面的字符
都遍历完了
在每一次遍历的时候呢
都将这个iter迭代器
所指向的当前元素
压到栈里面去
用push压到栈里面
然后全部元素都遍历完了
都进到栈里头以后
然后再用这个while循环
使这个元素依次出栈
只要栈不空的情况下
就调用top
输出栈顶的元素
然后
再调用pop
将栈顶的元素移出栈去
这样直到栈空了
那么全部的元素就都出栈了
由于栈是个后进先出的结构
所以这样就达到了
将字符串里面的所有字符
反向输出的这样的效果
我们来看运行结果确实是
输入的次序跟输出的次序
是反向的
优先队列呢
也像栈和队列一样
支持元素的压入和弹出
但是元素弹出的顺序
并不与它入队的先后次序相关
只与它的元素大小相关
每次弹出的总是容器中
最大的一个元素
那怎么判别
哪个元素是最大的呢
这个可以由我们使用的时候定制
一会可以从例子中看到
优先队列的基础容器
必须是支持随机访问的顺序容器
优先队列
它也支持栈和队列的size
empty push pop几个成员函数
用法呢
与栈和队列相同
但是优先队列
它并不支持比较操作
优先队列与栈类似
也提供一个top函数
可以获得下一个
即将被弹出的元素
也就是目前队列中
最大的元素的引用
下面一个例题呢
就使用优先队列
来模拟细胞分裂的过程
这个例题非常有意思
一种细胞在诞生
也就是上次刚刚分裂后
会在500到2000秒内
分裂成两个细胞
每个细胞又按照同样的规律
继续分裂
那这个时候呢
我们来看看如何利用优先队列
来模拟这个过程
在程序的开始部分呢
首先定义了两个常量
表示细胞分裂的最短时间
和细胞分裂的最长时间
然后定义了一个优先队列的对象
准备用来存这个带分裂的细胞
然后细胞分裂的功能呢
都实现在细胞类里面
我们看这个细胞类里面
它的数据成员有细胞的总数
有当前细胞的编号
还有细胞的分裂时间
它的构造函数呢
是用一个诞生时间作为参数的
然后
当前细胞的编号id
就是当前的细胞总数
经过这样初始化以后呢
当然我们要再把细胞总数要增1
因为多了一个细胞
然后分裂时间呢
初始化为诞生时间加一个随机数
加上去的这个随机数
应该是在最小分裂时间
和最大分裂时间
之间的一个随机数
然后其他的函数包括
得到细胞编号
得到分裂时间
还有这个是非常关键的一个
定义关系运算符小于号
也就是重载小于号
那么这个小于操作呢
跟实际它的分裂时间的大小呢
它是反过来的
也就是说我们希望
分裂时间比较早的细胞
被定义为比较大的
分裂时间比较晚的细胞
被定义为比较小的
这样的话
将来在优先队列中
就能够自动
每次弹出那个分裂时间
最早的细胞
下面一个函数呢
是进行细胞分裂
进行细胞分裂的时候呢
我们需要构造两个子细胞
这两个子细胞的
构造时候的初始值
也就是诞生时间
就是当前这个细胞的分裂时间
然后输出细胞分裂的这个信息
接下来将新诞生的两个细胞呢
再压入到优先队列中去
这是它类体里面的内容
那么在类外呢
对这个静态成员进行了定义
和初始化
看主函数中呢
首先要为后面的这个rand
随机数函数
准备随机数种子
那么这个随机数种子呢
我们是通过调用time
去取系统时间来得到的
这样的种子呢
就保证我们每次运行的时候
它是不同的
所以每次运行的时候呢
这个随机数序列
产生出来就是不同的
接下来呢
要输入一个模拟的时间长度
也就是说
我们要在多长时间范围内
来观察这个细胞分裂过程
好 接下来呢
就要准备这个细胞分裂过程了
首先将第一个细胞
压入到这个队列里面去
压入一个细胞
然后这个while循环呢
用什么来控制循环结束呢
一直在比较
一直在比较
当前马上要弹出来的
也就是队列最开头的
最大的那个细胞元素
它的分裂时间
是不是小于等于t
也就是是不是在我们
打算观察的这个时间范围之内
只要在这个时间范围之内
我们就将队列最开头的这个细胞
进行分裂
调用split进行分裂
分裂完了以后呢
就要把队列最头上这个细胞
因为它已经分裂过了
就要把它移出这个队列 pop
始终进行不断地循环
不断地模拟细胞的分裂
直到我们设定的观察时间到了
那么这个循环就结束
看这是某一次运行的时候
产生的结果
-导学
--导学
-继承的基本概念和语法
-第七章 继承与派生--继承的基本概念和语法习题
-继承方式
-第七章 继承与派生--继承方式
-基类与派生类类型转换
-第七章 继承与派生--基类与派生类类型转换
-派生类的构造和析构
--派生类的构造函数
--派生类的析构函数
--第七章 继承与派生--派生类的构造和析构
-派生类成员的标识与访问
--虚基类
-第七章 继承与派生--派生类成员的标识与访问
-小结
--小结
-综合实例
--第七章综合实例
-实验七
--实验七
-导学
--导学
-第八章 多态性--导学
-运算符重载
--运算符重载的规则
-第八章 多态性--运算符重载
-虚函数
--虚函数
--虚析构函数
--虚表与动态绑定
-第八章 多态性--虚函数
-抽象类
--抽象类
--第八章 多态性--抽象类
-override与final
-第八章 多态性--override与final
-小结
--第八章小结
-综合实例
--第八章综合实例
-实验八
--实验八
- 第八章讲义
-导学
--导学
-模板
--函数模板
--类模板
-第九章 模板与群体数据--模板
-线性群体
--线性群体的概念
-第九章 模板与群体数据--线性群体
-数组
--数组类模板
-链表
--链表类模板
-第九章 模板与群体数据--链表
-栈
--栈类模板
--栈类模板课后习题
--例9-9 栈的应用课后习题
-队列
--队列类模板
-第九章 模板与群体数据--队列
-排序
--排序概述
--插入排序
--选择排序
--交换排序
-第九章 模板与群体数据--排序
-查找
--查找
--查找课后习题
-小结
--小结
-综合实例
--综合实例
-实验九
--实验九
- 第九章讲义
-导学
--导学
-泛型程序设计及STL的结构
--STL简介
-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构
-迭代器
--迭代器
-第十章 泛型程序设计与C++标准模板库--迭代器
-容器的基本功能与分类
-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类
-顺序容器
--顺序容器的特征
--第十章 泛型程序设计与C++标准模板库--顺序容器
-关联容器
--集合
--映射
-第十章 泛型程序设计与C++标准模板库--关联容器
-函数对象
--函数对象
--函数适配器
-算法
--算法
-小结
--第十章小结
-综合实例
--综合实例
-实验十
--实验十
- 第十章讲义
-导学
--导学
-I/O流的概念及流类库结构
-第十一章 流类库与输入/输出--I/O流的概念及流类库结构
-输出流
--输出流概述
--向文本文件输出
--向二进制文件输出
--向字符串输出
-第十一章 流类库与输入/输出--输出流
-输入流
--输入流概述
--输入流应用举例
--从字符串输入
-第十一章 流类库与输入/输出--输入流
-输入/输出流
--输入/输出流
-第十一章 流类库与输入/输出--输入/输出流
-小结
--小结
-综合实例
--综合实例
-实验十一
--实验十一
- 第十一章讲义
-导学
--第12章导学
-异常处理的思想与程序实现
-第十二章 异常处理--异常处理的思想与程序实现
-异常处理中的构造与析构
-第十二章 异常处理--异常处理中的构造与析构
-标准程序库异常处理
-第十二章 异常处理--标准程序库异常处理
-小结
--第12章小结
-综合实例
--综合实例
-实验十二
--实验十二
- 第十二章讲义