c++primer笔记十、泛型算法

顺序容器只定义了很少的操作，而其他一些操作比如查找、替换、删除特定值等等，并没有给每个容器都定义成员函数，而是定义了一组泛型算法。
"算法":它们实现了一些经典算法的公共接口，如排序和搜索
"泛型":可以用于不同类型的元素和多种容器类型，还能用于其他类型的序列

10.1 概述

大多数算法定义在algorithm中，在numeric中还定义了一组数组泛型算法
一般情况下这些算法不直接操作容器，而是遍历两个迭代器的范围来操作
例如find

int val = 42;
auto result = find(vec.cbegin(), vec.cend(), val);

由于find操作的是迭代器，因此可以查找任何容器

string val = "a value";
auto result = find(lst.cbegin(), lst.cend(), val);

类似的，由于指针就像内置数组上的迭代器，因此可以查找数组

int ia[] = {27, 210, 12, 47, 109, 83};
int val = 83;
int* result = find(begin(ia), end(ia), val);

还可以在序列的子范围中查找

//从ia[1]找到ia[4](不包括ia[4])
auto result = find(ia + 1; ia + 4; val);

算法如何工作

以find为例：
1：访问序列中的首元素
2：比较此元素与我们要查找的值
3：如果此元素与我们要查找的值匹配，find返回标识此元素的值
4：否则，find前进到下一个元素，重复2、3
5：如果到达尾序列，find停止
6：如果find到达序列末尾，它应该返回一个指出元素未找到的值，此值与步骤3所返回的必须具有相容的类型

这些步骤都不依赖于容器所保存的元素类型，因此只要一个迭代器可以访问元素，find就不依赖于容器类型。

迭代器令算法不依赖于容器，但算法依赖于元素类型的操作

上述算法除了步骤2，都可以用迭代器操作来实现，比如解引用实现元素访问，递增可以移动到下一个元素，尾后迭代器可以判断end。
但是大多数算法都使用了一个(或多个)元素类型上的操作。
如2中，find用元素类型的==运算符完成比较，其他算法可能要求元素支持<。
不过大多数算法提供了一种思路，允许我们使用自定义的操作来代替默认的运算符。

关键概念：算法永远不会执行容器的操作

10.2 初识泛型算法

附录A列出了所有算法

只读算法

一些算法只读取输入范围内的元素，比如find，count
还有一个只读算法是accumulate,定义在numeric中。

int sum = accumulate(vec.cbegin(), vec.cend(), 0);  //sum为vec元素中的和，和的初始值为0

算法和元素类型

accumulate将第三个参数作为求和起点，蕴含了一个假定：将元素类型加到和的类型上的操作必须是可行的。(即类型匹配或能转换)
比如也可以把字符串连接起来

string sum = accumulate(v.cbegin(), v.cend(), string(""));

//如果把空串当成字符传递是不可行的
//const char*上没有定义+运算符
string sum = accumulate(v.cbegin(), v.cend(), "");

操作两个序列的算法

equal也是只读算法，用于确定两个序列是否保存相同的值。
此算法接受三个迭代器，前两个表示序列中的元素范围，第三个表示第二个序列的首元素

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

元素类型允许不同，只需要能用==来比较就行
但是equal基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。

那些只接受单一迭代器来表示第二个序列的算法，都默认要求长度比第一个长

写容器元素的算法

一些算法将新值赋予序列中的元素。使用这类算法时必须确保序列原大小至少不小于我们要求算法写入的元素数目。算法不会改变容器大小
例如fill接受一对迭代器表示范围，还接受一个值，把这个值赋予输入序列的每个元素
fill(vec.begin(), vec.end(), 0);
fill(vec.begin(), vec.begin() + vec.end()/2, 10);

算法不检查写操作

一些算法接受一个迭代器来指出一个单独的目的位置，将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。
例如fill_n接受一个单迭代器、一个计数值和一个值。给一个定制赋予指定个元素。

vector<int> vec;
fill_n(vec.begin(), vec.size(), 0);

千万不能在空容器上调用，因为泛型算法不会对容器操作。

back_inserter

