STL之算法模板函数实现详解

古城微笑少年丶 2022-05-27 02:15 171阅读 0赞

# 1、`<algorithm>` #

## 1、transform ##

template <class InputIterator, class OutputIterator, class UnaryOperation>
    OutputIterator transform(InputIterator first, InputIterator last,
                             OutputIterator result, UnaryOperation op) {
      for ( ; first != last; ++first, ++result)
        *result = op(*first);
      return result;
    }
    
    template <class InputIterator1, class InputIterator2, class OutputIterator,
     class BinaryOperation> OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op) { for ( ; first1 != last1; ++first1, ++first2, ++result) *result = binary_op(*first1, *first2); return result; }

第一版本以仿函数`op`作用与`[first,last)`中的每个元素，并将结果存入`result`指向的内存中。  
第一版本以仿函数`binary_op`作用与一对元素上，一个来自`[first1,last)`，一个来自`[first2,?)`，并将结果存入`result`指向的内存中。如果第二个序列元素少于第一个序列，执行结果不可预期。

// transform algorithm example
    #include <iostream> // std::cout
    #include <algorithm> // std::transform
    #include <vector> // std::vector
    #include <functional> // std::plus
    
    int op_increase (int i) { return ++i; }
    
    int main () {
      std::vector<int> foo;
      std::vector<int> bar;
    
      // set some values:
      for (int i=1; i<6; i++)
        foo.push_back (i*10);                         // foo: 10 20 30 40 50
    
      bar.resize(foo.size());                         // allocate space
    
      //作用与一个参数
      std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);//传入函数指针和仿函数一样，反正函数调用。
                                                      // bar: 11 21 31 41 51
    
      // std::plus adds together its two arguments:
      std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
                                                      // foo: 21 41 61 81 101
    
      std::cout << "bar contains:";
      for (std::vector<int>::iterator it=bar.begin(); it!=bar.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      std::cout << "foo contains:";
      for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
        std::cout << ' ' << *it;
      std::cout << '\n';
    
      return 0;
    }

![这里写图片描述][70]

## 2、mismatch ##

template <class InputIterator1, class InputIterator2>
    pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
                              InputIterator1 last1,
                              InputIterator2 first2) {
      while (first1 != last1 && *first1 == *first2) {
        ++first1;
        ++first2;
      }
      return pair<InputIterator1, InputIterator2>(first1, first2);
    }//返回第一个不匹配的迭代器
    
    template <class InputIterator1, class InputIterator2, class BinaryPredicate>
    pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
                              InputIterator1 last1,
                              InputIterator2 first2,
                              BinaryPredicate binary_pred) {
      while (first1 != last1 && binary_pred(*first1, *first2)) {
        ++first1;
        ++first2;
      }
      return pair<InputIterator1, InputIterator2>(first1, first2);
    }

# 2、`<numeric>` #

template <class InputIterator, class T>
    T accumulate(InputIterator first, InputIterator last, T init) {
      for ( ; first != last; ++first)
        init = init + *first;
     return init;
    }
    
    template <class InputIterator, class T, class BinaryOperation>
    T accumulate(InputIterator first, InputIterator last, T init,
                 BinaryOperation binary_op) {
      for ( ; first != last; ++first)
        init = binary_op(init, *first);
     return init;
    }

测试累加，很简单的测试代码。

// accumulate example
    #include <iostream> // std::cout
    #include <functional> // std::minus
    #include <numeric> // std::accumulate
    
    int myfunction (int x, int y) {
       return x+2*y;}
    struct myclass {
        int operator()(int x, int y) {
       return x+3*y;}
    } myobject;
    
    int main () {
      int init = 100;
      int numbers[] = {
       10,20,30};
    
      std::cout << "using default accumulate: ";
      std::cout << std::accumulate(numbers,numbers+3,init);
      std::cout << '\n';
    
      std::cout << "using functional's minus: ";
      std::cout << std::accumulate (numbers, numbers+3, init, std::minus<int>());
      std::cout << '\n';
    
      std::cout << "using custom function: ";
      std::cout << std::accumulate (numbers, numbers+3, init, myfunction);
      std::cout << '\n';
    
      std::cout << "using custom object: ";
      std::cout << std::accumulate (numbers, numbers+3, init, myobject);
      std::cout << '\n';
    
      return 0;
    }

Output:

using default accumulate: 160  
using functional’s minus: 40  
using custom function: 220  
using custom object: 280

[70]: /images/20220527/229b960793bd4dee80d5027899ed9710.png