This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
More doxygen markup for algorithms
- From: Jonathan Wakely <cow at compsoc dot man dot ac dot uk>
- To: libstdc++ at gcc dot gnu dot org
- Date: Fri, 5 Apr 2002 18:09:46 +0100
- Subject: More doxygen markup for algorithms
The patch below adds doxygen markup for more functions in stl_algo.h
Sorry it's been so long in coming, I've not found a lot of time to work on
it recently.
jon
2002-04-05 Jonathan Wakely <jw@kayari.org>
* include/bits/stl_algo.h (unique_copy, __gcd, rotate, rotate_copy,
random_shuffle, partition, stable_partition, sort, stable_sort,
partial_sort, partial_sort_copy, nth_element): Doxygenate.
Index: include/bits/stl_algo.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.25
diff -c -5 -p -r1.25 stl_algo.h
*** stl_algo.h 2002/03/27 21:41:31 1.25
--- stl_algo.h 2002/04/04 01:50:00
*************** namespace std
*** 1137,1146 ****
--- 1137,1148 ----
* @return An iterator designating the end of the resulting sequence.
*
* Copies each element in the range @p [first,last) to the range
* beginning at @p result, except that only the first element is copied
* from groups of consecutive elements that compare equal.
+ * unique_copy() is stable, so the relative order of elements that are
+ * copied is unchanged.
*/
template<typename _InputIter, typename _OutputIter>
inline _OutputIter
unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result)
*************** __result, __binary_pred, _IterType());
*** 1389,1398 ****
--- 1391,1401 ----
/**
* @if maint
* This is a helper function for the rotate algorithm specialized on RAIs.
+ * It returns the greatest common divisor of two integer values.
* @endif
*/
template<typename _EuclideanRingElement>
_EuclideanRingElement
__gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
*************** __result, __binary_pred, _IterType());
*** 1536,1552 ****
++__first;
}
}
/**
! * @brief TODO
* @param first A forward iterator.
* @param middle A forward iterator.
* @param last A forward iterator.
* @return Nothing.
*
! * @doctodo
*/
template<typename _ForwardIter>
inline void
rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
{
--- 1539,1564 ----
++__first;
}
}
/**
! * @brief Rotate the elements of a sequence.
* @param first A forward iterator.
* @param middle A forward iterator.
* @param last A forward iterator.
* @return Nothing.
*
! * Rotates the elements of the range @p [first,last) by @p (middle-first)
! * positions so that the element at @p middle is moved to @p first, the
! * element at @p middle+1 is moved to @first+1 and so on for each element
! * in the range @p [first,last).
! *
! * This effectively swaps the ranges @p [first,middle) and
! * @p [middle,last).
! *
! * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
! * each @p n in the range @p [0,last-first).
*/
template<typename _ForwardIter>
inline void
rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
{
*************** __result, __binary_pred, _IterType());
*** 1556,1573 ****
typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
__rotate(__first, __middle, __last, _IterType());
}
/**
! * @brief TODO
* @param first A forward iterator.
* @param middle A forward iterator.
* @param last A forward iterator.
* @param result An output iterator.
! * @return TODO
*
! * @doctodo
*/
template<typename _ForwardIter, typename _OutputIter>
_OutputIter
rotate_copy(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last, _OutputIter __result)
--- 1568,1592 ----
typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType;
__rotate(__first, __middle, __last, _IterType());
}
/**
! * @brief Copy a sequence, rotating its elements.
* @param first A forward iterator.
* @param middle A forward iterator.
* @param last A forward iterator.
* @param result An output iterator.
! * @return An iterator designating the end of the resulting sequence.
*
! * Copies the elements of the range @p [first,last) to the range
! * beginning at @result, rotating the copied elements by @p (middle-first)
! * positions so that the element at @p middle is moved to @p result, the
! * element at @p middle+1 is moved to @result+1 and so on for each element
! * in the range @p [first,last).
! *
! * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
! * each @p n in the range @p [0,last-first).
*/
template<typename _ForwardIter, typename _OutputIter>
_OutputIter
rotate_copy(_ForwardIter __first, _ForwardIter __middle,
_ForwardIter __last, _OutputIter __result)
*************** __result, __binary_pred, _IterType());
*** 1601,1616 ****
#endif
}
/**
! * @brief TODO
* @param first A forward iterator.
* @param last A forward iterator.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter>
inline void
random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
{
--- 1620,1637 ----
#endif
}
/**
! * @brief Randomly shuffle the elements of a sequence.
* @param first A forward iterator.
* @param last A forward iterator.
* @return Nothing.
*
! * Reorder the elements in the range @p [first,last) using a random
! * distribution, so that every possible ordering of the sequence is
! * equally likely.
*/
template<typename _RandomAccessIter>
inline void
random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
{
*************** __result, __binary_pred, _IterType());
*** 1622,1638 ****
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __random_number((__i - __first) + 1));
}
/**
! * @brief TODO
* @param first A forward iterator.
* @param last A forward iterator.
* @param rand The RNG functor or function.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter, typename _RandomNumberGenerator>
void
random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
_RandomNumberGenerator& __rand)
--- 1643,1663 ----
for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
iter_swap(__i, __first + __random_number((__i - __first) + 1));
}
/**
! * @brief Shuffle the elements of a sequence using a random number
! * generator.
* @param first A forward iterator.
* @param last A forward iterator.
* @param rand The RNG functor or function.
* @return Nothing.
*
! * Reorders the elements in the range @p [first,last) using @p rand to
! * provide a random distribution. Calling @p rand(N) for a positive
! * integer @p N should return a randomly chosen integer from the
! * range [0,N).
*/
template<typename _RandomAccessIter, typename _RandomNumberGenerator>
void
random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
_RandomNumberGenerator& __rand)
*************** __result, __binary_pred, _IterType());
*** 1705,1721 ****
++__first;
}
}
/**
! * @brief TODO
* @param first A forward iterator.
* @param last A forward iterator.
* @param pred A predicate functor.
! * @return TODO
! *
! * @doctodo
*/
template<typename _ForwardIter, typename _Predicate>
inline _ForwardIter
partition(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred)
--- 1730,1751 ----
++__first;
}
}
/**
! * @brief Move elements for which a predicate is true to the beginning
! * of a sequence.
* @param first A forward iterator.
* @param last A forward iterator.
* @param pred A predicate functor.
! * @return An iterator @p middle such that @p pred(i) is true for each
! * iterator @p i in the range @p [first,middle) and false for each @p i
! * in the range @p [middle,last).
! *
! * @p pred must not modify its operand. @p partition() does not preserve
! * the relative ordering of elements in each group, use
! * @p stable_partition() if this is needed.
*/
template<typename _ForwardIter, typename _Predicate>
inline _ForwardIter
partition(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred)
*************** __result, __binary_pred, _IterType());
*** 1798,1814 ****
return __begin;
}
}
/**
! * @brief TODO
* @param first A forward iterator.
* @param last A forward iterator.
* @param pred A predicate functor.
! * @return TODO
! *
! * @doctodo
*/
template<typename _ForwardIter, typename _Predicate>
_ForwardIter
stable_partition(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred)
--- 1828,1851 ----
return __begin;
}
}
/**
! * @brief Move elements for which a predicate is true to the beginning
! * of a sequence, preserving relative ordering.
* @param first A forward iterator.
* @param last A forward iterator.
* @param pred A predicate functor.
! * @return An iterator @p middle such that @p pred(i) is true for each
! * iterator @p i in the range @p [first,middle) and false for each @p i
! * in the range @p [middle,last).
! *
! * Performs the same function as @p partition() with the additional
! * guarantee that the relative ordering of elements in each group is
! * preserved, so any two elements @p x and @p y in the range
! * @p [first,last) such that @p pred(x)==pred(y) will have the same
! * relative ordering after calling @p stable_partition().
*/
template<typename _ForwardIter, typename _Predicate>
_ForwardIter
stable_partition(_ForwardIter __first, _ForwardIter __last,
_Predicate __pred)
*************** __result, __binary_pred, _IterType());
*** 2112,2127 ****
__last = __cut;
}
}
/**
! * @brief TODO
* @param first An iterator.
* @param last Another iterator.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter>
inline void
sort(_RandomAccessIter __first, _RandomAccessIter __last)
{
--- 2149,2169 ----
__last = __cut;
}
}
/**
! * @brief Sort the elements of a sequence.
* @param first An iterator.
* @param last Another iterator.
* @return Nothing.
*
! * Sorts the elements in the range @p [first,last) in ascending order,
! * such that @p *(i+1)<*i is false for each iterator @p i in the range
! * @p [first,last-1).
! *
! * The relative ordering of equivalent elements is not preserved, use
! * @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIter>
inline void
sort(_RandomAccessIter __first, _RandomAccessIter __last)
{
*************** __result, __binary_pred, _IterType());
*** 2137,2153 ****
__final_insertion_sort(__first, __last);
}
}
/**
! * @brief TODO
* @param first An iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter, typename _Compare>
inline void
sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
{
--- 2179,2200 ----
__final_insertion_sort(__first, __last);
}
}
/**
! * @brief Sort the elements of a sequence using a predicate for comparison.
* @param first An iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * Sorts the elements in the range @p [first,last) in ascending order,
! * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
! * range @p [first,last-1).
! *
! * The relative ordering of equivalent elements is not preserved, use
! * @p stable_sort() if this is needed.
*/
template<typename _RandomAccessIter, typename _Compare>
inline void
sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
{
*************** __result, __binary_pred, _IterType());
*** 2363,2378 ****
_Distance(__last - __middle), __buffer, __buffer_size,
__comp);
}
/**
! * @brief TODO
* @param first An iterator.
* @param last Another iterator.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter>
inline void
stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
{
--- 2410,2433 ----
_Distance(__last - __middle), __buffer, __buffer_size,
__comp);
}
/**
! * @brief Sort the elements of a sequence, preserving the relative order
! * of equivalent elements.
* @param first An iterator.
* @param last Another iterator.
* @return Nothing.
*
! * Sorts the elements in the range @p [first,last) in ascending order,
! * such that @p *(i+1)<*i is false for each iterator @p i in the range
! * @p [first,last-1).
! *
! * The relative ordering of equivalent elements is preserved, so any two
! * elements @p x and @p y in the range @p [first,last) such that
! * @p x<y is false and @p y<x is false will have the same relative
! * ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIter>
inline void
stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
{
*************** __result, __binary_pred, _IterType());
*** 2390,2406 ****
else
__stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
}
/**
! * @brief TODO
* @param first An iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter, typename _Compare>
inline void
stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
{
--- 2445,2469 ----
else
__stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()));
}
/**
! * @brief Sort the elements of a sequence using a predicate for comparison,
! * preserving the relative order of equivalent elements.
* @param first An iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * Sorts the elements in the range @p [first,last) in ascending order,
! * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
! * range @p [first,last-1).
! *
! * The relative ordering of equivalent elements is preserved, so any two
! * elements @p x and @p y in the range @p [first,last) such that
! * @p comp(x,y) is false and @p comp(y,x) is false will have the same
! * relative ordering after calling @p stable_sort().
*/
template<typename _RandomAccessIter, typename _Compare>
inline void
stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
{
*************** __result, __binary_pred, _IterType());
*** 2420,2436 ****
__stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
__comp);
}
/**
! * @brief TODO
* @param first An iterator.
* @param middle Another iterator.
* @param last Another iterator.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter>
void
partial_sort(_RandomAccessIter __first,
_RandomAccessIter __middle,
--- 2483,2505 ----
__stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()),
__comp);
}
/**
! * @brief Sort the smallest elements of a sequence.
* @param first An iterator.
* @param middle Another iterator.
* @param last Another iterator.
* @return Nothing.
*
! * Sorts the smallest @p (middle-first) elements in the range
! * @p [first,last) and moves them to the range @p [first,middle). The
! * order of the remaining elements in the range @p [middle,last) is
! * undefined.
! * After the sort if @p i and @j are iterators in the range
! * @p [first,middle) such that @i precedes @j and @k is an iterator in
! * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
*/
template<typename _RandomAccessIter>
void
partial_sort(_RandomAccessIter __first,
_RandomAccessIter __middle,
*************** __result, __binary_pred, _IterType());
*** 2449,2466 ****
__pop_heap(__first, __middle, __i, _ValueType(*__i));
sort_heap(__first, __middle);
}
/**
! * @brief TODO
* @param first An iterator.
* @param middle Another iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter, typename _Compare>
void
partial_sort(_RandomAccessIter __first,
_RandomAccessIter __middle,
--- 2518,2543 ----
__pop_heap(__first, __middle, __i, _ValueType(*__i));
sort_heap(__first, __middle);
}
/**
! * @brief Sort the smallest elements of a sequence using a predicate
! * for comparison.
* @param first An iterator.
* @param middle Another iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * Sorts the smallest @p (middle-first) elements in the range
! * @p [first,last) and moves them to the range @p [first,middle). The
! * order of the remaining elements in the range @p [middle,last) is
! * undefined.
! * After the sort if @p i and @j are iterators in the range
! * @p [first,middle) such that @i precedes @j and @k is an iterator in
! * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
! * are both false.
*/
template<typename _RandomAccessIter, typename _Compare>
void
partial_sort(_RandomAccessIter __first,
_RandomAccessIter __middle,
*************** __result, __binary_pred, _IterType());
*** 2481,2498 ****
__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
sort_heap(__first, __middle, __comp);
}
/**
! * @brief TODO
! * @param first An input iterator.
! * @param last Another input iterator.
* @param result_first A random-access iterator.
* @param result_last Another random-access iterator.
! * @return TODO
*
! * @doctodo
*/
template<typename _InputIter, typename _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
--- 2558,2582 ----
__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
sort_heap(__first, __middle, __comp);
}
/**
! * @brief Copy the smallest elements of a sequence.
! * @param first An iterator.
! * @param last Another iterator.
* @param result_first A random-access iterator.
* @param result_last Another random-access iterator.
! * @return An iterator indicating the end of the resulting sequence.
*
! * Copies and sorts the smallest N values from the range @p [first,last)
! * to the range beginning at @p result_first, where the number of
! * elements to be copied, @p N, is the smaller of @p (last-first) and
! * @p (result_last-result_first).
! * After the sort if @p i and @j are iterators in the range
! * @p [result_first,result_first+N) such that @i precedes @j then
! * @p *j<*i is false.
! * The value returned is @p result_first+N.
*/
template<typename _InputIter, typename _RandomAccessIter>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
*************** __result, __binary_pred, _IterType());
*** 2526,2544 ****
sort_heap(__result_first, __result_real_last);
return __result_real_last;
}
/**
! * @brief TODO
* @param first An input iterator.
* @param last Another input iterator.
* @param result_first A random-access iterator.
* @param result_last Another random-access iterator.
* @param comp A comparison functor.
! * @return TODO
*
! * @doctodo
*/
template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
--- 2610,2636 ----
sort_heap(__result_first, __result_real_last);
return __result_real_last;
}
/**
! * @brief Copy the smallest elements of a sequence using a predicate for
! * comparison.
* @param first An input iterator.
* @param last Another input iterator.
* @param result_first A random-access iterator.
* @param result_last Another random-access iterator.
* @param comp A comparison functor.
! * @return An iterator indicating the end of the resulting sequence.
*
! * Copies and sorts the smallest N values from the range @p [first,last)
! * to the range beginning at @p result_first, where the number of
! * elements to be copied, @p N, is the smaller of @p (last-first) and
! * @p (result_last-result_first).
! * After the sort if @p i and @j are iterators in the range
! * @p [result_first,result_first+N) such that @i precedes @j then
! * @p comp(*j,*i) is false.
! * The value returned is @p result_first+N.
*/
template<typename _InputIter, typename _RandomAccessIter, typename _Compare>
_RandomAccessIter
partial_sort_copy(_InputIter __first, _InputIter __last,
_RandomAccessIter __result_first,
*************** __result, __binary_pred, _IterType());
*** 2575,2591 ****
sort_heap(__result_first, __result_real_last, __comp);
return __result_real_last;
}
/**
! * @brief TODO
* @param first An iterator.
* @param nth Another iterator.
* @param last Another iterator.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter>
void
nth_element(_RandomAccessIter __first,
_RandomAccessIter __nth,
--- 2667,2689 ----
sort_heap(__result_first, __result_real_last, __comp);
return __result_real_last;
}
/**
! * @brief Sort a sequence just enough to find a particular position.
* @param first An iterator.
* @param nth Another iterator.
* @param last Another iterator.
* @return Nothing.
*
! * Rearranges the elements in the range @p [first,last) so that @p *nth
! * is the same element that would have been in that position had the
! * whole sequence been sorted.
! * whole sequence been sorted. The elements either side of @p *nth are
! * not completely sorted, but for any iterator @i in the range
! * @p [first,nth) and any iterator @j in the range @p [nth,last) it
! * holds that @p *j<*i is false.
*/
template<typename _RandomAccessIter>
void
nth_element(_RandomAccessIter __first,
_RandomAccessIter __nth,
*************** __result, __binary_pred, _IterType());
*** 2610,2627 ****
}
__insertion_sort(__first, __last);
}
/**
! * @brief TODO
* @param first An iterator.
* @param nth Another iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * @doctodo
*/
template<typename _RandomAccessIter, typename _Compare>
void
nth_element(_RandomAccessIter __first,
_RandomAccessIter __nth,
--- 2708,2731 ----
}
__insertion_sort(__first, __last);
}
/**
! * @brief Sort a sequence just enough to find a particular position
! * using a predicate for comparison.
* @param first An iterator.
* @param nth Another iterator.
* @param last Another iterator.
* @param comp A comparison functor.
* @return Nothing.
*
! * Rearranges the elements in the range @p [first,last) so that @p *nth
! * is the same element that would have been in that position had the
! * whole sequence been sorted. The elements either side of @p *nth are
! * not completely sorted, but for any iterator @i in the range
! * @p [first,nth) and any iterator @j in the range @p [nth,last) it
! * holds that @p comp(*j,*i) is false.
*/
template<typename _RandomAccessIter, typename _Compare>
void
nth_element(_RandomAccessIter __first,
_RandomAccessIter __nth,