C++泛化程序设计

# 泛型程序设计

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

# 概念

• 在 C++ STL 库中用 "概念" 来界定具备一定功能的数据类型
  • 将 “可以比大小的所有数据类型 (有比较运算符)“这一概念记为 Comparable
  • 将” 具有共有的复制构造函数并可以用‘=’赋值的数据类型 “这一概念记为 Assignable
  • 将 “可以比大小，具有公有的复制构造函数并可以用’=‘赋值的所有数据类型” 这个概念记作 Sortable
• 对于两个不同的概念 A 和 B，如果概念 A 所需求的所有功能也是概念 B 所需求的功能，那么就说概念 B 是概念 A 的子概念
  • sortable 是 Comparable 的子概念，也是 Assignable 的子概念

# 模型

• (model): 符合一个概念的数据类型称为该概念的模型
  • int 是 Comparable 概念的模型
  • 静态数组类型不是 Assignable 概念的模型 (无法用 "=" 给整个静态数组赋值 ")

# 用概念做模型参数名

• 为概念赋予一个名称，并使用该名称作为模版参数名

// 表示 insertionSort 这样一个函数模版的原型

template <class Sortable>

void insertSort(Sortable a[],int n);

# STL

• STL : 标准模板库 (Standard Template Library 简称 STL ) 提供了一些非常常用的数据结构和算法， STL 定义了一套概念体系，为泛化程序设计提供了逻辑基础
• STL 中的各个类模版，函数模版的参数都是用这个体系概念来规定的
• 使用 STL 模版，类型参数既可以是 C++标准库 中已有的类型，也可以是自己定义的类型 - 只要这些类型是所要求概念的模型

# STL 的基本组件

• 容器 (container)
• 迭代器 (iterator)
• 函数对象 (function object)
• 算法 (algorithms)

# 迭代器

• Iterators (迭代器) 是算法和容器的桥梁

  将迭代器作为算法的参数，通过迭代器来访问容器而不是把容器直接作为算法的参数

• 将函数对象作为算法的参数而不是将函数所执行的运算作为算法的一部分
• 使用 STL 中提供的或自定义的迭代器和函数对象，配合 STL 算法，可以组合出各种各样的功能
• 迭代器泛化的指针
• 提供了顺序访问容器中每个元素的方法
• 可以使用 "++" 运算符来获得指向下一个元素的迭代器
• 可以使用 "*" 运算符访问一个迭代器所指向的元素，如果元素类型是类或结构体，还可以使用 "->" 运算符来直接访问该元素的一个成员
• 有些迭代器还支持通过 "--" 运算符获得指向上一个元素的迭代器
• 有些迭代器是泛化的指针：指针也具有同样的特性，因此指针本身就是一种迭代器
• 使用独立于 STL 容器的迭代器，需要包含头文件 <iterator>

# 容器

• 容纳，包含一组元素的对象
• 基本容器类模版
  • 顺序容器

  array (数组), vector (向量), deque (双端队列), forward_list (单链表), list (列表)

  • (有序) 关联容器

  set (集合), multiset (多重集合), map (映射), multimap (多重 (可重复) 映射)

  • 无序关联容器

  unordered_set (无序集合), unordered_multiset (无序多重集合)
  unordered_map (无序映射), unorder_multimap (无序多重映射)

• 容器适配器

stack (栈), queue (队列), priority_queue (优先队列)

• 使用容器，需要包含对应的头文件

# 函数对象

• 一个行为类似函数的对象，对它可以像调用函数一样调用
• 函数对象时泛化的函数：任何普通的函数和任何重载了 “()” 运算符的类的对象都可以作为函数对象使用
• 使用 STL 的函数对象，需要包含头文件 <functional>

# transform 算法

• transform 算法 遍历first和last两个迭代器所指向的元素 ，
• 将每个元素的值作为函数对象 op 的参数
• 将 op 的返回值通过迭代器 result 顺序输出
• 遍历完成后 result迭代器 指向的是输出的最后一个元素的下一个位置，transform 会将迭代器返回

template <class Inputlterator,class Outputlterator,class UnaryFunction>

Outputlterator transform(InputLterator first,Inputlterator,Outputlterator result,UnaryFunction op)

{

	for(;first!=last;++first,++result)

	{

		*result = op(*first);

	}

	return result;

}

# 算法 (algorithms)

• STL 包含 70 多种算法
  • 例如：排序算法，消除算法，计数算法，变换算法，置换算法和容器管理等
• 可以广泛用于不同的对象和内置的数据类型
• 使用 STL 算法，需要包含头文件 <algorithm>

# 例：从标准输入读入几个整数，存入向量容器，输出相反数

#include <iostream>

#include <vector>		// 向量

#include <iterator>  // 迭代器

#include <algorithm>  // 算法

#include <functional> // 函数对象

using namespace std;

int main(void)

{

	const int N = 5;

	vector<int> s(N);  // 容器

	for (int i = 0; i < N; i++)

	{

		cin >> s[i];

	}

	transform(s.begin(), s.end(), ostream_iterator<int>(cout, "## "), negate<int>());  // 算法，negate 取相反数

	cout << endl;

	return 0;

}

# 迭代器

• 迭代器是算法和容器的桥梁
  • 迭代器用作访问容器中的元素
  • 算法不直接操作容器中的数据，而是通过 迭代器 间接操作
• 算法和容器独立
  • 添加新的算法，无需影响容器的实现
  • 添加新的容器，原有的算法也能适用

# 输入迭代器和输出迭代器

• 输入迭代器
  • istream_iterator<T>
  • 以输入流 (如 cin 为参数构造)
  • 可用 *(p++) 获取下一个输入的元素
• 输出流迭代器
  • ostream_iterator<T>
  • 构造时需要提供输出流 (如 cout )
  • 可用 (*p++)=x 将 x 输出到输出流
• 二者都属于适配器
  • 适配器是用来为已有对象提供新的接口的对象
  • 输入流适配器和输出流适配器为流对象提供了迭代器的接口

// 从标准输入读入几个实数，分别输出它们的平方

#include <iostream>

#include <iterator>

#include <algorithm>

using namespace std;

// 求平方的函数

double square(double x)

{

	return x * x;

}

int main(void)

{

	// 从标准输入读入若干个实数，分别将它们的平方输出

	transform(istream_iterator<double>(cin), istream_iterator<double>(), ostream_iterator<double>(cout, "\t"), square);

	// 头，尾，写入结果，函数处理

	// 头：输入流迭代器，double， 关联到 cin

	// 尾没有构造函数，不给为空，---- 指向输入流结束

	// 写入结果:cout  "\t" 两个输出项之间的分隔符

	// 函数处理:square

	cout << endl;

}

# 迭代器的区别

• 两个迭代器表示一个区间:[ p1,p2 ) 包含 p1 不包含 p2
• STL 算法常以 迭代器的区间 作为输入，传递输入数据
• 合法的区间
  • p1 经过 n 次 (n>0) 自增 (++) 操作后满足 p1==p2 ;
• 区间包含 p1 ，但不包含 p2

# 综合运用迭代器示例

#include <algorithm>

#include <iterator>

#include <vector>

#include <iostream>

using namespace std;

// 将来自输入 迭代器的 n 个 T 类型数值排序，将结果 通过输出迭代器 result 输出

template <class T,class InputIterator,class OutputIterator>

void mySort(InputIterator first,InputIterator last,OutputIterator result)

{

	// 通过输入迭代器将输入数据存入向量容器 s 中

	vector<T> s;

	for (; first != last; ++first)

		//push_back 依次插入元素，直到结束

		s.push_back(*first); // 将数据放入向量容器 s 中

	// 对 s 进行排序，sort 函数的参数必须是随机访问迭代器

	sort(s.begin(), s.end()); 

	copy(s.begin(), s.end(), result);// 将 s 序列通过输出迭代器输出

}

int main(void)

{

	// 将 s 数组的内容排序后输出

	double a[5] = { 1.2,2.4,0.8,3.3,3.2 };

	mySort<double>(a, a + 5, ostream_iterator<double>(cout, " "));

	cout << endl;

	// 从标准输入读入若干整数，ctrl+z 结束输入

	mySort<int>(istream_iterator<int>(cin), istream_iterator<int>(), ostream_iterator<int>(cout, " "));

	cout << endl;

	return 0;

}

# 迭代器的辅助函数

• advance(p,n)
  • 对 p 执行 n 次自增操作
• distance(first,last)
  • 计算两个迭代器 first 和 last 的距离，即对 first 执行多少次 "++" 操作后，能使 first==last

# 容器的基本功能与分类

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

# 容器的分类

# 容器的通用功能

• 容器的通用功能
  • 用默认构造函数构造空容器
  • 支持关系运算符: ==,!=,<,<=,>,>=
  • begin (),end (): 获得容器首尾常迭代器
  • cbegin(),cend() : 获取容器首，尾常迭代器，不需要改变容器时更安全
  • clear (): 将容器清空
  • empty (): 判断容器是否为空
  • size (): 得到容器元素个数
  • s1.swap(s2) : 将 s1 和 s2 两个容器内容交换
• 相关数据类型
  • S::iterator ：指向容器元素的迭代器类型
  • S::const_iterator ：常迭代器类型

# 对可逆容器的访问

• STL 为每个可逆容器都提供了逆向迭代器
  • rbegin() : 指向容器尾的逆向迭代器
  • rend() : 指向容器首的逆向迭代器
• 逆向迭代器的类型名的表示方式如下 (S 表示容器类型)
  • S::reverse_iterator : 逆向迭代器类型
  • S::const_reverse_iterator : 逆向常迭代器类型

# 顺序容器

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

# 顺序容器的基本功能

• 默认构造函数
• S s(n,t) ; 构造一个由 n 个 t 元素构成的容器实例 s
• S s(n) ; 构造一个有 n 个元素的容器实例，每个元素都是 T()
• S s(q1,q2) ; 使用将 [q1,q2) 区间内的数据作为 s 的元素构造 s

# 赋值函数

assign 将指定的元素赋给顺序容器，顺序容器中原先的元素会被清除，赋值函数的三种形式 是与构造函数一一对应的

• s.assign(n,t) 赋值后的容器由 n 个 t 元素构成
• s.assign(n) , 赋值后的容器有 n 个元素的容器实例 s，每个元素都是 T ()
• s.assign(q1,q2) 赋值后的容器的元素为 [q1,q2) 区间内的数据

# 插入函数

可以一次插入一个或多个指定元素，也可以将一个迭代器区间中的序列插入，通过一个指定当前容器元素的迭代器来指示插入位置，返回值为指向新插入的元素中第一个元素的迭代器

• s.insert(p1,t) 在 s 容器中 p1 所指向的位置插入一个 t 的复制，插入后的元素夹在原 p1 和 p1-1 所指向的元素之间
• s.insert(p1,n,t) 在 s 容器中 p1 所指向的位置插入 n 个 t 的复制，插入后的元素夹在原 p1 和 p1-1 所指向的元素之间
• s.insert(p1,q1,q2) 将 [q1,q2) 区间的元素顺序复制插入到 s 容器 p1 位置处，新元素夹在 p1 和 p1-1 所指向的元素之间
• s.emplace(p1,args) 将参数 args 传递给 T 的构造函数构造新元素 t，在 s 容器中 p1 所指向的位置插入该元素，插入后的元素夹在原 p1 和 p1-1 所指向的元素之间

# 其它函数

• erase
• clear
• pop_front (只对 list 和 deque )
• pop_back
• 首尾元素的直接访问
  • front
  • back
• 改变大小
  • resize

# 顺序容器的基本操作

#include <iostream>

#include <list>

#include <deque>

using namespace std;

// 输出指定顺序容器的元素

template <class T>

// 第一个输出字符，第二个传入容器类型常引用

void  printContainer(const char* msg, const T& s)

{

	cout << msg << ":";

	copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));

	cout << endl;

}

