| // Core algorithmic facilities -*- C++ -*- |
| |
| // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, |
| // 2011 Free Software Foundation, Inc. |
| // |
| // This file is part of the GNU ISO C++ Library. This library is free |
| // software; you can redistribute it and/or modify it under the |
| // terms of the GNU General Public License as published by the |
| // Free Software Foundation; either version 3, or (at your option) |
| // any later version. |
| |
| // This library is distributed in the hope that it will be useful, |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| // GNU General Public License for more details. |
| |
| // Under Section 7 of GPL version 3, you are granted additional |
| // permissions described in the GCC Runtime Library Exception, version |
| // 3.1, as published by the Free Software Foundation. |
| |
| // You should have received a copy of the GNU General Public License and |
| // a copy of the GCC Runtime Library Exception along with this program; |
| // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
| // <http://www.gnu.org/licenses/>. |
| |
| /* |
| * |
| * Copyright (c) 1994 |
| * Hewlett-Packard Company |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Hewlett-Packard Company makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| * |
| * |
| * Copyright (c) 1996-1998 |
| * Silicon Graphics Computer Systems, Inc. |
| * |
| * Permission to use, copy, modify, distribute and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies and |
| * that both that copyright notice and this permission notice appear |
| * in supporting documentation. Silicon Graphics makes no |
| * representations about the suitability of this software for any |
| * purpose. It is provided "as is" without express or implied warranty. |
| */ |
| |
| /** @file bits/stl_algobase.h |
| * This is an internal header file, included by other library headers. |
| * Do not attempt to use it directly. @headername{algorithm} |
| */ |
| |
| #ifndef _STL_ALGOBASE_H |
| #define _STL_ALGOBASE_H 1 |
| |
| #include <bits/c++config.h> |
| #include <bits/functexcept.h> |
| #include <bits/cpp_type_traits.h> |
| #include <ext/type_traits.h> |
| #include <ext/numeric_traits.h> |
| #include <bits/stl_pair.h> |
| #include <bits/stl_iterator_base_types.h> |
| #include <bits/stl_iterator_base_funcs.h> |
| #include <bits/stl_iterator.h> |
| #include <bits/concept_check.h> |
| #include <debug/debug.h> |
| #include <bits/move.h> // For std::swap and _GLIBCXX_MOVE |
| |
| namespace std _GLIBCXX_VISIBILITY(default) |
| { |
| _GLIBCXX_BEGIN_NAMESPACE_VERSION |
| |
| // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a |
| // nutshell, we are partially implementing the resolution of DR 187, |
| // when it's safe, i.e., the value_types are equal. |
| template<bool _BoolType> |
| struct __iter_swap |
| { |
| template<typename _ForwardIterator1, typename _ForwardIterator2> |
| static void |
| iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type |
| _ValueType1; |
| _ValueType1 __tmp = _GLIBCXX_MOVE(*__a); |
| *__a = _GLIBCXX_MOVE(*__b); |
| *__b = _GLIBCXX_MOVE(__tmp); |
| } |
| }; |
| |
| template<> |
| struct __iter_swap<true> |
| { |
| template<typename _ForwardIterator1, typename _ForwardIterator2> |
| static void |
| iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) |
| { |
| swap(*__a, *__b); |
| } |
| }; |
| |
| /** |
| * @brief Swaps the contents of two iterators. |
| * @ingroup mutating_algorithms |
| * @param __a An iterator. |
| * @param __b Another iterator. |
| * @return Nothing. |
| * |
| * This function swaps the values pointed to by two iterators, not the |
| * iterators themselves. |
| */ |
| template<typename _ForwardIterator1, typename _ForwardIterator2> |
| inline void |
| iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) |
| { |
| typedef typename iterator_traits<_ForwardIterator1>::value_type |
| _ValueType1; |
| typedef typename iterator_traits<_ForwardIterator2>::value_type |
| _ValueType2; |
| |
| // concept requirements |
| __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
| _ForwardIterator1>) |
| __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
| _ForwardIterator2>) |
| __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, |
| _ValueType2>) |
| __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, |
| _ValueType1>) |
| |
| typedef typename iterator_traits<_ForwardIterator1>::reference |
| _ReferenceType1; |
| typedef typename iterator_traits<_ForwardIterator2>::reference |
| _ReferenceType2; |
| std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value |
| && __are_same<_ValueType1&, _ReferenceType1>::__value |
| && __are_same<_ValueType2&, _ReferenceType2>::__value>:: |
| iter_swap(__a, __b); |
| } |
| |
| /** |
| * @brief Swap the elements of two sequences. |
| * @ingroup mutating_algorithms |
| * @param __first1 A forward iterator. |
| * @param __last1 A forward iterator. |
| * @param __first2 A forward iterator. |
| * @return An iterator equal to @p first2+(last1-first1). |
| * |
| * Swaps each element in the range @p [first1,last1) with the |
| * corresponding element in the range @p [first2,(last1-first1)). |
| * The ranges must not overlap. |
| */ |
| template<typename _ForwardIterator1, typename _ForwardIterator2> |
| _ForwardIterator2 |
| swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
| _ForwardIterator2 __first2) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
| _ForwardIterator1>) |
| __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
| _ForwardIterator2>) |
| __glibcxx_requires_valid_range(__first1, __last1); |
| |
| for (; __first1 != __last1; ++__first1, ++__first2) |
| std::iter_swap(__first1, __first2); |
| return __first2; |
| } |
| |
| /** |
| * @brief This does what you think it does. |
| * @ingroup sorting_algorithms |
| * @param __a A thing of arbitrary type. |
| * @param __b Another thing of arbitrary type. |
| * @return The lesser of the parameters. |
| * |
| * This is the simple classic generic implementation. It will work on |
| * temporary expressions, since they are only evaluated once, unlike a |
| * preprocessor macro. |
| */ |
| template<typename _Tp> |
| inline const _Tp& |
| min(const _Tp& __a, const _Tp& __b) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
| //return __b < __a ? __b : __a; |
| if (__b < __a) |
| return __b; |
| return __a; |
| } |
| |
| /** |
| * @brief This does what you think it does. |
| * @ingroup sorting_algorithms |
| * @param __a A thing of arbitrary type. |
| * @param __b Another thing of arbitrary type. |
| * @return The greater of the parameters. |
| * |
| * This is the simple classic generic implementation. It will work on |
| * temporary expressions, since they are only evaluated once, unlike a |
| * preprocessor macro. |
| */ |
| template<typename _Tp> |
| inline const _Tp& |
| max(const _Tp& __a, const _Tp& __b) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) |
| //return __a < __b ? __b : __a; |
| if (__a < __b) |
| return __b; |
| return __a; |
| } |
| |
| /** |
| * @brief This does what you think it does. |
| * @ingroup sorting_algorithms |
| * @param __a A thing of arbitrary type. |
| * @param __b Another thing of arbitrary type. |
| * @param __comp A @link comparison_functors comparison functor@endlink. |
| * @return The lesser of the parameters. |
| * |
| * This will work on temporary expressions, since they are only evaluated |
| * once, unlike a preprocessor macro. |
| */ |
| template<typename _Tp, typename _Compare> |
| inline const _Tp& |
| min(const _Tp& __a, const _Tp& __b, _Compare __comp) |
| { |
| //return __comp(__b, __a) ? __b : __a; |
| if (__comp(__b, __a)) |
| return __b; |
| return __a; |
| } |
| |
| /** |
| * @brief This does what you think it does. |
| * @ingroup sorting_algorithms |
| * @param __a A thing of arbitrary type. |
| * @param __b Another thing of arbitrary type. |
| * @param __comp A @link comparison_functors comparison functor@endlink. |
| * @return The greater of the parameters. |
| * |
| * This will work on temporary expressions, since they are only evaluated |
| * once, unlike a preprocessor macro. |
| */ |
| template<typename _Tp, typename _Compare> |
| inline const _Tp& |
| max(const _Tp& __a, const _Tp& __b, _Compare __comp) |
| { |
| //return __comp(__a, __b) ? __b : __a; |
| if (__comp(__a, __b)) |
| return __b; |
| return __a; |
| } |
| |
| // If _Iterator is a __normal_iterator return its base (a plain pointer, |
| // normally) otherwise return it untouched. See copy, fill, ... |
| template<typename _Iterator> |
| struct _Niter_base |
| : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value> |
| { }; |
| |
| template<typename _Iterator> |
| inline typename _Niter_base<_Iterator>::iterator_type |
| __niter_base(_Iterator __it) |
| { return std::_Niter_base<_Iterator>::_S_base(__it); } |
| |
| // Likewise, for move_iterator. |
| template<typename _Iterator> |
| struct _Miter_base |
| : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value> |
| { }; |
| |
| template<typename _Iterator> |
| inline typename _Miter_base<_Iterator>::iterator_type |
| __miter_base(_Iterator __it) |
| { return std::_Miter_base<_Iterator>::_S_base(__it); } |
| |
| // All of these auxiliary structs serve two purposes. (1) Replace |
| // calls to copy with memmove whenever possible. (Memmove, not memcpy, |
| // because the input and output ranges are permitted to overlap.) |
| // (2) If we're using random access iterators, then write the loop as |
| // a for loop with an explicit count. |
| |
| template<bool, bool, typename> |
| struct __copy_move |
| { |
| template<typename _II, typename _OI> |
| static _OI |
| __copy_m(_II __first, _II __last, _OI __result) |
| { |
| for (; __first != __last; ++__result, ++__first) |
| *__result = *__first; |
| return __result; |
| } |
| }; |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| template<typename _Category> |
| struct __copy_move<true, false, _Category> |
| { |
| template<typename _II, typename _OI> |
| static _OI |
| __copy_m(_II __first, _II __last, _OI __result) |
| { |
| for (; __first != __last; ++__result, ++__first) |
| *__result = std::move(*__first); |
| return __result; |
| } |
| }; |
| #endif |
| |
| template<> |
| struct __copy_move<false, false, random_access_iterator_tag> |
| { |
| template<typename _II, typename _OI> |
| static _OI |
| __copy_m(_II __first, _II __last, _OI __result) |
| { |
| typedef typename iterator_traits<_II>::difference_type _Distance; |
| for(_Distance __n = __last - __first; __n > 0; --__n) |
| { |
| *__result = *__first; |
| ++__first; |
| ++__result; |
| } |
| return __result; |
| } |
| }; |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| template<> |
| struct __copy_move<true, false, random_access_iterator_tag> |
| { |
| template<typename _II, typename _OI> |
| static _OI |
| __copy_m(_II __first, _II __last, _OI __result) |
| { |
| typedef typename iterator_traits<_II>::difference_type _Distance; |
| for(_Distance __n = __last - __first; __n > 0; --__n) |
| { |
| *__result = std::move(*__first); |
| ++__first; |
| ++__result; |
| } |
| return __result; |
| } |
| }; |
| #endif |
| |
| template<bool _IsMove> |
| struct __copy_move<_IsMove, true, random_access_iterator_tag> |
| { |
| template<typename _Tp> |
| static _Tp* |
| __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) |
| { |
| const ptrdiff_t _Num = __last - __first; |
| if (_Num) |
| __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); |
| return __result + _Num; |
| } |
| }; |
| |
| template<bool _IsMove, typename _II, typename _OI> |
| inline _OI |
| __copy_move_a(_II __first, _II __last, _OI __result) |
| { |
| typedef typename iterator_traits<_II>::value_type _ValueTypeI; |
| typedef typename iterator_traits<_OI>::value_type _ValueTypeO; |
| typedef typename iterator_traits<_II>::iterator_category _Category; |
| const bool __simple = (__is_trivial(_ValueTypeI) |
| && __is_pointer<_II>::__value |
| && __is_pointer<_OI>::__value |
| && __are_same<_ValueTypeI, _ValueTypeO>::__value); |
| |
| return std::__copy_move<_IsMove, __simple, |
| _Category>::__copy_m(__first, __last, __result); |
| } |
| |
| // Helpers for streambuf iterators (either istream or ostream). |
| // NB: avoid including <iosfwd>, relatively large. |
| template<typename _CharT> |
| struct char_traits; |
| |
| template<typename _CharT, typename _Traits> |
| class istreambuf_iterator; |
| |
| template<typename _CharT, typename _Traits> |
| class ostreambuf_iterator; |
| |
| template<bool _IsMove, typename _CharT> |
| typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
| ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type |
| __copy_move_a2(_CharT*, _CharT*, |
| ostreambuf_iterator<_CharT, char_traits<_CharT> >); |
| |
| template<bool _IsMove, typename _CharT> |
| typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
| ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type |
| __copy_move_a2(const _CharT*, const _CharT*, |
| ostreambuf_iterator<_CharT, char_traits<_CharT> >); |
| |
| template<bool _IsMove, typename _CharT> |
| typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, |
| _CharT*>::__type |
| __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, |
| istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); |
| |
| template<bool _IsMove, typename _II, typename _OI> |
| inline _OI |
| __copy_move_a2(_II __first, _II __last, _OI __result) |
| { |
| return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first), |
| std::__niter_base(__last), |
| std::__niter_base(__result))); |
| } |
| |
| /** |
| * @brief Copies the range [first,last) into result. |
| * @ingroup mutating_algorithms |
| * @param __first An input iterator. |
| * @param __last An input iterator. |
| * @param __result An output iterator. |
| * @return result + (first - last) |
| * |
| * This inline function will boil down to a call to @c memmove whenever |
| * possible. Failing that, if random access iterators are passed, then the |
| * loop count will be known (and therefore a candidate for compiler |
| * optimizations such as unrolling). Result may not be contained within |
| * [first,last); the copy_backward function should be used instead. |
| * |
| * Note that the end of the output range is permitted to be contained |
| * within [first,last). |
| */ |
| template<typename _II, typename _OI> |
| inline _OI |
| copy(_II __first, _II __last, _OI __result) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_InputIteratorConcept<_II>) |
| __glibcxx_function_requires(_OutputIteratorConcept<_OI, |
| typename iterator_traits<_II>::value_type>) |
| __glibcxx_requires_valid_range(__first, __last); |
| |
| return (std::__copy_move_a2<__is_move_iterator<_II>::__value> |
| (std::__miter_base(__first), std::__miter_base(__last), |
| __result)); |
| } |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| /** |
| * @brief Moves the range [first,last) into result. |
| * @ingroup mutating_algorithms |
| * @param __first An input iterator. |
| * @param __last An input iterator. |
| * @param __result An output iterator. |
| * @return result + (first - last) |
| * |
| * This inline function will boil down to a call to @c memmove whenever |
| * possible. Failing that, if random access iterators are passed, then the |
| * loop count will be known (and therefore a candidate for compiler |
| * optimizations such as unrolling). Result may not be contained within |
| * [first,last); the move_backward function should be used instead. |
| * |
| * Note that the end of the output range is permitted to be contained |
| * within [first,last). |
| */ |
| template<typename _II, typename _OI> |
| inline _OI |
| move(_II __first, _II __last, _OI __result) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_InputIteratorConcept<_II>) |
| __glibcxx_function_requires(_OutputIteratorConcept<_OI, |
| typename iterator_traits<_II>::value_type>) |
| __glibcxx_requires_valid_range(__first, __last); |
| |
| return std::__copy_move_a2<true>(std::__miter_base(__first), |
| std::__miter_base(__last), __result); |
| } |
| |
| #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) |
| #else |
| #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) |
| #endif |
| |
| template<bool, bool, typename> |
| struct __copy_move_backward |
| { |
| template<typename _BI1, typename _BI2> |
| static _BI2 |
| __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| while (__first != __last) |
| *--__result = *--__last; |
| return __result; |
| } |
| }; |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| template<typename _Category> |
| struct __copy_move_backward<true, false, _Category> |
| { |
| template<typename _BI1, typename _BI2> |
| static _BI2 |
| __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| while (__first != __last) |
| *--__result = std::move(*--__last); |
| return __result; |
| } |
| }; |
| #endif |
| |
| template<> |
| struct __copy_move_backward<false, false, random_access_iterator_tag> |
| { |
| template<typename _BI1, typename _BI2> |
| static _BI2 |
| __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| typename iterator_traits<_BI1>::difference_type __n; |
| for (__n = __last - __first; __n > 0; --__n) |
| *--__result = *--__last; |
| return __result; |
| } |
| }; |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| template<> |
| struct __copy_move_backward<true, false, random_access_iterator_tag> |
| { |
| template<typename _BI1, typename _BI2> |
| static _BI2 |
| __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| typename iterator_traits<_BI1>::difference_type __n; |
| for (__n = __last - __first; __n > 0; --__n) |
| *--__result = std::move(*--__last); |
| return __result; |
| } |
| }; |
| #endif |
| |
| template<bool _IsMove> |
| struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> |
| { |
| template<typename _Tp> |
| static _Tp* |
| __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) |
| { |
| const ptrdiff_t _Num = __last - __first; |
| if (_Num) |
| __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); |
| return __result - _Num; |
| } |
| }; |
| |
| template<bool _IsMove, typename _BI1, typename _BI2> |
| inline _BI2 |
| __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| typedef typename iterator_traits<_BI1>::value_type _ValueType1; |
| typedef typename iterator_traits<_BI2>::value_type _ValueType2; |
| typedef typename iterator_traits<_BI1>::iterator_category _Category; |
| const bool __simple = (__is_trivial(_ValueType1) |
| && __is_pointer<_BI1>::__value |
| && __is_pointer<_BI2>::__value |
| && __are_same<_ValueType1, _ValueType2>::__value); |
| |
| return std::__copy_move_backward<_IsMove, __simple, |
| _Category>::__copy_move_b(__first, |
| __last, |
| __result); |
| } |
| |
| template<bool _IsMove, typename _BI1, typename _BI2> |
| inline _BI2 |
| __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| return _BI2(std::__copy_move_backward_a<_IsMove> |
| (std::__niter_base(__first), std::__niter_base(__last), |
| std::__niter_base(__result))); |
| } |
| |
| /** |
| * @brief Copies the range [first,last) into result. |
| * @ingroup mutating_algorithms |
| * @param __first A bidirectional iterator. |
| * @param __last A bidirectional iterator. |
| * @param __result A bidirectional iterator. |
| * @return result - (first - last) |
| * |
| * The function has the same effect as copy, but starts at the end of the |
| * range and works its way to the start, returning the start of the result. |
| * This inline function will boil down to a call to @c memmove whenever |
| * possible. Failing that, if random access iterators are passed, then the |
| * loop count will be known (and therefore a candidate for compiler |
| * optimizations such as unrolling). |
| * |
| * Result may not be in the range [first,last). Use copy instead. Note |
| * that the start of the output range may overlap [first,last). |
| */ |
| template<typename _BI1, typename _BI2> |
| inline _BI2 |
| copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) |
| __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) |
| __glibcxx_function_requires(_ConvertibleConcept< |
| typename iterator_traits<_BI1>::value_type, |
| typename iterator_traits<_BI2>::value_type>) |
| __glibcxx_requires_valid_range(__first, __last); |
| |
| return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> |
| (std::__miter_base(__first), std::__miter_base(__last), |
| __result)); |
| } |
| |
| #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
| /** |
| * @brief Moves the range [first,last) into result. |
| * @ingroup mutating_algorithms |
| * @param __first A bidirectional iterator. |
| * @param __last A bidirectional iterator. |
| * @param __result A bidirectional iterator. |
| * @return result - (first - last) |
| * |
| * The function has the same effect as move, but starts at the end of the |
| * range and works its way to the start, returning the start of the result. |
| * This inline function will boil down to a call to @c memmove whenever |
| * possible. Failing that, if random access iterators are passed, then the |
| * loop count will be known (and therefore a candidate for compiler |
| * optimizations such as unrolling). |
| * |
| * Result may not be in the range (first,last]. Use move instead. Note |
| * that the start of the output range may overlap [first,last). |
| */ |
| template<typename _BI1, typename _BI2> |
| inline _BI2 |
| move_backward(_BI1 __first, _BI1 __last, _BI2 __result) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) |
| __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) |
| __glibcxx_function_requires(_ConvertibleConcept< |
| typename iterator_traits<_BI1>::value_type, |
| typename iterator_traits<_BI2>::value_type>) |
| __glibcxx_requires_valid_range(__first, __last); |
| |
| return std::__copy_move_backward_a2<true>(std::__miter_base(__first), |
| std::__miter_base(__last), |
| __result); |
| } |
| |
| #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) |
| #else |
| #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) |
| #endif |
| |
| template<typename _ForwardIterator, typename _Tp> |
| inline typename |
| __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type |
| __fill_a(_ForwardIterator __first, _ForwardIterator __last, |
| const _Tp& __value) |
| { |
| for (; __first != __last; ++__first) |
| *__first = __value; |
| } |
| |
| template<typename _ForwardIterator, typename _Tp> |
| inline typename |
| __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type |
| __fill_a(_ForwardIterator __first, _ForwardIterator __last, |
| const _Tp& __value) |
| { |
| const _Tp __tmp = __value; |
| for (; __first != __last; ++__first) |
| *__first = __tmp; |
| } |
| |
| // Specialization: for char types we can use memset. |
| template<typename _Tp> |
| inline typename |
| __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type |
| __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) |
| { |
| const _Tp __tmp = __c; |
| __builtin_memset(__first, static_cast<unsigned char>(__tmp), |
| __last - __first); |
| } |
| |
| /** |
| * @brief Fills the range [first,last) with copies of value. |
| * @ingroup mutating_algorithms |
| * @param __first A forward iterator. |
| * @param __last A forward iterator. |
| * @param __value A reference-to-const of arbitrary type. |
| * @return Nothing. |
| * |
| * This function fills a range with copies of the same value. For char |
| * types filling contiguous areas of memory, this becomes an inline call |
| * to @c memset or @c wmemset. |
| */ |
| template<typename _ForwardIterator, typename _Tp> |
| inline void |
| fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
| _ForwardIterator>) |
| __glibcxx_requires_valid_range(__first, __last); |
| |
| std::__fill_a(std::__niter_base(__first), std::__niter_base(__last), |
| __value); |
| } |
| |
| template<typename _OutputIterator, typename _Size, typename _Tp> |
| inline typename |
| __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type |
| __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) |
| { |
| for (__decltype(__n + 0) __niter = __n; |
| __niter > 0; --__niter, ++__first) |
| *__first = __value; |
| return __first; |
| } |
| |
| template<typename _OutputIterator, typename _Size, typename _Tp> |
| inline typename |
| __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type |
| __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) |
| { |
| const _Tp __tmp = __value; |
| for (__decltype(__n + 0) __niter = __n; |
| __niter > 0; --__niter, ++__first) |
| *__first = __tmp; |
| return __first; |
| } |
| |
| template<typename _Size, typename _Tp> |
| inline typename |
| __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type |
| __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) |
| { |
| std::__fill_a(__first, __first + __n, __c); |
| return __first + __n; |
| } |
| |
| /** |
| * @brief Fills the range [first,first+n) with copies of value. |
| * @ingroup mutating_algorithms |
| * @param __first An output iterator. |
| * @param __n The count of copies to perform. |
| * @param __value A reference-to-const of arbitrary type. |
| * @return The iterator at first+n. |
| * |
| * This function fills a range with copies of the same value. For char |
| * types filling contiguous areas of memory, this becomes an inline call |
| * to @c memset or @ wmemset. |
| * |
| * _GLIBCXX_RESOLVE_LIB_DEFECTS |
| * DR 865. More algorithms that throw away information |
| */ |
| template<typename _OI, typename _Size, typename _Tp> |
| inline _OI |
| fill_n(_OI __first, _Size __n, const _Tp& __value) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) |
| |
| return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value)); |
| } |
| |
| template<bool _BoolType> |
| struct __equal |
| { |
| template<typename _II1, typename _II2> |
| static bool |
| equal(_II1 __first1, _II1 __last1, _II2 __first2) |
| { |
| for (; __first1 != __last1; ++__first1, ++__first2) |
| if (!(*__first1 == *__first2)) |
| return false; |
| return true; |
| } |
| }; |
| |
| template<> |
| struct __equal<true> |
| { |
| template<typename _Tp> |
| static bool |
| equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) |
| { |
| return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) |
| * (__last1 - __first1)); |
| } |
| }; |
| |
| template<typename _II1, typename _II2> |
| inline bool |
| __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) |
| { |
| typedef typename iterator_traits<_II1>::value_type _ValueType1; |
| typedef typename iterator_traits<_II2>::value_type _ValueType2; |
| const bool __simple = ((__is_integer<_ValueType1>::__value |
| || __is_pointer<_ValueType1>::__value) |
| && __is_pointer<_II1>::__value |
| && __is_pointer<_II2>::__value |
| && __are_same<_ValueType1, _ValueType2>::__value); |
| |
| return std::__equal<__simple>::equal(__first1, __last1, __first2); |
| } |
| |
| |
| template<typename, typename> |
| struct __lc_rai |
| { |
| template<typename _II1, typename _II2> |
| static _II1 |
| __newlast1(_II1, _II1 __last1, _II2, _II2) |
| { return __last1; } |
| |
| template<typename _II> |
| static bool |
| __cnd2(_II __first, _II __last) |
| { return __first != __last; } |
| }; |
| |
| template<> |
| struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> |
| { |
| template<typename _RAI1, typename _RAI2> |
| static _RAI1 |
| __newlast1(_RAI1 __first1, _RAI1 __last1, |
| _RAI2 __first2, _RAI2 __last2) |
| { |
| const typename iterator_traits<_RAI1>::difference_type |
| __diff1 = __last1 - __first1; |
| const typename iterator_traits<_RAI2>::difference_type |
| __diff2 = __last2 - __first2; |
| return __diff2 < __diff1 ? __first1 + __diff2 : __last1; |
| } |
| |
| template<typename _RAI> |
| static bool |
| __cnd2(_RAI, _RAI) |
| { return true; } |
| }; |
| |
| template<bool _BoolType> |
| struct __lexicographical_compare |
| { |
| template<typename _II1, typename _II2> |
| static bool __lc(_II1, _II1, _II2, _II2); |
| }; |
| |
| template<bool _BoolType> |
| template<typename _II1, typename _II2> |
| bool |
| __lexicographical_compare<_BoolType>:: |
| __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) |
| { |
| typedef typename iterator_traits<_II1>::iterator_category _Category1; |
| typedef typename iterator_traits<_II2>::iterator_category _Category2; |
| typedef std::__lc_rai<_Category1, _Category2> __rai_type; |
| |
| __last1 = __rai_type::__newlast1(__first1, __last1, |
| __first2, __last2); |
| for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); |
| ++__first1, ++__first2) |
| { |
| if (*__first1 < *__first2) |
| return true; |
| if (*__first2 < *__first1) |
| return false; |
| } |
| return __first1 == __last1 && __first2 != __last2; |
| } |
| |
| template<> |
| struct __lexicographical_compare<true> |
| { |
| template<typename _Tp, typename _Up> |
| static bool |
| __lc(const _Tp* __first1, const _Tp* __last1, |
| const _Up* __first2, const _Up* __last2) |
| { |
| const size_t __len1 = __last1 - __first1; |
| const size_t __len2 = __last2 - __first2; |
| const int __result = __builtin_memcmp(__first1, __first2, |
| std::min(__len1, __len2)); |
| return __result != 0 ? __result < 0 : __len1 < __len2; |
| } |
| }; |
| |
| template<typename _II1, typename _II2> |
| inline bool |
| __lexicographical_compare_aux(_II1 __first1, _II1 __last1, |
| _II2 __first2, _II2 __last2) |
| { |
| typedef typename iterator_traits<_II1>::value_type _ValueType1; |
| typedef typename iterator_traits<_II2>::value_type _ValueType2; |
| const bool __simple = |
| (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value |
| && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed |
| && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed |
| && __is_pointer<_II1>::__value |
| && __is_pointer<_II2>::__value); |
| |
| return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, |
| __first2, __last2); |
| } |
| |
| /** |
| * @brief Finds the first position in which @a val could be inserted |
| * without changing the ordering. |
| * @param __first An iterator. |
| * @param __last Another iterator. |
| * @param __val The search term. |
| * @return An iterator pointing to the first element <em>not less |
| * than</em> @a val, or end() if every element is less than |
| * @a val. |
| * @ingroup binary_search_algorithms |
| */ |
| template<typename _ForwardIterator, typename _Tp> |
| _ForwardIterator |
| lower_bound(_ForwardIterator __first, _ForwardIterator __last, |
| const _Tp& __val) |
| { |
| typedef typename iterator_traits<_ForwardIterator>::value_type |
| _ValueType; |
| typedef typename iterator_traits<_ForwardIterator>::difference_type |
| _DistanceType; |
| |
| // concept requirements |
| __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
| __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) |
| __glibcxx_requires_partitioned_lower(__first, __last, __val); |
| |
| _DistanceType __len = std::distance(__first, __last); |
| |
| while (__len > 0) |
| { |
| _DistanceType __half = __len >> 1; |
| _ForwardIterator __middle = __first; |
| std::advance(__middle, __half); |
| if (*__middle < __val) |
| { |
| __first = __middle; |
| ++__first; |
| __len = __len - __half - 1; |
| } |
| else |
| __len = __half; |
| } |
| return __first; |
| } |
| |
| /// This is a helper function for the sort routines and for random.tcc. |
| // Precondition: __n > 0. |
| template<typename _Size> |
| inline _Size |
| __lg(_Size __n) |
| { |
| _Size __k; |
| for (__k = 0; __n != 0; __n >>= 1) |
| ++__k; |
| return __k - 1; |
| } |
| |
| inline int |
| __lg(int __n) |
| { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } |
| |
| inline unsigned |
| __lg(unsigned __n) |
| { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } |
| |
| inline long |
| __lg(long __n) |
| { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } |
| |
| inline unsigned long |
| __lg(unsigned long __n) |
| { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } |
| |
| inline long long |
| __lg(long long __n) |
| { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } |
| |
| inline unsigned long long |
| __lg(unsigned long long __n) |
| { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } |
| |
| _GLIBCXX_END_NAMESPACE_VERSION |
| |
| _GLIBCXX_BEGIN_NAMESPACE_ALGO |
| |
| /** |
| * @brief Tests a range for element-wise equality. |
| * @ingroup non_mutating_algorithms |
| * @param __first1 An input iterator. |
| * @param __last1 An input iterator. |
| * @param __first2 An input iterator. |
| * @return A boolean true or false. |
| * |
| * This compares the elements of two ranges using @c == and returns true or |
| * false depending on whether all of the corresponding elements of the |
| * ranges are equal. |
| */ |
| template<typename _II1, typename _II2> |
| inline bool |
| equal(_II1 __first1, _II1 __last1, _II2 __first2) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
| __glibcxx_function_requires(_InputIteratorConcept<_II2>) |
| __glibcxx_function_requires(_EqualOpConcept< |
| typename iterator_traits<_II1>::value_type, |
| typename iterator_traits<_II2>::value_type>) |
| __glibcxx_requires_valid_range(__first1, __last1); |
| |
| return std::__equal_aux(std::__niter_base(__first1), |
| std::__niter_base(__last1), |
| std::__niter_base(__first2)); |
| } |
| |
| /** |
| * @brief Tests a range for element-wise equality. |
| * @ingroup non_mutating_algorithms |
| * @param __first1 An input iterator. |
| * @param __last1 An input iterator. |
| * @param __first2 An input iterator. |
| * @param __binary_pred A binary predicate @link functors |
| * functor@endlink. |
| * @return A boolean true or false. |
| * |
| * This compares the elements of two ranges using the binary_pred |
| * parameter, and returns true or |
| * false depending on whether all of the corresponding elements of the |
| * ranges are equal. |
| */ |
| template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> |
| inline bool |
| equal(_IIter1 __first1, _IIter1 __last1, |
| _IIter2 __first2, _BinaryPredicate __binary_pred) |
| { |
| // concept requirements |
| __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) |
| __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) |
| __glibcxx_requires_valid_range(__first1, __last1); |
| |
| for (; __first1 != __last1; ++__first1, ++__first2) |
| if (!bool(__binary_pred(*__first1, *__first2))) |
| return false; |
| return true; |
| } |
| |
| /** |
| * @brief Performs @b dictionary comparison on ranges. |
| * @ingroup sorting_algorithms |
| * @param __first1 An input iterator. |
| * @param __last1 An input iterator. |
| * @param __first2 An input iterator. |
| * @param __last2 An input iterator. |
| * @return A boolean true or false. |
| * |
| * <em>Returns true if the sequence of elements defined by the range |
| * [first1,last1) is lexicographically less than the sequence of elements |
| * defined by the range [first2,last2). Returns false otherwise.</em> |
| * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, |
| * then this is an inline call to @c memcmp. |
| */ |
| template<typename _II1, typename _II2> |
| inline bool |
| lexicographical_compare(_II1 __first1, _II1 __last1, |
| _II2 __first2, _II2 __last2) |
| { |
| // concept requirements |
| typedef typename iterator_traits<_II1>::value_type _ValueType1; |
| typedef typename iterator_traits<_II2>::value_type _ValueType2; |
| __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
| __glibcxx_function_requires(_InputIteratorConcept<_II2>) |
| __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) |
| __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) |
| __glibcxx_requires_valid_range(__first1, __last1); |
| __glibcxx_requires_valid_range(__first2, __last2); |
| |
| return std::__lexicographical_compare_aux(std::__niter_base(__first1), |
| std::__niter_base(__last1), |
| std::__niter_base(__first2), |
| std::__niter_base(__last2)); |
| } |
| |
| /** |
| * @brief Performs @b dictionary comparison on ranges. |
| * @ingroup sorting_algorithms |
| * @param __first1 An input iterator. |
| * @param __last1 An input iterator. |
| * @param __first2 An input iterator. |
| * @param __last2 An input iterator. |
| * @param __comp A @link comparison_functors comparison functor@endlink. |
| * @return A boolean true or false. |
| * |
| * The same as the four-parameter @c lexicographical_compare, but uses the |
| * comp parameter instead of @c <. |
| */ |
| template<typename _II1, typename _II2, typename _Compare> |
| bool |
| lexicographical_compare(_II1 __first1, _II1 __last1, |
| _II2 __first2, _II2 __last2, _Compare __comp) |
| { |
| typedef typename iterator_traits<_II1>::iterator_category _Category1; |
| typedef typename iterator_traits<_II2>::iterator_category _Category2; |
| typedef std::__lc_rai<_Category1, _Category2> __rai_type; |
| |
| // concept requirements |
| __glibcxx_function_requires(_InputIteratorConcept<_II1>) |
| __glibcxx_function_requires(_InputIteratorConcept<_II2>) |
| __glibcxx_requires_valid_range(__first1, __last1); |
| __glibcxx_requires_valid_range(__first2, __last2); |
| |
| __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); |
| for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); |
| ++__first1, ++__first2) |
| { |
| if (__comp(*__first1, *__first2)) |
| return true; |
| if (__comp(*__first2, *__first1)) |
| return false; |
| } |
| return __first1 == __last1 && __first2 != __last2; |
| } |
| |
| /** |
| * @brief Finds the places in ranges which don't match. |
| * @ingroup non_mutating_algorithms |
| * @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. |
| * @ingroup non_mutating_algorithms |
| * @param __first1 An input iterator. |
| * @param __last1 An input iterator. |
| * @param __first2 An input iterator. |
| * @param __binary_pred A binary predicate @link functors |
| * 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); |
| } |
| |
| _GLIBCXX_END_NAMESPACE_ALGO |
| } // namespace std |
| |
| // NB: This file is included within many other C++ includes, as a way |
| // of getting the base algorithms. So, make sure that parallel bits |
| // come in too if requested. |
| #ifdef _GLIBCXX_PARALLEL |
| # include <parallel/algobase.h> |
| #endif |
| |
| #endif |