一个保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。
插入迭代器是一种向容器中添加元素的迭代器。
当我们通过一个插入迭代器赋值时，一个与赋值号右侧相等的元素被添加到容器中。
back_inserter接受要给指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中:

vector<int> vec;        //空向量
auto it = back_inserter(vec);       //通过它赋值会将元素添加到vec中
*it = 42;           //vec中添加了一个元素42

我们常用back_inserter来创建一个迭代器，作为算法的目的位置来使用

vector<int> vec;
//创建一个插入迭代器，来向vec添加元素
fill_n(back_inserter(vec), 10, 0);  //添加10个元素到vec

拷贝算法

另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。
接受三个迭代器，前两个表示范围，第三个表示目的序列的起始位置。
将输入范围的元素拷贝到目的序列，传递给copy的目的序列至少要包含和范围一样多的元素

int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)]; //a2和a1大小一样
//ret指向拷贝到a2的尾元素之后的位置
auto ret = copy(begin(a1), end(a1), a2);    //把a1内容拷贝给a2

copy返回是其位置迭代器(递增后)的值。
很多算法都提供“拷贝”版本，计算新元素的值，但不会放置在输入序列末尾，而是创建一个新序列保存结果。
例：replace读入一个序列，并将其中等于给定值的元素都改为另一个值

//把0替换为42
replace(ilist.begin(), ilst.end(), 0, 42);

如果希望原序列不变，可以用replace_copy,接受额外第三个迭代器参数，指出调整后序列的保存位置：

//使用back_inserter按需要增长目标序列
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

此调用后，ilst未变，ivec包含ilst的一份将0替换为42的拷贝

重排容器元素的算法

某些算法会重排元素顺序，比如sort

消除重复单词

首先对vector排序，使相同的单词相邻出现。然后用unique的标准库算法来重排vector。
由于算法不能执行容器的操作，所以将使用erase来完成删除操作

void elimDups(vector<string> &words)
{
    //排序words
    sort(words.begin(), words.end());
    //unique重排输入范围，使每个单词只出现一次
    //排列在范围的前部，返回执行不重复区域之后一个位置的迭代器
    auto end_unique = unique(word.begin(), word.end());
    //删除重复的
    words.erase(end_unique(), words.end());
}

使用unique后，并不能真正删除元素，只是覆盖相邻的重复元素。返回迭代器之后的位置元素仍然存在，只是不知道值是什么。
即使words中没有重复单词，erase也是安全的。

10.3 定制操作

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

向算法传递函数

sort有一个重载版本，接受第三个参数谓词

谓词

有两类：一元谓词(一个参数)和二元谓词(两个参数),接受谓词参数的算法对输入序列中的元素调用谓词。因此元素类型必须能转换为谓词的参数类型。
例：sort有一个接受二元谓词的版本，替换<来比较

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}
//按长度来排列，短的在前
sort(word.begin(), word.end(), isShorter);

排序算法

将words按大小重排同时，还想把具有相同长度的元素按字典序排列，可以用stable_sort算法。这种稳定排序算法维持相等元素的原有顺序。
而sort是不稳定的，可能会改变相对顺序

lambda表达式

有时希望进行的操作有更多参数，超出了谓词限制。
如果在编写中划分序列的谓词时，可以不必为每个可能的大小都编写一个独立的谓词，很有实际价值。
例：求大于等于一个给定长度的单词有多少的框架

void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimDups(words);        //按字典排序，删除重复单元
    //按长度排序，长度相同的维持字典序
    stable_sort(words.begin(), words.end(), isShorter);
    //获取一个迭代器，指向第一个满足size() >= sz的元素
    //计算数目
    //打印
}

可以使用find_if来查找第一个具有特定大小的元素。
find_if前两个参数时迭代器，第三个参数时谓词。它返回第一个使谓词返回非0的元素。否则返回尾迭代器

介绍lambda

可以向一个算法传递任何类别的可调用对象。
对于一个对象或一个表达式，如果可以对其使用调用运算符，则称为可调用的。
有四种：函数，函数指针，重载了函数调用运算符的类，lambda表达式

