目录

• 泛型算法概述
• • ※关键概念：泛型算法永远不会执行容器的操作
• 泛型算法的结构
• • 只读算法
  • • ※泛型算法中的"泛型操作"必须对元素类型是可行的
    • ※确保泛型算法不会访问不存在的元素
  • 写容器元素的算法
  • • ※泛型算法不检查写操作
    • back_insert_iterator和back_inserter
  • 拷贝算法(copy)
  • 重排容器元素的算法
  • • 排序算法(sort)
    • "删除"相邻重复元素(unique)

泛型算法概述

STL定义了一组泛型算法(generic algorithm)，大多数算法都定义在头文件algorithm中，还有一组数值泛型算法定义在头文件numeric中

泛型算法可以用于不同类型的元素和多种容器类型，所以称它们是"泛型的"

迭代器令泛型算法不依赖于容器，但依赖于元素类型的操作

※关键概念：泛型算法永远不会执行容器的操作

泛型算法本身不会执行容器的操作，它们只会运行与迭代器之上，甚至无需理会保存元素的是不是容器

泛型算法可能改变容器中保存元素的值，也可能在容器内移动元素，但永远不会改变底层容器的大小，添加或删除元素是容器/迭代器的工作，泛型算法自身永远不会做这样的操作

练习10.1：编写程序，读取int序列存入vector中，打印有多少个元素的值等于给定值

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	vector<int>vec = { 27,210,12,47,109,83 };
	int val = 83;
	cout << count(vec.cbegin(), vec.cend(), val) << endl;
	system("pause");
	return 0;
}

练习10.2：重做上一题，但读取string序列存入list中

#include<iostream>
#include<string>
#include<list>
#include<algorithm>
using namespace std;
int main() {
	list<string>lis = { "27","210","12","47","109","83" };
	string val = "83";
	cout << count(lis.cbegin(), lis.cend(), val) << endl;
	system("pause");
	return 0;
}

泛型算法的结构

只读算法

对于只读算法，通常最好使用cbegin()和cend()
如果计划使用算法返回的迭代器来改变元素的值，就需要使用begin()和end()

※泛型算法中的"泛型操作"必须对元素类型是可行的

例：对vec中的元素求和，和的初值是init_sum

vector<_Ty>vec;
accumulate(vec.cbegin(), vec.cend(), init_sum);

vec中的元素可以是int，或者是double、long long，或者其他任何可以加到_Ty上的类型

操作两个序列的算法一般只接受三个迭代器
例：equal用于确定两个序列是否保存相同的值

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

※确保泛型算法不会访问不存在的元素

那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长
确保算法不会试图访问第二个序列中不存在的元素是程序员的责任

练习10.3：用accumulate求一个vector中的元素之和

#include<iostream>
#include<vector>
#include<numeric>
using namespace std;
int main() {
	vector<int>vec = { 27,210,12,47,109,83 };
	cout << accumulate(vec.cbegin(), vec.cend(), 0) << endl;
	system("pause");
	return 0;
}

练习10.4：假定v是一个vector< double >，那么调用accumulate(v.cbegin(), v.cend(), 0)有何错误？
调用accumulate(v.cbegin(), v.cend(), 0)等价于执行以下代码：

int sum = 0;
for (const int&val : v)
	sum += val;
return sum;

0是int型，sum += val;语句会发生强制类型转换，导致可能得不到预期结果

练习10.5：调用accumulate(v.cbegin(), v.cend(), string(""))会发生什么？(v = vector< string >)
调用结果为v中所有string元素首尾连接而成的string

写容器元素的算法

泛型算法不改变容器大小，所以使用这类算法时，必须确保序列原大小不小于要求算法写入的元素数目

例：将迭代器表示范围内的每个元素置为0

fill(vec.begin(), vec.end(), 0);

※泛型算法不检查写操作

泛型算法不检查写入位置是否合法，也不检查写操作本身是否合法

vector<int>vec;
fill_n(vec.begin(), 10, 0);

错误，vec是空的，写入位置不合法

vector<string>vec(10);
fill(vec.begin(), vec.end(), 3.14);

错误，string未定义double的转换构造函数，写操作不合法

back_insert_iterator和back_inserter

