学堂在线C++程序设计第十二章学习笔记

泛型程序设计和标准模板库

泛型及STL

泛型程序设计

编写不依赖于具体数据类型的程序
将算法从特定的数据结构中抽象出来成为通用的
C++的模板为泛型程序设计奠定了关键的基础

术语：概念

可以比较大小的数据类型记作Comparable
具有公有的复制函数并可以用 = 赋值的记作Assignable
将可以比较大小并且具有公有复制函数可以用 = 赋值的记作Sortable

对于两个不同的概念A，B,如果A所需求的所有功能也是B所需求的，那么B是A的子概念，比如，Sortable是 Comparable 的子概念，也是 Assignable的子概念

术语：模型

符合一个概念的数据类型称为该概念的模型
比如 int 型是 Comparable的模型
静态数组不是 Assignable的模型

STL

标准模板库STL定义了一套概念体系，为泛型程序设计提供了逻辑基础
STL中的各个类模板，函数模板的参数都是用这个体系中的概念来规定的
使用STL模板时，类型参数既可以是C++标准库中已有的类型，也可以是自定义的类型–只要这些类型是所要求的概念的模型

STL基本组件

容器（container）：容纳，包含一组元素的对象
- 顺序容器：
  array,vector,双端队列，单链表，列表
- 有序容器：
  集合，多重集合，map,多重映射
- 无序关联容器
  无序集合，无序多重集合，无序映射，无序多重映射
迭代器（iterator）
- 提供了顺序访问容器中每个元素的方法
- 可以使用 ++ 运算符来获得指向下一个元素的迭代器
- 可以使用 * 运算符访问迭代器指向的元素，如果元素类型是类或结构体，还可以使用 -> 运算符直接访问成员
- 有些迭代器还支持通过 – 运算符获得指向上一个元素的迭代器
- 迭代器是泛化的指针：指针也具有同样的特性，因此指针本身就是一种迭代器
- 使用独立于STL容器的迭代器，需要包含头文件
函数对象（function object）
算法（algorithms）

迭代器是算法和容器的桥梁

将迭代器作为算法的参数，通过迭代器来访问容器而不是把容器直接作为算法参数
将函数对象作为算法参数而不是将函数所执行的运算作为算法的一部分。
使用STL中提供的或自定义的迭代器和函数对象，配合STL的算法，可以组合出各种各样的功能

容器适配器

栈
队列

迭代器

迭代器是算法和容器的桥梁

迭代器用作访问容器中的元素
算法不直接操作容器中的数据，而是通过迭代器间接操作

算法和容器独立

增加新的算法，无需影响容器的实现
增加新的容器，原有的算法也可以适用

输入流迭代器

istream_iterator
以输入流如 cin 为参数构造
可用 *(p++) 获得下一个输入的元素

输出流迭代器

ostream_iterator
构造时需要提供输出流如 cout
可用 (*p++) = x 将 x 输出到输出流

二者都属于适配器

适配器是用来为已有对象提供新的接口的对象
输入流适配器和输出流适配器为流对象提供了迭代器的接口

容器的基本功能和分类

容器类是容纳，包含一组元素或元素集合的对象
基于容器中元素的组织方式分类：顺序容器，关联容器
按照与容器所关联的迭代器类型分类：可逆容器，随机访问容器

顺序容器

顺序容器的基本功能

STL中的顺序容器
- 向量
- 双端队列(deque)
- 列表(list)
- 单向链表(forward_list)
- 数组(array)
元素线性排列，可以随时在指定位置插入元素和删除元素
必须符合 Assignable 这一概念（具有共有的复制构造函数并可以用 ‘=’ 赋值）
array 对象的大小固定，forward_list有特殊的添加和删除操作

顺序容器的接口（不包含单向链表和数组）

构造函数
赋值函数：assign
插入函数: insert, push_front(只对list和deque)，push_back, emplace, emplace_front
删除函数：erase, clear, pop_front, pop_back, emplace_back
首尾元素的直接访问：front, back
改变大小：resize

顺序容器的特征

向量

特点
- 一个可以扩展的动态数组
- 随机访问，在尾部插入或删除元素块
- 在中间或头部插入或删除元素慢
容量
- 容量：实际分配空间的大小
- s.capacity: 返回当前容量
- s.reserve(n): 容量小于n，则对s进行扩展，使其容量至少为n