int main(void)

{

	// 从标准输入读入 10 个整数，将让门分别从 s 的头部加入

	deque<int> s;

	for (int i = 0; i < 10; i++)

	{

		int x;

		cin >> x;

		s.push_back(x);

		// 将 x 的数据存入到 s 当中，每次都加入到开头位置

	}

	printContainer("deque at first", s);

	// 用 s 容器的内容的逆序构造列表容器

	list<int> l(s.rbegin(), s.rend());

	printContainer("list at first", l);

	// 将列表容器 l 的每相邻顺序颠倒 

	list<int>::iterator iter = l.begin();

	while (iter != l.end()) // 遍历 l

	{

		int v = *iter; // 取

		iter = l.erase(iter); // 删除该元素

		l.insert(++iter, v);

	}

	printContainer("list at list", l);

	// 用列表容器 l 的内容给 s 赋值，将 s 输出

	s.assign(l.begin(), l.end());

	printContainer("deque at last", s);

	return 0;

}

/*

0 9 8 6 4 3 2 1 5 4

deque at first:0 9 8 6 4 3 2 1 5 4

list at first:4 5 1 2 3 4 6 8 9 0

list at list:5 4 2 1 4 3 8 6 0 9

deque at last:5 4 2 1 4 3 8 6 0 9

*/