back_insert_iterator是插入迭代器(insert iterator)
通常通过迭代器想容器元素赋值时，值会被赋予迭代器指向的元素
通过插入迭代器赋值时，值会被添加到容器中

back_inserter是定义在头文件iterator中的一个函数
back_inserter接受一个容器引用，返回一个与该容器绑定的插入迭代器

vector<int>vec;					//空的vector
auto iter = back_inserter(vec);	//通过back_inserter获取与vec绑定的插入迭代器
*it = 42;						//vec中现在有一个元素，值为42
*it = 0;						//vec中现在有两个元素，分别是{42, 0}

通过上例可以发现，通过back_insert_iterator赋值不仅会向容器中添加元素，还会引起迭代器向后移动

通过插入迭代器使用泛型算法会改变容器的大小

vector<int>vec;					//空的vector
auto iter = back_inserter(vec);	//通过back_inserter获取与vec绑定的插入迭代器
fill_n(iter, 10, 0);			//添加10个元素到vec

上例是否违背了"泛型算法不改变容器大小"？
不违背，改变容器大小的不是泛型算法本身，而是插入迭代器，泛型算法的操作是基于迭代器的

拷贝算法(copy)

copy接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置
copy将输入范围中的元素拷贝到目的序列中

可以用copy实现内置数组的拷贝，代码如下：

int a1[] = { 0,1,2,3,4,5,6,7,8,9 };
int a2[sizeof(a1) / sizeof(*a1)];
auto ret = copy(begin(a1), end(a1), a2);

练习10.6：编写程序，使用fill_n将一个序列中的int值都设置为0

int arr[10];
fill_n(begin(arr), 10, 0);

练习10.7：下面的程序是否有错误？如果有，请改正
(a)

vector<int>vec;
list<int>lst;
int i;
while (cin >> i)
	lst.push_back(i);
copy(lst.cbegin(), lst.cend(), vec.begin());

错误，vec是空的，写操作不合法，改正如下：

list<int>lst;
int i;
while (cin >> i)
	lst.push_back(i);
vector<int>vec(lst.size());
copy(lst.cbegin(), lst.cend(), vec.begin());

(b)

vector<int>vec;
vec.reserve(10);	//reserve为容器预留空间
fill_n(vec.begin(), 10, 0);

错误，reserve方法为容器预留空间，但容器size外的预留空间同样是out_of_range的，改正如下：

vector<int>vec;
vec.resize(10);	//resize调整容器的大小
fill_n(vec.begin(), 10, 0);

练习10.8：“泛型算法不改变容器大小”，这句话在使用back_inserter时依然成立吗？
成立，改变容器大小的不是泛型算法本身，而是插入迭代器，泛型算法的操作是基于迭代器的

重排容器元素的算法

排序算法(sort)

sort算法可以依靠<运算符实现，凡是重载了<运算符的数据类型都可以利用sort排序
sort算法也可以依靠仿函数实现，详情戳sort仿函数

"删除"相邻重复元素(unique)

unique算法可以"删除"相邻重复元素，并返回一个指向不重复值范围末尾的迭代器，如

vector<int>vec = { 1,1,1,1,1,3,3,3,3,1,1, };
auto end = unique(vec.begin(), vec.end());
for (auto iter = vec.begin(); iter != end; iter++)
	cout << *iter << ' ';

输出结果：1 3 1

unique并不是真的删除元素，只是覆盖了相邻的重复元素，这符合"泛型算法不改变容器大小"
要真的删除元素，必须使用容器操作，如erase方法
*实验发现unique返回的迭代器以后的元素没有发生改变，猜测unique的实现方式类似于双指针

练习10.9：设计程序，消除vector< string >中重复的单词

void elimDups(vector<string>&words) {
	sort(words.begin(), words.end());
	auto end = unique(words.begin(), words.end());
	words.erase(end, words.end());
}

练习10.10：泛型算法为什么设计成不能直接改变容器大小？
1.泛型算法的所有操作被迭代器隔离的，这使泛型算法不依赖于容器，使泛型算法具有普适性
2.如果泛型算法可以直接改变容器大小，这会导致算法对容器类型有依赖性，这就破坏了泛型算法的普适性