泛型算法¶

概述¶

• 不直接操作容器，遍历由两个迭代器指定的一个元素范围进行操作
• 迭代器令算法不依赖于容器
• 算法依赖于元素类型的操作

初识泛型算法¶

只读算法¶

• find

• accumulate

int sum = accumulate(vec.begin(),vec.end(), 0);   // 第三个参数是和的初值
string sum = accumulate(v.cbegin(), v.cend(), string("")); // string定义了+运算符

• count

• equal：确定两个序列是否保存相同的值，接受三个迭代器；假定每个元素在第二个序列中都有一个与之对应的元素（第二个序列至少与第一个序列一样长）

写容器算法¶

• fill：接受一对迭代器表示一个范围，还接收一个值作为第三个参数；fill将第三个值赋予输入序列中的每个元素

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

• 使用插入迭代器来保证算法有足够元素空间来容纳输出数据的方法

vector<int> vec;
fill_n(back_iterator(vec), 10, 0);
// 每次赋值将在vec上调用push_back，每个元素值为0

拷贝算法¶

• 接受三个参数，前两个表示一个输入范围，第三个表示目的序列的起始位置

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);
// copy返回的是目的位置迭代器（递增后）的值；尾元素后面的位置

• replace(ilist.begin(), ilist.end(), 0, 42)：将所有0的元素改为42
• replace_copy(ilist.cbegin(), ilist.cend(), back_iterator(ivec), 0, 42)：不改变原来的序列，在ivec中为0的元素改为42

重排容器元素的算法¶

• sort(words.begin(), words.end())
• unique：重排输入序列，将相邻的重复项“消除”；返回一个指向不重复值范围末尾的迭代器（最后一个不重复元素之后的位置）

算法根本不知道容器的存在，算法在迭代器上进行操作；fill_n对容器进行插入，也是在back_iterator上进行的，而该迭代器向容器插入元素

定制操作¶

向算法传递参数¶

• 谓词：一个可调用的表达式，返回结果是一个能用作条件的值。标准库所用算法分为一元谓词和二元谓词

bool cmp(const string &s1, const string &s2) {
    return s1.size() < s2.size();
}
sort(words.begin(), words.end(), cmp);

lambda表达式¶

• 一个lambda只有在捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量
• 尽量保持lambda的变量捕获简单化
• 捕获一个普通变量，如int，string或其他非指针类型；可以采用简单的值捕获
• 捕获一个指针或迭代器，或采用引用捕获方式，必须确保在lambda执行时；绑定到迭代器、指针或引用的对象仍然存在同时保证对象具有预期的值；应该避免捕获引用和指针

可变lambda¶

• 对于一个值被拷贝的变量，lambda不会改变其值，如果我们需要改变一个被捕获的变量的值；必须在参数列表首加上mutable

指定lambda返回值类型¶

transform(vi.begin(), vi.end(), [](int i)->int {if(i > 0) return -i; else return i;});
    auto lambda = [&ncref = n, n](auto a, auto b, auto /*unused*/)
    {
        f(b, 42, a, ncref, n);
    };

参数绑定¶

• bind标准库函数，定义在头文件functional中；
• 可以看作通用的函数适配器；接受一个可调用对象，生成一个新的可调用对象

auto newCallable = bind(callable, arg_list);

• 使用placeholders命名空间，_1, _2..._n
• 函数模板 std::mem_fn 生成指向成员指针的包装对象，它可以存储、复制及调用指向成员指针。到对象的引用和指针（含智能指针）可在调用 std::mem_fn 时使用。

再探迭代器¶

• 插入迭代器
• 流迭代器：绑定到输入或输出流上
• 反向迭代器：向后移动
• 移动迭代器：不拷贝元素而是移动元素

插入迭代器¶

iostream迭代器¶

反向迭代器¶

泛型算法结构¶

特定容器算法¶

• 对于list和forward_list，应该优先使用成员函数版本的算法而不是通用算法

splice成员¶

• 链表数据结构所特有的

链表特有操作会改变容器¶

可变参数模板¶

    template<typename... Args> int add_many(Args... args)
    {
        return data + (args + ...);
    }