算法前置，定制操作与迭代器

定制操作

许多算法都会比较输入序列中的元素，默认情况下，这类算法使用元素自带的<或=运算符来完成比较。标准库中还定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。

谓词

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。
标准库中有的算法接受谓词来代替默认运算符。
谓词根据其接受的参数可分为一元谓词与二元谓词。
以下是一个使用的例子。

1
2
3
4
5
6

//比较函数
bool is_shorter(const string &s1,const string &s2){
    return s1.size()<s2.size();
}
//应用了比较函数的排序
sort(str.begin(),str.end(),is_shorter);

lambda表达式

lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与其他函数相似，其具有一个返回类型、一个参数列表和一个函数体。但与函数不同，其可以定义在函数内部。其表达式如下形式：
[捕获列表] (参数列表) -> return 返回类型 {函数体}
可以忽略返回类型和参数列表。
以下是个示例：

1
2
3
4

//与auto f = [] () -> return int { return 42; };等价
auto f = [] { return 42; };
//输出42
cout << f() << endl;

其中捕获列表是lambda所在函数中定义的局部变量列表，可以使用变量捕获、引用捕获或隐式捕获。

以下是个示例：

1
2
3
4
5
6

int sz = 5;
//也可以  [=]
auto f = [sz] (const string &a)
        { return a.size() >= sz;}
//返回指向第一个长度大于等于sz的元素的指针
auto wc = find_if(str.begin(), ste.end(), f());

bind函数

在一两个地方使用的简单操作，lambda是有用的。如果我们要在很多地方使用相同的操作，通常应定义一个函数。但许多算法不接受带有额外参数的函数。
而c++11引入了bind，它被定义在头文件functional中。可以将bind函数看做一个通用函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的函数列表。
调用bind的一般形式为：
auto 新可调用对象 = bind(可调用对象, 参数列表);
参数列表是以逗号分隔的对应给可调用对象的参数，即
当我们调用新可调用对象时，新调用对象会调用可调用对象，并拷贝传递参数列表中的参数
参数列表中的参数可能包含有_n的名字，其中n是一个整数。其被定义在std命名空间下的placeholders的命名空间中std::placeholders::_n，这些是占位符，表示新可调用对象的参数，他们占据传递给新可调用对象的参数的位置。n表示生成的可调用对象中参数的位置:_1为新可调用对象的第一个参数，_2为新可调用对象的第二个参数，以此类推。
以下是上个示例应用bind函数：

1
2
3
4
5
6
7

bool check_size(const string &s, int sz){
    return a.size() >= sz;
}

int sz = 5;
//返回指向第一个长度大于等于sz的元素的指针
auto wc = find_if(str.begin(), ste.end(), bind(check_size, _1, sz));

注：因为bind的那些不是占位符的参数被拷贝到bind的返回对象中去，但有些参数我们希望以引用的方式传递。我们可以使用ref()，要使用const的引用则使用cref()，这两函数定义在bing相同的头文件中。
以下是个例子：

1
2
3
4
5
6
7
8
9
10

ostream &print(ostream &os, const string &s, char c){
    return os << s << c;
}

//错误：os无法拷贝
for_each(str.begin(), str.end(),
    bing(print, os, _1, ' '));
//正常运行
for_each(str.begin(), str.end(),
    bing(print, ref(os), _1, ' '));

迭代器

除了为每个容器定义的迭代器之外，头文件iteration中还定义了以下几种迭代器。

插入迭代器

插入迭代器是种迭代适配器，它接受一个容器，生成迭代器，能实现向给定容器添加元素。当通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。
插入迭代器有三种类型，其区别在于插入位置：

• back_inserter：创建一个使用push_back的迭代器。
• front_inserter：创建一个使用push_front的迭代器。
• inserter：创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所示元素之前。

只有在容器支持push_front的情况下，才可以使用front_inserter，back_inserter同理。
以下是插入迭代器通用操作：

以下是一些列子：

1
2
3
4
5
6

list<int> lst = {1,2,3,4};
list<int> lst2,lst3;
//拷贝完成后，lst2包含 4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
//拷贝完成后，lst3包含 1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.end()));

iostream迭代器

虽然iostream类型不是容器，但标准库定义了IO类型对象的迭代器。迭代器将其对应的流当作特定类型的元素序列来处理，使其可以被泛型算法读写数据。

istream_iterator

istream_iterator为读取出入流的迭代器，其操作如下：

以下是一些例子：

1
2
3
4

//in为读取cin中int类型的迭代器，eof为尾后迭代器
istream_iterator<int> in(cin),eof;
//输出in迭代器中所有值的和
cout << accumulate(in, eof, 0) << endl;

ostream_iterator

ostream_iterator为输出流写数据的迭代器，其操作如下：

以下是一些例子：

1
2
3
4

ostream_iterator<int> out_iter(cout, " ");
//将vec中的内容输出
copy(vec.begin(), vec.end(), out_iter);
cout << endl;

反向迭代器

反向迭代器就是在容器中从尾元素反向移动的迭代器。对于反向迭代器，递增与递减操作的含义会返过来。递增一个反向迭代器会移动到前一个元素，递减则会移动到后一个元素。
反向迭代器也有const的版本。其与正常迭代器的关系如图：

反向迭代器会反向处理string，导致遍历string变成倒序，为了解决这个问题给出了反向迭代器.base()函数来获取正常顺序的迭代器，rcomma与rcomma.base()指向不同的元素，line.crbegin()与line.cend()同理。

以下是例子：

1
2
3
4
5
6
7
8
9

list<char> line = {FIRST,MIDDLE,LAST}
//从往前查找','
auto rcommea = find(line.cregin(), line.crend(), ',');
//错误逆序输出
//将输出TSAL
cout << string(line.crbegin(), rcomma) << endl;
//得到一个正向迭代器，从','输出到末尾
//将输出LAST
cout << string(rcomma.base(), line.cend()) << endl;

参考资料

C++primer中文版(第五版) 电子工业出版社。