一个lambda表达式表示一个可调用的代码单元，可以理解为内联函数。
具有一个返回类型，一个参数列表和一个函数体。
与函数不同在于lambda可以定义在函数内部。

//形式如下
[capture list] (parameter list) -> return type {function body}
//capture list:捕获列表，是lambda所在函数中定义的局部变量的列表，通常为空
//return type,parameter list, functionbodt和普通函数一样
//必须使用尾置返回来指定返回类型

可以忽略参数列表和返回类型，但必须有捕获列表和函数体

auto f = [] {return 42; };

向lambda传递参数

lambda不能有默认参数，其他与函数类似。

stable_sort(words.begin(), words.end(), 
            [](const string &a, const string &b)
            { return a.size() < b.size();});
//空捕获列表表示不使用任何局部变量

使用捕获列表

一个lambda只要在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用

[sz](const string &a)
    { return a.size() >= sz; };     //捕获了才能使用sz

调用find_if

查找第一个长度大于等于sz的元素

auto wc = find_if(words.begin(), word.end(), 
    [sz](const string &a)
    { return a.size() >= sz; });

如果查找不存在，则返回尾迭代器的拷贝
从而再利用迭代器可以计算一共有多少个元素

auto count = words.end() - wc;

for_each算法

接受一个可调用对象，并对输入序列中的每个元素调用该对象

//打印长度大于等于给定值的单词，后面接空格
for_each(wc, words.end(),
        [](const string &s){cout << s << " ";});
cout <<endl;

完整的biggies

void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimDups(words);
    stable_sort(words.begin(), words.end(), 
            [](const string &a, const string &b)
            { return a.size() < b.size();});
            
    auto wc = find_if(words.begin(), word.end(), 
    [sz](const string &a)
    { return a.size() >= sz; });
    
    auto count = words.end() - wc;
    cout << count << " " << make_plural(count, "word", "s")
         << " of length " << sz << " or longer " << endl;
         
    for_each(wc, words.end(),
        [](const string &s){cout << s << " ";});
    cout <<endl;
}

lambda捕获和返回

定义一个lambda时，编译器生成一个与lambda对应的新的类类型。
当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型和未命名对象。
类似，使用auto定义用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。

默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。类型普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。

值捕获

类似参数传递，变量捕获也可以是值或者引用。
被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝：

void fcn1()
{
    size_t v1 = 42;
    auto f = [v1] {retrun v1;};
    v1 = 0;
    auto j = f();           //j = 42
}

由于值是在创建时捕获，因此之后修改也不会影响lambda内对应的值

引用捕获

可以采用引用方式捕获

void fcn2()
{
    size_t v1 = 42;
    auto f2 = [&v1] { return v1;};
    v1 = 0;
    auto j = f2();      //j = 0
}

当在函数体内使用此变量时，实际上使用的时引用所绑定的对象。
限制：如果我们采用引用方式捕获一个变量，就必修确保被引用的对象在lambda执行的时候是存在的。
lambda捕获的是局部变量，这些变量在函数结束后就不复存在了。如果在函数结束后执行，捕获的引用指向的局部变量已经消失。
引用捕获有时是有必要的，比如ostream无法拷贝。

void biggies(vector<string> &words,
             vector<string>::size_type sz,
             ostream &os = cout, char c = ' ')
{
    for_each(word.begin(), words.end(),
             [&os, c](const string &s) {os << s << c;)};
}

一般来说，应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。如果可能的话，应该避免捕获指针或应用。

隐式捕获

除了显式列出我们希望的来自所在函数的变量之外，还可以让编译器根据lambda体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。
&表示采用捕获引用方式
=表示采用捕获值方式

wc = find_if(words.begin(), words.end(),
             [=] (const string &s)
                { return s.size() >= sz; });

如果一部分标量采用值捕获，其他采用引用捕获，可以混合使用隐式捕获和显式捕获:

void biggies(vector<string> &words,
             vector<string>::size_type sz,
             ostream &os = cout, char c = '')
{
    //os隐式捕获，引用捕获方式;c显式捕获，值捕获方式
    for_each(words.begin(), words.end(),
            [&, c] (const string &s) { os << s << c;});
    //os显式捕获,c隐式捕获
    for_each(words.begin(), words.end(),
            [=, &os](const string &s) {os << s << c;});
}

