0,0 → 1,6324 |
// Algorithm implementation -*- C++ -*- |
|
// Copyright (C) 2001-2013 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 |
* 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_algo.h |
* This is an internal header file, included by other library headers. |
* Do not attempt to use it directly. @headername{algorithm} |
*/ |
|
#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 |
|
#if __cplusplus >= 201103L |
#include <random> // for std::uniform_int_distribution |
#include <functional> // for std::bind |
#endif |
|
// See concept_check.h for the __glibcxx_*_requires macros. |
|
namespace std _GLIBCXX_VISIBILITY(default) |
{ |
_GLIBCXX_BEGIN_NAMESPACE_VERSION |
|
/// Swaps the median value of *__a, *__b and *__c to *__result |
template<typename _Iterator> |
void |
__move_median_to_first(_Iterator __result, _Iterator __a, |
_Iterator __b, _Iterator __c) |
{ |
// concept requirements |
__glibcxx_function_requires(_LessThanComparableConcept< |
typename iterator_traits<_Iterator>::value_type>) |
|
if (*__a < *__b) |
{ |
if (*__b < *__c) |
std::iter_swap(__result, __b); |
else if (*__a < *__c) |
std::iter_swap(__result, __c); |
else |
std::iter_swap(__result, __a); |
} |
else if (*__a < *__c) |
std::iter_swap(__result, __a); |
else if (*__b < *__c) |
std::iter_swap(__result, __c); |
else |
std::iter_swap(__result, __b); |
} |
|
/// Swaps the median value of *__a, *__b and *__c under __comp to *__result |
template<typename _Iterator, typename _Compare> |
void |
__move_median_to_first(_Iterator __result, _Iterator __a, |
_Iterator __b, _Iterator __c, |
_Compare __comp) |
{ |
// concept requirements |
__glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool, |
typename iterator_traits<_Iterator>::value_type, |
typename iterator_traits<_Iterator>::value_type>) |
|
if (__comp(*__a, *__b)) |
{ |
if (__comp(*__b, *__c)) |
std::iter_swap(__result, __b); |
else if (__comp(*__a, *__c)) |
std::iter_swap(__result, __c); |
else |
std::iter_swap(__result, __a); |
} |
else if (__comp(*__a, *__c)) |
std::iter_swap(__result, __a); |
else if (__comp(*__b, *__c)) |
std::iter_swap(__result, __c); |
else |
std::iter_swap(__result, __b); |
} |
|
// for_each |
|
/// This is an overload used by find() for the Input Iterator case. |
template<typename _InputIterator, typename _Tp> |
inline _InputIterator |
__find(_InputIterator __first, _InputIterator __last, |
const _Tp& __val, input_iterator_tag) |
{ |
while (__first != __last && !(*__first == __val)) |
++__first; |
return __first; |
} |
|
/// 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, |
_Predicate __pred, input_iterator_tag) |
{ |
while (__first != __last && !bool(__pred(*__first))) |
++__first; |
return __first; |
} |
|
/// This is an overload used by find() for the RAI case. |
template<typename _RandomAccessIterator, typename _Tp> |
_RandomAccessIterator |
__find(_RandomAccessIterator __first, _RandomAccessIterator __last, |
const _Tp& __val, random_access_iterator_tag) |
{ |
typename iterator_traits<_RandomAccessIterator>::difference_type |
__trip_count = (__last - __first) >> 2; |
|
for (; __trip_count > 0; --__trip_count) |
{ |
if (*__first == __val) |
return __first; |
++__first; |
|
if (*__first == __val) |
return __first; |
++__first; |
|
if (*__first == __val) |
return __first; |
++__first; |
|
if (*__first == __val) |
return __first; |
++__first; |
} |
|
switch (__last - __first) |
{ |
case 3: |
if (*__first == __val) |
return __first; |
++__first; |
case 2: |
if (*__first == __val) |
return __first; |
++__first; |
case 1: |
if (*__first == __val) |
return __first; |
++__first; |
case 0: |
default: |
return __last; |
} |
} |
|
/// This is an overload used by find_if() for the RAI case. |
template<typename _RandomAccessIterator, typename _Predicate> |
_RandomAccessIterator |
__find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, |
_Predicate __pred, random_access_iterator_tag) |
{ |
typename iterator_traits<_RandomAccessIterator>::difference_type |
__trip_count = (__last - __first) >> 2; |
|
for (; __trip_count > 0; --__trip_count) |
{ |
if (__pred(*__first)) |
return __first; |
++__first; |
|
if (__pred(*__first)) |
return __first; |
++__first; |
|
if (__pred(*__first)) |
return __first; |
++__first; |
|
if (__pred(*__first)) |
return __first; |
++__first; |
} |
|
switch (__last - __first) |
{ |
case 3: |
if (__pred(*__first)) |
return __first; |
++__first; |
case 2: |
if (__pred(*__first)) |
return __first; |
++__first; |
case 1: |
if (__pred(*__first)) |
return __first; |
++__first; |
case 0: |
default: |
return __last; |
} |
} |
|
/// This is an overload used by find_if_not() for the Input Iterator case. |
template<typename _InputIterator, typename _Predicate> |
inline _InputIterator |
__find_if_not(_InputIterator __first, _InputIterator __last, |
_Predicate __pred, input_iterator_tag) |
{ |
while (__first != __last && bool(__pred(*__first))) |
++__first; |
return __first; |
} |
|
/// This is an overload used by find_if_not() for the RAI case. |
template<typename _RandomAccessIterator, typename _Predicate> |
_RandomAccessIterator |
__find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last, |
_Predicate __pred, random_access_iterator_tag) |
{ |
typename iterator_traits<_RandomAccessIterator>::difference_type |
__trip_count = (__last - __first) >> 2; |
|
for (; __trip_count > 0; --__trip_count) |
{ |
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
|
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
|
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
|
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
} |
|
switch (__last - __first) |
{ |
case 3: |
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
case 2: |
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
case 1: |
if (!bool(__pred(*__first))) |
return __first; |
++__first; |
case 0: |
default: |
return __last; |
} |
} |
|
/// Provided for stable_partition to use. |
template<typename _InputIterator, typename _Predicate> |
inline _InputIterator |
__find_if_not(_InputIterator __first, _InputIterator __last, |
_Predicate __pred) |
{ |
return std::__find_if_not(__first, __last, __pred, |
std::__iterator_category(__first)); |
} |
|
/// Like find_if_not(), but uses and updates a count of the |
/// remaining range length instead of comparing against an end |
/// iterator. |
template<typename _InputIterator, typename _Predicate, typename _Distance> |
_InputIterator |
__find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred) |
{ |
for (; __len; --__len, ++__first) |
if (!bool(__pred(*__first))) |
break; |
return __first; |
} |
|
// set_difference |
// set_intersection |
// set_symmetric_difference |
// set_union |
// for_each |
// find |
// find_if |
// find_first_of |
// adjacent_find |
// count |
// count_if |
// search |
|
/** |
* This is an uglified |
* search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) |
* overloaded for forward iterators. |
*/ |
template<typename _ForwardIterator, typename _Integer, typename _Tp> |
_ForwardIterator |
__search_n(_ForwardIterator __first, _ForwardIterator __last, |
_Integer __count, const _Tp& __val, |
std::forward_iterator_tag) |
{ |
__first = _GLIBCXX_STD_A::find(__first, __last, __val); |
while (__first != __last) |
{ |
typename iterator_traits<_ForwardIterator>::difference_type |
__n = __count; |
_ForwardIterator __i = __first; |
++__i; |
while (__i != __last && __n != 1 && *__i == __val) |
{ |
++__i; |
--__n; |
} |
if (__n == 1) |
return __first; |
if (__i == __last) |
return __last; |
__first = _GLIBCXX_STD_A::find(++__i, __last, __val); |
} |
return __last; |
} |
|
/** |
* This is an uglified |
* search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) |
* overloaded for random access iterators. |
*/ |
template<typename _RandomAccessIter, typename _Integer, typename _Tp> |
_RandomAccessIter |
__search_n(_RandomAccessIter __first, _RandomAccessIter __last, |
_Integer __count, const _Tp& __val, |
std::random_access_iterator_tag) |
{ |
|
typedef typename std::iterator_traits<_RandomAccessIter>::difference_type |
_DistanceType; |
|
_DistanceType __tailSize = __last - __first; |
_DistanceType __remainder = __count; |
|
while (__remainder <= __tailSize) // the main loop... |
{ |
__first += __remainder; |
__tailSize -= __remainder; |
// __first here is always pointing to one past the last element of |
// next possible match. |
_RandomAccessIter __backTrack = __first; |
while (*--__backTrack == __val) |
{ |
if (--__remainder == 0) |
return (__first - __count); // Success |
} |
__remainder = __count + 1 - (__first - __backTrack); |
} |
return __last; // Failure |
} |
|
// search_n |
|
/** |
* This is an uglified |
* search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, |
* _BinaryPredicate) |
* overloaded for forward iterators. |
*/ |
template<typename _ForwardIterator, typename _Integer, typename _Tp, |
typename _BinaryPredicate> |
_ForwardIterator |
__search_n(_ForwardIterator __first, _ForwardIterator __last, |
_Integer __count, const _Tp& __val, |
_BinaryPredicate __binary_pred, std::forward_iterator_tag) |
{ |
while (__first != __last && !bool(__binary_pred(*__first, __val))) |
++__first; |
|
while (__first != __last) |
{ |
typename iterator_traits<_ForwardIterator>::difference_type |
__n = __count; |
_ForwardIterator __i = __first; |
++__i; |
while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val))) |
{ |
++__i; |
--__n; |
} |
if (__n == 1) |
return __first; |
if (__i == __last) |
return __last; |
__first = ++__i; |
while (__first != __last |
&& !bool(__binary_pred(*__first, __val))) |
++__first; |
} |
return __last; |
} |
|
/** |
* This is an uglified |
* search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, |
* _BinaryPredicate) |
* overloaded for random access iterators. |
*/ |
template<typename _RandomAccessIter, typename _Integer, typename _Tp, |
typename _BinaryPredicate> |
_RandomAccessIter |
__search_n(_RandomAccessIter __first, _RandomAccessIter __last, |
_Integer __count, const _Tp& __val, |
_BinaryPredicate __binary_pred, std::random_access_iterator_tag) |
{ |
|
typedef typename std::iterator_traits<_RandomAccessIter>::difference_type |
_DistanceType; |
|
_DistanceType __tailSize = __last - __first; |
_DistanceType __remainder = __count; |
|
while (__remainder <= __tailSize) // the main loop... |
{ |
__first += __remainder; |
__tailSize -= __remainder; |
// __first here is always pointing to one past the last element of |
// next possible match. |
_RandomAccessIter __backTrack = __first; |
while (__binary_pred(*--__backTrack, __val)) |
{ |
if (--__remainder == 0) |
return (__first - __count); // Success |
} |
__remainder = __count + 1 - (__first - __backTrack); |
} |
return __last; // Failure |
} |
|
// find_end for forward iterators. |
template<typename _ForwardIterator1, typename _ForwardIterator2> |
_ForwardIterator1 |
__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
_ForwardIterator2 __first2, _ForwardIterator2 __last2, |
forward_iterator_tag, forward_iterator_tag) |
{ |
if (__first2 == __last2) |
return __last1; |
else |
{ |
_ForwardIterator1 __result = __last1; |
while (1) |
{ |
_ForwardIterator1 __new_result |
= _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2); |
if (__new_result == __last1) |
return __result; |
else |
{ |
__result = __new_result; |
__first1 = __new_result; |
++__first1; |
} |
} |
} |
} |
|
template<typename _ForwardIterator1, typename _ForwardIterator2, |
typename _BinaryPredicate> |
_ForwardIterator1 |
__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
_ForwardIterator2 __first2, _ForwardIterator2 __last2, |
forward_iterator_tag, forward_iterator_tag, |
_BinaryPredicate __comp) |
{ |
if (__first2 == __last2) |
return __last1; |
else |
{ |
_ForwardIterator1 __result = __last1; |
while (1) |
{ |
_ForwardIterator1 __new_result |
= _GLIBCXX_STD_A::search(__first1, __last1, __first2, |
__last2, __comp); |
if (__new_result == __last1) |
return __result; |
else |
{ |
__result = __new_result; |
__first1 = __new_result; |
++__first1; |
} |
} |
} |
} |
|
// find_end for bidirectional iterators (much faster). |
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> |
_BidirectionalIterator1 |
__find_end(_BidirectionalIterator1 __first1, |
_BidirectionalIterator1 __last1, |
_BidirectionalIterator2 __first2, |
_BidirectionalIterator2 __last2, |
bidirectional_iterator_tag, bidirectional_iterator_tag) |
{ |
// concept requirements |
__glibcxx_function_requires(_BidirectionalIteratorConcept< |
_BidirectionalIterator1>) |
__glibcxx_function_requires(_BidirectionalIteratorConcept< |
_BidirectionalIterator2>) |
|
typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; |
typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; |
|
_RevIterator1 __rlast1(__first1); |
_RevIterator2 __rlast2(__first2); |
_RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1), |
__rlast1, |
_RevIterator2(__last2), |
__rlast2); |
|
if (__rresult == __rlast1) |
return __last1; |
else |
{ |
_BidirectionalIterator1 __result = __rresult.base(); |
std::advance(__result, -std::distance(__first2, __last2)); |
return __result; |
} |
} |
|
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, |
typename _BinaryPredicate> |
_BidirectionalIterator1 |
__find_end(_BidirectionalIterator1 __first1, |
_BidirectionalIterator1 __last1, |
_BidirectionalIterator2 __first2, |
_BidirectionalIterator2 __last2, |
bidirectional_iterator_tag, bidirectional_iterator_tag, |
_BinaryPredicate __comp) |
{ |
// concept requirements |
__glibcxx_function_requires(_BidirectionalIteratorConcept< |
_BidirectionalIterator1>) |
__glibcxx_function_requires(_BidirectionalIteratorConcept< |
_BidirectionalIterator2>) |
|
typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; |
typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; |
|
_RevIterator1 __rlast1(__first1); |
_RevIterator2 __rlast2(__first2); |
_RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, |
_RevIterator2(__last2), __rlast2, |
__comp); |
|
if (__rresult == __rlast1) |
return __last1; |
else |
{ |
_BidirectionalIterator1 __result = __rresult.base(); |
std::advance(__result, -std::distance(__first2, __last2)); |
return __result; |
} |
} |
|
/** |
* @brief Find last matching subsequence in a sequence. |
* @ingroup non_mutating_algorithms |
* @param __first1 Start of range to search. |
* @param __last1 End of range to search. |
* @param __first2 Start of sequence to match. |
* @param __last2 End of sequence to match. |
* @return The last 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. The sub-sequence will be the last such |
* subsequence contained in [__first,__last1). |
* |
* 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> |
inline _ForwardIterator1 |
find_end(_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); |
|
return std::__find_end(__first1, __last1, __first2, __last2, |
std::__iterator_category(__first1), |
std::__iterator_category(__first2)); |
} |
|
/** |
* @brief Find last matching subsequence in a sequence using a predicate. |
* @ingroup non_mutating_algorithms |
* @param __first1 Start of range to search. |
* @param __last1 End of range to search. |
* @param __first2 Start of sequence to match. |
* @param __last2 End of sequence to match. |
* @param __comp The predicate to use. |
* @return The last iterator @c i in the range @p |
* [__first1,__last1-(__last2-__first2)) such that @c |
* predicate(*(i+N), @p (__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 comp as a predicate and returns an |
* iterator to the first element of the sub-sequence, or @p __last1 |
* if the sub-sequence is not found. The sub-sequence will be the |
* last such subsequence contained in [__first,__last1). |
* |
* 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, |
typename _BinaryPredicate> |
inline _ForwardIterator1 |
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
_ForwardIterator2 __first2, _ForwardIterator2 __last2, |
_BinaryPredicate __comp) |
{ |
// 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); |
|
return std::__find_end(__first1, __last1, __first2, __last2, |
std::__iterator_category(__first1), |
std::__iterator_category(__first2), |
__comp); |
} |
|
#if __cplusplus >= 201103L |
/** |
* @brief Checks that a predicate is true for all the elements |
* of a sequence. |
* @ingroup non_mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __pred A predicate. |
* @return True if the check is true, false otherwise. |
* |
* Returns true if @p __pred is true for each element in the range |
* @p [__first,__last), and false otherwise. |
*/ |
template<typename _InputIterator, typename _Predicate> |
inline bool |
all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
{ return __last == std::find_if_not(__first, __last, __pred); } |
|
/** |
* @brief Checks that a predicate is false for all the elements |
* of a sequence. |
* @ingroup non_mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __pred A predicate. |
* @return True if the check is true, false otherwise. |
* |
* Returns true if @p __pred is false for each element in the range |
* @p [__first,__last), and false otherwise. |
*/ |
template<typename _InputIterator, typename _Predicate> |
inline bool |
none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
{ return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); } |
|
/** |
* @brief Checks that a predicate is false for at least an element |
* of a sequence. |
* @ingroup non_mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __pred A predicate. |
* @return True if the check is true, false otherwise. |
* |
* Returns true if an element exists in the range @p |
* [__first,__last) such that @p __pred is true, and false |
* otherwise. |
*/ |
template<typename _InputIterator, typename _Predicate> |
inline bool |
any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) |
{ return !std::none_of(__first, __last, __pred); } |
|
/** |
* @brief Find the first element in a sequence for which a |
* predicate is false. |
* @ingroup non_mutating_algorithms |
* @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 false, or @p __last if no such iterator exists. |
*/ |
template<typename _InputIterator, typename _Predicate> |
inline _InputIterator |
find_if_not(_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_not(__first, __last, __pred); |
} |
|
/** |
* @brief Checks whether the sequence is partitioned. |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __pred A predicate. |
* @return True if the range @p [__first,__last) is partioned by @p __pred, |
* i.e. if all elements that satisfy @p __pred appear before those that |
* do not. |
*/ |
template<typename _InputIterator, typename _Predicate> |
inline bool |
is_partitioned(_InputIterator __first, _InputIterator __last, |
_Predicate __pred) |
{ |
__first = std::find_if_not(__first, __last, __pred); |
return std::none_of(__first, __last, __pred); |
} |
|
/** |
* @brief Find the partition point of a partitioned range. |
* @ingroup mutating_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __pred A predicate. |
* @return An iterator @p mid such that @p all_of(__first, mid, __pred) |
* and @p none_of(mid, __last, __pred) are both true. |
*/ |
template<typename _ForwardIterator, typename _Predicate> |
_ForwardIterator |
partition_point(_ForwardIterator __first, _ForwardIterator __last, |
_Predicate __pred) |
{ |
// concept requirements |
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, |
typename iterator_traits<_ForwardIterator>::value_type>) |
|
// A specific debug-mode test will be necessary... |
__glibcxx_requires_valid_range(__first, __last); |
|
typedef typename iterator_traits<_ForwardIterator>::difference_type |
_DistanceType; |
|
_DistanceType __len = std::distance(__first, __last); |
_DistanceType __half; |
_ForwardIterator __middle; |
|
while (__len > 0) |
{ |
__half = __len >> 1; |
__middle = __first; |
std::advance(__middle, __half); |
if (__pred(*__middle)) |
{ |
__first = __middle; |
++__first; |
__len = __len - __half - 1; |
} |
else |
__len = __half; |
} |
return __first; |
} |
#endif |
|
|
/** |
* @brief Copy a sequence, removing elements of a given value. |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __result An output iterator. |
* @param __value The value to be removed. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Copies each element in the range @p [__first,__last) not equal |
* to @p __value to the range beginning at @p __result. |
* remove_copy() is stable, so the relative order of elements that |
* are copied is unchanged. |
*/ |
template<typename _InputIterator, typename _OutputIterator, typename _Tp> |
_OutputIterator |
remove_copy(_InputIterator __first, _InputIterator __last, |
_OutputIterator __result, const _Tp& __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) |
if (!(*__first == __value)) |
{ |
*__result = *__first; |
++__result; |
} |
return __result; |
} |
|
/** |
* @brief Copy a sequence, removing elements for which a predicate is true. |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __result An output iterator. |
* @param __pred A predicate. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Copies each element in the range @p [__first,__last) for which |
* @p __pred returns false to the range beginning at @p __result. |
* |
* remove_copy_if() is stable, so the relative order of elements that are |
* copied is unchanged. |
*/ |
template<typename _InputIterator, typename _OutputIterator, |
typename _Predicate> |
_OutputIterator |
remove_copy_if(_InputIterator __first, _InputIterator __last, |
_OutputIterator __result, _Predicate __pred) |
{ |
// 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) |
if (!bool(__pred(*__first))) |
{ |
*__result = *__first; |
++__result; |
} |
return __result; |
} |
|
#if __cplusplus >= 201103L |
/** |
* @brief Copy the elements of a sequence for which a predicate is true. |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __result An output iterator. |
* @param __pred A predicate. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Copies each element in the range @p [__first,__last) for which |
* @p __pred returns true to the range beginning at @p __result. |
* |
* copy_if() is stable, so the relative order of elements that are |
* copied is unchanged. |
*/ |
template<typename _InputIterator, typename _OutputIterator, |
typename _Predicate> |
_OutputIterator |
copy_if(_InputIterator __first, _InputIterator __last, |
_OutputIterator __result, _Predicate __pred) |
{ |
// 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) |
if (__pred(*__first)) |
{ |
*__result = *__first; |
++__result; |
} |
return __result; |
} |
|
|
template<typename _InputIterator, typename _Size, typename _OutputIterator> |
_OutputIterator |
__copy_n(_InputIterator __first, _Size __n, |
_OutputIterator __result, input_iterator_tag) |
{ |
if (__n > 0) |
{ |
while (true) |
{ |
*__result = *__first; |
++__result; |
if (--__n > 0) |
++__first; |
else |
break; |
} |
} |
return __result; |
} |
|
template<typename _RandomAccessIterator, typename _Size, |
typename _OutputIterator> |
inline _OutputIterator |
__copy_n(_RandomAccessIterator __first, _Size __n, |
_OutputIterator __result, random_access_iterator_tag) |
{ return std::copy(__first, __first + __n, __result); } |
|
/** |
* @brief Copies the range [first,first+n) into [result,result+n). |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __n The number of elements to copy. |
* @param __result An output iterator. |
* @return result+n. |
* |
* 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). |
*/ |
template<typename _InputIterator, typename _Size, typename _OutputIterator> |
inline _OutputIterator |
copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) |
{ |
// concept requirements |
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
typename iterator_traits<_InputIterator>::value_type>) |
|
return std::__copy_n(__first, __n, __result, |
std::__iterator_category(__first)); |
} |
|
/** |
* @brief Copy the elements of a sequence to separate output sequences |
* depending on the truth value of a predicate. |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __out_true An output iterator. |
* @param __out_false An output iterator. |
* @param __pred A predicate. |
* @return A pair designating the ends of the resulting sequences. |
* |
* Copies each element in the range @p [__first,__last) for which |
* @p __pred returns true to the range beginning at @p out_true |
* and each element for which @p __pred returns false to @p __out_false. |
*/ |
template<typename _InputIterator, typename _OutputIterator1, |
typename _OutputIterator2, typename _Predicate> |
pair<_OutputIterator1, _OutputIterator2> |
partition_copy(_InputIterator __first, _InputIterator __last, |
_OutputIterator1 __out_true, _OutputIterator2 __out_false, |
_Predicate __pred) |
{ |
// concept requirements |
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1, |
typename iterator_traits<_InputIterator>::value_type>) |
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2, |
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) |
if (__pred(*__first)) |
{ |
*__out_true = *__first; |
++__out_true; |
} |
else |
{ |
*__out_false = *__first; |
++__out_false; |
} |
|
return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); |
} |
#endif |
|
/** |
* @brief Remove elements from a sequence. |
* @ingroup mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __value The value to be removed. |
* @return An iterator designating the end of the resulting sequence. |
* |
* All elements equal to @p __value are removed from the range |
* @p [__first,__last). |
* |
* remove() is stable, so the relative order of elements that are |
* not removed is unchanged. |
* |
* Elements between the end of the resulting sequence and @p __last |
* are still present, but their value is unspecified. |
*/ |
template<typename _ForwardIterator, typename _Tp> |
_ForwardIterator |
remove(_ForwardIterator __first, _ForwardIterator __last, |
const _Tp& __value) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
_ForwardIterator>) |
__glibcxx_function_requires(_EqualOpConcept< |
typename iterator_traits<_ForwardIterator>::value_type, _Tp>) |
__glibcxx_requires_valid_range(__first, __last); |
|
__first = _GLIBCXX_STD_A::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; |
} |
|
/** |
* @brief Remove elements from a sequence using a predicate. |
* @ingroup mutating_algorithms |
* @param __first A forward iterator. |
* @param __last A forward iterator. |
* @param __pred A predicate. |
* @return An iterator designating the end of the resulting sequence. |
* |
* All elements for which @p __pred returns true are removed from the range |
* @p [__first,__last). |
* |
* remove_if() is stable, so the relative order of elements that are |
* not removed is unchanged. |
* |
* Elements between the end of the resulting sequence and @p __last |
* are still present, but their value is unspecified. |
*/ |
template<typename _ForwardIterator, typename _Predicate> |
_ForwardIterator |
remove_if(_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); |
|
__first = _GLIBCXX_STD_A::find_if(__first, __last, __pred); |
if(__first == __last) |
return __first; |
_ForwardIterator __result = __first; |
++__first; |
for(; __first != __last; ++__first) |
if(!bool(__pred(*__first))) |
{ |
*__result = _GLIBCXX_MOVE(*__first); |
++__result; |
} |
return __result; |
} |
|
/** |
* @brief Remove consecutive duplicate values from a sequence. |
* @ingroup mutating_algorithms |
* @param __first A forward iterator. |
* @param __last A forward iterator. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Removes all but the first element from each group of consecutive |
* values that compare equal. |
* unique() is stable, so the relative order of elements that are |
* not removed is unchanged. |
* Elements between the end of the resulting sequence and @p __last |
* are still present, but their value is unspecified. |
*/ |
template<typename _ForwardIterator> |
_ForwardIterator |
unique(_ForwardIterator __first, _ForwardIterator __last) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
_ForwardIterator>) |
__glibcxx_function_requires(_EqualityComparableConcept< |
typename iterator_traits<_ForwardIterator>::value_type>) |
__glibcxx_requires_valid_range(__first, __last); |
|
// Skip the beginning, if already unique. |
__first = _GLIBCXX_STD_A::adjacent_find(__first, __last); |
if (__first == __last) |
return __last; |
|
// Do the real copy work. |
_ForwardIterator __dest = __first; |
++__first; |
while (++__first != __last) |
if (!(*__dest == *__first)) |
*++__dest = _GLIBCXX_MOVE(*__first); |
return ++__dest; |
} |
|
/** |
* @brief Remove consecutive values from a sequence using a predicate. |
* @ingroup mutating_algorithms |
* @param __first A forward iterator. |
* @param __last A forward iterator. |
* @param __binary_pred A binary predicate. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Removes all but the first element from each group of consecutive |
* values for which @p __binary_pred returns true. |
* unique() is stable, so the relative order of elements that are |
* not removed is unchanged. |
* Elements between the end of the resulting sequence and @p __last |
* are still present, but their value is unspecified. |
*/ |
template<typename _ForwardIterator, typename _BinaryPredicate> |
_ForwardIterator |
unique(_ForwardIterator __first, _ForwardIterator __last, |
_BinaryPredicate __binary_pred) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_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); |
|
// Skip the beginning, if already unique. |
__first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred); |
if (__first == __last) |
return __last; |
|
// Do the real copy work. |
_ForwardIterator __dest = __first; |
++__first; |
while (++__first != __last) |
if (!bool(__binary_pred(*__dest, *__first))) |
*++__dest = _GLIBCXX_MOVE(*__first); |
return ++__dest; |
} |
|
/** |
* This is an uglified unique_copy(_InputIterator, _InputIterator, |
* _OutputIterator) |
* overloaded for forward iterators and output iterator as result. |
*/ |
template<typename _ForwardIterator, typename _OutputIterator> |
_OutputIterator |
__unique_copy(_ForwardIterator __first, _ForwardIterator __last, |
_OutputIterator __result, |
forward_iterator_tag, output_iterator_tag) |
{ |
// concept requirements -- taken care of in dispatching function |
_ForwardIterator __next = __first; |
*__result = *__first; |
while (++__next != __last) |
if (!(*__first == *__next)) |
{ |
__first = __next; |
*++__result = *__first; |
} |
return ++__result; |
} |
|
/** |
* This is an uglified unique_copy(_InputIterator, _InputIterator, |
* _OutputIterator) |
* overloaded for input iterators and output iterator as result. |
*/ |
template<typename _InputIterator, typename _OutputIterator> |
_OutputIterator |
__unique_copy(_InputIterator __first, _InputIterator __last, |
_OutputIterator __result, |
input_iterator_tag, output_iterator_tag) |
{ |
// concept requirements -- taken care of in dispatching function |
typename iterator_traits<_InputIterator>::value_type __value = *__first; |
*__result = __value; |
while (++__first != __last) |
if (!(__value == *__first)) |
{ |
__value = *__first; |
*++__result = __value; |
} |
return ++__result; |
} |
|
/** |
* This is an uglified unique_copy(_InputIterator, _InputIterator, |
* _OutputIterator) |
* overloaded for input iterators and forward iterator as result. |
*/ |
template<typename _InputIterator, typename _ForwardIterator> |
_ForwardIterator |
__unique_copy(_InputIterator __first, _InputIterator __last, |
_ForwardIterator __result, |
input_iterator_tag, forward_iterator_tag) |
{ |
// concept requirements -- taken care of in dispatching function |
*__result = *__first; |
while (++__first != __last) |
if (!(*__result == *__first)) |
*++__result = *__first; |
return ++__result; |
} |
|
/** |
* This is an uglified |
* unique_copy(_InputIterator, _InputIterator, _OutputIterator, |
* _BinaryPredicate) |
* overloaded for forward iterators and output iterator as result. |
*/ |
template<typename _ForwardIterator, typename _OutputIterator, |
typename _BinaryPredicate> |
_OutputIterator |
__unique_copy(_ForwardIterator __first, _ForwardIterator __last, |
_OutputIterator __result, _BinaryPredicate __binary_pred, |
forward_iterator_tag, output_iterator_tag) |
{ |
// concept requirements -- iterators already checked |
__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, |
typename iterator_traits<_ForwardIterator>::value_type, |
typename iterator_traits<_ForwardIterator>::value_type>) |
|
_ForwardIterator __next = __first; |
*__result = *__first; |
while (++__next != __last) |
if (!bool(__binary_pred(*__first, *__next))) |
{ |
__first = __next; |
*++__result = *__first; |
} |
return ++__result; |
} |
|
/** |
* This is an uglified |
* unique_copy(_InputIterator, _InputIterator, _OutputIterator, |
* _BinaryPredicate) |
* overloaded for input iterators and output iterator as result. |
*/ |
template<typename _InputIterator, typename _OutputIterator, |
typename _BinaryPredicate> |
_OutputIterator |
__unique_copy(_InputIterator __first, _InputIterator __last, |
_OutputIterator __result, _BinaryPredicate __binary_pred, |
input_iterator_tag, output_iterator_tag) |
{ |
// concept requirements -- iterators already checked |
__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, |
typename iterator_traits<_InputIterator>::value_type, |
typename iterator_traits<_InputIterator>::value_type>) |
|
typename iterator_traits<_InputIterator>::value_type __value = *__first; |
*__result = __value; |
while (++__first != __last) |
if (!bool(__binary_pred(__value, *__first))) |
{ |
__value = *__first; |
*++__result = __value; |
} |
return ++__result; |
} |
|
/** |
* This is an uglified |
* unique_copy(_InputIterator, _InputIterator, _OutputIterator, |
* _BinaryPredicate) |
* overloaded for input iterators and forward iterator as result. |
*/ |
template<typename _InputIterator, typename _ForwardIterator, |
typename _BinaryPredicate> |
_ForwardIterator |
__unique_copy(_InputIterator __first, _InputIterator __last, |
_ForwardIterator __result, _BinaryPredicate __binary_pred, |
input_iterator_tag, forward_iterator_tag) |
{ |
// concept requirements -- iterators already checked |
__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, |
typename iterator_traits<_ForwardIterator>::value_type, |
typename iterator_traits<_InputIterator>::value_type>) |
|
*__result = *__first; |
while (++__first != __last) |
if (!bool(__binary_pred(*__result, *__first))) |
*++__result = *__first; |
return ++__result; |
} |
|
/** |
* This is an uglified reverse(_BidirectionalIterator, |
* _BidirectionalIterator) |
* overloaded for bidirectional iterators. |
*/ |
template<typename _BidirectionalIterator> |
void |
__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, |
bidirectional_iterator_tag) |
{ |
while (true) |
if (__first == __last || __first == --__last) |
return; |
else |
{ |
std::iter_swap(__first, __last); |
++__first; |
} |
} |
|
/** |
* This is an uglified reverse(_BidirectionalIterator, |
* _BidirectionalIterator) |
* overloaded for random access iterators. |
*/ |
template<typename _RandomAccessIterator> |
void |
__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, |
random_access_iterator_tag) |
{ |
if (__first == __last) |
return; |
--__last; |
while (__first < __last) |
{ |
std::iter_swap(__first, __last); |
++__first; |
--__last; |
} |
} |
|
/** |
* @brief Reverse a sequence. |
* @ingroup mutating_algorithms |
* @param __first A bidirectional iterator. |
* @param __last A bidirectional iterator. |
* @return reverse() returns no value. |
* |
* Reverses the order of the elements in the range @p [__first,__last), |
* so that the first element becomes the last etc. |
* For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse() |
* swaps @p *(__first+i) and @p *(__last-(i+1)) |
*/ |
template<typename _BidirectionalIterator> |
inline void |
reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< |
_BidirectionalIterator>) |
__glibcxx_requires_valid_range(__first, __last); |
std::__reverse(__first, __last, std::__iterator_category(__first)); |
} |
|
/** |
* @brief Copy a sequence, reversing its elements. |
* @ingroup mutating_algorithms |
* @param __first A bidirectional iterator. |
* @param __last A bidirectional iterator. |
* @param __result An output iterator. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Copies the elements in the range @p [__first,__last) to the |
* range @p [__result,__result+(__last-__first)) such that the |
* order of the elements is reversed. For every @c i such that @p |
* 0<=i<=(__last-__first), @p reverse_copy() performs the |
* assignment @p *(__result+(__last-__first)-1-i) = *(__first+i). |
* The ranges @p [__first,__last) and @p |
* [__result,__result+(__last-__first)) must not overlap. |
*/ |
template<typename _BidirectionalIterator, typename _OutputIterator> |
_OutputIterator |
reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, |
_OutputIterator __result) |
{ |
// concept requirements |
__glibcxx_function_requires(_BidirectionalIteratorConcept< |
_BidirectionalIterator>) |
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
typename iterator_traits<_BidirectionalIterator>::value_type>) |
__glibcxx_requires_valid_range(__first, __last); |
|
while (__first != __last) |
{ |
--__last; |
*__result = *__last; |
++__result; |
} |
return __result; |
} |
|
/** |
* This is a helper function for the rotate algorithm specialized on RAIs. |
* It returns the greatest common divisor of two integer values. |
*/ |
template<typename _EuclideanRingElement> |
_EuclideanRingElement |
__gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) |
{ |
while (__n != 0) |
{ |
_EuclideanRingElement __t = __m % __n; |
__m = __n; |
__n = __t; |
} |
return __m; |
} |
|
/// This is a helper function for the rotate algorithm. |
template<typename _ForwardIterator> |
void |
__rotate(_ForwardIterator __first, |
_ForwardIterator __middle, |
_ForwardIterator __last, |
forward_iterator_tag) |
{ |
if (__first == __middle || __last == __middle) |
return; |
|
_ForwardIterator __first2 = __middle; |
do |
{ |
std::iter_swap(__first, __first2); |
++__first; |
++__first2; |
if (__first == __middle) |
__middle = __first2; |
} |
while (__first2 != __last); |
|
__first2 = __middle; |
|
while (__first2 != __last) |
{ |
std::iter_swap(__first, __first2); |
++__first; |
++__first2; |
if (__first == __middle) |
__middle = __first2; |
else if (__first2 == __last) |
__first2 = __middle; |
} |
} |
|
/// This is a helper function for the rotate algorithm. |
template<typename _BidirectionalIterator> |
void |
__rotate(_BidirectionalIterator __first, |
_BidirectionalIterator __middle, |
_BidirectionalIterator __last, |
bidirectional_iterator_tag) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< |
_BidirectionalIterator>) |
|
if (__first == __middle || __last == __middle) |
return; |
|
std::__reverse(__first, __middle, bidirectional_iterator_tag()); |
std::__reverse(__middle, __last, bidirectional_iterator_tag()); |
|
while (__first != __middle && __middle != __last) |
{ |
std::iter_swap(__first, --__last); |
++__first; |
} |
|
if (__first == __middle) |
std::__reverse(__middle, __last, bidirectional_iterator_tag()); |
else |
std::__reverse(__first, __middle, bidirectional_iterator_tag()); |
} |
|
/// This is a helper function for the rotate algorithm. |
template<typename _RandomAccessIterator> |
void |
__rotate(_RandomAccessIterator __first, |
_RandomAccessIterator __middle, |
_RandomAccessIterator __last, |
random_access_iterator_tag) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
_RandomAccessIterator>) |
|
if (__first == __middle || __last == __middle) |
return; |
|
typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
_Distance; |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_ValueType; |
|
_Distance __n = __last - __first; |
_Distance __k = __middle - __first; |
|
if (__k == __n - __k) |
{ |
std::swap_ranges(__first, __middle, __middle); |
return; |
} |
|
_RandomAccessIterator __p = __first; |
|
for (;;) |
{ |
if (__k < __n - __k) |
{ |
if (__is_pod(_ValueType) && __k == 1) |
{ |
_ValueType __t = _GLIBCXX_MOVE(*__p); |
_GLIBCXX_MOVE3(__p + 1, __p + __n, __p); |
*(__p + __n - 1) = _GLIBCXX_MOVE(__t); |
return; |
} |
_RandomAccessIterator __q = __p + __k; |
for (_Distance __i = 0; __i < __n - __k; ++ __i) |
{ |
std::iter_swap(__p, __q); |
++__p; |
++__q; |
} |
__n %= __k; |
if (__n == 0) |
return; |
std::swap(__n, __k); |
__k = __n - __k; |
} |
else |
{ |
__k = __n - __k; |
if (__is_pod(_ValueType) && __k == 1) |
{ |
_ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); |
_GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); |
*__p = _GLIBCXX_MOVE(__t); |
return; |
} |
_RandomAccessIterator __q = __p + __n; |
__p = __q - __k; |
for (_Distance __i = 0; __i < __n - __k; ++ __i) |
{ |
--__p; |
--__q; |
std::iter_swap(__p, __q); |
} |
__n %= __k; |
if (__n == 0) |
return; |
std::swap(__n, __k); |
} |
} |
} |
|
/** |
* @brief Rotate the elements of a sequence. |
* @ingroup mutating_algorithms |
* @param __first A forward iterator. |
* @param __middle A forward iterator. |
* @param __last A forward iterator. |
* @return Nothing. |
* |
* Rotates the elements of the range @p [__first,__last) by |
* @p (__middle - __first) positions so that the element at @p __middle |
* is moved to @p __first, the element at @p __middle+1 is moved to |
* @p __first+1 and so on for each element in the range |
* @p [__first,__last). |
* |
* This effectively swaps the ranges @p [__first,__middle) and |
* @p [__middle,__last). |
* |
* Performs |
* @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n) |
* for each @p n in the range @p [0,__last-__first). |
*/ |
template<typename _ForwardIterator> |
inline void |
rotate(_ForwardIterator __first, _ForwardIterator __middle, |
_ForwardIterator __last) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept< |
_ForwardIterator>) |
__glibcxx_requires_valid_range(__first, __middle); |
__glibcxx_requires_valid_range(__middle, __last); |
|
typedef typename iterator_traits<_ForwardIterator>::iterator_category |
_IterType; |
std::__rotate(__first, __middle, __last, _IterType()); |
} |
|
/** |
* @brief Copy a sequence, rotating its elements. |
* @ingroup mutating_algorithms |
* @param __first A forward iterator. |
* @param __middle A forward iterator. |
* @param __last A forward iterator. |
* @param __result An output iterator. |
* @return An iterator designating the end of the resulting sequence. |
* |
* Copies the elements of the range @p [__first,__last) to the |
* range beginning at @result, rotating the copied elements by |
* @p (__middle-__first) positions so that the element at @p __middle |
* is moved to @p __result, the element at @p __middle+1 is moved |
* to @p __result+1 and so on for each element in the range @p |
* [__first,__last). |
* |
* Performs |
* @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n) |
* for each @p n in the range @p [0,__last-__first). |
*/ |
template<typename _ForwardIterator, typename _OutputIterator> |
_OutputIterator |
rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, |
_ForwardIterator __last, _OutputIterator __result) |
{ |
// concept requirements |
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, |
typename iterator_traits<_ForwardIterator>::value_type>) |
__glibcxx_requires_valid_range(__first, __middle); |
__glibcxx_requires_valid_range(__middle, __last); |
|
return std::copy(__first, __middle, |
std::copy(__middle, __last, __result)); |
} |
|
/// This is a helper function... |
template<typename _ForwardIterator, typename _Predicate> |
_ForwardIterator |
__partition(_ForwardIterator __first, _ForwardIterator __last, |
_Predicate __pred, forward_iterator_tag) |
{ |
if (__first == __last) |
return __first; |
|
while (__pred(*__first)) |
if (++__first == __last) |
return __first; |
|
_ForwardIterator __next = __first; |
|
while (++__next != __last) |
if (__pred(*__next)) |
{ |
std::iter_swap(__first, __next); |
++__first; |
} |
|
return __first; |
} |
|
/// This is a helper function... |
template<typename _BidirectionalIterator, typename _Predicate> |
_BidirectionalIterator |
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, |
_Predicate __pred, bidirectional_iterator_tag) |
{ |
while (true) |
{ |
while (true) |
if (__first == __last) |
return __first; |
else if (__pred(*__first)) |
++__first; |
else |
break; |
--__last; |
while (true) |
if (__first == __last) |
return __first; |
else if (!bool(__pred(*__last))) |
--__last; |
else |
break; |
std::iter_swap(__first, __last); |
++__first; |
} |
} |
|
// partition |
|
/// This is a helper function... |
/// Requires __len != 0 and !__pred(*__first), |
/// same as __stable_partition_adaptive. |
template<typename _ForwardIterator, typename _Predicate, typename _Distance> |
_ForwardIterator |
__inplace_stable_partition(_ForwardIterator __first, |
_Predicate __pred, _Distance __len) |
{ |
if (__len == 1) |
return __first; |
_ForwardIterator __middle = __first; |
std::advance(__middle, __len / 2); |
_ForwardIterator __left_split = |
std::__inplace_stable_partition(__first, __pred, __len / 2); |
// Advance past true-predicate values to satisfy this |
// function's preconditions. |
_Distance __right_len = __len - __len / 2; |
_ForwardIterator __right_split = |
std::__find_if_not_n(__middle, __right_len, __pred); |
if (__right_len) |
__right_split = std::__inplace_stable_partition(__middle, |
__pred, |
__right_len); |
std::rotate(__left_split, __middle, __right_split); |
std::advance(__left_split, std::distance(__middle, __right_split)); |
return __left_split; |
} |
|
/// This is a helper function... |
/// Requires __first != __last and !__pred(*__first) |
/// and __len == distance(__first, __last). |
/// |
/// !__pred(*__first) allows us to guarantee that we don't |
/// move-assign an element onto itself. |
template<typename _ForwardIterator, typename _Pointer, typename _Predicate, |
typename _Distance> |
_ForwardIterator |
__stable_partition_adaptive(_ForwardIterator __first, |
_ForwardIterator __last, |
_Predicate __pred, _Distance __len, |
_Pointer __buffer, |
_Distance __buffer_size) |
{ |
if (__len <= __buffer_size) |
{ |
_ForwardIterator __result1 = __first; |
_Pointer __result2 = __buffer; |
// The precondition guarantees that !__pred(*__first), so |
// move that element to the buffer before starting the loop. |
// This ensures that we only call __pred once per element. |
*__result2 = _GLIBCXX_MOVE(*__first); |
++__result2; |
++__first; |
for (; __first != __last; ++__first) |
if (__pred(*__first)) |
{ |
*__result1 = _GLIBCXX_MOVE(*__first); |
++__result1; |
} |
else |
{ |
*__result2 = _GLIBCXX_MOVE(*__first); |
++__result2; |
} |
_GLIBCXX_MOVE3(__buffer, __result2, __result1); |
return __result1; |
} |
else |
{ |
_ForwardIterator __middle = __first; |
std::advance(__middle, __len / 2); |
_ForwardIterator __left_split = |
std::__stable_partition_adaptive(__first, __middle, __pred, |
__len / 2, __buffer, |
__buffer_size); |
// Advance past true-predicate values to satisfy this |
// function's preconditions. |
_Distance __right_len = __len - __len / 2; |
_ForwardIterator __right_split = |
std::__find_if_not_n(__middle, __right_len, __pred); |
if (__right_len) |
__right_split = |
std::__stable_partition_adaptive(__right_split, __last, __pred, |
__right_len, |
__buffer, __buffer_size); |
std::rotate(__left_split, __middle, __right_split); |
std::advance(__left_split, std::distance(__middle, __right_split)); |
return __left_split; |
} |
} |
|
/** |
* @brief Move elements for which a predicate is true to the beginning |
* of a sequence, preserving relative ordering. |
* @ingroup mutating_algorithms |
* @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). |
* |
* Performs the same function as @p partition() with the additional |
* guarantee that the relative ordering of elements in each group is |
* preserved, so any two elements @p x and @p y in the range |
* @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same |
* relative ordering after calling @p stable_partition(). |
*/ |
template<typename _ForwardIterator, typename _Predicate> |
_ForwardIterator |
stable_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); |
|
__first = std::__find_if_not(__first, __last, __pred); |
|
if (__first == __last) |
return __first; |
else |
{ |
typedef typename iterator_traits<_ForwardIterator>::value_type |
_ValueType; |
typedef typename iterator_traits<_ForwardIterator>::difference_type |
_DistanceType; |
|
_Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, |
__last); |
if (__buf.size() > 0) |
return |
std::__stable_partition_adaptive(__first, __last, __pred, |
_DistanceType(__buf.requested_size()), |
__buf.begin(), |
_DistanceType(__buf.size())); |
else |
return |
std::__inplace_stable_partition(__first, __pred, |
_DistanceType(__buf.requested_size())); |
} |
} |
|
/// This is a helper function for the sort routines. |
template<typename _RandomAccessIterator> |
void |
__heap_select(_RandomAccessIterator __first, |
_RandomAccessIterator __middle, |
_RandomAccessIterator __last) |
{ |
std::make_heap(__first, __middle); |
for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) |
if (*__i < *__first) |
std::__pop_heap(__first, __middle, __i); |
} |
|
/// 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) |
{ |
std::make_heap(__first, __middle, __comp); |
for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) |
if (__comp(*__i, *__first)) |
std::__pop_heap(__first, __middle, __i, __comp); |
} |
|
// partial_sort |
|
/** |
* @brief Copy the smallest elements of a sequence. |
* @ingroup sorting_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __result_first A random-access iterator. |
* @param __result_last Another random-access iterator. |
* @return An iterator indicating the end of the resulting sequence. |
* |
* Copies and sorts the smallest N values from the range @p [__first,__last) |
* to the range beginning at @p __result_first, where the number of |
* elements to be copied, @p N, is the smaller of @p (__last-__first) and |
* @p (__result_last-__result_first). |
* After the sort if @e i and @e j are iterators in the range |
* @p [__result_first,__result_first+N) such that i precedes j then |
* *j<*i is false. |
* The value returned is @p __result_first+N. |
*/ |
template<typename _InputIterator, typename _RandomAccessIterator> |
_RandomAccessIterator |
partial_sort_copy(_InputIterator __first, _InputIterator __last, |
_RandomAccessIterator __result_first, |
_RandomAccessIterator __result_last) |
{ |
typedef typename iterator_traits<_InputIterator>::value_type |
_InputValueType; |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_OutputValueType; |
typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
_DistanceType; |
|
// concept requirements |
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
__glibcxx_function_requires(_ConvertibleConcept<_InputValueType, |
_OutputValueType>) |
__glibcxx_function_requires(_LessThanOpConcept<_InputValueType, |
_OutputValueType>) |
__glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) |
__glibcxx_requires_valid_range(__first, __last); |
__glibcxx_requires_valid_range(__result_first, __result_last); |
|
if (__result_first == __result_last) |
return __result_last; |
_RandomAccessIterator __result_real_last = __result_first; |
while(__first != __last && __result_real_last != __result_last) |
{ |
*__result_real_last = *__first; |
++__result_real_last; |
++__first; |
} |
std::make_heap(__result_first, __result_real_last); |
while (__first != __last) |
{ |
if (*__first < *__result_first) |
std::__adjust_heap(__result_first, _DistanceType(0), |
_DistanceType(__result_real_last |
- __result_first), |
_InputValueType(*__first)); |
++__first; |
} |
std::sort_heap(__result_first, __result_real_last); |
return __result_real_last; |
} |
|
/** |
* @brief Copy the smallest elements of a sequence using a predicate for |
* comparison. |
* @ingroup sorting_algorithms |
* @param __first An input iterator. |
* @param __last Another input iterator. |
* @param __result_first A random-access iterator. |
* @param __result_last Another random-access iterator. |
* @param __comp A comparison functor. |
* @return An iterator indicating the end of the resulting sequence. |
* |
* Copies and sorts the smallest N values from the range @p [__first,__last) |
* to the range beginning at @p result_first, where the number of |
* elements to be copied, @p N, is the smaller of @p (__last-__first) and |
* @p (__result_last-__result_first). |
* After the sort if @e i and @e j are iterators in the range |
* @p [__result_first,__result_first+N) such that i precedes j then |
* @p __comp(*j,*i) is false. |
* The value returned is @p __result_first+N. |
*/ |
template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare> |
_RandomAccessIterator |
partial_sort_copy(_InputIterator __first, _InputIterator __last, |
_RandomAccessIterator __result_first, |
_RandomAccessIterator __result_last, |
_Compare __comp) |
{ |
typedef typename iterator_traits<_InputIterator>::value_type |
_InputValueType; |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_OutputValueType; |
typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
_DistanceType; |
|
// concept requirements |
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) |
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
_RandomAccessIterator>) |
__glibcxx_function_requires(_ConvertibleConcept<_InputValueType, |
_OutputValueType>) |
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare, |
_InputValueType, _OutputValueType>) |
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare, |
_OutputValueType, _OutputValueType>) |
__glibcxx_requires_valid_range(__first, __last); |
__glibcxx_requires_valid_range(__result_first, __result_last); |
|
if (__result_first == __result_last) |
return __result_last; |
_RandomAccessIterator __result_real_last = __result_first; |
while(__first != __last && __result_real_last != __result_last) |
{ |
*__result_real_last = *__first; |
++__result_real_last; |
++__first; |
} |
std::make_heap(__result_first, __result_real_last, __comp); |
while (__first != __last) |
{ |
if (__comp(*__first, *__result_first)) |
std::__adjust_heap(__result_first, _DistanceType(0), |
_DistanceType(__result_real_last |
- __result_first), |
_InputValueType(*__first), |
__comp); |
++__first; |
} |
std::sort_heap(__result_first, __result_real_last, __comp); |
return __result_real_last; |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator> |
void |
__unguarded_linear_insert(_RandomAccessIterator __last) |
{ |
typename iterator_traits<_RandomAccessIterator>::value_type |
__val = _GLIBCXX_MOVE(*__last); |
_RandomAccessIterator __next = __last; |
--__next; |
while (__val < *__next) |
{ |
*__last = _GLIBCXX_MOVE(*__next); |
__last = __next; |
--__next; |
} |
*__last = _GLIBCXX_MOVE(__val); |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator, typename _Compare> |
void |
__unguarded_linear_insert(_RandomAccessIterator __last, |
_Compare __comp) |
{ |
typename iterator_traits<_RandomAccessIterator>::value_type |
__val = _GLIBCXX_MOVE(*__last); |
_RandomAccessIterator __next = __last; |
--__next; |
while (__comp(__val, *__next)) |
{ |
*__last = _GLIBCXX_MOVE(*__next); |
__last = __next; |
--__next; |
} |
*__last = _GLIBCXX_MOVE(__val); |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator> |
void |
__insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last) |
{ |
if (__first == __last) |
return; |
|
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) |
{ |
if (*__i < *__first) |
{ |
typename iterator_traits<_RandomAccessIterator>::value_type |
__val = _GLIBCXX_MOVE(*__i); |
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); |
*__first = _GLIBCXX_MOVE(__val); |
} |
else |
std::__unguarded_linear_insert(__i); |
} |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator, typename _Compare> |
void |
__insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last, _Compare __comp) |
{ |
if (__first == __last) return; |
|
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) |
{ |
if (__comp(*__i, *__first)) |
{ |
typename iterator_traits<_RandomAccessIterator>::value_type |
__val = _GLIBCXX_MOVE(*__i); |
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); |
*__first = _GLIBCXX_MOVE(__val); |
} |
else |
std::__unguarded_linear_insert(__i, __comp); |
} |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator> |
inline void |
__unguarded_insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last) |
{ |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_ValueType; |
|
for (_RandomAccessIterator __i = __first; __i != __last; ++__i) |
std::__unguarded_linear_insert(__i); |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator, typename _Compare> |
inline void |
__unguarded_insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last, _Compare __comp) |
{ |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_ValueType; |
|
for (_RandomAccessIterator __i = __first; __i != __last; ++__i) |
std::__unguarded_linear_insert(__i, __comp); |
} |
|
/** |
* @doctodo |
* This controls some aspect of the sort routines. |
*/ |
enum { _S_threshold = 16 }; |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator> |
void |
__final_insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last) |
{ |
if (__last - __first > int(_S_threshold)) |
{ |
std::__insertion_sort(__first, __first + int(_S_threshold)); |
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last); |
} |
else |
std::__insertion_sort(__first, __last); |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator, typename _Compare> |
void |
__final_insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last, _Compare __comp) |
{ |
if (__last - __first > int(_S_threshold)) |
{ |
std::__insertion_sort(__first, __first + int(_S_threshold), __comp); |
std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, |
__comp); |
} |
else |
std::__insertion_sort(__first, __last, __comp); |
} |
|
/// This is a helper function... |
template<typename _RandomAccessIterator, typename _Tp> |
_RandomAccessIterator |
__unguarded_partition(_RandomAccessIterator __first, |
_RandomAccessIterator __last, const _Tp& __pivot) |
{ |
while (true) |
{ |
while (*__first < __pivot) |
++__first; |
--__last; |
while (__pivot < *__last) |
--__last; |
if (!(__first < __last)) |
return __first; |
std::iter_swap(__first, __last); |
++__first; |
} |
} |
|
/// This is a helper function... |
template<typename _RandomAccessIterator, typename _Tp, typename _Compare> |
_RandomAccessIterator |
__unguarded_partition(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
const _Tp& __pivot, _Compare __comp) |
{ |
while (true) |
{ |
while (__comp(*__first, __pivot)) |
++__first; |
--__last; |
while (__comp(__pivot, *__last)) |
--__last; |
if (!(__first < __last)) |
return __first; |
std::iter_swap(__first, __last); |
++__first; |
} |
} |
|
/// This is a helper function... |
template<typename _RandomAccessIterator> |
inline _RandomAccessIterator |
__unguarded_partition_pivot(_RandomAccessIterator __first, |
_RandomAccessIterator __last) |
{ |
_RandomAccessIterator __mid = __first + (__last - __first) / 2; |
std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2)); |
return std::__unguarded_partition(__first + 1, __last, *__first); |
} |
|
|
/// This is a helper function... |
template<typename _RandomAccessIterator, typename _Compare> |
inline _RandomAccessIterator |
__unguarded_partition_pivot(_RandomAccessIterator __first, |
_RandomAccessIterator __last, _Compare __comp) |
{ |
_RandomAccessIterator __mid = __first + (__last - __first) / 2; |
std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2), |
__comp); |
return std::__unguarded_partition(__first + 1, __last, *__first, __comp); |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator, typename _Size> |
void |
__introsort_loop(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Size __depth_limit) |
{ |
while (__last - __first > int(_S_threshold)) |
{ |
if (__depth_limit == 0) |
{ |
_GLIBCXX_STD_A::partial_sort(__first, __last, __last); |
return; |
} |
--__depth_limit; |
_RandomAccessIterator __cut = |
std::__unguarded_partition_pivot(__first, __last); |
std::__introsort_loop(__cut, __last, __depth_limit); |
__last = __cut; |
} |
} |
|
/// This is a helper function for the sort routine. |
template<typename _RandomAccessIterator, typename _Size, typename _Compare> |
void |
__introsort_loop(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Size __depth_limit, _Compare __comp) |
{ |
while (__last - __first > int(_S_threshold)) |
{ |
if (__depth_limit == 0) |
{ |
_GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp); |
return; |
} |
--__depth_limit; |
_RandomAccessIterator __cut = |
std::__unguarded_partition_pivot(__first, __last, __comp); |
std::__introsort_loop(__cut, __last, __depth_limit, __comp); |
__last = __cut; |
} |
} |
|
// sort |
|
template<typename _RandomAccessIterator, typename _Size> |
void |
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, |
_RandomAccessIterator __last, _Size __depth_limit) |
{ |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_ValueType; |
|
while (__last - __first > 3) |
{ |
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; |
} |
--__depth_limit; |
_RandomAccessIterator __cut = |
std::__unguarded_partition_pivot(__first, __last); |
if (__cut <= __nth) |
__first = __cut; |
else |
__last = __cut; |
} |
std::__insertion_sort(__first, __last); |
} |
|
template<typename _RandomAccessIterator, typename _Size, typename _Compare> |
void |
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, |
_RandomAccessIterator __last, _Size __depth_limit, |
_Compare __comp) |
{ |
typedef typename iterator_traits<_RandomAccessIterator>::value_type |
_ValueType; |
|
while (__last - __first > 3) |
{ |
if (__depth_limit == 0) |
{ |
std::__heap_select(__first, __nth + 1, __last, __comp); |
// Place the nth largest element in its final position. |
std::iter_swap(__first, __nth); |
return; |
} |
--__depth_limit; |
_RandomAccessIterator __cut = |
std::__unguarded_partition_pivot(__first, __last, __comp); |
if (__cut <= __nth) |
__first = __cut; |
else |
__last = __cut; |
} |
std::__insertion_sort(__first, __last, __comp); |
} |
|
// nth_element |
|
// lower_bound moved to stl_algobase.h |
|
/** |
* @brief Finds the first position in which @p __val could be inserted |
* without changing the ordering. |
* @ingroup binary_search_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @param __comp A functor to use for comparisons. |
* @return An iterator pointing to the first element <em>not less |
* than</em> @p __val, or end() if every element is less |
* than @p __val. |
* @ingroup binary_search_algorithms |
* |
* The comparison function should have the same effects on ordering as |
* the function used for the initial sort. |
*/ |
template<typename _ForwardIterator, typename _Tp, typename _Compare> |
_ForwardIterator |
lower_bound(_ForwardIterator __first, _ForwardIterator __last, |
const _Tp& __val, _Compare __comp) |
{ |
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(_BinaryPredicateConcept<_Compare, |
_ValueType, _Tp>) |
__glibcxx_requires_partitioned_lower_pred(__first, __last, |
__val, __comp); |
|
_DistanceType __len = std::distance(__first, __last); |
|
while (__len > 0) |
{ |
_DistanceType __half = __len >> 1; |
_ForwardIterator __middle = __first; |
std::advance(__middle, __half); |
if (__comp(*__middle, __val)) |
{ |
__first = __middle; |
++__first; |
__len = __len - __half - 1; |
} |
else |
__len = __half; |
} |
return __first; |
} |
|
/** |
* @brief Finds the last position in which @p __val could be inserted |
* without changing the ordering. |
* @ingroup binary_search_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @return An iterator pointing to the first element greater than @p __val, |
* or end() if no elements are greater than @p __val. |
* @ingroup binary_search_algorithms |
*/ |
template<typename _ForwardIterator, typename _Tp> |
_ForwardIterator |
upper_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<_Tp, _ValueType>) |
__glibcxx_requires_partitioned_upper(__first, __last, __val); |
|
_DistanceType __len = std::distance(__first, __last); |
|
while (__len > 0) |
{ |
_DistanceType __half = __len >> 1; |
_ForwardIterator __middle = __first; |
std::advance(__middle, __half); |
if (__val < *__middle) |
__len = __half; |
else |
{ |
__first = __middle; |
++__first; |
__len = __len - __half - 1; |
} |
} |
return __first; |
} |
|
/** |
* @brief Finds the last position in which @p __val could be inserted |
* without changing the ordering. |
* @ingroup binary_search_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @param __comp A functor to use for comparisons. |
* @return An iterator pointing to the first element greater than @p __val, |
* or end() if no elements are greater than @p __val. |
* @ingroup binary_search_algorithms |
* |
* The comparison function should have the same effects on ordering as |
* the function used for the initial sort. |
*/ |
template<typename _ForwardIterator, typename _Tp, typename _Compare> |
_ForwardIterator |
upper_bound(_ForwardIterator __first, _ForwardIterator __last, |
const _Tp& __val, _Compare __comp) |
{ |
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(_BinaryPredicateConcept<_Compare, |
_Tp, _ValueType>) |
__glibcxx_requires_partitioned_upper_pred(__first, __last, |
__val, __comp); |
|
_DistanceType __len = std::distance(__first, __last); |
|
while (__len > 0) |
{ |
_DistanceType __half = __len >> 1; |
_ForwardIterator __middle = __first; |
std::advance(__middle, __half); |
if (__comp(__val, *__middle)) |
__len = __half; |
else |
{ |
__first = __middle; |
++__first; |
__len = __len - __half - 1; |
} |
} |
return __first; |
} |
|
/** |
* @brief Finds the largest subrange in which @p __val could be inserted |
* at any place in it without changing the ordering. |
* @ingroup binary_search_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @return An pair of iterators defining the subrange. |
* @ingroup binary_search_algorithms |
* |
* This is equivalent to |
* @code |
* std::make_pair(lower_bound(__first, __last, __val), |
* upper_bound(__first, __last, __val)) |
* @endcode |
* but does not actually call those functions. |
*/ |
template<typename _ForwardIterator, typename _Tp> |
pair<_ForwardIterator, _ForwardIterator> |
equal_range(_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_function_requires(_LessThanOpConcept<_Tp, _ValueType>) |
__glibcxx_requires_partitioned_lower(__first, __last, __val); |
__glibcxx_requires_partitioned_upper(__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 if (__val < *__middle) |
__len = __half; |
else |
{ |
_ForwardIterator __left = std::lower_bound(__first, __middle, |
__val); |
std::advance(__first, __len); |
_ForwardIterator __right = std::upper_bound(++__middle, __first, |
__val); |
return pair<_ForwardIterator, _ForwardIterator>(__left, __right); |
} |
} |
return pair<_ForwardIterator, _ForwardIterator>(__first, __first); |
} |
|
/** |
* @brief Finds the largest subrange in which @p __val could be inserted |
* at any place in it without changing the ordering. |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @param __comp A functor to use for comparisons. |
* @return An pair of iterators defining the subrange. |
* @ingroup binary_search_algorithms |
* |
* This is equivalent to |
* @code |
* std::make_pair(lower_bound(__first, __last, __val, __comp), |
* upper_bound(__first, __last, __val, __comp)) |
* @endcode |
* but does not actually call those functions. |
*/ |
template<typename _ForwardIterator, typename _Tp, typename _Compare> |
pair<_ForwardIterator, _ForwardIterator> |
equal_range(_ForwardIterator __first, _ForwardIterator __last, |
const _Tp& __val, _Compare __comp) |
{ |
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(_BinaryPredicateConcept<_Compare, |
_ValueType, _Tp>) |
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare, |
_Tp, _ValueType>) |
__glibcxx_requires_partitioned_lower_pred(__first, __last, |
__val, __comp); |
__glibcxx_requires_partitioned_upper_pred(__first, __last, |
__val, __comp); |
|
_DistanceType __len = std::distance(__first, __last); |
|
while (__len > 0) |
{ |
_DistanceType __half = __len >> 1; |
_ForwardIterator __middle = __first; |
std::advance(__middle, __half); |
if (__comp(*__middle, __val)) |
{ |
__first = __middle; |
++__first; |
__len = __len - __half - 1; |
} |
else if (__comp(__val, *__middle)) |
__len = __half; |
else |
{ |
_ForwardIterator __left = std::lower_bound(__first, __middle, |
__val, __comp); |
std::advance(__first, __len); |
_ForwardIterator __right = std::upper_bound(++__middle, __first, |
__val, __comp); |
return pair<_ForwardIterator, _ForwardIterator>(__left, __right); |
} |
} |
return pair<_ForwardIterator, _ForwardIterator>(__first, __first); |
} |
|
/** |
* @brief Determines whether an element exists in a range. |
* @ingroup binary_search_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @return True if @p __val (or its equivalent) is in [@p |
* __first,@p __last ]. |
* |
* Note that this does not actually return an iterator to @p __val. For |
* that, use std::find or a container's specialized find member functions. |
*/ |
template<typename _ForwardIterator, typename _Tp> |
bool |
binary_search(_ForwardIterator __first, _ForwardIterator __last, |
const _Tp& __val) |
{ |
typedef typename iterator_traits<_ForwardIterator>::value_type |
_ValueType; |
|
// concept requirements |
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
__glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) |
__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); |
} |
|
/** |
* @brief Determines whether an element exists in a range. |
* @ingroup binary_search_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @param __val The search term. |
* @param __comp A functor to use for comparisons. |
* @return True if @p __val (or its equivalent) is in @p [__first,__last]. |
* |
* Note that this does not actually return an iterator to @p __val. For |
* that, use std::find or a container's specialized find member functions. |
* |
* The comparison function should have the same effects on ordering as |
* the function used for the initial sort. |
*/ |
template<typename _ForwardIterator, typename _Tp, typename _Compare> |
bool |
binary_search(_ForwardIterator __first, _ForwardIterator __last, |
const _Tp& __val, _Compare __comp) |
{ |
typedef typename iterator_traits<_ForwardIterator>::value_type |
_ValueType; |
|
// concept requirements |
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) |
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare, |
_Tp, _ValueType>) |
__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)); |
} |
|
// merge |
|
/// This is a helper function for the __merge_adaptive routines. |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator> |
void |
__move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, |
_InputIterator2 __first2, _InputIterator2 __last2, |
_OutputIterator __result) |
{ |
while (__first1 != __last1 && __first2 != __last2) |
{ |
if (*__first2 < *__first1) |
{ |
*__result = _GLIBCXX_MOVE(*__first2); |
++__first2; |
} |
else |
{ |
*__result = _GLIBCXX_MOVE(*__first1); |
++__first1; |
} |
++__result; |
} |
if (__first1 != __last1) |
_GLIBCXX_MOVE3(__first1, __last1, __result); |
} |
|
/// This is a helper function for the __merge_adaptive routines. |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator, typename _Compare> |
void |
__move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, |
_InputIterator2 __first2, _InputIterator2 __last2, |
_OutputIterator __result, _Compare __comp) |
{ |
while (__first1 != __last1 && __first2 != __last2) |
{ |
if (__comp(*__first2, *__first1)) |
{ |
*__result = _GLIBCXX_MOVE(*__first2); |
++__first2; |
} |
else |
{ |
*__result = _GLIBCXX_MOVE(*__first1); |
++__first1; |
} |
++__result; |
} |
if (__first1 != __last1) |
_GLIBCXX_MOVE3(__first1, __last1, __result); |
} |
|
/// This is a helper function for the __merge_adaptive routines. |
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, |
typename _BidirectionalIterator3> |
void |
__move_merge_adaptive_backward(_BidirectionalIterator1 __first1, |
_BidirectionalIterator1 __last1, |
_BidirectionalIterator2 __first2, |
_BidirectionalIterator2 __last2, |
_BidirectionalIterator3 __result) |
{ |
if (__first1 == __last1) |
{ |
_GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); |
return; |
} |
else if (__first2 == __last2) |
return; |
|
--__last1; |
--__last2; |
while (true) |
{ |
if (*__last2 < *__last1) |
{ |
*--__result = _GLIBCXX_MOVE(*__last1); |
if (__first1 == __last1) |
{ |
_GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); |
return; |
} |
--__last1; |
} |
else |
{ |
*--__result = _GLIBCXX_MOVE(*__last2); |
if (__first2 == __last2) |
return; |
--__last2; |
} |
} |
} |
|
/// This is a helper function for the __merge_adaptive routines. |
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, |
typename _BidirectionalIterator3, typename _Compare> |
void |
__move_merge_adaptive_backward(_BidirectionalIterator1 __first1, |
_BidirectionalIterator1 __last1, |
_BidirectionalIterator2 __first2, |
_BidirectionalIterator2 __last2, |
_BidirectionalIterator3 __result, |
_Compare __comp) |
{ |
if (__first1 == __last1) |
{ |
_GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); |
return; |
} |
else if (__first2 == __last2) |
return; |
|
--__last1; |
--__last2; |
while (true) |
{ |
if (__comp(*__last2, *__last1)) |
{ |
*--__result = _GLIBCXX_MOVE(*__last1); |
if (__first1 == __last1) |
{ |
_GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); |
return; |
} |
--__last1; |
} |
else |
{ |
*--__result = _GLIBCXX_MOVE(*__last2); |
if (__first2 == __last2) |
return; |
--__last2; |
} |
} |
} |
|
/// This is a helper function for the merge routines. |
template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, |
typename _Distance> |
_BidirectionalIterator1 |
__rotate_adaptive(_BidirectionalIterator1 __first, |
_BidirectionalIterator1 __middle, |
_BidirectionalIterator1 __last, |
_Distance __len1, _Distance __len2, |
_BidirectionalIterator2 __buffer, |
_Distance __buffer_size) |
{ |
_BidirectionalIterator2 __buffer_end; |
if (__len1 > __len2 && __len2 <= __buffer_size) |
{ |
if (__len2) |
{ |
__buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); |
_GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); |
return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); |
} |
else |
return __first; |
} |
else if (__len1 <= __buffer_size) |
{ |
if (__len1) |
{ |
__buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); |
_GLIBCXX_MOVE3(__middle, __last, __first); |
return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); |
} |
else |
return __last; |
} |
else |
{ |
std::rotate(__first, __middle, __last); |
std::advance(__first, std::distance(__middle, __last)); |
return __first; |
} |
} |
|
/// This is a helper function for the merge routines. |
template<typename _BidirectionalIterator, typename _Distance, |
typename _Pointer> |
void |
__merge_adaptive(_BidirectionalIterator __first, |
_BidirectionalIterator __middle, |
_BidirectionalIterator __last, |
_Distance __len1, _Distance __len2, |
_Pointer __buffer, _Distance __buffer_size) |
{ |
if (__len1 <= __len2 && __len1 <= __buffer_size) |
{ |
_Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); |
std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, |
__first); |
} |
else if (__len2 <= __buffer_size) |
{ |
_Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); |
std::__move_merge_adaptive_backward(__first, __middle, __buffer, |
__buffer_end, __last); |
} |
else |
{ |
_BidirectionalIterator __first_cut = __first; |
_BidirectionalIterator __second_cut = __middle; |
_Distance __len11 = 0; |
_Distance __len22 = 0; |
if (__len1 > __len2) |
{ |
__len11 = __len1 / 2; |
std::advance(__first_cut, __len11); |
__second_cut = std::lower_bound(__middle, __last, |
*__first_cut); |
__len22 = std::distance(__middle, __second_cut); |
} |
else |
{ |
__len22 = __len2 / 2; |
std::advance(__second_cut, __len22); |
__first_cut = std::upper_bound(__first, __middle, |
*__second_cut); |
__len11 = std::distance(__first, __first_cut); |
} |
_BidirectionalIterator __new_middle = |
std::__rotate_adaptive(__first_cut, __middle, __second_cut, |
__len1 - __len11, __len22, __buffer, |
__buffer_size); |
std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, |
__len22, __buffer, __buffer_size); |
std::__merge_adaptive(__new_middle, __second_cut, __last, |
__len1 - __len11, |
__len2 - __len22, __buffer, __buffer_size); |
} |
} |
|
/// 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, |
_BidirectionalIterator __last, |
_Distance __len1, _Distance __len2, |
_Pointer __buffer, _Distance __buffer_size, |
_Compare __comp) |
{ |
if (__len1 <= __len2 && __len1 <= __buffer_size) |
{ |
_Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); |
std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, |
__first, __comp); |
} |
else if (__len2 <= __buffer_size) |
{ |
_Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); |
std::__move_merge_adaptive_backward(__first, __middle, __buffer, |
__buffer_end, __last, __comp); |
} |
else |
{ |
_BidirectionalIterator __first_cut = __first; |
_BidirectionalIterator __second_cut = __middle; |
_Distance __len11 = 0; |
_Distance __len22 = 0; |
if (__len1 > __len2) |
{ |
__len11 = __len1 / 2; |
std::advance(__first_cut, __len11); |
__second_cut = std::lower_bound(__middle, __last, *__first_cut, |
__comp); |
__len22 = std::distance(__middle, __second_cut); |
} |
else |
{ |
__len22 = __len2 / 2; |
std::advance(__second_cut, __len22); |
__first_cut = std::upper_bound(__first, __middle, *__second_cut, |
__comp); |
__len11 = std::distance(__first, __first_cut); |
} |
_BidirectionalIterator __new_middle = |
std::__rotate_adaptive(__first_cut, __middle, __second_cut, |
__len1 - __len11, __len22, __buffer, |
__buffer_size); |
std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, |
__len22, __buffer, __buffer_size, __comp); |
std::__merge_adaptive(__new_middle, __second_cut, __last, |
__len1 - __len11, |
__len2 - __len22, __buffer, |
__buffer_size, __comp); |
} |
} |
|
/// This is a helper function for the merge routines. |
template<typename _BidirectionalIterator, typename _Distance> |
void |
__merge_without_buffer(_BidirectionalIterator __first, |
_BidirectionalIterator __middle, |
_BidirectionalIterator __last, |
_Distance __len1, _Distance __len2) |
{ |
if (__len1 == 0 || __len2 == 0) |
return; |
if (__len1 + __len2 == 2) |
{ |
if (*__middle < *__first) |
std::iter_swap(__first, __middle); |
return; |
} |
_BidirectionalIterator __first_cut = __first; |
_BidirectionalIterator __second_cut = __middle; |
_Distance __len11 = 0; |
_Distance __len22 = 0; |
if (__len1 > __len2) |
{ |
__len11 = __len1 / 2; |
std::advance(__first_cut, __len11); |
__second_cut = std::lower_bound(__middle, __last, *__first_cut); |
__len22 = std::distance(__middle, __second_cut); |
} |
else |
{ |
__len22 = __len2 / 2; |
std::advance(__second_cut, __len22); |
__first_cut = std::upper_bound(__first, __middle, *__second_cut); |
__len11 = std::distance(__first, __first_cut); |
} |
std::rotate(__first_cut, __middle, __second_cut); |
_BidirectionalIterator __new_middle = __first_cut; |
std::advance(__new_middle, std::distance(__middle, __second_cut)); |
std::__merge_without_buffer(__first, __first_cut, __new_middle, |
__len11, __len22); |
std::__merge_without_buffer(__new_middle, __second_cut, __last, |
__len1 - __len11, __len2 - __len22); |
} |
|
/// This is a helper function for the merge routines. |
template<typename _BidirectionalIterator, typename _Distance, |
typename _Compare> |
void |
__merge_without_buffer(_BidirectionalIterator __first, |
_BidirectionalIterator __middle, |
_BidirectionalIterator __last, |
_Distance __len1, _Distance __len2, |
_Compare __comp) |
{ |
if (__len1 == 0 || __len2 == 0) |
return; |
if (__len1 + __len2 == 2) |
{ |
if (__comp(*__middle, *__first)) |
std::iter_swap(__first, __middle); |
return; |
} |
_BidirectionalIterator __first_cut = __first; |
_BidirectionalIterator __second_cut = __middle; |
_Distance __len11 = 0; |
_Distance __len22 = 0; |
if (__len1 > __len2) |
{ |
__len11 = __len1 / 2; |
std::advance(__first_cut, __len11); |
__second_cut = std::lower_bound(__middle, __last, *__first_cut, |
__comp); |
__len22 = std::distance(__middle, __second_cut); |
} |
else |
{ |
__len22 = __len2 / 2; |
std::advance(__second_cut, __len22); |
__first_cut = std::upper_bound(__first, __middle, *__second_cut, |
__comp); |
__len11 = std::distance(__first, __first_cut); |
} |
std::rotate(__first_cut, __middle, __second_cut); |
_BidirectionalIterator __new_middle = __first_cut; |
std::advance(__new_middle, std::distance(__middle, __second_cut)); |
std::__merge_without_buffer(__first, __first_cut, __new_middle, |
__len11, __len22, __comp); |
std::__merge_without_buffer(__new_middle, __second_cut, __last, |
__len1 - __len11, __len2 - __len22, __comp); |
} |
|
/** |
* @brief Merges two sorted ranges in place. |
* @ingroup sorting_algorithms |
* @param __first An iterator. |
* @param __middle Another iterator. |
* @param __last Another iterator. |
* @return Nothing. |
* |
* Merges two sorted and consecutive ranges, [__first,__middle) and |
* [__middle,__last), and puts the result in [__first,__last). The |
* output will be sorted. 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. |
* |
* If enough additional memory is available, this takes (__last-__first)-1 |
* comparisons. Otherwise an NlogN algorithm is used, where N is |
* distance(__first,__last). |
*/ |
template<typename _BidirectionalIterator> |
void |
inplace_merge(_BidirectionalIterator __first, |
_BidirectionalIterator __middle, |
_BidirectionalIterator __last) |
{ |
typedef typename iterator_traits<_BidirectionalIterator>::value_type |
_ValueType; |
typedef typename iterator_traits<_BidirectionalIterator>::difference_type |
_DistanceType; |
|
// concept requirements |
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< |
_BidirectionalIterator>) |
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) |
__glibcxx_requires_sorted(__first, __middle); |
__glibcxx_requires_sorted(__middle, __last); |
|
if (__first == __middle || __middle == __last) |
return; |
|
_DistanceType __len1 = std::distance(__first, __middle); |
_DistanceType __len2 = std::distance(__middle, __last); |
|
_Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, |
__last); |
if (__buf.begin() == 0) |
std::__merge_without_buffer(__first, __middle, __last, __len1, __len2); |
else |
std::__merge_adaptive(__first, __middle, __last, __len1, __len2, |
__buf.begin(), _DistanceType(__buf.size())); |
} |
|
/** |
* @brief Merges two sorted ranges in place. |
* @ingroup sorting_algorithms |
* @param __first An iterator. |
* @param __middle Another iterator. |
* @param __last Another iterator. |
* @param __comp A functor to use for comparisons. |
* @return Nothing. |
* |
* Merges two sorted and consecutive ranges, [__first,__middle) and |
* [middle,last), and puts the result in [__first,__last). The output will |
* be sorted. 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. |
* |
* If enough additional memory is available, this takes (__last-__first)-1 |
* comparisons. Otherwise an NlogN algorithm is used, where N is |
* distance(__first,__last). |
* |
* The comparison function should have the same effects on ordering as |
* the function used for the initial sort. |
*/ |
template<typename _BidirectionalIterator, typename _Compare> |
void |
inplace_merge(_BidirectionalIterator __first, |
_BidirectionalIterator __middle, |
_BidirectionalIterator __last, |
_Compare __comp) |
{ |
typedef typename iterator_traits<_BidirectionalIterator>::value_type |
_ValueType; |
typedef typename iterator_traits<_BidirectionalIterator>::difference_type |
_DistanceType; |
|
// concept requirements |
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< |
_BidirectionalIterator>) |
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare, |
_ValueType, _ValueType>) |
__glibcxx_requires_sorted_pred(__first, __middle, __comp); |
__glibcxx_requires_sorted_pred(__middle, __last, __comp); |
|
if (__first == __middle || __middle == __last) |
return; |
|
const _DistanceType __len1 = std::distance(__first, __middle); |
const _DistanceType __len2 = std::distance(__middle, __last); |
|
_Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, |
__last); |
if (__buf.begin() == 0) |
std::__merge_without_buffer(__first, __middle, __last, __len1, |
__len2, __comp); |
else |
std::__merge_adaptive(__first, __middle, __last, __len1, __len2, |
__buf.begin(), _DistanceType(__buf.size()), |
__comp); |
} |
|
|
/// This is a helper function for the __merge_sort_loop routines. |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator> |
_OutputIterator |
__move_merge(_InputIterator1 __first1, _InputIterator1 __last1, |
_InputIterator2 __first2, _InputIterator2 __last2, |
_OutputIterator __result) |
{ |
while (__first1 != __last1 && __first2 != __last2) |
{ |
if (*__first2 < *__first1) |
{ |
*__result = _GLIBCXX_MOVE(*__first2); |
++__first2; |
} |
else |
{ |
*__result = _GLIBCXX_MOVE(*__first1); |
++__first1; |
} |
++__result; |
} |
return _GLIBCXX_MOVE3(__first2, __last2, |
_GLIBCXX_MOVE3(__first1, __last1, |
__result)); |
} |
|
/// This is a helper function for the __merge_sort_loop routines. |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator, typename _Compare> |
_OutputIterator |
__move_merge(_InputIterator1 __first1, _InputIterator1 __last1, |
_InputIterator2 __first2, _InputIterator2 __last2, |
_OutputIterator __result, _Compare __comp) |
{ |
while (__first1 != __last1 && __first2 != __last2) |
{ |
if (__comp(*__first2, *__first1)) |
{ |
*__result = _GLIBCXX_MOVE(*__first2); |
++__first2; |
} |
else |
{ |
*__result = _GLIBCXX_MOVE(*__first1); |
++__first1; |
} |
++__result; |
} |
return _GLIBCXX_MOVE3(__first2, __last2, |
_GLIBCXX_MOVE3(__first1, __last1, |
__result)); |
} |
|
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, |
typename _Distance> |
void |
__merge_sort_loop(_RandomAccessIterator1 __first, |
_RandomAccessIterator1 __last, |
_RandomAccessIterator2 __result, |
_Distance __step_size) |
{ |
const _Distance __two_step = 2 * __step_size; |
|
while (__last - __first >= __two_step) |
{ |
__result = std::__move_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::__move_merge(__first, __first + __step_size, |
__first + __step_size, __last, __result); |
} |
|
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, |
typename _Distance, typename _Compare> |
void |
__merge_sort_loop(_RandomAccessIterator1 __first, |
_RandomAccessIterator1 __last, |
_RandomAccessIterator2 __result, _Distance __step_size, |
_Compare __comp) |
{ |
const _Distance __two_step = 2 * __step_size; |
|
while (__last - __first >= __two_step) |
{ |
__result = std::__move_merge(__first, __first + __step_size, |
__first + __step_size, |
__first + __two_step, |
__result, __comp); |
__first += __two_step; |
} |
__step_size = std::min(_Distance(__last - __first), __step_size); |
|
std::__move_merge(__first,__first + __step_size, |
__first + __step_size, __last, __result, __comp); |
} |
|
template<typename _RandomAccessIterator, typename _Distance> |
void |
__chunk_insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Distance __chunk_size) |
{ |
while (__last - __first >= __chunk_size) |
{ |
std::__insertion_sort(__first, __first + __chunk_size); |
__first += __chunk_size; |
} |
std::__insertion_sort(__first, __last); |
} |
|
template<typename _RandomAccessIterator, typename _Distance, |
typename _Compare> |
void |
__chunk_insertion_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Distance __chunk_size, _Compare __comp) |
{ |
while (__last - __first >= __chunk_size) |
{ |
std::__insertion_sort(__first, __first + __chunk_size, __comp); |
__first += __chunk_size; |
} |
std::__insertion_sort(__first, __last, __comp); |
} |
|
enum { _S_chunk_size = 7 }; |
|
template<typename _RandomAccessIterator, typename _Pointer> |
void |
__merge_sort_with_buffer(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Pointer __buffer) |
{ |
typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
_Distance; |
|
const _Distance __len = __last - __first; |
const _Pointer __buffer_last = __buffer + __len; |
|
_Distance __step_size = _S_chunk_size; |
std::__chunk_insertion_sort(__first, __last, __step_size); |
|
while (__step_size < __len) |
{ |
std::__merge_sort_loop(__first, __last, __buffer, __step_size); |
__step_size *= 2; |
std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size); |
__step_size *= 2; |
} |
} |
|
template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> |
void |
__merge_sort_with_buffer(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Pointer __buffer, _Compare __comp) |
{ |
typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
_Distance; |
|
const _Distance __len = __last - __first; |
const _Pointer __buffer_last = __buffer + __len; |
|
_Distance __step_size = _S_chunk_size; |
std::__chunk_insertion_sort(__first, __last, __step_size, __comp); |
|
while (__step_size < __len) |
{ |
std::__merge_sort_loop(__first, __last, __buffer, |
__step_size, __comp); |
__step_size *= 2; |
std::__merge_sort_loop(__buffer, __buffer_last, __first, |
__step_size, __comp); |
__step_size *= 2; |
} |
} |
|
template<typename _RandomAccessIterator, typename _Pointer, |
typename _Distance> |
void |
__stable_sort_adaptive(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Pointer __buffer, _Distance __buffer_size) |
{ |
const _Distance __len = (__last - __first + 1) / 2; |
const _RandomAccessIterator __middle = __first + __len; |
if (__len > __buffer_size) |
{ |
std::__stable_sort_adaptive(__first, __middle, |
__buffer, __buffer_size); |
std::__stable_sort_adaptive(__middle, __last, |
__buffer, __buffer_size); |
} |
else |
{ |
std::__merge_sort_with_buffer(__first, __middle, __buffer); |
std::__merge_sort_with_buffer(__middle, __last, __buffer); |
} |
std::__merge_adaptive(__first, __middle, __last, |
_Distance(__middle - __first), |
_Distance(__last - __middle), |
__buffer, __buffer_size); |
} |
|
template<typename _RandomAccessIterator, typename _Pointer, |
typename _Distance, typename _Compare> |
void |
__stable_sort_adaptive(_RandomAccessIterator __first, |
_RandomAccessIterator __last, |
_Pointer __buffer, _Distance __buffer_size, |
_Compare __comp) |
{ |
const _Distance __len = (__last - __first + 1) / 2; |
const _RandomAccessIterator __middle = __first + __len; |
if (__len > __buffer_size) |
{ |
std::__stable_sort_adaptive(__first, __middle, __buffer, |
__buffer_size, __comp); |
std::__stable_sort_adaptive(__middle, __last, __buffer, |
__buffer_size, __comp); |
} |
else |
{ |
std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); |
std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); |
} |
std::__merge_adaptive(__first, __middle, __last, |
_Distance(__middle - __first), |
_Distance(__last - __middle), |
__buffer, __buffer_size, |
__comp); |
} |
|
/// This is a helper function for the stable sorting routines. |
template<typename _RandomAccessIterator> |
void |
__inplace_stable_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last) |
{ |
if (__last - __first < 15) |
{ |
std::__insertion_sort(__first, __last); |
return; |
} |
_RandomAccessIterator __middle = __first + (__last - __first) / 2; |
std::__inplace_stable_sort(__first, __middle); |
std::__inplace_stable_sort(__middle, __last); |
std::__merge_without_buffer(__first, __middle, __last, |
__middle - __first, |
__last - __middle); |
} |
|
/// This is a helper function for the stable sorting routines. |
template<typename _RandomAccessIterator, typename _Compare> |
void |
__inplace_stable_sort(_RandomAccessIterator __first, |
_RandomAccessIterator __last, _Compare __comp) |
{ |
if (__last - __first < 15) |
{ |
std::__insertion_sort(__first, __last, __comp); |
return; |
} |
_RandomAccessIterator __middle = __first + (__last - __first) / 2; |
std::__inplace_stable_sort(__first, __middle, __comp); |
std::__inplace_stable_sort(__middle, __last, __comp); |
std::__merge_without_buffer(__first, __middle, __last, |
__middle - __first, |
__last - __middle, |
__comp); |
} |
|
// stable_sort |
|
// Set algorithms: includes, set_union, set_intersection, set_difference, |
// set_symmetric_difference. All of these algorithms have the precondition |
// that their input ranges are sorted and the postcondition that their output |
// ranges are sorted. |
|
/** |
* @brief Determines whether all elements of a sequence exists in a range. |
* @param __first1 Start of search range. |
* @param __last1 End of search range. |
* @param __first2 Start of sequence |
* @param __last2 End of sequence. |
* @return True if each element in [__first2,__last2) is contained in order |
* within [__first1,__last1). False otherwise. |
* @ingroup set_algorithms |
* |
* This operation expects both [__first1,__last1) and |
* [__first2,__last2) to be sorted. Searches for the presence of |
* each element in [__first2,__last2) within [__first1,__last1). |
* The iterators over each range only move forward, so this is a |
* linear algorithm. If an element in [__first2,__last2) is not |
* found before the search iterator reaches @p __last2, false is |
* returned. |
*/ |
template<typename _InputIterator1, typename _InputIterator2> |
bool |
includes(_InputIterator1 __first1, _InputIterator1 __last1, |
_InputIterator2 __first2, _InputIterator2 __last2) |
{ |
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(_LessThanOpConcept<_ValueType1, _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) |
return false; |
else if(*__first1 < *__first2) |
++__first1; |
else |
++__first1, ++__first2; |
|
return __first2 == __last2; |
} |
|
/** |
* @brief Determines whether all elements of a sequence exists in a range |
* using comparison. |
* @ingroup set_algorithms |
* @param __first1 Start of search range. |
* @param __last1 End of search range. |
* @param __first2 Start of sequence |
* @param __last2 End of sequence. |
* @param __comp Comparison function to use. |
* @return True if each element in [__first2,__last2) is contained |
* in order within [__first1,__last1) according to comp. False |
* otherwise. @ingroup set_algorithms |
* |
* This operation expects both [__first1,__last1) and |
* [__first2,__last2) to be sorted. Searches for the presence of |
* each element in [__first2,__last2) within [__first1,__last1), |
* using comp to decide. The iterators over each range only move |
* forward, so this is a linear algorithm. If an element in |
* [__first2,__last2) is not found before the search iterator |
* reaches @p __last2, false is returned. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _Compare> |
bool |
includes(_InputIterator1 __first1, _InputIterator1 __last1, |
_InputIterator2 __first2, _InputIterator2 __last2, |
_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(_BinaryPredicateConcept<_Compare, |
_ValueType1, _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)) |
return false; |
else if(__comp(*__first1, *__first2)) |
++__first1; |
else |
++__first1, ++__first2; |
|
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 @e dictionary ordering. |
* @ingroup sorting_algorithms |
* @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 @e 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 @e dictionary ordering using |
* comparison functor. |
* @ingroup sorting_algorithms |
* @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 |
* @e dictionary sorted sequences ordered by @p __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 @e dictionary ordering. |
* @ingroup sorting_algorithms |
* @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 @e 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 @e dictionary ordering using |
* comparison functor. |
* @ingroup sorting_algorithms |
* @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 |
* @e dictionary sorted sequences ordered by @p __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. |
* @ingroup mutating_algorithms |
* @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; |
} |
|
#if __cplusplus >= 201103L |
/** |
* @brief Determines whether the elements of a sequence are sorted. |
* @ingroup sorting_algorithms |
* @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. |
* @ingroup sorting_algorithms |
* @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. |
* @ingroup sorting_algorithms |
* @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. |
* @ingroup sorting_algorithms |
* @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. |
* @ingroup sorting_algorithms |
* @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. |
* @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 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. |
* @ingroup sorting_algorithms |
* @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. |
* @ingroup sorting_algorithms |
* @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); |
} |
|
// N2722 + DR 915. |
template<typename _Tp> |
inline _Tp |
min(initializer_list<_Tp> __l) |
{ return *std::min_element(__l.begin(), __l.end()); } |
|
template<typename _Tp, typename _Compare> |
inline _Tp |
min(initializer_list<_Tp> __l, _Compare __comp) |
{ return *std::min_element(__l.begin(), __l.end(), __comp); } |
|
template<typename _Tp> |
inline _Tp |
max(initializer_list<_Tp> __l) |
{ return *std::max_element(__l.begin(), __l.end()); } |
|
template<typename _Tp, typename _Compare> |
inline _Tp |
max(initializer_list<_Tp> __l, _Compare __comp) |
{ return *std::max_element(__l.begin(), __l.end(), __comp); } |
|
template<typename _Tp> |
inline pair<_Tp, _Tp> |
minmax(initializer_list<_Tp> __l) |
{ |
pair<const _Tp*, const _Tp*> __p = |
std::minmax_element(__l.begin(), __l.end()); |
return std::make_pair(*__p.first, *__p.second); |
} |
|
template<typename _Tp, typename _Compare> |
inline pair<_Tp, _Tp> |
minmax(initializer_list<_Tp> __l, _Compare __comp) |
{ |
pair<const _Tp*, const _Tp*> __p = |
std::minmax_element(__l.begin(), __l.end(), __comp); |
return std::make_pair(*__p.first, *__p.second); |
} |
|
/** |
* @brief Checks whether a permutaion of the second sequence is equal |
* to the first sequence. |
* @ingroup non_mutating_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @return true if there exists a permutation of the elements in the range |
* [__first2, __first2 + (__last1 - __first1)), beginning with |
* ForwardIterator2 begin, such that equal(__first1, __last1, begin) |
* returns true; otherwise, returns false. |
*/ |
template<typename _ForwardIterator1, typename _ForwardIterator2> |
bool |
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
_ForwardIterator2 __first2) |
{ |
// Efficiently compare identical prefixes: O(N) if sequences |
// have the same elements in the same order. |
for (; __first1 != __last1; ++__first1, ++__first2) |
if (!(*__first1 == *__first2)) |
break; |
|
if (__first1 == __last1) |
return true; |
|
// Establish __last2 assuming equal ranges by iterating over the |
// rest of the list. |
_ForwardIterator2 __last2 = __first2; |
std::advance(__last2, std::distance(__first1, __last1)); |
for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) |
{ |
if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan)) |
continue; // We've seen this one before. |
|
auto __matches = std::count(__first2, __last2, *__scan); |
if (0 == __matches |
|| std::count(__scan, __last1, *__scan) != __matches) |
return false; |
} |
return true; |
} |
|
/** |
* @brief Checks whether a permutation of the second sequence is equal |
* to the first sequence. |
* @ingroup non_mutating_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __pred A binary predicate. |
* @return true if there exists a permutation of the elements in |
* the range [__first2, __first2 + (__last1 - __first1)), |
* beginning with ForwardIterator2 begin, such that |
* equal(__first1, __last1, __begin, __pred) returns true; |
* otherwise, returns false. |
*/ |
template<typename _ForwardIterator1, typename _ForwardIterator2, |
typename _BinaryPredicate> |
bool |
is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, |
_ForwardIterator2 __first2, _BinaryPredicate __pred) |
{ |
// Efficiently compare identical prefixes: O(N) if sequences |
// have the same elements in the same order. |
for (; __first1 != __last1; ++__first1, ++__first2) |
if (!bool(__pred(*__first1, *__first2))) |
break; |
|
if (__first1 == __last1) |
return true; |
|
// Establish __last2 assuming equal ranges by iterating over the |
// rest of the list. |
_ForwardIterator2 __last2 = __first2; |
std::advance(__last2, std::distance(__first1, __last1)); |
for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) |
{ |
using std::placeholders::_1; |
|
if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan, |
std::bind(__pred, _1, *__scan))) |
continue; // We've seen this one before. |
|
auto __matches = std::count_if(__first2, __last2, |
std::bind(__pred, _1, *__scan)); |
if (0 == __matches |
|| std::count_if(__scan, __last1, |
std::bind(__pred, _1, *__scan)) != __matches) |
return false; |
} |
return true; |
} |
|
#ifdef _GLIBCXX_USE_C99_STDINT_TR1 |
/** |
* @brief Shuffle the elements of a sequence using a uniform random |
* number generator. |
* @ingroup mutating_algorithms |
* @param __first A forward iterator. |
* @param __last A forward iterator. |
* @param __g A UniformRandomNumberGenerator (26.5.1.3). |
* @return Nothing. |
* |
* Reorders the elements in the range @p [__first,__last) using @p __g to |
* provide random numbers. |
*/ |
template<typename _RandomAccessIterator, |
typename _UniformRandomNumberGenerator> |
void |
shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, |
_UniformRandomNumberGenerator&& __g) |
{ |
// concept requirements |
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< |
_RandomAccessIterator>) |
__glibcxx_requires_valid_range(__first, __last); |
|
if (__first == __last) |
return; |
|
typedef typename iterator_traits<_RandomAccessIterator>::difference_type |
_DistanceType; |
|
typedef typename std::make_unsigned<_DistanceType>::type __ud_type; |
typedef typename std::uniform_int_distribution<__ud_type> __distr_type; |
typedef typename __distr_type::param_type __p_type; |
__distr_type __d; |
|
for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) |
std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); |
} |
#endif |
|
#endif // C++11 |
|
_GLIBCXX_END_NAMESPACE_VERSION |
|
_GLIBCXX_BEGIN_NAMESPACE_ALGO |
|
/** |
* @brief Apply a function to every element of a sequence. |
* @ingroup non_mutating_algorithms |
* @param __first An input iterator. |
* @param __last An input iterator. |
* @param __f A unary function object. |
* @return @p __f (std::move(@p __f) in C++0x). |
* |
* Applies the function object @p __f to each element in the range |
* @p [first,last). @p __f must not modify the order of the sequence. |
* 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 _GLIBCXX_MOVE(__f); |
} |
|
/** |
* @brief Find the first occurrence of a value in a sequence. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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_A::find(__first1, __last1, *__first2); |
|
// General case. |
_ForwardIterator2 __p; |
_ForwardIterator1 __current = __first1; |
|
for (;;) |
{ |
__first1 = _GLIBCXX_STD_A::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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup non_mutating_algorithms |
* @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_A::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. |
* @ingroup non_mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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). |
* |
* _GLIBCXX_RESOLVE_LIB_DEFECTS |
* DR 865. More algorithms that throw away information |
*/ |
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 (__decltype(__n + 0) __niter = __n; |
__niter > 0; --__niter, ++__first) |
*__first = __gen(); |
return __first; |
} |
|
|
/** |
* @brief Copy a sequence, removing consecutive duplicate values. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup mutating_algorithms |
* @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, |
#if __cplusplus >= 201103L |
_RandomNumberGenerator&& __rand) |
#else |
_RandomNumberGenerator& __rand) |
#endif |
{ |
// 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. |
* @ingroup mutating_algorithms |
* @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. |
* @ingroup sorting_algorithms |
* @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 @e i and @e j are iterators in the range |
* @p [__first,__middle) such that i precedes j and @e k is an iterator in |
* the range @p [__middle,__last) then *j<*i and *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. |
* @ingroup sorting_algorithms |
* @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 @e i and @e j are iterators in the range |
* @p [__first,__middle) such that i precedes j and @e 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. |
* @ingroup sorting_algorithms |
* @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. The elements either side of @p *__nth are |
* not completely sorted, but for any iterator @e i in the range |
* @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it |
* holds that *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. |
* @ingroup sorting_algorithms |
* @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 @e i in the range |
* @p [__first,__nth) and any iterator @e 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. |
* @ingroup sorting_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @return Nothing. |
* |
* Sorts the elements in the range @p [__first,__last) in ascending order, |
* such that for each iterator @e i in the range @p [__first,__last-1), |
* *(i+1)<*i is false. |
* |
* 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. |
* @ingroup sorting_algorithms |
* @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 @e 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. |
* @ingroup sorting_algorithms |
* @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 <em>not less |
* than</em> @e val. |
* |
* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into |
* the sorted range @p [__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. |
* @ingroup sorting_algorithms |
* @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" @e val. |
* |
* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into |
* the sorted range @p [__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. |
* @ingroup sorting_algorithms |
* @param __first An iterator. |
* @param __last Another iterator. |
* @return Nothing. |
* |
* Sorts the elements in the range @p [__first,__last) in ascending order, |
* such that for each iterator @p i in the range @p [__first,__last-1), |
* @p *(i+1)<*i is false. |
* |
* 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. |
* @ingroup sorting_algorithms |
* @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 for each iterator @p i in the range @p [__first,__last-1), |
* @p __comp(*(i+1),*i) is false. |
* |
* 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. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* each range in order to the output range. Iterators increment for each |
* range. When the current element of one range is less than the other, |
* that element is copied and the iterator advanced. If an element is |
* contained in both ranges, the element from the first range is copied and |
* both ranges advance. The output range may not overlap either input |
* range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator> |
_OutputIterator |
set_union(_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<_ValueType1, _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 (*__first1 < *__first2) |
{ |
*__result = *__first1; |
++__first1; |
} |
else if (*__first2 < *__first1) |
{ |
*__result = *__first2; |
++__first2; |
} |
else |
{ |
*__result = *__first1; |
++__first1; |
++__first2; |
} |
++__result; |
} |
return std::copy(__first2, __last2, std::copy(__first1, __last1, |
__result)); |
} |
|
/** |
* @brief Return the union of two sorted ranges using a comparison functor. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @param __comp The comparison functor. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* each range in order to the output range. Iterators increment for each |
* range. When the current element of one range is less than the other |
* according to @p __comp, that element is copied and the iterator advanced. |
* If an equivalent element according to @p __comp is contained in both |
* ranges, the element from the first range is copied and both ranges |
* advance. The output range may not overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator, typename _Compare> |
_OutputIterator |
set_union(_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, |
_ValueType1, _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(*__first1, *__first2)) |
{ |
*__result = *__first1; |
++__first1; |
} |
else if (__comp(*__first2, *__first1)) |
{ |
*__result = *__first2; |
++__first2; |
} |
else |
{ |
*__result = *__first1; |
++__first1; |
++__first2; |
} |
++__result; |
} |
return std::copy(__first2, __last2, std::copy(__first1, __last1, |
__result)); |
} |
|
/** |
* @brief Return the intersection of two sorted ranges. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* both ranges in order to the output range. Iterators increment for each |
* range. When the current element of one range is less than the other, |
* that iterator advances. If an element is contained in both ranges, the |
* element from the first range is copied and both ranges advance. The |
* output range may not overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator> |
_OutputIterator |
set_intersection(_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(_LessThanOpConcept<_ValueType1, _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 (*__first1 < *__first2) |
++__first1; |
else if (*__first2 < *__first1) |
++__first2; |
else |
{ |
*__result = *__first1; |
++__first1; |
++__first2; |
++__result; |
} |
return __result; |
} |
|
/** |
* @brief Return the intersection of two sorted ranges using comparison |
* functor. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @param __comp The comparison functor. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* both ranges in order to the output range. Iterators increment for each |
* range. When the current element of one range is less than the other |
* according to @p __comp, that iterator advances. If an element is |
* contained in both ranges according to @p __comp, the element from the |
* first range is copied and both ranges advance. The output range may not |
* overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator, typename _Compare> |
_OutputIterator |
set_intersection(_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(_BinaryPredicateConcept<_Compare, |
_ValueType1, _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(*__first1, *__first2)) |
++__first1; |
else if (__comp(*__first2, *__first1)) |
++__first2; |
else |
{ |
*__result = *__first1; |
++__first1; |
++__first2; |
++__result; |
} |
return __result; |
} |
|
/** |
* @brief Return the difference of two sorted ranges. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* the first range but not the second in order to the output range. |
* Iterators increment for each range. When the current element of the |
* first range is less than the second, that element is copied and the |
* iterator advances. If the current element of the second range is less, |
* the iterator advances, but no element is copied. If an element is |
* contained in both ranges, no elements are copied and both ranges |
* advance. The output range may not overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator> |
_OutputIterator |
set_difference(_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(_LessThanOpConcept<_ValueType1, _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 (*__first1 < *__first2) |
{ |
*__result = *__first1; |
++__first1; |
++__result; |
} |
else if (*__first2 < *__first1) |
++__first2; |
else |
{ |
++__first1; |
++__first2; |
} |
return std::copy(__first1, __last1, __result); |
} |
|
/** |
* @brief Return the difference of two sorted ranges using comparison |
* functor. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @param __comp The comparison functor. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* the first range but not the second in order to the output range. |
* Iterators increment for each range. When the current element of the |
* first range is less than the second according to @p __comp, that element |
* is copied and the iterator advances. If the current element of the |
* second range is less, no element is copied and the iterator advances. |
* If an element is contained in both ranges according to @p __comp, no |
* elements are copied and both ranges advance. The output range may not |
* overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator, typename _Compare> |
_OutputIterator |
set_difference(_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(_BinaryPredicateConcept<_Compare, |
_ValueType1, _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(*__first1, *__first2)) |
{ |
*__result = *__first1; |
++__first1; |
++__result; |
} |
else if (__comp(*__first2, *__first1)) |
++__first2; |
else |
{ |
++__first1; |
++__first2; |
} |
return std::copy(__first1, __last1, __result); |
} |
|
/** |
* @brief Return the symmetric difference of two sorted ranges. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* one range but not the other in order to the output range. Iterators |
* increment for each range. When the current element of one range is less |
* than the other, that element is copied and the iterator advances. If an |
* element is contained in both ranges, no elements are copied and both |
* ranges advance. The output range may not overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator> |
_OutputIterator |
set_symmetric_difference(_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<_ValueType1, _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 (*__first1 < *__first2) |
{ |
*__result = *__first1; |
++__first1; |
++__result; |
} |
else if (*__first2 < *__first1) |
{ |
*__result = *__first2; |
++__first2; |
++__result; |
} |
else |
{ |
++__first1; |
++__first2; |
} |
return std::copy(__first2, __last2, std::copy(__first1, |
__last1, __result)); |
} |
|
/** |
* @brief Return the symmetric difference of two sorted ranges using |
* comparison functor. |
* @ingroup set_algorithms |
* @param __first1 Start of first range. |
* @param __last1 End of first range. |
* @param __first2 Start of second range. |
* @param __last2 End of second range. |
* @param __comp The comparison functor. |
* @return End of the output range. |
* @ingroup set_algorithms |
* |
* This operation iterates over both ranges, copying elements present in |
* one range but not the other in order to the output range. Iterators |
* increment for each range. When the current element of one range is less |
* than the other according to @p comp, that element is copied and the |
* iterator advances. If an element is contained in both ranges according |
* to @p __comp, no elements are copied and both ranges advance. The output |
* range may not overlap either input range. |
*/ |
template<typename _InputIterator1, typename _InputIterator2, |
typename _OutputIterator, typename _Compare> |
_OutputIterator |
set_symmetric_difference(_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, |
_ValueType1, _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(*__first1, *__first2)) |
{ |
*__result = *__first1; |
++__first1; |
++__result; |
} |
else if (__comp(*__first2, *__first1)) |
{ |
*__result = *__first2; |
++__first2; |
++__result; |
} |
else |
{ |
++__first1; |
++__first2; |
} |
return std::copy(__first2, __last2, |
std::copy(__first1, __last1, __result)); |
} |
|
|
/** |
* @brief Return the minimum element in a range. |
* @ingroup sorting_algorithms |
* @param __first Start of range. |
* @param __last End of range. |
* @return Iterator referencing the first instance of the smallest value. |
*/ |
template<typename _ForwardIterator> |
_ForwardIterator |
min_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); |
|
if (__first == __last) |
return __first; |
_ForwardIterator __result = __first; |
while (++__first != __last) |
if (*__first < *__result) |
__result = __first; |
return __result; |
} |
|
/** |
* @brief Return the minimum element in a range using comparison functor. |
* @ingroup sorting_algorithms |
* @param __first Start of range. |
* @param __last End of range. |
* @param __comp Comparison functor. |
* @return Iterator referencing the first instance of the smallest value |
* according to __comp. |
*/ |
template<typename _ForwardIterator, typename _Compare> |
_ForwardIterator |
min_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); |
|
if (__first == __last) |
return __first; |
_ForwardIterator __result = __first; |
while (++__first != __last) |
if (__comp(*__first, *__result)) |
__result = __first; |
return __result; |
} |
|
/** |
* @brief Return the maximum element in a range. |
* @ingroup sorting_algorithms |
* @param __first Start of range. |
* @param __last End of range. |
* @return Iterator referencing the first instance of the largest value. |
*/ |
template<typename _ForwardIterator> |
_ForwardIterator |
max_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); |
|
if (__first == __last) |
return __first; |
_ForwardIterator __result = __first; |
while (++__first != __last) |
if (*__result < *__first) |
__result = __first; |
return __result; |
} |
|
/** |
* @brief Return the maximum element in a range using comparison functor. |
* @ingroup sorting_algorithms |
* @param __first Start of range. |
* @param __last End of range. |
* @param __comp Comparison functor. |
* @return Iterator referencing the first instance of the largest value |
* according to __comp. |
*/ |
template<typename _ForwardIterator, typename _Compare> |
_ForwardIterator |
max_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); |
|
if (__first == __last) return __first; |
_ForwardIterator __result = __first; |
while (++__first != __last) |
if (__comp(*__result, *__first)) |
__result = __first; |
return __result; |
} |
|
_GLIBCXX_END_NAMESPACE_ALGO |
} // namespace std |
|
#endif /* _STL_ALGO_H */ |