第10章 泛型算法

• 泛型算法（通用）：可用于不同类型的容器和不同类型的元素
• 泛型算法 迭代器
• 顺序容器定义操作：添加/删除元素、访问首尾元素、确定容器是否为空、获得指向首元素或尾元素之后位置的迭代器
• 其他有用操作：查找特定元素、替换/删除特定值、重排元素顺序
• 泛型算法：经典算法公共接口(如排序和搜索)，可用于不同类型的元素和多种容器类型（标准库类型、内置数组、）以及其他的序列

---

10.1 概述

• 头文件algorithm：大多数算法；头文件numeric：数值泛型算法
• 不直接操作容器，遍历由两个迭代器指定的一个元素范围
• find(vec.cbegin(),vec.cend(),val)
  • 前两个参数表示元素范围的迭代器，第三个参数为一个值
  • 将范围内的每个元素与给定值进行比较，返回第一个等于给定值的元素的迭代器
  • 若范围内无匹配参数，返回第二个参数表示搜索失败
  • 可通过比较返回值和第二个参数来判断搜索是否成功
  • 操作的是迭代器，可在任何容器中查找值，也可在数组中查找值
• 算法是如何工作的
  • find在一个未排序的元素序列中查找一个特定元素（不依赖容器类型）
    • 1. 访问序列首元素
    • 2. 比较该元素与查找值
    • 3. 若与查找值匹配，返回标识此元素的值
    • 4. 否则前进到下一元素，重复2和3
    • 5. 如达序列尾，停止
    • 6. 达序列尾，返回一个指出元素未找到的值（与3返回值具相容类型）
• 迭代器令算法不依赖于容器，但仍依赖于元素的操作类型
  • find除步骤外都可用迭代器操作来实现
    • 解引用迭代器，实现元素访问
    • 发现匹配元素，返回指向该元素的迭代器
    • 迭代器递增移动到下一元素
    • 尾后迭代器可用于判断find是否到达序列尾
    • 返回尾后迭代器表示未找到给定元素
  • 但大多数算法都使用了一个或多个元素类型上的操作
    • 如find用==运算符完成每个元素与给定值的比较
    • 其他算法可能要求元素类型支持<运算符
    • 允许使用自定义操作来代替默认运算符
• 泛型算法永远不会执行容器的操作
  • 只会运行于迭代器之上，执行迭代器操作
  • 算法永远不会改变底层容器的大小
    • 可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素
  • 标准库特殊迭代器：插入器
    • 当给该类迭代器赋值时，会在底层的容器上执行插入操作
    • 迭代器可完成向容器添加元素的效果，但算法自身永远不会做这样的操作

---

10.2 初始泛型算法

• 标准库定义超100个算法，算法有一致的结构，统一原则
• 除少数列外，标准库算法都对一个范围内（输入范围；前两个参数，要处理的第一个元素以及尾元素之后位置的迭代器）的元素进行操作
• 遍历输入范围的方式相似，但使用范围中元素的方式不同
  • 是否读取元素、改变元素、或重排元素

10.2.1 只读算法

• 读取输入范围内元素，从不改变元素，如find、accumulate
  • accumulate定义于头文件numeric
  • 接受三个参数，前两个指出求和元素范围，第三个参数是和的初值
  • 第三个参数的类型决定函数使用哪个加法运算符以及返回值类型
• 算法和元素类型
  • accumulate第三个参数作为求和起点，蕴含编程假定
    • 将元素类型加到和的类型上的操作必须是可行的（序列元素类型须与第三个参数匹配，或能转换为第三个参数的类型）
      • 如char*上没有定义+运算符，所以第三个参数不能为字符串字面值"“，而应该显示创建一个string(”")
  • 对于只读取而不改变元素的算法，最好使用cbegin()和cend()
  • 如需使用算法返回的迭代器改变元素的值，需使用begin()和end()
• 操作两个序列的算法
  • 只读算法equal：用于确定两个序列是否保存相同的值
    • 将第一个序列中的每个元素与第二个序列中的对应元素进行比较
    • 如所有对应元素都相等则返回true,否则返回false
    • 算法接受三个迭代器，前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素。第二个序列至少应该与第一个序列一样长，假定第一个序列中每个元素在第二个序列中都有一个与之对应的元素
    • 可用于比较两个不同类型的容器中的元素，而且元素类型也不必相同，只要能用==来比较两个元素类型即可
  • 对于只接受一个单迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长

10.2.2 写容器元素的算法