可变lambda

默认情况下，对与一个值拷贝的变量，lambda不会该表其值。
如果我们希望能改变一个被捕获的变量的值，必须在参数列表首加上mutable

void fun3()
{
    size_t v1 = 42;
    auto f = [v1] () mutable {return ++v1;};
    v1 = 0;
    auto j = f();   //j为43
}

void fun4()
{
     size_t v1 = 42;
    auto f = [&v1] () {return ++v1;};
    v1 = 0;
    auto j = f();   //j为1
}

指定lambda返回类型

如果lambda包含return之外的任何语句，则编译器假定返回void, 不能返回值
例：替换每个负数

transform(vi.begin(), vi.end(), vi.begin(),
          [] (int i) {return i < 0 ? -i : i;});
          
//如果使用IF就会出错
transform(vi.begin(), vi.end(), vi.begin(),
          [] (int i) { if ( i < 0) return -i ; else return i;});

如果需要返回类型，必须用尾置返回类型

transform(vi.begin(), vi.end(), vi.begin(),
          [] (int i) -> int
          { if ( i < 0) return -i ; else return i;});

参数绑定

对于捕获局部变量的lambda，需要捕获局部变量，用函数代替不容易。比如find_if只能接受一元谓词，因此传递的调用对象必须接受单一参数。
为了用函数代替lambda，必须解决如何向形传递参数的问题。

标准库bind函数

定义在头文件functional中，可以将其看作一个通用的函数适配器，接受一个可调用对象，生成一个新的可调用对象来适应原对象的参数列表。

//调用bind的一般形式为:
auto newCallable = bind(callable, arg_list);

其中，newCallable本身是一个可调用对象，arg_list是一个逗号分割的参数列表。对应给定的callable的参数。
即当我们调用newCallable时，会调用callable,并传递给它arg_list中的参数。
用_n表示占位符

绑定check_size的sz参数

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

此函数不能传入find_if
用bind生成一个调用check_size的对象

auto check6 = bind(check_size, _1, 6)

check6只接受单一参数，第二个参数为6
使用bind,可以将原来lambda的find_if调用替换为函数的版本：

auto wc = find_if(words.begin(), words.end(),
                 bind(check_size, _1, sz));

使用placeholders名字

名字_n都定义在一个名为placeholders的命名空间中，这个命名空间本身定义在std中。
使用应该如下：

using std::placeholders::_1

//也可以全局
using namespace std::placeholders

bind的参数

可以用bind修正参数的值，还可以用bind绑定给定可调用对象中的参数或重新安排其顺序。

//f有5个参数
auto g = bind(f, a, b, _2, c, _1);

当调用g(X,Y)时

f(a, b, Y, c, X)

用bind重排参数顺序

颠倒isShorter的含义

//由短至长排序
sort(words.begin(), words.end(), isShorter);
//由长至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1);

绑定引用参数

有时对绑定的参数希望引用传递，或者要绑定的参数类型无法拷贝
例：替换一个引用方式捕获ostream的lambda:

//os是一个局部变量，引用一个输出流
//c是一个局部变量，类型为char
for_each(words.begin(), words.end(),
         [&os, c](const string &s) (os << s << c; ));

可以很容易编写一个函数，但不能替代对os捕获

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

要传递给bind一个对象而又不拷贝它，必须使用标准库ref函数:

for_each(words.begin(), words.end(),
         bing(print, ref(os), _1, ' ');

ref返回一个对象，包含给定的引用，此对象是可以拷贝的。
还有一个cref生成一个保存const引用的类。

10.4再探迭代器

iterator中还定义了额外几种迭代器：

插入迭代器：这些迭代器被绑定到一个容器上，可以用来向容器插入元素。
流迭代器：被绑定到输入或输出流上，可用来遍历所有关联的IO流。

反向迭代器:这些迭代器向后而不是向前移动。
**移动迭代器:这些迭代器不是拷贝其中的元素，而是移动他们。

插入迭代器

是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素

//操作
it = t  //在it指定的位置插入值t。比如调用c.push_back(t)、c.insert(t,p),p为位置
*it,++it,it //不会对it做任何事情，都返回it

有三种类型,区别在于插入位置：

back_inserter   //使用push_back的
fornt_inserter //使用push_front
inserter    //接受第二个参数，指向一个迭代器，元素插入到该迭代器之前

例如

*it = val;
//等效
it = c.insert(it, val);
++it;

fornt_inserter元素总是插入到容器第一个元素之前

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.begin());

