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表示只有当满足一定条件的时候该算法才会执行一定任务。

比如:

1    
2    bool IsEven(int value) {
3    return value % 2 == 0;
4    }
5    cout << count_if(myVec.begin(), myVec.end(), IsEven) << endl;

_n表示执行一个特定的操作n次。

比如:

1    fill_n(myDeque.begin(), 10, 0);
2

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 alogithm的find是O(n)的复杂度。

Iterator Adaptors

具有Iterator的性质,但是比Iterator更强..

比如ostream_iterator

通过copy(myVector.begin(), myVector.end(), ostream_iterator(cout, " ")); 可以直接将一个容器中的元素输出。

比如insert_iterator,对于要从一个容器拷贝元素到另一个容器,但是在编写代码时不知道源容器的元素有多少个的问题,可以很好解决?

1    set<int> result;
2    set_union(setOne.begin(), setOne.end(),
3    // All of the elements in setOne
4    setTwo.begin(), setTwo.end(),
5    // All of the elements in setTwo
6    inserter(result, result.begin())); // Store in result.
7

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:连个参数,表示这两个迭代器之间元素的个数。