Module: Standard C++ Library Library: Algorithms
Function
A basic set operation (algorithm) for constructing a sorted difference
#include <algorithm>
namespace std {
template <class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference(InputIterator1 start1,
InputIterator1 finish1,
InputIterator2 start2,
InputIterator2 finish2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference(InputIterator1 start1,
InputIterator1 finish1,
InputIterator2 start2,
InputIterator2 finish2,
OutputIterator result,
Compare comp);
}
The set_difference() algorithm constructs a sorted difference that includes copies of the elements that are present in the range [start1, finish1) but are not present in the range [start2, finish2). It returns the end of the constructed range.
As an example, assume we have the following two sets:
1 2 3 4 5
and
3 4 5 6 7
The result of applying set_difference() is the set:
1 2
The result of set_difference() is undefined if the result range overlaps with either of the original ranges.
set_difference() assumes that the ranges are sorted using operator<(), unless an alternative comparison function object (comp) is provided.
Use the set_symetric_difference() algorithm to obtain a result that contains all elements that are not in common between the two sets.
At most ((finish1 - start1) + (finish2 - start2)) * 2 -1 comparisons are performed.
//
// set_diff.cpp
//
#include <algorithm>
#include <set>
#include <iostream>
int main ()
{
#ifndef _RWSTD_NO_NAMESPACE
using namespace std;
#endif
// Initialize some sets.
int a1[10] = {1,2,3,4,5,6,7,8,9,10};
int a2[6] = {2,4,6,8,10,12};
set<int, less<int>,allocator<int> > all(a1+0, a1+10),
even(a2+0, a2+6), odd;
// Create an insert_iterator for odd.
insert_iterator<set <int, less<int>,allocator<int> > >
odd_ins(odd, odd.begin());
// Demonstrate set_difference.
cout << "The result of:" << endl << "{";
copy(all.begin(),all.end(),
ostream_iterator<int,char,char_traits<char> >
(cout," "));
cout << "} - {";
copy(even.begin(),even.end(),
ostream_iterator<int,char,char_traits<char> >
(cout," "));
cout << "} =" << endl << "{";
set_difference(all.begin(), all.end(), even.begin(),
even.end(), odd_ins);
copy(odd.begin(),odd.end(),
ostream_iterator<int,char,char_traits<char> >
(cout," "));
cout << "}" << endl << endl;
return 0;
}
Program Output:
The result of:
{1 2 3 4 5 6 7 8 9 10 } - {2 4 6 8 10 12 } =
{1 3 5 7 9 }
includes(), Iterators, set_union(), set_intersection(), set_symmetric_difference()
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.5.4
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).