目录
泛型算法概述
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.如果泛型算法可以直接改变容器大小，这会导致算法对容器类型有依赖性，这就破坏了泛型算法的普适性