stl_algo.h revision 132720
197403Sobrien// Algorithm implementation -*- C++ -*- 297403Sobrien 3132720Skan// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file stl_algo.h 5797403Sobrien * This is an internal header file, included by other library headers. 5897403Sobrien * You should not attempt to use it directly. 5997403Sobrien */ 6097403Sobrien 61132720Skan#ifndef _ALGO_H 62132720Skan#define _ALGO_H 1 6397403Sobrien 6497403Sobrien#include <bits/stl_heap.h> 6597403Sobrien#include <bits/stl_tempbuf.h> // for _Temporary_buffer 66132720Skan#include <debug/debug.h> 6797403Sobrien 68132720Skan// See concept_check.h for the __glibcxx_*_requires macros. 6997403Sobrien 7097403Sobriennamespace std 7197403Sobrien{ 7297403Sobrien /** 7397403Sobrien * @brief Find the median of three values. 7497403Sobrien * @param a A value. 7597403Sobrien * @param b A value. 7697403Sobrien * @param c A value. 7797403Sobrien * @return One of @p a, @p b or @p c. 7897403Sobrien * 7997403Sobrien * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 8097403Sobrien * then the value returned will be @c m. 8197403Sobrien * This is an SGI extension. 8297403Sobrien * @ingroup SGIextensions 8397403Sobrien */ 8497403Sobrien template<typename _Tp> 85132720Skan inline const _Tp& 8697403Sobrien __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 8797403Sobrien { 8897403Sobrien // concept requirements 89132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 9097403Sobrien if (__a < __b) 9197403Sobrien if (__b < __c) 9297403Sobrien return __b; 9397403Sobrien else if (__a < __c) 9497403Sobrien return __c; 9597403Sobrien else 9697403Sobrien return __a; 9797403Sobrien else if (__a < __c) 9897403Sobrien return __a; 9997403Sobrien else if (__b < __c) 10097403Sobrien return __c; 10197403Sobrien else 10297403Sobrien return __b; 10397403Sobrien } 10497403Sobrien 10597403Sobrien /** 10697403Sobrien * @brief Find the median of three values using a predicate for comparison. 10797403Sobrien * @param a A value. 10897403Sobrien * @param b A value. 10997403Sobrien * @param c A value. 11097403Sobrien * @param comp A binary predicate. 11197403Sobrien * @return One of @p a, @p b or @p c. 11297403Sobrien * 11397403Sobrien * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 11497403Sobrien * and @p comp(m,n) are both true then the value returned will be @c m. 11597403Sobrien * This is an SGI extension. 11697403Sobrien * @ingroup SGIextensions 11797403Sobrien */ 11897403Sobrien template<typename _Tp, typename _Compare> 11997403Sobrien inline const _Tp& 12097403Sobrien __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 12197403Sobrien { 12297403Sobrien // concept requirements 123132720Skan __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>) 12497403Sobrien if (__comp(__a, __b)) 12597403Sobrien if (__comp(__b, __c)) 12697403Sobrien return __b; 12797403Sobrien else if (__comp(__a, __c)) 12897403Sobrien return __c; 12997403Sobrien else 13097403Sobrien return __a; 13197403Sobrien else if (__comp(__a, __c)) 13297403Sobrien return __a; 13397403Sobrien else if (__comp(__b, __c)) 13497403Sobrien return __c; 13597403Sobrien else 13697403Sobrien return __b; 13797403Sobrien } 13897403Sobrien 13997403Sobrien /** 14097403Sobrien * @brief Apply a function to every element of a sequence. 14197403Sobrien * @param first An input iterator. 14297403Sobrien * @param last An input iterator. 14397403Sobrien * @param f A unary function object. 14497403Sobrien * @return @p f. 14597403Sobrien * 14697403Sobrien * Applies the function object @p f to each element in the range 14797403Sobrien * @p [first,last). @p f must not modify the order of the sequence. 14897403Sobrien * If @p f has a return value it is ignored. 14997403Sobrien */ 150132720Skan template<typename _InputIterator, typename _Function> 15197403Sobrien _Function 152132720Skan for_each(_InputIterator __first, _InputIterator __last, _Function __f) 15397403Sobrien { 15497403Sobrien // concept requirements 155132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 156132720Skan __glibcxx_requires_valid_range(__first, __last); 15797403Sobrien for ( ; __first != __last; ++__first) 15897403Sobrien __f(*__first); 15997403Sobrien return __f; 16097403Sobrien } 16197403Sobrien 16297403Sobrien /** 16397403Sobrien * @if maint 16497403Sobrien * This is an overload used by find() for the Input Iterator case. 16597403Sobrien * @endif 16697403Sobrien */ 167132720Skan template<typename _InputIterator, typename _Tp> 168132720Skan inline _InputIterator 169132720Skan find(_InputIterator __first, _InputIterator __last, 170132720Skan const _Tp& __val, input_iterator_tag) 17197403Sobrien { 17297403Sobrien while (__first != __last && !(*__first == __val)) 17397403Sobrien ++__first; 17497403Sobrien return __first; 17597403Sobrien } 17697403Sobrien 17797403Sobrien /** 17897403Sobrien * @if maint 17997403Sobrien * This is an overload used by find_if() for the Input Iterator case. 18097403Sobrien * @endif 18197403Sobrien */ 182132720Skan template<typename _InputIterator, typename _Predicate> 183132720Skan inline _InputIterator 184132720Skan find_if(_InputIterator __first, _InputIterator __last, 185132720Skan _Predicate __pred, input_iterator_tag) 18697403Sobrien { 18797403Sobrien while (__first != __last && !__pred(*__first)) 18897403Sobrien ++__first; 18997403Sobrien return __first; 19097403Sobrien } 19197403Sobrien 19297403Sobrien /** 19397403Sobrien * @if maint 19497403Sobrien * This is an overload used by find() for the RAI case. 19597403Sobrien * @endif 19697403Sobrien */ 197132720Skan template<typename _RandomAccessIterator, typename _Tp> 198132720Skan _RandomAccessIterator 199132720Skan find(_RandomAccessIterator __first, _RandomAccessIterator __last, 200132720Skan const _Tp& __val, random_access_iterator_tag) 20197403Sobrien { 202132720Skan typename iterator_traits<_RandomAccessIterator>::difference_type 203132720Skan __trip_count = (__last - __first) >> 2; 20497403Sobrien 205132720Skan for ( ; __trip_count > 0 ; --__trip_count) 206132720Skan { 207132720Skan if (*__first == __val) 208132720Skan return __first; 209132720Skan ++__first; 21097403Sobrien 211132720Skan if (*__first == __val) 212132720Skan return __first; 213132720Skan ++__first; 21497403Sobrien 215132720Skan if (*__first == __val) 216132720Skan return __first; 217132720Skan ++__first; 21897403Sobrien 219132720Skan if (*__first == __val) 220132720Skan return __first; 221132720Skan ++__first; 222132720Skan } 22397403Sobrien 224132720Skan switch (__last - __first) 225132720Skan { 226132720Skan case 3: 227132720Skan if (*__first == __val) 228132720Skan return __first; 229132720Skan ++__first; 230132720Skan case 2: 231132720Skan if (*__first == __val) 232132720Skan return __first; 233132720Skan ++__first; 234132720Skan case 1: 235132720Skan if (*__first == __val) 236132720Skan return __first; 237132720Skan ++__first; 238132720Skan case 0: 239132720Skan default: 240132720Skan return __last; 241132720Skan } 24297403Sobrien } 24397403Sobrien 24497403Sobrien /** 24597403Sobrien * @if maint 24697403Sobrien * This is an overload used by find_if() for the RAI case. 24797403Sobrien * @endif 24897403Sobrien */ 249132720Skan template<typename _RandomAccessIterator, typename _Predicate> 250132720Skan _RandomAccessIterator 251132720Skan find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, 252132720Skan _Predicate __pred, random_access_iterator_tag) 25397403Sobrien { 254132720Skan typename iterator_traits<_RandomAccessIterator>::difference_type 255132720Skan __trip_count = (__last - __first) >> 2; 25697403Sobrien 257132720Skan for ( ; __trip_count > 0 ; --__trip_count) 258132720Skan { 259132720Skan if (__pred(*__first)) 260132720Skan return __first; 261132720Skan ++__first; 26297403Sobrien 263132720Skan if (__pred(*__first)) 264132720Skan return __first; 265132720Skan ++__first; 26697403Sobrien 267132720Skan if (__pred(*__first)) 268132720Skan return __first; 269132720Skan ++__first; 27097403Sobrien 271132720Skan if (__pred(*__first)) 272132720Skan return __first; 273132720Skan ++__first; 274132720Skan } 27597403Sobrien 276132720Skan switch (__last - __first) 277132720Skan { 278132720Skan case 3: 279132720Skan if (__pred(*__first)) 280132720Skan return __first; 281132720Skan ++__first; 282132720Skan case 2: 283132720Skan if (__pred(*__first)) 284132720Skan return __first; 285132720Skan ++__first; 286132720Skan case 1: 287132720Skan if (__pred(*__first)) 288132720Skan return __first; 289132720Skan ++__first; 290132720Skan case 0: 291132720Skan default: 292132720Skan return __last; 293132720Skan } 29497403Sobrien } 29597403Sobrien 29697403Sobrien /** 29797403Sobrien * @brief Find the first occurrence of a value in a sequence. 29897403Sobrien * @param first An input iterator. 29997403Sobrien * @param last An input iterator. 30097403Sobrien * @param val The value to find. 30197403Sobrien * @return The first iterator @c i in the range @p [first,last) 30297403Sobrien * such that @c *i == @p val, or @p last if no such iterator exists. 30397403Sobrien */ 304132720Skan template<typename _InputIterator, typename _Tp> 305132720Skan inline _InputIterator 306132720Skan find(_InputIterator __first, _InputIterator __last, 30797403Sobrien const _Tp& __val) 30897403Sobrien { 30997403Sobrien // concept requirements 310132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 311132720Skan __glibcxx_function_requires(_EqualOpConcept< 312132720Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 313132720Skan __glibcxx_requires_valid_range(__first, __last); 314132720Skan return std::find(__first, __last, __val, 315132720Skan std::__iterator_category(__first)); 31697403Sobrien } 31797403Sobrien 31897403Sobrien /** 31997403Sobrien * @brief Find the first element in a sequence for which a predicate is true. 32097403Sobrien * @param first An input iterator. 32197403Sobrien * @param last An input iterator. 32297403Sobrien * @param pred A predicate. 32397403Sobrien * @return The first iterator @c i in the range @p [first,last) 32497403Sobrien * such that @p pred(*i) is true, or @p last if no such iterator exists. 32597403Sobrien */ 326132720Skan template<typename _InputIterator, typename _Predicate> 327132720Skan inline _InputIterator 328132720Skan find_if(_InputIterator __first, _InputIterator __last, 32997403Sobrien _Predicate __pred) 33097403Sobrien { 33197403Sobrien // concept requirements 332132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 333132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 334132720Skan typename iterator_traits<_InputIterator>::value_type>) 335132720Skan __glibcxx_requires_valid_range(__first, __last); 336132720Skan return std::find_if(__first, __last, __pred, 337132720Skan std::__iterator_category(__first)); 33897403Sobrien } 33997403Sobrien 34097403Sobrien /** 34197403Sobrien * @brief Find two adjacent values in a sequence that are equal. 34297403Sobrien * @param first A forward iterator. 34397403Sobrien * @param last A forward iterator. 34497403Sobrien * @return The first iterator @c i such that @c i and @c i+1 are both 34597403Sobrien * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 34697403Sobrien * or @p last if no such iterator exists. 34797403Sobrien */ 348132720Skan template<typename _ForwardIterator> 349132720Skan _ForwardIterator 350132720Skan adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 35197403Sobrien { 35297403Sobrien // concept requirements 353132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 354132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 355132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 356132720Skan __glibcxx_requires_valid_range(__first, __last); 35797403Sobrien if (__first == __last) 35897403Sobrien return __last; 359132720Skan _ForwardIterator __next = __first; 360132720Skan while(++__next != __last) 361132720Skan { 362132720Skan if (*__first == *__next) 363132720Skan return __first; 364132720Skan __first = __next; 365132720Skan } 36697403Sobrien return __last; 36797403Sobrien } 36897403Sobrien 36997403Sobrien /** 37097403Sobrien * @brief Find two adjacent values in a sequence using a predicate. 37197403Sobrien * @param first A forward iterator. 37297403Sobrien * @param last A forward iterator. 37397403Sobrien * @param binary_pred A binary predicate. 37497403Sobrien * @return The first iterator @c i such that @c i and @c i+1 are both 37597403Sobrien * valid iterators in @p [first,last) and such that 37697403Sobrien * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 37797403Sobrien * exists. 37897403Sobrien */ 379132720Skan template<typename _ForwardIterator, typename _BinaryPredicate> 380132720Skan _ForwardIterator 381132720Skan adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 38297403Sobrien _BinaryPredicate __binary_pred) 38397403Sobrien { 38497403Sobrien // concept requirements 385132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 386132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 387132720Skan typename iterator_traits<_ForwardIterator>::value_type, 388132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 389132720Skan __glibcxx_requires_valid_range(__first, __last); 39097403Sobrien if (__first == __last) 39197403Sobrien return __last; 392132720Skan _ForwardIterator __next = __first; 393132720Skan while(++__next != __last) 394132720Skan { 395132720Skan if (__binary_pred(*__first, *__next)) 396132720Skan return __first; 397132720Skan __first = __next; 398132720Skan } 39997403Sobrien return __last; 40097403Sobrien } 40197403Sobrien 40297403Sobrien /** 40397403Sobrien * @brief Count the number of copies of a value in a sequence. 40497403Sobrien * @param first An input iterator. 40597403Sobrien * @param last An input iterator. 40697403Sobrien * @param value The value to be counted. 40797403Sobrien * @return The number of iterators @c i in the range @p [first,last) 40897403Sobrien * for which @c *i == @p value 40997403Sobrien */ 410132720Skan template<typename _InputIterator, typename _Tp> 411132720Skan typename iterator_traits<_InputIterator>::difference_type 412132720Skan count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 41397403Sobrien { 41497403Sobrien // concept requirements 415132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 416132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 417132720Skan typename iterator_traits<_InputIterator>::value_type >) 418132720Skan __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 419132720Skan __glibcxx_requires_valid_range(__first, __last); 420132720Skan typename iterator_traits<_InputIterator>::difference_type __n = 0; 42197403Sobrien for ( ; __first != __last; ++__first) 42297403Sobrien if (*__first == __value) 42397403Sobrien ++__n; 42497403Sobrien return __n; 42597403Sobrien } 42697403Sobrien 42797403Sobrien /** 42897403Sobrien * @brief Count the elements of a sequence for which a predicate is true. 42997403Sobrien * @param first An input iterator. 43097403Sobrien * @param last An input iterator. 43197403Sobrien * @param pred A predicate. 43297403Sobrien * @return The number of iterators @c i in the range @p [first,last) 43397403Sobrien * for which @p pred(*i) is true. 43497403Sobrien */ 435132720Skan template<typename _InputIterator, typename _Predicate> 436132720Skan typename iterator_traits<_InputIterator>::difference_type 437132720Skan count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 43897403Sobrien { 43997403Sobrien // concept requirements 440132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 441132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 442132720Skan typename iterator_traits<_InputIterator>::value_type>) 443132720Skan __glibcxx_requires_valid_range(__first, __last); 444132720Skan typename iterator_traits<_InputIterator>::difference_type __n = 0; 44597403Sobrien for ( ; __first != __last; ++__first) 44697403Sobrien if (__pred(*__first)) 44797403Sobrien ++__n; 44897403Sobrien return __n; 44997403Sobrien } 45097403Sobrien 45197403Sobrien /** 45297403Sobrien * @brief Search a sequence for a matching sub-sequence. 45397403Sobrien * @param first1 A forward iterator. 45497403Sobrien * @param last1 A forward iterator. 45597403Sobrien * @param first2 A forward iterator. 45697403Sobrien * @param last2 A forward iterator. 45797403Sobrien * @return The first iterator @c i in the range 45897403Sobrien * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 45997403Sobrien * for each @c N in the range @p [0,last2-first2), or @p last1 if no 46097403Sobrien * such iterator exists. 46197403Sobrien * 46297403Sobrien * Searches the range @p [first1,last1) for a sub-sequence that compares 46397403Sobrien * equal value-by-value with the sequence given by @p [first2,last2) and 46497403Sobrien * returns an iterator to the first element of the sub-sequence, or 46597403Sobrien * @p last1 if the sub-sequence is not found. 46697403Sobrien * 46797403Sobrien * Because the sub-sequence must lie completely within the range 46897403Sobrien * @p [first1,last1) it must start at a position less than 46997403Sobrien * @p last1-(last2-first2) where @p last2-first2 is the length of the 47097403Sobrien * sub-sequence. 47197403Sobrien * This means that the returned iterator @c i will be in the range 47297403Sobrien * @p [first1,last1-(last2-first2)) 47397403Sobrien */ 474132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 475132720Skan _ForwardIterator1 476132720Skan search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 477132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2) 47897403Sobrien { 47997403Sobrien // concept requirements 480132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 481132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 482132720Skan __glibcxx_function_requires(_EqualOpConcept< 483132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 484132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 485132720Skan __glibcxx_requires_valid_range(__first1, __last1); 486132720Skan __glibcxx_requires_valid_range(__first2, __last2); 48797403Sobrien // Test for empty ranges 48897403Sobrien if (__first1 == __last1 || __first2 == __last2) 48997403Sobrien return __first1; 49097403Sobrien 49197403Sobrien // Test for a pattern of length 1. 492132720Skan _ForwardIterator2 __tmp(__first2); 49397403Sobrien ++__tmp; 49497403Sobrien if (__tmp == __last2) 495132720Skan return std::find(__first1, __last1, *__first2); 49697403Sobrien 49797403Sobrien // General case. 498132720Skan _ForwardIterator2 __p1, __p; 49997403Sobrien __p1 = __first2; ++__p1; 500132720Skan _ForwardIterator1 __current = __first1; 50197403Sobrien 502132720Skan while (__first1 != __last1) 503132720Skan { 504132720Skan __first1 = std::find(__first1, __last1, *__first2); 505132720Skan if (__first1 == __last1) 506132720Skan return __last1; 50797403Sobrien 508132720Skan __p = __p1; 509132720Skan __current = __first1; 51097403Sobrien if (++__current == __last1) 51197403Sobrien return __last1; 512132720Skan 513132720Skan while (*__current == *__p) 514132720Skan { 515132720Skan if (++__p == __last2) 516132720Skan return __first1; 517132720Skan if (++__current == __last1) 518132720Skan return __last1; 519132720Skan } 520132720Skan ++__first1; 52197403Sobrien } 52297403Sobrien return __first1; 52397403Sobrien } 52497403Sobrien 52597403Sobrien /** 52697403Sobrien * @brief Search a sequence for a matching sub-sequence using a predicate. 52797403Sobrien * @param first1 A forward iterator. 52897403Sobrien * @param last1 A forward iterator. 52997403Sobrien * @param first2 A forward iterator. 53097403Sobrien * @param last2 A forward iterator. 53197403Sobrien * @param predicate A binary predicate. 53297403Sobrien * @return The first iterator @c i in the range 53397403Sobrien * @p [first1,last1-(last2-first2)) such that 53497403Sobrien * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 53597403Sobrien * @p [0,last2-first2), or @p last1 if no such iterator exists. 53697403Sobrien * 53797403Sobrien * Searches the range @p [first1,last1) for a sub-sequence that compares 53897403Sobrien * equal value-by-value with the sequence given by @p [first2,last2), 53997403Sobrien * using @p predicate to determine equality, and returns an iterator 54097403Sobrien * to the first element of the sub-sequence, or @p last1 if no such 54197403Sobrien * iterator exists. 54297403Sobrien * 54397403Sobrien * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 54497403Sobrien */ 545132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2, 546132720Skan typename _BinaryPredicate> 547132720Skan _ForwardIterator1 548132720Skan search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 549132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 550132720Skan _BinaryPredicate __predicate) 55197403Sobrien { 55297403Sobrien // concept requirements 553132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 554132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 555132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 556132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 557132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 558132720Skan __glibcxx_requires_valid_range(__first1, __last1); 559132720Skan __glibcxx_requires_valid_range(__first2, __last2); 56097403Sobrien 56197403Sobrien // Test for empty ranges 56297403Sobrien if (__first1 == __last1 || __first2 == __last2) 56397403Sobrien return __first1; 56497403Sobrien 56597403Sobrien // Test for a pattern of length 1. 566132720Skan _ForwardIterator2 __tmp(__first2); 56797403Sobrien ++__tmp; 568132720Skan if (__tmp == __last2) 569132720Skan { 570132720Skan while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 571132720Skan ++__first1; 572132720Skan return __first1; 573132720Skan } 57497403Sobrien 57597403Sobrien // General case. 576132720Skan _ForwardIterator2 __p1, __p; 57797403Sobrien __p1 = __first2; ++__p1; 578132720Skan _ForwardIterator1 __current = __first1; 57997403Sobrien 580132720Skan while (__first1 != __last1) 581132720Skan { 582132720Skan while (__first1 != __last1) 583132720Skan { 584132720Skan if (__predicate(*__first1, *__first2)) 585132720Skan break; 586132720Skan ++__first1; 587132720Skan } 588132720Skan while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 589132720Skan ++__first1; 590132720Skan if (__first1 == __last1) 591132720Skan return __last1; 59297403Sobrien 593132720Skan __p = __p1; 594132720Skan __current = __first1; 59597403Sobrien if (++__current == __last1) 59697403Sobrien return __last1; 597132720Skan 598132720Skan while (__predicate(*__current, *__p)) 599132720Skan { 600132720Skan if (++__p == __last2) 601132720Skan return __first1; 602132720Skan if (++__current == __last1) 603132720Skan return __last1; 604132720Skan } 605132720Skan ++__first1; 60697403Sobrien } 60797403Sobrien return __first1; 60897403Sobrien } 60997403Sobrien 61097403Sobrien /** 61197403Sobrien * @brief Search a sequence for a number of consecutive values. 61297403Sobrien * @param first A forward iterator. 61397403Sobrien * @param last A forward iterator. 61497403Sobrien * @param count The number of consecutive values. 61597403Sobrien * @param val The value to find. 61697403Sobrien * @return The first iterator @c i in the range @p [first,last-count) 61797403Sobrien * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 61897403Sobrien * or @p last if no such iterator exists. 61997403Sobrien * 62097403Sobrien * Searches the range @p [first,last) for @p count consecutive elements 62197403Sobrien * equal to @p val. 62297403Sobrien */ 623132720Skan template<typename _ForwardIterator, typename _Integer, typename _Tp> 624132720Skan _ForwardIterator 625132720Skan search_n(_ForwardIterator __first, _ForwardIterator __last, 62697403Sobrien _Integer __count, const _Tp& __val) 62797403Sobrien { 62897403Sobrien // concept requirements 629132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 630132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 631132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 632132720Skan __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) 633132720Skan __glibcxx_requires_valid_range(__first, __last); 63497403Sobrien 63597403Sobrien if (__count <= 0) 63697403Sobrien return __first; 637132720Skan else 638132720Skan { 639132720Skan __first = std::find(__first, __last, __val); 640132720Skan while (__first != __last) 641132720Skan { 642132720Skan typename iterator_traits<_ForwardIterator>::difference_type 643132720Skan __n = __count; 644132720Skan _ForwardIterator __i = __first; 645132720Skan ++__i; 646132720Skan while (__i != __last && __n != 1 && *__i == __val) 647132720Skan { 648132720Skan ++__i; 649132720Skan --__n; 650132720Skan } 651132720Skan if (__n == 1) 652132720Skan return __first; 653132720Skan else 654132720Skan __first = std::find(__i, __last, __val); 655132720Skan } 656132720Skan return __last; 65797403Sobrien } 65897403Sobrien } 65997403Sobrien 66097403Sobrien /** 66197403Sobrien * @brief Search a sequence for a number of consecutive values using a 66297403Sobrien * predicate. 66397403Sobrien * @param first A forward iterator. 66497403Sobrien * @param last A forward iterator. 66597403Sobrien * @param count The number of consecutive values. 66697403Sobrien * @param val The value to find. 66797403Sobrien * @param binary_pred A binary predicate. 66897403Sobrien * @return The first iterator @c i in the range @p [first,last-count) 66997403Sobrien * such that @p binary_pred(*(i+N),val) is true for each @c N in the 67097403Sobrien * range @p [0,count), or @p last if no such iterator exists. 67197403Sobrien * 67297403Sobrien * Searches the range @p [first,last) for @p count consecutive elements 67397403Sobrien * for which the predicate returns true. 67497403Sobrien */ 675132720Skan template<typename _ForwardIterator, typename _Integer, typename _Tp, 676132720Skan typename _BinaryPredicate> 677132720Skan _ForwardIterator 678132720Skan search_n(_ForwardIterator __first, _ForwardIterator __last, 67997403Sobrien _Integer __count, const _Tp& __val, 680132720Skan _BinaryPredicate __binary_pred) 68197403Sobrien { 68297403Sobrien // concept requirements 683132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 684132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 685132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 686132720Skan __glibcxx_requires_valid_range(__first, __last); 68797403Sobrien 68897403Sobrien if (__count <= 0) 68997403Sobrien return __first; 690132720Skan else 691132720Skan { 692132720Skan while (__first != __last) 693132720Skan { 694132720Skan if (__binary_pred(*__first, __val)) 69597403Sobrien break; 696132720Skan ++__first; 697132720Skan } 698132720Skan while (__first != __last) 699132720Skan { 700132720Skan typename iterator_traits<_ForwardIterator>::difference_type 701132720Skan __n = __count; 702132720Skan _ForwardIterator __i = __first; 70397403Sobrien ++__i; 704132720Skan while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) 705132720Skan { 706132720Skan ++__i; 707132720Skan --__n; 708132720Skan } 709132720Skan if (__n == 1) 710132720Skan return __first; 711132720Skan else 712132720Skan { 713132720Skan while (__i != __last) 714132720Skan { 715132720Skan if (__binary_pred(*__i, __val)) 716132720Skan break; 717132720Skan ++__i; 718132720Skan } 719132720Skan __first = __i; 720132720Skan } 72197403Sobrien } 722132720Skan return __last; 72397403Sobrien } 72497403Sobrien } 72597403Sobrien 72697403Sobrien /** 72797403Sobrien * @brief Swap the elements of two sequences. 72897403Sobrien * @param first1 A forward iterator. 72997403Sobrien * @param last1 A forward iterator. 73097403Sobrien * @param first2 A forward iterator. 73197403Sobrien * @return An iterator equal to @p first2+(last1-first1). 73297403Sobrien * 73397403Sobrien * Swaps each element in the range @p [first1,last1) with the 73497403Sobrien * corresponding element in the range @p [first2,(last1-first1)). 73597403Sobrien * The ranges must not overlap. 73697403Sobrien */ 737132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 738132720Skan _ForwardIterator2 739132720Skan swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 740132720Skan _ForwardIterator2 __first2) 74197403Sobrien { 74297403Sobrien // concept requirements 743132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 744132720Skan _ForwardIterator1>) 745132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 746132720Skan _ForwardIterator2>) 747132720Skan __glibcxx_function_requires(_ConvertibleConcept< 748132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 749132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 750132720Skan __glibcxx_function_requires(_ConvertibleConcept< 751132720Skan typename iterator_traits<_ForwardIterator2>::value_type, 752132720Skan typename iterator_traits<_ForwardIterator1>::value_type>) 753132720Skan __glibcxx_requires_valid_range(__first1, __last1); 75497403Sobrien 75597403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2) 756132720Skan std::iter_swap(__first1, __first2); 75797403Sobrien return __first2; 75897403Sobrien } 75997403Sobrien 76097403Sobrien /** 76197403Sobrien * @brief Perform an operation on a sequence. 76297403Sobrien * @param first An input iterator. 76397403Sobrien * @param last An input iterator. 76497403Sobrien * @param result An output iterator. 76597403Sobrien * @param unary_op A unary operator. 76697403Sobrien * @return An output iterator equal to @p result+(last-first). 76797403Sobrien * 76897403Sobrien * Applies the operator to each element in the input range and assigns 76997403Sobrien * the results to successive elements of the output sequence. 77097403Sobrien * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 77197403Sobrien * range @p [0,last-first). 77297403Sobrien * 77397403Sobrien * @p unary_op must not alter its argument. 77497403Sobrien */ 775132720Skan template<typename _InputIterator, typename _OutputIterator, 776132720Skan typename _UnaryOperation> 777132720Skan _OutputIterator 778132720Skan transform(_InputIterator __first, _InputIterator __last, 779132720Skan _OutputIterator __result, _UnaryOperation __unary_op) 78097403Sobrien { 78197403Sobrien // concept requirements 782132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 783132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 78497403Sobrien // "the type returned by a _UnaryOperation" 78597403Sobrien __typeof__(__unary_op(*__first))>) 786132720Skan __glibcxx_requires_valid_range(__first, __last); 78797403Sobrien 78897403Sobrien for ( ; __first != __last; ++__first, ++__result) 78997403Sobrien *__result = __unary_op(*__first); 79097403Sobrien return __result; 79197403Sobrien } 79297403Sobrien 79397403Sobrien /** 79497403Sobrien * @brief Perform an operation on corresponding elements of two sequences. 79597403Sobrien * @param first1 An input iterator. 79697403Sobrien * @param last1 An input iterator. 79797403Sobrien * @param first2 An input iterator. 79897403Sobrien * @param result An output iterator. 79997403Sobrien * @param binary_op A binary operator. 80097403Sobrien * @return An output iterator equal to @p result+(last-first). 80197403Sobrien * 80297403Sobrien * Applies the operator to the corresponding elements in the two 80397403Sobrien * input ranges and assigns the results to successive elements of the 80497403Sobrien * output sequence. 80597403Sobrien * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 80697403Sobrien * @c N in the range @p [0,last1-first1). 80797403Sobrien * 80897403Sobrien * @p binary_op must not alter either of its arguments. 80997403Sobrien */ 810132720Skan template<typename _InputIterator1, typename _InputIterator2, 811132720Skan typename _OutputIterator, typename _BinaryOperation> 812132720Skan _OutputIterator 813132720Skan transform(_InputIterator1 __first1, _InputIterator1 __last1, 814132720Skan _InputIterator2 __first2, _OutputIterator __result, 81597403Sobrien _BinaryOperation __binary_op) 81697403Sobrien { 81797403Sobrien // concept requirements 818132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 819132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 820132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 82197403Sobrien // "the type returned by a _BinaryOperation" 82297403Sobrien __typeof__(__binary_op(*__first1,*__first2))>) 823132720Skan __glibcxx_requires_valid_range(__first1, __last1); 82497403Sobrien 82597403Sobrien for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 82697403Sobrien *__result = __binary_op(*__first1, *__first2); 82797403Sobrien return __result; 82897403Sobrien } 82997403Sobrien 83097403Sobrien /** 83197403Sobrien * @brief Replace each occurrence of one value in a sequence with another 83297403Sobrien * value. 83397403Sobrien * @param first A forward iterator. 83497403Sobrien * @param last A forward iterator. 83597403Sobrien * @param old_value The value to be replaced. 83697403Sobrien * @param new_value The replacement value. 83797403Sobrien * @return replace() returns no value. 83897403Sobrien * 83997403Sobrien * For each iterator @c i in the range @p [first,last) if @c *i == 84097403Sobrien * @p old_value then the assignment @c *i = @p new_value is performed. 84197403Sobrien */ 842132720Skan template<typename _ForwardIterator, typename _Tp> 84397403Sobrien void 844132720Skan replace(_ForwardIterator __first, _ForwardIterator __last, 84597403Sobrien const _Tp& __old_value, const _Tp& __new_value) 84697403Sobrien { 84797403Sobrien // concept requirements 848132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 849132720Skan _ForwardIterator>) 850132720Skan __glibcxx_function_requires(_EqualOpConcept< 851132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 852132720Skan __glibcxx_function_requires(_ConvertibleConcept<_Tp, 853132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 854132720Skan __glibcxx_requires_valid_range(__first, __last); 85597403Sobrien 85697403Sobrien for ( ; __first != __last; ++__first) 85797403Sobrien if (*__first == __old_value) 85897403Sobrien *__first = __new_value; 85997403Sobrien } 86097403Sobrien 86197403Sobrien /** 86297403Sobrien * @brief Replace each value in a sequence for which a predicate returns 86397403Sobrien * true with another value. 86497403Sobrien * @param first A forward iterator. 86597403Sobrien * @param last A forward iterator. 86697403Sobrien * @param pred A predicate. 86797403Sobrien * @param new_value The replacement value. 86897403Sobrien * @return replace_if() returns no value. 86997403Sobrien * 87097403Sobrien * For each iterator @c i in the range @p [first,last) if @p pred(*i) 87197403Sobrien * is true then the assignment @c *i = @p new_value is performed. 87297403Sobrien */ 873132720Skan template<typename _ForwardIterator, typename _Predicate, typename _Tp> 87497403Sobrien void 875132720Skan replace_if(_ForwardIterator __first, _ForwardIterator __last, 87697403Sobrien _Predicate __pred, const _Tp& __new_value) 87797403Sobrien { 87897403Sobrien // concept requirements 879132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 880132720Skan _ForwardIterator>) 881132720Skan __glibcxx_function_requires(_ConvertibleConcept<_Tp, 882132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 883132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 884132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 885132720Skan __glibcxx_requires_valid_range(__first, __last); 88697403Sobrien 88797403Sobrien for ( ; __first != __last; ++__first) 88897403Sobrien if (__pred(*__first)) 88997403Sobrien *__first = __new_value; 89097403Sobrien } 89197403Sobrien 89297403Sobrien /** 89397403Sobrien * @brief Copy a sequence, replacing each element of one value with another 89497403Sobrien * value. 89597403Sobrien * @param first An input iterator. 89697403Sobrien * @param last An input iterator. 89797403Sobrien * @param result An output iterator. 89897403Sobrien * @param old_value The value to be replaced. 89997403Sobrien * @param new_value The replacement value. 90097403Sobrien * @return The end of the output sequence, @p result+(last-first). 90197403Sobrien * 90297403Sobrien * Copies each element in the input range @p [first,last) to the 90397403Sobrien * output range @p [result,result+(last-first)) replacing elements 90497403Sobrien * equal to @p old_value with @p new_value. 90597403Sobrien */ 906132720Skan template<typename _InputIterator, typename _OutputIterator, typename _Tp> 907132720Skan _OutputIterator 908132720Skan replace_copy(_InputIterator __first, _InputIterator __last, 909132720Skan _OutputIterator __result, 91097403Sobrien const _Tp& __old_value, const _Tp& __new_value) 91197403Sobrien { 91297403Sobrien // concept requirements 913132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 914132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 915132720Skan typename iterator_traits<_InputIterator>::value_type>) 916132720Skan __glibcxx_function_requires(_EqualOpConcept< 917132720Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 918132720Skan __glibcxx_requires_valid_range(__first, __last); 91997403Sobrien 92097403Sobrien for ( ; __first != __last; ++__first, ++__result) 92197403Sobrien *__result = *__first == __old_value ? __new_value : *__first; 92297403Sobrien return __result; 92397403Sobrien } 92497403Sobrien 92597403Sobrien /** 92697403Sobrien * @brief Copy a sequence, replacing each value for which a predicate 92797403Sobrien * returns true with another value. 92897403Sobrien * @param first An input iterator. 92997403Sobrien * @param last An input iterator. 93097403Sobrien * @param result An output iterator. 93197403Sobrien * @param pred A predicate. 93297403Sobrien * @param new_value The replacement value. 93397403Sobrien * @return The end of the output sequence, @p result+(last-first). 93497403Sobrien * 93597403Sobrien * Copies each element in the range @p [first,last) to the range 93697403Sobrien * @p [result,result+(last-first)) replacing elements for which 93797403Sobrien * @p pred returns true with @p new_value. 93897403Sobrien */ 939132720Skan template<typename _InputIterator, typename _OutputIterator, 940132720Skan typename _Predicate, typename _Tp> 941132720Skan _OutputIterator 942132720Skan replace_copy_if(_InputIterator __first, _InputIterator __last, 943132720Skan _OutputIterator __result, 94497403Sobrien _Predicate __pred, const _Tp& __new_value) 94597403Sobrien { 94697403Sobrien // concept requirements 947132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 948132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 949132720Skan typename iterator_traits<_InputIterator>::value_type>) 950132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 951132720Skan typename iterator_traits<_InputIterator>::value_type>) 952132720Skan __glibcxx_requires_valid_range(__first, __last); 95397403Sobrien 95497403Sobrien for ( ; __first != __last; ++__first, ++__result) 95597403Sobrien *__result = __pred(*__first) ? __new_value : *__first; 95697403Sobrien return __result; 95797403Sobrien } 95897403Sobrien 95997403Sobrien /** 96097403Sobrien * @brief Assign the result of a function object to each value in a 96197403Sobrien * sequence. 96297403Sobrien * @param first A forward iterator. 96397403Sobrien * @param last A forward iterator. 96497403Sobrien * @param gen A function object taking no arguments. 96597403Sobrien * @return generate() returns no value. 96697403Sobrien * 96797403Sobrien * Performs the assignment @c *i = @p gen() for each @c i in the range 96897403Sobrien * @p [first,last). 96997403Sobrien */ 970132720Skan template<typename _ForwardIterator, typename _Generator> 97197403Sobrien void 972132720Skan generate(_ForwardIterator __first, _ForwardIterator __last, 973132720Skan _Generator __gen) 97497403Sobrien { 97597403Sobrien // concept requirements 976132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 977132720Skan __glibcxx_function_requires(_GeneratorConcept<_Generator, 978132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 979132720Skan __glibcxx_requires_valid_range(__first, __last); 98097403Sobrien 98197403Sobrien for ( ; __first != __last; ++__first) 98297403Sobrien *__first = __gen(); 98397403Sobrien } 98497403Sobrien 98597403Sobrien /** 98697403Sobrien * @brief Assign the result of a function object to each value in a 98797403Sobrien * sequence. 98897403Sobrien * @param first A forward iterator. 98997403Sobrien * @param n The length of the sequence. 99097403Sobrien * @param gen A function object taking no arguments. 99197403Sobrien * @return The end of the sequence, @p first+n 99297403Sobrien * 99397403Sobrien * Performs the assignment @c *i = @p gen() for each @c i in the range 99497403Sobrien * @p [first,first+n). 99597403Sobrien */ 996132720Skan template<typename _OutputIterator, typename _Size, typename _Generator> 997132720Skan _OutputIterator 998132720Skan generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 99997403Sobrien { 100097403Sobrien // concept requirements 1001132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 100297403Sobrien // "the type returned by a _Generator" 1003132720Skan __typeof__(__gen())>) 100497403Sobrien 100597403Sobrien for ( ; __n > 0; --__n, ++__first) 100697403Sobrien *__first = __gen(); 100797403Sobrien return __first; 100897403Sobrien } 100997403Sobrien 101097403Sobrien /** 101197403Sobrien * @brief Copy a sequence, removing elements of a given value. 101297403Sobrien * @param first An input iterator. 101397403Sobrien * @param last An input iterator. 101497403Sobrien * @param result An output iterator. 101597403Sobrien * @param value The value to be removed. 101697403Sobrien * @return An iterator designating the end of the resulting sequence. 101797403Sobrien * 101897403Sobrien * Copies each element in the range @p [first,last) not equal to @p value 101997403Sobrien * to the range beginning at @p result. 102097403Sobrien * remove_copy() is stable, so the relative order of elements that are 102197403Sobrien * copied is unchanged. 102297403Sobrien */ 1023132720Skan template<typename _InputIterator, typename _OutputIterator, typename _Tp> 1024132720Skan _OutputIterator 1025132720Skan remove_copy(_InputIterator __first, _InputIterator __last, 1026132720Skan _OutputIterator __result, const _Tp& __value) 102797403Sobrien { 102897403Sobrien // concept requirements 1029132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1030132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1031132720Skan typename iterator_traits<_InputIterator>::value_type>) 1032132720Skan __glibcxx_function_requires(_EqualOpConcept< 1033132720Skan typename iterator_traits<_InputIterator>::value_type, _Tp>) 1034132720Skan __glibcxx_requires_valid_range(__first, __last); 103597403Sobrien 103697403Sobrien for ( ; __first != __last; ++__first) 1037132720Skan if (!(*__first == __value)) 1038132720Skan { 1039132720Skan *__result = *__first; 1040132720Skan ++__result; 1041132720Skan } 104297403Sobrien return __result; 104397403Sobrien } 104497403Sobrien 104597403Sobrien /** 104697403Sobrien * @brief Copy a sequence, removing elements for which a predicate is true. 104797403Sobrien * @param first An input iterator. 104897403Sobrien * @param last An input iterator. 104997403Sobrien * @param result An output iterator. 105097403Sobrien * @param pred A predicate. 105197403Sobrien * @return An iterator designating the end of the resulting sequence. 105297403Sobrien * 105397403Sobrien * Copies each element in the range @p [first,last) for which 105497403Sobrien * @p pred returns true to the range beginning at @p result. 105597403Sobrien * 105697403Sobrien * remove_copy_if() is stable, so the relative order of elements that are 105797403Sobrien * copied is unchanged. 105897403Sobrien */ 1059132720Skan template<typename _InputIterator, typename _OutputIterator, 1060132720Skan typename _Predicate> 1061132720Skan _OutputIterator 1062132720Skan remove_copy_if(_InputIterator __first, _InputIterator __last, 1063132720Skan _OutputIterator __result, _Predicate __pred) 106497403Sobrien { 106597403Sobrien // concept requirements 1066132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1067132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1068132720Skan typename iterator_traits<_InputIterator>::value_type>) 1069132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1070132720Skan typename iterator_traits<_InputIterator>::value_type>) 1071132720Skan __glibcxx_requires_valid_range(__first, __last); 107297403Sobrien 107397403Sobrien for ( ; __first != __last; ++__first) 1074132720Skan if (!__pred(*__first)) 1075132720Skan { 1076132720Skan *__result = *__first; 1077132720Skan ++__result; 1078132720Skan } 107997403Sobrien return __result; 108097403Sobrien } 108197403Sobrien 108297403Sobrien /** 108397403Sobrien * @brief Remove elements from a sequence. 108497403Sobrien * @param first An input iterator. 108597403Sobrien * @param last An input iterator. 108697403Sobrien * @param value The value to be removed. 108797403Sobrien * @return An iterator designating the end of the resulting sequence. 108897403Sobrien * 108997403Sobrien * All elements equal to @p value are removed from the range 109097403Sobrien * @p [first,last). 109197403Sobrien * 109297403Sobrien * remove() is stable, so the relative order of elements that are 109397403Sobrien * not removed is unchanged. 109497403Sobrien * 109597403Sobrien * Elements between the end of the resulting sequence and @p last 109697403Sobrien * are still present, but their value is unspecified. 109797403Sobrien */ 1098132720Skan template<typename _ForwardIterator, typename _Tp> 1099132720Skan _ForwardIterator 1100132720Skan remove(_ForwardIterator __first, _ForwardIterator __last, 110197403Sobrien const _Tp& __value) 110297403Sobrien { 110397403Sobrien // concept requirements 1104132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1105132720Skan _ForwardIterator>) 1106132720Skan __glibcxx_function_requires(_ConvertibleConcept<_Tp, 1107132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1108132720Skan __glibcxx_function_requires(_EqualOpConcept< 1109132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 1110132720Skan __glibcxx_requires_valid_range(__first, __last); 111197403Sobrien 1112132720Skan __first = std::find(__first, __last, __value); 1113132720Skan _ForwardIterator __i = __first; 111497403Sobrien return __first == __last ? __first 1115132720Skan : std::remove_copy(++__i, __last, 1116132720Skan __first, __value); 111797403Sobrien } 111897403Sobrien 111997403Sobrien /** 112097403Sobrien * @brief Remove elements from a sequence using a predicate. 112197403Sobrien * @param first A forward iterator. 112297403Sobrien * @param last A forward iterator. 112397403Sobrien * @param pred A predicate. 112497403Sobrien * @return An iterator designating the end of the resulting sequence. 112597403Sobrien * 112697403Sobrien * All elements for which @p pred returns true are removed from the range 112797403Sobrien * @p [first,last). 112897403Sobrien * 112997403Sobrien * remove_if() is stable, so the relative order of elements that are 113097403Sobrien * not removed is unchanged. 113197403Sobrien * 113297403Sobrien * Elements between the end of the resulting sequence and @p last 113397403Sobrien * are still present, but their value is unspecified. 113497403Sobrien */ 1135132720Skan template<typename _ForwardIterator, typename _Predicate> 1136132720Skan _ForwardIterator 1137132720Skan remove_if(_ForwardIterator __first, _ForwardIterator __last, 113897403Sobrien _Predicate __pred) 113997403Sobrien { 114097403Sobrien // concept requirements 1141132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1142132720Skan _ForwardIterator>) 1143132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1144132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1145132720Skan __glibcxx_requires_valid_range(__first, __last); 114697403Sobrien 1147132720Skan __first = std::find_if(__first, __last, __pred); 1148132720Skan _ForwardIterator __i = __first; 114997403Sobrien return __first == __last ? __first 1150132720Skan : std::remove_copy_if(++__i, __last, 1151132720Skan __first, __pred); 115297403Sobrien } 115397403Sobrien 115497403Sobrien /** 115597403Sobrien * @if maint 1156132720Skan * This is an uglified unique_copy(_InputIterator, _InputIterator, 1157132720Skan * _OutputIterator) 115897403Sobrien * overloaded for output iterators. 115997403Sobrien * @endif 116097403Sobrien */ 1161132720Skan template<typename _InputIterator, typename _OutputIterator> 1162132720Skan _OutputIterator 1163132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1164132720Skan _OutputIterator __result, 116597403Sobrien output_iterator_tag) 116697403Sobrien { 116797403Sobrien // concept requirements -- taken care of in dispatching function 1168132720Skan typename iterator_traits<_InputIterator>::value_type __value = *__first; 116997403Sobrien *__result = __value; 117097403Sobrien while (++__first != __last) 1171132720Skan if (!(__value == *__first)) 1172132720Skan { 1173132720Skan __value = *__first; 1174132720Skan *++__result = __value; 1175132720Skan } 117697403Sobrien return ++__result; 117797403Sobrien } 117897403Sobrien 117997403Sobrien /** 118097403Sobrien * @if maint 1181132720Skan * This is an uglified unique_copy(_InputIterator, _InputIterator, 1182132720Skan * _OutputIterator) 118397403Sobrien * overloaded for forward iterators. 118497403Sobrien * @endif 118597403Sobrien */ 1186132720Skan template<typename _InputIterator, typename _ForwardIterator> 1187132720Skan _ForwardIterator 1188132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1189132720Skan _ForwardIterator __result, 119097403Sobrien forward_iterator_tag) 119197403Sobrien { 119297403Sobrien // concept requirements -- taken care of in dispatching function 119397403Sobrien *__result = *__first; 119497403Sobrien while (++__first != __last) 119597403Sobrien if (!(*__result == *__first)) 119697403Sobrien *++__result = *__first; 119797403Sobrien return ++__result; 119897403Sobrien } 119997403Sobrien 120097403Sobrien /** 120197403Sobrien * @if maint 120297403Sobrien * This is an uglified 1203132720Skan * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1204132720Skan * _BinaryPredicate) 120597403Sobrien * overloaded for output iterators. 120697403Sobrien * @endif 120797403Sobrien */ 1208132720Skan template<typename _InputIterator, typename _OutputIterator, 1209132720Skan typename _BinaryPredicate> 1210132720Skan _OutputIterator 1211132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1212132720Skan _OutputIterator __result, 121397403Sobrien _BinaryPredicate __binary_pred, 121497403Sobrien output_iterator_tag) 121597403Sobrien { 121697403Sobrien // concept requirements -- iterators already checked 1217132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1218132720Skan typename iterator_traits<_InputIterator>::value_type, 1219132720Skan typename iterator_traits<_InputIterator>::value_type>) 122097403Sobrien 1221132720Skan typename iterator_traits<_InputIterator>::value_type __value = *__first; 122297403Sobrien *__result = __value; 122397403Sobrien while (++__first != __last) 1224132720Skan if (!__binary_pred(__value, *__first)) 1225132720Skan { 1226132720Skan __value = *__first; 1227132720Skan *++__result = __value; 1228132720Skan } 122997403Sobrien return ++__result; 123097403Sobrien } 123197403Sobrien 123297403Sobrien /** 123397403Sobrien * @if maint 123497403Sobrien * This is an uglified 1235132720Skan * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1236132720Skan * _BinaryPredicate) 123797403Sobrien * overloaded for forward iterators. 123897403Sobrien * @endif 123997403Sobrien */ 1240132720Skan template<typename _InputIterator, typename _ForwardIterator, 1241132720Skan typename _BinaryPredicate> 1242132720Skan _ForwardIterator 1243132720Skan __unique_copy(_InputIterator __first, _InputIterator __last, 1244132720Skan _ForwardIterator __result, 124597403Sobrien _BinaryPredicate __binary_pred, 124697403Sobrien forward_iterator_tag) 124797403Sobrien { 124897403Sobrien // concept requirements -- iterators already checked 1249132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1250132720Skan typename iterator_traits<_ForwardIterator>::value_type, 1251132720Skan typename iterator_traits<_InputIterator>::value_type>) 125297403Sobrien 125397403Sobrien *__result = *__first; 125497403Sobrien while (++__first != __last) 125597403Sobrien if (!__binary_pred(*__result, *__first)) *++__result = *__first; 125697403Sobrien return ++__result; 125797403Sobrien } 125897403Sobrien 125997403Sobrien /** 1260132720Skan * @brief Copy a sequence, removing consecutive duplicate values. 1261132720Skan * @param first An input iterator. 1262132720Skan * @param last An input iterator. 1263132720Skan * @param result An output iterator. 1264132720Skan * @return An iterator designating the end of the resulting sequence. 1265132720Skan * 1266132720Skan * Copies each element in the range @p [first,last) to the range 1267132720Skan * beginning at @p result, except that only the first element is copied 1268132720Skan * from groups of consecutive elements that compare equal. 1269132720Skan * unique_copy() is stable, so the relative order of elements that are 1270132720Skan * copied is unchanged. 1271132720Skan */ 1272132720Skan template<typename _InputIterator, typename _OutputIterator> 1273132720Skan inline _OutputIterator 1274132720Skan unique_copy(_InputIterator __first, _InputIterator __last, 1275132720Skan _OutputIterator __result) 1276132720Skan { 1277132720Skan // concept requirements 1278132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1279132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1280132720Skan typename iterator_traits<_InputIterator>::value_type>) 1281132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 1282132720Skan typename iterator_traits<_InputIterator>::value_type>) 1283132720Skan __glibcxx_requires_valid_range(__first, __last); 1284132720Skan 1285132720Skan typedef typename iterator_traits<_OutputIterator>::iterator_category 1286132720Skan _IterType; 1287132720Skan 1288132720Skan if (__first == __last) return __result; 1289132720Skan return std::__unique_copy(__first, __last, __result, _IterType()); 1290132720Skan } 1291132720Skan 1292132720Skan /** 129397403Sobrien * @brief Copy a sequence, removing consecutive values using a predicate. 129497403Sobrien * @param first An input iterator. 129597403Sobrien * @param last An input iterator. 129697403Sobrien * @param result An output iterator. 129797403Sobrien * @param binary_pred A binary predicate. 129897403Sobrien * @return An iterator designating the end of the resulting sequence. 129997403Sobrien * 130097403Sobrien * Copies each element in the range @p [first,last) to the range 130197403Sobrien * beginning at @p result, except that only the first element is copied 130297403Sobrien * from groups of consecutive elements for which @p binary_pred returns 130397403Sobrien * true. 130497403Sobrien * unique_copy() is stable, so the relative order of elements that are 130597403Sobrien * copied is unchanged. 130697403Sobrien */ 1307132720Skan template<typename _InputIterator, typename _OutputIterator, 1308132720Skan typename _BinaryPredicate> 1309132720Skan inline _OutputIterator 1310132720Skan unique_copy(_InputIterator __first, _InputIterator __last, 1311132720Skan _OutputIterator __result, 131297403Sobrien _BinaryPredicate __binary_pred) 131397403Sobrien { 131497403Sobrien // concept requirements -- predicates checked later 1315132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1316132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1317132720Skan typename iterator_traits<_InputIterator>::value_type>) 1318132720Skan __glibcxx_requires_valid_range(__first, __last); 131997403Sobrien 1320132720Skan typedef typename iterator_traits<_OutputIterator>::iterator_category 1321132720Skan _IterType; 132297403Sobrien 132397403Sobrien if (__first == __last) return __result; 1324132720Skan return std::__unique_copy(__first, __last, __result, 1325132720Skan __binary_pred, _IterType()); 132697403Sobrien } 132797403Sobrien 132897403Sobrien /** 132997403Sobrien * @brief Remove consecutive duplicate values from a sequence. 133097403Sobrien * @param first A forward iterator. 133197403Sobrien * @param last A forward iterator. 133297403Sobrien * @return An iterator designating the end of the resulting sequence. 133397403Sobrien * 133497403Sobrien * Removes all but the first element from each group of consecutive 133597403Sobrien * values that compare equal. 133697403Sobrien * unique() is stable, so the relative order of elements that are 133797403Sobrien * not removed is unchanged. 133897403Sobrien * Elements between the end of the resulting sequence and @p last 133997403Sobrien * are still present, but their value is unspecified. 134097403Sobrien */ 1341132720Skan template<typename _ForwardIterator> 1342132720Skan _ForwardIterator 1343132720Skan unique(_ForwardIterator __first, _ForwardIterator __last) 134497403Sobrien { 1345132720Skan // concept requirements 1346132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1347132720Skan _ForwardIterator>) 1348132720Skan __glibcxx_function_requires(_EqualityComparableConcept< 1349132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1350132720Skan __glibcxx_requires_valid_range(__first, __last); 135197403Sobrien 1352132720Skan // Skip the beginning, if already unique. 1353132720Skan __first = std::adjacent_find(__first, __last); 1354132720Skan if (__first == __last) 1355132720Skan return __last; 1356132720Skan 1357132720Skan // Do the real copy work. 1358132720Skan _ForwardIterator __dest = __first; 1359132720Skan ++__first; 1360132720Skan while (++__first != __last) 1361132720Skan if (!(*__dest == *__first)) 1362132720Skan *++__dest = *__first; 1363132720Skan return ++__dest; 136497403Sobrien } 136597403Sobrien 136697403Sobrien /** 136797403Sobrien * @brief Remove consecutive values from a sequence using a predicate. 136897403Sobrien * @param first A forward iterator. 136997403Sobrien * @param last A forward iterator. 137097403Sobrien * @param binary_pred A binary predicate. 137197403Sobrien * @return An iterator designating the end of the resulting sequence. 137297403Sobrien * 137397403Sobrien * Removes all but the first element from each group of consecutive 137497403Sobrien * values for which @p binary_pred returns true. 137597403Sobrien * unique() is stable, so the relative order of elements that are 137697403Sobrien * not removed is unchanged. 137797403Sobrien * Elements between the end of the resulting sequence and @p last 137897403Sobrien * are still present, but their value is unspecified. 137997403Sobrien */ 1380132720Skan template<typename _ForwardIterator, typename _BinaryPredicate> 1381132720Skan _ForwardIterator 1382132720Skan unique(_ForwardIterator __first, _ForwardIterator __last, 138397403Sobrien _BinaryPredicate __binary_pred) 138497403Sobrien { 138597403Sobrien // concept requirements 1386132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1387132720Skan _ForwardIterator>) 1388132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1389132720Skan typename iterator_traits<_ForwardIterator>::value_type, 1390132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1391132720Skan __glibcxx_requires_valid_range(__first, __last); 139297403Sobrien 1393132720Skan // Skip the beginning, if already unique. 1394132720Skan __first = std::adjacent_find(__first, __last, __binary_pred); 1395132720Skan if (__first == __last) 1396132720Skan return __last; 1397132720Skan 1398132720Skan // Do the real copy work. 1399132720Skan _ForwardIterator __dest = __first; 1400132720Skan ++__first; 1401132720Skan while (++__first != __last) 1402132720Skan if (!__binary_pred(*__dest, *__first)) 1403132720Skan *++__dest = *__first; 1404132720Skan return ++__dest; 140597403Sobrien } 140697403Sobrien 140797403Sobrien /** 140897403Sobrien * @if maint 1409132720Skan * This is an uglified reverse(_BidirectionalIterator, 1410132720Skan * _BidirectionalIterator) 141197403Sobrien * overloaded for bidirectional iterators. 141297403Sobrien * @endif 141397403Sobrien */ 1414132720Skan template<typename _BidirectionalIterator> 141597403Sobrien void 1416132720Skan __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, 141797403Sobrien bidirectional_iterator_tag) 141897403Sobrien { 1419132720Skan while (true) 1420132720Skan if (__first == __last || __first == --__last) 1421132720Skan return; 1422132720Skan else 1423132720Skan std::iter_swap(__first++, __last); 142497403Sobrien } 142597403Sobrien 142697403Sobrien /** 142797403Sobrien * @if maint 1428132720Skan * This is an uglified reverse(_BidirectionalIterator, 1429132720Skan * _BidirectionalIterator) 143097403Sobrien * overloaded for bidirectional iterators. 143197403Sobrien * @endif 143297403Sobrien */ 1433132720Skan template<typename _RandomAccessIterator> 143497403Sobrien void 1435132720Skan __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, 143697403Sobrien random_access_iterator_tag) 143797403Sobrien { 1438132720Skan while (__first < __last) 1439132720Skan std::iter_swap(__first++, --__last); 144097403Sobrien } 144197403Sobrien 144297403Sobrien /** 144397403Sobrien * @brief Reverse a sequence. 144497403Sobrien * @param first A bidirectional iterator. 144597403Sobrien * @param last A bidirectional iterator. 144697403Sobrien * @return reverse() returns no value. 144797403Sobrien * 144897403Sobrien * Reverses the order of the elements in the range @p [first,last), 144997403Sobrien * so that the first element becomes the last etc. 145097403Sobrien * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse() 145197403Sobrien * swaps @p *(first+i) and @p *(last-(i+1)) 145297403Sobrien */ 1453132720Skan template<typename _BidirectionalIterator> 145497403Sobrien inline void 1455132720Skan reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 145697403Sobrien { 1457132720Skan // concept requirements 1458132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1459132720Skan _BidirectionalIterator>) 1460132720Skan __glibcxx_requires_valid_range(__first, __last); 1461132720Skan std::__reverse(__first, __last, std::__iterator_category(__first)); 146297403Sobrien } 146397403Sobrien 146497403Sobrien /** 146597403Sobrien * @brief Copy a sequence, reversing its elements. 146697403Sobrien * @param first A bidirectional iterator. 146797403Sobrien * @param last A bidirectional iterator. 146897403Sobrien * @param result An output iterator. 146997403Sobrien * @return An iterator designating the end of the resulting sequence. 147097403Sobrien * 147197403Sobrien * Copies the elements in the range @p [first,last) to the range 147297403Sobrien * @p [result,result+(last-first)) such that the order of the 147397403Sobrien * elements is reversed. 147497403Sobrien * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy() 147597403Sobrien * performs the assignment @p *(result+(last-first)-i) = *(first+i). 147697403Sobrien * The ranges @p [first,last) and @p [result,result+(last-first)) 147797403Sobrien * must not overlap. 147897403Sobrien */ 1479132720Skan template<typename _BidirectionalIterator, typename _OutputIterator> 1480132720Skan _OutputIterator 1481132720Skan reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, 1482132720Skan _OutputIterator __result) 148397403Sobrien { 148497403Sobrien // concept requirements 1485132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 1486132720Skan _BidirectionalIterator>) 1487132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1488132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 1489132720Skan __glibcxx_requires_valid_range(__first, __last); 149097403Sobrien 1491132720Skan while (__first != __last) 1492132720Skan { 1493132720Skan --__last; 1494132720Skan *__result = *__last; 1495132720Skan ++__result; 1496132720Skan } 149797403Sobrien return __result; 149897403Sobrien } 149997403Sobrien 150097403Sobrien 150197403Sobrien /** 150297403Sobrien * @if maint 150397403Sobrien * This is a helper function for the rotate algorithm specialized on RAIs. 150497403Sobrien * It returns the greatest common divisor of two integer values. 150597403Sobrien * @endif 150697403Sobrien */ 150797403Sobrien template<typename _EuclideanRingElement> 150897403Sobrien _EuclideanRingElement 150997403Sobrien __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 151097403Sobrien { 1511132720Skan while (__n != 0) 1512132720Skan { 1513132720Skan _EuclideanRingElement __t = __m % __n; 1514132720Skan __m = __n; 1515132720Skan __n = __t; 1516132720Skan } 151797403Sobrien return __m; 151897403Sobrien } 151997403Sobrien 152097403Sobrien /** 152197403Sobrien * @if maint 152297403Sobrien * This is a helper function for the rotate algorithm. 152397403Sobrien * @endif 152497403Sobrien */ 1525132720Skan template<typename _ForwardIterator> 152697403Sobrien void 1527132720Skan __rotate(_ForwardIterator __first, 1528132720Skan _ForwardIterator __middle, 1529132720Skan _ForwardIterator __last, 153097403Sobrien forward_iterator_tag) 153197403Sobrien { 153297403Sobrien if ((__first == __middle) || (__last == __middle)) 153397403Sobrien return; 153497403Sobrien 1535132720Skan _ForwardIterator __first2 = __middle; 1536132720Skan do 1537132720Skan { 1538132720Skan swap(*__first++, *__first2++); 1539132720Skan if (__first == __middle) 1540132720Skan __middle = __first2; 1541132720Skan } 1542132720Skan while (__first2 != __last); 154397403Sobrien 154497403Sobrien __first2 = __middle; 154597403Sobrien 1546132720Skan while (__first2 != __last) 1547132720Skan { 1548132720Skan swap(*__first++, *__first2++); 1549132720Skan if (__first == __middle) 1550132720Skan __middle = __first2; 1551132720Skan else if (__first2 == __last) 1552132720Skan __first2 = __middle; 1553132720Skan } 155497403Sobrien } 155597403Sobrien 155697403Sobrien /** 155797403Sobrien * @if maint 155897403Sobrien * This is a helper function for the rotate algorithm. 155997403Sobrien * @endif 156097403Sobrien */ 1561132720Skan template<typename _BidirectionalIterator> 156297403Sobrien void 1563132720Skan __rotate(_BidirectionalIterator __first, 1564132720Skan _BidirectionalIterator __middle, 1565132720Skan _BidirectionalIterator __last, 156697403Sobrien bidirectional_iterator_tag) 156797403Sobrien { 156897403Sobrien // concept requirements 1569132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1570132720Skan _BidirectionalIterator>) 157197403Sobrien 157297403Sobrien if ((__first == __middle) || (__last == __middle)) 157397403Sobrien return; 157497403Sobrien 1575132720Skan std::__reverse(__first, __middle, bidirectional_iterator_tag()); 1576132720Skan std::__reverse(__middle, __last, bidirectional_iterator_tag()); 157797403Sobrien 157897403Sobrien while (__first != __middle && __middle != __last) 1579132720Skan swap(*__first++, *--__last); 158097403Sobrien 1581132720Skan if (__first == __middle) 1582132720Skan std::__reverse(__middle, __last, bidirectional_iterator_tag()); 1583132720Skan else 1584132720Skan std::__reverse(__first, __middle, bidirectional_iterator_tag()); 158597403Sobrien } 158697403Sobrien 158797403Sobrien /** 158897403Sobrien * @if maint 158997403Sobrien * This is a helper function for the rotate algorithm. 159097403Sobrien * @endif 159197403Sobrien */ 1592132720Skan template<typename _RandomAccessIterator> 159397403Sobrien void 1594132720Skan __rotate(_RandomAccessIterator __first, 1595132720Skan _RandomAccessIterator __middle, 1596132720Skan _RandomAccessIterator __last, 159797403Sobrien random_access_iterator_tag) 159897403Sobrien { 159997403Sobrien // concept requirements 1600132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1601132720Skan _RandomAccessIterator>) 160297403Sobrien 160397403Sobrien if ((__first == __middle) || (__last == __middle)) 160497403Sobrien return; 160597403Sobrien 1606132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 1607132720Skan _Distance; 1608132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 1609132720Skan _ValueType; 161097403Sobrien 1611132720Skan const _Distance __n = __last - __first; 1612132720Skan const _Distance __k = __middle - __first; 1613132720Skan const _Distance __l = __n - __k; 161497403Sobrien 1615132720Skan if (__k == __l) 1616132720Skan { 1617132720Skan std::swap_ranges(__first, __middle, __middle); 1618132720Skan return; 1619132720Skan } 162097403Sobrien 1621132720Skan const _Distance __d = __gcd(__n, __k); 162297403Sobrien 1623132720Skan for (_Distance __i = 0; __i < __d; __i++) 1624132720Skan { 1625132720Skan const _ValueType __tmp = *__first; 1626132720Skan _RandomAccessIterator __p = __first; 162797403Sobrien 1628132720Skan if (__k < __l) 1629132720Skan { 1630132720Skan for (_Distance __j = 0; __j < __l / __d; __j++) 1631132720Skan { 1632132720Skan if (__p > __first + __l) 1633132720Skan { 1634132720Skan *__p = *(__p - __l); 1635132720Skan __p -= __l; 1636132720Skan } 163797403Sobrien 1638132720Skan *__p = *(__p + __k); 1639132720Skan __p += __k; 1640132720Skan } 164197403Sobrien } 1642132720Skan else 1643132720Skan { 1644132720Skan for (_Distance __j = 0; __j < __k / __d - 1; __j ++) 1645132720Skan { 1646132720Skan if (__p < __last - __k) 1647132720Skan { 1648132720Skan *__p = *(__p + __k); 1649132720Skan __p += __k; 1650132720Skan } 1651132720Skan *__p = * (__p - __l); 1652132720Skan __p -= __l; 1653132720Skan } 1654132720Skan } 165597403Sobrien 1656132720Skan *__p = __tmp; 1657132720Skan ++__first; 165897403Sobrien } 165997403Sobrien } 166097403Sobrien 166197403Sobrien /** 166297403Sobrien * @brief Rotate the elements of a sequence. 166397403Sobrien * @param first A forward iterator. 166497403Sobrien * @param middle A forward iterator. 166597403Sobrien * @param last A forward iterator. 166697403Sobrien * @return Nothing. 166797403Sobrien * 166897403Sobrien * Rotates the elements of the range @p [first,last) by @p (middle-first) 166997403Sobrien * positions so that the element at @p middle is moved to @p first, the 167097403Sobrien * element at @p middle+1 is moved to @first+1 and so on for each element 167197403Sobrien * in the range @p [first,last). 167297403Sobrien * 167397403Sobrien * This effectively swaps the ranges @p [first,middle) and 167497403Sobrien * @p [middle,last). 167597403Sobrien * 167697403Sobrien * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for 167797403Sobrien * each @p n in the range @p [0,last-first). 167897403Sobrien */ 1679132720Skan template<typename _ForwardIterator> 168097403Sobrien inline void 1681132720Skan rotate(_ForwardIterator __first, _ForwardIterator __middle, 1682132720Skan _ForwardIterator __last) 168397403Sobrien { 168497403Sobrien // concept requirements 1685132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1686132720Skan _ForwardIterator>) 1687132720Skan __glibcxx_requires_valid_range(__first, __middle); 1688132720Skan __glibcxx_requires_valid_range(__middle, __last); 168997403Sobrien 1690132720Skan typedef typename iterator_traits<_ForwardIterator>::iterator_category 1691132720Skan _IterType; 1692132720Skan std::__rotate(__first, __middle, __last, _IterType()); 169397403Sobrien } 169497403Sobrien 169597403Sobrien /** 169697403Sobrien * @brief Copy a sequence, rotating its elements. 169797403Sobrien * @param first A forward iterator. 169897403Sobrien * @param middle A forward iterator. 169997403Sobrien * @param last A forward iterator. 170097403Sobrien * @param result An output iterator. 170197403Sobrien * @return An iterator designating the end of the resulting sequence. 170297403Sobrien * 170397403Sobrien * Copies the elements of the range @p [first,last) to the range 170497403Sobrien * beginning at @result, rotating the copied elements by @p (middle-first) 170597403Sobrien * positions so that the element at @p middle is moved to @p result, the 170697403Sobrien * element at @p middle+1 is moved to @result+1 and so on for each element 170797403Sobrien * in the range @p [first,last). 170897403Sobrien * 170997403Sobrien * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for 171097403Sobrien * each @p n in the range @p [0,last-first). 171197403Sobrien */ 1712132720Skan template<typename _ForwardIterator, typename _OutputIterator> 1713132720Skan _OutputIterator 1714132720Skan rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 1715132720Skan _ForwardIterator __last, _OutputIterator __result) 171697403Sobrien { 171797403Sobrien // concept requirements 1718132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1719132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1720132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1721132720Skan __glibcxx_requires_valid_range(__first, __middle); 1722132720Skan __glibcxx_requires_valid_range(__middle, __last); 172397403Sobrien 1724132720Skan return std::copy(__first, __middle, copy(__middle, __last, __result)); 172597403Sobrien } 172697403Sobrien 172797403Sobrien /** 172897403Sobrien * @brief Randomly shuffle the elements of a sequence. 172997403Sobrien * @param first A forward iterator. 173097403Sobrien * @param last A forward iterator. 173197403Sobrien * @return Nothing. 173297403Sobrien * 173397403Sobrien * Reorder the elements in the range @p [first,last) using a random 173497403Sobrien * distribution, so that every possible ordering of the sequence is 173597403Sobrien * equally likely. 173697403Sobrien */ 1737132720Skan template<typename _RandomAccessIterator> 173897403Sobrien inline void 1739132720Skan random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 174097403Sobrien { 174197403Sobrien // concept requirements 1742132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1743132720Skan _RandomAccessIterator>) 1744132720Skan __glibcxx_requires_valid_range(__first, __last); 174597403Sobrien 1746132720Skan if (__first != __last) 1747132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1748132720Skan std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1))); 174997403Sobrien } 175097403Sobrien 175197403Sobrien /** 175297403Sobrien * @brief Shuffle the elements of a sequence using a random number 175397403Sobrien * generator. 175497403Sobrien * @param first A forward iterator. 175597403Sobrien * @param last A forward iterator. 175697403Sobrien * @param rand The RNG functor or function. 175797403Sobrien * @return Nothing. 175897403Sobrien * 175997403Sobrien * Reorders the elements in the range @p [first,last) using @p rand to 176097403Sobrien * provide a random distribution. Calling @p rand(N) for a positive 176197403Sobrien * integer @p N should return a randomly chosen integer from the 176297403Sobrien * range [0,N). 176397403Sobrien */ 1764132720Skan template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 176597403Sobrien void 1766132720Skan random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 176797403Sobrien _RandomNumberGenerator& __rand) 176897403Sobrien { 176997403Sobrien // concept requirements 1770132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1771132720Skan _RandomAccessIterator>) 1772132720Skan __glibcxx_requires_valid_range(__first, __last); 177397403Sobrien 1774132720Skan if (__first == __last) 1775132720Skan return; 1776132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1777132720Skan std::iter_swap(__i, __first + __rand((__i - __first) + 1)); 177897403Sobrien } 177997403Sobrien 178097403Sobrien 178197403Sobrien /** 178297403Sobrien * @if maint 178397403Sobrien * This is a helper function... 178497403Sobrien * @endif 178597403Sobrien */ 1786132720Skan template<typename _ForwardIterator, typename _Predicate> 1787132720Skan _ForwardIterator 1788132720Skan __partition(_ForwardIterator __first, _ForwardIterator __last, 1789132720Skan _Predicate __pred, 179097403Sobrien forward_iterator_tag) 179197403Sobrien { 1792132720Skan if (__first == __last) 1793132720Skan return __first; 179497403Sobrien 179597403Sobrien while (__pred(*__first)) 1796132720Skan if (++__first == __last) 1797132720Skan return __first; 179897403Sobrien 1799132720Skan _ForwardIterator __next = __first; 180097403Sobrien 180197403Sobrien while (++__next != __last) 1802132720Skan if (__pred(*__next)) 1803132720Skan { 1804132720Skan swap(*__first, *__next); 1805132720Skan ++__first; 1806132720Skan } 180797403Sobrien 180897403Sobrien return __first; 180997403Sobrien } 181097403Sobrien 181197403Sobrien /** 181297403Sobrien * @if maint 181397403Sobrien * This is a helper function... 181497403Sobrien * @endif 181597403Sobrien */ 1816132720Skan template<typename _BidirectionalIterator, typename _Predicate> 1817132720Skan _BidirectionalIterator 1818132720Skan __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 181997403Sobrien _Predicate __pred, 182097403Sobrien bidirectional_iterator_tag) 182197403Sobrien { 1822132720Skan while (true) 1823132720Skan { 1824132720Skan while (true) 1825132720Skan if (__first == __last) 1826132720Skan return __first; 1827132720Skan else if (__pred(*__first)) 1828132720Skan ++__first; 1829132720Skan else 1830132720Skan break; 1831132720Skan --__last; 1832132720Skan while (true) 1833132720Skan if (__first == __last) 1834132720Skan return __first; 1835132720Skan else if (!__pred(*__last)) 1836132720Skan --__last; 1837132720Skan else 1838132720Skan break; 1839132720Skan std::iter_swap(__first, __last); 1840132720Skan ++__first; 1841132720Skan } 184297403Sobrien } 184397403Sobrien 184497403Sobrien /** 184597403Sobrien * @brief Move elements for which a predicate is true to the beginning 184697403Sobrien * of a sequence. 184797403Sobrien * @param first A forward iterator. 184897403Sobrien * @param last A forward iterator. 184997403Sobrien * @param pred A predicate functor. 185097403Sobrien * @return An iterator @p middle such that @p pred(i) is true for each 185197403Sobrien * iterator @p i in the range @p [first,middle) and false for each @p i 185297403Sobrien * in the range @p [middle,last). 1853132720Skan * 185497403Sobrien * @p pred must not modify its operand. @p partition() does not preserve 185597403Sobrien * the relative ordering of elements in each group, use 185697403Sobrien * @p stable_partition() if this is needed. 185797403Sobrien */ 1858132720Skan template<typename _ForwardIterator, typename _Predicate> 1859132720Skan inline _ForwardIterator 1860132720Skan partition(_ForwardIterator __first, _ForwardIterator __last, 186197403Sobrien _Predicate __pred) 186297403Sobrien { 186397403Sobrien // concept requirements 1864132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1865132720Skan _ForwardIterator>) 1866132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1867132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1868132720Skan __glibcxx_requires_valid_range(__first, __last); 186997403Sobrien 1870132720Skan return std::__partition(__first, __last, __pred, 1871132720Skan std::__iterator_category(__first)); 187297403Sobrien } 187397403Sobrien 187497403Sobrien 187597403Sobrien /** 187697403Sobrien * @if maint 187797403Sobrien * This is a helper function... 187897403Sobrien * @endif 187997403Sobrien */ 1880132720Skan template<typename _ForwardIterator, typename _Predicate, typename _Distance> 1881132720Skan _ForwardIterator 1882132720Skan __inplace_stable_partition(_ForwardIterator __first, 1883132720Skan _ForwardIterator __last, 188497403Sobrien _Predicate __pred, _Distance __len) 188597403Sobrien { 188697403Sobrien if (__len == 1) 188797403Sobrien return __pred(*__first) ? __last : __first; 1888132720Skan _ForwardIterator __middle = __first; 1889132720Skan std::advance(__middle, __len / 2); 1890132720Skan _ForwardIterator __begin = std::__inplace_stable_partition(__first, 1891132720Skan __middle, 1892132720Skan __pred, 1893132720Skan __len / 2); 1894132720Skan _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last, 1895132720Skan __pred, 1896132720Skan __len 1897132720Skan - __len / 2); 1898132720Skan std::rotate(__begin, __middle, __end); 1899132720Skan std::advance(__begin, std::distance(__middle, __end)); 190097403Sobrien return __begin; 190197403Sobrien } 190297403Sobrien 190397403Sobrien /** 190497403Sobrien * @if maint 190597403Sobrien * This is a helper function... 190697403Sobrien * @endif 190797403Sobrien */ 1908132720Skan template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 190997403Sobrien typename _Distance> 1910132720Skan _ForwardIterator 1911132720Skan __stable_partition_adaptive(_ForwardIterator __first, 1912132720Skan _ForwardIterator __last, 191397403Sobrien _Predicate __pred, _Distance __len, 191497403Sobrien _Pointer __buffer, 191597403Sobrien _Distance __buffer_size) 191697403Sobrien { 1917132720Skan if (__len <= __buffer_size) 1918132720Skan { 1919132720Skan _ForwardIterator __result1 = __first; 1920132720Skan _Pointer __result2 = __buffer; 1921132720Skan for ( ; __first != __last ; ++__first) 1922132720Skan if (__pred(*__first)) 1923132720Skan { 1924132720Skan *__result1 = *__first; 1925132720Skan ++__result1; 1926132720Skan } 1927132720Skan else 1928132720Skan { 1929132720Skan *__result2 = *__first; 1930132720Skan ++__result2; 1931132720Skan } 1932132720Skan std::copy(__buffer, __result2, __result1); 1933132720Skan return __result1; 1934132720Skan } 1935132720Skan else 1936132720Skan { 1937132720Skan _ForwardIterator __middle = __first; 1938132720Skan std::advance(__middle, __len / 2); 1939132720Skan _ForwardIterator __begin = 1940132720Skan std::__stable_partition_adaptive(__first, __middle, __pred, 1941132720Skan __len / 2, __buffer, 1942132720Skan __buffer_size); 1943132720Skan _ForwardIterator __end = 1944132720Skan std::__stable_partition_adaptive(__middle, __last, __pred, 1945132720Skan __len - __len / 2, 1946132720Skan __buffer, __buffer_size); 1947132720Skan std::rotate(__begin, __middle, __end); 1948132720Skan std::advance(__begin, std::distance(__middle, __end)); 1949132720Skan return __begin; 1950132720Skan } 195197403Sobrien } 195297403Sobrien 195397403Sobrien /** 195497403Sobrien * @brief Move elements for which a predicate is true to the beginning 195597403Sobrien * of a sequence, preserving relative ordering. 195697403Sobrien * @param first A forward iterator. 195797403Sobrien * @param last A forward iterator. 195897403Sobrien * @param pred A predicate functor. 195997403Sobrien * @return An iterator @p middle such that @p pred(i) is true for each 196097403Sobrien * iterator @p i in the range @p [first,middle) and false for each @p i 196197403Sobrien * in the range @p [middle,last). 1962132720Skan * 196397403Sobrien * Performs the same function as @p partition() with the additional 196497403Sobrien * guarantee that the relative ordering of elements in each group is 196597403Sobrien * preserved, so any two elements @p x and @p y in the range 196697403Sobrien * @p [first,last) such that @p pred(x)==pred(y) will have the same 196797403Sobrien * relative ordering after calling @p stable_partition(). 196897403Sobrien */ 1969132720Skan template<typename _ForwardIterator, typename _Predicate> 1970132720Skan _ForwardIterator 1971132720Skan stable_partition(_ForwardIterator __first, _ForwardIterator __last, 197297403Sobrien _Predicate __pred) 197397403Sobrien { 197497403Sobrien // concept requirements 1975132720Skan __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1976132720Skan _ForwardIterator>) 1977132720Skan __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1978132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 1979132720Skan __glibcxx_requires_valid_range(__first, __last); 198097403Sobrien 198197403Sobrien if (__first == __last) 198297403Sobrien return __first; 198397403Sobrien else 1984132720Skan { 1985132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 1986132720Skan _ValueType; 1987132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 1988132720Skan _DistanceType; 198997403Sobrien 1990132720Skan _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, 1991132720Skan __last); 199297403Sobrien if (__buf.size() > 0) 1993132720Skan return 1994132720Skan std::__stable_partition_adaptive(__first, __last, __pred, 1995132720Skan _DistanceType(__buf.requested_size()), 1996132720Skan __buf.begin(), __buf.size()); 199797403Sobrien else 1998132720Skan return 1999132720Skan std::__inplace_stable_partition(__first, __last, __pred, 2000132720Skan _DistanceType(__buf.requested_size())); 2001132720Skan } 200297403Sobrien } 200397403Sobrien 200497403Sobrien /** 200597403Sobrien * @if maint 200697403Sobrien * This is a helper function... 200797403Sobrien * @endif 200897403Sobrien */ 2009132720Skan template<typename _RandomAccessIterator, typename _Tp> 2010132720Skan _RandomAccessIterator 2011132720Skan __unguarded_partition(_RandomAccessIterator __first, 2012132720Skan _RandomAccessIterator __last, _Tp __pivot) 201397403Sobrien { 2014132720Skan while (true) 2015132720Skan { 2016132720Skan while (*__first < __pivot) 2017132720Skan ++__first; 2018132720Skan --__last; 2019132720Skan while (__pivot < *__last) 2020132720Skan --__last; 2021132720Skan if (!(__first < __last)) 2022132720Skan return __first; 2023132720Skan std::iter_swap(__first, __last); 202497403Sobrien ++__first; 2025132720Skan } 202697403Sobrien } 202797403Sobrien 202897403Sobrien /** 202997403Sobrien * @if maint 203097403Sobrien * This is a helper function... 203197403Sobrien * @endif 203297403Sobrien */ 2033132720Skan template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 2034132720Skan _RandomAccessIterator 2035132720Skan __unguarded_partition(_RandomAccessIterator __first, 2036132720Skan _RandomAccessIterator __last, 203797403Sobrien _Tp __pivot, _Compare __comp) 203897403Sobrien { 2039132720Skan while (true) 2040132720Skan { 2041132720Skan while (__comp(*__first, __pivot)) 2042132720Skan ++__first; 2043132720Skan --__last; 2044132720Skan while (__comp(__pivot, *__last)) 2045132720Skan --__last; 2046132720Skan if (!(__first < __last)) 2047132720Skan return __first; 2048132720Skan std::iter_swap(__first, __last); 204997403Sobrien ++__first; 2050132720Skan } 205197403Sobrien } 205297403Sobrien 205397403Sobrien /** 205497403Sobrien * @if maint 205597403Sobrien * @doctodo 205697403Sobrien * This controls some aspect of the sort routines. 205797403Sobrien * @endif 205897403Sobrien */ 2059132720Skan enum { _S_threshold = 16 }; 206097403Sobrien 206197403Sobrien /** 206297403Sobrien * @if maint 206397403Sobrien * This is a helper function for the sort routine. 206497403Sobrien * @endif 206597403Sobrien */ 2066132720Skan template<typename _RandomAccessIterator, typename _Tp> 206797403Sobrien void 2068132720Skan __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val) 206997403Sobrien { 2070132720Skan _RandomAccessIterator __next = __last; 207197403Sobrien --__next; 2072132720Skan while (__val < *__next) 2073132720Skan { 2074132720Skan *__last = *__next; 2075132720Skan __last = __next; 2076132720Skan --__next; 2077132720Skan } 207897403Sobrien *__last = __val; 207997403Sobrien } 208097403Sobrien 208197403Sobrien /** 208297403Sobrien * @if maint 208397403Sobrien * This is a helper function for the sort routine. 208497403Sobrien * @endif 208597403Sobrien */ 2086132720Skan template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 208797403Sobrien void 2088132720Skan __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, 2089132720Skan _Compare __comp) 209097403Sobrien { 2091132720Skan _RandomAccessIterator __next = __last; 209297403Sobrien --__next; 2093132720Skan while (__comp(__val, *__next)) 2094132720Skan { 2095132720Skan *__last = *__next; 2096132720Skan __last = __next; 2097132720Skan --__next; 2098132720Skan } 209997403Sobrien *__last = __val; 210097403Sobrien } 210197403Sobrien 210297403Sobrien /** 210397403Sobrien * @if maint 210497403Sobrien * This is a helper function for the sort routine. 210597403Sobrien * @endif 210697403Sobrien */ 2107132720Skan template<typename _RandomAccessIterator> 210897403Sobrien void 2109132720Skan __insertion_sort(_RandomAccessIterator __first, 2110132720Skan _RandomAccessIterator __last) 211197403Sobrien { 2112132720Skan if (__first == __last) 2113132720Skan return; 211497403Sobrien 2115132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 2116132720Skan { 2117132720Skan typename iterator_traits<_RandomAccessIterator>::value_type 2118132720Skan __val = *__i; 2119132720Skan if (__val < *__first) 2120132720Skan { 2121132720Skan std::copy_backward(__first, __i, __i + 1); 2122132720Skan *__first = __val; 2123132720Skan } 2124132720Skan else 2125132720Skan std::__unguarded_linear_insert(__i, __val); 212697403Sobrien } 212797403Sobrien } 212897403Sobrien 212997403Sobrien /** 213097403Sobrien * @if maint 213197403Sobrien * This is a helper function for the sort routine. 213297403Sobrien * @endif 213397403Sobrien */ 2134132720Skan template<typename _RandomAccessIterator, typename _Compare> 213597403Sobrien void 2136132720Skan __insertion_sort(_RandomAccessIterator __first, 2137132720Skan _RandomAccessIterator __last, _Compare __comp) 213897403Sobrien { 213997403Sobrien if (__first == __last) return; 214097403Sobrien 2141132720Skan for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 2142132720Skan { 2143132720Skan typename iterator_traits<_RandomAccessIterator>::value_type 2144132720Skan __val = *__i; 2145132720Skan if (__comp(__val, *__first)) 2146132720Skan { 2147132720Skan std::copy_backward(__first, __i, __i + 1); 2148132720Skan *__first = __val; 2149132720Skan } 2150132720Skan else 2151132720Skan std::__unguarded_linear_insert(__i, __val, __comp); 215297403Sobrien } 215397403Sobrien } 215497403Sobrien 215597403Sobrien /** 215697403Sobrien * @if maint 215797403Sobrien * This is a helper function for the sort routine. 215897403Sobrien * @endif 215997403Sobrien */ 2160132720Skan template<typename _RandomAccessIterator> 216197403Sobrien inline void 2162132720Skan __unguarded_insertion_sort(_RandomAccessIterator __first, 2163132720Skan _RandomAccessIterator __last) 216497403Sobrien { 2165132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2166132720Skan _ValueType; 216797403Sobrien 2168132720Skan for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 2169132720Skan std::__unguarded_linear_insert(__i, _ValueType(*__i)); 217097403Sobrien } 217197403Sobrien 217297403Sobrien /** 217397403Sobrien * @if maint 217497403Sobrien * This is a helper function for the sort routine. 217597403Sobrien * @endif 217697403Sobrien */ 2177132720Skan template<typename _RandomAccessIterator, typename _Compare> 217897403Sobrien inline void 2179132720Skan __unguarded_insertion_sort(_RandomAccessIterator __first, 2180132720Skan _RandomAccessIterator __last, _Compare __comp) 218197403Sobrien { 2182132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2183132720Skan _ValueType; 218497403Sobrien 2185132720Skan for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 2186132720Skan std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp); 218797403Sobrien } 218897403Sobrien 218997403Sobrien /** 219097403Sobrien * @if maint 219197403Sobrien * This is a helper function for the sort routine. 219297403Sobrien * @endif 219397403Sobrien */ 2194132720Skan template<typename _RandomAccessIterator> 219597403Sobrien void 2196132720Skan __final_insertion_sort(_RandomAccessIterator __first, 2197132720Skan _RandomAccessIterator __last) 219897403Sobrien { 2199132720Skan if (__last - __first > _S_threshold) 2200132720Skan { 2201132720Skan std::__insertion_sort(__first, __first + _S_threshold); 2202132720Skan std::__unguarded_insertion_sort(__first + _S_threshold, __last); 2203132720Skan } 220497403Sobrien else 2205132720Skan std::__insertion_sort(__first, __last); 220697403Sobrien } 220797403Sobrien 220897403Sobrien /** 220997403Sobrien * @if maint 221097403Sobrien * This is a helper function for the sort routine. 221197403Sobrien * @endif 221297403Sobrien */ 2213132720Skan template<typename _RandomAccessIterator, typename _Compare> 221497403Sobrien void 2215132720Skan __final_insertion_sort(_RandomAccessIterator __first, 2216132720Skan _RandomAccessIterator __last, _Compare __comp) 221797403Sobrien { 2218132720Skan if (__last - __first > _S_threshold) 2219132720Skan { 2220132720Skan std::__insertion_sort(__first, __first + _S_threshold, __comp); 2221132720Skan std::__unguarded_insertion_sort(__first + _S_threshold, __last, 2222132720Skan __comp); 2223132720Skan } 222497403Sobrien else 2225132720Skan std::__insertion_sort(__first, __last, __comp); 222697403Sobrien } 222797403Sobrien 222897403Sobrien /** 222997403Sobrien * @if maint 223097403Sobrien * This is a helper function for the sort routine. 223197403Sobrien * @endif 223297403Sobrien */ 223397403Sobrien template<typename _Size> 223497403Sobrien inline _Size 223597403Sobrien __lg(_Size __n) 223697403Sobrien { 223797403Sobrien _Size __k; 2238132720Skan for (__k = 0; __n != 1; __n >>= 1) 2239132720Skan ++__k; 224097403Sobrien return __k; 224197403Sobrien } 224297403Sobrien 224397403Sobrien /** 224497403Sobrien * @brief Sort the smallest elements of a sequence. 224597403Sobrien * @param first An iterator. 224697403Sobrien * @param middle Another iterator. 224797403Sobrien * @param last Another iterator. 224897403Sobrien * @return Nothing. 224997403Sobrien * 225097403Sobrien * Sorts the smallest @p (middle-first) elements in the range 225197403Sobrien * @p [first,last) and moves them to the range @p [first,middle). The 225297403Sobrien * order of the remaining elements in the range @p [middle,last) is 225397403Sobrien * undefined. 225497403Sobrien * After the sort if @p i and @j are iterators in the range 225597403Sobrien * @p [first,middle) such that @i precedes @j and @k is an iterator in 225697403Sobrien * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 225797403Sobrien */ 2258132720Skan template<typename _RandomAccessIterator> 225997403Sobrien void 2260132720Skan partial_sort(_RandomAccessIterator __first, 2261132720Skan _RandomAccessIterator __middle, 2262132720Skan _RandomAccessIterator __last) 226397403Sobrien { 2264132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2265132720Skan _ValueType; 226697403Sobrien 226797403Sobrien // concept requirements 2268132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2269132720Skan _RandomAccessIterator>) 2270132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 2271132720Skan __glibcxx_requires_valid_range(__first, __middle); 2272132720Skan __glibcxx_requires_valid_range(__middle, __last); 227397403Sobrien 2274132720Skan std::make_heap(__first, __middle); 2275132720Skan for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 227697403Sobrien if (*__i < *__first) 2277132720Skan std::__pop_heap(__first, __middle, __i, _ValueType(*__i)); 2278132720Skan std::sort_heap(__first, __middle); 227997403Sobrien } 228097403Sobrien 228197403Sobrien /** 228297403Sobrien * @brief Sort the smallest elements of a sequence using a predicate 228397403Sobrien * for comparison. 228497403Sobrien * @param first An iterator. 228597403Sobrien * @param middle Another iterator. 228697403Sobrien * @param last Another iterator. 228797403Sobrien * @param comp A comparison functor. 228897403Sobrien * @return Nothing. 228997403Sobrien * 229097403Sobrien * Sorts the smallest @p (middle-first) elements in the range 229197403Sobrien * @p [first,last) and moves them to the range @p [first,middle). The 229297403Sobrien * order of the remaining elements in the range @p [middle,last) is 229397403Sobrien * undefined. 229497403Sobrien * After the sort if @p i and @j are iterators in the range 229597403Sobrien * @p [first,middle) such that @i precedes @j and @k is an iterator in 229697403Sobrien * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 229797403Sobrien * are both false. 229897403Sobrien */ 2299132720Skan template<typename _RandomAccessIterator, typename _Compare> 230097403Sobrien void 2301132720Skan partial_sort(_RandomAccessIterator __first, 2302132720Skan _RandomAccessIterator __middle, 2303132720Skan _RandomAccessIterator __last, 230497403Sobrien _Compare __comp) 230597403Sobrien { 2306132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2307132720Skan _ValueType; 230897403Sobrien 230997403Sobrien // concept requirements 2310132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2311132720Skan _RandomAccessIterator>) 2312132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2313132720Skan _ValueType, _ValueType>) 2314132720Skan __glibcxx_requires_valid_range(__first, __middle); 2315132720Skan __glibcxx_requires_valid_range(__middle, __last); 231697403Sobrien 2317132720Skan std::make_heap(__first, __middle, __comp); 2318132720Skan for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 231997403Sobrien if (__comp(*__i, *__first)) 2320132720Skan std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 2321132720Skan std::sort_heap(__first, __middle, __comp); 232297403Sobrien } 232397403Sobrien 232497403Sobrien /** 232597403Sobrien * @brief Copy the smallest elements of a sequence. 232697403Sobrien * @param first An iterator. 232797403Sobrien * @param last Another iterator. 232897403Sobrien * @param result_first A random-access iterator. 232997403Sobrien * @param result_last Another random-access iterator. 233097403Sobrien * @return An iterator indicating the end of the resulting sequence. 233197403Sobrien * 233297403Sobrien * Copies and sorts the smallest N values from the range @p [first,last) 233397403Sobrien * to the range beginning at @p result_first, where the number of 233497403Sobrien * elements to be copied, @p N, is the smaller of @p (last-first) and 233597403Sobrien * @p (result_last-result_first). 233697403Sobrien * After the sort if @p i and @j are iterators in the range 233797403Sobrien * @p [result_first,result_first+N) such that @i precedes @j then 233897403Sobrien * @p *j<*i is false. 233997403Sobrien * The value returned is @p result_first+N. 234097403Sobrien */ 2341132720Skan template<typename _InputIterator, typename _RandomAccessIterator> 2342132720Skan _RandomAccessIterator 2343132720Skan partial_sort_copy(_InputIterator __first, _InputIterator __last, 2344132720Skan _RandomAccessIterator __result_first, 2345132720Skan _RandomAccessIterator __result_last) 234697403Sobrien { 2347132720Skan typedef typename iterator_traits<_InputIterator>::value_type 2348132720Skan _InputValueType; 2349132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2350132720Skan _OutputValueType; 2351132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2352132720Skan _DistanceType; 235397403Sobrien 235497403Sobrien // concept requirements 2355132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 2356132720Skan __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 2357132720Skan _OutputValueType>) 2358132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 2359132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>) 2360132720Skan __glibcxx_requires_valid_range(__first, __last); 2361132720Skan __glibcxx_requires_valid_range(__result_first, __result_last); 236297403Sobrien 2363132720Skan if (__result_first == __result_last) 2364132720Skan return __result_last; 2365132720Skan _RandomAccessIterator __result_real_last = __result_first; 2366132720Skan while(__first != __last && __result_real_last != __result_last) 2367132720Skan { 2368132720Skan *__result_real_last = *__first; 2369132720Skan ++__result_real_last; 2370132720Skan ++__first; 2371132720Skan } 2372132720Skan std::make_heap(__result_first, __result_real_last); 2373132720Skan while (__first != __last) 2374132720Skan { 2375132720Skan if (*__first < *__result_first) 2376132720Skan std::__adjust_heap(__result_first, _DistanceType(0), 2377132720Skan _DistanceType(__result_real_last 2378132720Skan - __result_first), 2379132720Skan _InputValueType(*__first)); 2380132720Skan ++__first; 2381132720Skan } 2382132720Skan std::sort_heap(__result_first, __result_real_last); 238397403Sobrien return __result_real_last; 238497403Sobrien } 238597403Sobrien 238697403Sobrien /** 238797403Sobrien * @brief Copy the smallest elements of a sequence using a predicate for 238897403Sobrien * comparison. 238997403Sobrien * @param first An input iterator. 239097403Sobrien * @param last Another input iterator. 239197403Sobrien * @param result_first A random-access iterator. 239297403Sobrien * @param result_last Another random-access iterator. 239397403Sobrien * @param comp A comparison functor. 239497403Sobrien * @return An iterator indicating the end of the resulting sequence. 239597403Sobrien * 239697403Sobrien * Copies and sorts the smallest N values from the range @p [first,last) 239797403Sobrien * to the range beginning at @p result_first, where the number of 239897403Sobrien * elements to be copied, @p N, is the smaller of @p (last-first) and 239997403Sobrien * @p (result_last-result_first). 240097403Sobrien * After the sort if @p i and @j are iterators in the range 240197403Sobrien * @p [result_first,result_first+N) such that @i precedes @j then 240297403Sobrien * @p comp(*j,*i) is false. 240397403Sobrien * The value returned is @p result_first+N. 240497403Sobrien */ 2405132720Skan template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare> 2406132720Skan _RandomAccessIterator 2407132720Skan partial_sort_copy(_InputIterator __first, _InputIterator __last, 2408132720Skan _RandomAccessIterator __result_first, 2409132720Skan _RandomAccessIterator __result_last, 241097403Sobrien _Compare __comp) 241197403Sobrien { 2412132720Skan typedef typename iterator_traits<_InputIterator>::value_type 2413132720Skan _InputValueType; 2414132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2415132720Skan _OutputValueType; 2416132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2417132720Skan _DistanceType; 241897403Sobrien 241997403Sobrien // concept requirements 2420132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 2421132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2422132720Skan _RandomAccessIterator>) 2423132720Skan __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 2424132720Skan _OutputValueType>) 2425132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 242697403Sobrien _OutputValueType, _OutputValueType>) 2427132720Skan __glibcxx_requires_valid_range(__first, __last); 2428132720Skan __glibcxx_requires_valid_range(__result_first, __result_last); 242997403Sobrien 2430132720Skan if (__result_first == __result_last) 2431132720Skan return __result_last; 2432132720Skan _RandomAccessIterator __result_real_last = __result_first; 2433132720Skan while(__first != __last && __result_real_last != __result_last) 2434132720Skan { 2435132720Skan *__result_real_last = *__first; 2436132720Skan ++__result_real_last; 2437132720Skan ++__first; 2438132720Skan } 2439132720Skan std::make_heap(__result_first, __result_real_last, __comp); 2440132720Skan while (__first != __last) 2441132720Skan { 2442132720Skan if (__comp(*__first, *__result_first)) 2443132720Skan std::__adjust_heap(__result_first, _DistanceType(0), 2444132720Skan _DistanceType(__result_real_last 2445132720Skan - __result_first), 2446132720Skan _InputValueType(*__first), 2447132720Skan __comp); 2448132720Skan ++__first; 2449132720Skan } 2450132720Skan std::sort_heap(__result_first, __result_real_last, __comp); 245197403Sobrien return __result_real_last; 245297403Sobrien } 245397403Sobrien 245497403Sobrien /** 2455132720Skan * @if maint 2456132720Skan * This is a helper function for the sort routine. 2457132720Skan * @endif 2458132720Skan */ 2459132720Skan template<typename _RandomAccessIterator, typename _Size> 2460132720Skan void 2461132720Skan __introsort_loop(_RandomAccessIterator __first, 2462132720Skan _RandomAccessIterator __last, 2463132720Skan _Size __depth_limit) 2464132720Skan { 2465132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2466132720Skan _ValueType; 2467132720Skan 2468132720Skan while (__last - __first > _S_threshold) 2469132720Skan { 2470132720Skan if (__depth_limit == 0) 2471132720Skan { 2472132720Skan std::partial_sort(__first, __last, __last); 2473132720Skan return; 2474132720Skan } 2475132720Skan --__depth_limit; 2476132720Skan _RandomAccessIterator __cut = 2477132720Skan std::__unguarded_partition(__first, __last, 2478132720Skan _ValueType(std::__median(*__first, 2479132720Skan *(__first 2480132720Skan + (__last 2481132720Skan - __first) 2482132720Skan / 2), 2483132720Skan *(__last 2484132720Skan - 1)))); 2485132720Skan std::__introsort_loop(__cut, __last, __depth_limit); 2486132720Skan __last = __cut; 2487132720Skan } 2488132720Skan } 2489132720Skan 2490132720Skan /** 2491132720Skan * @if maint 2492132720Skan * This is a helper function for the sort routine. 2493132720Skan * @endif 2494132720Skan */ 2495132720Skan template<typename _RandomAccessIterator, typename _Size, typename _Compare> 2496132720Skan void 2497132720Skan __introsort_loop(_RandomAccessIterator __first, 2498132720Skan _RandomAccessIterator __last, 2499132720Skan _Size __depth_limit, _Compare __comp) 2500132720Skan { 2501132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2502132720Skan _ValueType; 2503132720Skan 2504132720Skan while (__last - __first > _S_threshold) 2505132720Skan { 2506132720Skan if (__depth_limit == 0) 2507132720Skan { 2508132720Skan std::partial_sort(__first, __last, __last, __comp); 2509132720Skan return; 2510132720Skan } 2511132720Skan --__depth_limit; 2512132720Skan _RandomAccessIterator __cut = 2513132720Skan std::__unguarded_partition(__first, __last, 2514132720Skan _ValueType(std::__median(*__first, 2515132720Skan *(__first 2516132720Skan + (__last 2517132720Skan - __first) 2518132720Skan / 2), 2519132720Skan *(__last - 1), 2520132720Skan __comp)), 2521132720Skan __comp); 2522132720Skan std::__introsort_loop(__cut, __last, __depth_limit, __comp); 2523132720Skan __last = __cut; 2524132720Skan } 2525132720Skan } 2526132720Skan 2527132720Skan /** 2528132720Skan * @brief Sort the elements of a sequence. 252997403Sobrien * @param first An iterator. 253097403Sobrien * @param last Another iterator. 253197403Sobrien * @return Nothing. 253297403Sobrien * 2533132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 2534132720Skan * such that @p *(i+1)<*i is false for each iterator @p i in the range 2535132720Skan * @p [first,last-1). 2536132720Skan * 2537132720Skan * The relative ordering of equivalent elements is not preserved, use 2538132720Skan * @p stable_sort() if this is needed. 253997403Sobrien */ 2540132720Skan template<typename _RandomAccessIterator> 2541132720Skan inline void 2542132720Skan sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 254397403Sobrien { 2544132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2545132720Skan _ValueType; 254697403Sobrien 254797403Sobrien // concept requirements 2548132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2549132720Skan _RandomAccessIterator>) 2550132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 2551132720Skan __glibcxx_requires_valid_range(__first, __last); 255297403Sobrien 2553132720Skan if (__first != __last) 2554132720Skan { 2555132720Skan std::__introsort_loop(__first, __last, __lg(__last - __first) * 2); 2556132720Skan std::__final_insertion_sort(__first, __last); 2557132720Skan } 255897403Sobrien } 255997403Sobrien 256097403Sobrien /** 2561132720Skan * @brief Sort the elements of a sequence using a predicate for comparison. 256297403Sobrien * @param first An iterator. 256397403Sobrien * @param last Another iterator. 256497403Sobrien * @param comp A comparison functor. 256597403Sobrien * @return Nothing. 256697403Sobrien * 2567132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 2568132720Skan * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 2569132720Skan * range @p [first,last-1). 2570132720Skan * 2571132720Skan * The relative ordering of equivalent elements is not preserved, use 2572132720Skan * @p stable_sort() if this is needed. 257397403Sobrien */ 2574132720Skan template<typename _RandomAccessIterator, typename _Compare> 2575132720Skan inline void 2576132720Skan sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 2577132720Skan _Compare __comp) 257897403Sobrien { 2579132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 2580132720Skan _ValueType; 258197403Sobrien 258297403Sobrien // concept requirements 2583132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 2584132720Skan _RandomAccessIterator>) 2585132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, 2586132720Skan _ValueType>) 2587132720Skan __glibcxx_requires_valid_range(__first, __last); 258897403Sobrien 2589132720Skan if (__first != __last) 2590132720Skan { 2591132720Skan std::__introsort_loop(__first, __last, __lg(__last - __first) * 2, 259297403Sobrien __comp); 2593132720Skan std::__final_insertion_sort(__first, __last, __comp); 2594132720Skan } 259597403Sobrien } 259697403Sobrien 259797403Sobrien /** 259897403Sobrien * @brief Finds the first position in which @a val could be inserted 259997403Sobrien * without changing the ordering. 260097403Sobrien * @param first An iterator. 260197403Sobrien * @param last Another iterator. 260297403Sobrien * @param val The search term. 2603132720Skan * @return An iterator pointing to the first element "not less than" @a val, 2604132720Skan * or end() if every element is less than @a val. 260597403Sobrien * @ingroup binarysearch 260697403Sobrien */ 2607132720Skan template<typename _ForwardIterator, typename _Tp> 2608132720Skan _ForwardIterator 2609132720Skan lower_bound(_ForwardIterator __first, _ForwardIterator __last, 2610132720Skan const _Tp& __val) 261197403Sobrien { 2612132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2613132720Skan _ValueType; 2614132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2615132720Skan _DistanceType; 261697403Sobrien 261797403Sobrien // concept requirements 261897403Sobrien // Note that these are slightly stricter than those of the 4-argument 261997403Sobrien // version, defined next. The difference is in the strictness of the 262097403Sobrien // comparison operations... so for looser checking, define your own 262197403Sobrien // comparison function, as was intended. 2622132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2623132720Skan __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 2624132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 2625132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 262697403Sobrien 2627132720Skan _DistanceType __len = std::distance(__first, __last); 262897403Sobrien _DistanceType __half; 2629132720Skan _ForwardIterator __middle; 263097403Sobrien 2631132720Skan while (__len > 0) 2632132720Skan { 2633132720Skan __half = __len >> 1; 2634132720Skan __middle = __first; 2635132720Skan std::advance(__middle, __half); 2636132720Skan if (*__middle < __val) 2637132720Skan { 2638132720Skan __first = __middle; 2639132720Skan ++__first; 2640132720Skan __len = __len - __half - 1; 2641132720Skan } 2642132720Skan else 2643132720Skan __len = __half; 264497403Sobrien } 264597403Sobrien return __first; 264697403Sobrien } 264797403Sobrien 264897403Sobrien /** 264997403Sobrien * @brief Finds the first position in which @a val could be inserted 265097403Sobrien * without changing the ordering. 265197403Sobrien * @param first An iterator. 265297403Sobrien * @param last Another iterator. 265397403Sobrien * @param val The search term. 265497403Sobrien * @param comp A functor to use for comparisons. 2655132720Skan * @return An iterator pointing to the first element "not less than" @a val, 2656132720Skan * or end() if every element is less than @a val. 265797403Sobrien * @ingroup binarysearch 265897403Sobrien * 265997403Sobrien * The comparison function should have the same effects on ordering as 266097403Sobrien * the function used for the initial sort. 266197403Sobrien */ 2662132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 2663132720Skan _ForwardIterator 2664132720Skan lower_bound(_ForwardIterator __first, _ForwardIterator __last, 266597403Sobrien const _Tp& __val, _Compare __comp) 266697403Sobrien { 2667132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2668132720Skan _ValueType; 2669132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2670132720Skan _DistanceType; 267197403Sobrien 267297403Sobrien // concept requirements 2673132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2674132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2675132720Skan _ValueType, _Tp>) 2676132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 267797403Sobrien 2678132720Skan _DistanceType __len = std::distance(__first, __last); 267997403Sobrien _DistanceType __half; 2680132720Skan _ForwardIterator __middle; 268197403Sobrien 2682132720Skan while (__len > 0) 2683132720Skan { 2684132720Skan __half = __len >> 1; 2685132720Skan __middle = __first; 2686132720Skan std::advance(__middle, __half); 2687132720Skan if (__comp(*__middle, __val)) 2688132720Skan { 2689132720Skan __first = __middle; 2690132720Skan ++__first; 2691132720Skan __len = __len - __half - 1; 2692132720Skan } 2693132720Skan else 2694132720Skan __len = __half; 269597403Sobrien } 269697403Sobrien return __first; 269797403Sobrien } 269897403Sobrien 269997403Sobrien /** 270097403Sobrien * @brief Finds the last position in which @a val could be inserted 270197403Sobrien * without changing the ordering. 270297403Sobrien * @param first An iterator. 270397403Sobrien * @param last Another iterator. 270497403Sobrien * @param val The search term. 2705132720Skan * @return An iterator pointing to the first element greater than @a val, 2706132720Skan * or end() if no elements are greater than @a val. 270797403Sobrien * @ingroup binarysearch 270897403Sobrien */ 2709132720Skan template<typename _ForwardIterator, typename _Tp> 2710132720Skan _ForwardIterator 2711132720Skan upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2712132720Skan const _Tp& __val) 271397403Sobrien { 2714132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2715132720Skan _ValueType; 2716132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2717132720Skan _DistanceType; 271897403Sobrien 271997403Sobrien // concept requirements 272097403Sobrien // See comments on lower_bound. 2721132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2722132720Skan __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 2723132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 2724132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 272597403Sobrien 2726132720Skan _DistanceType __len = std::distance(__first, __last); 272797403Sobrien _DistanceType __half; 2728132720Skan _ForwardIterator __middle; 272997403Sobrien 2730132720Skan while (__len > 0) 2731132720Skan { 2732132720Skan __half = __len >> 1; 2733132720Skan __middle = __first; 2734132720Skan std::advance(__middle, __half); 2735132720Skan if (__val < *__middle) 2736132720Skan __len = __half; 2737132720Skan else 2738132720Skan { 2739132720Skan __first = __middle; 2740132720Skan ++__first; 2741132720Skan __len = __len - __half - 1; 2742132720Skan } 274397403Sobrien } 274497403Sobrien return __first; 274597403Sobrien } 274697403Sobrien 274797403Sobrien /** 274897403Sobrien * @brief Finds the last position in which @a val could be inserted 274997403Sobrien * without changing the ordering. 275097403Sobrien * @param first An iterator. 275197403Sobrien * @param last Another iterator. 275297403Sobrien * @param val The search term. 275397403Sobrien * @param comp A functor to use for comparisons. 2754132720Skan * @return An iterator pointing to the first element greater than @a val, 2755132720Skan * or end() if no elements are greater than @a val. 275697403Sobrien * @ingroup binarysearch 275797403Sobrien * 275897403Sobrien * The comparison function should have the same effects on ordering as 275997403Sobrien * the function used for the initial sort. 276097403Sobrien */ 2761132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 2762132720Skan _ForwardIterator 2763132720Skan upper_bound(_ForwardIterator __first, _ForwardIterator __last, 276497403Sobrien const _Tp& __val, _Compare __comp) 276597403Sobrien { 2766132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 2767132720Skan _ValueType; 2768132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 2769132720Skan _DistanceType; 277097403Sobrien 277197403Sobrien // concept requirements 2772132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2773132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2774132720Skan _Tp, _ValueType>) 2775132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 277697403Sobrien 2777132720Skan _DistanceType __len = std::distance(__first, __last); 277897403Sobrien _DistanceType __half; 2779132720Skan _ForwardIterator __middle; 278097403Sobrien 2781132720Skan while (__len > 0) 2782132720Skan { 2783132720Skan __half = __len >> 1; 2784132720Skan __middle = __first; 2785132720Skan std::advance(__middle, __half); 2786132720Skan if (__comp(__val, *__middle)) 2787132720Skan __len = __half; 2788132720Skan else 2789132720Skan { 2790132720Skan __first = __middle; 2791132720Skan ++__first; 2792132720Skan __len = __len - __half - 1; 2793132720Skan } 279497403Sobrien } 279597403Sobrien return __first; 279697403Sobrien } 279797403Sobrien 279897403Sobrien /** 2799132720Skan * @if maint 2800132720Skan * This is a helper function for the merge routines. 2801132720Skan * @endif 280297403Sobrien */ 2803132720Skan template<typename _BidirectionalIterator, typename _Distance> 2804132720Skan void 2805132720Skan __merge_without_buffer(_BidirectionalIterator __first, 2806132720Skan _BidirectionalIterator __middle, 2807132720Skan _BidirectionalIterator __last, 2808132720Skan _Distance __len1, _Distance __len2) 280997403Sobrien { 2810132720Skan if (__len1 == 0 || __len2 == 0) 2811132720Skan return; 2812132720Skan if (__len1 + __len2 == 2) 2813132720Skan { 2814132720Skan if (*__middle < *__first) 2815132720Skan std::iter_swap(__first, __middle); 2816132720Skan return; 281797403Sobrien } 2818132720Skan _BidirectionalIterator __first_cut = __first; 2819132720Skan _BidirectionalIterator __second_cut = __middle; 2820132720Skan _Distance __len11 = 0; 2821132720Skan _Distance __len22 = 0; 2822132720Skan if (__len1 > __len2) 2823132720Skan { 2824132720Skan __len11 = __len1 / 2; 2825132720Skan std::advance(__first_cut, __len11); 2826132720Skan __second_cut = std::lower_bound(__middle, __last, *__first_cut); 2827132720Skan __len22 = std::distance(__middle, __second_cut); 282897403Sobrien } 2829132720Skan else 2830132720Skan { 2831132720Skan __len22 = __len2 / 2; 2832132720Skan std::advance(__second_cut, __len22); 2833132720Skan __first_cut = std::upper_bound(__first, __middle, *__second_cut); 2834132720Skan __len11 = std::distance(__first, __first_cut); 2835132720Skan } 2836132720Skan std::rotate(__first_cut, __middle, __second_cut); 2837132720Skan _BidirectionalIterator __new_middle = __first_cut; 2838132720Skan std::advance(__new_middle, std::distance(__middle, __second_cut)); 2839132720Skan std::__merge_without_buffer(__first, __first_cut, __new_middle, 2840132720Skan __len11, __len22); 2841132720Skan std::__merge_without_buffer(__new_middle, __second_cut, __last, 2842132720Skan __len1 - __len11, __len2 - __len22); 284397403Sobrien } 284497403Sobrien 284597403Sobrien /** 2846132720Skan * @if maint 2847132720Skan * This is a helper function for the merge routines. 2848132720Skan * @endif 284997403Sobrien */ 2850132720Skan template<typename _BidirectionalIterator, typename _Distance, 2851132720Skan typename _Compare> 2852132720Skan void 2853132720Skan __merge_without_buffer(_BidirectionalIterator __first, 2854132720Skan _BidirectionalIterator __middle, 2855132720Skan _BidirectionalIterator __last, 2856132720Skan _Distance __len1, _Distance __len2, 2857132720Skan _Compare __comp) 285897403Sobrien { 2859132720Skan if (__len1 == 0 || __len2 == 0) 2860132720Skan return; 2861132720Skan if (__len1 + __len2 == 2) 2862132720Skan { 2863132720Skan if (__comp(*__middle, *__first)) 2864132720Skan std::iter_swap(__first, __middle); 2865132720Skan return; 286697403Sobrien } 2867132720Skan _BidirectionalIterator __first_cut = __first; 2868132720Skan _BidirectionalIterator __second_cut = __middle; 2869132720Skan _Distance __len11 = 0; 2870132720Skan _Distance __len22 = 0; 2871132720Skan if (__len1 > __len2) 2872132720Skan { 2873132720Skan __len11 = __len1 / 2; 2874132720Skan std::advance(__first_cut, __len11); 2875132720Skan __second_cut = std::lower_bound(__middle, __last, *__first_cut, 2876132720Skan __comp); 2877132720Skan __len22 = std::distance(__middle, __second_cut); 287897403Sobrien } 2879132720Skan else 2880132720Skan { 2881132720Skan __len22 = __len2 / 2; 2882132720Skan std::advance(__second_cut, __len22); 2883132720Skan __first_cut = std::upper_bound(__first, __middle, *__second_cut, 2884132720Skan __comp); 2885132720Skan __len11 = std::distance(__first, __first_cut); 2886132720Skan } 2887132720Skan std::rotate(__first_cut, __middle, __second_cut); 2888132720Skan _BidirectionalIterator __new_middle = __first_cut; 2889132720Skan std::advance(__new_middle, std::distance(__middle, __second_cut)); 2890132720Skan std::__merge_without_buffer(__first, __first_cut, __new_middle, 2891132720Skan __len11, __len22, __comp); 2892132720Skan std::__merge_without_buffer(__new_middle, __second_cut, __last, 2893132720Skan __len1 - __len11, __len2 - __len22, __comp); 289497403Sobrien } 289597403Sobrien 289697403Sobrien /** 2897132720Skan * @if maint 2898132720Skan * This is a helper function for the stable sorting routines. 2899132720Skan * @endif 290097403Sobrien */ 2901132720Skan template<typename _RandomAccessIterator> 2902132720Skan void 2903132720Skan __inplace_stable_sort(_RandomAccessIterator __first, 2904132720Skan _RandomAccessIterator __last) 290597403Sobrien { 2906132720Skan if (__last - __first < 15) 2907132720Skan { 2908132720Skan std::__insertion_sort(__first, __last); 2909132720Skan return; 2910132720Skan } 2911132720Skan _RandomAccessIterator __middle = __first + (__last - __first) / 2; 2912132720Skan std::__inplace_stable_sort(__first, __middle); 2913132720Skan std::__inplace_stable_sort(__middle, __last); 2914132720Skan std::__merge_without_buffer(__first, __middle, __last, 2915132720Skan __middle - __first, 2916132720Skan __last - __middle); 291797403Sobrien } 291897403Sobrien 291997403Sobrien /** 2920132720Skan * @if maint 2921132720Skan * This is a helper function for the stable sorting routines. 2922132720Skan * @endif 292397403Sobrien */ 2924132720Skan template<typename _RandomAccessIterator, typename _Compare> 2925132720Skan void 2926132720Skan __inplace_stable_sort(_RandomAccessIterator __first, 2927132720Skan _RandomAccessIterator __last, _Compare __comp) 292897403Sobrien { 2929132720Skan if (__last - __first < 15) 2930132720Skan { 2931132720Skan std::__insertion_sort(__first, __last, __comp); 2932132720Skan return; 2933132720Skan } 2934132720Skan _RandomAccessIterator __middle = __first + (__last - __first) / 2; 2935132720Skan std::__inplace_stable_sort(__first, __middle, __comp); 2936132720Skan std::__inplace_stable_sort(__middle, __last, __comp); 2937132720Skan std::__merge_without_buffer(__first, __middle, __last, 2938132720Skan __middle - __first, 2939132720Skan __last - __middle, 2940132720Skan __comp); 294197403Sobrien } 294297403Sobrien 294397403Sobrien /** 294497403Sobrien * @brief Merges two sorted ranges. 294597403Sobrien * @param first1 An iterator. 294697403Sobrien * @param first2 Another iterator. 294797403Sobrien * @param last1 Another iterator. 294897403Sobrien * @param last2 Another iterator. 294997403Sobrien * @param result An iterator pointing to the end of the merged range. 295097403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 295197403Sobrien * 295297403Sobrien * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 295397403Sobrien * [result, result + (last1-first1) + (last2-first2)). Both input ranges 295497403Sobrien * must be sorted, and the output range must not overlap with either of 295597403Sobrien * the input ranges. The sort is @e stable, that is, for equivalent 295697403Sobrien * elements in the two ranges, elements from the first range will always 295797403Sobrien * come before elements from the second. 295897403Sobrien */ 2959132720Skan template<typename _InputIterator1, typename _InputIterator2, 2960132720Skan typename _OutputIterator> 2961132720Skan _OutputIterator 2962132720Skan merge(_InputIterator1 __first1, _InputIterator1 __last1, 2963132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 2964132720Skan _OutputIterator __result) 296597403Sobrien { 296697403Sobrien // concept requirements 2967132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2968132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2969132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 2970132720Skan typename iterator_traits<_InputIterator1>::value_type>) 2971132720Skan __glibcxx_function_requires(_SameTypeConcept< 2972132720Skan typename iterator_traits<_InputIterator1>::value_type, 2973132720Skan typename iterator_traits<_InputIterator2>::value_type>) 2974132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 2975132720Skan typename iterator_traits<_InputIterator1>::value_type>) 2976132720Skan __glibcxx_requires_sorted(__first1, __last1); 2977132720Skan __glibcxx_requires_sorted(__first2, __last2); 297897403Sobrien 2979132720Skan while (__first1 != __last1 && __first2 != __last2) 2980132720Skan { 2981132720Skan if (*__first2 < *__first1) 2982132720Skan { 2983132720Skan *__result = *__first2; 2984132720Skan ++__first2; 2985132720Skan } 2986132720Skan else 2987132720Skan { 2988132720Skan *__result = *__first1; 2989132720Skan ++__first1; 2990132720Skan } 2991132720Skan ++__result; 299297403Sobrien } 2993132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 2994132720Skan __result)); 299597403Sobrien } 299697403Sobrien 299797403Sobrien /** 299897403Sobrien * @brief Merges two sorted ranges. 299997403Sobrien * @param first1 An iterator. 300097403Sobrien * @param first2 Another iterator. 300197403Sobrien * @param last1 Another iterator. 300297403Sobrien * @param last2 Another iterator. 300397403Sobrien * @param result An iterator pointing to the end of the merged range. 300497403Sobrien * @param comp A functor to use for comparisons. 300597403Sobrien * @return An iterator pointing to the first element "not less than" @a val. 300697403Sobrien * 300797403Sobrien * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 300897403Sobrien * [result, result + (last1-first1) + (last2-first2)). Both input ranges 300997403Sobrien * must be sorted, and the output range must not overlap with either of 301097403Sobrien * the input ranges. The sort is @e stable, that is, for equivalent 301197403Sobrien * elements in the two ranges, elements from the first range will always 301297403Sobrien * come before elements from the second. 301397403Sobrien * 301497403Sobrien * The comparison function should have the same effects on ordering as 301597403Sobrien * the function used for the initial sort. 301697403Sobrien */ 3017132720Skan template<typename _InputIterator1, typename _InputIterator2, 3018132720Skan typename _OutputIterator, typename _Compare> 3019132720Skan _OutputIterator 3020132720Skan merge(_InputIterator1 __first1, _InputIterator1 __last1, 3021132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 3022132720Skan _OutputIterator __result, _Compare __comp) 302397403Sobrien { 302497403Sobrien // concept requirements 3025132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 3026132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 3027132720Skan __glibcxx_function_requires(_SameTypeConcept< 3028132720Skan typename iterator_traits<_InputIterator1>::value_type, 3029132720Skan typename iterator_traits<_InputIterator2>::value_type>) 3030132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3031132720Skan typename iterator_traits<_InputIterator1>::value_type>) 3032132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3033132720Skan typename iterator_traits<_InputIterator1>::value_type, 3034132720Skan typename iterator_traits<_InputIterator2>::value_type>) 3035132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 3036132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 303797403Sobrien 3038132720Skan while (__first1 != __last1 && __first2 != __last2) 3039132720Skan { 3040132720Skan if (__comp(*__first2, *__first1)) 3041132720Skan { 3042132720Skan *__result = *__first2; 3043132720Skan ++__first2; 3044132720Skan } 3045132720Skan else 3046132720Skan { 3047132720Skan *__result = *__first1; 3048132720Skan ++__first1; 3049132720Skan } 3050132720Skan ++__result; 305197403Sobrien } 3052132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 3053132720Skan __result)); 3054132720Skan } 3055132720Skan 3056132720Skan template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 3057132720Skan typename _Distance> 3058132720Skan void 3059132720Skan __merge_sort_loop(_RandomAccessIterator1 __first, 3060132720Skan _RandomAccessIterator1 __last, 3061132720Skan _RandomAccessIterator2 __result, 3062132720Skan _Distance __step_size) 3063132720Skan { 3064132720Skan const _Distance __two_step = 2 * __step_size; 3065132720Skan 3066132720Skan while (__last - __first >= __two_step) 3067132720Skan { 3068132720Skan __result = std::merge(__first, __first + __step_size, 3069132720Skan __first + __step_size, __first + __two_step, 3070132720Skan __result); 3071132720Skan __first += __two_step; 307297403Sobrien } 3073132720Skan 3074132720Skan __step_size = std::min(_Distance(__last - __first), __step_size); 3075132720Skan std::merge(__first, __first + __step_size, __first + __step_size, __last, 3076132720Skan __result); 307797403Sobrien } 307897403Sobrien 3079132720Skan template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 3080132720Skan typename _Distance, typename _Compare> 308197403Sobrien void 3082132720Skan __merge_sort_loop(_RandomAccessIterator1 __first, 3083132720Skan _RandomAccessIterator1 __last, 3084132720Skan _RandomAccessIterator2 __result, _Distance __step_size, 3085132720Skan _Compare __comp) 308697403Sobrien { 3087132720Skan const _Distance __two_step = 2 * __step_size; 3088132720Skan 3089132720Skan while (__last - __first >= __two_step) 3090132720Skan { 3091132720Skan __result = std::merge(__first, __first + __step_size, 3092132720Skan __first + __step_size, __first + __two_step, 3093132720Skan __result, 3094132720Skan __comp); 3095132720Skan __first += __two_step; 3096132720Skan } 3097132720Skan __step_size = std::min(_Distance(__last - __first), __step_size); 3098132720Skan 3099132720Skan std::merge(__first, __first + __step_size, 3100132720Skan __first + __step_size, __last, 3101132720Skan __result, 3102132720Skan __comp); 310397403Sobrien } 310497403Sobrien 3105132720Skan enum { _S_chunk_size = 7 }; 3106132720Skan 3107132720Skan template<typename _RandomAccessIterator, typename _Distance> 310897403Sobrien void 3109132720Skan __chunk_insertion_sort(_RandomAccessIterator __first, 3110132720Skan _RandomAccessIterator __last, 3111132720Skan _Distance __chunk_size) 311297403Sobrien { 3113132720Skan while (__last - __first >= __chunk_size) 3114132720Skan { 3115132720Skan std::__insertion_sort(__first, __first + __chunk_size); 3116132720Skan __first += __chunk_size; 3117132720Skan } 3118132720Skan std::__insertion_sort(__first, __last); 311997403Sobrien } 312097403Sobrien 3121132720Skan template<typename _RandomAccessIterator, typename _Distance, typename _Compare> 3122132720Skan void 3123132720Skan __chunk_insertion_sort(_RandomAccessIterator __first, 3124132720Skan _RandomAccessIterator __last, 3125132720Skan _Distance __chunk_size, _Compare __comp) 312697403Sobrien { 3127132720Skan while (__last - __first >= __chunk_size) 3128132720Skan { 3129132720Skan std::__insertion_sort(__first, __first + __chunk_size, __comp); 3130132720Skan __first += __chunk_size; 3131132720Skan } 3132132720Skan std::__insertion_sort(__first, __last, __comp); 313397403Sobrien } 313497403Sobrien 3135132720Skan template<typename _RandomAccessIterator, typename _Pointer> 3136132720Skan void 3137132720Skan __merge_sort_with_buffer(_RandomAccessIterator __first, 3138132720Skan _RandomAccessIterator __last, 3139132720Skan _Pointer __buffer) 3140132720Skan { 3141132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3142132720Skan _Distance; 3143132720Skan 3144132720Skan const _Distance __len = __last - __first; 3145132720Skan const _Pointer __buffer_last = __buffer + __len; 3146132720Skan 3147132720Skan _Distance __step_size = _S_chunk_size; 3148132720Skan std::__chunk_insertion_sort(__first, __last, __step_size); 3149132720Skan 3150132720Skan while (__step_size < __len) 3151132720Skan { 3152132720Skan std::__merge_sort_loop(__first, __last, __buffer, __step_size); 3153132720Skan __step_size *= 2; 3154132720Skan std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 3155132720Skan __step_size *= 2; 3156132720Skan } 3157132720Skan } 3158132720Skan 3159132720Skan template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 3160132720Skan void 3161132720Skan __merge_sort_with_buffer(_RandomAccessIterator __first, 3162132720Skan _RandomAccessIterator __last, 3163132720Skan _Pointer __buffer, _Compare __comp) 3164132720Skan { 3165132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3166132720Skan _Distance; 3167132720Skan 3168132720Skan const _Distance __len = __last - __first; 3169132720Skan const _Pointer __buffer_last = __buffer + __len; 3170132720Skan 3171132720Skan _Distance __step_size = _S_chunk_size; 3172132720Skan std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 3173132720Skan 3174132720Skan while (__step_size < __len) 3175132720Skan { 3176132720Skan std::__merge_sort_loop(__first, __last, __buffer, 3177132720Skan __step_size, __comp); 3178132720Skan __step_size *= 2; 3179132720Skan std::__merge_sort_loop(__buffer, __buffer_last, __first, 3180132720Skan __step_size, __comp); 3181132720Skan __step_size *= 2; 3182132720Skan } 3183132720Skan } 3184132720Skan 318597403Sobrien /** 318697403Sobrien * @if maint 318797403Sobrien * This is a helper function for the merge routines. 318897403Sobrien * @endif 318997403Sobrien */ 3190132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 3191132720Skan typename _BidirectionalIterator3> 3192132720Skan _BidirectionalIterator3 3193132720Skan __merge_backward(_BidirectionalIterator1 __first1, 3194132720Skan _BidirectionalIterator1 __last1, 3195132720Skan _BidirectionalIterator2 __first2, 3196132720Skan _BidirectionalIterator2 __last2, 3197132720Skan _BidirectionalIterator3 __result) 319897403Sobrien { 319997403Sobrien if (__first1 == __last1) 3200132720Skan return std::copy_backward(__first2, __last2, __result); 320197403Sobrien if (__first2 == __last2) 3202132720Skan return std::copy_backward(__first1, __last1, __result); 320397403Sobrien --__last1; 320497403Sobrien --__last2; 3205132720Skan while (true) 3206132720Skan { 3207132720Skan if (*__last2 < *__last1) 3208132720Skan { 3209132720Skan *--__result = *__last1; 3210132720Skan if (__first1 == __last1) 3211132720Skan return std::copy_backward(__first2, ++__last2, __result); 3212132720Skan --__last1; 3213132720Skan } 3214132720Skan else 3215132720Skan { 3216132720Skan *--__result = *__last2; 3217132720Skan if (__first2 == __last2) 3218132720Skan return std::copy_backward(__first1, ++__last1, __result); 3219132720Skan --__last2; 3220132720Skan } 322197403Sobrien } 322297403Sobrien } 322397403Sobrien 322497403Sobrien /** 322597403Sobrien * @if maint 322697403Sobrien * This is a helper function for the merge routines. 322797403Sobrien * @endif 322897403Sobrien */ 3229132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 3230132720Skan typename _BidirectionalIterator3, typename _Compare> 3231132720Skan _BidirectionalIterator3 3232132720Skan __merge_backward(_BidirectionalIterator1 __first1, 3233132720Skan _BidirectionalIterator1 __last1, 3234132720Skan _BidirectionalIterator2 __first2, 3235132720Skan _BidirectionalIterator2 __last2, 3236132720Skan _BidirectionalIterator3 __result, 323797403Sobrien _Compare __comp) 323897403Sobrien { 323997403Sobrien if (__first1 == __last1) 3240132720Skan return std::copy_backward(__first2, __last2, __result); 324197403Sobrien if (__first2 == __last2) 3242132720Skan return std::copy_backward(__first1, __last1, __result); 324397403Sobrien --__last1; 324497403Sobrien --__last2; 3245132720Skan while (true) 3246132720Skan { 3247132720Skan if (__comp(*__last2, *__last1)) 3248132720Skan { 3249132720Skan *--__result = *__last1; 3250132720Skan if (__first1 == __last1) 3251132720Skan return std::copy_backward(__first2, ++__last2, __result); 3252132720Skan --__last1; 3253132720Skan } 3254132720Skan else 3255132720Skan { 3256132720Skan *--__result = *__last2; 3257132720Skan if (__first2 == __last2) 3258132720Skan return std::copy_backward(__first1, ++__last1, __result); 3259132720Skan --__last2; 3260132720Skan } 326197403Sobrien } 3262132720Skan } 3263132720Skan 3264132720Skan /** 3265132720Skan * @if maint 3266132720Skan * This is a helper function for the merge routines. 3267132720Skan * @endif 3268132720Skan */ 3269132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 3270132720Skan typename _Distance> 3271132720Skan _BidirectionalIterator1 3272132720Skan __rotate_adaptive(_BidirectionalIterator1 __first, 3273132720Skan _BidirectionalIterator1 __middle, 3274132720Skan _BidirectionalIterator1 __last, 3275132720Skan _Distance __len1, _Distance __len2, 3276132720Skan _BidirectionalIterator2 __buffer, 3277132720Skan _Distance __buffer_size) 3278132720Skan { 3279132720Skan _BidirectionalIterator2 __buffer_end; 3280132720Skan if (__len1 > __len2 && __len2 <= __buffer_size) 3281132720Skan { 3282132720Skan __buffer_end = std::copy(__middle, __last, __buffer); 3283132720Skan std::copy_backward(__first, __middle, __last); 3284132720Skan return std::copy(__buffer, __buffer_end, __first); 328597403Sobrien } 3286132720Skan else if (__len1 <= __buffer_size) 3287132720Skan { 3288132720Skan __buffer_end = std::copy(__first, __middle, __buffer); 3289132720Skan std::copy(__middle, __last, __first); 3290132720Skan return std::copy_backward(__buffer, __buffer_end, __last); 3291132720Skan } 3292132720Skan else 3293132720Skan { 3294132720Skan std::rotate(__first, __middle, __last); 3295132720Skan std::advance(__first, std::distance(__middle, __last)); 3296132720Skan return __first; 3297132720Skan } 329897403Sobrien } 329997403Sobrien 330097403Sobrien /** 330197403Sobrien * @if maint 330297403Sobrien * This is a helper function for the merge routines. 330397403Sobrien * @endif 330497403Sobrien */ 3305132720Skan template<typename _BidirectionalIterator, typename _Distance, 3306132720Skan typename _Pointer> 330797403Sobrien void 3308132720Skan __merge_adaptive(_BidirectionalIterator __first, 3309132720Skan _BidirectionalIterator __middle, 3310132720Skan _BidirectionalIterator __last, 331197403Sobrien _Distance __len1, _Distance __len2, 331297403Sobrien _Pointer __buffer, _Distance __buffer_size) 331397403Sobrien { 3314132720Skan if (__len1 <= __len2 && __len1 <= __buffer_size) 3315132720Skan { 3316132720Skan _Pointer __buffer_end = std::copy(__first, __middle, __buffer); 3317132720Skan std::merge(__buffer, __buffer_end, __middle, __last, __first); 3318132720Skan } 3319132720Skan else if (__len2 <= __buffer_size) 3320132720Skan { 3321132720Skan _Pointer __buffer_end = std::copy(__middle, __last, __buffer); 3322132720Skan std::__merge_backward(__first, __middle, __buffer, 3323132720Skan __buffer_end, __last); 3324132720Skan } 3325132720Skan else 3326132720Skan { 3327132720Skan _BidirectionalIterator __first_cut = __first; 3328132720Skan _BidirectionalIterator __second_cut = __middle; 3329132720Skan _Distance __len11 = 0; 3330132720Skan _Distance __len22 = 0; 3331132720Skan if (__len1 > __len2) 3332132720Skan { 3333132720Skan __len11 = __len1 / 2; 3334132720Skan std::advance(__first_cut, __len11); 3335132720Skan __second_cut = std::lower_bound(__middle, __last, 3336132720Skan *__first_cut); 3337132720Skan __len22 = std::distance(__middle, __second_cut); 333897403Sobrien } 3339132720Skan else 3340132720Skan { 3341132720Skan __len22 = __len2 / 2; 3342132720Skan std::advance(__second_cut, __len22); 3343132720Skan __first_cut = std::upper_bound(__first, __middle, 3344132720Skan *__second_cut); 3345132720Skan __len11 = std::distance(__first, __first_cut); 334697403Sobrien } 3347132720Skan _BidirectionalIterator __new_middle = 3348132720Skan std::__rotate_adaptive(__first_cut, __middle, __second_cut, 3349132720Skan __len1 - __len11, __len22, __buffer, 3350132720Skan __buffer_size); 3351132720Skan std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 3352132720Skan __len22, __buffer, __buffer_size); 3353132720Skan std::__merge_adaptive(__new_middle, __second_cut, __last, 3354132720Skan __len1 - __len11, 3355132720Skan __len2 - __len22, __buffer, __buffer_size); 3356132720Skan } 335797403Sobrien } 335897403Sobrien 335997403Sobrien /** 336097403Sobrien * @if maint 336197403Sobrien * This is a helper function for the merge routines. 336297403Sobrien * @endif 336397403Sobrien */ 3364132720Skan template<typename _BidirectionalIterator, typename _Distance, typename _Pointer, 336597403Sobrien typename _Compare> 336697403Sobrien void 3367132720Skan __merge_adaptive(_BidirectionalIterator __first, 3368132720Skan _BidirectionalIterator __middle, 3369132720Skan _BidirectionalIterator __last, 337097403Sobrien _Distance __len1, _Distance __len2, 337197403Sobrien _Pointer __buffer, _Distance __buffer_size, 337297403Sobrien _Compare __comp) 337397403Sobrien { 3374132720Skan if (__len1 <= __len2 && __len1 <= __buffer_size) 3375132720Skan { 3376132720Skan _Pointer __buffer_end = std::copy(__first, __middle, __buffer); 3377132720Skan std::merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 3378132720Skan } 3379132720Skan else if (__len2 <= __buffer_size) 3380132720Skan { 3381132720Skan _Pointer __buffer_end = std::copy(__middle, __last, __buffer); 3382132720Skan std::__merge_backward(__first, __middle, __buffer, __buffer_end, 3383132720Skan __last, __comp); 3384132720Skan } 3385132720Skan else 3386132720Skan { 3387132720Skan _BidirectionalIterator __first_cut = __first; 3388132720Skan _BidirectionalIterator __second_cut = __middle; 3389132720Skan _Distance __len11 = 0; 3390132720Skan _Distance __len22 = 0; 3391132720Skan if (__len1 > __len2) 3392132720Skan { 3393132720Skan __len11 = __len1 / 2; 3394132720Skan std::advance(__first_cut, __len11); 3395132720Skan __second_cut = std::lower_bound(__middle, __last, *__first_cut, 3396132720Skan __comp); 3397132720Skan __len22 = std::distance(__middle, __second_cut); 3398132720Skan } 3399132720Skan else 3400132720Skan { 3401132720Skan __len22 = __len2 / 2; 3402132720Skan std::advance(__second_cut, __len22); 3403132720Skan __first_cut = std::upper_bound(__first, __middle, *__second_cut, 340497403Sobrien __comp); 3405132720Skan __len11 = std::distance(__first, __first_cut); 340697403Sobrien } 3407132720Skan _BidirectionalIterator __new_middle = 3408132720Skan std::__rotate_adaptive(__first_cut, __middle, __second_cut, 3409132720Skan __len1 - __len11, __len22, __buffer, 3410132720Skan __buffer_size); 3411132720Skan std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 3412132720Skan __len22, __buffer, __buffer_size, __comp); 3413132720Skan std::__merge_adaptive(__new_middle, __second_cut, __last, 3414132720Skan __len1 - __len11, 3415132720Skan __len2 - __len22, __buffer, 3416132720Skan __buffer_size, __comp); 3417132720Skan } 341897403Sobrien } 341997403Sobrien 342097403Sobrien /** 342197403Sobrien * @brief Merges two sorted ranges in place. 342297403Sobrien * @param first An iterator. 342397403Sobrien * @param middle Another iterator. 342497403Sobrien * @param last Another iterator. 342597403Sobrien * @return Nothing. 342697403Sobrien * 342797403Sobrien * Merges two sorted and consecutive ranges, [first,middle) and 342897403Sobrien * [middle,last), and puts the result in [first,last). The output will 342997403Sobrien * be sorted. The sort is @e stable, that is, for equivalent 343097403Sobrien * elements in the two ranges, elements from the first range will always 343197403Sobrien * come before elements from the second. 343297403Sobrien * 343397403Sobrien * If enough additional memory is available, this takes (last-first)-1 343497403Sobrien * comparisons. Otherwise an NlogN algorithm is used, where N is 343597403Sobrien * distance(first,last). 343697403Sobrien */ 3437132720Skan template<typename _BidirectionalIterator> 343897403Sobrien void 3439132720Skan inplace_merge(_BidirectionalIterator __first, 3440132720Skan _BidirectionalIterator __middle, 3441132720Skan _BidirectionalIterator __last) 344297403Sobrien { 3443132720Skan typedef typename iterator_traits<_BidirectionalIterator>::value_type 344497403Sobrien _ValueType; 3445132720Skan typedef typename iterator_traits<_BidirectionalIterator>::difference_type 344697403Sobrien _DistanceType; 344797403Sobrien 344897403Sobrien // concept requirements 3449132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 3450132720Skan _BidirectionalIterator>) 3451132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 3452132720Skan __glibcxx_requires_sorted(__first, __middle); 3453132720Skan __glibcxx_requires_sorted(__middle, __last); 345497403Sobrien 345597403Sobrien if (__first == __middle || __middle == __last) 345697403Sobrien return; 345797403Sobrien 3458132720Skan _DistanceType __len1 = std::distance(__first, __middle); 3459132720Skan _DistanceType __len2 = std::distance(__middle, __last); 346097403Sobrien 3461132720Skan _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 3462132720Skan __last); 346397403Sobrien if (__buf.begin() == 0) 3464132720Skan std::__merge_without_buffer(__first, __middle, __last, __len1, __len2); 346597403Sobrien else 3466132720Skan std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 3467132720Skan __buf.begin(), _DistanceType(__buf.size())); 346897403Sobrien } 346997403Sobrien 347097403Sobrien /** 347197403Sobrien * @brief Merges two sorted ranges in place. 347297403Sobrien * @param first An iterator. 347397403Sobrien * @param middle Another iterator. 347497403Sobrien * @param last Another iterator. 347597403Sobrien * @param comp A functor to use for comparisons. 347697403Sobrien * @return Nothing. 347797403Sobrien * 347897403Sobrien * Merges two sorted and consecutive ranges, [first,middle) and 347997403Sobrien * [middle,last), and puts the result in [first,last). The output will 348097403Sobrien * be sorted. The sort is @e stable, that is, for equivalent 348197403Sobrien * elements in the two ranges, elements from the first range will always 348297403Sobrien * come before elements from the second. 348397403Sobrien * 348497403Sobrien * If enough additional memory is available, this takes (last-first)-1 348597403Sobrien * comparisons. Otherwise an NlogN algorithm is used, where N is 348697403Sobrien * distance(first,last). 348797403Sobrien * 348897403Sobrien * The comparison function should have the same effects on ordering as 348997403Sobrien * the function used for the initial sort. 349097403Sobrien */ 3491132720Skan template<typename _BidirectionalIterator, typename _Compare> 349297403Sobrien void 3493132720Skan inplace_merge(_BidirectionalIterator __first, 3494132720Skan _BidirectionalIterator __middle, 3495132720Skan _BidirectionalIterator __last, 349697403Sobrien _Compare __comp) 349797403Sobrien { 3498132720Skan typedef typename iterator_traits<_BidirectionalIterator>::value_type 349997403Sobrien _ValueType; 3500132720Skan typedef typename iterator_traits<_BidirectionalIterator>::difference_type 350197403Sobrien _DistanceType; 350297403Sobrien 350397403Sobrien // concept requirements 3504132720Skan __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 3505132720Skan _BidirectionalIterator>) 3506132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 350797403Sobrien _ValueType, _ValueType>) 3508132720Skan __glibcxx_requires_sorted_pred(__first, __middle, __comp); 3509132720Skan __glibcxx_requires_sorted_pred(__middle, __last, __comp); 351097403Sobrien 351197403Sobrien if (__first == __middle || __middle == __last) 351297403Sobrien return; 351397403Sobrien 3514132720Skan const _DistanceType __len1 = std::distance(__first, __middle); 3515132720Skan const _DistanceType __len2 = std::distance(__middle, __last); 351697403Sobrien 3517132720Skan _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first, 3518132720Skan __last); 351997403Sobrien if (__buf.begin() == 0) 3520132720Skan std::__merge_without_buffer(__first, __middle, __last, __len1, 3521132720Skan __len2, __comp); 352297403Sobrien else 3523132720Skan std::__merge_adaptive(__first, __middle, __last, __len1, __len2, 3524132720Skan __buf.begin(), _DistanceType(__buf.size()), 3525132720Skan __comp); 352697403Sobrien } 352797403Sobrien 3528132720Skan template<typename _RandomAccessIterator, typename _Pointer, 3529132720Skan typename _Distance> 3530132720Skan void 3531132720Skan __stable_sort_adaptive(_RandomAccessIterator __first, 3532132720Skan _RandomAccessIterator __last, 3533132720Skan _Pointer __buffer, _Distance __buffer_size) 3534132720Skan { 3535132720Skan const _Distance __len = (__last - __first + 1) / 2; 3536132720Skan const _RandomAccessIterator __middle = __first + __len; 3537132720Skan if (__len > __buffer_size) 3538132720Skan { 3539132720Skan std::__stable_sort_adaptive(__first, __middle, 3540132720Skan __buffer, __buffer_size); 3541132720Skan std::__stable_sort_adaptive(__middle, __last, 3542132720Skan __buffer, __buffer_size); 3543132720Skan } 3544132720Skan else 3545132720Skan { 3546132720Skan std::__merge_sort_with_buffer(__first, __middle, __buffer); 3547132720Skan std::__merge_sort_with_buffer(__middle, __last, __buffer); 3548132720Skan } 3549132720Skan std::__merge_adaptive(__first, __middle, __last, 3550132720Skan _Distance(__middle - __first), 3551132720Skan _Distance(__last - __middle), 3552132720Skan __buffer, __buffer_size); 3553132720Skan } 3554132720Skan 3555132720Skan template<typename _RandomAccessIterator, typename _Pointer, 3556132720Skan typename _Distance, typename _Compare> 3557132720Skan void 3558132720Skan __stable_sort_adaptive(_RandomAccessIterator __first, 3559132720Skan _RandomAccessIterator __last, 3560132720Skan _Pointer __buffer, _Distance __buffer_size, 3561132720Skan _Compare __comp) 3562132720Skan { 3563132720Skan const _Distance __len = (__last - __first + 1) / 2; 3564132720Skan const _RandomAccessIterator __middle = __first + __len; 3565132720Skan if (__len > __buffer_size) 3566132720Skan { 3567132720Skan std::__stable_sort_adaptive(__first, __middle, __buffer, 3568132720Skan __buffer_size, __comp); 3569132720Skan std::__stable_sort_adaptive(__middle, __last, __buffer, 3570132720Skan __buffer_size, __comp); 3571132720Skan } 3572132720Skan else 3573132720Skan { 3574132720Skan std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 3575132720Skan std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 3576132720Skan } 3577132720Skan std::__merge_adaptive(__first, __middle, __last, 3578132720Skan _Distance(__middle - __first), 3579132720Skan _Distance(__last - __middle), 3580132720Skan __buffer, __buffer_size, 3581132720Skan __comp); 3582132720Skan } 3583132720Skan 3584132720Skan /** 3585132720Skan * @brief Sort the elements of a sequence, preserving the relative order 3586132720Skan * of equivalent elements. 3587132720Skan * @param first An iterator. 3588132720Skan * @param last Another iterator. 3589132720Skan * @return Nothing. 3590132720Skan * 3591132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 3592132720Skan * such that @p *(i+1)<*i is false for each iterator @p i in the range 3593132720Skan * @p [first,last-1). 3594132720Skan * 3595132720Skan * The relative ordering of equivalent elements is preserved, so any two 3596132720Skan * elements @p x and @p y in the range @p [first,last) such that 3597132720Skan * @p x<y is false and @p y<x is false will have the same relative 3598132720Skan * ordering after calling @p stable_sort(). 3599132720Skan */ 3600132720Skan template<typename _RandomAccessIterator> 3601132720Skan inline void 3602132720Skan stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 3603132720Skan { 3604132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3605132720Skan _ValueType; 3606132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3607132720Skan _DistanceType; 3608132720Skan 3609132720Skan // concept requirements 3610132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3611132720Skan _RandomAccessIterator>) 3612132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 3613132720Skan __glibcxx_requires_valid_range(__first, __last); 3614132720Skan 3615132720Skan _Temporary_buffer<_RandomAccessIterator, _ValueType> 3616132720Skan buf(__first, __last); 3617132720Skan if (buf.begin() == 0) 3618132720Skan std::__inplace_stable_sort(__first, __last); 3619132720Skan else 3620132720Skan std::__stable_sort_adaptive(__first, __last, buf.begin(), 3621132720Skan _DistanceType(buf.size())); 3622132720Skan } 3623132720Skan 3624132720Skan /** 3625132720Skan * @brief Sort the elements of a sequence using a predicate for comparison, 3626132720Skan * preserving the relative order of equivalent elements. 3627132720Skan * @param first An iterator. 3628132720Skan * @param last Another iterator. 3629132720Skan * @param comp A comparison functor. 3630132720Skan * @return Nothing. 3631132720Skan * 3632132720Skan * Sorts the elements in the range @p [first,last) in ascending order, 3633132720Skan * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 3634132720Skan * range @p [first,last-1). 3635132720Skan * 3636132720Skan * The relative ordering of equivalent elements is preserved, so any two 3637132720Skan * elements @p x and @p y in the range @p [first,last) such that 3638132720Skan * @p comp(x,y) is false and @p comp(y,x) is false will have the same 3639132720Skan * relative ordering after calling @p stable_sort(). 3640132720Skan */ 3641132720Skan template<typename _RandomAccessIterator, typename _Compare> 3642132720Skan inline void 3643132720Skan stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 3644132720Skan _Compare __comp) 3645132720Skan { 3646132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3647132720Skan _ValueType; 3648132720Skan typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3649132720Skan _DistanceType; 3650132720Skan 3651132720Skan // concept requirements 3652132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3653132720Skan _RandomAccessIterator>) 3654132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3655132720Skan _ValueType, 3656132720Skan _ValueType>) 3657132720Skan __glibcxx_requires_valid_range(__first, __last); 3658132720Skan 3659132720Skan _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last); 3660132720Skan if (buf.begin() == 0) 3661132720Skan std::__inplace_stable_sort(__first, __last, __comp); 3662132720Skan else 3663132720Skan std::__stable_sort_adaptive(__first, __last, buf.begin(), 3664132720Skan _DistanceType(buf.size()), __comp); 3665132720Skan } 3666132720Skan 3667132720Skan /** 3668132720Skan * @brief Sort a sequence just enough to find a particular position. 3669132720Skan * @param first An iterator. 3670132720Skan * @param nth Another iterator. 3671132720Skan * @param last Another iterator. 3672132720Skan * @return Nothing. 3673132720Skan * 3674132720Skan * Rearranges the elements in the range @p [first,last) so that @p *nth 3675132720Skan * is the same element that would have been in that position had the 3676132720Skan * whole sequence been sorted. 3677132720Skan * whole sequence been sorted. The elements either side of @p *nth are 3678132720Skan * not completely sorted, but for any iterator @i in the range 3679132720Skan * @p [first,nth) and any iterator @j in the range @p [nth,last) it 3680132720Skan * holds that @p *j<*i is false. 3681132720Skan */ 3682132720Skan template<typename _RandomAccessIterator> 3683132720Skan void 3684132720Skan nth_element(_RandomAccessIterator __first, 3685132720Skan _RandomAccessIterator __nth, 3686132720Skan _RandomAccessIterator __last) 3687132720Skan { 3688132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3689132720Skan _ValueType; 3690132720Skan 3691132720Skan // concept requirements 3692132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3693132720Skan _RandomAccessIterator>) 3694132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 3695132720Skan __glibcxx_requires_valid_range(__first, __nth); 3696132720Skan __glibcxx_requires_valid_range(__nth, __last); 3697132720Skan 3698132720Skan while (__last - __first > 3) 3699132720Skan { 3700132720Skan _RandomAccessIterator __cut = 3701132720Skan std::__unguarded_partition(__first, __last, 3702132720Skan _ValueType(std::__median(*__first, 3703132720Skan *(__first 3704132720Skan + (__last 3705132720Skan - __first) 3706132720Skan / 2), 3707132720Skan *(__last 3708132720Skan - 1)))); 3709132720Skan if (__cut <= __nth) 3710132720Skan __first = __cut; 3711132720Skan else 3712132720Skan __last = __cut; 3713132720Skan } 3714132720Skan std::__insertion_sort(__first, __last); 3715132720Skan } 3716132720Skan 3717132720Skan /** 3718132720Skan * @brief Sort a sequence just enough to find a particular position 3719132720Skan * using a predicate for comparison. 3720132720Skan * @param first An iterator. 3721132720Skan * @param nth Another iterator. 3722132720Skan * @param last Another iterator. 3723132720Skan * @param comp A comparison functor. 3724132720Skan * @return Nothing. 3725132720Skan * 3726132720Skan * Rearranges the elements in the range @p [first,last) so that @p *nth 3727132720Skan * is the same element that would have been in that position had the 3728132720Skan * whole sequence been sorted. The elements either side of @p *nth are 3729132720Skan * not completely sorted, but for any iterator @i in the range 3730132720Skan * @p [first,nth) and any iterator @j in the range @p [nth,last) it 3731132720Skan * holds that @p comp(*j,*i) is false. 3732132720Skan */ 3733132720Skan template<typename _RandomAccessIterator, typename _Compare> 3734132720Skan void 3735132720Skan nth_element(_RandomAccessIterator __first, 3736132720Skan _RandomAccessIterator __nth, 3737132720Skan _RandomAccessIterator __last, 3738132720Skan _Compare __comp) 3739132720Skan { 3740132720Skan typedef typename iterator_traits<_RandomAccessIterator>::value_type 3741132720Skan _ValueType; 3742132720Skan 3743132720Skan // concept requirements 3744132720Skan __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3745132720Skan _RandomAccessIterator>) 3746132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3747132720Skan _ValueType, _ValueType>) 3748132720Skan __glibcxx_requires_valid_range(__first, __nth); 3749132720Skan __glibcxx_requires_valid_range(__nth, __last); 3750132720Skan 3751132720Skan while (__last - __first > 3) 3752132720Skan { 3753132720Skan _RandomAccessIterator __cut = 3754132720Skan std::__unguarded_partition(__first, __last, 3755132720Skan _ValueType(std::__median(*__first, 3756132720Skan *(__first 3757132720Skan + (__last 3758132720Skan - __first) 3759132720Skan / 2), 3760132720Skan *(__last - 1), 3761132720Skan __comp)), __comp); 3762132720Skan if (__cut <= __nth) 3763132720Skan __first = __cut; 3764132720Skan else 3765132720Skan __last = __cut; 3766132720Skan } 3767132720Skan std::__insertion_sort(__first, __last, __comp); 3768132720Skan } 3769132720Skan 3770132720Skan /** 3771132720Skan * @brief Finds the largest subrange in which @a val could be inserted 3772132720Skan * at any place in it without changing the ordering. 3773132720Skan * @param first An iterator. 3774132720Skan * @param last Another iterator. 3775132720Skan * @param val The search term. 3776132720Skan * @return An pair of iterators defining the subrange. 3777132720Skan * @ingroup binarysearch 3778132720Skan * 3779132720Skan * This is equivalent to 3780132720Skan * @code 3781132720Skan * std::make_pair(lower_bound(first, last, val), 3782132720Skan * upper_bound(first, last, val)) 3783132720Skan * @endcode 3784132720Skan * but does not actually call those functions. 3785132720Skan */ 3786132720Skan template<typename _ForwardIterator, typename _Tp> 3787132720Skan pair<_ForwardIterator, _ForwardIterator> 3788132720Skan equal_range(_ForwardIterator __first, _ForwardIterator __last, 3789132720Skan const _Tp& __val) 3790132720Skan { 3791132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 3792132720Skan _ValueType; 3793132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 3794132720Skan _DistanceType; 3795132720Skan 3796132720Skan // concept requirements 3797132720Skan // See comments on lower_bound. 3798132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3799132720Skan __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) 3800132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 3801132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 3802132720Skan 3803132720Skan _DistanceType __len = std::distance(__first, __last); 3804132720Skan _DistanceType __half; 3805132720Skan _ForwardIterator __middle, __left, __right; 3806132720Skan 3807132720Skan while (__len > 0) 3808132720Skan { 3809132720Skan __half = __len >> 1; 3810132720Skan __middle = __first; 3811132720Skan std::advance(__middle, __half); 3812132720Skan if (*__middle < __val) 3813132720Skan { 3814132720Skan __first = __middle; 3815132720Skan ++__first; 3816132720Skan __len = __len - __half - 1; 3817132720Skan } 3818132720Skan else if (__val < *__middle) 3819132720Skan __len = __half; 3820132720Skan else 3821132720Skan { 3822132720Skan __left = std::lower_bound(__first, __middle, __val); 3823132720Skan std::advance(__first, __len); 3824132720Skan __right = std::upper_bound(++__middle, __first, __val); 3825132720Skan return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 3826132720Skan } 3827132720Skan } 3828132720Skan return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 3829132720Skan } 3830132720Skan 3831132720Skan /** 3832132720Skan * @brief Finds the largest subrange in which @a val could be inserted 3833132720Skan * at any place in it without changing the ordering. 3834132720Skan * @param first An iterator. 3835132720Skan * @param last Another iterator. 3836132720Skan * @param val The search term. 3837132720Skan * @param comp A functor to use for comparisons. 3838132720Skan * @return An pair of iterators defining the subrange. 3839132720Skan * @ingroup binarysearch 3840132720Skan * 3841132720Skan * This is equivalent to 3842132720Skan * @code 3843132720Skan * std::make_pair(lower_bound(first, last, val, comp), 3844132720Skan * upper_bound(first, last, val, comp)) 3845132720Skan * @endcode 3846132720Skan * but does not actually call those functions. 3847132720Skan */ 3848132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 3849132720Skan pair<_ForwardIterator, _ForwardIterator> 3850132720Skan equal_range(_ForwardIterator __first, _ForwardIterator __last, 3851132720Skan const _Tp& __val, 3852132720Skan _Compare __comp) 3853132720Skan { 3854132720Skan typedef typename iterator_traits<_ForwardIterator>::value_type 3855132720Skan _ValueType; 3856132720Skan typedef typename iterator_traits<_ForwardIterator>::difference_type 3857132720Skan _DistanceType; 3858132720Skan 3859132720Skan // concept requirements 3860132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3861132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3862132720Skan _ValueType, _Tp>) 3863132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3864132720Skan _Tp, _ValueType>) 3865132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 3866132720Skan 3867132720Skan _DistanceType __len = std::distance(__first, __last); 3868132720Skan _DistanceType __half; 3869132720Skan _ForwardIterator __middle, __left, __right; 3870132720Skan 3871132720Skan while (__len > 0) 3872132720Skan { 3873132720Skan __half = __len >> 1; 3874132720Skan __middle = __first; 3875132720Skan std::advance(__middle, __half); 3876132720Skan if (__comp(*__middle, __val)) 3877132720Skan { 3878132720Skan __first = __middle; 3879132720Skan ++__first; 3880132720Skan __len = __len - __half - 1; 3881132720Skan } 3882132720Skan else if (__comp(__val, *__middle)) 3883132720Skan __len = __half; 3884132720Skan else 3885132720Skan { 3886132720Skan __left = std::lower_bound(__first, __middle, __val, __comp); 3887132720Skan std::advance(__first, __len); 3888132720Skan __right = std::upper_bound(++__middle, __first, __val, __comp); 3889132720Skan return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 3890132720Skan } 3891132720Skan } 3892132720Skan return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 3893132720Skan } 3894132720Skan 3895132720Skan /** 3896132720Skan * @brief Determines whether an element exists in a range. 3897132720Skan * @param first An iterator. 3898132720Skan * @param last Another iterator. 3899132720Skan * @param val The search term. 3900132720Skan * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 3901132720Skan * @ingroup binarysearch 3902132720Skan * 3903132720Skan * Note that this does not actually return an iterator to @a val. For 3904132720Skan * that, use std::find or a container's specialized find member functions. 3905132720Skan */ 3906132720Skan template<typename _ForwardIterator, typename _Tp> 3907132720Skan bool 3908132720Skan binary_search(_ForwardIterator __first, _ForwardIterator __last, 3909132720Skan const _Tp& __val) 3910132720Skan { 3911132720Skan // concept requirements 3912132720Skan // See comments on lower_bound. 3913132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3914132720Skan __glibcxx_function_requires(_SameTypeConcept<_Tp, 3915132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 3916132720Skan __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 3917132720Skan __glibcxx_requires_partitioned(__first, __last, __val); 3918132720Skan 3919132720Skan _ForwardIterator __i = std::lower_bound(__first, __last, __val); 3920132720Skan return __i != __last && !(__val < *__i); 3921132720Skan } 3922132720Skan 3923132720Skan /** 3924132720Skan * @brief Determines whether an element exists in a range. 3925132720Skan * @param first An iterator. 3926132720Skan * @param last Another iterator. 3927132720Skan * @param val The search term. 3928132720Skan * @param comp A functor to use for comparisons. 3929132720Skan * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 3930132720Skan * @ingroup binarysearch 3931132720Skan * 3932132720Skan * Note that this does not actually return an iterator to @a val. For 3933132720Skan * that, use std::find or a container's specialized find member functions. 3934132720Skan * 3935132720Skan * The comparison function should have the same effects on ordering as 3936132720Skan * the function used for the initial sort. 3937132720Skan */ 3938132720Skan template<typename _ForwardIterator, typename _Tp, typename _Compare> 3939132720Skan bool 3940132720Skan binary_search(_ForwardIterator __first, _ForwardIterator __last, 3941132720Skan const _Tp& __val, _Compare __comp) 3942132720Skan { 3943132720Skan // concept requirements 3944132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3945132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3946132720Skan typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 3947132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, 3948132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 3949132720Skan __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); 3950132720Skan 3951132720Skan _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp); 3952132720Skan return __i != __last && !__comp(__val, *__i); 3953132720Skan } 3954132720Skan 395597403Sobrien // Set algorithms: includes, set_union, set_intersection, set_difference, 395697403Sobrien // set_symmetric_difference. All of these algorithms have the precondition 395797403Sobrien // that their input ranges are sorted and the postcondition that their output 395897403Sobrien // ranges are sorted. 395997403Sobrien 3960132720Skan /** 3961132720Skan * @brief Determines whether all elements of a sequence exists in a range. 3962132720Skan * @param first1 Start of search range. 3963132720Skan * @param last1 End of search range. 3964132720Skan * @param first2 Start of sequence 3965132720Skan * @param last2 End of sequence. 3966132720Skan * @return True if each element in [first2,last2) is contained in order 3967132720Skan * within [first1,last1). False otherwise. 3968132720Skan * @ingroup setoperations 3969132720Skan * 3970132720Skan * This operation expects both [first1,last1) and [first2,last2) to be 3971132720Skan * sorted. Searches for the presence of each element in [first2,last2) 3972132720Skan * within [first1,last1). The iterators over each range only move forward, 3973132720Skan * so this is a linear algorithm. If an element in [first2,last2) is not 3974132720Skan * found before the search iterator reaches @a last2, false is returned. 3975132720Skan */ 3976132720Skan template<typename _InputIterator1, typename _InputIterator2> 397797403Sobrien bool 3978132720Skan includes(_InputIterator1 __first1, _InputIterator1 __last1, 3979132720Skan _InputIterator2 __first2, _InputIterator2 __last2) 398097403Sobrien { 398197403Sobrien // concept requirements 3982132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 3983132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 3984132720Skan __glibcxx_function_requires(_SameTypeConcept< 3985132720Skan typename iterator_traits<_InputIterator1>::value_type, 3986132720Skan typename iterator_traits<_InputIterator2>::value_type>) 3987132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 3988132720Skan typename iterator_traits<_InputIterator1>::value_type>) 3989132720Skan __glibcxx_requires_sorted(__first1, __last1); 3990132720Skan __glibcxx_requires_sorted(__first2, __last2); 399197403Sobrien 399297403Sobrien while (__first1 != __last1 && __first2 != __last2) 399397403Sobrien if (*__first2 < *__first1) 399497403Sobrien return false; 399597403Sobrien else if(*__first1 < *__first2) 399697403Sobrien ++__first1; 399797403Sobrien else 399897403Sobrien ++__first1, ++__first2; 399997403Sobrien 400097403Sobrien return __first2 == __last2; 400197403Sobrien } 400297403Sobrien 4003132720Skan /** 4004132720Skan * @brief Determines whether all elements of a sequence exists in a range 4005132720Skan * using comparison. 4006132720Skan * @param first1 Start of search range. 4007132720Skan * @param last1 End of search range. 4008132720Skan * @param first2 Start of sequence 4009132720Skan * @param last2 End of sequence. 4010132720Skan * @param comp Comparison function to use. 4011132720Skan * @return True if each element in [first2,last2) is contained in order 4012132720Skan * within [first1,last1) according to comp. False otherwise. 4013132720Skan * @ingroup setoperations 4014132720Skan * 4015132720Skan * This operation expects both [first1,last1) and [first2,last2) to be 4016132720Skan * sorted. Searches for the presence of each element in [first2,last2) 4017132720Skan * within [first1,last1), using comp to decide. The iterators over each 4018132720Skan * range only move forward, so this is a linear algorithm. If an element 4019132720Skan * in [first2,last2) is not found before the search iterator reaches @a 4020132720Skan * last2, false is returned. 4021132720Skan */ 4022132720Skan template<typename _InputIterator1, typename _InputIterator2, 4023132720Skan typename _Compare> 402497403Sobrien bool 4025132720Skan includes(_InputIterator1 __first1, _InputIterator1 __last1, 4026132720Skan _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) 402797403Sobrien { 402897403Sobrien // concept requirements 4029132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4030132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4031132720Skan __glibcxx_function_requires(_SameTypeConcept< 4032132720Skan typename iterator_traits<_InputIterator1>::value_type, 4033132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4034132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4035132720Skan typename iterator_traits<_InputIterator1>::value_type, 4036132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4037132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4038132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 403997403Sobrien 404097403Sobrien while (__first1 != __last1 && __first2 != __last2) 404197403Sobrien if (__comp(*__first2, *__first1)) 404297403Sobrien return false; 404397403Sobrien else if(__comp(*__first1, *__first2)) 404497403Sobrien ++__first1; 404597403Sobrien else 404697403Sobrien ++__first1, ++__first2; 404797403Sobrien 404897403Sobrien return __first2 == __last2; 404997403Sobrien } 405097403Sobrien 4051132720Skan /** 4052132720Skan * @brief Return the union of two sorted ranges. 4053132720Skan * @param first1 Start of first range. 4054132720Skan * @param last1 End of first range. 4055132720Skan * @param first2 Start of second range. 4056132720Skan * @param last2 End of second range. 4057132720Skan * @return End of the output range. 4058132720Skan * @ingroup setoperations 4059132720Skan * 4060132720Skan * This operation iterates over both ranges, copying elements present in 4061132720Skan * each range in order to the output range. Iterators increment for each 4062132720Skan * range. When the current element of one range is less than the other, 4063132720Skan * that element is copied and the iterator advanced. If an element is 4064132720Skan * contained in both ranges, the element from the first range is copied and 4065132720Skan * both ranges advance. The output range may not overlap either input 4066132720Skan * range. 4067132720Skan */ 4068132720Skan template<typename _InputIterator1, typename _InputIterator2, 4069132720Skan typename _OutputIterator> 4070132720Skan _OutputIterator 4071132720Skan set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4072132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4073132720Skan _OutputIterator __result) 407497403Sobrien { 407597403Sobrien // concept requirements 4076132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4077132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4078132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4079132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4080132720Skan __glibcxx_function_requires(_SameTypeConcept< 4081132720Skan typename iterator_traits<_InputIterator1>::value_type, 4082132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4083132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4084132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4085132720Skan __glibcxx_requires_sorted(__first1, __last1); 4086132720Skan __glibcxx_requires_sorted(__first2, __last2); 408797403Sobrien 4088132720Skan while (__first1 != __last1 && __first2 != __last2) 4089132720Skan { 4090132720Skan if (*__first1 < *__first2) 4091132720Skan { 4092132720Skan *__result = *__first1; 4093132720Skan ++__first1; 4094132720Skan } 4095132720Skan else if (*__first2 < *__first1) 4096132720Skan { 4097132720Skan *__result = *__first2; 4098132720Skan ++__first2; 4099132720Skan } 4100132720Skan else 4101132720Skan { 4102132720Skan *__result = *__first1; 4103132720Skan ++__first1; 4104132720Skan ++__first2; 4105132720Skan } 4106132720Skan ++__result; 410797403Sobrien } 4108132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 4109132720Skan __result)); 411097403Sobrien } 411197403Sobrien 4112132720Skan /** 4113132720Skan * @brief Return the union of two sorted ranges using a comparison functor. 4114132720Skan * @param first1 Start of first range. 4115132720Skan * @param last1 End of first range. 4116132720Skan * @param first2 Start of second range. 4117132720Skan * @param last2 End of second range. 4118132720Skan * @param comp The comparison functor. 4119132720Skan * @return End of the output range. 4120132720Skan * @ingroup setoperations 4121132720Skan * 4122132720Skan * This operation iterates over both ranges, copying elements present in 4123132720Skan * each range in order to the output range. Iterators increment for each 4124132720Skan * range. When the current element of one range is less than the other 4125132720Skan * according to @a comp, that element is copied and the iterator advanced. 4126132720Skan * If an equivalent element according to @a comp is contained in both 4127132720Skan * ranges, the element from the first range is copied and both ranges 4128132720Skan * advance. The output range may not overlap either input range. 4129132720Skan */ 4130132720Skan template<typename _InputIterator1, typename _InputIterator2, 4131132720Skan typename _OutputIterator, typename _Compare> 4132132720Skan _OutputIterator 4133132720Skan set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4134132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4135132720Skan _OutputIterator __result, _Compare __comp) 413697403Sobrien { 413797403Sobrien // concept requirements 4138132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4139132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4140132720Skan __glibcxx_function_requires(_SameTypeConcept< 4141132720Skan typename iterator_traits<_InputIterator1>::value_type, 4142132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4143132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4144132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4145132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4146132720Skan typename iterator_traits<_InputIterator1>::value_type, 4147132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4148132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4149132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 415097403Sobrien 4151132720Skan while (__first1 != __last1 && __first2 != __last2) 4152132720Skan { 4153132720Skan if (__comp(*__first1, *__first2)) 4154132720Skan { 4155132720Skan *__result = *__first1; 4156132720Skan ++__first1; 4157132720Skan } 4158132720Skan else if (__comp(*__first2, *__first1)) 4159132720Skan { 4160132720Skan *__result = *__first2; 4161132720Skan ++__first2; 4162132720Skan } 4163132720Skan else 4164132720Skan { 4165132720Skan *__result = *__first1; 4166132720Skan ++__first1; 4167132720Skan ++__first2; 4168132720Skan } 4169132720Skan ++__result; 417097403Sobrien } 4171132720Skan return std::copy(__first2, __last2, std::copy(__first1, __last1, 4172132720Skan __result)); 417397403Sobrien } 417497403Sobrien 4175132720Skan /** 4176132720Skan * @brief Return the intersection of two sorted ranges. 4177132720Skan * @param first1 Start of first range. 4178132720Skan * @param last1 End of first range. 4179132720Skan * @param first2 Start of second range. 4180132720Skan * @param last2 End of second range. 4181132720Skan * @return End of the output range. 4182132720Skan * @ingroup setoperations 4183132720Skan * 4184132720Skan * This operation iterates over both ranges, copying elements present in 4185132720Skan * both ranges in order to the output range. Iterators increment for each 4186132720Skan * range. When the current element of one range is less than the other, 4187132720Skan * that iterator advances. If an element is contained in both ranges, the 4188132720Skan * element from the first range is copied and both ranges advance. The 4189132720Skan * output range may not overlap either input range. 4190132720Skan */ 4191132720Skan template<typename _InputIterator1, typename _InputIterator2, 4192132720Skan typename _OutputIterator> 4193132720Skan _OutputIterator 4194132720Skan set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 4195132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4196132720Skan _OutputIterator __result) 419797403Sobrien { 419897403Sobrien // concept requirements 4199132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4200132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4201132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4202132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4203132720Skan __glibcxx_function_requires(_SameTypeConcept< 4204132720Skan typename iterator_traits<_InputIterator1>::value_type, 4205132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4206132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4207132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4208132720Skan __glibcxx_requires_sorted(__first1, __last1); 4209132720Skan __glibcxx_requires_sorted(__first2, __last2); 421097403Sobrien 421197403Sobrien while (__first1 != __last1 && __first2 != __last2) 421297403Sobrien if (*__first1 < *__first2) 421397403Sobrien ++__first1; 421497403Sobrien else if (*__first2 < *__first1) 421597403Sobrien ++__first2; 4216132720Skan else 4217132720Skan { 4218132720Skan *__result = *__first1; 4219132720Skan ++__first1; 4220132720Skan ++__first2; 4221132720Skan ++__result; 4222132720Skan } 422397403Sobrien return __result; 422497403Sobrien } 422597403Sobrien 4226132720Skan /** 4227132720Skan * @brief Return the intersection of two sorted ranges using comparison 4228132720Skan * functor. 4229132720Skan * @param first1 Start of first range. 4230132720Skan * @param last1 End of first range. 4231132720Skan * @param first2 Start of second range. 4232132720Skan * @param last2 End of second range. 4233132720Skan * @param comp The comparison functor. 4234132720Skan * @return End of the output range. 4235132720Skan * @ingroup setoperations 4236132720Skan * 4237132720Skan * This operation iterates over both ranges, copying elements present in 4238132720Skan * both ranges in order to the output range. Iterators increment for each 4239132720Skan * range. When the current element of one range is less than the other 4240132720Skan * according to @a comp, that iterator advances. If an element is 4241132720Skan * contained in both ranges according to @a comp, the element from the 4242132720Skan * first range is copied and both ranges advance. The output range may not 4243132720Skan * overlap either input range. 4244132720Skan */ 4245132720Skan template<typename _InputIterator1, typename _InputIterator2, 4246132720Skan typename _OutputIterator, typename _Compare> 4247132720Skan _OutputIterator 4248132720Skan set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 4249132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4250132720Skan _OutputIterator __result, _Compare __comp) 425197403Sobrien { 425297403Sobrien // concept requirements 4253132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4254132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4255132720Skan __glibcxx_function_requires(_SameTypeConcept< 4256132720Skan typename iterator_traits<_InputIterator1>::value_type, 4257132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4258132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4259132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4260132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4261132720Skan typename iterator_traits<_InputIterator1>::value_type, 4262132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4263132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4264132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 426597403Sobrien 426697403Sobrien while (__first1 != __last1 && __first2 != __last2) 426797403Sobrien if (__comp(*__first1, *__first2)) 426897403Sobrien ++__first1; 426997403Sobrien else if (__comp(*__first2, *__first1)) 427097403Sobrien ++__first2; 4271132720Skan else 4272132720Skan { 4273132720Skan *__result = *__first1; 4274132720Skan ++__first1; 4275132720Skan ++__first2; 4276132720Skan ++__result; 4277132720Skan } 427897403Sobrien return __result; 427997403Sobrien } 428097403Sobrien 4281132720Skan /** 4282132720Skan * @brief Return the difference of two sorted ranges. 4283132720Skan * @param first1 Start of first range. 4284132720Skan * @param last1 End of first range. 4285132720Skan * @param first2 Start of second range. 4286132720Skan * @param last2 End of second range. 4287132720Skan * @return End of the output range. 4288132720Skan * @ingroup setoperations 4289132720Skan * 4290132720Skan * This operation iterates over both ranges, copying elements present in 4291132720Skan * the first range but not the second in order to the output range. 4292132720Skan * Iterators increment for each range. When the current element of the 4293132720Skan * first range is less than the second, that element is copied and the 4294132720Skan * iterator advances. If the current element of the second range is less, 4295132720Skan * the iterator advances, but no element is copied. If an element is 4296132720Skan * contained in both ranges, no elements are copied and both ranges 4297132720Skan * advance. The output range may not overlap either input range. 4298132720Skan */ 4299132720Skan template<typename _InputIterator1, typename _InputIterator2, 4300132720Skan typename _OutputIterator> 4301132720Skan _OutputIterator 4302132720Skan set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4303132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4304132720Skan _OutputIterator __result) 430597403Sobrien { 430697403Sobrien // concept requirements 4307132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4308132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4309132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4310132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4311132720Skan __glibcxx_function_requires(_SameTypeConcept< 4312132720Skan typename iterator_traits<_InputIterator1>::value_type, 4313132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4314132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4315132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4316132720Skan __glibcxx_requires_sorted(__first1, __last1); 4317132720Skan __glibcxx_requires_sorted(__first2, __last2); 431897403Sobrien 431997403Sobrien while (__first1 != __last1 && __first2 != __last2) 4320132720Skan if (*__first1 < *__first2) 4321132720Skan { 4322132720Skan *__result = *__first1; 4323132720Skan ++__first1; 4324132720Skan ++__result; 4325132720Skan } 432697403Sobrien else if (*__first2 < *__first1) 432797403Sobrien ++__first2; 4328132720Skan else 4329132720Skan { 4330132720Skan ++__first1; 4331132720Skan ++__first2; 4332132720Skan } 4333132720Skan return std::copy(__first1, __last1, __result); 433497403Sobrien } 433597403Sobrien 4336132720Skan /** 4337132720Skan * @brief Return the difference of two sorted ranges using comparison 4338132720Skan * functor. 4339132720Skan * @param first1 Start of first range. 4340132720Skan * @param last1 End of first range. 4341132720Skan * @param first2 Start of second range. 4342132720Skan * @param last2 End of second range. 4343132720Skan * @param comp The comparison functor. 4344132720Skan * @return End of the output range. 4345132720Skan * @ingroup setoperations 4346132720Skan * 4347132720Skan * This operation iterates over both ranges, copying elements present in 4348132720Skan * the first range but not the second in order to the output range. 4349132720Skan * Iterators increment for each range. When the current element of the 4350132720Skan * first range is less than the second according to @a comp, that element 4351132720Skan * is copied and the iterator advances. If the current element of the 4352132720Skan * second range is less, no element is copied and the iterator advances. 4353132720Skan * If an element is contained in both ranges according to @a comp, no 4354132720Skan * elements are copied and both ranges advance. The output range may not 4355132720Skan * overlap either input range. 4356132720Skan */ 4357132720Skan template<typename _InputIterator1, typename _InputIterator2, 4358132720Skan typename _OutputIterator, typename _Compare> 4359132720Skan _OutputIterator 4360132720Skan set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4361132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4362132720Skan _OutputIterator __result, _Compare __comp) 436397403Sobrien { 436497403Sobrien // concept requirements 4365132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4366132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4367132720Skan __glibcxx_function_requires(_SameTypeConcept< 4368132720Skan typename iterator_traits<_InputIterator1>::value_type, 4369132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4370132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4371132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4372132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4373132720Skan typename iterator_traits<_InputIterator1>::value_type, 4374132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4375132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4376132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 437797403Sobrien 437897403Sobrien while (__first1 != __last1 && __first2 != __last2) 4379132720Skan if (__comp(*__first1, *__first2)) 4380132720Skan { 4381132720Skan *__result = *__first1; 4382132720Skan ++__first1; 4383132720Skan ++__result; 4384132720Skan } 438597403Sobrien else if (__comp(*__first2, *__first1)) 438697403Sobrien ++__first2; 4387132720Skan else 4388132720Skan { 4389132720Skan ++__first1; 4390132720Skan ++__first2; 4391132720Skan } 4392132720Skan return std::copy(__first1, __last1, __result); 439397403Sobrien } 439497403Sobrien 4395132720Skan /** 4396132720Skan * @brief Return the symmetric difference of two sorted ranges. 4397132720Skan * @param first1 Start of first range. 4398132720Skan * @param last1 End of first range. 4399132720Skan * @param first2 Start of second range. 4400132720Skan * @param last2 End of second range. 4401132720Skan * @return End of the output range. 4402132720Skan * @ingroup setoperations 4403132720Skan * 4404132720Skan * This operation iterates over both ranges, copying elements present in 4405132720Skan * one range but not the other in order to the output range. Iterators 4406132720Skan * increment for each range. When the current element of one range is less 4407132720Skan * than the other, that element is copied and the iterator advances. If an 4408132720Skan * element is contained in both ranges, no elements are copied and both 4409132720Skan * ranges advance. The output range may not overlap either input range. 4410132720Skan */ 4411132720Skan template<typename _InputIterator1, typename _InputIterator2, 4412132720Skan typename _OutputIterator> 4413132720Skan _OutputIterator 4414132720Skan set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4415132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4416132720Skan _OutputIterator __result) 441797403Sobrien { 441897403Sobrien // concept requirements 4419132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4420132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4421132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4422132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4423132720Skan __glibcxx_function_requires(_SameTypeConcept< 4424132720Skan typename iterator_traits<_InputIterator1>::value_type, 4425132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4426132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4427132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4428132720Skan __glibcxx_requires_sorted(__first1, __last1); 4429132720Skan __glibcxx_requires_sorted(__first2, __last2); 443097403Sobrien 443197403Sobrien while (__first1 != __last1 && __first2 != __last2) 4432132720Skan if (*__first1 < *__first2) 4433132720Skan { 4434132720Skan *__result = *__first1; 4435132720Skan ++__first1; 4436132720Skan ++__result; 4437132720Skan } 4438132720Skan else if (*__first2 < *__first1) 4439132720Skan { 4440132720Skan *__result = *__first2; 4441132720Skan ++__first2; 4442132720Skan ++__result; 4443132720Skan } 4444132720Skan else 4445132720Skan { 4446132720Skan ++__first1; 4447132720Skan ++__first2; 4448132720Skan } 4449132720Skan return std::copy(__first2, __last2, std::copy(__first1, 4450132720Skan __last1, __result)); 445197403Sobrien } 445297403Sobrien 4453132720Skan /** 4454132720Skan * @brief Return the symmetric difference of two sorted ranges using 4455132720Skan * comparison functor. 4456132720Skan * @param first1 Start of first range. 4457132720Skan * @param last1 End of first range. 4458132720Skan * @param first2 Start of second range. 4459132720Skan * @param last2 End of second range. 4460132720Skan * @param comp The comparison functor. 4461132720Skan * @return End of the output range. 4462132720Skan * @ingroup setoperations 4463132720Skan * 4464132720Skan * This operation iterates over both ranges, copying elements present in 4465132720Skan * one range but not the other in order to the output range. Iterators 4466132720Skan * increment for each range. When the current element of one range is less 4467132720Skan * than the other according to @a comp, that element is copied and the 4468132720Skan * iterator advances. If an element is contained in both ranges according 4469132720Skan * to @a comp, no elements are copied and both ranges advance. The output 4470132720Skan * range may not overlap either input range. 4471132720Skan */ 4472132720Skan template<typename _InputIterator1, typename _InputIterator2, 4473132720Skan typename _OutputIterator, typename _Compare> 4474132720Skan _OutputIterator 4475132720Skan set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 4476132720Skan _InputIterator2 __first2, _InputIterator2 __last2, 4477132720Skan _OutputIterator __result, 447897403Sobrien _Compare __comp) 447997403Sobrien { 448097403Sobrien // concept requirements 4481132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4482132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4483132720Skan __glibcxx_function_requires(_SameTypeConcept< 4484132720Skan typename iterator_traits<_InputIterator1>::value_type, 4485132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4486132720Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4487132720Skan typename iterator_traits<_InputIterator1>::value_type>) 4488132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4489132720Skan typename iterator_traits<_InputIterator1>::value_type, 4490132720Skan typename iterator_traits<_InputIterator2>::value_type>) 4491132720Skan __glibcxx_requires_sorted_pred(__first1, __last1, __comp); 4492132720Skan __glibcxx_requires_sorted_pred(__first2, __last2, __comp); 449397403Sobrien 449497403Sobrien while (__first1 != __last1 && __first2 != __last2) 4495132720Skan if (__comp(*__first1, *__first2)) 4496132720Skan { 4497132720Skan *__result = *__first1; 4498132720Skan ++__first1; 4499132720Skan ++__result; 4500132720Skan } 4501132720Skan else if (__comp(*__first2, *__first1)) 4502132720Skan { 4503132720Skan *__result = *__first2; 4504132720Skan ++__first2; 4505132720Skan ++__result; 4506132720Skan } 4507132720Skan else 4508132720Skan { 4509132720Skan ++__first1; 4510132720Skan ++__first2; 4511132720Skan } 4512132720Skan return std::copy(__first2, __last2, std::copy(__first1, 4513132720Skan __last1, __result)); 451497403Sobrien } 451597403Sobrien 451697403Sobrien // min_element and max_element, with and without an explicitly supplied 451797403Sobrien // comparison function. 451897403Sobrien 4519132720Skan /** 4520132720Skan * @brief Return the maximum element in a range. 4521132720Skan * @param first Start of range. 4522132720Skan * @param last End of range. 4523132720Skan * @return Iterator referencing the first instance of the largest value. 4524132720Skan */ 4525132720Skan template<typename _ForwardIterator> 4526132720Skan _ForwardIterator 4527132720Skan max_element(_ForwardIterator __first, _ForwardIterator __last) 452897403Sobrien { 452997403Sobrien // concept requirements 4530132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4531132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4532132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4533132720Skan __glibcxx_requires_valid_range(__first, __last); 453497403Sobrien 4535132720Skan if (__first == __last) 4536132720Skan return __first; 4537132720Skan _ForwardIterator __result = __first; 453897403Sobrien while (++__first != __last) 453997403Sobrien if (*__result < *__first) 454097403Sobrien __result = __first; 454197403Sobrien return __result; 454297403Sobrien } 454397403Sobrien 4544132720Skan /** 4545132720Skan * @brief Return the maximum element in a range using comparison functor. 4546132720Skan * @param first Start of range. 4547132720Skan * @param last End of range. 4548132720Skan * @param comp Comparison functor. 4549132720Skan * @return Iterator referencing the first instance of the largest value 4550132720Skan * according to comp. 4551132720Skan */ 4552132720Skan template<typename _ForwardIterator, typename _Compare> 4553132720Skan _ForwardIterator 4554132720Skan max_element(_ForwardIterator __first, _ForwardIterator __last, 455597403Sobrien _Compare __comp) 455697403Sobrien { 455797403Sobrien // concept requirements 4558132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4559132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4560132720Skan typename iterator_traits<_ForwardIterator>::value_type, 4561132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4562132720Skan __glibcxx_requires_valid_range(__first, __last); 456397403Sobrien 456497403Sobrien if (__first == __last) return __first; 4565132720Skan _ForwardIterator __result = __first; 456697403Sobrien while (++__first != __last) 456797403Sobrien if (__comp(*__result, *__first)) __result = __first; 456897403Sobrien return __result; 456997403Sobrien } 457097403Sobrien 4571132720Skan /** 4572132720Skan * @brief Return the minimum element in a range. 4573132720Skan * @param first Start of range. 4574132720Skan * @param last End of range. 4575132720Skan * @return Iterator referencing the first instance of the smallest value. 4576132720Skan */ 4577132720Skan template<typename _ForwardIterator> 4578132720Skan _ForwardIterator 4579132720Skan min_element(_ForwardIterator __first, _ForwardIterator __last) 458097403Sobrien { 458197403Sobrien // concept requirements 4582132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4583132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4584132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4585132720Skan __glibcxx_requires_valid_range(__first, __last); 458697403Sobrien 4587132720Skan if (__first == __last) 4588132720Skan return __first; 4589132720Skan _ForwardIterator __result = __first; 459097403Sobrien while (++__first != __last) 459197403Sobrien if (*__first < *__result) 459297403Sobrien __result = __first; 459397403Sobrien return __result; 459497403Sobrien } 459597403Sobrien 4596132720Skan /** 4597132720Skan * @brief Return the minimum element in a range using comparison functor. 4598132720Skan * @param first Start of range. 4599132720Skan * @param last End of range. 4600132720Skan * @param comp Comparison functor. 4601132720Skan * @return Iterator referencing the first instance of the smallest value 4602132720Skan * according to comp. 4603132720Skan */ 4604132720Skan template<typename _ForwardIterator, typename _Compare> 4605132720Skan _ForwardIterator 4606132720Skan min_element(_ForwardIterator __first, _ForwardIterator __last, 460797403Sobrien _Compare __comp) 460897403Sobrien { 460997403Sobrien // concept requirements 4610132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4611132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4612132720Skan typename iterator_traits<_ForwardIterator>::value_type, 4613132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4614132720Skan __glibcxx_requires_valid_range(__first, __last); 461597403Sobrien 4616132720Skan if (__first == __last) 4617132720Skan return __first; 4618132720Skan _ForwardIterator __result = __first; 461997403Sobrien while (++__first != __last) 462097403Sobrien if (__comp(*__first, *__result)) 462197403Sobrien __result = __first; 462297403Sobrien return __result; 462397403Sobrien } 462497403Sobrien 462597403Sobrien // next_permutation and prev_permutation, with and without an explicitly 462697403Sobrien // supplied comparison function. 462797403Sobrien 4628132720Skan /** 4629132720Skan * @brief Permute range into the next "dictionary" ordering. 4630132720Skan * @param first Start of range. 4631132720Skan * @param last End of range. 4632132720Skan * @return False if wrapped to first permutation, true otherwise. 4633132720Skan * 4634132720Skan * Treats all permutations of the range as a set of "dictionary" sorted 4635132720Skan * sequences. Permutes the current sequence into the next one of this set. 4636132720Skan * Returns true if there are more sequences to generate. If the sequence 4637132720Skan * is the largest of the set, the smallest is generated and false returned. 4638132720Skan */ 4639132720Skan template<typename _BidirectionalIterator> 464097403Sobrien bool 4641132720Skan next_permutation(_BidirectionalIterator __first, 4642132720Skan _BidirectionalIterator __last) 464397403Sobrien { 464497403Sobrien // concept requirements 4645132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 4646132720Skan _BidirectionalIterator>) 4647132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4648132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 4649132720Skan __glibcxx_requires_valid_range(__first, __last); 465097403Sobrien 465197403Sobrien if (__first == __last) 465297403Sobrien return false; 4653132720Skan _BidirectionalIterator __i = __first; 465497403Sobrien ++__i; 465597403Sobrien if (__i == __last) 465697403Sobrien return false; 465797403Sobrien __i = __last; 465897403Sobrien --__i; 465997403Sobrien 4660132720Skan for(;;) 4661132720Skan { 4662132720Skan _BidirectionalIterator __ii = __i; 4663132720Skan --__i; 4664132720Skan if (*__i < *__ii) 4665132720Skan { 4666132720Skan _BidirectionalIterator __j = __last; 4667132720Skan while (!(*__i < *--__j)) 4668132720Skan {} 4669132720Skan std::iter_swap(__i, __j); 4670132720Skan std::reverse(__ii, __last); 4671132720Skan return true; 4672132720Skan } 4673132720Skan if (__i == __first) 4674132720Skan { 4675132720Skan std::reverse(__first, __last); 4676132720Skan return false; 4677132720Skan } 467897403Sobrien } 467997403Sobrien } 468097403Sobrien 4681132720Skan /** 4682132720Skan * @brief Permute range into the next "dictionary" ordering using 4683132720Skan * comparison functor. 4684132720Skan * @param first Start of range. 4685132720Skan * @param last End of range. 4686132720Skan * @param comp 4687132720Skan * @return False if wrapped to first permutation, true otherwise. 4688132720Skan * 4689132720Skan * Treats all permutations of the range [first,last) as a set of 4690132720Skan * "dictionary" sorted sequences ordered by @a comp. Permutes the current 4691132720Skan * sequence into the next one of this set. Returns true if there are more 4692132720Skan * sequences to generate. If the sequence is the largest of the set, the 4693132720Skan * smallest is generated and false returned. 4694132720Skan */ 4695132720Skan template<typename _BidirectionalIterator, typename _Compare> 469697403Sobrien bool 4697132720Skan next_permutation(_BidirectionalIterator __first, 4698132720Skan _BidirectionalIterator __last, _Compare __comp) 469997403Sobrien { 470097403Sobrien // concept requirements 4701132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 4702132720Skan _BidirectionalIterator>) 4703132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4704132720Skan typename iterator_traits<_BidirectionalIterator>::value_type, 4705132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 4706132720Skan __glibcxx_requires_valid_range(__first, __last); 470797403Sobrien 470897403Sobrien if (__first == __last) 470997403Sobrien return false; 4710132720Skan _BidirectionalIterator __i = __first; 471197403Sobrien ++__i; 471297403Sobrien if (__i == __last) 471397403Sobrien return false; 471497403Sobrien __i = __last; 471597403Sobrien --__i; 471697403Sobrien 4717132720Skan for(;;) 4718132720Skan { 4719132720Skan _BidirectionalIterator __ii = __i; 4720132720Skan --__i; 4721132720Skan if (__comp(*__i, *__ii)) 4722132720Skan { 4723132720Skan _BidirectionalIterator __j = __last; 4724132720Skan while (!__comp(*__i, *--__j)) 4725132720Skan {} 4726132720Skan std::iter_swap(__i, __j); 4727132720Skan std::reverse(__ii, __last); 4728132720Skan return true; 4729132720Skan } 4730132720Skan if (__i == __first) 4731132720Skan { 4732132720Skan std::reverse(__first, __last); 4733132720Skan return false; 4734132720Skan } 473597403Sobrien } 473697403Sobrien } 473797403Sobrien 4738132720Skan /** 4739132720Skan * @brief Permute range into the previous "dictionary" ordering. 4740132720Skan * @param first Start of range. 4741132720Skan * @param last End of range. 4742132720Skan * @return False if wrapped to last permutation, true otherwise. 4743132720Skan * 4744132720Skan * Treats all permutations of the range as a set of "dictionary" sorted 4745132720Skan * sequences. Permutes the current sequence into the previous one of this 4746132720Skan * set. Returns true if there are more sequences to generate. If the 4747132720Skan * sequence is the smallest of the set, the largest is generated and false 4748132720Skan * returned. 4749132720Skan */ 4750132720Skan template<typename _BidirectionalIterator> 475197403Sobrien bool 4752132720Skan prev_permutation(_BidirectionalIterator __first, 4753132720Skan _BidirectionalIterator __last) 475497403Sobrien { 475597403Sobrien // concept requirements 4756132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 4757132720Skan _BidirectionalIterator>) 4758132720Skan __glibcxx_function_requires(_LessThanComparableConcept< 4759132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 4760132720Skan __glibcxx_requires_valid_range(__first, __last); 476197403Sobrien 476297403Sobrien if (__first == __last) 476397403Sobrien return false; 4764132720Skan _BidirectionalIterator __i = __first; 476597403Sobrien ++__i; 476697403Sobrien if (__i == __last) 476797403Sobrien return false; 476897403Sobrien __i = __last; 476997403Sobrien --__i; 477097403Sobrien 4771132720Skan for(;;) 4772132720Skan { 4773132720Skan _BidirectionalIterator __ii = __i; 4774132720Skan --__i; 4775132720Skan if (*__ii < *__i) 4776132720Skan { 4777132720Skan _BidirectionalIterator __j = __last; 4778132720Skan while (!(*--__j < *__i)) 4779132720Skan {} 4780132720Skan std::iter_swap(__i, __j); 4781132720Skan std::reverse(__ii, __last); 4782132720Skan return true; 4783132720Skan } 4784132720Skan if (__i == __first) 4785132720Skan { 4786132720Skan std::reverse(__first, __last); 4787132720Skan return false; 4788132720Skan } 478997403Sobrien } 479097403Sobrien } 479197403Sobrien 4792132720Skan /** 4793132720Skan * @brief Permute range into the previous "dictionary" ordering using 4794132720Skan * comparison functor. 4795132720Skan * @param first Start of range. 4796132720Skan * @param last End of range. 4797132720Skan * @param comp 4798132720Skan * @return False if wrapped to last permutation, true otherwise. 4799132720Skan * 4800132720Skan * Treats all permutations of the range [first,last) as a set of 4801132720Skan * "dictionary" sorted sequences ordered by @a comp. Permutes the current 4802132720Skan * sequence into the previous one of this set. Returns true if there are 4803132720Skan * more sequences to generate. If the sequence is the smallest of the set, 4804132720Skan * the largest is generated and false returned. 4805132720Skan */ 4806132720Skan template<typename _BidirectionalIterator, typename _Compare> 480797403Sobrien bool 4808132720Skan prev_permutation(_BidirectionalIterator __first, 4809132720Skan _BidirectionalIterator __last, _Compare __comp) 481097403Sobrien { 481197403Sobrien // concept requirements 4812132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 4813132720Skan _BidirectionalIterator>) 4814132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4815132720Skan typename iterator_traits<_BidirectionalIterator>::value_type, 4816132720Skan typename iterator_traits<_BidirectionalIterator>::value_type>) 4817132720Skan __glibcxx_requires_valid_range(__first, __last); 481897403Sobrien 481997403Sobrien if (__first == __last) 482097403Sobrien return false; 4821132720Skan _BidirectionalIterator __i = __first; 482297403Sobrien ++__i; 482397403Sobrien if (__i == __last) 482497403Sobrien return false; 482597403Sobrien __i = __last; 482697403Sobrien --__i; 482797403Sobrien 4828132720Skan for(;;) 4829132720Skan { 4830132720Skan _BidirectionalIterator __ii = __i; 4831132720Skan --__i; 4832132720Skan if (__comp(*__ii, *__i)) 4833132720Skan { 4834132720Skan _BidirectionalIterator __j = __last; 4835132720Skan while (!__comp(*--__j, *__i)) 4836132720Skan {} 4837132720Skan std::iter_swap(__i, __j); 4838132720Skan std::reverse(__ii, __last); 4839132720Skan return true; 4840132720Skan } 4841132720Skan if (__i == __first) 4842132720Skan { 4843132720Skan std::reverse(__first, __last); 4844132720Skan return false; 4845132720Skan } 484697403Sobrien } 484797403Sobrien } 484897403Sobrien 484997403Sobrien // find_first_of, with and without an explicitly supplied comparison function. 485097403Sobrien 4851132720Skan /** 4852132720Skan * @brief Find element from a set in a sequence. 4853132720Skan * @param first1 Start of range to search. 4854132720Skan * @param last1 End of range to search. 4855132720Skan * @param first2 Start of match candidates. 4856132720Skan * @param last2 End of match candidates. 4857132720Skan * @return The first iterator @c i in the range 4858132720Skan * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an 4859132720Skan * interator in [first2,last2), or @p last1 if no such iterator exists. 4860132720Skan * 4861132720Skan * Searches the range @p [first1,last1) for an element that is equal to 4862132720Skan * some element in the range [first2,last2). If found, returns an iterator 4863132720Skan * in the range [first1,last1), otherwise returns @p last1. 4864132720Skan */ 4865132720Skan template<typename _InputIterator, typename _ForwardIterator> 4866132720Skan _InputIterator 4867132720Skan find_first_of(_InputIterator __first1, _InputIterator __last1, 4868132720Skan _ForwardIterator __first2, _ForwardIterator __last2) 486997403Sobrien { 487097403Sobrien // concept requirements 4871132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4872132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4873132720Skan __glibcxx_function_requires(_EqualOpConcept< 4874132720Skan typename iterator_traits<_InputIterator>::value_type, 4875132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4876132720Skan __glibcxx_requires_valid_range(__first1, __last1); 4877132720Skan __glibcxx_requires_valid_range(__first2, __last2); 487897403Sobrien 487997403Sobrien for ( ; __first1 != __last1; ++__first1) 4880132720Skan for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 488197403Sobrien if (*__first1 == *__iter) 488297403Sobrien return __first1; 488397403Sobrien return __last1; 488497403Sobrien } 488597403Sobrien 4886132720Skan /** 4887132720Skan * @brief Find element from a set in a sequence using a predicate. 4888132720Skan * @param first1 Start of range to search. 4889132720Skan * @param last1 End of range to search. 4890132720Skan * @param first2 Start of match candidates. 4891132720Skan * @param last2 End of match candidates. 4892132720Skan * @param comp Predicate to use. 4893132720Skan * @return The first iterator @c i in the range 4894132720Skan * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an 4895132720Skan * interator in [first2,last2), or @p last1 if no such iterator exists. 4896132720Skan * 4897132720Skan * Searches the range @p [first1,last1) for an element that is equal to 4898132720Skan * some element in the range [first2,last2). If found, returns an iterator in 4899132720Skan * the range [first1,last1), otherwise returns @p last1. 4900132720Skan */ 4901132720Skan template<typename _InputIterator, typename _ForwardIterator, 4902132720Skan typename _BinaryPredicate> 4903132720Skan _InputIterator 4904132720Skan find_first_of(_InputIterator __first1, _InputIterator __last1, 4905132720Skan _ForwardIterator __first2, _ForwardIterator __last2, 490697403Sobrien _BinaryPredicate __comp) 490797403Sobrien { 490897403Sobrien // concept requirements 4909132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4910132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4911132720Skan __glibcxx_function_requires(_EqualOpConcept< 4912132720Skan typename iterator_traits<_InputIterator>::value_type, 4913132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4914132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4915132720Skan typename iterator_traits<_InputIterator>::value_type, 4916132720Skan typename iterator_traits<_ForwardIterator>::value_type>) 4917132720Skan __glibcxx_requires_valid_range(__first1, __last1); 4918132720Skan __glibcxx_requires_valid_range(__first2, __last2); 491997403Sobrien 492097403Sobrien for ( ; __first1 != __last1; ++__first1) 4921132720Skan for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 492297403Sobrien if (__comp(*__first1, *__iter)) 492397403Sobrien return __first1; 492497403Sobrien return __last1; 492597403Sobrien } 492697403Sobrien 492797403Sobrien 492897403Sobrien // find_end, with and without an explicitly supplied comparison function. 492997403Sobrien // Search [first2, last2) as a subsequence in [first1, last1), and return 493097403Sobrien // the *last* possible match. Note that find_end for bidirectional iterators 493197403Sobrien // is much faster than for forward iterators. 493297403Sobrien 493397403Sobrien // find_end for forward iterators. 4934132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 4935132720Skan _ForwardIterator1 4936132720Skan __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4937132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 493897403Sobrien forward_iterator_tag, forward_iterator_tag) 493997403Sobrien { 494097403Sobrien if (__first2 == __last2) 494197403Sobrien return __last1; 4942132720Skan else 4943132720Skan { 4944132720Skan _ForwardIterator1 __result = __last1; 4945132720Skan while (1) 4946132720Skan { 4947132720Skan _ForwardIterator1 __new_result 4948132720Skan = std::search(__first1, __last1, __first2, __last2); 4949132720Skan if (__new_result == __last1) 4950132720Skan return __result; 4951132720Skan else 4952132720Skan { 4953132720Skan __result = __new_result; 4954132720Skan __first1 = __new_result; 4955132720Skan ++__first1; 4956132720Skan } 4957132720Skan } 495897403Sobrien } 495997403Sobrien } 496097403Sobrien 4961132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2, 496297403Sobrien typename _BinaryPredicate> 4963132720Skan _ForwardIterator1 4964132720Skan __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4965132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 496697403Sobrien forward_iterator_tag, forward_iterator_tag, 496797403Sobrien _BinaryPredicate __comp) 496897403Sobrien { 496997403Sobrien if (__first2 == __last2) 497097403Sobrien return __last1; 4971132720Skan else 4972132720Skan { 4973132720Skan _ForwardIterator1 __result = __last1; 4974132720Skan while (1) 4975132720Skan { 4976132720Skan _ForwardIterator1 __new_result 4977132720Skan = std::search(__first1, __last1, __first2, __last2, __comp); 4978132720Skan if (__new_result == __last1) 4979132720Skan return __result; 4980132720Skan else 4981132720Skan { 4982132720Skan __result = __new_result; 4983132720Skan __first1 = __new_result; 4984132720Skan ++__first1; 4985132720Skan } 4986132720Skan } 498797403Sobrien } 498897403Sobrien } 498997403Sobrien 499097403Sobrien // find_end for bidirectional iterators. Requires partial specialization. 4991132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> 4992132720Skan _BidirectionalIterator1 4993132720Skan __find_end(_BidirectionalIterator1 __first1, 4994132720Skan _BidirectionalIterator1 __last1, 4995132720Skan _BidirectionalIterator2 __first2, 4996132720Skan _BidirectionalIterator2 __last2, 499797403Sobrien bidirectional_iterator_tag, bidirectional_iterator_tag) 499897403Sobrien { 499997403Sobrien // concept requirements 5000132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5001132720Skan _BidirectionalIterator1>) 5002132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5003132720Skan _BidirectionalIterator2>) 500497403Sobrien 5005132720Skan typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 5006132720Skan typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 500797403Sobrien 5008132720Skan _RevIterator1 __rlast1(__first1); 5009132720Skan _RevIterator2 __rlast2(__first2); 5010132720Skan _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, 5011132720Skan _RevIterator2(__last2), __rlast2); 501297403Sobrien 501397403Sobrien if (__rresult == __rlast1) 501497403Sobrien return __last1; 5015132720Skan else 5016132720Skan { 5017132720Skan _BidirectionalIterator1 __result = __rresult.base(); 5018132720Skan std::advance(__result, -std::distance(__first2, __last2)); 5019132720Skan return __result; 5020132720Skan } 502197403Sobrien } 502297403Sobrien 5023132720Skan template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 502497403Sobrien typename _BinaryPredicate> 5025132720Skan _BidirectionalIterator1 5026132720Skan __find_end(_BidirectionalIterator1 __first1, 5027132720Skan _BidirectionalIterator1 __last1, 5028132720Skan _BidirectionalIterator2 __first2, 5029132720Skan _BidirectionalIterator2 __last2, 503097403Sobrien bidirectional_iterator_tag, bidirectional_iterator_tag, 503197403Sobrien _BinaryPredicate __comp) 503297403Sobrien { 503397403Sobrien // concept requirements 5034132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5035132720Skan _BidirectionalIterator1>) 5036132720Skan __glibcxx_function_requires(_BidirectionalIteratorConcept< 5037132720Skan _BidirectionalIterator2>) 503897403Sobrien 5039132720Skan typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 5040132720Skan typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 504197403Sobrien 5042132720Skan _RevIterator1 __rlast1(__first1); 5043132720Skan _RevIterator2 __rlast2(__first2); 5044132720Skan _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1, 5045132720Skan _RevIterator2(__last2), __rlast2, 5046132720Skan __comp); 504797403Sobrien 504897403Sobrien if (__rresult == __rlast1) 504997403Sobrien return __last1; 5050132720Skan else 5051132720Skan { 5052132720Skan _BidirectionalIterator1 __result = __rresult.base(); 5053132720Skan std::advance(__result, -std::distance(__first2, __last2)); 5054132720Skan return __result; 5055132720Skan } 505697403Sobrien } 505797403Sobrien 505897403Sobrien // Dispatching functions for find_end. 505997403Sobrien 5060132720Skan /** 5061132720Skan * @brief Find last matching subsequence in a sequence. 5062132720Skan * @param first1 Start of range to search. 5063132720Skan * @param last1 End of range to search. 5064132720Skan * @param first2 Start of sequence to match. 5065132720Skan * @param last2 End of sequence to match. 5066132720Skan * @return The last iterator @c i in the range 5067132720Skan * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 5068132720Skan * for each @c N in the range @p [0,last2-first2), or @p last1 if no 5069132720Skan * such iterator exists. 5070132720Skan * 5071132720Skan * Searches the range @p [first1,last1) for a sub-sequence that compares 5072132720Skan * equal value-by-value with the sequence given by @p [first2,last2) and 5073132720Skan * returns an iterator to the first element of the sub-sequence, or 5074132720Skan * @p last1 if the sub-sequence is not found. The sub-sequence will be the 5075132720Skan * last such subsequence contained in [first,last1). 5076132720Skan * 5077132720Skan * Because the sub-sequence must lie completely within the range 5078132720Skan * @p [first1,last1) it must start at a position less than 5079132720Skan * @p last1-(last2-first2) where @p last2-first2 is the length of the 5080132720Skan * sub-sequence. 5081132720Skan * This means that the returned iterator @c i will be in the range 5082132720Skan * @p [first1,last1-(last2-first2)) 5083132720Skan */ 5084132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2> 5085132720Skan inline _ForwardIterator1 5086132720Skan find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 5087132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2) 508897403Sobrien { 508997403Sobrien // concept requirements 5090132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 5091132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 5092132720Skan __glibcxx_function_requires(_EqualOpConcept< 5093132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 5094132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 5095132720Skan __glibcxx_requires_valid_range(__first1, __last1); 5096132720Skan __glibcxx_requires_valid_range(__first2, __last2); 509797403Sobrien 5098132720Skan return std::__find_end(__first1, __last1, __first2, __last2, 5099132720Skan std::__iterator_category(__first1), 5100132720Skan std::__iterator_category(__first2)); 510197403Sobrien } 510297403Sobrien 5103132720Skan /** 5104132720Skan * @brief Find last matching subsequence in a sequence using a predicate. 5105132720Skan * @param first1 Start of range to search. 5106132720Skan * @param last1 End of range to search. 5107132720Skan * @param first2 Start of sequence to match. 5108132720Skan * @param last2 End of sequence to match. 5109132720Skan * @param comp The predicate to use. 5110132720Skan * @return The last iterator @c i in the range 5111132720Skan * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p 5112132720Skan * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or 5113132720Skan * @p last1 if no such iterator exists. 5114132720Skan * 5115132720Skan * Searches the range @p [first1,last1) for a sub-sequence that compares 5116132720Skan * equal value-by-value with the sequence given by @p [first2,last2) using 5117132720Skan * comp as a predicate and returns an iterator to the first element of the 5118132720Skan * sub-sequence, or @p last1 if the sub-sequence is not found. The 5119132720Skan * sub-sequence will be the last such subsequence contained in 5120132720Skan * [first,last1). 5121132720Skan * 5122132720Skan * Because the sub-sequence must lie completely within the range 5123132720Skan * @p [first1,last1) it must start at a position less than 5124132720Skan * @p last1-(last2-first2) where @p last2-first2 is the length of the 5125132720Skan * sub-sequence. 5126132720Skan * This means that the returned iterator @c i will be in the range 5127132720Skan * @p [first1,last1-(last2-first2)) 5128132720Skan */ 5129132720Skan template<typename _ForwardIterator1, typename _ForwardIterator2, 513097403Sobrien typename _BinaryPredicate> 5131132720Skan inline _ForwardIterator1 5132132720Skan find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 5133132720Skan _ForwardIterator2 __first2, _ForwardIterator2 __last2, 513497403Sobrien _BinaryPredicate __comp) 513597403Sobrien { 513697403Sobrien // concept requirements 5137132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 5138132720Skan __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 5139132720Skan __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 5140132720Skan typename iterator_traits<_ForwardIterator1>::value_type, 5141132720Skan typename iterator_traits<_ForwardIterator2>::value_type>) 5142132720Skan __glibcxx_requires_valid_range(__first1, __last1); 5143132720Skan __glibcxx_requires_valid_range(__first2, __last2); 514497403Sobrien 5145132720Skan return std::__find_end(__first1, __last1, __first2, __last2, 5146132720Skan std::__iterator_category(__first1), 5147132720Skan std::__iterator_category(__first2), 5148132720Skan __comp); 514997403Sobrien } 515097403Sobrien 515197403Sobrien} // namespace std 515297403Sobrien 5153132720Skan#endif /* _ALGO_H */ 5154