泛型算法

泛型算法是可以支持多种类型的算法，这里主要讨论C++标准库中定义的算法，包括

algorithm
numeric
ranges

这里出现了一个问题，那就是为什么要引入泛型算法而不采用方法的形式，主要原因有以下两点

这里的方法指的是类的成员函数

内建数据类型不支持方法
泛型算法内部的计算逻辑一般来说是存在相似性的，可以避免在方法中重复实现相同的逻辑

这里的相似性一般使用模版来实现

那么泛型算法如何实现支持多种类型呢？C++给出的办法是使用迭代器来作为算法与数据之间的桥梁，比如

    std::vector<int>x(100);
    std::sort(std::begin(x),std::end(x));

泛型算法通常来说都不复杂，但拥有足够好的优化，主要体现在：速度足够快，对于异常输入的处理足够鲁棒

在C++中，一些算法与方法同名，实现的功能类似，此时我们建议调用方法而不是算法，比如std::find VS std::map::find

这里的std::find使用的是线性查找，而std::map::find利用了红黑树的排序性质，实现了类似二分的查找

通常来说类的成员方法的性能要优于同名的泛型算法

这里我们将泛型算法大致分为三类

读算法：给定一个迭代区间，读取其中的元素并进行计算，比如
1. accumulate：累加，在C++20以后可以自定义操作
2. find：查找
3. count：计数
写算法：向一个迭代区间中写入元素
1. 单纯写操作：
  - fill：给定一个区间，将区间中的元素全部使用给定值填充
  - fill_n：给定区间开头和要填充的个数，使用给定值填充区间开头之后指定个数的元素
2. 读+写操作
  - transform：遍历输入区间的每一个元素，对元素进行变换并写入到输出区间中
  - copy：遍历输入区间的每一个元素，将输入区间的元素拷贝到输出区间中
注意fill_n、transform和copy都不会给定输出区间或者填充区间的结尾，所以一定要确保目标区间足够大，否则会产生未定义的行为
排序算法：改变输入区间中元素的顺序，缺省情况下从小到大，元素要支持使用<进行排序

可以自定义排序方法
- sort：对区间内快排
- unique：对有序区间内的元素进行去重
注意unique只是将不重复的元素放到了区间开头的部分，返回一个指向不重复元素区间下一个位置的迭代器，我们后续需要对后面的元素进行删除才能得到真正的有序不重复区间

我们可以看到以上的泛型算法基本上都是基于迭代器来实现的，C++中的迭代器分为以下几类：

输入迭代器：可读、可递增，典型的应用为find算法
输出迭代器：可写、可递增，典型的应用为copy算法
前向迭代器，可读写、可递增，典型的应用为replace算法
双向迭代器、可读写、可递增递减，典型应用为reverse算法
随机访问迭代器：可读写、可增减一个整数，典型应用为sort算法

一些算法会根据迭代器类别的不同引入相应的优化，比如distance算法

接下来我们来讨论一些特殊的迭代器

插入迭代器：back_insert_iterator/front_insert_iterator/insert_iterator

int main()
{
    std::deque<int> q;
    std::back_insert_iterator< std::deque<int> > it(q);
 
    for (int i=0; i<10; ++i)
        it = i; // calls q.push_back(i)
 
    for (auto& elem : q) std::cout << elem << ' ';
}
// 输出为0 1 2 3 4 5 6 7 8 9

本质上是对迭代器的行为进行了封装，在上层提供统一的=接口，但是在底层调用容器的不同的插入函数

流迭代器：ostream_iterator/istream_iterator

int main()
{
    std::istringstream stream("1 2 3 4 5");
    std::copy(
        std::istream_iterator<int>(stream),
        std::istream_iterator<int>(),					//这里要注意，流迭代器的默认构造和end()的含义是一致的，这里表明输出流中的所有元素都已经被读完，在C++中他有一个名字叫做哨兵(Sentinel)
        std::ostream_iterator<int>(std::cout, " ")
    );
}
// 输出为1 2 3 4 5

int main()
{
    std::ostream_iterator<char> oo {std::cout};
    std::ostream_iterator<int> i1 {std::cout, ", "};		// 这里的第二个参数表示每次输出后附加一个","
    std::fill_n(i1, 5, -1);
    *oo++ = '\n';
 
    std::ostream_iterator<double> i2 {std::cout, "; "};
    *i2++ = 3.14;
    *i2++ = 2.71;
	// 输出为-1, -1, -1, -1, -1,
	//		3.14; 2.71;
}

反向迭代器

移动迭代器：move_iterator，本质上在每次读取时候会调用std::move，对于支持移动赋值构造的对象来说会将原有的对象的内容清空

int main()
{
    std::vector<std::string> v{"this", "_", "is", "_", "an", "_", "example"};
 
    auto print_v = [&](auto const rem) {
        std::cout << rem;
        for (const auto& s : v)
            std::cout << std::quoted(s) << ' ';
        std::cout << '\n';
    };
 
    print_v("Old contents of the vector: ");
 
    std::string concat = std::accumulate(std::make_move_iterator(v.begin()),
                                         std::make_move_iterator(v.end()),
                                         std::string());
 
    print_v("New contents of the vector: ");
 
    std::cout << "Concatenated as string: " << quoted(concat) << '\n';
}
// 输出为Old contents of the vector: "this" "_" "is" "_" "an" "_" "example" 
// 		New contents of the vector: "" "" "" "" "" "" ""
// 		Concatenated as string: "this_is_an_example"