diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_algo.h')
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 3934 |
1 files changed, 2030 insertions, 1904 deletions
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 160dc2f8abc..549c0cac7e7 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -1,6 +1,6 @@ // Algorithm implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -62,9 +62,10 @@ #ifndef _STL_ALGO_H #define _STL_ALGO_H 1 +#include <cstdlib> // for rand +#include <bits/algorithmfwd.h> #include <bits/stl_heap.h> #include <bits/stl_tempbuf.h> // for _Temporary_buffer -#include <cstdlib> // for rand #include <debug/debug.h> // See concept_check.h for the __glibcxx_*_requires macros. @@ -122,7 +123,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { // concept requirements - __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>) + __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, + _Tp, _Tp>) if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; @@ -138,34 +140,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __b; } - /** - * @brief Apply a function to every element of a sequence. - * @param first An input iterator. - * @param last An input iterator. - * @param f A unary function object. - * @return @p f. - * - * 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. - * If @p f has a return value it is ignored. - */ - template<typename _InputIterator, typename _Function> - _Function - for_each(_InputIterator __first, _InputIterator __last, _Function __f) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_requires_valid_range(__first, __last); - for (; __first != __last; ++__first) - __f(*__first); - return __f; - } + // for_each - /** - * @if maint - * This is an overload used by find() for the Input Iterator case. - * @endif - */ + /// This is an overload used by find() for the Input Iterator case. template<typename _InputIterator, typename _Tp> inline _InputIterator __find(_InputIterator __first, _InputIterator __last, @@ -176,11 +153,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __first; } - /** - * @if maint - * This is an overload used by find_if() for the Input Iterator case. - * @endif - */ + /// This is an overload used by find_if() for the Input Iterator case. template<typename _InputIterator, typename _Predicate> inline _InputIterator __find_if(_InputIterator __first, _InputIterator __last, @@ -191,11 +164,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __first; } - /** - * @if maint - * This is an overload used by find() for the RAI case. - * @endif - */ + /// This is an overload used by find() for the RAI case. template<typename _RandomAccessIterator, typename _Tp> _RandomAccessIterator __find(_RandomAccessIterator __first, _RandomAccessIterator __last, @@ -243,11 +212,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is an overload used by find_if() for the RAI case. - * @endif - */ + /// This is an overload used by find_if() for the RAI case. template<typename _RandomAccessIterator, typename _Predicate> _RandomAccessIterator __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, @@ -295,457 +260,23 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @brief Find the first occurrence of a value in a sequence. - * @param first An input iterator. - * @param last An input iterator. - * @param val The value to find. - * @return The first iterator @c i in the range @p [first,last) - * such that @c *i == @p val, or @p last if no such iterator exists. - */ - template<typename _InputIterator, typename _Tp> - inline _InputIterator - find(_InputIterator __first, _InputIterator __last, - const _Tp& __val) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_InputIterator>::value_type, _Tp>) - __glibcxx_requires_valid_range(__first, __last); - return std::__find(__first, __last, __val, - std::__iterator_category(__first)); - } - - /** - * @brief Find the first element in a sequence for which a predicate is true. - * @param first An input iterator. - * @param last An input iterator. - * @param pred A predicate. - * @return The first iterator @c i in the range @p [first,last) - * such that @p pred(*i) is true, or @p last if no such iterator exists. - */ - template<typename _InputIterator, typename _Predicate> - inline _InputIterator - find_if(_InputIterator __first, _InputIterator __last, - _Predicate __pred) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - return std::__find_if(__first, __last, __pred, - std::__iterator_category(__first)); - } - - /** - * @brief Find element from a set in a sequence. - * @param first1 Start of range to search. - * @param last1 End of range to search. - * @param first2 Start of match candidates. - * @param last2 End of match candidates. - * @return The first iterator @c i in the range - * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an - * interator in [first2,last2), or @p last1 if no such iterator exists. - * - * 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 - find_first_of(_InputIterator __first1, _InputIterator __last1, - _ForwardIterator __first2, _ForwardIterator __last2) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_InputIterator>::value_type, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - for (; __first1 != __last1; ++__first1) - for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) - if (*__first1 == *__iter) - return __first1; - return __last1; - } - - /** - * @brief Find element from a set in a sequence using a predicate. - * @param first1 Start of range to search. - * @param last1 End of range to search. - * @param first2 Start of match candidates. - * @param last2 End of match candidates. - * @param comp Predicate to use. - * @return The first iterator @c i in the range - * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an - * interator in [first2,last2), or @p last1 if no such iterator exists. - * - * 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, - typename _BinaryPredicate> - _InputIterator - find_first_of(_InputIterator __first1, _InputIterator __last1, - _ForwardIterator __first2, _ForwardIterator __last2, - _BinaryPredicate __comp) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, - typename iterator_traits<_InputIterator>::value_type, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - for (; __first1 != __last1; ++__first1) - for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) - if (__comp(*__first1, *__iter)) - return __first1; - return __last1; - } - - /** - * @brief Find two adjacent values in a sequence that are equal. - * @param first A forward iterator. - * @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 - adjacent_find(_ForwardIterator __first, _ForwardIterator __last) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - if (__first == __last) - return __last; - _ForwardIterator __next = __first; - while(++__next != __last) - { - if (*__first == *__next) - return __first; - __first = __next; - } - return __last; - } - - /** - * @brief Find two adjacent values in a sequence using a predicate. - * @param first A forward iterator. - * @param last A forward iterator. - * @param binary_pred A binary predicate. - * @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 - * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator - * exists. - */ - template<typename _ForwardIterator, typename _BinaryPredicate> - _ForwardIterator - adjacent_find(_ForwardIterator __first, _ForwardIterator __last, - _BinaryPredicate __binary_pred) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, - typename iterator_traits<_ForwardIterator>::value_type, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - if (__first == __last) - return __last; - _ForwardIterator __next = __first; - while(++__next != __last) - { - if (__binary_pred(*__first, *__next)) - return __first; - __first = __next; - } - return __last; - } - - /** - * @brief Count the number of copies of a value in a sequence. - * @param first An input iterator. - * @param last An input iterator. - * @param value The value to be counted. - * @return The number of iterators @c i in the range @p [first,last) - * for which @c *i == @p value - */ - template<typename _InputIterator, typename _Tp> - typename iterator_traits<_InputIterator>::difference_type - count(_InputIterator __first, _InputIterator __last, const _Tp& __value) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_InputIterator>::value_type, _Tp>) - __glibcxx_requires_valid_range(__first, __last); - typename iterator_traits<_InputIterator>::difference_type __n = 0; - for (; __first != __last; ++__first) - if (*__first == __value) - ++__n; - return __n; - } - - /** - * @brief Count the elements of a sequence for which a predicate is true. - * @param first An input iterator. - * @param last An input iterator. - * @param pred A predicate. - * @return The number of iterators @c i in the range @p [first,last) - * for which @p pred(*i) is true. - */ - template<typename _InputIterator, typename _Predicate> - typename iterator_traits<_InputIterator>::difference_type - count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - typename iterator_traits<_InputIterator>::difference_type __n = 0; - for (; __first != __last; ++__first) - if (__pred(*__first)) - ++__n; - return __n; - } - - /** - * @brief Finds the places in ranges which don't match. - * @param first1 An input iterator. - * @param last1 An input iterator. - * @param first2 An input iterator. - * @return A pair of iterators pointing to the first mismatch. - * - * 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> - mismatch(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - - while (__first1 != __last1 && *__first1 == *__first2) - { - ++__first1; - ++__first2; - } - return pair<_InputIterator1, _InputIterator2>(__first1, __first2); - } - - /** - * @brief Finds the places in ranges which don't match. - * @param first1 An input iterator. - * @param last1 An input iterator. - * @param first2 An input iterator. - * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. - * @return A pair of iterators pointing to the first mismatch. - * - * This compares the elements of two ranges using the binary_pred - * parameter, 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, - typename _BinaryPredicate> - pair<_InputIterator1, _InputIterator2> - mismatch(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _BinaryPredicate __binary_pred) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_requires_valid_range(__first1, __last1); - - while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) - { - ++__first1; - ++__first2; - } - return pair<_InputIterator1, _InputIterator2>(__first1, __first2); - } - - /** - * @brief Search a sequence for a matching sub-sequence. - * @param first1 A forward iterator. - * @param last1 A forward iterator. - * @param first2 A forward iterator. - * @param last2 A forward iterator. - * @return The first iterator @c i in the range - * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) - * for each @c N in the range @p [0,last2-first2), or @p last1 if no - * such iterator exists. - * - * Searches the range @p [first1,last1) for a sub-sequence that compares - * equal value-by-value with the sequence given by @p [first2,last2) and - * returns an iterator to the first element of the sub-sequence, or - * @p last1 if the sub-sequence is not found. - * - * Because the sub-sequence must lie completely within the range - * @p [first1,last1) it must start at a position less than - * @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 - search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_ForwardIterator1>::value_type, - typename iterator_traits<_ForwardIterator2>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - // Test for empty ranges - if (__first1 == __last1 || __first2 == __last2) - return __first1; - - // Test for a pattern of length 1. - _ForwardIterator2 __p1(__first2); - if (++__p1 == __last2) - return std::find(__first1, __last1, *__first2); - - // General case. - _ForwardIterator2 __p; - _ForwardIterator1 __current = __first1; - - for (;;) - { - __first1 = std::find(__first1, __last1, *__first2); - if (__first1 == __last1) - return __last1; - - __p = __p1; - __current = __first1; - if (++__current == __last1) - return __last1; - - while (*__current == *__p) - { - if (++__p == __last2) - return __first1; - if (++__current == __last1) - return __last1; - } - ++__first1; - } - return __first1; - } - - /** - * @brief Search a sequence for a matching sub-sequence using a predicate. - * @param first1 A forward iterator. - * @param last1 A forward iterator. - * @param first2 A forward iterator. - * @param last2 A forward iterator. - * @param predicate A binary predicate. - * @return The first iterator @c i in the range - * @p [first1,last1-(last2-first2)) such that - * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range - * @p [0,last2-first2), or @p last1 if no such iterator exists. - * - * Searches the range @p [first1,last1) for a sub-sequence that compares - * equal value-by-value with the sequence given by @p [first2,last2), - * using @p predicate to determine equality, and returns an iterator - * to the first element of the sub-sequence, or @p last1 if no such - * iterator exists. - * - * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) - */ - template<typename _ForwardIterator1, typename _ForwardIterator2, - typename _BinaryPredicate> - _ForwardIterator1 - search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __predicate) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) - __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, - typename iterator_traits<_ForwardIterator1>::value_type, - typename iterator_traits<_ForwardIterator2>::value_type>) - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - // Test for empty ranges - if (__first1 == __last1 || __first2 == __last2) - return __first1; - - // Test for a pattern of length 1. - _ForwardIterator2 __p1(__first2); - if (++__p1 == __last2) - { - while (__first1 != __last1 - && !bool(__predicate(*__first1, *__first2))) - ++__first1; - return __first1; - } - - // General case. - _ForwardIterator2 __p; - _ForwardIterator1 __current = __first1; - - for (;;) - { - while (__first1 != __last1 - && !bool(__predicate(*__first1, *__first2))) - ++__first1; - if (__first1 == __last1) - return __last1; - - __p = __p1; - __current = __first1; - if (++__current == __last1) - return __last1; - - while (__predicate(*__current, *__p)) - { - if (++__p == __last2) - return __first1; - if (++__current == __last1) - return __last1; - } - ++__first1; - } - return __first1; - } + // set_difference + // set_intersection + // set_symmetric_difference + // set_union + // for_each + // find + // find_if + // find_first_of + // adjacent_find + // count + // count_if + // search /** - * @if maint * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) * overloaded for forward iterators. - * @endif */ template<typename _ForwardIterator, typename _Integer, typename _Tp> _ForwardIterator @@ -753,7 +284,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _Integer __count, const _Tp& __val, std::forward_iterator_tag) { - __first = std::find(__first, __last, __val); + __first = _GLIBCXX_STD_P::find(__first, __last, __val); while (__first != __last) { typename iterator_traits<_ForwardIterator>::difference_type @@ -769,17 +300,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __first; if (__i == __last) return __last; - __first = std::find(++__i, __last, __val); + __first = _GLIBCXX_STD_P::find(++__i, __last, __val); } return __last; } /** - * @if maint * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) * overloaded for random access iterators. - * @endif */ template<typename _RandomAccessIter, typename _Integer, typename _Tp> _RandomAccessIter @@ -826,45 +355,13 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @brief Search a sequence for a number of consecutive values. - * @param first A forward iterator. - * @param last A forward iterator. - * @param count The number of consecutive values. - * @param val The value to find. - * @return The first iterator @c i in the range @p [first,last-count) - * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), - * 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 - search_n(_ForwardIterator __first, _ForwardIterator __last, - _Integer __count, const _Tp& __val) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_ForwardIterator>::value_type, _Tp>) - __glibcxx_requires_valid_range(__first, __last); - - if (__count <= 0) - return __first; - if (__count == 1) - return std::find(__first, __last, __val); - return std::__search_n(__first, __last, __count, __val, - std::__iterator_category(__first)); - } + // search_n /** - * @if maint * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, * _BinaryPredicate) * overloaded for forward iterators. - * @endif */ template<typename _ForwardIterator, typename _Integer, typename _Tp, typename _BinaryPredicate> @@ -900,12 +397,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, * _BinaryPredicate) * overloaded for random access iterators. - * @endif */ template<typename _RandomAccessIter, typename _Integer, typename _Tp, typename _BinaryPredicate> @@ -953,46 +448,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @brief Search a sequence for a number of consecutive values using a - * predicate. - * @param first A forward iterator. - * @param last A forward iterator. - * @param count The number of consecutive values. - * @param val The value to find. - * @param binary_pred A binary predicate. - * @return The first iterator @c i in the range @p [first,last-count) - * such that @p binary_pred(*(i+N),val) is true for each @c N in the - * range @p [0,count), or @p last if no such iterator exists. - * - * Searches the range @p [first,last) for @p count consecutive elements - * for which the predicate returns true. - */ - template<typename _ForwardIterator, typename _Integer, typename _Tp, - typename _BinaryPredicate> - _ForwardIterator - search_n(_ForwardIterator __first, _ForwardIterator __last, - _Integer __count, const _Tp& __val, - _BinaryPredicate __binary_pred) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, - typename iterator_traits<_ForwardIterator>::value_type, _Tp>) - __glibcxx_requires_valid_range(__first, __last); - - if (__count <= 0) - return __first; - if (__count == 1) - { - while (__first != __last && !bool(__binary_pred(*__first, __val))) - ++__first; - return __first; - } - return std::__search_n(__first, __last, __count, __val, __binary_pred, - std::__iterator_category(__first)); - } - // find_end for forward iterators. template<typename _ForwardIterator1, typename _ForwardIterator2> _ForwardIterator1 @@ -1008,7 +463,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (1) { _ForwardIterator1 __new_result - = std::search(__first1, __last1, __first2, __last2); + = _GLIBCXX_STD_P::search(__first1, __last1, __first2, __last2); if (__new_result == __last1) return __result; else @@ -1037,7 +492,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (1) { _ForwardIterator1 __new_result - = std::search(__first1, __last1, __first2, __last2, __comp); + = _GLIBCXX_STD_P::search(__first1, __last1, __first2, + __last2, __comp); if (__new_result == __last1) return __result; else @@ -1070,8 +526,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _RevIterator1 __rlast1(__first1); _RevIterator2 __rlast2(__first2); - _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, - _RevIterator2(__last2), __rlast2); + _RevIterator1 __rresult = _GLIBCXX_STD_P::search(_RevIterator1(__last1), + __rlast1, + _RevIterator2(__last2), + __rlast2); if (__rresult == __rlast1) return __last1; @@ -1209,261 +667,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __comp); } - /** - * @brief Perform an operation on a sequence. - * @param first An input iterator. - * @param last An input iterator. - * @param result An output iterator. - * @param unary_op A unary operator. - * @return An output iterator equal to @p result+(last-first). - * - * Applies the operator to each element in the input range and assigns - * the results to successive elements of the output sequence. - * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the - * range @p [0,last-first). - * - * @p unary_op must not alter its argument. - */ - template<typename _InputIterator, typename _OutputIterator, - typename _UnaryOperation> - _OutputIterator - transform(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _UnaryOperation __unary_op) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - // "the type returned by a _UnaryOperation" - __typeof__(__unary_op(*__first))>) - __glibcxx_requires_valid_range(__first, __last); - - for (; __first != __last; ++__first, ++__result) - *__result = __unary_op(*__first); - return __result; - } - - /** - * @brief Perform an operation on corresponding elements of two sequences. - * @param first1 An input iterator. - * @param last1 An input iterator. - * @param first2 An input iterator. - * @param result An output iterator. - * @param binary_op A binary operator. - * @return An output iterator equal to @p result+(last-first). - * - * Applies the operator to the corresponding elements in the two - * input ranges and assigns the results to successive elements of the - * output sequence. - * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each - * @c N in the range @p [0,last1-first1). - * - * @p binary_op must not alter either of its arguments. - */ - template<typename _InputIterator1, typename _InputIterator2, - typename _OutputIterator, typename _BinaryOperation> - _OutputIterator - transform(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _OutputIterator __result, - _BinaryOperation __binary_op) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - // "the type returned by a _BinaryOperation" - __typeof__(__binary_op(*__first1,*__first2))>) - __glibcxx_requires_valid_range(__first1, __last1); - - for (; __first1 != __last1; ++__first1, ++__first2, ++__result) - *__result = __binary_op(*__first1, *__first2); - return __result; - } - - /** - * @brief Replace each occurrence of one value in a sequence with another - * value. - * @param first A forward iterator. - * @param last A forward iterator. - * @param old_value The value to be replaced. - * @param new_value The replacement value. - * @return replace() returns no value. - * - * For each iterator @c i in the range @p [first,last) if @c *i == - * @p old_value then the assignment @c *i = @p new_value is performed. - */ - template<typename _ForwardIterator, typename _Tp> - void - replace(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __old_value, const _Tp& __new_value) - { - // concept requirements - __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< - _ForwardIterator>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_ForwardIterator>::value_type, _Tp>) - __glibcxx_function_requires(_ConvertibleConcept<_Tp, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - for (; __first != __last; ++__first) - if (*__first == __old_value) - *__first = __new_value; - } - - /** - * @brief Replace each value in a sequence for which a predicate returns - * true with another value. - * @param first A forward iterator. - * @param last A forward iterator. - * @param pred A predicate. - * @param new_value The replacement value. - * @return replace_if() returns no value. - * - * For each iterator @c i in the range @p [first,last) if @p pred(*i) - * is true then the assignment @c *i = @p new_value is performed. - */ - template<typename _ForwardIterator, typename _Predicate, typename _Tp> - void - replace_if(_ForwardIterator __first, _ForwardIterator __last, - _Predicate __pred, const _Tp& __new_value) - { - // concept requirements - __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< - _ForwardIterator>) - __glibcxx_function_requires(_ConvertibleConcept<_Tp, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - for (; __first != __last; ++__first) - if (__pred(*__first)) - *__first = __new_value; - } - - /** - * @brief Copy a sequence, replacing each element of one value with another - * value. - * @param first An input iterator. - * @param last An input iterator. - * @param result An output iterator. - * @param old_value The value to be replaced. - * @param new_value The replacement value. - * @return The end of the output sequence, @p result+(last-first). - * - * Copies each element in the input range @p [first,last) to the - * output range @p [result,result+(last-first)) replacing elements - * equal to @p old_value with @p new_value. - */ - template<typename _InputIterator, typename _OutputIterator, typename _Tp> - _OutputIterator - replace_copy(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, - const _Tp& __old_value, const _Tp& __new_value) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_function_requires(_EqualOpConcept< - typename iterator_traits<_InputIterator>::value_type, _Tp>) - __glibcxx_requires_valid_range(__first, __last); - - for (; __first != __last; ++__first, ++__result) - if (*__first == __old_value) - *__result = __new_value; - else - *__result = *__first; - return __result; - } - - /** - * @brief Copy a sequence, replacing each value for which a predicate - * returns true with another value. - * @param first An input iterator. - * @param last An input iterator. - * @param result An output iterator. - * @param pred A predicate. - * @param new_value The replacement value. - * @return The end of the output sequence, @p result+(last-first). - * - * Copies each element in the range @p [first,last) to the range - * @p [result,result+(last-first)) replacing elements for which - * @p pred returns true with @p new_value. - */ - template<typename _InputIterator, typename _OutputIterator, - typename _Predicate, typename _Tp> - _OutputIterator - replace_copy_if(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, - _Predicate __pred, const _Tp& __new_value) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - for (; __first != __last; ++__first, ++__result) - if (__pred(*__first)) - *__result = __new_value; - else - *__result = *__first; - return __result; - } - - /** - * @brief Assign the result of a function object to each value in a - * sequence. - * @param first A forward iterator. - * @param last A forward iterator. - * @param gen A function object taking no arguments. - * @return generate() returns no value. - * - * Performs the assignment @c *i = @p gen() for each @c i in the range - * @p [first,last). - */ - template<typename _ForwardIterator, typename _Generator> - void - generate(_ForwardIterator __first, _ForwardIterator __last, - _Generator __gen) - { - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_GeneratorConcept<_Generator, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - for (; __first != __last; ++__first) - *__first = __gen(); - } - - /** - * @brief Assign the result of a function object to each value in a - * sequence. - * @param first A forward iterator. - * @param n The length of the sequence. - * @param gen A function object taking no arguments. - * @return The end of the sequence, @p first+n - * - * Performs the assignment @c *i = @p gen() for each @c i in the range - * @p [first,first+n). - */ - template<typename _OutputIterator, typename _Size, typename _Generator> - _OutputIterator - generate_n(_OutputIterator __first, _Size __n, _Generator __gen) - { - // concept requirements - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - // "the type returned by a _Generator" - __typeof__(__gen())>) - - for (; __n > 0; --__n, ++__first) - *__first = __gen(); - return __first; - } /** * @brief Copy a sequence, removing elements of a given value. @@ -1565,11 +768,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename iterator_traits<_ForwardIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); - __first = std::find(__first, __last, __value); - _ForwardIterator __i = __first; - return __first == __last ? __first - : std::remove_copy(++__i, __last, - __first, __value); + __first = _GLIBCXX_STD_P::find(__first, __last, __value); + if(__first == __last) + return __first; + _ForwardIterator __result = __first; + ++__first; + for(; __first != __last; ++__first) + if(!(*__first == __value)) + { + *__result = _GLIBCXX_MOVE(*__first); + ++__result; + } + return __result; } /** @@ -1600,11 +810,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename iterator_traits<_ForwardIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); - __first = std::find_if(__first, __last, __pred); - _ForwardIterator __i = __first; - return __first == __last ? __first - : std::remove_copy_if(++__i, __last, - __first, __pred); + __first = _GLIBCXX_STD_P::find_if(__first, __last, __pred); + if(__first == __last) + return __first; + _ForwardIterator __result = __first; + ++__first; + for(; __first != __last; ++__first) + if(!__pred(*__first)) + { + *__result = _GLIBCXX_MOVE(*__first); + ++__result; + } + return __result; } /** @@ -1632,7 +849,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_requires_valid_range(__first, __last); // Skip the beginning, if already unique. - __first = std::adjacent_find(__first, __last); + __first = _GLIBCXX_STD_P::adjacent_find(__first, __last); if (__first == __last) return __last; @@ -1641,7 +858,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) ++__first; while (++__first != __last) if (!(*__dest == *__first)) - *++__dest = *__first; + *++__dest = _GLIBCXX_MOVE(*__first); return ++__dest; } @@ -1673,7 +890,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_requires_valid_range(__first, __last); // Skip the beginning, if already unique. - __first = std::adjacent_find(__first, __last, __binary_pred); + __first = _GLIBCXX_STD_P::adjacent_find(__first, __last, __binary_pred); if (__first == __last) return __last; @@ -1682,16 +899,14 @@ _GLIBCXX_BEGIN_NAMESPACE(std) ++__first; while (++__first != __last) if (!bool(__binary_pred(*__dest, *__first))) - *++__dest = *__first; + *++__dest = _GLIBCXX_MOVE(*__first); return ++__dest; } /** - * @if maint * This is an uglified unique_copy(_InputIterator, _InputIterator, * _OutputIterator) * overloaded for forward iterators and output iterator as result. - * @endif */ template<typename _ForwardIterator, typename _OutputIterator> _OutputIterator @@ -1712,11 +927,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified unique_copy(_InputIterator, _InputIterator, * _OutputIterator) * overloaded for input iterators and output iterator as result. - * @endif */ template<typename _InputIterator, typename _OutputIterator> _OutputIterator @@ -1737,11 +950,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified unique_copy(_InputIterator, _InputIterator, * _OutputIterator) * overloaded for input iterators and forward iterator as result. - * @endif */ template<typename _InputIterator, typename _ForwardIterator> _ForwardIterator @@ -1758,12 +969,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified * unique_copy(_InputIterator, _InputIterator, _OutputIterator, * _BinaryPredicate) * overloaded for forward iterators and output iterator as result. - * @endif */ template<typename _ForwardIterator, typename _OutputIterator, typename _BinaryPredicate> @@ -1789,12 +998,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified * unique_copy(_InputIterator, _InputIterator, _OutputIterator, * _BinaryPredicate) * overloaded for input iterators and output iterator as result. - * @endif */ template<typename _InputIterator, typename _OutputIterator, typename _BinaryPredicate> @@ -1820,12 +1027,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified * unique_copy(_InputIterator, _InputIterator, _OutputIterator, * _BinaryPredicate) * overloaded for input iterators and forward iterator as result. - * @endif */ template<typename _InputIterator, typename _ForwardIterator, typename _BinaryPredicate> @@ -1847,93 +1052,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @brief Copy a sequence, removing consecutive duplicate values. - * @param first An input iterator. - * @param last An input iterator. - * @param result An output iterator. - * @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. - * - * @if maint - * _GLIBCXX_RESOLVE_LIB_DEFECTS - * DR 241. Does unique_copy() require CopyConstructible and Assignable? - * - * _GLIBCXX_RESOLVE_LIB_DEFECTS - * DR 538. 241 again: Does unique_copy() require CopyConstructible and - * Assignable? - * @endif - */ - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - unique_copy(_InputIterator __first, _InputIterator __last, - _OutputIterator __result) - { - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return __result; - return std::__unique_copy(__first, __last, __result, - std::__iterator_category(__first), - std::__iterator_category(__result)); - } - - /** - * @brief Copy a sequence, removing consecutive values using a predicate. - * @param first An input iterator. - * @param last An input iterator. - * @param result An output iterator. - * @param binary_pred A binary predicate. - * @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 for which @p binary_pred returns - * true. - * unique_copy() is stable, so the relative order of elements that are - * copied is unchanged. - * - * @if maint - * _GLIBCXX_RESOLVE_LIB_DEFECTS - * DR 241. Does unique_copy() require CopyConstructible and Assignable? - * @endif - */ - template<typename _InputIterator, typename _OutputIterator, - typename _BinaryPredicate> - inline _OutputIterator - unique_copy(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, - _BinaryPredicate __binary_pred) - { - // concept requirements -- predicates checked later - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return __result; - return std::__unique_copy(__first, __last, __result, __binary_pred, - std::__iterator_category(__first), - std::__iterator_category(__result)); - } - - /** - * @if maint * This is an uglified reverse(_BidirectionalIterator, * _BidirectionalIterator) * overloaded for bidirectional iterators. - * @endif */ template<typename _BidirectionalIterator> void @@ -1951,11 +1072,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * This is an uglified reverse(_BidirectionalIterator, * _BidirectionalIterator) * overloaded for random access iterators. - * @endif */ template<typename _RandomAccessIterator> void @@ -2032,10 +1151,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @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 @@ -2050,11 +1167,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __m; } - /** - * @if maint - * This is a helper function for the rotate algorithm. - * @endif - */ + /// This is a helper function for the rotate algorithm. template<typename _ForwardIterator> void __rotate(_ForwardIterator __first, @@ -2068,7 +1181,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ForwardIterator __first2 = __middle; do { - swap(*__first, *__first2); + std::iter_swap(__first, __first2); ++__first; ++__first2; if (__first == __middle) @@ -2080,7 +1193,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (__first2 != __last) { - swap(*__first, *__first2); + std::iter_swap(__first, __first2); ++__first; ++__first2; if (__first == __middle) @@ -2090,11 +1203,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the rotate algorithm. - * @endif - */ + /// This is a helper function for the rotate algorithm. template<typename _BidirectionalIterator> void __rotate(_BidirectionalIterator __first, @@ -2114,7 +1223,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (__first != __middle && __middle != __last) { - swap(*__first, *--__last); + std::iter_swap(__first, --__last); ++__first; } @@ -2124,11 +1233,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::__reverse(__first, __middle, bidirectional_iterator_tag()); } - /** - * @if maint - * This is a helper function for the rotate algorithm. - * @endif - */ + /// This is a helper function for the rotate algorithm. template<typename _RandomAccessIterator> void __rotate(_RandomAccessIterator __first, @@ -2162,7 +1267,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) for (_Distance __i = 0; __i < __d; __i++) { - _ValueType __tmp = *__first; + _ValueType __tmp = _GLIBCXX_MOVE(*__first); _RandomAccessIterator __p = __first; if (__k < __l) @@ -2171,11 +1276,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { if (__p > __first + __l) { - *__p = *(__p - __l); + *__p = _GLIBCXX_MOVE(*(__p - __l)); __p -= __l; } - *__p = *(__p + __k); + *__p = _GLIBCXX_MOVE(*(__p + __k)); __p += __k; } } @@ -2185,15 +1290,15 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { if (__p < __last - __k) { - *__p = *(__p + __k); + *__p = _GLIBCXX_MOVE(*(__p + __k)); __p += __k; } - *__p = * (__p - __l); + *__p = _GLIBCXX_MOVE(*(__p - __l)); __p -= __l; } } - *__p = __tmp; + *__p = _GLIBCXX_MOVE(__tmp); ++__first; } } @@ -2265,70 +1370,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::copy(__middle, __last, __result)); } - /** - * @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 _RandomAccessIterator> - inline void - random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) - { - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first != __last) - for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) - std::iter_swap(__i, __first + (std::rand() % ((__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 _RandomAccessIterator, typename _RandomNumberGenerator> - void - random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, - _RandomNumberGenerator& __rand) - { - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return; - for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) - std::iter_swap(__i, __first + __rand((__i - __first) + 1)); - } - - - /** - * @if maint - * This is a helper function... - * @endif - */ + /// This is a helper function... template<typename _ForwardIterator, typename _Predicate> _ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, - _Predicate __pred, - forward_iterator_tag) + _Predicate __pred, forward_iterator_tag) { if (__first == __last) return __first; @@ -2342,23 +1388,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (++__next != __last) if (__pred(*__next)) { - swap(*__first, *__next); + std::iter_swap(__first, __next); ++__first; } return __first; } - /** - * @if maint - * This is a helper function... - * @endif - */ + /// This is a helper function... template<typename _BidirectionalIterator, typename _Predicate> _BidirectionalIterator __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, - _Predicate __pred, - bidirectional_iterator_tag) + _Predicate __pred, bidirectional_iterator_tag) { while (true) { @@ -2382,42 +1423,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @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 _ForwardIterator, typename _Predicate> - inline _ForwardIterator - partition(_ForwardIterator __first, _ForwardIterator __last, - _Predicate __pred) - { - // concept requirements - __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< - _ForwardIterator>) - __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - return std::__partition(__first, __last, __pred, - std::__iterator_category(__first)); - } - + // partition - /** - * @if maint - * This is a helper function... - * @endif - */ + /// This is a helper function... template<typename _ForwardIterator, typename _Predicate, typename _Distance> _ForwardIterator __inplace_stable_partition(_ForwardIterator __first, @@ -2441,11 +1449,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __begin; } - /** - * @if maint - * This is a helper function... - * @endif - */ + /// This is a helper function... template<typename _ForwardIterator, typename _Pointer, typename _Predicate, typename _Distance> _ForwardIterator @@ -2543,120 +1547,33 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the sort routines. - * @endif - */ + /// This is a helper function for the sort routines. template<typename _RandomAccessIterator> void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - std::make_heap(__first, __middle); for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) if (*__i < *__first) - std::__pop_heap(__first, __middle, __i, _ValueType(*__i)); + std::__pop_heap(__first, __middle, __i); } - /** - * @if maint - * This is a helper function for the sort routines. - * @endif - */ + /// This is a helper function for the sort routines. template<typename _RandomAccessIterator, typename _Compare> void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - std::make_heap(__first, __middle, __comp); for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) if (__comp(*__i, *__first)) - std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __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 _RandomAccessIterator> - inline void - partial_sort(_RandomAccessIterator __first, - _RandomAccessIterator __middle, - _RandomAccessIterator __last) - { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) - __glibcxx_requires_valid_range(__first, __middle); - __glibcxx_requires_valid_range(__middle, __last); - - std::__heap_select(__first, __middle, __last); - std::sort_heap(__first, __middle); + std::__pop_heap(__first, __middle, __i, __comp); } - /** - * @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 _RandomAccessIterator, typename _Compare> - inline void - partial_sort(_RandomAccessIterator __first, - _RandomAccessIterator __middle, - _RandomAccessIterator __last, - _Compare __comp) - { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - _ValueType, _ValueType>) - __glibcxx_requires_valid_range(__first, __middle); - __glibcxx_requires_valid_range(__middle, __last); - - std::__heap_select(__first, __middle, __last, __comp); - std::sort_heap(__first, __middle, __comp); - } + // partial_sort /** * @brief Copy the smallest elements of a sequence. @@ -2791,11 +1708,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __result_real_last; } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Tp> void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val) @@ -2811,11 +1724,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) *__last = __val; } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Tp, typename _Compare> void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, @@ -2832,11 +1741,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) *__last = __val; } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator> void __insertion_sort(_RandomAccessIterator __first, @@ -2859,11 +1764,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Compare> void __insertion_sort(_RandomAccessIterator __first, @@ -2885,11 +1786,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator> inline void __unguarded_insertion_sort(_RandomAccessIterator __first, @@ -2902,11 +1799,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::__unguarded_linear_insert(__i, _ValueType(*__i)); } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Compare> inline void __unguarded_insertion_sort(_RandomAccessIterator __first, @@ -2920,18 +1813,12 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } /** - * @if maint * @doctodo * This controls some aspect of the sort routines. - * @endif */ enum { _S_threshold = 16 }; - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator> void __final_insertion_sort(_RandomAccessIterator __first, @@ -2946,11 +1833,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::__insertion_sort(__first, __last); } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Compare> void __final_insertion_sort(_RandomAccessIterator __first, @@ -2966,11 +1849,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::__insertion_sort(__first, __last, __comp); } - /** - * @if maint - * This is a helper function... - * @endif - */ + /// This is a helper function... template<typename _RandomAccessIterator, typename _Tp> _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, @@ -2990,11 +1869,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function... - * @endif - */ + /// This is a helper function... template<typename _RandomAccessIterator, typename _Tp, typename _Compare> _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, @@ -3015,11 +1890,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Size> void __introsort_loop(_RandomAccessIterator __first, @@ -3033,7 +1904,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { if (__depth_limit == 0) { - std::partial_sort(__first, __last, __last); + _GLIBCXX_STD_P::partial_sort(__first, __last, __last); return; } --__depth_limit; @@ -3051,11 +1922,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the sort routine. - * @endif - */ + /// This is a helper function for the sort routine. template<typename _RandomAccessIterator, typename _Size, typename _Compare> void __introsort_loop(_RandomAccessIterator __first, @@ -3069,7 +1936,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { if (__depth_limit == 0) { - std::partial_sort(__first, __last, __last, __comp); + _GLIBCXX_STD_P::partial_sort(__first, __last, __last, __comp); return; } --__depth_limit; @@ -3088,91 +1955,30 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the sort routines. - * @endif - */ + /// 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 != 1; __n >>= 1) + for (__k = 0; __n != 0; __n >>= 1) ++__k; - return __k; + return __k - 1; } - /** - * @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 _RandomAccessIterator> - inline void - sort(_RandomAccessIterator __first, _RandomAccessIterator __last) - { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first != __last) - { - std::__introsort_loop(__first, __last, - std::__lg(__last - __first) * 2); - std::__final_insertion_sort(__first, __last); - } - } + inline int + __lg(int __n) + { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } - /** - * @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 _RandomAccessIterator, typename _Compare> - inline void - sort(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Compare __comp) - { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; + inline long + __lg(long __n) + { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, - _ValueType>) - __glibcxx_requires_valid_range(__first, __last); + inline long long + __lg(long long __n) + { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } - if (__first != __last) - { - std::__introsort_loop(__first, __last, - std::__lg(__last - __first) * 2, __comp); - std::__final_insertion_sort(__first, __last, __comp); - } - } + // sort template<typename _RandomAccessIterator, typename _Size> void @@ -3187,6 +1993,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (__depth_limit == 0) { std::__heap_select(__first, __nth + 1, __last); + // Place the nth largest element in its final position. std::iter_swap(__first, __nth); return; @@ -3246,81 +2053,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::__insertion_sort(__first, __last, __comp); } - /** - * @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 _RandomAccessIterator> - inline void - nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, - _RandomAccessIterator __last) - { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) - __glibcxx_requires_valid_range(__first, __nth); - __glibcxx_requires_valid_range(__nth, __last); - - if (__first == __last || __nth == __last) - return; - - std::__introselect(__first, __nth, __last, - std::__lg(__last - __first) * 2); - } - - /** - * @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 _RandomAccessIterator, typename _Compare> - inline void - nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, - _RandomAccessIterator __last, _Compare __comp) - { - typedef typename iterator_traits<_RandomAccessIterator>::value_type - _ValueType; - - // concept requirements - __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - _ValueType, _ValueType>) - __glibcxx_requires_valid_range(__first, __nth); - __glibcxx_requires_valid_range(__nth, __last); - - if (__first == __last || __nth == __last) - return; - - std::__introselect(__first, __nth, __last, - std::__lg(__last - __first) * 2, __comp); - } + // nth_element /** * @brief Finds the first position in which @a val could be inserted @@ -3328,8 +2061,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param first An iterator. * @param last Another iterator. * @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. + * @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> @@ -3345,7 +2079,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) - __glibcxx_requires_partitioned(__first, __last, __val); + __glibcxx_requires_partitioned_lower(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); _DistanceType __half; @@ -3396,7 +2130,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) - __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); + __glibcxx_requires_partitioned_lower_pred(__first, __last, + __val, __comp); _DistanceType __len = std::distance(__first, __last); _DistanceType __half; @@ -3442,7 +2177,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) - __glibcxx_requires_partitioned(__first, __last, __val); + __glibcxx_requires_partitioned_upper(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); _DistanceType __half; @@ -3493,7 +2228,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) - __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); + __glibcxx_requires_partitioned_upper_pred(__first, __last, + __val, __comp); _DistanceType __len = std::distance(__first, __last); _DistanceType __half; @@ -3546,7 +2282,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) - __glibcxx_requires_partitioned(__first, __last, __val); + __glibcxx_requires_partitioned_lower(__first, __last, __val); + __glibcxx_requires_partitioned_upper(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); _DistanceType __half; @@ -3610,7 +2347,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType, _Tp>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) - __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); + __glibcxx_requires_partitioned_lower_pred(__first, __last, + __val, __comp); + __glibcxx_requires_partitioned_upper_pred(__first, __last, + __val, __comp); _DistanceType __len = std::distance(__first, __last); _DistanceType __half; @@ -3645,7 +2385,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param first An iterator. * @param last Another iterator. * @param val The search term. - * @return True if @a val (or its equivelent) is in [@a first,@a last ]. + * @return True if @a val (or its equivalent) is in [@a first,@a last ]. * @ingroup binarysearch * * Note that this does not actually return an iterator to @a val. For @@ -3662,7 +2402,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) - __glibcxx_requires_partitioned(__first, __last, __val); + __glibcxx_requires_partitioned_lower(__first, __last, __val); + __glibcxx_requires_partitioned_upper(__first, __last, __val); _ForwardIterator __i = std::lower_bound(__first, __last, __val); return __i != __last && !(__val < *__i); @@ -3674,7 +2415,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param last Another iterator. * @param val The search term. * @param comp A functor to use for comparisons. - * @return True if @a val (or its equivelent) is in [@a first,@a last ]. + * @return True if @a val (or its equivalent) is in [@a first,@a last ]. * @ingroup binarysearch * * Note that this does not actually return an iterator to @a val. For @@ -3695,136 +2436,18 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) - __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); + __glibcxx_requires_partitioned_lower_pred(__first, __last, + __val, __comp); + __glibcxx_requires_partitioned_upper_pred(__first, __last, + __val, __comp); _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp); return __i != __last && !bool(__comp(__val, *__i)); } - /** - * @brief Merges two sorted ranges. - * @param first1 An iterator. - * @param first2 Another iterator. - * @param last1 Another iterator. - * @param last2 Another iterator. - * @param result An iterator pointing to the end of the merged range. - * @return An iterator pointing to the first element "not less than" @a val. - * - * Merges the ranges [first1,last1) and [first2,last2) into the sorted range - * [result, result + (last1-first1) + (last2-first2)). Both input ranges - * must be sorted, and the output range must not overlap with either of - * 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 - merge(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _OutputIterator __result) - { - typedef typename iterator_traits<_InputIterator1>::value_type - _ValueType1; - typedef typename iterator_traits<_InputIterator2>::value_type - _ValueType2; + // merge - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - _ValueType1>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - _ValueType2>) - __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); - - while (__first1 != __last1 && __first2 != __last2) - { - if (*__first2 < *__first1) - { - *__result = *__first2; - ++__first2; - } - else - { - *__result = *__first1; - ++__first1; - } - ++__result; - } - return std::copy(__first2, __last2, std::copy(__first1, __last1, - __result)); - } - - /** - * @brief Merges two sorted ranges. - * @param first1 An iterator. - * @param first2 Another iterator. - * @param last1 Another iterator. - * @param last2 Another iterator. - * @param result An iterator pointing to the end of the merged range. - * @param comp A functor to use for comparisons. - * @return An iterator pointing to the first element "not less than" @a val. - * - * Merges the ranges [first1,last1) and [first2,last2) into the sorted range - * [result, result + (last1-first1) + (last2-first2)). Both input ranges - * must be sorted, and the output range must not overlap with either of - * 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. - * - * The comparison function should have the same effects on ordering as - * the function used for the initial sort. - */ - template<typename _InputIterator1, typename _InputIterator2, - typename _OutputIterator, typename _Compare> - _OutputIterator - merge(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _OutputIterator __result, _Compare __comp) - { - typedef typename iterator_traits<_InputIterator1>::value_type - _ValueType1; - typedef typename iterator_traits<_InputIterator2>::value_type - _ValueType2; - - // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - _ValueType1>) - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - _ValueType2>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); - - while (__first1 != __last1 && __first2 != __last2) - { - if (__comp(*__first2, *__first1)) - { - *__result = *__first2; - ++__first2; - } - else - { - *__result = *__first1; - ++__first1; - } - ++__result; - } - return std::copy(__first2, __last2, std::copy(__first1, __last1, - __result)); - } - - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ + /// This is a helper function for the merge routines. template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _BidirectionalIterator3> _BidirectionalIterator3 @@ -3859,11 +2482,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ + /// This is a helper function for the merge routines. template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _BidirectionalIterator3, typename _Compare> _BidirectionalIterator3 @@ -3899,11 +2518,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ + /// This is a helper function for the merge routines. template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, typename _Distance> _BidirectionalIterator1 @@ -3935,11 +2550,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ + /// This is a helper function for the merge routines. template<typename _BidirectionalIterator, typename _Distance, typename _Pointer> void @@ -3952,7 +2563,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = std::copy(__first, __middle, __buffer); - std::merge(__buffer, __buffer_end, __middle, __last, __first); + _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last, + __first); } else if (__len2 <= __buffer_size) { @@ -3994,13 +2606,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ - template<typename _BidirectionalIterator, typename _Distance, typename _Pointer, - typename _Compare> + /// This is a helper function for the merge routines. + template<typename _BidirectionalIterator, typename _Distance, + typename _Pointer, typename _Compare> void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, @@ -4012,7 +2620,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = std::copy(__first, __middle, __buffer); - std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp); + _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last, + __first, __comp); } else if (__len2 <= __buffer_size) { @@ -4055,11 +2664,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ + /// This is a helper function for the merge routines. template<typename _BidirectionalIterator, typename _Distance> void __merge_without_buffer(_BidirectionalIterator __first, @@ -4102,11 +2707,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __len1 - __len11, __len2 - __len22); } - /** - * @if maint - * This is a helper function for the merge routines. - * @endif - */ + /// This is a helper function for the merge routines. template<typename _BidirectionalIterator, typename _Distance, typename _Compare> void @@ -4273,15 +2874,17 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (__last - __first >= __two_step) { - __result = std::merge(__first, __first + __step_size, - __first + __step_size, __first + __two_step, - __result); + __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size, + __first + __step_size, + __first + __two_step, + __result); __first += __two_step; } __step_size = std::min(_Distance(__last - __first), __step_size); - std::merge(__first, __first + __step_size, __first + __step_size, __last, - __result); + _GLIBCXX_STD_P::merge(__first, __first + __step_size, + __first + __step_size, __last, + __result); } template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, @@ -4296,7 +2899,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) while (__last - __first >= __two_step) { - __result = std::merge(__first, __first + __step_size, + __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size, __first + __step_size, __first + __two_step, __result, __comp); @@ -4304,10 +2907,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } __step_size = std::min(_Distance(__last - __first), __step_size); - std::merge(__first, __first + __step_size, - __first + __step_size, __last, - __result, - __comp); + _GLIBCXX_STD_P::merge(__first, __first + __step_size, + __first + __step_size, __last, __result, __comp); } template<typename _RandomAccessIterator, typename _Distance> @@ -4324,7 +2925,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::__insertion_sort(__first, __last); } - template<typename _RandomAccessIterator, typename _Distance, typename _Compare> + template<typename _RandomAccessIterator, typename _Distance, + typename _Compare> void __chunk_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, @@ -4446,11 +3048,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __comp); } - /** - * @if maint - * This is a helper function for the stable sorting routines. - * @endif - */ + /// This is a helper function for the stable sorting routines. template<typename _RandomAccessIterator> void __inplace_stable_sort(_RandomAccessIterator __first, @@ -4469,11 +3067,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __last - __middle); } - /** - * @if maint - * This is a helper function for the stable sorting routines. - * @endif - */ + /// This is a helper function for the stable sorting routines. template<typename _RandomAccessIterator, typename _Compare> void __inplace_stable_sort(_RandomAccessIterator __first, @@ -4493,89 +3087,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __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 _RandomAccessIterator> - inline void - stable_sort(_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); - - _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, - __last); - if (__buf.begin() == 0) - std::__inplace_stable_sort(__first, __last); - else - std::__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 _RandomAccessIterator, typename _Compare> - inline void - stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Compare __comp) - { - 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(_BinaryPredicateConcept<_Compare, - _ValueType, - _ValueType>) - __glibcxx_requires_valid_range(__first, __last); - - _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, - __last); - if (__buf.begin() == 0) - std::__inplace_stable_sort(__first, __last, __comp); - else - std::__stable_sort_adaptive(__first, __last, __buf.begin(), - _DistanceType(__buf.size()), __comp); - } + // stable_sort // Set algorithms: includes, set_union, set_intersection, set_difference, // set_symmetric_difference. All of these algorithms have the precondition @@ -4613,8 +3125,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first2 < *__first1) @@ -4650,7 +3162,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename _Compare> bool includes(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) + _InputIterator2 __first2, _InputIterator2 __last2, + _Compare __comp) { typedef typename iterator_traits<_InputIterator1>::value_type _ValueType1; @@ -4664,8 +3177,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) @@ -4678,6 +3191,1845 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __first2 == __last2; } + // nth_element + // merge + // set_difference + // set_intersection + // set_union + // stable_sort + // set_symmetric_difference + // min_element + // max_element + + /** + * @brief Permute range into the next "dictionary" ordering. + * @param first Start of range. + * @param last End of range. + * @return False if wrapped to first permutation, true otherwise. + * + * 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 + next_permutation(_BidirectionalIterator __first, + _BidirectionalIterator __last) + { + // concept requirements + __glibcxx_function_requires(_BidirectionalIteratorConcept< + _BidirectionalIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_BidirectionalIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return false; + _BidirectionalIterator __i = __first; + ++__i; + if (__i == __last) + return false; + __i = __last; + --__i; + + for(;;) + { + _BidirectionalIterator __ii = __i; + --__i; + if (*__i < *__ii) + { + _BidirectionalIterator __j = __last; + while (!(*__i < *--__j)) + {} + std::iter_swap(__i, __j); + std::reverse(__ii, __last); + return true; + } + if (__i == __first) + { + std::reverse(__first, __last); + return false; + } + } + } + + /** + * @brief Permute range into the next "dictionary" ordering using + * comparison functor. + * @param first Start of range. + * @param last End of range. + * @param comp A comparison functor. + * @return False if wrapped to first permutation, true otherwise. + * + * Treats all permutations of the range [first,last) as a set of + * "dictionary" sorted sequences ordered by @a comp. 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, typename _Compare> + bool + next_permutation(_BidirectionalIterator __first, + _BidirectionalIterator __last, _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_BidirectionalIteratorConcept< + _BidirectionalIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + typename iterator_traits<_BidirectionalIterator>::value_type, + typename iterator_traits<_BidirectionalIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return false; + _BidirectionalIterator __i = __first; + ++__i; + if (__i == __last) + return false; + __i = __last; + --__i; + + for(;;) + { + _BidirectionalIterator __ii = __i; + --__i; + if (__comp(*__i, *__ii)) + { + _BidirectionalIterator __j = __last; + while (!bool(__comp(*__i, *--__j))) + {} + std::iter_swap(__i, __j); + std::reverse(__ii, __last); + return true; + } + if (__i == __first) + { + std::reverse(__first, __last); + return false; + } + } + } + + /** + * @brief Permute range into the previous "dictionary" ordering. + * @param first Start of range. + * @param last End of range. + * @return False if wrapped to last permutation, true otherwise. + * + * Treats all permutations of the range as a set of "dictionary" sorted + * 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 + prev_permutation(_BidirectionalIterator __first, + _BidirectionalIterator __last) + { + // concept requirements + __glibcxx_function_requires(_BidirectionalIteratorConcept< + _BidirectionalIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_BidirectionalIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return false; + _BidirectionalIterator __i = __first; + ++__i; + if (__i == __last) + return false; + __i = __last; + --__i; + + for(;;) + { + _BidirectionalIterator __ii = __i; + --__i; + if (*__ii < *__i) + { + _BidirectionalIterator __j = __last; + while (!(*--__j < *__i)) + {} + std::iter_swap(__i, __j); + std::reverse(__ii, __last); + return true; + } + if (__i == __first) + { + std::reverse(__first, __last); + return false; + } + } + } + + /** + * @brief Permute range into the previous "dictionary" ordering using + * comparison functor. + * @param first Start of range. + * @param last End of range. + * @param comp A comparison functor. + * @return False if wrapped to last permutation, true otherwise. + * + * Treats all permutations of the range [first,last) as a set of + * "dictionary" sorted sequences ordered by @a comp. 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, typename _Compare> + bool + prev_permutation(_BidirectionalIterator __first, + _BidirectionalIterator __last, _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_BidirectionalIteratorConcept< + _BidirectionalIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + typename iterator_traits<_BidirectionalIterator>::value_type, + typename iterator_traits<_BidirectionalIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return false; + _BidirectionalIterator __i = __first; + ++__i; + if (__i == __last) + return false; + __i = __last; + --__i; + + for(;;) + { + _BidirectionalIterator __ii = __i; + --__i; + if (__comp(*__ii, *__i)) + { + _BidirectionalIterator __j = __last; + while (!bool(__comp(*--__j, *__i))) + {} + std::iter_swap(__i, __j); + std::reverse(__ii, __last); + return true; + } + if (__i == __first) + { + std::reverse(__first, __last); + return false; + } + } + } + + // replace + // replace_if + + /** + * @brief Copy a sequence, replacing each element of one value with another + * value. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @param old_value The value to be replaced. + * @param new_value The replacement value. + * @return The end of the output sequence, @p result+(last-first). + * + * Copies each element in the input range @p [first,last) to the + * output range @p [result,result+(last-first)) replacing elements + * equal to @p old_value with @p new_value. + */ + template<typename _InputIterator, typename _OutputIterator, typename _Tp> + _OutputIterator + replace_copy(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, + const _Tp& __old_value, const _Tp& __new_value) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator>::value_type, _Tp>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first, ++__result) + if (*__first == __old_value) + *__result = __new_value; + else + *__result = *__first; + return __result; + } + + /** + * @brief Copy a sequence, replacing each value for which a predicate + * returns true with another value. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @param pred A predicate. + * @param new_value The replacement value. + * @return The end of the output sequence, @p result+(last-first). + * + * Copies each element in the range @p [first,last) to the range + * @p [result,result+(last-first)) replacing elements for which + * @p pred returns true with @p new_value. + */ + template<typename _InputIterator, typename _OutputIterator, + typename _Predicate, typename _Tp> + _OutputIterator + replace_copy_if(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, + _Predicate __pred, const _Tp& __new_value) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first, ++__result) + if (__pred(*__first)) + *__result = __new_value; + else + *__result = *__first; + return __result; + } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Determines whether the elements of a sequence are sorted. + * @param first An iterator. + * @param last Another iterator. + * @return True if the elements are sorted, false otherwise. + */ + template<typename _ForwardIterator> + inline bool + is_sorted(_ForwardIterator __first, _ForwardIterator __last) + { return std::is_sorted_until(__first, __last) == __last; } + + /** + * @brief Determines whether the elements of a sequence are sorted + * according to a comparison functor. + * @param first An iterator. + * @param last Another iterator. + * @param comp A comparison functor. + * @return True if the elements are sorted, false otherwise. + */ + template<typename _ForwardIterator, typename _Compare> + inline bool + is_sorted(_ForwardIterator __first, _ForwardIterator __last, + _Compare __comp) + { return std::is_sorted_until(__first, __last, __comp) == __last; } + + /** + * @brief Determines the end of a sorted sequence. + * @param first An iterator. + * @param last Another iterator. + * @return An iterator pointing to the last iterator i in [first, last) + * for which the range [first, i) is sorted. + */ + template<typename _ForwardIterator> + _ForwardIterator + is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __last; + + _ForwardIterator __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) + if (*__next < *__first) + return __next; + return __next; + } + + /** + * @brief Determines the end of a sorted sequence using comparison functor. + * @param first An iterator. + * @param last Another iterator. + * @param comp A comparison functor. + * @return An iterator pointing to the last iterator i in [first, last) + * for which the range [first, i) is sorted. + */ + template<typename _ForwardIterator, typename _Compare> + _ForwardIterator + is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, + _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __last; + + _ForwardIterator __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) + if (__comp(*__next, *__first)) + return __next; + return __next; + } + + /** + * @brief Determines min and max at once as an ordered pair. + * @param a A thing of arbitrary type. + * @param b Another thing of arbitrary type. + * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise. + */ + template<typename _Tp> + inline pair<const _Tp&, const _Tp&> + minmax(const _Tp& __a, const _Tp& __b) + { + // concept requirements + __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + + return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) + : pair<const _Tp&, const _Tp&>(__a, __b); + } + + /** + * @brief Determines min and max at once as an ordered pair. + * @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 A pair(b, a) if b is smaller than a, pair(a, b) otherwise. + */ + template<typename _Tp, typename _Compare> + inline pair<const _Tp&, const _Tp&> + minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) + { + return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) + : pair<const _Tp&, const _Tp&>(__a, __b); + } + + /** + * @brief Return a pair of iterators pointing to the minimum and maximum + * elements in a range. + * @param first Start of range. + * @param last End of range. + * @return make_pair(m, M), where m is the first iterator i in + * [first, last) such that no other element in the range is + * smaller, and where M is the last iterator i in [first, last) + * such that no other element in the range is larger. + */ + template<typename _ForwardIterator> + pair<_ForwardIterator, _ForwardIterator> + minmax_element(_ForwardIterator __first, _ForwardIterator __last) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + _ForwardIterator __next = __first; + if (__first == __last + || ++__next == __last) + return std::make_pair(__first, __first); + + _ForwardIterator __min, __max; + if (*__next < *__first) + { + __min = __next; + __max = __first; + } + else + { + __min = __first; + __max = __next; + } + + __first = __next; + ++__first; + + while (__first != __last) + { + __next = __first; + if (++__next == __last) + { + if (*__first < *__min) + __min = __first; + else if (!(*__first < *__max)) + __max = __first; + break; + } + + if (*__next < *__first) + { + if (*__next < *__min) + __min = __next; + if (!(*__first < *__max)) + __max = __first; + } + else + { + if (*__first < *__min) + __min = __first; + if (!(*__next < *__max)) + __max = __next; + } + + __first = __next; + ++__first; + } + + return std::make_pair(__min, __max); + } + + /** + * @brief Return a pair of iterators pointing to the minimum and maximum + * elements in a range. + * @param first Start of range. + * @param last End of range. + * @param comp Comparison functor. + * @return make_pair(m, M), where m is the first iterator i in + * [first, last) such that no other element in the range is + * smaller, and where M is the last iterator i in [first, last) + * such that no other element in the range is larger. + */ + template<typename _ForwardIterator, typename _Compare> + pair<_ForwardIterator, _ForwardIterator> + minmax_element(_ForwardIterator __first, _ForwardIterator __last, + _Compare __comp) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + _ForwardIterator __next = __first; + if (__first == __last + || ++__next == __last) + return std::make_pair(__first, __first); + + _ForwardIterator __min, __max; + if (__comp(*__next, *__first)) + { + __min = __next; + __max = __first; + } + else + { + __min = __first; + __max = __next; + } + + __first = __next; + ++__first; + + while (__first != __last) + { + __next = __first; + if (++__next == __last) + { + if (__comp(*__first, *__min)) + __min = __first; + else if (!__comp(*__first, *__max)) + __max = __first; + break; + } + + if (__comp(*__next, *__first)) + { + if (__comp(*__next, *__min)) + __min = __next; + if (!__comp(*__first, *__max)) + __max = __first; + } + else + { + if (__comp(*__first, *__min)) + __min = __first; + if (!__comp(*__next, *__max)) + __max = __next; + } + + __first = __next; + ++__first; + } + + return std::make_pair(__min, __max); + } +#endif // __GXX_EXPERIMENTAL_CXX0X__ + +_GLIBCXX_END_NAMESPACE + +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) + + /** + * @brief Apply a function to every element of a sequence. + * @param first An input iterator. + * @param last An input iterator. + * @param f A unary function object. + * @return @p f. + * + * 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. + * If @p f has a return value it is ignored. + */ + template<typename _InputIterator, typename _Function> + _Function + for_each(_InputIterator __first, _InputIterator __last, _Function __f) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_requires_valid_range(__first, __last); + for (; __first != __last; ++__first) + __f(*__first); + return __f; + } + + /** + * @brief Find the first occurrence of a value in a sequence. + * @param first An input iterator. + * @param last An input iterator. + * @param val The value to find. + * @return The first iterator @c i in the range @p [first,last) + * such that @c *i == @p val, or @p last if no such iterator exists. + */ + template<typename _InputIterator, typename _Tp> + inline _InputIterator + find(_InputIterator __first, _InputIterator __last, + const _Tp& __val) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator>::value_type, _Tp>) + __glibcxx_requires_valid_range(__first, __last); + return std::__find(__first, __last, __val, + std::__iterator_category(__first)); + } + + /** + * @brief Find the first element in a sequence for which a + * predicate is true. + * @param first An input iterator. + * @param last An input iterator. + * @param pred A predicate. + * @return The first iterator @c i in the range @p [first,last) + * such that @p pred(*i) is true, or @p last if no such iterator exists. + */ + template<typename _InputIterator, typename _Predicate> + inline _InputIterator + find_if(_InputIterator __first, _InputIterator __last, + _Predicate __pred) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + return std::__find_if(__first, __last, __pred, + std::__iterator_category(__first)); + } + + /** + * @brief Find element from a set in a sequence. + * @param first1 Start of range to search. + * @param last1 End of range to search. + * @param first2 Start of match candidates. + * @param last2 End of match candidates. + * @return The first iterator @c i in the range + * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an + * iterator in [first2,last2), or @p last1 if no such iterator exists. + * + * 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 + find_first_of(_InputIterator __first1, _InputIterator __last1, + _ForwardIterator __first2, _ForwardIterator __last2) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + for (; __first1 != __last1; ++__first1) + for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) + if (*__first1 == *__iter) + return __first1; + return __last1; + } + + /** + * @brief Find element from a set in a sequence using a predicate. + * @param first1 Start of range to search. + * @param last1 End of range to search. + * @param first2 Start of match candidates. + * @param last2 End of match candidates. + * @param comp Predicate to use. + * @return The first iterator @c i in the range + * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an + * iterator in [first2,last2), or @p last1 if no such iterator exists. + * + + * 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, + typename _BinaryPredicate> + _InputIterator + find_first_of(_InputIterator __first1, _InputIterator __last1, + _ForwardIterator __first2, _ForwardIterator __last2, + _BinaryPredicate __comp) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_InputIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + for (; __first1 != __last1; ++__first1) + for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) + if (__comp(*__first1, *__iter)) + return __first1; + return __last1; + } + + /** + * @brief Find two adjacent values in a sequence that are equal. + * @param first A forward iterator. + * @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 + adjacent_find(_ForwardIterator __first, _ForwardIterator __last) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_EqualityComparableConcept< + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + if (__first == __last) + return __last; + _ForwardIterator __next = __first; + while(++__next != __last) + { + if (*__first == *__next) + return __first; + __first = __next; + } + return __last; + } + + /** + * @brief Find two adjacent values in a sequence using a predicate. + * @param first A forward iterator. + * @param last A forward iterator. + * @param binary_pred A binary predicate. + * @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 + * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator + * exists. + */ + template<typename _ForwardIterator, typename _BinaryPredicate> + _ForwardIterator + adjacent_find(_ForwardIterator __first, _ForwardIterator __last, + _BinaryPredicate __binary_pred) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + if (__first == __last) + return __last; + _ForwardIterator __next = __first; + while(++__next != __last) + { + if (__binary_pred(*__first, *__next)) + return __first; + __first = __next; + } + return __last; + } + + /** + * @brief Count the number of copies of a value in a sequence. + * @param first An input iterator. + * @param last An input iterator. + * @param value The value to be counted. + * @return The number of iterators @c i in the range @p [first,last) + * for which @c *i == @p value + */ + template<typename _InputIterator, typename _Tp> + typename iterator_traits<_InputIterator>::difference_type + count(_InputIterator __first, _InputIterator __last, const _Tp& __value) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator>::value_type, _Tp>) + __glibcxx_requires_valid_range(__first, __last); + typename iterator_traits<_InputIterator>::difference_type __n = 0; + for (; __first != __last; ++__first) + if (*__first == __value) + ++__n; + return __n; + } + + /** + * @brief Count the elements of a sequence for which a predicate is true. + * @param first An input iterator. + * @param last An input iterator. + * @param pred A predicate. + * @return The number of iterators @c i in the range @p [first,last) + * for which @p pred(*i) is true. + */ + template<typename _InputIterator, typename _Predicate> + typename iterator_traits<_InputIterator>::difference_type + count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + typename iterator_traits<_InputIterator>::difference_type __n = 0; + for (; __first != __last; ++__first) + if (__pred(*__first)) + ++__n; + return __n; + } + + /** + * @brief Search a sequence for a matching sub-sequence. + * @param first1 A forward iterator. + * @param last1 A forward iterator. + * @param first2 A forward iterator. + * @param last2 A forward iterator. + * @return The first iterator @c i in the range + * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) + * for each @c N in the range @p [0,last2-first2), or @p last1 if no + * such iterator exists. + * + * Searches the range @p [first1,last1) for a sub-sequence that compares + * equal value-by-value with the sequence given by @p [first2,last2) and + * returns an iterator to the first element of the sub-sequence, or + * @p last1 if the sub-sequence is not found. + * + * Because the sub-sequence must lie completely within the range + * @p [first1,last1) it must start at a position less than + * @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 + search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_ForwardIterator1>::value_type, + typename iterator_traits<_ForwardIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + // Test for empty ranges + if (__first1 == __last1 || __first2 == __last2) + return __first1; + + // Test for a pattern of length 1. + _ForwardIterator2 __p1(__first2); + if (++__p1 == __last2) + return _GLIBCXX_STD_P::find(__first1, __last1, *__first2); + + // General case. + _ForwardIterator2 __p; + _ForwardIterator1 __current = __first1; + + for (;;) + { + __first1 = _GLIBCXX_STD_P::find(__first1, __last1, *__first2); + if (__first1 == __last1) + return __last1; + + __p = __p1; + __current = __first1; + if (++__current == __last1) + return __last1; + + while (*__current == *__p) + { + if (++__p == __last2) + return __first1; + if (++__current == __last1) + return __last1; + } + ++__first1; + } + return __first1; + } + + /** + * @brief Search a sequence for a matching sub-sequence using a predicate. + * @param first1 A forward iterator. + * @param last1 A forward iterator. + * @param first2 A forward iterator. + * @param last2 A forward iterator. + * @param predicate A binary predicate. + * @return The first iterator @c i in the range + * @p [first1,last1-(last2-first2)) such that + * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range + * @p [0,last2-first2), or @p last1 if no such iterator exists. + * + * Searches the range @p [first1,last1) for a sub-sequence that compares + * equal value-by-value with the sequence given by @p [first2,last2), + * using @p predicate to determine equality, and returns an iterator + * to the first element of the sub-sequence, or @p last1 if no such + * iterator exists. + * + * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) + */ + template<typename _ForwardIterator1, typename _ForwardIterator2, + typename _BinaryPredicate> + _ForwardIterator1 + search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __predicate) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) + __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIterator1>::value_type, + typename iterator_traits<_ForwardIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); + + // Test for empty ranges + if (__first1 == __last1 || __first2 == __last2) + return __first1; + + // Test for a pattern of length 1. + _ForwardIterator2 __p1(__first2); + if (++__p1 == __last2) + { + while (__first1 != __last1 + && !bool(__predicate(*__first1, *__first2))) + ++__first1; + return __first1; + } + + // General case. + _ForwardIterator2 __p; + _ForwardIterator1 __current = __first1; + + for (;;) + { + while (__first1 != __last1 + && !bool(__predicate(*__first1, *__first2))) + ++__first1; + if (__first1 == __last1) + return __last1; + + __p = __p1; + __current = __first1; + if (++__current == __last1) + return __last1; + + while (__predicate(*__current, *__p)) + { + if (++__p == __last2) + return __first1; + if (++__current == __last1) + return __last1; + } + ++__first1; + } + return __first1; + } + + + /** + * @brief Search a sequence for a number of consecutive values. + * @param first A forward iterator. + * @param last A forward iterator. + * @param count The number of consecutive values. + * @param val The value to find. + * @return The first iterator @c i in the range @p [first,last-count) + * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), + * 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 + search_n(_ForwardIterator __first, _ForwardIterator __last, + _Integer __count, const _Tp& __val) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_ForwardIterator>::value_type, _Tp>) + __glibcxx_requires_valid_range(__first, __last); + + if (__count <= 0) + return __first; + if (__count == 1) + return _GLIBCXX_STD_P::find(__first, __last, __val); + return std::__search_n(__first, __last, __count, __val, + std::__iterator_category(__first)); + } + + + /** + * @brief Search a sequence for a number of consecutive values using a + * predicate. + * @param first A forward iterator. + * @param last A forward iterator. + * @param count The number of consecutive values. + * @param val The value to find. + * @param binary_pred A binary predicate. + * @return The first iterator @c i in the range @p [first,last-count) + * such that @p binary_pred(*(i+N),val) is true for each @c N in the + * range @p [0,count), or @p last if no such iterator exists. + * + * Searches the range @p [first,last) for @p count consecutive elements + * for which the predicate returns true. + */ + template<typename _ForwardIterator, typename _Integer, typename _Tp, + typename _BinaryPredicate> + _ForwardIterator + search_n(_ForwardIterator __first, _ForwardIterator __last, + _Integer __count, const _Tp& __val, + _BinaryPredicate __binary_pred) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIterator>::value_type, _Tp>) + __glibcxx_requires_valid_range(__first, __last); + + if (__count <= 0) + return __first; + if (__count == 1) + { + while (__first != __last && !bool(__binary_pred(*__first, __val))) + ++__first; + return __first; + } + return std::__search_n(__first, __last, __count, __val, __binary_pred, + std::__iterator_category(__first)); + } + + + /** + * @brief Perform an operation on a sequence. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @param unary_op A unary operator. + * @return An output iterator equal to @p result+(last-first). + * + * Applies the operator to each element in the input range and assigns + * the results to successive elements of the output sequence. + * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the + * range @p [0,last-first). + * + * @p unary_op must not alter its argument. + */ + template<typename _InputIterator, typename _OutputIterator, + typename _UnaryOperation> + _OutputIterator + transform(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _UnaryOperation __unary_op) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + // "the type returned by a _UnaryOperation" + __typeof__(__unary_op(*__first))>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first, ++__result) + *__result = __unary_op(*__first); + return __result; + } + + /** + * @brief Perform an operation on corresponding elements of two sequences. + * @param first1 An input iterator. + * @param last1 An input iterator. + * @param first2 An input iterator. + * @param result An output iterator. + * @param binary_op A binary operator. + * @return An output iterator equal to @p result+(last-first). + * + * Applies the operator to the corresponding elements in the two + * input ranges and assigns the results to successive elements of the + * output sequence. + * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each + * @c N in the range @p [0,last1-first1). + * + * @p binary_op must not alter either of its arguments. + */ + template<typename _InputIterator1, typename _InputIterator2, + typename _OutputIterator, typename _BinaryOperation> + _OutputIterator + transform(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _OutputIterator __result, + _BinaryOperation __binary_op) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + // "the type returned by a _BinaryOperation" + __typeof__(__binary_op(*__first1,*__first2))>) + __glibcxx_requires_valid_range(__first1, __last1); + + for (; __first1 != __last1; ++__first1, ++__first2, ++__result) + *__result = __binary_op(*__first1, *__first2); + return __result; + } + + /** + * @brief Replace each occurrence of one value in a sequence with another + * value. + * @param first A forward iterator. + * @param last A forward iterator. + * @param old_value The value to be replaced. + * @param new_value The replacement value. + * @return replace() returns no value. + * + * For each iterator @c i in the range @p [first,last) if @c *i == + * @p old_value then the assignment @c *i = @p new_value is performed. + */ + template<typename _ForwardIterator, typename _Tp> + void + replace(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __old_value, const _Tp& __new_value) + { + // concept requirements + __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< + _ForwardIterator>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_ForwardIterator>::value_type, _Tp>) + __glibcxx_function_requires(_ConvertibleConcept<_Tp, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first) + if (*__first == __old_value) + *__first = __new_value; + } + + /** + * @brief Replace each value in a sequence for which a predicate returns + * true with another value. + * @param first A forward iterator. + * @param last A forward iterator. + * @param pred A predicate. + * @param new_value The replacement value. + * @return replace_if() returns no value. + * + * For each iterator @c i in the range @p [first,last) if @p pred(*i) + * is true then the assignment @c *i = @p new_value is performed. + */ + template<typename _ForwardIterator, typename _Predicate, typename _Tp> + void + replace_if(_ForwardIterator __first, _ForwardIterator __last, + _Predicate __pred, const _Tp& __new_value) + { + // concept requirements + __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< + _ForwardIterator>) + __glibcxx_function_requires(_ConvertibleConcept<_Tp, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first) + if (__pred(*__first)) + *__first = __new_value; + } + + /** + * @brief Assign the result of a function object to each value in a + * sequence. + * @param first A forward iterator. + * @param last A forward iterator. + * @param gen A function object taking no arguments and returning + * std::iterator_traits<_ForwardIterator>::value_type + * @return generate() returns no value. + * + * Performs the assignment @c *i = @p gen() for each @c i in the range + * @p [first,last). + */ + template<typename _ForwardIterator, typename _Generator> + void + generate(_ForwardIterator __first, _ForwardIterator __last, + _Generator __gen) + { + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_GeneratorConcept<_Generator, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first) + *__first = __gen(); + } + + /** + * @brief Assign the result of a function object to each value in a + * sequence. + * @param first A forward iterator. + * @param n The length of the sequence. + * @param gen A function object taking no arguments and returning + * std::iterator_traits<_ForwardIterator>::value_type + * @return The end of the sequence, @p first+n + * + * Performs the assignment @c *i = @p gen() for each @c i in the range + * @p [first,first+n). + */ + template<typename _OutputIterator, typename _Size, typename _Generator> + _OutputIterator + generate_n(_OutputIterator __first, _Size __n, _Generator __gen) + { + // concept requirements + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + // "the type returned by a _Generator" + __typeof__(__gen())>) + + for (; __n > 0; --__n, ++__first) + *__first = __gen(); + return __first; + } + + + /** + * @brief Copy a sequence, removing consecutive duplicate values. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @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. + * + * _GLIBCXX_RESOLVE_LIB_DEFECTS + * DR 241. Does unique_copy() require CopyConstructible and Assignable? + * + * _GLIBCXX_RESOLVE_LIB_DEFECTS + * DR 538. 241 again: Does unique_copy() require CopyConstructible and + * Assignable? + */ + template<typename _InputIterator, typename _OutputIterator> + inline _OutputIterator + unique_copy(_InputIterator __first, _InputIterator __last, + _OutputIterator __result) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_function_requires(_EqualityComparableConcept< + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __result; + return std::__unique_copy(__first, __last, __result, + std::__iterator_category(__first), + std::__iterator_category(__result)); + } + + /** + * @brief Copy a sequence, removing consecutive values using a predicate. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @param binary_pred A binary predicate. + * @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 for which @p binary_pred returns + * true. + * unique_copy() is stable, so the relative order of elements that are + * copied is unchanged. + * + * _GLIBCXX_RESOLVE_LIB_DEFECTS + * DR 241. Does unique_copy() require CopyConstructible and Assignable? + */ + template<typename _InputIterator, typename _OutputIterator, + typename _BinaryPredicate> + inline _OutputIterator + unique_copy(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, + _BinaryPredicate __binary_pred) + { + // concept requirements -- predicates checked later + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __result; + return std::__unique_copy(__first, __last, __result, __binary_pred, + std::__iterator_category(__first), + std::__iterator_category(__result)); + } + + + /** + * @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 _RandomAccessIterator> + inline void + random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) + { + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first != __last) + for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) + std::iter_swap(__i, __first + (std::rand() % ((__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 _RandomAccessIterator, typename _RandomNumberGenerator> + void + random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, + _RandomNumberGenerator& __rand) + { + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return; + for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) + std::iter_swap(__i, __first + __rand((__i - __first) + 1)); + } + + + /** + * @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 _ForwardIterator, typename _Predicate> + inline _ForwardIterator + partition(_ForwardIterator __first, _ForwardIterator __last, + _Predicate __pred) + { + // concept requirements + __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< + _ForwardIterator>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + return std::__partition(__first, __last, __pred, + std::__iterator_category(__first)); + } + + + + /** + * @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 _RandomAccessIterator> + inline void + partial_sort(_RandomAccessIterator __first, + _RandomAccessIterator __middle, + _RandomAccessIterator __last) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) + __glibcxx_requires_valid_range(__first, __middle); + __glibcxx_requires_valid_range(__middle, __last); + + std::__heap_select(__first, __middle, __last); + std::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 _RandomAccessIterator, typename _Compare> + inline void + partial_sort(_RandomAccessIterator __first, + _RandomAccessIterator __middle, + _RandomAccessIterator __last, + _Compare __comp) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType, _ValueType>) + __glibcxx_requires_valid_range(__first, __middle); + __glibcxx_requires_valid_range(__middle, __last); + + std::__heap_select(__first, __middle, __last, __comp); + std::sort_heap(__first, __middle, __comp); + } + + /** + * @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 _RandomAccessIterator> + inline void + nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, + _RandomAccessIterator __last) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) + __glibcxx_requires_valid_range(__first, __nth); + __glibcxx_requires_valid_range(__nth, __last); + + if (__first == __last || __nth == __last) + return; + + std::__introselect(__first, __nth, __last, + std::__lg(__last - __first) * 2); + } + + /** + * @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 _RandomAccessIterator, typename _Compare> + inline void + nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, + _RandomAccessIterator __last, _Compare __comp) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType, _ValueType>) + __glibcxx_requires_valid_range(__first, __nth); + __glibcxx_requires_valid_range(__nth, __last); + + if (__first == __last || __nth == __last) + return; + + std::__introselect(__first, __nth, __last, + std::__lg(__last - __first) * 2, __comp); + } + + + /** + * @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 _RandomAccessIterator> + inline void + sort(_RandomAccessIterator __first, _RandomAccessIterator __last) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first != __last) + { + std::__introsort_loop(__first, __last, + std::__lg(__last - __first) * 2); + std::__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 _RandomAccessIterator, typename _Compare> + inline void + sort(_RandomAccessIterator __first, _RandomAccessIterator __last, + _Compare __comp) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, + _ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first != __last) + { + std::__introsort_loop(__first, __last, + std::__lg(__last - __first) * 2, __comp); + std::__final_insertion_sort(__first, __last, __comp); + } + } + + /** + * @brief Merges two sorted ranges. + * @param first1 An iterator. + * @param first2 Another iterator. + * @param last1 Another iterator. + * @param last2 Another iterator. + * @param result An iterator pointing to the end of the merged range. + * @return An iterator pointing to the first element "not less + * than" @a val. + * + * Merges the ranges [first1,last1) and [first2,last2) into the sorted range + * [result, result + (last1-first1) + (last2-first2)). Both input ranges + * must be sorted, and the output range must not overlap with either of + * 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 + merge(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result) + { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); + + while (__first1 != __last1 && __first2 != __last2) + { + if (*__first2 < *__first1) + { + *__result = *__first2; + ++__first2; + } + else + { + *__result = *__first1; + ++__first1; + } + ++__result; + } + return std::copy(__first2, __last2, std::copy(__first1, __last1, + __result)); + } + + /** + * @brief Merges two sorted ranges. + * @param first1 An iterator. + * @param first2 Another iterator. + * @param last1 Another iterator. + * @param last2 Another iterator. + * @param result An iterator pointing to the end of the merged range. + * @param comp A functor to use for comparisons. + * @return An iterator pointing to the first element "not less + * than" @a val. + * + * Merges the ranges [first1,last1) and [first2,last2) into the sorted range + * [result, result + (last1-first1) + (last2-first2)). Both input ranges + * must be sorted, and the output range must not overlap with either of + * 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. + * + * The comparison function should have the same effects on ordering as + * the function used for the initial sort. + */ + template<typename _InputIterator1, typename _InputIterator2, + typename _OutputIterator, typename _Compare> + _OutputIterator + merge(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result, _Compare __comp) + { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType2, _ValueType1>) + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); + + while (__first1 != __last1 && __first2 != __last2) + { + if (__comp(*__first2, *__first1)) + { + *__result = *__first2; + ++__first2; + } + else + { + *__result = *__first1; + ++__first1; + } + ++__result; + } + return std::copy(__first2, __last2, std::copy(__first1, __last1, + __result)); + } + + + /** + * @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 _RandomAccessIterator> + inline void + stable_sort(_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); + + _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, + __last); + if (__buf.begin() == 0) + std::__inplace_stable_sort(__first, __last); + else + std::__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 _RandomAccessIterator, typename _Compare> + inline void + stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, + _Compare __comp) + { + 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(_BinaryPredicateConcept<_Compare, + _ValueType, + _ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, + __last); + if (__buf.begin() == 0) + std::__inplace_stable_sort(__first, __last, __comp); + else + std::__stable_sort_adaptive(__first, __last, __buf.begin(), + _DistanceType(__buf.size()), __comp); + } + + /** * @brief Return the union of two sorted ranges. * @param first1 Start of first range. @@ -4716,8 +5068,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) { @@ -4784,8 +5136,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) { @@ -4846,8 +5198,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) @@ -4904,8 +5256,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) @@ -4959,8 +5311,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) @@ -5021,8 +5373,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) @@ -5078,8 +5430,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) - __glibcxx_requires_sorted(__first1, __last1); - __glibcxx_requires_sorted(__first2, __last2); + __glibcxx_requires_sorted_set(__first1, __last1, __first2); + __glibcxx_requires_sorted_set(__first2, __last2, __first1); while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) @@ -5146,8 +5498,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType2, _ValueType1>) - __glibcxx_requires_sorted_pred(__first1, __last1, __comp); - __glibcxx_requires_sorted_pred(__first2, __last2, __comp); + __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); + __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) @@ -5167,12 +5519,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) ++__first1; ++__first2; } - return std::copy(__first2, __last2, std::copy(__first1, - __last1, __result)); + return std::copy(__first2, __last2, + std::copy(__first1, __last1, __result)); } - // min_element and max_element, with and without an explicitly supplied - // comparison function. /** * @brief Return the minimum element in a range. @@ -5281,230 +5631,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __result; } - // next_permutation and prev_permutation, with and without an explicitly - // supplied comparison function. - - /** - * @brief Permute range into the next "dictionary" ordering. - * @param first Start of range. - * @param last End of range. - * @return False if wrapped to first permutation, true otherwise. - * - * 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 - next_permutation(_BidirectionalIterator __first, - _BidirectionalIterator __last) - { - // concept requirements - __glibcxx_function_requires(_BidirectionalIteratorConcept< - _BidirectionalIterator>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_BidirectionalIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return false; - _BidirectionalIterator __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) - { - _BidirectionalIterator __ii = __i; - --__i; - if (*__i < *__ii) - { - _BidirectionalIterator __j = __last; - while (!(*__i < *--__j)) - {} - std::iter_swap(__i, __j); - std::reverse(__ii, __last); - return true; - } - if (__i == __first) - { - std::reverse(__first, __last); - return false; - } - } - } - - /** - * @brief Permute range into the next "dictionary" ordering using - * comparison functor. - * @param first Start of range. - * @param last End of range. - * @param comp - * @return False if wrapped to first permutation, true otherwise. - * - * Treats all permutations of the range [first,last) as a set of - * "dictionary" sorted sequences ordered by @a comp. 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, typename _Compare> - bool - next_permutation(_BidirectionalIterator __first, - _BidirectionalIterator __last, _Compare __comp) - { - // concept requirements - __glibcxx_function_requires(_BidirectionalIteratorConcept< - _BidirectionalIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_BidirectionalIterator>::value_type, - typename iterator_traits<_BidirectionalIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return false; - _BidirectionalIterator __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) - { - _BidirectionalIterator __ii = __i; - --__i; - if (__comp(*__i, *__ii)) - { - _BidirectionalIterator __j = __last; - while (!bool(__comp(*__i, *--__j))) - {} - std::iter_swap(__i, __j); - std::reverse(__ii, __last); - return true; - } - if (__i == __first) - { - std::reverse(__first, __last); - return false; - } - } - } - - /** - * @brief Permute range into the previous "dictionary" ordering. - * @param first Start of range. - * @param last End of range. - * @return False if wrapped to last permutation, true otherwise. - * - * Treats all permutations of the range as a set of "dictionary" sorted - * 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 - prev_permutation(_BidirectionalIterator __first, - _BidirectionalIterator __last) - { - // concept requirements - __glibcxx_function_requires(_BidirectionalIteratorConcept< - _BidirectionalIterator>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_BidirectionalIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return false; - _BidirectionalIterator __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) - { - _BidirectionalIterator __ii = __i; - --__i; - if (*__ii < *__i) - { - _BidirectionalIterator __j = __last; - while (!(*--__j < *__i)) - {} - std::iter_swap(__i, __j); - std::reverse(__ii, __last); - return true; - } - if (__i == __first) - { - std::reverse(__first, __last); - return false; - } - } - } - - /** - * @brief Permute range into the previous "dictionary" ordering using - * comparison functor. - * @param first Start of range. - * @param last End of range. - * @param comp - * @return False if wrapped to last permutation, true otherwise. - * - * Treats all permutations of the range [first,last) as a set of - * "dictionary" sorted sequences ordered by @a comp. 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, typename _Compare> - bool - prev_permutation(_BidirectionalIterator __first, - _BidirectionalIterator __last, _Compare __comp) - { - // concept requirements - __glibcxx_function_requires(_BidirectionalIteratorConcept< - _BidirectionalIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_BidirectionalIterator>::value_type, - typename iterator_traits<_BidirectionalIterator>::value_type>) - __glibcxx_requires_valid_range(__first, __last); - - if (__first == __last) - return false; - _BidirectionalIterator __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) - { - _BidirectionalIterator __ii = __i; - --__i; - if (__comp(*__ii, *__i)) - { - _BidirectionalIterator __j = __last; - while (!bool(__comp(*--__j, *__i))) - {} - std::iter_swap(__i, __j); - std::reverse(__ii, __last); - return true; - } - if (__i == __first) - { - std::reverse(__first, __last); - return false; - } - } - } - -_GLIBCXX_END_NAMESPACE +_GLIBCXX_END_NESTED_NAMESPACE #endif /* _STL_ALGO_H */ |