通用编程是c支持的另一种编程模式。 与OPP的目标相同。 使重用代码和抽象通用概念的技术更简单。 OPP强调编程的数据面,强调通用编程独立于特定的数据类型。 OPP是一个管理大型项目的工具,通用编程提供了一些执行数据排序、链表联接等常见任务的工具。
STL库1通用编程2 STL标准模板库2.1 STL库的基本组件2.1.1 STL基本组件----容器2.1.2 STL基本组件----小程序2.1
1通用编程
通用编程是指尽量使编程通用。 STL标准库是通用编程的一个很好的例子。
编制不依赖于特定数据类型的程序
将算法从特定的数据结构中抽象出来,使之通用
c类模板为通用编程奠定了重要基础。
两个术语:
在STL库中,许多模板实现都是在概念上命名模板参数,在概念上创建模板参数名称:
为概念命名,并将该名称用作模板参数名称。
eg :
模板类可解析
语音识别(sortable a [ ],int n );
2 STL标准模板库标准模板库STL(Standardtemplatelibrary )定义了一系列概念体系,为通用编程提供了逻辑基础。
STL中各级模板、函数模板的参数均由该体系中的概念规定。
使用STL模板时,类型参数可以是c标准库中已经存在的类型,也可以是自定义类型---只要这些类型是要求的概念模板。
2.1 STL库的基本组件容器(container ) )
迭代器(迭代器)迭代器)
函数对象(function对象)
算法(algorithms ) )
关系:
迭代器是算法和容器之间的桥梁:
将迭代器作为算法的参数,通过迭代器访问容器。 不是将容器直接作为算法的参数
使用函数对象作为算法的参数,而不是作为执行函数的运算。
您可以使用STL中提供的或自定义的迭代器和函数对象,根据STL算法组合各种功能。
2.1.1 STL基本组件----容器收纳,含一组元素对象;
基本容器类模板
顺控容器:
阵列、矢量、deque、前向_列表、列表链表
(有序)相关容器:
set (集合)、multiset (多重)、map (多重)多重映射
无序(相关容器:
unordered_set、unordered_multiset、
unordered_map、unordered_multimap
这些容器类的模板是不够的,还需要堆栈和队列。 实际上,堆栈和队列是访问操作受限制的路线表,STL库中的处理过程也允许将适配器附加到基本容器
堆叠
队列(队列)队列
priority_queue (优先队列) ) ) ) ) 0
2.1.2 STL基本组件----提供按顺序访问迭代器容器中的每个元素的方法;
可以使用运算符获取指向以下元素的迭代器:
可以使用*运算符访问迭代器指向的元素。 如果元素类型是类或结构,也可以使用-访问成员。
迭代器是泛化的指针(指针本身是迭代器);
要使用独立于STL容器的迭代器,必须包含头文件迭代器。
2.1.3 STL基本组件----函数对象一个运行类似于函数的对象。 对此可以像调用函数一样调用。
函数对象是泛化的函数。 常规函数和(重载运算符的类中的对象可以用作函数对象
使用STL的函数对象必须包含头文件functional
2.1.4 STL基本组件----算法可广泛用于不同对象和内置数据类型。
STL有70多种算法。 排序、清除、计数、比较、转换、替换、容器管理等
必须包括algorithm
3迭代器充当算法和容器之间的桥梁。 因为有了这个桥梁,算法和容器独立,彼此更通用。
迭代器是算法和容器之间的桥梁:
迭代器用于访问容器中的元素;
算法不是直接操作容器中的数据,而是由迭代器间接操作
迭代器是算法和容器之间的桥梁:
添加无阴影新算法
响容器的实现· 增加新的容器,原有的算法也能实现
输入流迭代器和输出流迭代器:
◇ 输入流迭代器
istream_iterator
·以输入流(如cin)为参数构造
·可用*(p++)获得下一个输入元素
◇ 输出流迭代器
ostream_iterator
·构造时需提供输出流(如cout)
·可用 *(p++)=x 将x输出到输出流
◇二者都属于适配器
·适配器是用来为已有对象提供新的接口的对象
·输入流适配器和输出流适配器为流对象提供了迭代器 的接口
迭代器分类:
迭代器支持的操作:
◇ 迭代器是泛化的指针,提供了类似指针的操作(诸如 ++ * -> 运算符)
◇ 输入迭代器
· 可以用来从序列中读取数据,如输入流迭代器
◇ 输出流迭代器
· 允许向序列中写入数据,如输出流迭代器
◇ 前向迭代器
· 既是输入流迭代器又是输出流迭代器,并且可以对序列进行单向的遍历
◇ 双向迭代器
· 与前向迭代器相似,但是在两个方向上都可以对数据遍历
◇ 随机访问迭代器
· 也是双向迭代器,但是能在序列中的任意两个位置之间进行跳转,如指针、使用vector的begin()、end()函数得到的迭代器。
用两个迭代器表示一个区间:
◇ 两个迭代器表示一个区间:[p1,p2)
◇STL算法以迭代器的区间作为输入,传递输入数据
◇合法区间
· p1经过n次(n>0)自增(++)操作后满足p1==p2
◇ 区间包含p1,但不包含p2
◇ 容器类是容纳、包含一组元素或元素集合的对象的对象
◇ 基于容器中元素的组织方式分类:顺序容器、关联容器
◇ 按照与容器所关联的迭代器类型分类:可逆容器、随机访问容器
◇ 顺序容器:
·array(数组)、vector(向量)、deque(双端队列)、forward_list(单链表)、list(链表)
◇ (有序)关联容器:
·set(集合)、multiset(多重集合)、map(映射)、multimap(多重映射)
◇ (无序)关联容器:
·unordered_set(无序集合)、unordered_multiset(无序多重集合)、
·unordered_map(无序映射)、unordered_multimap(无序多重映射)
◇容器的通用功能
· 用默认构造函数构造空容器
· 支持关系运算符:== != < <= > >=
· begin() end() : 获得容器首位迭代器
· clear() : 将容器清零
· empty() : 判断容器是否为空
· size() : 得到容器元素个数
· s1.swap(s2) : 将s1和s2两容器内容交换
◇相关数据类型(S表示容器类型)
· S::iterator : 指向容器元素的迭代器类型
· S::const_iterator : 常迭代器类型
对可逆容器的访问
◇ STL为每个可逆容器都提供了逆向迭代器,逆向迭代器可以通过下面的成员函数得到:
· rbegin() : 指向容器尾逆向迭代器
· rand() : 指向容器首的逆向迭代器
◇ 逆向迭代器的类型名的表示方式如下:
· S::reverse_iterator : 逆向迭代器类型
· S::const_reverse_iterator : 逆向常迭代器类型
随机访问容器
◇ 支持对容器的元素进行随机访问
s[n] : 获得容器s的第n个元素
◇ STL中的顺序容器
· 向量(vector)
· 双端队列(deque)
· 列表(list)
· 单向列表(forward_list)
· 数组(array)
以上顺序容器在逻辑上可以看做一个长度可扩展的数组
◇ 元素线性排列,可以随时在指定位置插入元素和删除元素
◇ 必须符合Assignable这一概念(即具有公有的复制构造函数并可以使用 = 赋值)。
◇ array对象的大小固定,forward_list有特殊的添加和删除操作。
顺序容器的接口(不包含单向列表(forward_list)和数组(array))
◇ 构造函数
◇ 赋值函数
· insert,push_front(只对list和deque),push_back,emplace,emplace_front
◇ 删除函数
· erase,clear,pop_front(只对list和deque),pop_back,emplace_back
◇ 首位元素的直接访问
· front,back
◇ 改变大小
· resize
◇ 用于向容器的头部,尾部或者中间指定位置插入元素的迭代器
◇ 包括前插迭代器(front_inserter)、后插迭代器(back_inserter)和任意位置插入迭代器(insterer)
eg:
lists;
back_inserter iter(s);
*(iter++)=5; //通过iter把5插入s末尾
顺序容器的适配器
◇ 以顺序容器尾基础构建一些常用的数据结构,是对顺序容器的封装
· 栈(stack):最先压入的元素最后被弹出
· 队列(queue):最先压入的元素最先被弹出
· 优先级队列(priority_queue):最“大”元素最先被弹出
栈模板和队列模板
◇ 栈模板
template< class T ,class Sequence = deque > class stack;
◇ 队列模板
template< class T ,class FrontInsertionSequence= deque > class queue;
◇ 栈可以用任何一种顺序容器作为基础容器,而队列只允许前插顺序容器(双端队列或列表)
栈和队列共同支持的操作
◇ s1 op s2 op可以是== != < <= > >=
◇ s.size() 返回s元素个数
◇ s.empty() 返回s是否为空
◇ s.push(t) 将元素t压入
◇ s.pop 讲一个元素弹出
◇ 都不支持迭代器,因为不允许任意元素的访问
栈的操作:s.top() 返回栈顶元素的引用
队列操作:s.front() s.back() 获得对首/尾的引用
◇参考:《C++语言程序设计 郑莉》