范型算法 | Fish

常用函数

#include <algorithm>

// 标准STL函数
find(first, last, val);
count(first, last, val);
fill(first, last, init);
replacd(first, last, n, p);
copy(first1, last1, first2);
unique(first, last);
transform(first, last, func);

1 2	sort(first1, last1); stable_sort(first, last);

#include <numeric>

accumulate(first, last, init);
equal(first1, last1, first2);

back_inserter

使用back_inserter函数返回一个类似与动态迭代器的东西。比如，如果使用普通迭代器，在使用fill函数时，如果容器没有值，将会返回一个未知错误

std::vecter<int> vi;
// 错误，因为容器vi为空，所以不能添加任何值
auto it = vi.begin();
*it = 1;
// 使用写函数也是不可以的
std::fill(vi.begin(), vi.end(), 0);

std::vector<int> vi;
// 正确，因为使用的是动态迭代器
auto back_vi = std::back_inserter(vi);
*it = 1;

重构算法函数

这种使用函数的方法在现在这个学习的阶段我理解为使用一个回调函数来替代标准库里面的默认函数，使用函数作为参数可以使用自定义的函数作为参数，也可以使用lambda表达式（也称为匿名函数），举一个例子。

将将一段英文按照单词的大小顺序重新排序

std::string str("eat apple c++ english swift java");
std::vector<std::string> svec;
std::string word;
std::istringstream iss(str);

// 将字符串中的单词逐个存入容器svec中
while (iss >> word) {
    svec.push_back(word);
}

// 输出svec中的单词
for (auto s : svec) {
    std::cout << s << " ";
}
std::cout << "\n";

// 进行排序操作
std::sort(svec.begin(), svec.end());

// 再次输出svec中的内容
for (auto s : svec) {
    std::cout << s << " ";
}

上面这段代码输出，可以看出标准库里面的排序算法是按照单词字母大小升序排列的

1 2	eat apple c++ english swift java apple c++ eat english java swift

但是如果在使用的时候不想使用单词的字母排序，需要使用单词的长度排序时，sort函数就不起作用了，所以官方对这些算法函数提供了一个重载版本，只需要我们专注于各种算法，忽略了在进行算法操作时的各种迭代操作，算是减少了代码量吧

重写算法函数作为参数

写一个关于判断字符串长短的函数，如果str1长度小于str2则返回true

1
2
3

bool isShorter(const std::string& str1, const std::string& str2) {
    return str1.size() < str2.size();
}

在将函数名作为参数传入sort作为第三个参数，排序过后容器中的输出如下

1 2	// 重载sort函数，将isShorter作为参数传入函数中 std::sort(svec.begin(), svec.end(), isShorter);

1 2	// 打印容器中排列顺序 c c++ asm php java swift golang python

lambda表达式

lambda表达式的基本结构描述如下，需要理解的有捕获列表和参数列表。

1	[capture list] (parameter list) -> return type { function body }

在实际用法如下描述，不得不说在用法上有函数指针的味道

1 2	auto f = []() -> int { return 42; }; std::cout << f() << std::endl;

如果使用lambda表达式来作为stable_sort函数的谓词，则写法如下，这句代码作用是将容器svec中的字符串按照长度从小到大排列

1
2
3

std::stable_sort(svec.begin(), svec.end(), [](const std::string& str1, const std::string& str2) -> bool {
        return str1.size() < str2. size();
    });

lambda的捕获列表

emm，我的理解是，由于lambda表达式的参数只能由被使用函数决定而不能由我们来决定，所以局限性非常大，捕获列表的出现就是为了解决这种局限性问题，将我们想定义的参数放在捕获列表中，然后由lambda表达式调用。

例如下面这个例子，函数find_if函数返回一个迭代器，我们使用lambda函数重写查询算法，返回一个字符串长度大于等于sz的迭代器，而sz就是我们捕获列表中的那个值，这个值只要find_if函数可以访问都可以作为捕获列表中的值

int sz = 5;
auto fi = std::find_if(svec.begin(), svec.end(), [sz] (const std::string& str) -> bool {
    return str.size() <= sz;
});

std::cout << *fi << std::endl;

特别注意，如果lambda表达式的返回值无法识别（比如说函数中有判断语句，多个return等），那么lambda将会返回void类型，导致与设置的返回值不同而编译时报错

bind函数

lambda表达式的出现是为了解决标准库算法函数默认的多元谓词与所需要的算法函数所需要的参数数量不匹配的问题，但是lambda表达式的缺陷也比较明显，就是不能写太复杂的表达式，如果使用太复杂的表达式可能导致无法识别的问题，这个时候就还是需要使用函数，bind函数就是为了解决这个问题

// 使用方法
auto newCallable = bind(callable, arg_list);参数
// 绑定check_size和sz参数
auto check6 = std::bind(check_size, std::placeholders::_1, 6);

有了bind参数之后，之前使用lambda表达式的函数就可以用bind函数来表示

// lambda表达式如下
auto fi = std::find_if(svec.begin(), svec.end(), [sz] (const std::string& str) -> bool {
    return str.size() <= sz;
});

// bind函数绑定如下
auto it = std::find_if(svec.begin(), svec.end(), check6);

使用bind函数绑定的参数时，占位符的顺序可以交换，一旦交换，那么函数的作用就可能是反过来的

// 需要绑定的函数
bool isShorter(const std::string& str1, const std::string& str2) {
    return str1.size() < str2.size();
}

// 将容器中的字符串长度由小到大排列
auto is_short1 = std::bind(isShorter, std::placeholders::_1, std::placeholders::_2);

// 将容器中的字符串长度由大到小排列
auto is_short2 = std::bind(isShorter, std::placeholders::_2, std::placeholders::_1);

迭代器

迭代器除了经常使用的容器迭代器之外，还有四种不同类型的迭代器

插入迭代器（insert iterator）
流迭代器（stream iterator）
反向迭代器（reverse iterator）
移动迭代器（mov iterator）