迫于拙劣的cpp水平，这次来记录一些关于STL算法部分的内容。
参考内容是CS106L的course reader
Iterator Categories#
Iterators分为以下五种：
- Output Iterators：可以使用
++；可以用*myItr = value，不能用value = *myItr - Input Iterators：可以使用
++；可以用value = *myItr，不能用*myItr = value - Forward Iterators：可以使用
++，可以同时用value = *myItr和*myItr = value - Bidirectional Iterators：比起 Forward Iterator 多了
--，但是不能+或者+= - Random-Access Iterators：比起 Bidirectional Iterators 多了
+和+=
Algorithm Naming Conventions#
一些关于STL Algorithm的命名规则
后缀_if表示只有当满足一定条件的时候该算法才会执行一定任务。
比如：
1bool IsEven(int value) {
2return value % 2 == 0;
3}
4cout << count_if(myVec.begin(), myVec.end(), IsEven) << endl;_n表示执行一个特定的操作n次。
比如：
1fill_n(myDeque.begin(), 10, 0);Reordering Algorithms#
- sort：传入的必须是 Random-Access Iterators，记得定义
<函数。 - random_shuffle：传入的必须是 Random-Access Iterators，作用是将一个区间内的元素打乱重排。可以在使用之前先使用 srand 函数。
- rotate：作用是循环改变容器中元素的顺序。
rotate(v.begin(), v.begin() + 2, v.end())会让(0, 1, 2, 3, 4, 5)变为(2, 3, 4, 5, 0, 1)。
Searching Algorithms#
- find：三个参数，前面两个迭代器表示寻找的范围，第三个参数表示要找的值。返回第一个该值所在的位置的迭代器，或者返回第二个迭代器（如果没找到）。
- binary_search：需要有序；返回某个值是否在一个范围内。
- lower_bound：需要有序；返回大于等于某值的第一个位置的迭代器。
**需要注意的是，如果某个容器本身有和 STL algorithm 同名的成员函数（比如 set 的 find），那么优先使用该容器的成员函数。**原因是 STL Algorithm 需要具有普适性，不会针对特定容器优化。因此对于 set 来说，其成员函数 find 的复杂度是 logn 的，而 STL algorithm 的 find 是 O(n) 的复杂度。
Iterator Adaptors#
具有 Iterator 的性质，但是比 Iterator 更强..
比如 ostream_iterator
通过 copy(myVector.begin(), myVector.end(), ostream_iterator<int>(cout, " ")); 可以直接将一个容器中的元素输出。
比如 insert_iterator，对于要从一个容器拷贝元素到另一个容器，但是在编写代码时不知道源容器的元素有多少个的问题，可以很好解决？
1set<int> result;
2set_union(setOne.begin(), setOne.end(),
3// All of the elements in setOne
4setTwo.begin(), setTwo.end(),
5// All of the elements in setTwo
6inserter(result, result.begin())); // Store in result.
Removal Algorithms#
需要注意的是并没有真的 remove，而是将 “remove” 的元素放在了容器后面（？），原因是 STL Algorithms 接受的是 Iterator，而不是 Container。
Other Noteworthy Algorithms#
- transform：四个参数，前两个迭代器表示要变换的范围，第三个迭代器表示结果的开始位置，第四个参数为一个函数，表示将该范围的每个元素经过该函数的处理。不要求结果和原始的数据类型相同。
- min_element：两个迭代器表示一个范围，返回该范围中最小元素的迭代器；可以有第三个参数来自定义小于关系。max_element 与之类似。
- accumulate：
template< class InputIt, class T > T accumulate( InputIt first, InputIt last, T init ); - inner_product：求内积；
T inner_product( InputIt1 first1, InputIt1 last1, InputIt2 first2, T value ); - distance：两个参数，表示这两个迭代器之间元素的个数。