This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[patch]: Removing duplicate functions, part 3
- From: Chris Jefferson <caj at cs dot york dot ac dot uk>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 13 Feb 2005 15:00:20 +0000
- Subject: [patch]: Removing duplicate functions, part 3
This file finishes (I think, I'm going to make one more pass) the
removal of duplicate functions in <algorithm>, removing them from
stl_algobase.h and stl_heap.h. I haven't bothered including test cases
as there are already complete testcases for them.
Chris
Index: stl_algobase.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_algobase.h,v
retrieving revision 1.30.6.6
diff -u -r1.30.6.6 stl_algobase.h
--- stl_algobase.h 1 Feb 2005 16:06:59 -0000 1.30.6.6
+++ stl_algobase.h 13 Feb 2005 14:41:44 -0000
@@ -167,20 +167,18 @@
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
+ * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The lesser of the parameters.
*
- * This is the simple classic generic implementation. It will work on
- * temporary expressions, since they are only evaluated once, unlike a
- * preprocessor macro.
+ * This will work on temporary expressions, since they are only evaluated
+ * once, unlike a preprocessor macro.
*/
- template<typename _Tp>
+ template<typename _Tp, typename _Compare>
inline const _Tp&
- min(const _Tp& __a, const _Tp& __b)
+ min(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
- // concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- //return __b < __a ? __b : __a;
- if (__b < __a)
+ //return __comp(__b, __a) ? __b : __a;
+ if (__comp(__b, __a))
return __b;
return __a;
}
@@ -189,20 +187,18 @@
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
+ * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The greater of the parameters.
*
- * This is the simple classic generic implementation. It will work on
- * temporary expressions, since they are only evaluated once, unlike a
- * preprocessor macro.
+ * This will work on temporary expressions, since they are only evaluated
+ * once, unlike a preprocessor macro.
*/
- template<typename _Tp>
+ template<typename _Tp, typename _Compare>
inline const _Tp&
- max(const _Tp& __a, const _Tp& __b)
+ max(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
- // concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- //return __a < __b ? __b : __a;
- if (__a < __b)
+ //return __comp(__a, __b) ? __b : __a;
+ if (__comp(__a, __b))
return __b;
return __a;
}
@@ -211,40 +207,38 @@
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
- * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The lesser of the parameters.
*
- * This will work on temporary expressions, since they are only evaluated
- * once, unlike a preprocessor macro.
+ * This is the simple classic generic implementation. It will work on
+ * temporary expressions, since they are only evaluated once, unlike a
+ * preprocessor macro.
*/
- template<typename _Tp, typename _Compare>
+ template<typename _Tp>
inline const _Tp&
- min(const _Tp& __a, const _Tp& __b, _Compare __comp)
+ min(const _Tp& __a, const _Tp& __b)
{
- //return __comp(__b, __a) ? __b : __a;
- if (__comp(__b, __a))
- return __b;
- return __a;
+ // concept requirements
+ __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+ return min(__a, __b, __gnu_cxx::__ops::less());
}
/**
* @brief This does what you think it does.
* @param a A thing of arbitrary type.
* @param b Another thing of arbitrary type.
- * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
* @return The greater of the parameters.
*
- * This will work on temporary expressions, since they are only evaluated
- * once, unlike a preprocessor macro.
+ * This is the simple classic generic implementation. It will work on
+ * temporary expressions, since they are only evaluated once, unlike a
+ * preprocessor macro.
*/
- template<typename _Tp, typename _Compare>
+ template<typename _Tp>
inline const _Tp&
- max(const _Tp& __a, const _Tp& __b, _Compare __comp)
+ max(const _Tp& __a, const _Tp& __b)
{
- //return __comp(__a, __b) ? __b : __a;
- if (__comp(__a, __b))
- return __b;
- return __a;
+ // concept requirements
+ __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+ return max(__a, __b, __gnu_cxx::__ops::less());
}
// All of these auxiliary structs serve two purposes. (1) Replace
Index: stl_heap.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_heap.h,v
retrieving revision 1.16
diff -u -r1.16 stl_heap.h
--- stl_heap.h 8 Feb 2004 04:46:42 -0000 1.16
+++ stl_heap.h 13 Feb 2005 14:41:47 -0000
@@ -1,6 +1,6 @@
// Heap implementation -*- C++ -*-
-// Copyright (C) 2001, 2004 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
@@ -61,27 +61,13 @@
#define _STL_HEAP_H 1
#include <debug/debug.h>
+#include <bits/predefined_ops.h>
namespace std
{
// is_heap, a predicate testing whether or not a range is
// a heap. This function is an extension, not part of the C++
// standard.
- template<typename _RandomAccessIterator, typename _Distance>
- bool
- __is_heap(_RandomAccessIterator __first, _Distance __n)
- {
- _Distance __parent = 0;
- for (_Distance __child = 1; __child < __n; ++__child)
- {
- if (__first[__parent] < __first[__child])
- return false;
- if ((__child & 1) == 0)
- ++__parent;
- }
- return true;
- }
-
template<typename _RandomAccessIterator, typename _Distance,
typename _StrictWeakOrdering>
bool
@@ -99,6 +85,11 @@
return true;
}
+ template<typename _RandomAccessIterator, typename _Distance>
+ bool
+ __is_heap(_RandomAccessIterator __first, _Distance __n)
+ { return std::__is_heap(__first, __n, __gnu_cxx::__ops::less()); }
+
template<typename _RandomAccessIterator>
bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
@@ -112,50 +103,6 @@
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
- void
- __push_heap(_RandomAccessIterator __first,
- _Distance __holeIndex, _Distance __topIndex, _Tp __value)
- {
- _Distance __parent = (__holeIndex - 1) / 2;
- while (__holeIndex > __topIndex && *(__first + __parent) < __value)
- {
- *(__first + __holeIndex) = *(__first + __parent);
- __holeIndex = __parent;
- __parent = (__holeIndex - 1) / 2;
- }
- *(__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)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
-
- // concept requirements
- __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- __glibcxx_requires_valid_range(__first, __last);
- // __glibcxx_requires_heap(__first, __last - 1);
-
- std::__push_heap(__first, _DistanceType((__last - __first) - 1),
- _DistanceType(0), _ValueType(*(__last - 1)));
- }
-
template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
typename _Compare>
void
@@ -204,66 +151,33 @@
_DistanceType(0), _ValueType(*(__last - 1)), __comp);
}
- template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
- void
- __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
- _Distance __len, _Tp __value)
- {
- const _Distance __topIndex = __holeIndex;
- _Distance __secondChild = 2 * __holeIndex + 2;
- while (__secondChild < __len)
- {
- if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
- __secondChild--;
- *(__first + __holeIndex) = *(__first + __secondChild);
- __holeIndex = __secondChild;
- __secondChild = 2 * (__secondChild + 1);
- }
- if (__secondChild == __len)
- {
- *(__first + __holeIndex) = *(__first + (__secondChild - 1));
- __holeIndex = __secondChild - 1;
- }
- std::__push_heap(__first, __holeIndex, __topIndex, __value);
- }
-
- template<typename _RandomAccessIterator, typename _Tp>
- inline void
- __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
- _RandomAccessIterator __result, _Tp __value)
- {
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _Distance;
- *__result = *__first;
- std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
- __value);
- }
-
/**
- * @brief Pop an element off a heap.
+ * @brief Push an element onto a heap.
* @param first Start of heap.
- * @param last End of heap.
+ * @param last End of heap + element.
* @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.
+ * 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
- pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+ push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
+ _ValueType;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
- __glibcxx_requires_heap(__first, __last);
- std::__pop_heap(__first, __last - 1, __last - 1,
- _ValueType(*(__last - 1)));
+ std::__push_heap(__first, _DistanceType((__last - __first) - 1),
+ _DistanceType(0), _ValueType(*(__last - 1)),
+ __gnu_cxx::__ops::less());
}
template<typename _RandomAccessIterator, typename _Distance,
@@ -332,41 +246,30 @@
}
/**
- * @brief Construct a heap over a range.
+ * @brief Pop an element off a heap.
* @param first Start of heap.
* @param last End of heap.
* @ingroup heap
*
- * This operation makes the elements in [first,last) into a 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>
- void
- make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+ inline void
+ pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_RandomAccessIterator>::difference_type
- _DistanceType;
+ _ValueType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
+ __glibcxx_requires_heap(__first, __last);
- if (__last - __first < 2)
- return;
-
- const _DistanceType __len = __last - __first;
- _DistanceType __parent = (__len - 2) / 2;
- while (true)
- {
- std::__adjust_heap(__first, __parent, __len,
- _ValueType(*(__first + __parent)));
- if (__parent == 0)
- return;
- __parent--;
- }
+ std::__pop_heap(__first, __last - 1, __last - 1,
+ _ValueType(*(__last - 1)), __gnu_cxx::__ops::less());
}
/**
@@ -410,27 +313,26 @@
}
/**
- * @brief Sort a heap.
+ * @brief Construct a heap over a range.
* @param first Start of heap.
* @param last End of heap.
* @ingroup heap
*
- * This operation sorts the valid heap in the range [first,last).
+ * This operation makes the elements in [first,last) into a heap.
*/
template<typename _RandomAccessIterator>
void
- sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
+ make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+
// concept requirements
- __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIterator>)
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIterator>::value_type>)
- __glibcxx_requires_valid_range(__first, __last);
- // __glibcxx_requires_heap(__first, __last);
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- while (__last - __first > 1)
- std::pop_heap(__first, __last--);
+ std::make_heap(__first, __last, __gnu_cxx::__ops::less());
}
/**
@@ -458,6 +360,25 @@
std::pop_heap(__first, __last--, __comp);
}
+ /**
+ * @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)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_LessThanComparableConcept<
+ typename iterator_traits<_RandomAccessIterator>::value_type>)
+
+ std::sort_heap(__first, __last, __gnu_cxx::__ops::less());
+ }
+
} // namespace std
#endif /* _STL_HEAP_H */
2005-02-12 Christopher Jefferson <chris@bubblescope.net>
* include/bits/stl_heap.h (__is_heap, __push_heap, push_heap,
pop_heap, make_heap, sort_heap) : Make non-predicated version call
predicated version.
* include/bits/stl_heap.h (__push_heap, __pop_heap, __adjust_heap) :
Remove unused overloads.
* include/bits/stl_algobase.h (min, max) : Make non-predicated version
call predicated version.