// <algorithm> 
// 等价比较(1)    
template <class ForwardIterator1,
    class ForwardIterator2>
    ForwardIterator1 find_end (
        ForwardIterator1 first1,
        ForwardIterator1 last1,
        ForwardIterator2 first2,
        ForwardIterator2 last2);
// 自定义谓词比较(2)    
template <class ForwardIterator1,
    class ForwardIterator2,
​    class BinaryPredicate>
    ForwardIterator1 find_end (
        ForwardIterator1 first1,
        ForwardIterator1 last1,
        ForwardIterator2 first2,
        ForwardIterator2 last2,
        BinaryPredicate pred);

查找范围 A 中与范围 B 等价的子范围最后出现的位置。

该函数等价于:

template<class _FwdIt1,
    class _FwdIt2,
    class _Diff1,
    class _Diff2,
    class _Pr> inline
    _FwdIt1 _Find_end(_FwdIt1 _First1, _FwdIt1 _Last1,
        _FwdIt2 _First2, _FwdIt2 _Last2, _Pr _Pred, _Diff1 *, _Diff2 *)
    {    // find last [_First2, _Last2) satisfying _Pred
        _Diff1 _Count1 = 0;
        _Distance(_First1, _Last1, _Count1);
        _Diff2 _Count2 = 0;
        _Distance(_First2, _Last2, _Count2);
        _FwdIt1 _Ans = _Last1;

        if (0 < _Count2)
            for (; _Count2 <= _Count1; ++_First1, --_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);
    }
  • first1last1

    分别指向一个被搜索(Searched)序列中初始及末尾位置的正向迭代器(Forward Iterators)。这个范围即 [first1,last1) ,包括 first1 到 last1 间的所有元素,包括 first1 指向的元素,但不包括 last1 指向的元素。

    first2last2

    分别指向一个需要搜索到的(to be searched)序列中初始及末尾位置的正向迭代器。这个范围即 [first2,last2) ,包括 first2 到 last2 间的所有元素,包括 first2 指向的元素,但不包括 last2 指向的元素。

    pred

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明指定两个元素是否满足当前函数所检测的匹配条件。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

    返回

    返回指向序列 [first2,last2) 在序列 [first1,last1) 中最后一次出现位置处的第一个元素的迭代器。

    C++98

    如果序列 [first2,last2) 为空,结果未知。

    C++11

    如果序列 [first2,last2) 为空,当前函数返回 last1

  • 例 1

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
        bool IfEqual(int m, int n) {
            return (m == n);
        }
        void FindEnd_1() {
            CLASSFOO_VECTOR(int, BigVector, { 8, 23, 5, 6, 7, 29, 0, 5, 6, 7, 1, 1 });
            CLASSFOO_VECTOR(int, SmallVector, { 5, 6, 7 });
            // 等价比较
            std::vector<int>::iterator it = std::find_end(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector),
                std::end(SmallVector));
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
            // 自定谓词比较
            it = std::find_end(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector),
                std::end(SmallVector),
                IfEqual);
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
        }
    }
    int main()
    {
        ClassFoo::FindEnd_1();
        return 0;
    }

    找到: 5
    前一个元素是: 0
    找到: 5
    前一个元素是: 0

    例 2

    C++11

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    namespace ClassFoo{
        void FindEnd_2() {
            std::vector<int> BigVector = { 8, 23, 5, 6, 7, 29, 0, 5, 6, 7, 1, 1 };
            std::vector<int> SmallVector = { 5, 6, 7 };
            // 等价比较
            auto it = std::find_end(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector),
                std::end(SmallVector));
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
            // 自定谓词比较
            it = std::find_end(
                std::begin(BigVector),
                std::end(BigVector),
                std::begin(SmallVector),
                std::end(SmallVector),
                [](int &m, int &n) { return m == n; });
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
        }
    }
    int main()
    {
        ClassFoo::FindEnd_2();
        return 0;
    }

    找到: 5
    前一个元素是: 0
    找到: 5
    前一个元素是: 0

  • 复杂度

    最多 S*(T-S+1) 次比较,其中 S = distance(first2,last2)N = distance(first1,last1)

    数据争用相关

    访问在两个范围中的部份(或所有)元素,且每个元素可能被访问多次。

    异常安全性相关

    如果 pred 或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)