STL Algorithms

广义而言,我们所写的每个程序都是一个算法,其中的每个函数也都是一个算法,毕竟它们都用来解决或大或小的逻辑问题或数学问题。
STL算法包括排序、查找、排列组合算法,以及用于数据移动、复制、删除、比较、组合、运算等等。

质变与非质变

如果以运算过程中会更改区间内的元素内容区分算法,可以分为质变算法与非质变算法。

  • 质变算法包括:拷贝、互换、替换、填写、删除、排列组合、分割、随机重排、排序等等。
  • 非质变算法包括:查找、匹配、计数、巡访、比较、寻找极值等等。

算法泛化

所有泛型算法的前两个参数都是一对迭代器,通常称为first和last,用以标示算法的操作区间。STL习惯采用前闭后开区间,写成[first,last),表示区间涵盖first至last(不含last)之间的所有元素。当first==last时,上述所表现的便是一个空区间。

只要把操作对象的型别加以抽象化,把操作对象的标示法和区间目标的移动行为抽象化,整个算法也就在一个抽象层面上工作了。

1
2
3
4
5
6
7
template<class Iterator,class T>
Iterator find(Iterator begin, Iterator end, const T& value)
{
while(begin != end && *begin != value)
++begin;
return begin;
}

Hay un mundo mejor, pero carísimo.