• 将新值赋予序列中的元素，确保序列原大小不小于不小于要求算法写入的元素数目（算法不会执行容器操作，自身不可能改变容器大小）
• 一些算法会自己向输入范围写入元素，最多写入与给定序列一样多的元素
  • fill 接受一对迭代器表示一个范围（需传递有效输入序列），接受一个值作为第三个参数，将这个值赋予序列中的每一个元素
• 迭代器参数
  • 算法从两个序列中读取元素时，构成两个序列的元素可来自不同类型容器，两序列元素类型不严格要求匹配，只需要能够比较两个序列中的元素
  • 操作两个序列区别：如何传递第二个序列
    • 接受3个迭代器：前两个表示第一个序列的范围，第三个表示第二个序列首元素
    • 接受4个迭代器：前两个表示第一个序列的范围，后两个表示第二个序列的范围
  • 用一单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长
• 算法不检查写操作
  • 接受一个迭代器作为单独目的位置，算法将新值赋予一个序列中的元素，序列从目的位置迭代器指向的元素开始
    • fill_n：将给定值赋予迭代器指向的元素开始的指定n个元素(须确保迭代器指向的序列至少包含n个元素)
    • 向目的位置写入数据的算法假定目的位置足够大，能容纳要写入的元素
• 介绍back_inserter
  • 使用插入迭代器（向容器中添加元素的迭代器）可保证算法有足够元素空间
  • 通过迭代器向容器元素赋值，值被赋予迭代器指向的元素
  • 插入迭代器赋值，一个与赋值号右侧相等的元素被添加到容器中
  • back_inserter，定义于头文件iterator
    • 接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器
    • 通过迭代器赋值，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中
• 拷贝算法
  • 拷贝（copy）算法向目的位置迭代器指向的（新）输出序列写入数据的算法
  • 接受三个迭代器参数，前两个表示一个输入范围，第三个表示目的序列的起始位置，将输入范围中的元素拷贝到目的序列中（目的序列须至少包含与输入序列一样多的元素）
  • copy返回目的位置迭代器（递增后）的值
  • 多个算法提供“拷贝”版本，加_copy后缀
    • replace(ilist.begin(),ilist.end(),要搜索的值a,值a要替换成的值b)；会直接改变原序列
    • replace_copy(ilist.begin(),ilist.end(),back_inserter(ivec),要搜索的值a,值a要替换成的值b)；不改变原序列，将改变后新值序列写入ivec

10.2.3 重排容器元素的算法

• sort 重排元素算法，利用<运算符来实现
• 消除重复单词
  • 先利用sort排序
  • 再使用unique标准库算法重排vector,使不重复的元素出现在vector开始部分，返回指向不重复区域位置之后一个位置的迭代器
  • 使用vector成员函数erase删除尾部重复单词
• 使用unique
  • 重排输入序列，将相邻重复项“消除”，返回一个指向不重复值范围末尾的迭代器
  • 容器大小未改变，元素顺序被改变，覆盖相邻重复元素，使不重复元素出现在序列开始部分，返回最后i一个不重复元素之后的位置。此位置后元素仍然存在，但我们不知道他们的值
• 标准库算法对迭代器而不是容器进行操作，算法不能（直接）添加/删除元素
• 使用容器操作删除元素
  • 接受两个迭代器表示要删除元素的范围[左闭右开),迭代器相等意味着元素范围为空，删除空范围没有什么不良后果，因此程序即使输入无重复元素调用unique后再erase也是正确的

---

10.3 定制操作

• 以下情况需，重载算法（如比较元素用<或==）的默认行为
  • 允许提供自定义操作来代替默认运算符
  • 序列保存的是未定义<运算符的元素类型

10.3.1 向算法传递参数

• 如 希望序列按单词长度排序，大小相同的再按照字典排序
  • 重载sort版本，接受第三个参数（一个谓词）
• 谓词
  • 可调用的表达式，返回结果是一个能用作条件的值
  • 一元谓词：只接受单一参数
  • 二元谓词：有两个参数
  • 接受谓词的算法对输入序列中的元素调用谓词，元素类型必须能转换为谓词的参数类型
    • 接受二元谓词参数的sort版本用谓词来代替<比较元素
    • 此操作必须在输入序列中所有可能的元素值上定义一个一致的序
• 排序算法
  • stable_sort算法：稳定排序算法维持相等元素的原有位置
• partition算法
  • 接受一个谓词，对容器内容进行划分，使谓词为true的值排在容器前半部分，使谓词为false的值排在后半部分。返回一个迭代器，指向最后一个使谓词为true的元素之后的位置

10.3.2 lambda表达式

• 谓词只能严格接受一个或两个参数
• find_if算法查找第一个具有特定特定大小的元素
  • 接受一对迭代器表示一个范围
  • 第三个参数是一个谓词，序列范围内每个元素调用谓词，
  • 返回第一个使谓词返回非0值的元素，如不存在这样的元素，返回尾迭代器
• 介绍lambda
  • 可以向一个算法传递任何类别的可调用对象
  • 可调用的：一个对象/表达式，可以对它使用调用运算符（）
  • 可调用对象
    • 函数、函数指针、重载了函数调用运算符的类、lambda表达式
  • 一个lambda表达式（可理解为一个未命名的内联函数）
    • 表示一个可调用的代码单元
    • 一个lambda表达式具有一个返回类型、一个参数列表、一个函数体
    • 与函数不同，lambda可能定义在函数内部
  • [capture list](parameter list)->return type{function body}
    • [capture list] 捕获列表是一个lambda所在函数中定义的局部变量的列表(通常为空)
    • (parameter list) 参数列表
    • ->return type 返回类型，必须使用尾置返回
    • {function body}函数体
    • 可忽略参数列表和返回类型，但必须永远包含捕获列表和函数体
  • auto f=[]{return 42;} 定义了函数对象f,不接受参数
    • 调用方法，使用调用运算符，f()
    • 忽略括号和参数列表等价于指定一个空参数列表
    • 忽略返回类型时（未指定返回类型），可根据函数体中代码推断出返回类型
      • 如函数体只是一个return语句，则返回类型从返回的表达式的类型推断而来
      • 否则（除了return外还有别的内容等）返回类型为void
• 向lambda传递参数
  • 调用lambda给定的实参被用来初始化lambda的形参
  • 实参和形参的类型必须匹配
  • 不能有默认参数，调用实参数目与形参数目相等
  • 形参初始化完毕，执行函数体
• 使用捕获列表
  • lambda可出现在函数中，但只能使用明确指明的变量
  • 将局部变量包含在捕获列表中指出将会使用这些变量
  • 捕获列表[]，在其中提供一个以逗号分隔的名字列表，空捕获列表表示不使用lambda所在函数中的任何局部变量
• 调用find_if
  • 调用返回一个迭代器，指向第一个长度不小于给定参数（lambda返回为true）的元素
• for_each算法
  • 接受一个可调用的对象，并对输入序列中的每个元素调用此对象
  • 只对lambda所在函数中定义的变量（局部非static变量）使用捕获列表；lambda可直接使用定义在当前函数之外的名字（局部static变量/所在函数之外声明的名字）
• 完整的biggies
  • 按字典序排序，删除重复单词
  • 按长度排序，长度相同单词维持字典序
  • 获取一个迭代器it，指向第一个满足长度大于指定值的元素find_if
  • 计算长度大于指定值元素的个数end()-it
  • 打印长度大于指定值的元素 for_each(it,words.end(),[](const string &s){..})

10.3.3 lambda捕获和返回

• 定义一个lambda时编译器生成一与lambda对应的新的（未命名）类类型
  • 向一函数传递lambda时，同时定义了一个新的类型和该类型的一个对象
  • 传递的参数就是此编译器生成的类类型的未命名对象
  • 当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象
  • lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员（在lambda对象创建时被初始化）
• 值捕获
  • 类似于参数传递的值传递，前提是变量可以拷贝
  • 被捕获变量的值在lambda创建时拷贝（不是在调用时拷贝），随后对其修改不会影响到lambda内对应的值
• 引用捕获
  • 引用方式捕获的变量与其他任何类型的引用的行为类似（变量前加&）
  • 在lambda内使用此变量时，使用的是引用所绑定的对象
  • 采用引用方式捕获一个变量时，必须确保被引用的对象在lambda执行的时候是存在的（捕获的局部变量，在函数结束后就不复存在了）
  • 对于不能拷贝的对象如ostream，捕获os的唯一方法是捕获其引用
  • 从函数返回（可直接返回一个可调用对象）lambda或一个含有可调用对象的数据成员的类对象，则此lambda不能包含引用捕获（类似于函数不能返回一个局部变量的引用）
• 尽量保持lambda的变量捕获简单化
  • 捕获普通变量如int/string/其他非指针类型，通常可采用值捕获（关注捕获时是否为需要的值）
  • 捕获指针或迭代器采用引用捕获，确保lambda执行时，绑定到迭代器/指针/引用的对象仍然存在
  • 尽量减少捕获的数据量，避免潜在的捕获导致的问题，尽量避免捕获指针或引用
• 隐式捕获
  • 指示编译器推断捕获列表，在捕获列表中写&（引用捕获方式）或=（值捕获方式）
  • 若希望一部分采用值捕获方式，其他采用引用捕获方式，可混合使用隐式捕获和值捕获
    • 混合使用隐式捕获和显示捕获时，捕获列表中的第一个元素必须是一个&或=，指定了默认捕获方式为引用或值
    • 显式捕获的变量必须使用与隐式捕获不同的方式

	表10.1 lambda捕获列表
[]	空捕获列表。lambda不能使用所在函数中的变量。一个lambda只有在捕获变量后才能使用它们
[names]	names是一个逗号分隔的名字列表，这些名字都是在lambda所在函数的局部变量。默认情况下，捕获列表中的变量都被拷贝，名字前如果使用了&，则采用引用捕获方式
[&]	隐式捕获列表，采用引用捕获方式。lambda体中所使用的来自所在函数的实体都采用引用方式使用
[=]	隐式捕获列表，采用值捕获方式。lambda体将拷贝所使用的来自所在函数的实体的值
[&, identifier_list]	identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。identifier_list中的名字前面不能使用&
[=, identifier_list]	identifier_list中的变量采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。identifier_list中的名字不能包括this，且这些名字之前必须使用&

• 可变lambda
  • 捕获列表值拷贝变量一般lambda不会改变其值，当希望改变变量值时，须在参数列表后跟上关键字mutable，因此可变lambda可省略参数列表
  • 引用捕获的变量是否可变依赖于指向的变量是const类型还是非const类型
• 指定lambda返回类型
  • 只含单一return语句时，返回类型可以根据运算符的类型推断出来
  • 如lambda包含return之外的任何语句，编译器假定lambda返回void；被推断返回void的lambda不能返回值（类似返回void的函数），例如推断为void返回为int则会产生编译错误
  • 当需要为lambda定义返回类型时，必须使用尾置返回类型，在参数列表后跟上->type

10.3.4 参数绑定

• lambda表达式 用于只在一两个地方使用的简单操作

• 函数 需要在很多地方使用相同的操作/或需要很多语句才能完成

  • 如lambda的捕获列表为空，通常可用函数来代替它
  • 若lambda捕获列表不为空，函数传递形参个数限制问题（如只接受一元谓词的算法）

• 标准库bind函数

  • bind函数可看作 通用的函数适配器，接受一个可调用对象，生成一个新的可调用对象来适应原对象的参数列表
  • auto newCallable=bind(callable,arg_list);
    • newCallable可调用对象；arg_list逗号分隔的参数列表，对应于callable的参数；
    • 调用newCallable时，newCallable调用callable，并将arg_list中的参数传递给callable
    • arg_list参数为placeholders::_n的名字（n为整数），这些参数为占位符，占据了传递给newCallable参数的位置，数值n表示生成的可调用对象中参数的位置，_1为newCallable的第一个参数，_2为第二个参数

• 绑定check_size的sz参数

  • bind调用有几个占位符就表示newCallable接受几个参数，占位符出现在arg_list的第几个位置，表示newCallable的此参数对应callable的第几个参数

• 使用placeholders名字

  • std::placeholders::_n，placeholders命名空间与bind函数都定义于functional头文件
  • 对于每个占位符名字，我们都必须提供一个单独的using声明较为繁琐，可以使用using namespce namespace_name;说明希望所有来自namespace_name的名字都可以在程序中直接使用

• bind的参数

  • 可以用bin修正参数的值，也可以用bind绑定给定可调用对象中参数或重新安排其顺序
  • auto newCallable=bind(callable,arg_list);
    • 传递给callable的参数按照arg_list里的参数顺序
    • 传递给newCallable的参数则按照第一个参数绑定到bind()函数arg_list的占位符_1位置处，第二个参数绑定到bind()函数arg_list的占位符_2位置处，以此类推，传递给newCallable的第n个参数绑定到bind()函数arg_list的占位符_n位置处
    • 如auto g=bind(f,a,b,_2,c,_1);，映射到函数f为f(a,b,_2,c,_1);，调用g(x,y)实际会调用f(a,b,y,c,x);

• 用bind重排参数顺序

  • 可以用bind更改参数顺序，颠倒isShroter的含义
  • 如比较元素A和Bsort(words,begin(),words,end(),isShroter); isShroter(a,b)
  • sort(words,begin(),words,end(),bind(isShroter,_2,_1)); isShroter(b,a)

• 绑定引用参数

  • 默认情况下bind中不是占位符的参数被拷贝到bind返回的可调用对象中
  • 若希望传递给bind一个对象而又不拷贝它，就必须使用标准库ref函数
    • ref(对象)返回一个对象，包含给定对象的引用，此对象是可拷贝的
    • cref()生成一个保存const引用的类
    • ref()和cref()跟bind()一样都定义于functional头文件

• 向后兼容：参数绑定

  • bind1st bind2nd 分别只能绑定第一或第二个参数，已被弃用
  • 被弃用的特性：在新版本中不再支持的特性

---

10.4 再探迭代器

• 插入迭代器：迭代器被绑定到一容器上，可用来向容器插入元素
• 流迭代器：被绑定到输入或输出流上，可用来遍历所有关联的IO流
• 反向迭代器：迭代器向后而不是向前移动，除了foreward_list外的标准库容器都有反向迭代器
• 移动迭代器：迭代器移动其中的元素，而不是拷贝他们

10.4.1 插入迭代器

• 迭代器适配器，接受一容器，生成一迭代器，实现向给定容器添加元素
• 通过插入迭代器进行赋值时，迭代器调用容器操作来向给定容器的指定位置插入元素

	表10.2 插入迭代器操作
it=t	在it指定的当前位置插入值t。假定c是it绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用c.push_back(t)、c.push_front(t)、c.insert(t, p)，其中p是传递给inserter的迭代器位置
*it, ++it, it++	这些操作虽然存在，但不会对it做任何事情，每个操作都返回it

• 插入迭代器有三种类型，差异在于元素插入的位置
  • back_inserter 创建一个使用push_back的迭代器
  • front_inserter 创建一个使用push_front的迭代器
  • inserter 创建一个使用inserter的迭代器。函数接受第二个参数，为一个指向给定容器的迭代器；元素将被插入到给定迭代器所表示的元素之前；
  • 只有在容器支持push_back/push_front时才能使用back_inserter/front_inserter
  • inserter总是将元素插入到定迭代器所表示的元素之前；而front_inserter总是将元素插入到容器第一个元素之前，即每次插入的元素变成容器的新元素；front_inserter生成的迭代器会将插入的元素顺序颠倒过来，而back_inserter和inserter则不会

10.4.2 iostream迭代器

• istream_itertaor 读取输入流
• ostream_itertaor 向输出流写数据
• 流迭代器将他们对应的流当作一个特定类型的元素序列来处理，使用泛型算法从流对象读取数据以及向其写入数据
• istream_itertaor 操作
  • 创建一个流迭代器时，必须指定迭代器要读写的对象类型
  • istream_itertaor 使用>>来读取流，要读取的类型必须定义了输入运算符>>
  • 创建istream_itertaor时可以将其绑定到一个流，还可以默认初始化迭代器（创建了一个可以当作尾后值使用的迭代器）
    • istream_iterator<int> in_iter(cin),eof;
    • vector<int> vec(in_iter,eof);
  • 绑定到流的迭代器，一旦其关联的流遇到文件尾或遇到IO错误，迭代器的值就与尾后迭代器相等
  • vec.push_back(*in_iter++)后置递增运算会从流中读取下一个值，向前推进但返回迭代器的旧值，对迭代器解引用获取该值

	表10.3 istream_iterator操作
istream_iterator<T> in(is);	in从输入流is读取类型为T的值
istream_iterator<T> end;	读取类型是T的值的istream_iterator迭代器，表示尾后位置
in1 == in2	in1和in2必须读取相同类型。如果他们都是尾后迭代器，或绑定到相同的输入，则两者相等。
in1 != in2	⬆读取相同类型，但迭代器位置不同则不等
*in	返回从流中读取的值
in->mem	与*(in).mem含义相同
++in, in++	使用元素类型所定义的>>运算符从输入流中读取下一个值。前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值

• 使用算法操作流迭代器
  • accumulate(in,eof,0);
  • 从标准输入读取输入数值的和，第三个参数为求和起始值
• istream_iterator允许使用懒惰求值
  • 将一个istream_iterator绑定到流时，标准库不保证迭代器立即从流读取数据；
  • 实现时可推迟从流读取数据，直到使用迭代器时才真正读取
  • 标准库保证在第一次解引用迭代器前，从流中读取的操作已经完成
  • 读取顺序在以下2种情况下很重要
    • 创建了一个istream_iterator，还没有使用就销毁了
    • 正在从两个不同的对象同步读取一个流
• ostream_itertaor 操作
  • 对具有输出运算符<<的类型定义ostream_itertaor
  • 创建ostream_itertaor时，可提供（可选）第二参数（为字符串），在输出每个元素后都打印此字符串（须为C风格字符串，一个字符串字面常量/指向以空字符结尾的字符数组的指针）
  • 必须将ostream_itertaor绑定到一个指定的流，不允许空的或表示尾后位置的ostream_itertaor

	表10.4 ostream_itertaor操作
ostream_iterator<T> out(os);	out将类型为T的值写到输出流os中
ostream_iterator<T> out(os, d);	out将类型为T的值写到输出流os中，每个值后面都输出一个d。d指向一个空字符结尾的字符数组。
out = val	用<<运算符将val写入到out所绑定的ostream中。val的类型必须与out可写的类型兼容
*out, ++out, out++	这些运算符是存在的，但不对out做任何事情。每个运算符都返回out

• 可通过调用copy打印vec中的元素，比编写循环更简单
• 使用流迭代器处理类类型
  • 用流迭代器重写sales_item书店程序

10.4.3 反向迭代器

• 反向迭代器在容器中从原元素向首元素反向移动的迭代器
• 递增++it反向迭代器会移动到前一个元素，递减–it反向迭代器会移动到下一个元素
• 除了forward_list外都支持反向迭代器
• 可调用rbegin/rend/crbegin/crend成员函数来获得反向迭代器
• 成员函数返回指向容器尾元素和首元素之前一个位置的迭代器
• 反向迭代器也有const和非const版本
• 使用反向迭代器可逆序打印vec中的元素
• 反向迭代器需要递减运算符
  • 只能从既支持++也支持–的迭代器来定义反向迭代器
  • 反向迭代器目的是在序列中反向移动
  • forward_list和流迭代器不支持递减运算，因此不能从他们创建反向迭代器
• 反向迭代器和其他迭代器间的关系
  • 反向迭代器会反向朝着string的开始位置移动
  • 调用reverse_iterator的base()成员可将反向迭代器转换返回其对应的普通迭代器（一般指向反向迭代器的下一个元素）；rcommon/crbegin和rcommon.base()/cend()指向不同的元素（相邻的位置），保证了元素范围无论是正向处理还是反向处理都是相同的
  • 普通迭代器与反向迭代器的关系反映了左闭合区间的特性
    • [line.crbegin(),rcomma)和[rcomma,base(),line.cend())指向line中相同的元素范围
  • 反向迭代器目的：表示元素范围，范围不对称
    • 当使用一个普通迭代器初始化一个反向迭代器，或给一个反向迭代器赋值时，结果迭代器与原迭代器指向的并不是相同的元素

---

10.5 泛型算法结构

• 算法基本特性：要求迭代器提供哪些操作
  • find:要求通过迭代器访问元素、递增迭代器以及比较两个迭代器是否相等
  • sort:读、写和随机访问元素的能力
  • 算法所要求的迭代器操作可以分为5个迭代器类别
    • 每个算法都会对它的每个迭代器参数指明提供哪类迭代器

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

• 第二种分类方式：按照是否读、写或是重排序列中的元素来分类
• 算法还共享一组参数传递规范和一组命名规范

10.5.1 5类迭代器

• 迭代器定义公共操作
  • 一些操作所有迭代器都支持，另外一些只有特定类型迭代器才支持
  • ostream iterator只支持递增、解引用和赋值
  • vector、string、deque除支持这些外，还支持递减、关系和算术运算
• 迭代器按所提供操作来分类，分类形成了一种层次
  • 除输出迭代器外，一个高层次类别的迭代器支持低层次类别迭代器的所有操作
• c++标准指明泛型和数值算法的每个迭代器参数的最小类别
  • 对每个迭代器参数来说，其能力必须与规定的最小类别至少相当
  • 向算法传递一个能力更差的迭代器会产生错误（很多编译器不会给任何警告或提示）
• 迭代器类别
  • 输入迭代器：可读取序列中的元素，迭代器须支持
    • 1. 用于比较两个迭代器的相等和不相等运算符（==,!=）
    • 2. 推进迭代器的前置后后置递增运算符(++)
    • 3. 读取元素的解引用运算符(*);*只出现在赋值运算符的右侧
    • 4. 箭头运算符(->)，等价于(*it).member;解引用迭代器并提取对象成员
    • 只能用于顺序访问；*it++保证有效，但递增导致所有指向流的迭代器失效，不能保证输入迭代器的状态可以保存下来并用于访问元素；只能用于单遍扫描算法
    • （如istream_iterator）
  • 输出迭代器：只写而不读元素（可看作输入迭代器补集），须支持
    • 1. 用于推进迭代器的前置后后置递增运算符(++)
    • 2. 读取元素的解引用运算符(*);*只出现在赋值运算符的左侧（向已解引用输出迭代器赋值，就是将值写入它所指向的元素）
    • 只能向输出迭代器赋值一次（单遍扫描）
    • 用作目的位置的迭代器通常都是输出迭代器
    • （如ostream_iterator）
  • 前向迭代器：可读写元素，只能在序列中沿着一个方向移动
    • 支持所有输入和输出迭代器的操作，可多次读写同一个元素（可保存前向迭代器状态多遍扫描）
    • （如forward_list上的迭代器；replace也要求前向迭代器）
  • 双向迭代器：可正向/反向读写序列中元素，支持所有前向迭代器操作外，支持
    • 1. 前置/后置递减运算符(–)
    • (reverse要求双向迭代器，除forward_list其他标准库都提供扶符合双向迭代器要求的迭代器)
  • 随机访问迭代器：常量时间内访问序列任意元素的能力；支持双向迭代器所有功能，还支持
    • 1. 比较两迭代器相对位置的关系运算符(<,<=,>,>=)
    • 2. 迭代器和整数值加减运算(+,+=,-,-=),计算结果为迭代器在序列中前进（或后退给定整数个元素后的位置）
    • 3. 用于两个迭代器上的减法运算符（-），得到两个迭代器的距离
    • 4. 下标运算符（iter[n]),与(iter[n])等价
    • （sort算法要求随机访问迭代器；array,deque,strng,vector迭代器都是随机访问迭代器；用于访问内置数组元素的指针）

10.5.2 算法形参模式

• 参数规范（在任何其他算法分类之上）

  • 通过理解参数含义，将注意力集中在算法所做的操作上

• 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、beg2、end2都是迭代器参数

  • 指定目的位置、第二个迭代器范围

• 有些算法还接受额外的、非迭代器的特定参数

• 接受单个目标迭代器的算法（dest）

  • dest表示算法可写入的目的位置的迭代器；算法假定按需写入，不管写入多少都是安全的（目标空间足够容纳写入的数据）
  • dest直接指向容器的迭代器，算法将输出数据写到容器中已存在的元素内
  • dest被绑定到一个插入迭代器/ostream_iterator，插入迭代器会将新元素加入到容器中，可确保空间是足够的；ostream_iterator会将数据写入输出流，不管要写入多少元素都没问题

• 接受第二个输入序列的算法

  • 接受beg2、end2表示第二个输入范围
  • 通常使用第二个范围中的元素与第一个输入范围结合来进行运算
  • [beg,end)第一个范围 [beg2,end2)第二个范围
  • 如只接受单独beg2(不接受end2),算法将beg2作为第二个输入范围中的首元素，范围结束位置未指定；算法假定beg2开始的范围与[beg,end)所表示的范围至少一样大

10.5.3 算法命名规范

• 参数规范、命名/重载规范
  • 1. 如何提供一默认操作代替默认的<或==运算符
  • 2. 算法是将输出数据写入输入序列还是一个分离的目的位置等
• 一些算法使用重载形式传递一个谓词
  • 接受谓词代替<或==，以及不接受额外参数的算法，通常都是重载的函数
  • 一个版本用元素类型运算符比较元素；另一个版本接受额外谓词参数来代替<或==
  • 由于两个版本在参数个数上不相等，因此具体调用哪个版本不会产生歧义
• _if版本的算法
  • 该版本接受一个谓词代替元素值，算法都附加有_if的后缀
  • 一个在输入范围内查找特定元素首次出现位置；_if版查找使得谓词返回非零值的元素
  • 算法提供命名上的差异版本而不是重载，是因为算法接受参数相同，避免产生重载歧义
• 区分拷贝元素的版本和不拷贝元素的版本
  • 默认 重排元素的算法将重排后的元素写回给定序列
  • 提供另外一个版本 将元素写入到指定输出目的位置，该版本在算法名后加上_copy后缀
  • 一些算法同时提供_copy_if版本，接受一个目的位置迭代器和一个谓词

---

10.6 特定容器算法

• 链表类型list和forward_list定义了几个成员函数形式的算法
  • 如独有的 sort/merge/remove/reverse/unique
  • 通用算法可用于链表，但代价太高需交换输入序列元素；链表版本可通过改变元素间的链接而不是真正交换他们的值来快速交换元素，性能更好；
  • 应优先使用链表成员函数版本而不是通用算法

	表10.6 list和forward_list成员函数版本的算法
	这些操作都返回void
lst.merge(lst2)	将来自lst2的元素合并入lst，lst2和lst都必须是有序的，元素将从lst2中删除。在和并之后，lst2变为空。该版本使用<运算符
lst.merge(lst2, comp)	⬆ 该版本使用给定的比较操作
lst.remove(val)	调用erase删除掉与给定值相等(==)的每个元素
lst.remove_if(pred)	调用erase删除掉令一元谓词为真的每个元素
lst.reverse()	反转lst中元素的顺序
lst.sort()	使用<排序元素
lst.sort(comp)	使用给定比较操作排序元素
lst.unique()	调用erase删除同一个值的连续拷贝。使用==
lst.unique(pred)	调用erase删除同一个值的连续拷贝。使用给定的二元谓词

• splice成员
  • 链表数据结构所特有

	表10.7 list和forward_list的splice成员函数版本的参数
	lst.splice(args)或flst.splice_after(args)
(p, lst2)	p是一个指向lst中元素的迭代器，或者一个指向flst首前位置的迭代器。函数将lst2中的所有元素移动到lst中p之前的位置或是flst中p之后的位置。将元素从lst2中删除。lst2的类型必须和lst相同，而且不能是同一个链表。
(p, lst2, p2)	同上，p2是一个指向lst2中位置的有效的迭代器，将p2指向的元素移动到lst中，或将p2之后的元素移动到flst中。lst2可以是与lst或flst相同的链表。
(p, lst2, b, e)	b和e表示lst2中的合法范围。将给定范围中的元素从lst2移动到lst或flst。lst2与lst（或flst）可以是相同的链表，但p不能指向给定范围中元素

• 链表特有操作会改变容器
  • 多数链表算法都与其通用版本相似但不完全相同
  • 链表版本会改变底层容器
    • remove链表版本会删除指定元素
    • unique链表版本会删除第二个和后继的重复元素
    • merge和splice会销毁其参数
      • 通用版本merge将合并序列写入目标迭代器，两输入序列不变
      • 链表版本merge销毁给定链表元素从参数指定链表删除，被合并调用merge的链表对象中；两链表中元素仍存在，但已在同一个链表中

---

小结

• 标准库定义约100个类型无关对输入序列进行操作的算法
  • 序列可为：标准库容器；内置数组；或通过读写流生成的
  • 算法在迭代器上进行操作来实现类型无关
  • 多数算法前两个参数是一对迭代器，表示一个元素范围
  • 额外迭代器参数可能包括
    • 目的位置的输出迭代器
    • 或表示第二个输入范围的另一个或一对迭代器
• 根据支持操作不同，可将迭代器分为5类
  • 输入、输出、前向、双向、随机访问迭代器
  • 如果一迭代器支持某个迭代器类别所要求的操作，则属于该类别
• 传递给算法的迭代器参数也按照所要求操作进行分类
  • 仅读取序列只要求输入迭代器操作
  • 写入数据到目的位置迭代器算法只要求输出迭代器
• 算法从不直接改变所操作序列的大小，会将元素从一个位置拷贝到另一个位置，但不会直接添加或删除元素
• 算法不能向序列添加元素，但插入迭代器可以；将插入迭代器绑定到一个容器上，将一个容器元素类型的值赋予插入迭代器，迭代器会将该值添加到容器中
• 容器list和forward_list对一些通用定义了自己特有的版本，会修改给定的链表

---

术语表

• 可调用对象：可以出现子啊调用运算符左边的对象。函数指针、lambda以及重载了函数调用运算符的类都是可调用对象
• 泛型算法：与类型无关的的算法
• 插入器：迭代器适配器，接受一个迭代器和一个指向容器的引用，生成一个插入迭代器，该插入迭代器在给定迭代器指向的元素之前的位置添加元素
• 移动迭代器：迭代器适配器，生成一个迭代器，该迭代器移动而不是拷贝元素
• 谓词：返回可以转换为bool类型的值的函数
• 一元谓词：接受一个参数的谓词
• ref：从一个指向不可拷贝类型的对象的引用生成一个可拷贝对象
• cref：返回一个可拷贝对象，保存了一个指向不可拷贝类型的对象的const对象的引用
• base()：调用reverse_iterator的base()成员可将反向迭代器转换返回其对应的普通迭代器