includes()

Library:  Algorithms

Function

• Local Index
• Summary
• Synopsis
• Description
• Complexity
• Example
• See Also
• Standards Conformance

An algorithm that returns true if every element in one sorted sequence is contained in another sorted sequence

#include <algorithm>

namespace std {
  template <class InputIterator1, class InputIterator2>
  bool includes(InputIterator1 start1, InputIterator1 finish1,
                InputIterator2 start2, 
                InputIterator2 finish2);

  template <class InputIterator1, class InputIterator2, 
           class Compare>
  bool includes(InputIterator1 start1, InputIterator1 finish1,
                InputIterator2 start2, 
                InputIterator2 finish2, Compare comp);
}

The includes() algorithm compares two sorted sequences and returns true if every element in the range [start2, finish2) is contained in the range [start1, finish1). It returns false otherwise. includes() assumes that the sequences are sorted using operator<(), or using the predicate comp.

At most ((finish1 - start1) + (finish2 - start2)) * 2 - 1 comparisons are performed.

//
//  includes.cpp
//

#include <algorithm>   // for includes
#include <iostream>    // for cout, endl
#include <set>         // for set



int main ()
{
    // Typedefs for convenience.
    typedef std::set<int, std::less<int>, std::allocator<int> >       
            Set;
    typedef std::ostream_iterator<int, char, 
                                  std::char_traits<char> > 
             os_iter;

    int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int a2[] = { 2, 4, 6, 8, 10, 12 };
    int a3[] = { 3, 5, 7, 8 };

    // Initialize three sets.
    Set all   (a1, a1 + sizeof a1 / sizeof *a1);
    Set even  (a2, a2 + sizeof a2 / sizeof *a2);
    Set other (a3, a3 + sizeof a3 / sizeof *a3);

    // Demonstrate includes.
    std::cout << "The set: ";
    std::copy (all.begin (), all.end (), 
               os_iter (std::cout, " "));

    bool answer = std::includes (all.begin (), all.end (), 
                                 other.begin (), other.end ());

    std::cout << std::endl 
              << (answer ? "INCLUDES " : "DOES NOT INCLUDE ");
    std::copy (other.begin (), other.end (), 
               os_iter (std::cout, " "));

    answer = std::includes (all.begin (), all.end (),
                            even.begin (), even.end ());

    std::cout << ", and" << std::endl
              << (answer ? "INCLUDES" : "DOES NOT INCLUDE ");

    std::copy (even.begin (), even.end (), 
               os_iter (std::cout, " "));

    std::cout << std::endl << std::endl;

    return 0;
}


Program Output:
The set: 1 2 3 4 5 6 7 8 9 10 
INCLUDES 3 5 7 8 , and
DOES NOT INCLUDE 2 4 6 8 10 12 

set_union(), set_intersection(), set_difference(), set_symmetric_difference()

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.5.1