# 顺序容器的特点

# 向量 ( vector )

• 特点:
  • 一个可以扩展的 动态数组
  • 随机访问，在尾部插入或删除元素快
  • 在中间或头部插入或 删除元素慢
• 向量的容量
  • 容量 (capacity): 实际分配空间的大小
  • s.capacity() ：返回当前容量
  • s.reserve() ：若容量 小于 n 则对 s 进行扩展，使其容量至少为 n
  • s.shrink_to_fit() : 回收未使用的元素空间，即 size 和 capacity 函数返回值相等

# 双端队列 ( deque )

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

#include <iostream>

#include <vector>

#include <deque>

#include <algorithm>

using namespace std;

// 通过双端队列实现奇偶排序

// 先按照从大到 小顺序输出计数，再按照从小到 大顺序输出偶数

int main(void)

{

	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.push_back(*iter); // 偶数放到 s2 尾部

		}

		else

		{

			s2.push_front(*iter); // 奇数放到 s2 首部

		}

	}

	// 将 s2 的结果输出

	copy(s2.begin(), s2.end(), ostream_iterator<int>(cout, " "));

	cout << endl;

	return 0;

}

# 列表

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

#include <iostream>

#include <string>

#include <list>

#include <algorithm>

using namespace std;

int main(void)

{

	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 第三个元素

	list<string>::iterator iter2 = s2.begin(); //iter2 指向 s2 首

	++iter2; //iter2 前进一个元素，它将指向 s2 的第二个元素

	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;

}

