set_intersection()

Module:  Standard C++ Library   Library:  Algorithms

Function

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

A basic set operation (algorithm) for constructing a sorted intersection

#include <algorithm>

namespace std {
  template <class InputIterator1, class InputIterator2, 
            class OutputIterator>
  OutputIterator  
  set_intersection(InputIterator1 start1, 
                   InputIterator1 finish1,
                   InputIterator2 start2, 
                   InputIterator2 finish2,
                   OutputIterator result);
  template <class InputIterator1, class InputIterator2, 
            class OutputIterator, class Compare>
  OutputIterator  
  set_intersection(InputIterator1 start1, 
                   InputIterator1 finish1,
                   InputIterator2 start2, 
                   InputIterator2 finish2, 
                   OutputIterator result, 
                   Compare comp);
}

The set_intersection() algorithm constructs a sorted intersection of elements from the two ranges. It returns the end of the constructed range. When it finds an element present in both ranges, set_intersection() always copies the element from the first range into result. This means that the result of set_intersection() is guaranteed to be stable. The result of set_intersection() is undefined if the result range overlaps with either of the original ranges.

set_intersection() assumes that the ranges are sorted using operator<(), unless an alternative comparison function object (comp) is provided.

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

//
//  set_intr.cpp
//

#include <algorithm>
#include <set>
#include <iostream>

int main ()
{
#ifndef _RWSTD_NO_NAMESPACE
  using namespace std;
#endif


  // Initialize some sets.

  int a1[10] = {1,3,5,7,9,11};
  int a3[4]  = {3,5,7,8};
  set<int, less<int>,allocator<int>  > odd(a1+0, a1+6),
                                       result, 
                                       smalll(a3+0, a3+4);

  // Create an insert_iterator for result.

  insert_iterator<set<int, less<int>,allocator<int> > > 
                  res_ins(result, result.begin());

  // Demonstrate set_intersection.

  cout << "The result of:" << endl << "{";
  copy(smalll.begin(),smalll.end(), 
       ostream_iterator<int,char,char_traits<char> >
                       (cout," "));
  cout << "} intersection {";
  copy(odd.begin(),odd.end(),
       ostream_iterator<int,char,char_traits<char> >
                       (cout," "));
  cout << "} =" << endl << "{";

  set_intersection(smalll.begin(),smalll.end(),
                   odd.begin(),odd.end(),res_ins);
  copy(result.begin(),result.end(),
       ostream_iterator<int,char,char_traits<char> >
                       (cout," "));
  cout << "}" << endl << endl;

  return 0;
}


Program Output:

The result of:
{3 5 7 8 } intersection {1 3 5 7 9 11 } =
{3 5 7 }

includes(), Iterators, set_union(), set_difference(), set_symmetric_difference()

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

Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).