#include <bits/stl_heap.h>
#include <bits/stl_tempbuf.h> // for _Temporary_buffer
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#include <random> // for std::uniform_int_distribution
+#endif
+
// See concept_check.h for the __glibcxx_*_requires macros.
_GLIBCXX_BEGIN_NAMESPACE(std)
- /**
- * @brief Find the median of three values.
- * @param a A value.
- * @param b A value.
- * @param c A value.
- * @return One of @p a, @p b or @p c.
- *
- * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
- * then the value returned will be @c m.
- * This is an SGI extension.
- * @ingroup SGIextensions
- */
- template<typename _Tp>
- inline const _Tp&
- __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
- {
- // concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- if (__a < __b)
- if (__b < __c)
- return __b;
- else if (__a < __c)
- return __c;
- else
- return __a;
- else if (__a < __c)
- return __a;
- else if (__b < __c)
- return __c;
- else
- return __b;
- }
-
- /**
- * @brief Find the median of three values using a predicate for comparison.
- * @param a A value.
- * @param b A value.
- * @param c A value.
- * @param comp A binary predicate.
- * @return One of @p a, @p b or @p c.
- *
- * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
- * and @p comp(m,n) are both true then the value returned will be @c m.
- * This is an SGI extension.
- * @ingroup SGIextensions
- */
- template<typename _Tp, typename _Compare>
- inline const _Tp&
- __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
- {
- // concept requirements
- __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
- _Tp, _Tp>)
- if (__comp(__a, __b))
- if (__comp(__b, __c))
- return __b;
- else if (__comp(__a, __c))
- return __c;
- else
- return __a;
- else if (__comp(__a, __c))
- return __a;
- else if (__comp(__b, __c))
- return __c;
- else
- return __b;
- }
-
/// Swaps the median value of *__a, *__b and *__c to *__a
template<typename _Iterator>
void
}
}
- /// This is a helper function for the sort routines. Precondition: __n > 0.
- template<typename _Size>
- inline _Size
- __lg(_Size __n)
- {
- _Size __k;
- for (__k = 0; __n != 0; __n >>= 1)
- ++__k;
- return __k - 1;
- }
-
- inline int
- __lg(int __n)
- { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
-
- inline long
- __lg(long __n)
- { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
-
- inline long long
- __lg(long long __n)
- { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
-
// sort
template<typename _RandomAccessIterator, typename _Size>
// nth_element
- /**
- * @brief Finds the first position in which @a val could be inserted
- * without changing the ordering.
- * @param first An iterator.
- * @param last Another iterator.
- * @param val The search term.
- * @return An iterator pointing to the first element <em>not less
- * than</em> @a val, or end() if every element is less than
- * @a val.
- * @ingroup binary_search_algorithms
- */
- template<typename _ForwardIterator, typename _Tp>
- _ForwardIterator
- lower_bound(_ForwardIterator __first, _ForwardIterator __last,
- const _Tp& __val)
- {
- typedef typename iterator_traits<_ForwardIterator>::value_type
- _ValueType;
- typedef typename iterator_traits<_ForwardIterator>::difference_type
- _DistanceType;
-
- // concept requirements
- __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
- __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
- __glibcxx_requires_partitioned_lower(__first, __last, __val);
-
- _DistanceType __len = std::distance(__first, __last);
- _DistanceType __half;
- _ForwardIterator __middle;
-
- while (__len > 0)
- {
- __half = __len >> 1;
- __middle = __first;
- std::advance(__middle, __half);
- if (*__middle < __val)
- {
- __first = __middle;
- ++__first;
- __len = __len - __half - 1;
- }
- else
- __len = __half;
- }
- return __first;
- }
+ // lower_bound moved to stl_algobase.h
/**
* @brief Finds the first position in which @a val could be inserted
return std::make_pair(__min, __max);
}
- // N2722 + fixes.
+ // N2722 + DR 915.
template<typename _Tp>
inline _Tp
min(initializer_list<_Tp> __l)
std::minmax_element(__l.begin(), __l.end(), __comp);
return std::make_pair(*__p.first, *__p.second);
}
+
+#ifdef _GLIBCXX_USE_C99_STDINT_TR1
+ /**
+ * @brief Shuffle the elements of a sequence using a uniform random
+ * number generator.
+ * @ingroup mutating_algorithms
+ * @param first A forward iterator.
+ * @param last A forward iterator.
+ * @param g A UniformRandomNumberGenerator (26.5.1.3).
+ * @return Nothing.
+ *
+ * Reorders the elements in the range @p [first,last) using @p g to
+ * provide random numbers.
+ */
+ template<typename _RandomAccessIterator,
+ typename _UniformRandomNumberGenerator>
+ void
+ shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _UniformRandomNumberGenerator& __g)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
+ _RandomAccessIterator>)
+ __glibcxx_requires_valid_range(__first, __last);
+
+ if (__first == __last)
+ return;
+
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _DistanceType;
+
+ typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
+ typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
+ typedef typename __distr_type::param_type __p_type;
+ __distr_type __d;
+
+ for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
+ }
+#endif
+
#endif // __GXX_EXPERIMENTAL_CXX0X__
_GLIBCXX_END_NAMESPACE
* @param first An input iterator.
* @param last An input iterator.
* @param f A unary function object.
- * @return @p f.
+ * @return @p f (std::move(@p f) in C++0x).
*
* Applies the function object @p f to each element in the range
* @p [first,last). @p f must not modify the order of the sequence.
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
__f(*__first);
- return __f;
+ return _GLIBCXX_MOVE(__f);
}
/**
template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ _RandomNumberGenerator&& __rand)
+#else
_RandomNumberGenerator& __rand)
+#endif
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
OSDN Git Service
