STL::算法::常见算法

  • CLR/CLRS

    表示算法导论一书的几位作者。

    • “CLRS”：Cormen, Leiserson, Rivest, Stein

    • “CLR” ：Cormen, Leiserson, Rivest，in the first edition,

find 与 find_if

  • find

    根据 equality 操作符，循序（++first）查找[first, last)内的所有元素，找出第一个匹配等同（equality）条件者。如果找到，就返回一个InputIterator指向该元素，否则返回迭代器last：

    template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

  • find_if

    我们放宽相等性equality约束，根据指定的pred（predicate：断言）运算条件（function object），循序查找[first, last)内的所有元素，找出第一个满足断言pred者（断言的返回值是bool类型），也就是把pred(*pos)为真者，如果找到就返回一个InputIterator指向该元素，否则返回迭代器last

    template<typename InputIterator, typename Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

transform 的两个版本

在STL的算法（<algorithm>）实现中，一般针对某一函数（也即某一特定算法）都有两个版本（或者叫函数重载），一种是基础版本（表现为最常用或最直观的那种版本），一种是泛化版本。

tranform() 的第一个版本以一元仿函数op作用于输入序列[first, last)中的每一个元素身上，并以其结果返回一个新序列。

y=f(x)

template<typename InputIterator, typename OutputIterator, typename UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,                           // sourceOutputIterator result,                                             // destinatonUnaryOperation op);

第二个版本以二元仿函数binary_op作用于一对元素身上，并以其结果产生一个新序列。如果第二个输入序列的长度小于第一个序列，属于undefined behavior。关于undefined behavior更详细的讨论请见<矫情的C++——不明确行为（undefined behavior）>。

z=f(x,y)

template<typename InputIterator, typename OutputIterator, typename BinaryOperation>
OutputIterator transform(InputIterator first1, InputIterator last1, InputIterator first2,BinaryOperation op);

lexicographical_compare

#include <utility>

以“字典排列方式”对两个序列[first1, last1)和[first2, last2)进行比较。比较操作针对两序列中的对应位置上的元素进行，并持续直到（也即遍历退出的条件，也是for三条语句的第二条语句）：

  • （1） 某一组对应元素彼此不相等
  • （2） 同时到达last1和last2（两序列的大小相同）
  • （3）到达last1或last2（也即两序列的大小不同）
template<class InputIterator>
bool lexicographical_compare(InputIterator first1, InpoutIterator last1, InputIterator first2, InputIterator last2);template<class InputIterator, class Compare>
bool lexicographical_compare(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2, Compare comp);