/*

helen lucy David Levin Susan

Bob Mike Alice

*/

# 单向链表 ( forward_list )

• 单向链表每个结点只有指向下个结点的指针，没有简单的方法来获取一个节点的前驱
• 未定义insert,emplace和erase操作 ，而定义了 insert_after,emplace_after 和 erase_after 操作，其参数与 list 的 insert， emmplace 和 erase 相同，但并不是插入或删除迭代器 p1 所指向的元素，而是对 p1 所只元素之后的结点进行操作
• 不支持 size 操作

# 数组 (array)

• array 是对内置数组的封装，提供了更安全，更方便的使用数组的方式
• array 的对象的 大小是固定 的，定义时除了需要指定元素类型，还需要指定容器大小
• 不能动态地改变容器大小

# 顺序容器的比较

• 如果需要执行大量的随机访问操作，而且当扩展容器时只需要向容器尾部加入新的元素，就应当选择向量容器 vector
• 如果需要少量的随机访问操作，需要 在容器两端插入或删除操作，则应当选择双端队列容器 deque ;
• 如果不需要对容器进行随机访问，但是需要在中间位置插入或删除元素，就应当选择列表容器 list 或 forward_list
• 如果需要数组，array 相对于内置数组类型而言，是一种更安全，更容易使用的数组类型

# 顺序容器的插入迭代器

• 用于向容器头部，尾部或中间指定位置插入元素的迭代器
• 包括前插迭代器 ( front_inserter) , 后插迭代器 ( back_inserter ) 和任意位置插入迭代器 (inserter)

list<int> s;

back_inserter iter(s);

*(iter++) = 5; // 通过 iter 把 5 插入 s 末尾

# 顺序容器的适配器

以顺序容器的基础构建一些常用数据结构，是对顺序容器的封装

• 栈 (stack)：最先压入的元素最后被弹出
• 队列 (queue)：最先压入的元素最先被弹出
• 优先级队列 (priority_qyeye) : 最 "大" 的 元素最先被弹出

# 栈和队列模版

• 栈模版

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() 获得队尾元素的引用

# 栈反向输出单词

#include <iostream>

#include <stack>

using namespace std;

int main(void)

{

	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;

}

# 优先级队列

• 优先级队列 也像栈和队列一样支持元素的压入和弹出，但元素弹出的顺序与 元素的大小 有关，每次弹出的总是 容器中最"大"的一个元素

template <class T,class Sequence = vector<T> > class priority_queue;

• 优先级队列的基础容器必须是支持随机访问的顺序容器
• 支持栈和队列的 size,empty,push,pop 几个成员函数，用法与栈和队列相同
• 优先级队列并不支持比较操作
• 与栈类似，优先级队列提供一个 top 函数，可以获得下一个即将被弹出元素的引用