STL学习其他算法

2040阅读　0评论2013-10-21　梦醒潇湘love
分类：C/C++


    （1）adjacent_find
    找出第一组满足条件的相邻元素。这里所谓的条件，在版本一中是指“两元素相等”，在版本二中允许用户指定一个二元运算，两个操作数分别是相邻的第一个元素和第二个元素。
  1. //查找相邻的重复元素，版本一
  2. template <class ForwardInterator>
  3. ForwardInterator adjacent_find(ForwardInterator first, ForwardInterator last)
  4. {
  5.     if(first == last)
  6.     {
  7.         return last;
  8.     }
  9.     ForwardInterator next = first;
  10.     while(++next != last)
  11.     {
  12.         if(*next == *first)
  13.         {
  14.             return first;    //如果找到相邻的元素值相等，就结束
  15.         }
  16.         first = next;
  17.     }
  18.     return last;
  19. }

  21. //查找相邻重复元素，版本二
  22. template <class ForwardInterator, class BinaryPredicate>
  23. ForwardInterator adjacent_find(ForwardInterator first, ForwardInterator last, BinaryPredicate binary_pred)
  24. {
  25.     if(first == last)
  26.     {
  27.         return last;
  28.     }
  29.     ForwardInterator next = first;
  30.     while(++next != last)
  31.     {
  32.         //如果找到相邻的元素符合外界指定的条件，就结束
  33.         if(binary_pred(*first, *next))
  34.         {
  35.             return first;    //如果找到相邻的元素值相等，就结束
  36.         }
  37.         first = next;
  38.     }
  39.     return last;
  40. }
    
    （2）count
    运用equaltiy操作符，将[first, last)区间内的每一个元素拿来与指定值value比较，并返回与value相等的元素个数。
  1. template < class InputInterator, class T>
  2. typename intertor_traits<InputInterator>::difference_type
  3. count(InputInterator first, InputInterator last, const T&value)
  4. {
  5.     //以下声明一个计数器n
  6.     typename iterator_traits<InputInterator>::difference_type n = 0;
  7.     for( ; first != last; first++)
  8.     {
  9.         if(*first == value)
  10.         {
  11.             n++;
  12.         }
  13.     }
  14.     return n;
  15. }

    （3）count_if
    将指定操作（一个仿函数）pred实施于[first, last)区间内的每一个元素身上，并将“造成pred之计算结果为true”的所有元素的个数返回。
  1. template < class InputInterator, class BinaryPredice>
  2. typename intertor_traits<InputInterator>::difference_type
  3. count_if(InputInterator first, InputInterator last, BinaryPredice binary_pred)
  4. {
  5.     //以下声明一个计数器n
  6.     typename iterator_traits<InputInterator>::difference_type n = 0;
  7.     for( ; first != last; first++)
  8.     {
  9.         if(binary_pred(*first))
  10.         {
  11.             n++;
  12.         }
  13.     }
  14.     return n;
  15. }

    （4）find
    根据equality操作符，循序查找[first, last)内的所有元素，找出第一个匹配“等同条件”者。如果找到，就返回一个InputIterator指向该元素，否则返回迭代器last。
  1. template <class InputInterator, class T>
  2. InputInterator find(InputInterator first, InputInterator last, const T &value)
  3. {
  4.     while(first != last && *first != value)
  5.     {
  6.         first++;
  7.     }
  8.     return first;
  9. }

    （5）find_if
    根据指定的pred运算条件（以仿函数表示），循序查找[first, last)内的所有元素，找出第一个令pred运算结果为true者。
  1. template <class InputInterator, class BinaryPredice>
  2. InputInterator find(InputInterator first, InputInterator last, BinaryPredice pred)
  3. {
  4.     while(first != last && !pred(*first))
  5.     {
  6.         first++;
  7.     }
  8.     return first;
  9. }

    （6）find_end
    在序列一[first1, last1)所涵盖的区间中，查找序列二[first2, last2)的最后一次出现点。如果序列一之内不存在“完全匹配序列二”的子序列，便返回迭代器last1,。此算法有两个版本，版本一使用元素型别所提供的equality操作符，版本二允许用户指定某个二元运算（以仿函数呈现），作为判断元素相等与否的依据。

    （7）find_first_of
    该算法以[first2, last2)区间内的某些元素作为查找目标，寻找它们在[first1, last1）区间内的第一个出现的地点。

    （8）for_each
    将仿函数f施行于[first, last)区间内的每一个元素身上。f不可以改变元素内容，因为first和last都是InputIterators，不保证接受赋值行为。
  1. template <class InputIterator, class Function>
  2. Function for_each(InputIterator first, InputIterator last, Function f)
  3. {
  4.     for( ; first != last; first++)
  5.     {
  6.         f(*first);        //调用仿函数f的function call操作符。返回值被忽略
  7.     }
  8.     return f;
  9. }

    （9）generate
    将仿函数gen的运算结果填写在[first, last)区间内的所有元素身上。所谓填写，用的是迭代器所指元素之assignment操作符。

    （10）generate_n
    将仿函数gen的运算结果填写在从迭代器first开始的n个元素身上。所谓填写，用的是迭代器所指元素之assignment操作符。

    （11）includes（应用于有序区间）
    判断序列二s2是否“涵盖于”序列一s1。s1和s2都必须是有序集合，其中的元素都可以重复，不必唯一。所谓涵盖，意思是“s2中的每一个元素都出现于s1中”。
    includes算法可供用户选择采用less或greater进行两元素的大小比较。
    换句话说，如果s1和s2是递增排序，includes算法应该这样使用：
  1. includes<s1.begin(), s1.end(), s2.begin(), s2.end());
    这和下一行完全相同：
  1. includes<s1.begin(), s1.end(), s2.begin(), s2.end(), less<int>());
    然而如果s1和s2是递减排序，includes算法应该这么使用：
  1. includes<s1.begin(), s1.end(), s2.begin(), s2.end(),greater<int>());

    （12）max_element
    这个算法返回一个迭代器，指向序列之中数值最大的元素。

    （13）merge（应用于有序区间）
    将两个经过排序的集合s1和s2，合并起来置于另一段空间。所得结果也是一个有序序列。返回一个迭代器，指向最后结果序列的最后一个元素的下一位置。
    版本一的代码。
  1. template <class InputIterator1, class InputIterator2, class OutputIterator>
  2. OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
  3. {
  4.     while(first1 != last1 && first2 != last2)
  5.     {
  6.         if(*first1 < *first2)
  7.         {
  8.             *result = first1;
  9.             first1++;
  10.         }
  11.         else
  12.         {
  13.             *result = *first2;
  14.             first2++;
  15.         }
  16.         result++;
  17.     }

  19.     //最后剩余元素以copy复制到目的端。以下两个序列一定至少有一个为空
  20.     copy(first2, last2, copy(first1, last1, result));
  21. }
    
    （14）min_element
    这个算法返回一个迭代器，指向序列之中数值最小的元素。

    （15）partition
    partition会将区间[first, last)中的元素重新排列。所有被一元条件运算pred判定为true的元素，都会被放到区间的前段，被判定为false的元素，都会被放到区间的后段。这个算法并不保留元素的原始相对位置。如果需要保留原始相对位置，应使用stable_partition。
上一篇：STL学习之set相关算法
下一篇：STL学习之排列组合算法算法