iostream迭代器

**istream_iterator*读取输入流
ostream_iterator输出流写数据
这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。
通过使用迭代器，我们可以使用泛型算法从流对象读取数据以及向其写入数据。

istream_iterator操作

当创建一个流迭代器时，必须指定迭代器将要读写的流的对象类型。

istream_iterator<int> int_it(cin);  //从cin读取int
istream_iterator<int> int_eof;      //尾后迭代器
ifstream in("afile");
istream_iterator<string> str_it(in);    //从"afile"读取字符串

从标准输入读取数据，存入一个vector的例子

istream_iterator<int> in_iter(cin);
istream_iterator<int> ieof; 
while(in_iter != eof)
    vec.push_back(*in_iter++);

对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或遇到IO错误，迭代器的值就和尾后迭代器相等。
可以将程序重写，体现其更有用的地方

istream_iterator<int> in_iter(cin), eof;
vector<int> vec(in_iter, eof);  /从迭代器范围构造vec

使用算法操作流迭代器

可以用某些算法来操作流迭代器。如accumulate:

istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl;

如果输入为:

23 109 45 89 6 34 12 90 34 23 56 23 8 89 23

则输出为664

istream_iterator允许使用懒惰求值

istream_iterator绑定到流，不保证迭代器立即从流读取数据。
具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。

ostream_iterator

可以对具有输出运算符(<<)的类型定义
可以提供第二参数，一个字符串(c风格)，在输出每个元素后都会打印
必须中绑定到一个指定的流，不允许空的或者表示尾后位置的ostream_iterator
例：输出值的序列

ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
    *out_iter++ = e;
cout << endl;

将vec中每个元素写的cout，并且在后面加一个空格。
向out_iter赋值时可以忽略解引用和递增运算

//可以重写
for (auto e : vec)
    out_iter = e;
cout << endl;

推荐第一个写法，对迭代器的使用保持一致

可以通过copy来打印vec中的元素

copy(vec.begin(), vec.end(), out_iter);
cout << endl;

使用流迭代器处理类类型

重写书店程序