双端队列

特点
- 在两端插入或删除元素快
- 在中间插入或删除元素慢
- 随机访问较快，但比向量慢

列表

特点
- 在任意位置插入和删除元素都很快
- 不支持随机访问
接合操作（splice）
- s.splice(p, s2, q1, q2): 将s2中[q1,q2)移动到s1中p所指向元素之前

顺序容器的插入迭代器与适配器

顺序容器的插入迭代器

用于向容器头部，尾部或中间指定位置插入元素的迭代器
包括前插迭代器（front_inserter），后插迭代器（back_inserter）和任意位置插入迭代器（inserter）
例子：
list s;
back_iserter iter(s);
*(iter++) = 5; //通过iter把5插入s末尾

顺序容器的适配器

以顺序容器为基础构建一些常用数据结构，是对顺序容器的封装
- 栈
- 队列
- 优先级队列：最 大 的先弹出

栈和队列模板

栈模板
template <class T, class Sequence = deque> class stack;
队列模板
template <class T,class FrontInsertionSequence = deque> class queue;
栈可以用任何一种顺序容器作为基础容器，而队列只允许用前插顺序容器（双端队列或列表）

栈和队列共同支持的操作

比较
返回元素个数
empty
push
pop
不支持迭代器，因为不允许对任意元素访问

栈和队列不同的操作

栈的操作
s.top 返回栈顶元素的引用
队列操作
s.front 获得队头元素的引用
s.back 获得队尾元素的引用

优先级队列

优先级队列也像栈和队列一样支持元素的压入和弹出，但元素弹出顺序和元素大小有关，每次弹出最大的
template <class T, class Sequence = Vector> class priority_queue
优先级队列的基础容器必须是支持随机访问的顺序容器
支持栈和队列的size,empty, push, pop几个函数
优先级队列并不支持比较操作
与栈类似，优先级队列提供一个 top 函数，可以获得下一个即将被弹出元素的引用

关联容器

分类和基本功能

关联容器的特点

每个关联容器都有一个key
可以根据key高效查找元素

接口

插入insert
删除 erase
查找 find
定界 lower_bound,upper_bound,equal_bound
计数 count

集合

集合用来存储一组无重复的数据。用于集合的元素本身是有序的，可以高效查找元素，也可以方便的得到指定大小范围的元素在容器中所处的区间

映射

映射和集合的主要区别

集合的元素类型是key本身
映射的元素类型是key,value二元组
在集合中按照key查找一个元素时，一般只是确定这个元素是否存在。
映射中按照key查找时，除了能确定是否存在外，还可以得到相应的附加数据

多重集合和多重映射

多重集合允许有重复元素的集合，多重映射允许一个key对应多个value
多重集合与集合，多重映射与映射的用法差不多

函数对象

一个行为类似函数的对象
可以没有参数，也可以带有若干参数
其功能是获取值，或者改变操作状态
普通函数就是函数对象
重载了 “()” 运算符的类的实例是函数对象

函数适配器

绑定适配器
- bind1st, bind2nd: 将n元函数对象的指定参数绑定为一个常数，得到n-1元函数对象
组合适配器
- not1,not2: 将指定谓词的结果取反
函数指针适配器
- ptr_fun: 将一般函数指针转换为函数对象，使之能够作为其他函数适配器的输入
- 在进行参数绑定或其他转换的时候，通常需要函数对象的类型信息
成员函数适配器:ptr_fun,ptr_fun_ref
- 对成员函数指针使用，把n元成员函数适配为n + 1元函数对象，该函数对象的第一个参数为调用该成员函数时的目的对象
- 也就是 object->method() 变成 method(object)
- 将 object->method(arg1) 变成 method(object, arg1)

STL算法

本身是一种函数模板

通过迭代器获得输入数据
通过函数对象对数据进行处理
通过迭代器将结果输出

STL算法是通用的，独立于具体的数据类型，容器类型

分类

不可变序列算法
- 不直接修改所操作的容器内容的算法
- 用于查找指定元素，比较是否相等，对元素进行计数等
可变序列算法
- 可修改所操作的容器对象的算法
- 包括复制，删除，替换，洗牌及生成一个序列的算法
排序和搜索算法
- 对序列排序
- 搜索
- 堆算法
数值算法
- 求和，求差，积等