首页 > 代码库 > STL (13) 非变动型算法

STL (13) 非变动型算法

STL (13) 非变动型算法

    • algorithm是“算法”必须的头文件。
      • Non-modifying sequence operations (非变动式算法):算法过后,容器内部数据不发生改变。
        all_of
        Test condition on all elements in range (function template )
        any_of
        Test if any element in range fulfills condition (function template )
        none_of
        Test if no elements fulfill condition (function template )
        for_each
        Apply function to range (function template )
        find
        Find value in range (function template )
        find_if
        Find element in range (function template )
        find_if_not
        Find element in range (negative condition) (function template )
        find_end
        Find last subsequence in range (function template )
        find_first_of
        Find element from set in range (function template )
        adjacent_find
        Find equal adjacent elements in range (function template )
        count
        Count appearances of value in range (function template )
        count_if
        Return number of elements in range satisfying condition (function template )
        mismatch
        Return first position where two ranges differ (function template )
        equal
        Test whether the elements in two ranges are equal (function template )
        is_permutation
        Test whether range is permutation of another (function template )
        search
        Search range for subsequence (function template )
        search_n
        Search range for elements (function template )
    • all_of  Test condition on all elements in range (function template )
      测试范围内所有元素的条件(函数模板)???
      • 观察本质
        • cplusplus页面上的范例
          template<class InputIterator, class UnaryPredicate>
          bool all_of (InputIterator first, InputIterator last, UnaryPredicate pred)
          {
          while (first!=last) {
          if (!pred(*first)) return false;
          ++first;
          }
          return true;
          }

          ---------------------------------------------------------
          // all_of example
          #include <iostream> // std::cout
          #include <algorithm> // std::all_of
          #include <array> // std::array

          int main () {
          std::array<int,8> foo = {3,5,7,11,13,17,19,23};

          if ( std::all_of(foo.begin(), foo.end(), [](int i){return i%2;}) )
          std::cout << "All the elements are odd numbers.\n";

          return 0;
          }???
          ------------------------------------------------------
          Output:
          All the elements are odd numbers.?

          解释:
          1. [](int i){return i%2;})??? 这里表示一个匿名函数,C++11专属
          2. 些算法效率比较高:因为不是全部判断,只要其中有一个不符合,就返回false了。?



          ??
        • vs2015中代码如下:
          // TEMPLATE FUNCTION all_of
          template<class _InIt,class _Pr> inline
          bool _All_of_unchecked(_InIt _First, _InIt _Last, _Pr& _Pred)
          { // test if all elements satisfy _Pred
          for (; _First != _Last; ++_First)
          if (!_Pred(*_First))
          return (false);
          return (true);
          }????
      • all_of使用场景是很多的,它能帮我们判断容器内数据,是否符合我们的要求。
    • any_of  Test if any element in range fulfills condition (function template )
      • 观察本质
        • 与all_of成对出现,all_of是判断是否全部符合,any_of则是判断是否有一个符合。
        • 示例:
          template<class InputIterator, class UnaryPredicate>
          bool any_of (InputIterator first, InputIterator last, UnaryPredicate pred)
          {
          while (first!=last) {
          if (pred(*first)) return true;
          ++first;
          }
          return false;
          }
          ----------------------------------------------------------
          ??// any_of example
          #include <iostream> // std::cout
          #include <algorithm> // std::any_of
          #include <array> // std::array

          int main () {
          std::array<int,7> foo = {0,1,-1,3,-3,5,-5};

          if ( std::any_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
          std::cout << "There are negative elements in the range.\n";

          return 0;
          }

          --------------------------------------------------------------------
          Output:
          There are negative elements in the range.


          解释:测试如果有一个元素满足条件
          ????
          ????
    • none_of  Test if no elements fulfill condition (function template ) 如果没有元素满足条件
      • 观察本质
        • 示例
          template<class InputIterator, class UnaryPredicate>
          bool none_of (InputIterator first, InputIterator last, UnaryPredicate pred)
          {
          while (first!=last) {
          if (pred(*first)) return false;
          ++first;
          }
          return true;
          }
          ---------------------------------------------------------
          ??
          // none_of example
          #include <iostream> // std::cout
          #include <algorithm> // std::none_of
          #include <array> // std::array

          int main () {
          std::array<int,8> foo = {1,2,4,8,16,32,64,128};

          if ( std::none_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
          std::cout << "There are no negative elements in the range.\n";

          return 0;
          }

          -------------------------------------------------------------

          Output:
          There are no negative elements in the range.?????

          解释:测试如果没有元素满足条件
          ?

          ????
    • for_each Apply function to range (function template ) 将函数应用到范围
      • 观察本质
        template<class InputIterator, class Function>
        Function for_each(InputIterator first, InputIterator last, Function fn)
        {
        while (first!=last) {
        fn (*first);
        ++first;
        }
        return fn; // or, since C++11: return move(fn);
        }
        -------------------------------------------

        ??// for_each example
        #include <iostream> // std::cout
        #include <algorithm> // std::for_each
        #include <vector> // std::vector

        void myfunction (int i) { // function:
        std::cout << ‘ ‘ << i;
        }

        struct myclass { // function object type:
        void operator() (int i) {std::cout << ‘ ‘ << i;}
        } myobject;

        int main () {
        std::vector<int> myvector;
        myvector.push_back(10);
        myvector.push_back(20);
        myvector.push_back(30);

        std::cout << "myvector contains:";
        for_each (myvector.begin(), myvector.end(), myfunction);
        std::cout << ‘\n‘;

        // or:
        std::cout << "myvector contains:";
        for_each (myvector.begin(), myvector.end(), myobject);
        std::cout << ‘\n‘;

        return 0;
        }

        ----------------------------------------------------------------------

        Output:
        myvector contains: 10 20 30
        myvector contains: 10 20 30????

        解释:??要注意C++98 与C++11返回值的不同。
        C++11:Returns fn, as if calling std::move(fn).
        C++98:Returns fn.???
        ???
    • find Find value in range (function template ) 在范围内查找值
      • 观察本质:找到了,直接返回找到的值,没找到,返回last。(有效空间的后面位置)
        template<class InputIterator, class T>
        InputIterator find (InputIterator first, InputIterator last, const T& val)
        {
        while (first!=last) {
        if (*first==val) return first;
        ++first;
        }
        return last; //返回有效区间+1的位置
        }
        -------------------------------------------------------------------------------

        // find example
        #include <iostream> // std::cout
        #include <algorithm> // std::find
        #include <vector> // std::vector

        int main () {
        // using std::find with array and pointer:
        int myints[] = { 10, 20, 30, 40 };
        int * p;

        p = std::find (myints, myints+4, 30);
        if (p != myints+4)
        std::cout << "Element found in myints: " << *p << ‘\n‘;
        else
        std::cout << "Element not found in myints\n";

        // using std::find with vector and iterator:
        std::vector<int> myvector (myints,myints+4); //这里要注意,myints+4是有效区间+1的位置。
        std::vector<int>::iterator it;

        it = find (myvector.begin(), myvector.end(), 30);
        if (it != myvector.end())
        std::cout << "Element found in myvector: " << *it << ‘\n‘;
        else
        std::cout << "Element not found in myvector\n";

        return 0;
        }

        ---------------------------------------------------------------------------------

        ???????Output:
        Element found in myints: 30
        Element found in myvector: 30


        解释:???查找值需要“operator==”支持
        if (*first==val) return first; 核心代码:如果*first与val是相等的,返回first.?

        ------------------------vs2015代码----------------------------------
        template<class _InIt,
        class _Ty> inline
        _InIt _Find_unchecked1(_InIt _First, _InIt _Last, const _Ty& _Val, false_type)
        { // find first matching _Val
        for (; _First != _Last; ++_First)
        if (*_First == _Val)
        break;
        return (_First);
        }
        ????
      • 注意点:
        • 1 查找值需要“operator==”支持
        • 2 查找值需要遍历容器数据,迭代器需要支持"operator++"
        • 3 注意返回的位置,特别要注意数组和容器数据的不同,最后返回的位置last,在数组中是有效数据;而在前闭后开的容器中,last的位置是“有效数据+1”的无效数据。
        • 示例
          #include <iostream>
          #include "Algorithm.h"
          #include <array>
          class Demo
          {
          int no_;
          public:
          bool operator==(int num)
          {
          return no_ == num;
          }
          };
          int main ()
          ?{
          Demo demoArray[10];
          std::find(&demoArray[0], &demoArray[9], 20); //这里demoArray[9]是有效数据,demoArray[10]才是无效的数据
          return 0;
          }??
    • find_if Find element in range (function template ) 在一个范围里面查找元素
      • 观察本质
        template<class InputIterator, class UnaryPredicate>
        InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred)
        {
        while (first!=last) {
        if (pred(*first)) return first; //返回第一个符合条件的元素。
        ++first;
        }
        return last;
        }
        ----------------------------------------------------------------------------------------
        // find_if example
        #include <iostream> // std::cout
        #include <algorithm> // std::find_if
        #include <vector> // std::vector
        bool IsOdd (int i) {
        return ((i%2)==1);
        }
        int main () {
        std::vector<int> myvector;
        myvector.push_back(10);
        myvector.push_back(25);
        myvector.push_back(40);
        myvector.push_back(55);
        std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd);
        std::cout << "The first odd value is " << *it << ‘\n‘;
        return 0;
        }

        ----------------------------------------------------------------------------------------------

        Output:
        The first odd value is 25

        解释:返回第一个符合条件的元素。如果没有找到,则返回有效区间+1的无效数据位置。
        ?
        ???????
        ???
    • find_if_not  Find element in range (negative condition 否定条件) (function template )
      • 观察本质
        template<class InputIterator, class UnaryPredicate>
        InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred)
        {
        while (first!=last) {
        if (!pred(*first)) return first; //返回第一个不符合要求的元素
        ++first;
        }
        return last;
        }
        -----------------------------------------------------------------------------------------------
        // find_if_not example
        #include <iostream> // std::cout
        #include <algorithm> // std::find_if_not
        #include <array> // std::array

        int main () {
        std::array<int,5> foo = {1,2,3,4,5};

        std::array<int,5>::iterator it =
        std::find_if_not (foo.begin(), foo.end(), [](int i){return i%2;} );
        std::cout << "The first even value is " << *it << ‘\n‘;

        return 0;
        }

        ---------------------------------------------------------------------------------------------------
        ???Output:
        The first even value is 2

        解释:在一个范围内查找不符合要求的元素,返回第一个不符合要求的元素。
        ???
        ???
    • find_end Find last subsequence in range (function template )
      • 观察本质
        template<class ForwardIterator1, class ForwardIterator2> //只写了带4个参数的实现
        ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2)
        {
        if (first2==last2) return last1; // specified in C++11 判断第2区间是否有效

        ForwardIterator1 ret = last1;

        while (first1!=last1) //遍历第1区间
        {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1==*it2) { // or: while (pred(*it1,*it2)) for version (2)
        ++it1; ++it2; //用临时it变量对比,第1区间每个元素,与第2区间的每个元素
        if (it2==last2) { ret=first1; break; } //判断第2区间是否遍历完,完成了则重置要返回的值,跳出此内循环
        if (it1==last1) return ret; //判断第1区间是否遍历完,完成了返回第1区间末尾加一位置
        }
        ++first1;
        }
        return ret;
        }
        ---------------------------------------------------------------------------------------
        // find_end example
        #include <iostream> // std::cout
        #include <algorithm> // std::find_end
        #include <vector> // std::vector
        bool myfunction (int i, int j) {
        return (i==j);
        }
        int main () {
        int myints[] = {1,2,3,4,5,1,2,3,4,5};
        std::vector<int> haystack (myints,myints+10);
        ?
        int needle1[] = {1,2,3};?
        // using default comparison:
        std::vector<int>::iterator it;
        it = std::find_end (haystack.begin(), haystack.end(), needle1, needle1+3);
        if (it!=haystack.end())
        std::cout << "needle1 last found at position " << (it-haystack.begin()) << ‘\n‘;
        ?
        int needle2[] = {4,5,1};?
        // using predicate comparison:
        it = std::find_end (haystack.begin(), haystack.end(), needle2, needle2+3, myfunction);
        if (it!=haystack.end())
        std::cout << "needle2 last found at position " << (it-haystack.begin()) << ‘\n‘;
        ?
        return 0;
        }
        ------------------------------------------------------------------------------------------------
        Output:
        needle1 found at position 5
        needle2 found at position 3

        解释:
        1 函数重载,一个4参数,一个5参数,后面多一个BinaryPredicate pred ?????(二元谓词)
        2 算法功能:在第1区间查找,是否与第2区间完全匹配,匹配成功返回第1空间匹配最后的元素。简单来说:就是查找某一段数据。
        3 ??注意点:数据如果不是在前闭后开的容器中(如:数组),都要注意最后的元素的设定。
        ----------------------------------------vs2015代码-----------------------------------------
        // TEMPLATE FUNCTION find_end WITH PRED
        template<class _FwdIt1, class _FwdIt2, class _Pr> inline
        _FwdIt1 _Find_end_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
        _FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred)
        { // find last [_First2, _Last2) satisfying _Pred
        _Iter_diff_t<_FwdIt1> _Count1 = _STD distance(_First1, _Last1); //区间距离1
        _Iter_diff_t<_FwdIt2> _Count2 = _STD distance(_First2, _Last2); //区间距离2
        _FwdIt1 _Ans = _Last1;

        if (0 < _Count2)
        { // validate _Pred and test
        _DEBUG_POINTER_IF(_Count2 <= _Count1, _Pred);
        for (; _Count2 <= _Count1; ++_First1, (void)--_Count1)
        { // room for match, try it
        _FwdIt1 _Mid1 = _First1;
        for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1)
        if (!_Pred(*_Mid1, *_Mid2))
        break;
        else if (++_Mid2 == _Last2)
        { // potential answer, save it
        _Ans = _First1;
        break;
        }
        }
        }

        return (_Ans);
        }??
        ???
    • find_first_of Find element from set in range (function template ) 从设定范围内查找元素
      • 观察本质
        template<class InputIterator, class ForwardIterator>
        InputIterator find_first_of ( InputIterator first1, InputIterator last1,
        ForwardIterator first2, ForwardIterator last2)
        {
        while (first1!=last1) {
        for (ForwardIterator it=first2; it!=last2; ++it) {
        if (*it==*first1) // or: if (pred(*it,*first)) for version (2)
        return first1;
        }
        ++first1;
        }
        return last1;
        }
        --------------------------------------------------------------------------------------------
        // find_first_of example
        #include <iostream> // std::cout
        #include <algorithm> // std::find_first_of
        #include <vector> // std::vector
        #include <cctype> // std::tolower

        bool comp_case_insensitive (char c1, char c2) {
        return (std::tolower(c1)==std::tolower(c2));
        }

        int main () {
        int mychars[] = {‘a‘,‘b‘,‘c‘,‘A‘,‘B‘,‘C‘};
        std::vector<char> haystack (mychars,mychars+6);
        std::vector<char>::iterator it;

        int needle[] = {‘A‘,‘B‘,‘C‘};

        // using default comparison:
        it = find_first_of (haystack.begin(), haystack.end(), needle, needle+3);

        if (it!=haystack.end())
        std::cout << "The first match is: " << *it << ‘\n‘;

        // using predicate comparison:
        it = find_first_of (haystack.begin(), haystack.end(),
        needle, needle+3, comp_case_insensitive);

        if (it!=haystack.end())
        std::cout << "The first match is: " << *it << ‘\n‘;

        return 0;
        }
        ----------------------------------------------------------------------------------------
        Output:
        The first match is: A
        The first match is: a

        解释:
        循环区间1,里面嵌套循环区间2,用临时it比较所有元素,相等(或其它条件)则直接返回区间1此时元素.
        简单来说:就是查找任意一个相同(或者其它条件)元素,即刻返回。?

        ---------------------------------------------vs2015--------------------------------------
        // TEMPLATE FUNCTION find_first_of WITH PRED
        template<class _FwdIt1, class _FwdIt2, class _Pr> inline
        _FwdIt1 _Find_first_of_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
        _FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred)
        { // look for one of [_First2, _Last2) satisfying _Pred with element
        for (; _First1 != _Last1; ++_First1)
        for (_FwdIt2 _Mid2 = _First2; _Mid2 != _Last2; ++_Mid2)
        if (_Pred(*_First1, *_Mid2))
        return (_First1);
        return (_First1);
        }??????
        ???
        ???
    • adjacent_find Find equal adjacent elements in range (function template ) 在范围内查找相等的相邻元素
      • 观察本质
        template <class ForwardIterator>
        ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
        {
        if (first != last)
        {
        ForwardIterator next=first; ++next; //跳过第1个元素
        while (next != last) {
        if (*first == *next) // or: if (pred(*first,*next)), for version (2) 比较第1个和第2个元素
        return first; //如符合条件,直接返回first
        ++first; ++next; //不符合条件,则轮番向前
        }
        }
        return last;
        }
        ---------------------------------------------------------------------------------------
        // adjacent_find example
        #include <iostream> // std::cout
        #include <algorithm> // std::adjacent_find
        #include <vector> // std::vector

        bool myfunction (int i, int j) {
        return (i==j);
        }

        int main () {
        int myints[] = {5,20,5,30,30,20,10,10,20};
        std::vector<int> myvector (myints,myints+8);
        std::vector<int>::iterator it;

        // using default comparison:
        it = std::adjacent_find (myvector.begin(), myvector.end());

        if (it!=myvector.end())
        std::cout << "the first pair of repeated elements are: " << *it << ‘\n‘;

        //using predicate comparison:
        it = std::adjacent_find (++it, myvector.end(), myfunction);

        if (it!=myvector.end())
        std::cout << "the second pair of repeated elements are: " << *it << ‘\n‘;

        return 0;
        }
        -------------------------------------------------------------------------------------------
        Output:
        the first pair of repeated elements are: 30
        the second pair of repeated elements are: 10

        解释:


        ------------------------------------vs2015-----------------------------------------------
        // TEMPLATE FUNCTION adjacent_find WITH PRED
        template<class _FwdIt,
        class _Pr> inline
        _FwdIt _Adjacent_find_unchecked(_FwdIt _First, _FwdIt _Last, _Pr& _Pred)
        { // find first satisfying _Pred with successor
        if (_First != _Last)
        for (_FwdIt _Firstb; (void)(_Firstb = _First), ++_First != _Last; )
        if (_Pred(*_Firstb, *_First))
        return (_Firstb);
        return (_Last);
        }????????

        ????
    • count Count appearances of value in range (function template ) 计数
      • 观察本质
        template <class InputIterator, class UnaryPredicate>
        typename iterator_traits<InputIterator>::difference_type
        count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
        {
        typename iterator_traits<InputIterator>::difference_type ret = 0;
        while (first!=last) {
        if (pred(*first)) ++ret;
        ++first;
        }
        return ret;
        }
        -------------------------------------------------------------------------------------
        // count_if example
        #include <iostream> // std::cout
        #include <algorithm> // std::count_if
        #include <vector> // std::vector

        bool IsOdd (int i) { return ((i%2)==1); }

        int main () {
        std::vector<int> myvector;
        for (int i=1; i<10; i++) myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9

        int mycount = count_if (myvector.begin(), myvector.end(), IsOdd);
        std::cout << "myvector contains " << mycount << " odd values.\n";

        return 0;
        }
        ---------------------------------------------------------------------------------------------
        Output:
        myvector contains 5 odd values.

        解释:计数算法

        -------------------------------------------vs2015--------------------------------------------
        // TEMPLATE FUNCTION count
        template<class _InIt,
        class _Ty> inline
        _Iter_diff_t<_InIt>
        _Count_unchecked(_InIt _First, _InIt _Last, const _Ty& _Val)
        { // count elements that match _Val
        _Iter_diff_t<_InIt> _Count = 0;

        for (; _First != _Last; ++_First)
        if (*_First == _Val)
        ++_Count;
        return (_Count);
        }
        ??????????
    • count_if Return number of elements in range satisfying condition (function template ) 按条件计数
      • 观察本质
        template <class InputIterator, class UnaryPredicate>
        typename iterator_traits<InputIterator>::difference_type
        count_if (InputIterator first, InputIterator last, UnaryPredicate pred)
        {
        typename iterator_traits<InputIterator>::difference_type ret = 0;
        while (first!=last) {
        if (pred(*first)) ++ret;
        ++first;
        }
        return ret;
        }
        ------------------------------------------------------------------------------------
        // count_if example
        #include <iostream> // std::cout
        #include <algorithm> // std::count_if
        #include <vector> // std::vector

        bool IsOdd (int i) { return ((i%2)==1); }

        int main () {
        std::vector<int> myvector;
        for (int i=1; i<10; i++) myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9

        int mycount = count_if (myvector.begin(), myvector.end(), IsOdd);
        std::cout << "myvector contains " << mycount << " odd values.\n";

        return 0;
        }
        -----------------------------------------------------------------------------------

        Output:
        myvector contains 5 odd values.

        解释:按条件计数


        -------------------------------------------------vs2015--------------------------

        ????????????
    • mismatch Return first position where two ranges differ (function template ) 返回两个范围不同的第一位置
      • 观察本质
        template <class InputIterator1, class InputIterator2>
        pair<InputIterator1, InputIterator2>
        mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
        {
        while ( (first1!=last1) && (*first1==*first2) ) // or: pred(*first1,*first2), for version 2
        { ++first1; ++first2; }
        return std::make_pair(first1,first2);
        }
        ----------------------------------------------------------------------------------------------
        // mismatch algorithm example
        #include <iostream> // std::cout
        #include <algorithm> // std::mismatch
        #include <vector> // std::vector
        #include <utility> // std::pair

        bool mypredicate (int i, int j) {
        return (i==j);
        }

        int main () {
        std::vector<int> myvector;
        for (int i=1; i<6; i++) myvector.push_back (i*10); // myvector: 10 20 30 40 50

        int myints[] = {10,20,80,320,1024}; // myints: 10 20 80 320 1024

        std::pair<std::vector<int>::iterator,int*> mypair;

        // using default comparison:
        mypair = std::mismatch (myvector.begin(), myvector.end(), myints);
        std::cout << "First mismatching elements: " << *mypair.first;
        std::cout << " and " << *mypair.second << ‘\n‘;

        ++mypair.first; ++mypair.second;

        // using predicate comparison:
        mypair = std::mismatch (mypair.first, myvector.end(), mypair.second, mypredicate);
        std::cout << "Second mismatching elements: " << *mypair.first;
        std::cout << " and " << *mypair.second << ‘\n‘;

        return 0;
        }
        -------------------------------------------------------------------------------------------------------------
        Output:
        First mismatching elements: 30 and 80
        Second mismatching elements: 40 and 320

        解释:


        ---------------------------------------vs2015--------------------------------------------------\
        // TEMPLATE FUNCTION mismatch
        template<class _InIt1,class _InIt2> inline
        pair<_InIt1, _InIt2>
        mismatch(_InIt1 _First1, _InIt1 _Last1,
        _InIt2 _First2)
        { // return [_First1, _Last1)/[_First2, ...) mismatch
        return (_STD mismatch(_First1, _Last1, _First2,
        equal_to<>()));
        }?????
        -------------------------------------------------------------------------------------------------------、
        // TEMPLATE FUNCTION mismatch WITH PRED
        template<class _InIt1,class _InIt2, class _Pr> inline
        pair<_InIt1, _InIt2>
        _Mismatch_unchecked(_InIt1 _First1, _InIt1 _Last1,
        _InIt2 _First2, _Pr& _Pred)
        { // return [_First1, _Last1)/[_First2, ...) mismatch using _Pred
        for (; _First1 != _Last1 && _Pred(*_First1, *_First2); )
        { // point past match
        ++_First1;
        ++_First2;
        }

        return (pair<_InIt1, _InIt2>(_First1, _First2));
        }????
        ??????
    • equal Test whether the elements in two ranges are equal (function template )
      • 观察本质
        template <class InputIterator1, class InputIterator2>
        bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
        {
        while (first1!=last1) {
        if (!(*first1 == *first2)) // or: if (!pred(*first1,*first2)), for version 2
        return false;
        ++first1; ++first2; //第2区间没有判断条件
        }
        return true;
        }
        --------------------------------------------------------------------------------------------
        // equal algorithm example
        #include <iostream> // std::cout
        #include <algorithm> // std::equal
        #include <vector> // std::vector

        bool mypredicate (int i, int j) {
        return (i==j);
        }

        int main () {
        int myints[] = {20,40,60,80,100}; // myints: 20 40 60 80 100
        std::vector<int>myvector (myints,myints+5); // myvector: 20 40 60 80 100

        // using default comparison:
        if ( std::equal (myvector.begin(), myvector.end(), myints) )
        std::cout << "The contents of both sequences are equal.\n";
        else
        std::cout << "The contents of both sequences differ.\n";

        myvector[3]=81; // myvector: 20 40 60 81 100

        // using predicate comparison:
        if ( std::equal (myvector.begin(), myvector.end(), myints, mypredicate) )
        std::cout << "The contents of both sequences are equal.\n";
        else
        std::cout << "The contents of both sequences differ.\n";

        return 0;
        }
        ----------------------------------------------------------------------------------------
        Output:
        The contents of both sequences are equal.
        The contents of both sequence differ.

        解释:第2区间要保证比第1区间要长,不然会出问题。

        -------------------------------------------------vs2015---------------------------------

        // TEMPLATE FUNCTION equal WITH TWO RANGES, PRED
        template<class _InIt1,class _InIt2,class _Pr> inline
        bool _Equal_unchecked(_InIt1 _First1, _InIt1 _Last1,
        _InIt2 _First2, _InIt2 _Last2, _Pr& _Pred,
        input_iterator_tag, input_iterator_tag)
        { // compare [_First1, _Last1) to [_First2, _Last2)
        // using _Pred, arbitrary iterators
        _DEBUG_POINTER_IF(_First1 != _Last1 && _First2 != _Last2, _Pred);
        for (; _First1 != _Last1 && _First2 != _Last2; ++_First1, (void)++_First2)
        if (!_Pred(*_First1, *_First2))
        return (false);
        return (_First1 == _Last1 && _First2 == _Last2);
        }??????
        ?????
    • is_permutation  Test whether range is permutation of another (function template ) 测试范围是否是另一个排列
      • 观察本质
        template <class InputIterator1, class InputIterator2>
        bool is_permutation (InputIterator1 first1, InputIterator1 last1,
        InputIterator2 first2)
        {
        std::tie (first1,first2) = std::mismatch (first1,last1,first2);
        if (first1==last1) return true;
        InputIterator2 last2 = first2; std::advance (last2,std::distance(first1,last1));
        for (InputIterator1 it1=first1; it1!=last1; ++it1) {
        if (std::find(first1,it1,*it1)==it1) {
        auto n = std::count (first2,last2,*it1);
        if (n==0 || std::count (it1,last1,*it1)!=n) return false;
        }
        }
        return true;
        }
        -----------------------------------------------------------------------------------------
        // is_permutation example
        #include <iostream> // std::cout
        #include <algorithm> // std::is_permutation
        #include <array> // std::array

        int main () {
        std::array<int,5> foo = {1,2,3,4,5};
        std::array<int,5> bar = {3,1,4,5,2};

        if ( std::is_permutation (foo.begin(), foo.end(), bar.begin()) )
        std::cout << "foo and bar contain the same elements.\n";

        return 0;
        }
        ------------------------------------------------------------------------------------------------
        Output:
        foo and bar contain the same elements.

        解释:是否是一组有序的排列

        ------------------------------------------vs2015-------------------------------------------

        // TEMPLATE FUNCTION is_permutation WITH PRED
        template<class _FwdIt1,
        class _FwdIt2,
        class _Pr> inline
        bool _Is_permutation_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
        _FwdIt2 _First2, _Pr& _Pred)
        { // test if [_First1, _Last1) == permuted [_First2, ...), using _Pred
        for (; _First1 != _Last1; ++_First1, (void)++_First2)
        if (!_Pred(*_First1, *_First2))
        { // found first inequality, check match counts in suffix
        _FwdIt2 _Last2 = _STD next(_First2,
        _STD distance(_First1, _Last1));
        return (_Check_match_counts(_First1, _Last1,
        _First2, _Last2, _Pred));
        }

        return (true);
        }?
        ??????????
    • search Search range for subsequence (function template ) 搜索 标准的范围查找 对应 find_end
      • 观察本质
        template<class ForwardIterator1, class ForwardIterator2>
        ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
        ForwardIterator2 first2, ForwardIterator2 last2)
        {
        if (first2==last2) return first1; // specified in C++11

        while (first1!=last1)
        {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        while (*it1==*it2) { // or: while (pred(*it1,*it2)) for version 2
        ++it1; ++it2;
        if (it2==last2) return first1;
        if (it1==last1) return last1;
        }
        ++first1;
        }
        return last1;
        }
        ---------------------------------------------------------------------------------
        // search algorithm example
        #include <iostream> // std::cout
        #include <algorithm> // std::search
        #include <vector> // std::vector

        bool mypredicate (int i, int j) {
        return (i==j);
        }

        int main () {
        std::vector<int> haystack;

        // set some values: haystack: 10 20 30 40 50 60 70 80 90
        for (int i=1; i<10; i++) haystack.push_back(i*10);

        // using default comparison:
        int needle1[] = {40,50,60,70};
        std::vector<int>::iterator it;
        it = std::search (haystack.begin(), haystack.end(), needle1, needle1+4);

        if (it!=haystack.end())
        std::cout << "needle1 found at position " << (it-haystack.begin()) << ‘\n‘;
        else
        std::cout << "needle1 not found\n";

        // using predicate comparison:
        int needle2[] = {20,30,50};
        it = std::search (haystack.begin(), haystack.end(), needle2, needle2+3, mypredicate);

        if (it!=haystack.end())
        std::cout << "needle2 found at position " << (it-haystack.begin()) << ‘\n‘;
        else
        std::cout << "needle2 not found\n";

        return 0;
        }
        ---------------------------------------------------------------------------------------------
        Output:
        needle1 found at position 3
        needle2 not found

        解释:

        -------------------------------------vs2015------------------------------------------------
        // TEMPLATE FUNCTION search WITH PRED
        template<class _FwdIt1, class _FwdIt2, class _Pr> inline
        _FwdIt1 _Search_unchecked(_FwdIt1 _First1, _FwdIt1 _Last1,
        _FwdIt2 _First2, _FwdIt2 _Last2, _Pr& _Pred,
        forward_iterator_tag, forward_iterator_tag)
        { // find first [_First2, _Last2) satisfying _Pred, arbitrary iterators
        for (; ; ++_First1)
        { // loop until match or end of a sequence
        _FwdIt1 _Mid1 = _First1;
        for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, (void)++_Mid2)
        if (_Mid2 == _Last2)
        return (_First1);
        else if (_Mid1 == _Last1)
        return (_Last1);
        else if (!_Pred(*_Mid1, *_Mid2))
        break;
        }
        }?????????
    • search_n Search range for elements (function template )
      • 观察本质
        template<class ForwardIterator, class Size, class T>
        ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
        Size count, const T& val)
        {
        ForwardIterator it, limit;
        ? Size i;

        limit=first; std::advance(limit,std::distance(first,last)-count);

        while (first!=limit)
        {
        it = first; i=0;
        while (*it==val) // or: while (pred(*it,val)) for the pred version
        { ++it; if (++i==count) return first; }
        ++first;
        }
        return last;
        }
        -------------------------------------------------------------------------------------
        // search_n example
        #include <iostream> // std::cout
        #include <algorithm> // std::search_n
        #include <vector> // std::vector

        bool mypredicate (int i, int j) {
        return (i==j);
        }

        int main () {
        int myints[]={10,20,30,30,20,10,10,20};
        std::vector<int> myvector (myints,myints+8);

        std::vector<int>::iterator it;

        // using default comparison:
        it = std::search_n (myvector.begin(), myvector.end(), 2, 30);

        if (it!=myvector.end())
        std::cout << "two 30s found at position " << (it-myvector.begin()) << ‘\n‘;
        else
        std::cout << "match not found\n";

        // using predicate comparison:
        it = std::search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate);

        if (it!=myvector.end())
        std::cout << "two 10s found at position " << int(it-myvector.begin()) << ‘\n‘;
        else
        std::cout << "match not found\n";

        return 0;
        }
        ------------------------------------------------------------------------------------------
        Output:
        Two 30s found at position 2
        Two 10s found at position 5

        解释:##advance
        template <class InputIterator, class Distance>
        void advance (InputIterator& it, Distance n);
        迭代器辅助函数。
        使迭代器it偏移n,其中n为整数。?
        -----------------------------advance-----------------------
        ?
        #include <iostream> // std::cout
        #include <iterator> // std::advance
        #include <list> // std::list

        int main () {
        std::list<int> mylist;
        for (int i=0; i<10; i++) mylist.push_back (i*10);

        std::list<int>::iterator it = mylist.begin();

        std::advance (it,5);
        std::cout << "The sixth element in mylist is: " << *it << ‘\n‘;

        std::advance (it,-1);
        std::cout << "The fifth element in mylist is: " << *it << ‘\n‘;

        return 0;
        }?
        -------------------------advnce Deom output---------------------
        The sixth element in mylist is: 50
        The fifth element in mylist is: 40??
        ?
        ?????
        --------------------------------------vs2015-search_n--------------------------------------
        ?
        // TEMPLATE FUNCTION search_n WITH PRED
        template<class _FwdIt,class _Diff,class _Ty,class _Pr> inline
        _FwdIt _Search_n_unchecked(_FwdIt _First, _FwdIt _Last,
        _Diff _Count, const _Ty& _Val, _Pr& _Pred, forward_iterator_tag)
        { // find first _Count * _Val satisfying _Pred, forward iterators
        if (_Count <= 0)
        return (_First);

        for (; _First != _Last; ++_First)
        if (_Pred(*_First, _Val))
        { // found start of possible match, check it out
        _FwdIt _Mid = _First;

        for (_Diff _Count1 = _Count; ; )
        if (--_Count1 == 0)
        return (_First); // found rest of match, report it
        else if (++_Mid == _Last)
        return (_Last); // short match at end
        else if (!_Pred(*_Mid, _Val))
        { // short match not at end
        break;
        }

        _First = _Mid; // pick up just beyond failed match
        }

        return (_Last);
        }????
    • 非变动型算法分类:
      • 算法 粗略分类0
        • 1 不带后缀
          • 基本上算法的主要功能,在语义上表示出来。
            如:find count equal search
        • 2 带后缀
          • xxx_of of带有“如果”的意义,此种带“of”后缀的算法,一定会带一个函数,来进行判断,返回一个bool值。all_of功能就是:判断容器里面全部数据是不是一个什么(of).如果是则返回true,否则返回faulse.
          • xxx_if if带有“判断条件”的意义
      • 算法 粗略分类1
        • 搜索
          search
          search_n?
        • 查找
          find
          find_if
          find_if_not
          find_end
          find_first_of????
        • 是否相等(相同)
          equal?
          mismatch?
        • 是否同一组
          is_permutation
        • 计数
          count
          count_if?
    • 小结:非变动型算法
      1 all_of any_of none_of这3个主要功能:用来测试,测试在容器中有没有符合条件的数据。
      2 ?for_each主要功能:巡访、遍历,具体是否改变,由程序员决定。
      3 ?搜索查找系列:find find_if find_if_not find_end find_first_of search search_n ##“搜查七种武器
      find:值的查找 find_if 符合条件的查找 find_if_not 符合条件的查找取反 ?find_end 最后一个的、一整块符合条件的查找 find_first_of 查找符合条件的第一个元素 search 搜查最前一个的、一整块符合条件的 search_n 搜查一定偏移量的区间,查找符合特定条件的。
      4 ?统计计数count count_if
      5 比较 equal等。?
      ?

STL (13) 非变动型算法