// <algorithm> 
// 等价比较(1)    
template <class ForwardIterator,
    class Size, class T>
    ForwardIterator search_n (
        ForwardIterator first,
        ForwardIterator last,
        Size count, const T& val);
// 自定义谓词比较(2)    
template <class ForwardIterator,
    class Size, class T,
    class BinaryPredicate>
    ForwardIterator search_n (
        ForwardIterator first,
        ForwardIterator last,
        Size count, const T& val,
        BinaryPredicate pred );

在给定范围中查找第一个连续 n 个元素都等价于给定值的子范围的位置。

该函数等价于:

template<class _FwdIt1,
    class _Diff2,
    class _Ty,
    class _Pr> inline
    _FwdIt1 _Search_n(_FwdIt1 _First1, _FwdIt1 _Last1,
        _Diff2 _Count, const _Ty& _Val, _Pr _Pred, forward_iterator_tag)
    {    // find first _Count * _Val satisfying _Pred, forward iterators
        if (_Count <= 0)
            return (_First1);

        for (; _First1 != _Last1; ++_First1)
            if (_Pred(*_First1, _Val))
                {    // found start of possible match, check it out
                _FwdIt1 _Mid1 = _First1;

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

                _First1 = _Mid1;    // pick up just beyond failed match
                }
        return (_Last1);
    }
  • firstlast

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

    count

    所需匹配的连续相等的元素的个数的最小值。

    Size 必须为(或能够转换成)一个整数类型。

    val

    用于比较的值,或作为谓词 pred(或果有) 的一个参数。

    pred

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

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

    该函数不能修改其参数。

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

    返回

    返回指向找到的子序列中的第一元素的迭代器。

    如果找不到该子序列,则返回 last

  • 例 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 SearchN_1() {
            CLASSFOO_VECTOR(int, BigVector, { 1, 99, 99, 2, 99, 99, 99, 3, 99, 99, 99, 4, 99, 99, 99, 99 });
            // 在序列中查找连续 3 个 99 第一次出现的位置
            // 等价比较
            std::vector<int>::iterator it = std::search_n(
                std::begin(BigVector),
                std::end(BigVector),
                3, 99);
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
            // 自定谓词比较
            it = std::search_n(
                std::begin(BigVector),
                std::end(BigVector),
                3, 99,
                IfEqual);
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
        }
    }
    int main()
    {
        ClassFoo::SearchN_1();
        return 0;
    }

    找到: 99
    前一个元素是: 2
    找到: 99
    前一个元素是: 2

    例 2

    C++11

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    namespace ClassFoo{
        void SearchN_2() {
            std::vector<int> BigVector = { 1, 99, 99, 2, 99, 99, 99, 3, 99, 99, 99, 4, 99, 99, 99, 99 };
            // 在序列中查找连续 3 个 99 第一次出现的位置
            // 等价比较
            std::vector<int>::iterator it = std::search_n(
                std::begin(BigVector),
                std::end(BigVector),
                3, 99);
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
            // 自定谓词比较
            it = std::search_n(
                std::begin(BigVector),
                std::end(BigVector),
                3, 99,
                [](const int &m, const int &n) { return m == n; });
            if (it != std::end(BigVector)) {
                std::cout << "找到: " << *it << '\n';
                std::cout << "前一个元素是: " << *(it - 1) << '\n';
            }
        }
    }
    int main()
    {
        ClassFoo::SearchN_2();
        return 0;
    }

    找到: 99
    前一个元素是: 2
    找到: 99
    前一个元素是: 2

  • 复杂度

    O(n)n 为 last first,比较各个元素,直到发现匹配的子序列。

    数据争用相关

    访问在范围 [first,last) 中的部份(或所有)元素,且每个元素确定只被访问一次。

    异常安全性相关

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

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