This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
Attachment:
ChangeLog-doc
Description: application/text
Index: bits/stl_algo.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.47.6.12
diff -u -6 -r1.47.6.12 stl_algo.h
--- bits/stl_algo.h 7 Jun 2005 00:29:11 -0000 1.47.6.12
+++ bits/stl_algo.h 13 Jun 2005 17:02:01 -0000
@@ -369,13 +369,13 @@
* @param last A forward iterator.
* @return The first iterator @c i such that @c i and @c i+1 are both
* valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
* or @p last if no such iterator exists.
*/
template<typename _ForwardIterator>
- _ForwardIterator
+ inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
{
// concept requirements
__glibcxx_function_requires(_EqualityComparableConcept<
typename iterator_traits<_ForwardIterator>::value_type>)
return std::adjacent_find(__first, __last, __gnu_cxx::__ops::equal_to());
@@ -535,13 +535,13 @@
* @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>
- _ForwardIterator1
+ inline _ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
// concept requirements
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_ForwardIterator1>::value_type,
@@ -629,13 +629,13 @@
* or @p last if no such iterator exists.
*
* Searches the range @p [first,last) for @p count consecutive elements
* equal to @p val.
*/
template<typename _ForwardIterator, typename _Integer, typename _Tp>
- _ForwardIterator
+ inline _ForwardIterator
search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count, const _Tp& __val)
{
// concept requirements
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
@@ -1264,13 +1264,13 @@
* unique() is stable, so the relative order of elements that are
* not removed is unchanged.
* Elements between the end of the resulting sequence and @p last
* are still present, but their value is unspecified.
*/
template<typename _ForwardIterator>
- _ForwardIterator
+ inline _ForwardIterator
unique(_ForwardIterator __first, _ForwardIterator __last)
{
// concept requirements
__glibcxx_function_requires(_EqualityComparableConcept<
typename iterator_traits<_ForwardIterator>::value_type>)
return std::unique(__first, __last, __gnu_cxx::__ops::equal_to());
@@ -1667,13 +1667,15 @@
std::iter_swap(__i, __first + __rand((__i - __first) + 1));
}
/**
* @if maint
- * This is a helper function...
+ * This is an uglified
+ * partition(_Forwarditerator, _ForwardIterator, _Predicate)
+ * overloaded for forward iterators.
* @endif
*/
template<typename _ForwardIterator, typename _Predicate>
_ForwardIterator
__partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred,
@@ -1697,13 +1699,15 @@
return __first;
}
/**
* @if maint
- * This is a helper function...
+ * This is an uglified
+ * partition(_Forwarditerator, _ForwardIterator, _Predicate)
+ * overloaded for bidirectional iterators.
* @endif
*/
template<typename _BidirectionalIterator, typename _Predicate>
_BidirectionalIterator
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
_Predicate __pred,
@@ -1761,13 +1765,14 @@
std::__iterator_category(__first));
}
/**
* @if maint
- * This is a helper function...
+ * This is a helper function for stable_partition, used when it is
+ * not possible to allocate a temporary buffer.
* @endif
*/
template<typename _ForwardIterator, typename _Predicate, typename _Distance>
_ForwardIterator
__inplace_stable_partition(_ForwardIterator __first,
_ForwardIterator __last,
@@ -1789,13 +1794,14 @@
std::advance(__begin, std::distance(__middle, __end));
return __begin;
}
/**
* @if maint
- * This is a helper function...
+ * This is a helper function for stable_partition, used when it is possible
+ * to allocate a temporary buffer.
* @endif
*/
template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
typename _Distance>
_ForwardIterator
__stable_partition_adaptive(_ForwardIterator __first,
@@ -1890,13 +1896,16 @@
_DistanceType(__buf.requested_size()));
}
}
/**
* @if maint
- * This is a helper function...
+ * @pre __pivot is the dereferenced value of some iterator in the range
+ * [__first, __last).
+ *
+ * This is a helper function called from __introsort_partition.
* @endif
*/
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
@@ -1915,21 +1924,23 @@
++__first;
}
}
/**
* @if maint
- * @doctodo
- * This controls some aspect of the sort routines.
+ * This controls the largest range which partitioning is performed on
+ * during sorting. For ranges smaller than this, insertion sort is used.
* @endif
*/
enum { _S_threshold = 16 };
/**
* @if maint
- * This is a helper function for the sort routine.
+ * @pre Exists valid iterator i such that i<__last and !comp(*i, *__last).
+ *
+ * This is a helper function for sort.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline void
__unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
{
@@ -1945,14 +1956,17 @@
}
*__last = __gnu_cxx::__move(__val);
}
/**
* @if maint
- * This is a helper function. It assumes __pivot is not in the range
+ * @pre There exist iterators i,j in [__first, __last) such that
+ * !__comp(*i, __pivot) and !__comp(*j, __pivot). __pivot is not in range
* [__first, __last).
+ *
+ * This is a helper function for the sort function.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_nocopy_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
@@ -1971,13 +1985,15 @@
++__first;
}
}
/**
* @if maint
- * This is a helper function for the sort routine.
+ * @pre __pivot is in the range [__first, __last).
+ *
+ * This is a helper for the sort function.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_mid_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
@@ -2059,13 +2075,15 @@
std::__unguarded_linear_insert(__i, __comp);
}
}
/**
* @if maint
- * This is a helper function for the sort routine.
+ * @pre Forall i in the range [__first, __last), !comp(*i, *(__first - 1)).
+ *
+ * This is a helper for the sort function.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
@@ -2169,13 +2187,13 @@
* 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 _RandomAccessIterator>
- void
+ inline void
partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -2268,13 +2286,13 @@
* 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 _InputIterator, typename _RandomAccessIterator>
- _RandomAccessIterator
+ inline _RandomAccessIterator
partial_sort_copy(_InputIterator __first, _InputIterator __last,
_RandomAccessIterator __result_first,
_RandomAccessIterator __result_last)
{
typedef typename iterator_traits<_InputIterator>::value_type
_InputValueType;
@@ -2282,17 +2300,23 @@
_OutputValueType;
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
__glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
- std::partial_sort_copy(__first, __last, __result_first, __result_last,
- __gnu_cxx::__ops::less());
+ return std::partial_sort_copy(__first, __last, __result_first,
+ __result_last, __gnu_cxx::__ops::less());
}
-
+ /**
+ * @if maint
+ * This is a helper function for the sort routine designed for non-moveable
+ * types which partitions the range [__first, __last). It copies the
+ * element which is being pivoted on.
+ * @endif
+ */
template<typename _RandomAccessIterator, typename _Compare>
inline typename __enable_if<_RandomAccessIterator,
!(__gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
::value_type>::value)>::__type
__introsort_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
@@ -2308,12 +2332,19 @@
- __first)
/ 2),
*(__last - 1),
__comp)), __comp);
}
+ /**
+ * @if maint
+ * This is a helper function for the sort routine designed for moveable
+ * types which partitions the range [__first, __last). It avoids copying
+ * the element which is pivoted on.
+ * @endif
+ */
template<typename _RandomAccessIterator, typename _Compare>
inline typename __enable_if<_RandomAccessIterator,
__gnu_cxx::__is_moveable<typename iterator_traits<_RandomAccessIterator>
::value_type>::value>::__type
__introsort_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
@@ -2347,13 +2378,15 @@
__comp);
return __cut;
}
/**
* @if maint
- * This is a helper function for the sort routine.
+ * This is a helper function for the sort routine which ensures each
+ * element of [__first, __last) is no more than _S_threshold from its
+ * correct position.
* @endif
*/
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
@@ -2499,13 +2532,13 @@
* @param val The search term.
* @return An iterator pointing to the first element "not less than" @a val,
* or end() if every element is less than @a val.
* @ingroup binarysearch
*/
template<typename _ForwardIterator, typename _Tp>
- _ForwardIterator
+ inline _ForwardIterator
lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
@@ -2578,13 +2611,13 @@
* @param val The search term.
* @return An iterator pointing to the first element greater than @a val,
* or end() if no elements are greater than @a val.
* @ingroup binarysearch
*/
template<typename _ForwardIterator, typename _Tp>
- _ForwardIterator
+ inline _ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
@@ -2645,13 +2678,14 @@
std::__merge_without_buffer(__new_middle, __second_cut, __last,
__len1 - __len11, __len2 - __len22, __comp);
}
/**
* @if maint
- * This is a helper function for the stable sorting routines.
+ * This is a helper function for the stable sorting routines for use
+ * when no extra buffer could be allocated.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
void
__inplace_stable_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
@@ -2744,24 +2778,30 @@
* the input ranges. The sort is @e stable, that is, for equivalent
* elements in the two ranges, elements from the first range will always
* come before elements from the second.
*/
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator>
- _OutputIterator
+ inline _OutputIterator
merge(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_InputIterator1>::value_type>)
return std::merge(__first1, __last1, __first2, __last2, __result,
__gnu_cxx::__ops::less());
}
+ /**
+ * @if maint
+ * This is a helper function for stable_sort for when an extra buffer
+ * was allocated.
+ * @endif
+ */
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
typename _Distance, typename _Compare>
void
__merge_sort_loop(_RandomAccessIterator1 __first,
_RandomAccessIterator1 __last,
_RandomAccessIterator2 __result, _Distance __step_size,
@@ -2782,14 +2822,25 @@
std::merge(__first, __first + __step_size,
__first + __step_size, __last,
__result,
__comp);
}
+ /**
+ * @if maint
+ * This sets at what size range stable_sort should switch to using an
+ * insertion sort.
+ * @endif
+ */
enum { _S_chunk_size = 7 };
+ /**
+ * @if maint
+ * This is a helper function for stable_sort.
+ * @endif
+ */
template<typename _RandomAccessIterator, typename _Distance, typename _Compare>
void
__chunk_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Distance __chunk_size, _Compare __comp)
{
@@ -2798,12 +2849,18 @@
std::__insertion_sort(__first, __first + __chunk_size, __comp);
__first += __chunk_size;
}
std::__insertion_sort(__first, __last, __comp);
}
+ /**
+ * @if maint
+ * This is a helper function for stable_sort for when the buffer is
+ * large enough to store the range [__first, __last).
+ * @endif
+ */
template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
void
__merge_sort_with_buffer(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Pointer __buffer, _Compare __comp)
{
@@ -3037,25 +3094,30 @@
*
* If enough additional memory is available, this takes (last-first)-1
* comparisons. Otherwise an NlogN algorithm is used, where N is
* distance(first,last).
*/
template<typename _BidirectionalIterator>
- void
+ inline void
inplace_merge(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
_BidirectionalIterator __last)
{
typedef typename iterator_traits<_BidirectionalIterator>::value_type
_ValueType;
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
std::inplace_merge(__first, __middle, __last, __gnu_cxx::__ops::less());
}
+ /**
+ * @if maint
+ * This is a helper function for stable_sort.
+ * @endif
+ */
template<typename _RandomAccessIterator, typename _Pointer,
typename _Distance, typename _Compare>
void
__stable_sort_adaptive(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Pointer __buffer, _Distance __buffer_size,
@@ -3213,13 +3275,13 @@
* 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 _RandomAccessIterator>
- void
+ inline void
nth_element(_RandomAccessIterator __first,
_RandomAccessIterator __nth,
_RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
@@ -3307,13 +3369,13 @@
* std::make_pair(lower_bound(first, last, val),
* upper_bound(first, last, val))
* @endcode
* but does not actually call those functions.
*/
template<typename _ForwardIterator, typename _Tp>
- pair<_ForwardIterator, _ForwardIterator>
+ inline pair<_ForwardIterator, _ForwardIterator>
equal_range(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
@@ -3366,13 +3428,13 @@
* @ingroup binarysearch
*
* Note that this does not actually return an iterator to @a val. For
* that, use std::find or a container's specialized find member functions.
*/
template<typename _ForwardIterator, typename _Tp>
- bool
+ inline bool
binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
// concept requirements
// See comments on lower_bound.
__glibcxx_function_requires(_SameTypeConcept<_Tp,
@@ -3449,13 +3511,13 @@
* 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 @a last2, false is returned.
*/
template<typename _InputIterator1, typename _InputIterator2>
- bool
+ inline bool
includes(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_InputIterator1>::value_type>)
@@ -3542,13 +3604,13 @@
* 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
+ inline _OutputIterator
set_union(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
@@ -3627,13 +3689,13 @@
* 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
+ inline _OutputIterator
set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
@@ -3718,13 +3780,13 @@
* 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
+ inline _OutputIterator
set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
@@ -3811,13 +3873,13 @@
* 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
+ inline _OutputIterator
set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
@@ -3860,13 +3922,13 @@
* @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
+ inline _ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_ForwardIterator>::value_type>)
return std::max_element(__first, __last, __gnu_cxx::__ops::less());
@@ -3905,13 +3967,13 @@
* @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
+ inline _ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_ForwardIterator>::value_type>)
return std::min_element(__first, __last, __gnu_cxx::__ops::less());
@@ -3986,13 +4048,13 @@
* 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
+ inline bool
next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_BidirectionalIterator>::value_type>)
@@ -4066,13 +4128,13 @@
* 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
+ inline bool
prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_BidirectionalIterator>::value_type>)
@@ -4131,13 +4193,13 @@
*
* 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 @p last1.
*/
template<typename _InputIterator, typename _ForwardIterator>
- _InputIterator
+ inline _InputIterator
find_first_of(_InputIterator __first1, _InputIterator __last1,
_ForwardIterator __first2, _ForwardIterator __last2)
{
// concept requirements
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator>::value_type,
Index: bits/stl_algobase.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_algobase.h,v
retrieving revision 1.30.6.11
diff -u -6 -r1.30.6.11 stl_algobase.h
--- bits/stl_algobase.h 7 Jun 2005 00:29:12 -0000 1.30.6.11
+++ bits/stl_algobase.h 13 Jun 2005 17:02:01 -0000
@@ -351,13 +351,13 @@
/**
* @brief Copies the range [first,last) into result.
* @param first An input iterator.
* @param last An input iterator.
* @param result An output iterator.
- * @return result + (first - last)
+ * @return result + (last - first)
*
* 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). Result may not be contained within
* [first,last); the copy_backward function should be used instead.
@@ -378,13 +378,28 @@
const bool __in = __is_normal_iterator<_InputIterator>::__value;
const bool __out = __is_normal_iterator<_OutputIterator>::__value;
return std::__copy_normal<__in, __out>::copy_n(__first, __last,
__result);
}
-
+
+ /**
+ * @brief Moves the range [first,last) into result.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param result An output iterator.
+ * @return result + (last - first)
+ *
+ * Uses __gnu_cxx::__move to move each element in the input range to the
+ * output range. The values in the input range are left in a valid but
+ * undefined state. 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 typename __enable_if<_OutputIterator,
__gnu_cxx::__is_moveable<
typename std::iterator_traits<_OutputIterator>::value_type>::value &&
__are_same<typename std::iterator_traits<_InputIterator>::value_type,
typename std::iterator_traits<_OutputIterator>::value_type>
@@ -393,13 +408,23 @@
_OutputIterator __result)
{
for(; __first != __last; ++__result, ++__first)
*__result = __gnu_cxx::__move(*__first);
return __result;
}
-
+
+ /**
+ * @brief Moves the range [first,last) into result.
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param result An output iterator.
+ * @return result + (last - first)
+ *
+ * Used when a type is not specialized for move semantics. Simply calls
+ * std::copy with the given values and returns its result.
+ */
template<typename _InputIterator, typename _OutputIterator>
inline typename __enable_if<_OutputIterator,
!(__gnu_cxx::__is_moveable<
typename std::iterator_traits<_OutputIterator>::value_type>::value &&
__are_same<typename std::iterator_traits<_InputIterator>::value_type,
typename std::iterator_traits<_OutputIterator>::value_type>
@@ -502,13 +527,13 @@
copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
{ return _BI2(std::__copy_backward_aux(__first.base(), __last.base(),
__result.base())); }
};
/**
- * @brief Copies the range [first,last) into result.
+ * @brief Moves the range [first,last) into result.
* @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
@@ -536,12 +561,22 @@
const bool __bi1 = __is_normal_iterator<_BI1>::__value;
const bool __bi2 = __is_normal_iterator<_BI2>::__value;
return std::__copy_backward_normal<__bi1, __bi2>::copy_b_n(__first, __last,
__result);
}
+ /**
+ * @brief Copies the range [first,last) into result.
+ * @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_backward, except it uses
+ * __gnu_cxx::__move to move the values rather than copy them.
+ */
template<typename _InputIterator, typename _OutputIterator>
inline
typename __enable_if<_OutputIterator,
__gnu_cxx::__is_moveable<
typename iterator_traits<_OutputIterator>::value_type>::value &&
__are_same<typename iterator_traits<_InputIterator>::value_type,
@@ -551,13 +586,23 @@
_OutputIterator __result)
{
while (__first != __last)
*--__result = __gnu_cxx::__move(*--__last);
return __result;
}
-
+
+ /**
+ * @brief Moves the range [first,last) into result.
+ * @param first A bidirectional iterator.
+ * @param last A bidirectional iterator.
+ * @param result A bidirectional iterator.
+ * @return result - (first - last)
+ *
+ * Used for non-moveable types, this simply calls copy_backward with the
+ * given values, and returns its result.
+ */
template<typename _InputIterator, typename _OutputIterator>
inline
typename __enable_if<_OutputIterator,
!(__gnu_cxx::__is_moveable<
typename iterator_traits<_OutputIterator>::value_type>::value &&
__are_same<typename iterator_traits<_InputIterator>::value_type,
@@ -759,13 +804,13 @@
* This compares the elements of two ranges using @c == and returns a pair
* of iterators. The first iterator points into the first range, the
* second iterator points into the second range, and the elements pointed
* to by the iterators are not equal.
*/
template<typename _InputIterator1, typename _InputIterator2>
- pair<_InputIterator1, _InputIterator2>
+ inline pair<_InputIterator1, _InputIterator2>
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2)
{
// concept requirements
__glibcxx_function_requires(_EqualOpConcept<
typename iterator_traits<_InputIterator1>::value_type,
@@ -877,13 +922,13 @@
* [first1,last1) is lexicographically less than the sequence of elements
* defined by the range [first2,last2). Returns false otherwise."
* (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
* then this is an inline call to @c memcmp.
*/
template<typename _InputIterator1, typename _InputIterator2>
- bool
+ inline bool
lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
// concept requirements
__glibcxx_function_requires(_LessThanOpConcept<
typename iterator_traits<_InputIterator1>::value_type,
Index: bits/stl_heap.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_heap.h,v
retrieving revision 1.16.6.2
diff -u -6 -r1.16.6.2 stl_heap.h
--- bits/stl_heap.h 20 May 2005 15:08:34 -0000 1.16.6.2
+++ bits/stl_heap.h 13 Jun 2005 17:02:01 -0000
@@ -83,23 +83,23 @@
++__parent;
}
return true;
}
template<typename _RandomAccessIterator, typename _Distance>
- bool
+ inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
{ return std::__is_heap(__first, __gnu_cxx::__ops::less(), __n); }
template<typename _RandomAccessIterator>
- bool
+ inline bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{ return std::__is_heap(__first, std::distance(__first, __last)); }
template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
- bool
+ inline bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_StrictWeakOrdering __comp)
{ return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
@@ -330,13 +330,13 @@
* @param last End of heap.
* @ingroup heap
*
* This operation makes the elements in [first,last) into a heap.
*/
template<typename _RandomAccessIterator>
- void
+ inline void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;
@@ -378,13 +378,13 @@
* @param last End of heap.
* @ingroup heap
*
* This operation sorts the valid heap in the range [first,last).
*/
template<typename _RandomAccessIterator>
- void
+ inline void
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<
typename iterator_traits<_RandomAccessIterator>::value_type>)
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |