【C++】泛型算法（五）：泛型算法结构与特定容器算法

10.5 泛型算法结构

10.5.1 5 类迭代器

类似于容器，迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另外一些只有特定类别的迭代器才支持。例如 ostream_iterator 只支持递增、解引用和赋值。vector、string 和 deque 的迭代器除了这些操作外，还支持递减、关系和算术运算。

迭代器类别

输入迭代器（Input Iterator）

输入迭代器可以读取序列中的元素。一个输入迭代器必须支持：

• 比较两个迭代器相等和不相等的运算符；
• 推进迭代器的前置和后置递增运算符；
• 用于读取元素的解引用运算符；
• 箭头运算符；

输入迭代器只用于顺序访问。

输出迭代器（Output Iterator）

可以看作是输入迭代器功能上的补集——只写而不读元素。输出迭代器必须支持：

• 推进迭代器的前置和后置递增运算符；
• 解引用运算符；

输出迭代器的一个例子是 ostream_iterator，copy 泛型函数的第三个参数也是输出迭代器。

前向迭代器（Forward Iterator）

可以读写元素。这类迭代器只能在序列中沿着一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，且可以多次读写同一个元素。

双向迭代器（Bidirectional Iterator）

可以正向/反向读写序列中的元素。

随机访问迭代器（Random-access Iterator）

提供在常量时间内访问序列中任意元素的能力。

10.5.2 算法形参模式

10.5.3 算法命名规范

10.6 特定容器算法

通用版本的 sort 要求随机访问迭代器，因此不能用于 list 和 forward_list 两种容器。

链表类型 list 和 forward_list 定义了几个成员函数形式的算法。它们定义了独有的 sort、merge、remove、reverse 和 unique。

splice 成员

链表类型还定义了 splice 算法。该算法是链表数据结构独有的。

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

链表特有版本的算法与通用版本间最重要的区别是链表版本可能会改变底层的容器。例如，remove 的链表版本会删除指定的元素，而 unique 的链表版本会删除第二个和后继的重复元素（而普通版本的 unique 是返回一个迭代器，它是非重复元素的尾后迭代器，需要使用 erase 删除返回迭代器与原始容器的尾后迭代器之间的迭代器范围才能完成真正意义上的去重操作）。

类似地，merge 和 splice 会销毁其参数。