[RFC] Moving apart SGI extensions
Paolo Carlini
pcarlini@unitus.it
Mon Dec 24 18:11:00 GMT 2001
Hi all,
a while ago, Benjamin suggested auditing the library for SGI extensions. I
started today from stl_algo.h and found the following:
count (returning void)
count_if (returing void)
random_sample
random_sample_n (+ helpers)
is_heap (+ helpers)
is_sorted
For the time being I have simply moved them at the end of the file inside
namespace __gnu_cxx (with the minimal necessary adjustments, basically a few
added std::). This structure is similar to what currently happens for the
installed g++-v3/exception.
What else should I do? Even inside __gnu_cxx should the names be uglifyied? In
case, how exactly, i.e., how when, f.i., __random_sample and random_sample are
both already used??
Perhaps another namespace (not __gnu_cxx) should be used for SGI extensions vs
general extensions?
Cheers,
Paolo.
//////////////////
--- stl_algo.h.orig Sun Dec 23 10:58:20 2001
+++ stl_algo.h Sun Dec 23 11:17:44 2001
@@ -292,42 +292,7 @@ namespace std
return __last;
}
- // count and count_if. There are two version of each, one whose return type
- // type is void and one (present only if we have partial specialization)
- // whose return type is iterator_traits<_InputIter>::difference_type. The
- // C++ standard only has the latter version, but the former, which was
present
- // in the HP STL, is retained for backward compatibility.
-
- template<typename _InputIter, typename _Tp, typename _Size>
- void
- count(_InputIter __first, _InputIter __last,
- const _Tp& __value,
- _Size& __n)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_InputIter>::value_type >)
- __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
- for ( ; __first != __last; ++__first)
- if (*__first == __value)
- ++__n;
- }
-
- template<typename _InputIter, typename _Predicate, typename _Size>
- void
- count_if(_InputIter __first, _InputIter __last,
- _Predicate __pred,
- _Size& __n)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
- typename iterator_traits<_InputIter>::value_type>)
- for ( ; __first != __last; ++__first)
- if (__pred(*__first))
- ++__n;
- }
+ // count and count_if.
template<typename _InputIter, typename _Tp>
typename iterator_traits<_InputIter>::difference_type
@@ -1177,146 +1142,6 @@ __result, __binary_pred, _IterType());
iter_swap(__i, __first + __rand((__i - __first) + 1));
}
- // random_sample and random_sample_n (extensions, not part of the standard).
-
- template<typename _ForwardIter, typename _OutputIter, typename _Distance>
- _OutputIter
- random_sample_n(_ForwardIter __first, _ForwardIter __last,
- _OutputIter __out, const _Distance __n)
- {
- // concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_ForwardIter>::value_type>)
-
- _Distance __remaining = distance(__first, __last);
- _Distance __m = min(__n, __remaining);
-
- while (__m > 0) {
- if (__random_number(__remaining) < __m) {
- *__out = *__first;
- ++__out;
- --__m;
- }
-
- --__remaining;
- ++__first;
- }
- return __out;
- }
-
- template<typename _ForwardIter, typename _OutputIter, typename _Distance,
- typename _RandomNumberGenerator>
- _OutputIter
- random_sample_n(_ForwardIter __first, _ForwardIter __last,
- _OutputIter __out, const _Distance __n,
- _RandomNumberGenerator& __rand)
- {
- // concept requirements
- __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
- __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
- typename iterator_traits<_ForwardIter>::value_type>)
- __glibcpp_function_requires(_UnaryFunctionConcept<
- _RandomNumberGenerator, _Distance, _Distance>)
-
- _Distance __remaining = distance(__first, __last);
- _Distance __m = min(__n, __remaining);
-
- while (__m > 0) {
- if (__rand(__remaining) < __m) {
- *__out = *__first;
- ++__out;
- --__m;
- }
-
- --__remaining;
- ++__first;
- }
- return __out;
- }
-
- template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
- _RandomAccessIter
- __random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out,
- const _Distance __n)
- {
- _Distance __m = 0;
- _Distance __t = __n;
- for ( ; __first != __last && __m < __n; ++__m, ++__first)
- __out[__m] = *__first;
-
- while (__first != __last) {
- ++__t;
- _Distance __M = __random_number(__t);
- if (__M < __n)
- __out[__M] = *__first;
- ++__first;
- }
-
- return __out + __m;
- }
-
- template<typename _InputIter, typename _RandomAccessIter,
- typename _RandomNumberGenerator, typename _Distance>
- _RandomAccessIter
- __random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out,
- _RandomNumberGenerator& __rand,
- const _Distance __n)
- {
- // concept requirements
- __glibcpp_function_requires(_UnaryFunctionConcept<
- _RandomNumberGenerator, _Distance, _Distance>)
-
- _Distance __m = 0;
- _Distance __t = __n;
- for ( ; __first != __last && __m < __n; ++__m, ++__first)
- __out[__m] = *__first;
-
- while (__first != __last) {
- ++__t;
- _Distance __M = __rand(__t);
- if (__M < __n)
- __out[__M] = *__first;
- ++__first;
- }
-
- return __out + __m;
- }
-
- template<typename _InputIter, typename _RandomAccessIter>
- inline _RandomAccessIter
- random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out_first, _RandomAccessIter __out_last)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIter>)
-
- return __random_sample(__first, __last,
- __out_first, __out_last - __out_first);
- }
-
-
- template<typename _InputIter, typename _RandomAccessIter,
- typename _RandomNumberGenerator>
- inline _RandomAccessIter
- random_sample(_InputIter __first, _InputIter __last,
- _RandomAccessIter __out_first, _RandomAccessIter __out_last,
- _RandomNumberGenerator& __rand)
- {
- // concept requirements
- __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
- __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
- _RandomAccessIter>)
-
- return __random_sample(__first, __last,
- __out_first, __rand,
- __out_last - __out_first);
- }
-
// partition, stable_partition, and their auxiliary functions
template<typename _ForwardIter, typename _Predicate>
@@ -3491,6 +3316,184 @@ __result, __binary_pred, _IterType());
__comp);
}
+} // namespace std
+
+
+namespace __gnu_cxx
+{
+ // count and count_if: this version, whose return type is void, was present
+ // in the HP STL, and is retained as an extension for backward compatibility.
+
+ template<typename _InputIter, typename _Tp, typename _Size>
+ void
+ count(_InputIter __first, _InputIter __last,
+ const _Tp& __value,
+ _Size& __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_EqualityComparableConcept<
+ typename std::iterator_traits<_InputIter>::value_type >)
+ __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
+ for ( ; __first != __last; ++__first)
+ if (*__first == __value)
+ ++__n;
+ }
+
+ template<typename _InputIter, typename _Predicate, typename _Size>
+ void
+ count_if(_InputIter __first, _InputIter __last,
+ _Predicate __pred,
+ _Size& __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
+ typename std::iterator_traits<_InputIter>::value_type>)
+ for ( ; __first != __last; ++__first)
+ if (__pred(*__first))
+ ++__n;
+ }
+
+ // random_sample and random_sample_n (extensions, not part of the standard).
+
+ template<typename _ForwardIter, typename _OutputIter, typename _Distance>
+ _OutputIter
+ random_sample_n(_ForwardIter __first, _ForwardIter __last,
+ _OutputIter __out, const _Distance __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+ __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+ typename std::iterator_traits<_ForwardIter>::value_type>)
+
+ _Distance __remaining = std::distance(__first, __last);
+ _Distance __m = std::min(__n, __remaining);
+
+ while (__m > 0) {
+ if (std::__random_number(__remaining) < __m) {
+ *__out = *__first;
+ ++__out;
+ --__m;
+ }
+
+ --__remaining;
+ ++__first;
+ }
+ return __out;
+ }
+
+ template<typename _ForwardIter, typename _OutputIter, typename _Distance,
+ typename _RandomNumberGenerator>
+ _OutputIter
+ random_sample_n(_ForwardIter __first, _ForwardIter __last,
+ _OutputIter __out, const _Distance __n,
+ _RandomNumberGenerator& __rand)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
+ __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
+ typename std::iterator_traits<_ForwardIter>::value_type>)
+ __glibcpp_function_requires(_UnaryFunctionConcept<
+ _RandomNumberGenerator, _Distance, _Distance>)
+
+ _Distance __remaining = std::distance(__first, __last);
+ _Distance __m = std::min(__n, __remaining);
+
+ while (__m > 0) {
+ if (__rand(__remaining) < __m) {
+ *__out = *__first;
+ ++__out;
+ --__m;
+ }
+
+ --__remaining;
+ ++__first;
+ }
+ return __out;
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
+ _RandomAccessIter
+ __random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out,
+ const _Distance __n)
+ {
+ _Distance __m = 0;
+ _Distance __t = __n;
+ for ( ; __first != __last && __m < __n; ++__m, ++__first)
+ __out[__m] = *__first;
+
+ while (__first != __last) {
+ ++__t;
+ _Distance __M = std::__random_number(__t);
+ if (__M < __n)
+ __out[__M] = *__first;
+ ++__first;
+ }
+
+ return __out + __m;
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter,
+ typename _RandomNumberGenerator, typename _Distance>
+ _RandomAccessIter
+ __random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out,
+ _RandomNumberGenerator& __rand,
+ const _Distance __n)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_UnaryFunctionConcept<
+ _RandomNumberGenerator, _Distance, _Distance>)
+
+ _Distance __m = 0;
+ _Distance __t = __n;
+ for ( ; __first != __last && __m < __n; ++__m, ++__first)
+ __out[__m] = *__first;
+
+ while (__first != __last) {
+ ++__t;
+ _Distance __M = __rand(__t);
+ if (__M < __n)
+ __out[__M] = *__first;
+ ++__first;
+ }
+
+ return __out + __m;
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter>
+ inline _RandomAccessIter
+ random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out_first, _RandomAccessIter __out_last)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIter>)
+
+ return __random_sample(__first, __last,
+ __out_first, __out_last - __out_first);
+ }
+
+ template<typename _InputIter, typename _RandomAccessIter,
+ typename _RandomNumberGenerator>
+ inline _RandomAccessIter
+ random_sample(_InputIter __first, _InputIter __last,
+ _RandomAccessIter __out_first, _RandomAccessIter __out_last,
+ _RandomNumberGenerator& __rand)
+ {
+ // concept requirements
+ __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
+ __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIter>)
+
+ return __random_sample(__first, __last,
+ __out_first, __rand,
+ __out_last - __out_first);
+ }
+
// is_heap, a predicate testing whether or not a range is
// a heap. This function is an extension, not part of the C++
// standard.
@@ -3532,12 +3535,11 @@ __result, __binary_pred, _IterType());
// concept requirements
__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
__glibcpp_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIter>::value_type>)
+ typename std::iterator_traits<_RandomAccessIter>::value_type>)
return __is_heap(__first, __last - __first);
}
-
template<typename _RandomAccessIter, typename _StrictWeakOrdering>
inline bool
is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
@@ -3546,8 +3548,8 @@ __result, __binary_pred, _IterType());
// concept requirements
__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
__glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
- typename iterator_traits<_RandomAccessIter>::value_type,
- typename iterator_traits<_RandomAccessIter>::value_type>)
+ typename std::iterator_traits<_RandomAccessIter>::value_type,
+ typename std::iterator_traits<_RandomAccessIter>::value_type>)
return __is_heap(__first, __comp, __last - __first);
}
@@ -3563,7 +3565,7 @@ __result, __binary_pred, _IterType());
// concept requirements
__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
__glibcpp_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIter>::value_type>)
+ typename std::iterator_traits<_ForwardIter>::value_type>)
if (__first == __last)
return true;
@@ -3584,8 +3586,8 @@ __result, __binary_pred, _IterType());
// concept requirements
__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
__glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
- typename iterator_traits<_ForwardIter>::value_type,
- typename iterator_traits<_ForwardIter>::value_type>)
+ typename std::iterator_traits<_ForwardIter>::value_type,
+ typename std::iterator_traits<_ForwardIter>::value_type>)
if (__first == __last)
return true;
@@ -3599,7 +3601,7 @@ __result, __binary_pred, _IterType());
return true;
}
-} // namespace std
+} // namespace __gnu_cxx
#endif /* __GLIBCPP_INTERNAL_ALGO_H */
More information about the Libstdc++
mailing list