Set operation algorithms


Detailed Description

These algorithms are common set operations performed on sequences that are already sorted.

The number of comparisons will be linear.

Functions


Function Documentation

bool std::includes _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_Compare  __comp
 

Determines whether all elements of a sequence exists in a range using comparison.

Parameters:
first1 Start of search range.
last1 End of search range.
first2 Start of sequence
last2 End of sequence.
comp Comparison function to use.
Returns:
True if each element in [first2,last2) is contained in order within [first1,last1) according to comp. False otherwise.
This operation expects both [first1,last1) and [first2,last2) to be sorted. Searches for the presence of each element in [first2,last2) within [first1,last1), using comp to decide. The iterators over each range only move forward, so this is a linear algorithm. If an element in [first2,last2) is not found before the search iterator reaches last2, false is returned.

Definition at line 4039 of file stl_algo.h.

References __glibcxx_function_requires.

bool std::includes _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2
 

Determines whether all elements of a sequence exists in a range.

Parameters:
first1 Start of search range.
last1 End of search range.
first2 Start of sequence
last2 End of sequence.
Returns:
True if each element in [first2,last2) is contained in order within [first1,last1). False otherwise.
This operation expects both [first1,last1) and [first2,last2) to be sorted. Searches for the presence of each element in [first2,last2) within [first1,last1). The iterators over each range only move forward, so this is a linear algorithm. If an element in [first2,last2) is not found before the search iterator reaches last2, false is returned.

Definition at line 3992 of file stl_algo.h.

References __glibcxx_function_requires.

_OutputIterator std::set_difference _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result,
_Compare  __comp
 

Return the difference of two sorted ranges using comparison functor.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
comp The comparison functor.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in the first range but not the second in order to the output range. Iterators increment for each range. When the current element of the first range is less than the second according to comp, that element is copied and the iterator advances. If the current element of the second range is less, no element is copied and the iterator advances. If an element is contained in both ranges according to comp, no elements are copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4374 of file stl_algo.h.

References __glibcxx_function_requires, and std::copy().

_OutputIterator std::set_difference _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result
 

Return the difference of two sorted ranges.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in the first range but not the second in order to the output range. Iterators increment for each range. When the current element of the first range is less than the second, that element is copied and the iterator advances. If the current element of the second range is less, the iterator advances, but no element is copied. If an element is contained in both ranges, no elements are copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4316 of file stl_algo.h.

References __glibcxx_function_requires, and std::copy().

_OutputIterator std::set_intersection _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result,
_Compare  __comp
 

Return the intersection of two sorted ranges using comparison functor.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
comp The comparison functor.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in both ranges in order to the output range. Iterators increment for each range. When the current element of one range is less than the other according to comp, that iterator advances. If an element is contained in both ranges according to comp, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4262 of file stl_algo.h.

References __glibcxx_function_requires.

_OutputIterator std::set_intersection _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result
 

Return the intersection of two sorted ranges.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in both ranges in order to the output range. Iterators increment for each range. When the current element of one range is less than the other, that iterator advances. If an element is contained in both ranges, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4208 of file stl_algo.h.

References __glibcxx_function_requires.

_OutputIterator std::set_symmetric_difference _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result,
_Compare  __comp
 

Return the symmetric difference of two sorted ranges using comparison functor.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
comp The comparison functor.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in one range but not the other in order to the output range. Iterators increment for each range. When the current element of one range is less than the other according to comp, that element is copied and the iterator advances. If an element is contained in both ranges according to comp, no elements are copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4489 of file stl_algo.h.

References __glibcxx_function_requires, and std::copy().

_OutputIterator std::set_symmetric_difference _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result
 

Return the symmetric difference of two sorted ranges.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in one range but not the other in order to the output range. Iterators increment for each range. When the current element of one range is less than the other, that element is copied and the iterator advances. If an element is contained in both ranges, no elements are copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4428 of file stl_algo.h.

References __glibcxx_function_requires, and std::copy().

_OutputIterator std::set_union _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result,
_Compare  __comp
 

Return the union of two sorted ranges using a comparison functor.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
comp The comparison functor.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in each range in order to the output range. Iterators increment for each range. When the current element of one range is less than the other according to comp, that element is copied and the iterator advanced. If an equivalent element according to comp is contained in both ranges, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4147 of file stl_algo.h.

References __glibcxx_function_requires, and std::copy().

_OutputIterator std::set_union _InputIterator1  __first1,
_InputIterator1  __last1,
_InputIterator2  __first2,
_InputIterator2  __last2,
_OutputIterator  __result
 

Return the union of two sorted ranges.

Parameters:
first1 Start of first range.
last1 End of first range.
first2 Start of second range.
last2 End of second range.
Returns:
End of the output range.
This operation iterates over both ranges, copying elements present in each range in order to the output range. Iterators increment for each range. When the current element of one range is less than the other, that element is copied and the iterator advanced. If an element is contained in both ranges, the element from the first range is copied and both ranges advance. The output range may not overlap either input range.

Definition at line 4085 of file stl_algo.h.

References __glibcxx_function_requires, and std::copy().


Generated on Sat Oct 1 15:08:59 2005 for libstdc++ source by  doxygen 1.4.4