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) 同时到达last1last2(两序列的大小相同)
  • (3)到达last1last2(也即两序列的大小不同)
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);