C++ STL Algotithms 学习笔记

迫于拙劣的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：两个参数，表示这两个迭代器之间元素的个数。