// <algorithm> 
template <class InputIterator1,
    class InputIterator2>
    bool includes (
        InputIterator1 first1,
        InputIterator1 last1,
        InputIterator2 first2,
        InputIterator2 last2 );
template <class InputIterator1,
    class InputIterator2, class Compare>
    bool includes (
        InputIterator1 first1,
        InputIterator1 last1,
        InputIterator2 first2,
        InputIterator2 last2,
        Compare comp );

判断一个集合是否是另一个集合的子集。两个输入序列须保证已排好序。

该函数等价于:

template<class _InIt1,
class _InIt2,
class _Pr> inline
bool _Includes(_InIt1 _First1, _InIt1 _Last1,
    _InIt2 _First2, _InIt2 _Last2, _Pr _Pred)
{    // test if set [_First1, _Last1) in [_First2, _Last2), using _Pred
    for (; _First1 != _Last1 && _First2 != _Last2; )
    if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
        return (false);
    else if (_Pred(*_First1, *_First2))
        ++_First1;
    else
    {    // advance both
        ++_First1;
        ++_First2;
    }
    return (_First2 == _Last2);
}
  • first1last1

    分别指向一个序列中初始及末尾位置的输入迭代器(Input iterators)。这个范围即 [first1,last1) ,包括 first1 到 last1 之间的所有元素,包括 first1 指向的元素,但不包括 last1 指向的元素。

    first2last2

    分别指向一个序列中初始及末尾位置的输入迭代器。这个范围即 [first2,last2) ,包括 first2 到 last2 之间的所有元素,包括 first2 指向的元素,但不包括 last2 指向的元素。

    comp

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

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

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

  • 如果范围 [first2,last2) 中的所有元素都包含在范围 [first1,last1) 中,则返回 true

    否则返回 false

    C++98

    如果范围 [first2,last2) 为空,结果将不确定(根据各个编译器实现)。

    C++11

    如果范围 [first2,last2) 为空,则返回 true

  • 参照 std::sort 以获得与自定义函数谓词、函数对象谓词、对象数组、lambda 表达式 C++11、初始化列表 std::initializer_list C++11 等相关的例子。

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #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{
    
        void Includes_1() {
            // 构造 vector 对象
            CLASSFOO_VECTOR(int, foo, { 1, 3, 5, 7, 9, 10, 0, 2, 4, 6, 8 });
            CLASSFOO_VECTOR(int, bar, { 3, 6, 7, 5, 10 });
    
            // 先排序
            std::sort(
                foo.begin(),
                foo.end());
    
            std::sort(
                bar.begin(),
                bar.end());
    
            bool Existed = std::includes(
                foo.begin(),
                foo.end(),
                bar.begin(),
                bar.begin());
    
            // 是否存在
            std::cout << std::boolalpha << Existed << std::endl;
    } } int main() { ClassFoo::Includes_1(); return 0; }

    true

  • 复杂度

    O(2*(m + n) - 1)m 等值于 std::distance(first1,last1)n 等值于 std::distance(first2,last2)

    数据争用相关

    访问在范围 [first1,last1) 、 [first2,last2) 中的部分(或所有)元素,最多访问两次。

    异常安全性相关

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

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