[GeekBand][STL与泛型编程]第二周笔记

Tips：

算法 Algorithm 是 function template.
Algorithms 看不见 Containers，对其一无所知。所以，它所需要的一切信息都必须从 Iterators 取得。而 Iterators (由 Containers 供应)必须能够回答 Algorithm 的所有提问，才能搭配该 Algorithm 的所有操作。
Algorithm 的一般形式
A.

template<typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
    …
}

template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
    …
}

Algorithms 和 Iterators 之间沟通需要通过 iterator_traits 。确保 Iterators 不是 class 时也能正常运件运作。

1. 迭代器的分类

五种 iterator category

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag :public input_iterator_tag {};
struct bidirectional_iterator_tag :public forward_iterator_tag {};
struct random_access_iterator_tag :public bidirectional_iterator_tag {};

它们之间的关系

2. 算法举例

算法 accumulate

算法 accumulate

算法 accumulate 对元素执行累计动作。
算法 for_each

算法 for_each

算法 for_each 对每个元素执行同一个动作。
该算法可用 range-based for statement (Since C++11)代替：

for (decl : coll)
{
    statement
}

算法 replace，replace_if，replace_copy

算法 replace

算法 replace_if

算法 replace_copy
算法 count，count_if

算法 count，count_if

容器成员函数整理
算法 find，find_if

算法 find，find_if

容器成员函数整理
算法 sort

算法 sort 使用

容器成员函数整理
关于 reverse iterator，rbegin()，rend()

关于 reverse iterator，rbegin()，rend()

iterator adapter
算法 binary_search

算法 binary_search