This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3] Algorithm docs
- From: Jerry Quinn <jlquinn at optonline dot net>
- To: libstdc++ at gcc dot gnu dot org
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Mon, 14 Jul 2003 00:04:56 -0400
- Subject: [v3] Algorithm docs
This should finish off the standard functions in section 25.
2003-07-14 Jerry Quinn <jlquinn@optonline.net>
* include/bits/stl_algo.h (includes, set_union, set_intersection,
set_difference, set_symmetric_difference, max_element, min_element,
next_permutation, prev_permutation, find_first_of, find_end):
Document.
* include/bits/stl_algobase.h (copy,copy_backward): Clarify overlap
restrictions in docs.
* include/bits/stl_heap.h (push_heap, pop_heap, make_heap, sort_heap):
Document.
Index: include/bits/stl_algo.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.34
diff -u -r1.34 stl_algo.h
--- include/bits/stl_algo.h 14 Jul 2003 02:52:04 -0000 1.34
+++ include/bits/stl_algo.h 14 Jul 2003 03:59:59 -0000
@@ -3593,6 +3593,22 @@
// that their input ranges are sorted and the postcondition that their output
// ranges are sorted.
+ /**
+ * @brief Determines whether all elements of a sequence exists in a range.
+ * @param first1 Start of search range.
+ * @param last1 End of search range.
+ * @param first2 Start of sequence
+ * @param last2 End of sequence.
+ * @return True if each element in [first2,last2) is contained in order
+ * within [first1,last1). False otherwise.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2>
bool
includes(_InputIterator1 __first1, _InputIterator1 __last1,
@@ -3618,6 +3634,25 @@
return __first2 == __last2;
}
+ /**
+ * @brief Determines whether all elements of a sequence exists in a range
+ * using comparison.
+ * @param first1 Start of search range.
+ * @param last1 End of search range.
+ * @param first2 Start of sequence
+ * @param last2 End of sequence.
+ * @param comp Comparison function to use.
+ * @return True if each element in [first2,last2) is contained in order
+ * within [first1,last1) according to comp. False otherwise.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _Compare>
bool
includes(_InputIterator1 __first1, _InputIterator1 __last1,
@@ -3644,6 +3679,23 @@
return __first2 == __last2;
}
+ /**
+ * @brief Return the union of two sorted ranges.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
_OutputIterator
set_union(_InputIterator1 __first1, _InputIterator1 __last1,
@@ -3680,6 +3732,24 @@
return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
}
+ /**
+ * @brief Return the union of two sorted ranges using a comparison functor.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @param comp The comparison functor.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
typename _Compare>
_OutputIterator
@@ -3718,6 +3788,22 @@
return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
}
+ /**
+ * @brief Return the intersection of two sorted ranges.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
_OutputIterator
set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
@@ -3749,6 +3835,25 @@
return __result;
}
+ /**
+ * @brief Return the intersection of two sorted ranges using comparison
+ * functor.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @param comp The comparison functor.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
typename _Compare>
_OutputIterator
@@ -3782,6 +3887,24 @@
return __result;
}
+ /**
+ * @brief Return the difference of two sorted ranges.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
_OutputIterator
set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
@@ -3814,6 +3937,27 @@
return std::copy(__first1, __last1, __result);
}
+ /**
+ * @brief Return the difference of two sorted ranges using comparison
+ * functor.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @param comp The comparison functor.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
typename _Compare>
_OutputIterator
@@ -3848,6 +3992,22 @@
return std::copy(__first1, __last1, __result);
}
+ /**
+ * @brief Return the symmetric difference of two sorted ranges.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator>
_OutputIterator
set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
@@ -3883,6 +4043,25 @@
return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
}
+ /**
+ * @brief Return the symmetric difference of two sorted ranges using
+ * comparison functor.
+ * @param first1 Start of first range.
+ * @param last1 End of first range.
+ * @param first2 Start of second range.
+ * @param last2 End of second range.
+ * @param comp The comparison functor.
+ * @return End of the output range.
+ * @ingroup setoperations
+ *
+ * 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.
+ */
template<typename _InputIterator1, typename _InputIterator2, typename _OutputIterator,
typename _Compare>
_OutputIterator
@@ -3924,6 +4103,12 @@
// min_element and max_element, with and without an explicitly supplied
// comparison function.
+ /**
+ * @brief Return the maximum element in a range.
+ * @param first Start of range.
+ * @param last End of range.
+ * @return Iterator referencing the first instance of the largest value.
+ */
template<typename _ForwardIterator>
_ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last)
@@ -3941,6 +4126,14 @@
return __result;
}
+ /**
+ * @brief Return the maximum element in a range using comparison functor.
+ * @param first Start of range.
+ * @param last End of range.
+ * @param comp Comparison functor.
+ * @return Iterator referencing the first instance of the largest value
+ * according to comp.
+ */
template<typename _ForwardIterator, typename _Compare>
_ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last,
@@ -3959,6 +4152,12 @@
return __result;
}
+ /**
+ * @brief Return the minimum element in a range.
+ * @param first Start of range.
+ * @param last End of range.
+ * @return Iterator referencing the first instance of the smallest value.
+ */
template<typename _ForwardIterator>
_ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last)
@@ -3976,6 +4175,14 @@
return __result;
}
+ /**
+ * @brief Return the minimum element in a range using comparison functor.
+ * @param first Start of range.
+ * @param last End of range.
+ * @param comp Comparison functor.
+ * @return Iterator referencing the first instance of the smallest value
+ * according to comp.
+ */
template<typename _ForwardIterator, typename _Compare>
_ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last,
@@ -3998,6 +4205,17 @@
// next_permutation and prev_permutation, with and without an explicitly
// supplied comparison function.
+ /**
+ * @brief Permute range into the next "dictionary" ordering.
+ * @param first Start of range.
+ * @param last End of range.
+ * @return False if wrapped to first permutation, true otherwise.
+ *
+ * Treats all permutations of the range as a set of "dictionary" sorted
+ * sequences. Permutes the current sequence into the next one of this set.
+ * Returns true if there are more sequences to generate. If the sequence
+ * is the largest of the set, the smallest is generated and false returned.
+ */
template<typename _BidirectionalIterator>
bool
next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
@@ -4034,6 +4252,20 @@
}
}
+ /**
+ * @brief Permute range into the next "dictionary" ordering using
+ * comparison functor.
+ * @param first Start of range.
+ * @param last End of range.
+ * @param comp
+ * @return False if wrapped to first permutation, true otherwise.
+ *
+ * Treats all permutations of the range [first,last) as a set of
+ * "dictionary" sorted sequences ordered by comp. Permutes the current
+ * sequence into the next one of this set. Returns true if there are more
+ * sequences to generate. If the sequence is the largest of the set, the
+ * smallest is generated and false returned.
+ */
template<typename _BidirectionalIterator, typename _Compare>
bool
next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last,
@@ -4072,6 +4304,18 @@
}
}
+ /**
+ * @brief Permute range into the previous "dictionary" ordering.
+ * @param first Start of range.
+ * @param last End of range.
+ * @return False if wrapped to last permutation, true otherwise.
+ *
+ * Treats all permutations of the range as a set of "dictionary" sorted
+ * sequences. Permutes the current sequence into the previous one of this
+ * set. Returns true if there are more sequences to generate. If the
+ * sequence is the smallest of the set, the largest is generated and false
+ * returned.
+ */
template<typename _BidirectionalIterator>
bool
prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
@@ -4108,6 +4352,20 @@
}
}
+ /**
+ * @brief Permute range into the previous "dictionary" ordering using
+ * comparison functor.
+ * @param first Start of range.
+ * @param last End of range.
+ * @param comp
+ * @return False if wrapped to last permutation, true otherwise.
+ *
+ * Treats all permutations of the range [first,last) as a set of
+ * "dictionary" sorted sequences ordered by comp. Permutes the current
+ * sequence into the previous one of this set. Returns true if there are
+ * more sequences to generate. If the sequence is the smallest of the set,
+ * the largest is generated and false returned.
+ */
template<typename _BidirectionalIterator, typename _Compare>
bool
prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last,
@@ -4148,6 +4406,20 @@
// find_first_of, with and without an explicitly supplied comparison function.
+ /**
+ * @brief Find element from a set in a sequence.
+ * @param first1 Start of range to search.
+ * @param last1 End of range to search.
+ * @param first2 Start of match candidates.
+ * @param last2 End of match candidates.
+ * @return The first iterator @c i in the range
+ * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
+ * interator in [first2,last2), or @p last1 if no such iterator exists.
+ *
+ * Searches the range @p [first1,last1) for an element that is equal to
+ * some element in the range [first2,last2). If found, returns an iterator
+ * in the range [first1,last1), otherwise returns last1.
+ */
template<typename _InputIterator, typename _ForwardIterator>
_InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
@@ -4167,6 +4439,21 @@
return __last1;
}
+ /**
+ * @brief Find element from a set in a sequence using a predicate.
+ * @param first1 Start of range to search.
+ * @param last1 End of range to search.
+ * @param first2 Start of match candidates.
+ * @param last2 End of match candidates.
+ * @param comp Predicate to use.
+ * @return The first iterator @c i in the range
+ * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
+ * interator in [first2,last2), or @p last1 if no such iterator exists.
+ *
+ * Searches the range @p [first1,last1) for an element that is equal to
+ * some element in the range [first2,last2). If found, returns an iterator in
+ * the range [first1,last1), otherwise returns last1.
+ */
template<typename _InputIterator, typename _ForwardIterator, typename _BinaryPredicate>
_InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
@@ -4307,6 +4594,30 @@
// Dispatching functions for find_end.
+ /**
+ * @brief Find last matching subsequence in a sequence.
+ * @param first1 Start of range to search.
+ * @param last1 End of range to search.
+ * @param first2 Start of sequence to match.
+ * @param last2 End of sequence to match.
+ * @return The last iterator @c i in the range
+ * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
+ * for each @c N in the range @p [0,last2-first2), or @p last1 if no
+ * such iterator exists.
+ *
+ * Searches the range @p [first1,last1) for a sub-sequence that compares
+ * equal value-by-value with the sequence given by @p [first2,last2) and
+ * returns an iterator to the first element of the sub-sequence, or
+ * @p last1 if the sub-sequence is not found. The sub-sequence will be the
+ * last such subsequence contained in [first,last1).
+ *
+ * Because the sub-sequence must lie completely within the range
+ * @p [first1,last1) it must start at a position less than
+ * @p last1-(last2-first2) where @p last2-first2 is the length of the
+ * sub-sequence.
+ * This means that the returned iterator @c i will be in the range
+ * @p [first1,last1-(last2-first2))
+ */
template<typename _ForwardIterator1, typename _ForwardIterator2>
inline _ForwardIterator1
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
@@ -4324,6 +4635,32 @@
std::__iterator_category(__first2));
}
+ /**
+ * @brief Find last matching subsequence in a sequence using a predicate.
+ * @param first1 Start of range to search.
+ * @param last1 End of range to search.
+ * @param first2 Start of sequence to match.
+ * @param last2 End of sequence to match.
+ * @param comp The predicate to use.
+ * @return The last iterator @c i in the range
+ * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
+ * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
+ * @p last1 if no such iterator exists.
+ *
+ * Searches the range @p [first1,last1) for a sub-sequence that compares
+ * equal value-by-value with the sequence given by @p [first2,last2) using
+ * comp as a predicate and returns an iterator to the first element of the
+ * sub-sequence, or @p last1 if the sub-sequence is not found. The
+ * sub-sequence will be the last such subsequence contained in
+ * [first,last1).
+ *
+ * Because the sub-sequence must lie completely within the range
+ * @p [first1,last1) it must start at a position less than
+ * @p last1-(last2-first2) where @p last2-first2 is the length of the
+ * sub-sequence.
+ * This means that the returned iterator @c i will be in the range
+ * @p [first1,last1-(last2-first2))
+ */
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
inline _ForwardIterator1
Index: include/bits/stl_algobase.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_algobase.h,v
retrieving revision 1.25
diff -u -r1.25 stl_algobase.h
--- include/bits/stl_algobase.h 5 Jul 2003 04:05:35 -0000 1.25
+++ include/bits/stl_algobase.h 14 Jul 2003 04:00:00 -0000
@@ -319,8 +319,11 @@
* This inline function will boil down to a call to @c memmove whenever
* possible. Failing that, if random access iterators are passed, then the
* loop count will be known (and therefore a candidate for compiler
- * optimizations such as unrolling). If the input range and the output
- * range overlap, then the copy_backward function should be used instead.
+ * optimizations such as unrolling). Result may not be contained within
+ * [first,last); the copy_backward function should be used instead.
+ *
+ * Note that the end of the output range is permitted to be contained
+ * within [first,last).
*/
template<typename _InputIterator, typename _OutputIterator>
inline _OutputIterator
@@ -443,9 +446,9 @@
/**
* @brief Copies the range [first,last) into result.
- * @param first An input iterator.
- * @param last An input iterator.
- * @param result An output iterator.
+ * @param first A bidirectional iterator.
+ * @param last A bidirectional iterator.
+ * @param result A bidirectional iterator.
* @return result - (first - last)
*
* The function has the same effect as copy, but starts at the end of the
@@ -454,6 +457,9 @@
* possible. Failing that, if random access iterators are passed, then the
* loop count will be known (and therefore a candidate for compiler
* optimizations such as unrolling).
+ *
+ * Result may not be in the range [first,last). Use copy instead. Note
+ * that the start of the output range may overlap [first,last).
*/
template <typename _BI1, typename _BI2>
inline _BI2
Index: include/bits/stl_heap.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_heap.h,v
retrieving revision 1.12
diff -u -r1.12 stl_heap.h
--- include/bits/stl_heap.h 5 Jul 2003 04:05:35 -0000 1.12
+++ include/bits/stl_heap.h 14 Jul 2003 04:00:01 -0000
@@ -79,6 +79,15 @@
*(__first + __holeIndex) = __value;
}
+ /**
+ * @brief Push an element onto a heap.
+ * @param first Start of heap.
+ * @param last End of heap + element.
+ * @ingroup heap
+ *
+ * This operation pushes the element at last-1 onto the valid heap over the
+ * range [first,last-1). After completion, [first,last) is a valid heap.
+ */
template<typename _RandomAccessIterator>
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
@@ -112,6 +121,17 @@
*(__first + __holeIndex) = __value;
}
+ /**
+ * @brief Push an element onto a heap using comparison functor.
+ * @param first Start of heap.
+ * @param last End of heap + element.
+ * @param comp Comparison functor.
+ * @ingroup heap
+ *
+ * This operation pushes the element at last-1 onto the valid heap over the
+ * range [first,last-1). After completion, [first,last) is a valid heap.
+ * Compare operations are performed using comp.
+ */
template<typename _RandomAccessIterator, typename _Compare>
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
@@ -161,6 +181,15 @@
std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
}
+ /**
+ * @brief Pop an element off a heap.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @ingroup heap
+ *
+ * This operation pops the top of the heap. The elements first and last-1
+ * are swapped and [first,last-1) is made into a heap.
+ */
template<typename _RandomAccessIterator>
inline void
pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
@@ -208,6 +237,17 @@
__value, __comp);
}
+ /**
+ * @brief Pop an element off a heap using comparison functor.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @param comp Comparison functor to use.
+ * @ingroup heap
+ *
+ * This operation pops the top of the heap. The elements first and last-1
+ * are swapped and [first,last-1) is made into a heap. Comparisons are
+ * made using comp.
+ */
template<typename _RandomAccessIterator, typename _Compare>
inline void
pop_heap(_RandomAccessIterator __first,
@@ -221,6 +261,14 @@
std::__pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp);
}
+ /**
+ * @brief Construct a heap over a range.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @ingroup heap
+ *
+ * This operation makes the elements in [first,last) into a heap.
+ */
template<typename _RandomAccessIterator>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
@@ -246,6 +294,16 @@
}
}
+ /**
+ * @brief Construct a heap over a range using comparison functor.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @param comp Comparison functor to use.
+ * @ingroup heap
+ *
+ * This operation makes the elements in [first,last) into a heap.
+ * Comparisons are made using comp.
+ */
template<typename _RandomAccessIterator, typename _Compare>
inline void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
@@ -272,6 +330,14 @@
}
}
+ /**
+ * @brief Sort a heap.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @ingroup heap
+ *
+ * This operation sorts the valid heap in the range [first,last).
+ */
template<typename _RandomAccessIterator>
void
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
@@ -286,6 +352,16 @@
std::pop_heap(__first, __last--);
}
+ /**
+ * @brief Sort a heap using comparison functor.
+ * @param first Start of heap.
+ * @param last End of heap.
+ * @param comp Comparison functor to use.
+ * @ingroup heap
+ *
+ * This operation sorts the valid heap in the range [first,last).
+ * Comparisons are made using comp.
+ */
template<typename _RandomAccessIterator, typename _Compare>
void
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,