istream_iterator<Sales_item> item_iter(cin), eof;
ostream_iterator<Sales_item> out_iter(cout, "
");
//将第一个笔交易记录存在sum中，并读取下一条记录
Sales_item sum = *item_iter++;
while (item_iter != eof)
{
    if(item_iter->isbn() == sum.isbn())
        sum += *item_iter++;        //将其加到sum上并读取下一条记录
    else
    {
        out_iter = sum;         //输出sum当前值
        sum = *item_iter++;     //读取下一条记录
    }
}
out_iter = sum;

可以用item_iter读取第一条交易记录，用它的值来初始化sum:

Sales_item sum = *item_iter++;

反向迭代器

在容器中从尾元素向首元素反向移动的迭代器。
++it会移动到前一个，--it会移动到下一个
除了forwrad_list其他都支持反向迭代器。
使用rbegin、rend、crbegin、crend来获取

例：逆序打印vec

vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
for(auto r_iter = vec.crbegin();
         r_iter != vec.crend();
        ++r_iter)
    cout << *r_iter << endl;

也可以改变sort的顺序

sort(vec.begin(), vec.end());
sort(vec.rbegin(), vec.rend());

反向迭代器需要递减运算符，因此不可能从一个forwrd_list或一个流迭代器创建一个反向迭代器

反向迭代器和其他迭代器的关系

假定一个string名为line,保存着一个逗号分割的单词列表。
打印line中的第一个单词

auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;

打印最后一个单词

auto rcomma = find(line.crbegin(), line.crend(), ',');

如果使用

cout << string(line.crbegin(), rcomma) << endl;

输入LAST会打印TSAL
正确的方法是把rcomma转换为一个普通迭代器

cout << string(rcomma.base(), line.cend()) << endl;

10.5泛型算法结构

任何算法最基本的特性就是要求其迭代器提供哪些操作。
可以分为5类：

输入迭代器： 只读不写，单遍扫描，只能递增
输出迭代器：只写不读，单遍扫描，只能递增
前向迭代器：可读写，多遍扫描，只能递增
双向迭代器：可读写，多遍扫描，可递增递减
随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算

输入迭代器

必须支持：
1、用于比较的==和!=
2、用于推进的前置和后置递增运算++
3、用于读取元素的解引用运算*
4、箭头运算符->

输入迭代器只用于顺序访问。对于一个输入迭代器，*it++保证有效，但递增导致所有其他指向流的迭代器失效，结果就是不能保证输入迭代器的状态可以保存下来并用来访问元素。
因此只能用于单遍扫描算法，如find和accumulate
istream_iterator是一种输入迭代器

输出迭代器

输入迭代器功能上的补集：只写而不读元素
必须支持：
1、用于推进的前置和后置递增运算++
2、解引用运算*
只能向一个输出迭代器赋值一次。
只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器。
copy的第三个参数就是输出迭代器
ostream_iterator也是输出迭代器

前向迭代器

只能在序列中沿一个方向移动。支持所有输入和输出的操作，并且可以多次读写同一个元素。
可以保存迭代器状态，可以多遍扫描。
replace要求前向迭代器
forward_list上的迭代器是前向迭代器

双向迭代器

可以正反向读写序列中的元素。
除了支持所有前向迭代器的操作以外，还支持前置和后置递减--
reverse要求双向迭代器。
除了forward_list外，其他标准库都提供双向迭代器

随机访问迭代器

提供常量时间内访问序列中任意元素的能力。
除了双向迭代器的所有功能，还提供了：
1、比较相对位置的关系运算符< <= > >=
2、迭代器和整数值的加减运算(+ += - -=),计算结果是相对位置
3、用于两个迭代器的减法--，得到距离
4、下标运算符iter[n]

算法sort要求随机访问迭代器
array,deque,string,vector的迭代器是随机访问迭代器

算法形参模式

大多数算法具有如下四种形式：

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);

其中alg是算法名字，beg和end表示算法所操作的输入范围。
dest是指定的位置

接受单个迭代器的算法

dest参数是一个表示算法可以写入目的位置的迭代器。算法假定：按其需要写入数据，不管写入多少个元素都是安全的。
如果dest是直接指向容器的迭代器，那么输出数据写道容器中已存在的元素内
如何dest绑定到一个插入迭代器或ostream_iterator.则会添加新元素到容器。

接受两个输入序列的算法

一般用来表示一个范围

算法命名规范

除了参数规范，算法还遵循一套命名和重载规范。

一些算法使用重载形式传递一个谓词

接受谓词参数来代替<或==运算符的算法，以及不接受额外参数的算法，通常都是重载的函数。
一个版本用运算符，一个版本用谓词

unique(beg, end);   //用==bijn
unique(beg, end, comp); //用comp比较元素

_if的版本

接受一个谓词代替元素值的版本

find(beg, end, val);        //查找val第一次出现的位置
find(beg, end, pred);       //查找第一个令pred为真的元素

拷贝元素的版本和不拷贝的版本

拷贝版本一般在后面加上_copy

reverse(beg, end);              //直接翻转输入范围中的元素
reverse_copy(beg, end, dest);   //将元素按逆序拷贝到dest

还有些算法同时提供_copy和_if版本

//将偶数元素从输入范围拷贝到v2中
remove_copy_if(v1.begin, v1.end, back_inserter(v2),
                [](int i ) {return i % 2;});

10.6 特定容器算法

list和forward_list定义了几个成员函数形式的算法。
主要有sort、merge、remove、reverse、unique。
性能比通用版本好得多

splice成员

见表10.7，用于移动

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

特有版本和通用版本的区别在于：链表版本会改变底层的容器