19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1994 49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hewlett-Packard Company 59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997 79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc. 89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997 109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology 119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999 139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev 149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed 169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk. 179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted 199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies. 209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted, 219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was 229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice. 239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* NOTE: This is an internal header file, included by other STL headers. 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * You should not attempt to use it directly. 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGO_H 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_INTERNAL_ALGO_H 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGOBASE_H 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_algobase.h> 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_HEAP_H 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_heap.h> 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ITERATOR_H 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_iterator.h> 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_FUNCTION_BASE_H 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_function_base.h> 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (__SUNPRO_CC) && !defined (_STLP_INTERNAL_CSTDIO) 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// remove() conflict 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_cstdio.h> 529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// for_each. Apply a function to every element of a range. 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Function> 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _Function 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockfor_each(_InputIter __first, _InputIter __last, _Function __f) { 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __f(*__first); 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __f; 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// count_if 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Predicate> 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter) 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockcount_if(_InputIter __first, _InputIter __last, _Predicate __pred) { 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0; 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) { 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__n; 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __n; 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// adjacent_find. 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _BinaryPredicate> 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockadjacent_find(_ForwardIter __first, _ForwardIter __last, 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred) { 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __next = __first; 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while(++__next != __last) { 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__binary_pred(*__first, *__next)) 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = __next; 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockadjacent_find(_ForwardIter __first, _ForwardIter __last) { 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return adjacent_find(__first, __last, 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _ForwardIter))); 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_NO_ANACHRONISMS) 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Tp, class _Size> 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockcount(_InputIter __first, _InputIter __last, const _Tp& __val, _Size& __n) { 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__n; 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Predicate, class _Size> 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockcount_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) { 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__n; 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2> 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2); 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// search_n. Search for __count consecutive copies of __val. 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Integer, class _Tp> 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __count, const _Tp& __val); 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __count, const _Tp& __val, _BinaryPred __binary_pred); 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _ForwardIter> 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _InputIter find_first_of(_InputIter __first1, _InputIter __last1, 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __first2, _ForwardIter __last2) { 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 140e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2); 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _ForwardIter, class _BinaryPredicate> 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _InputIter 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockfind_first_of(_InputIter __first1, _InputIter __last1, 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) { 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2, __comp); 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2> 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockfind_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2); 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// swap_ranges 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2> 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter2 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockswap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2) { 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first1 != __last1; ++__first1, ++__first2) 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__first1, __first2); 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first2; 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// transform 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _UnaryOperation> 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIter 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktransform(_InputIter __first, _InputIter __last, _OutputIter __result, _UnaryOperation __opr) { 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first, ++__result) 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = __opr(*__first); 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation> 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIter 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktransform(_InputIter1 __first1, _InputIter1 __last1, 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _OutputIter __result,_BinaryOperation __binary_op) { 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = __binary_op(*__first1, *__first2); 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// replace_if, replace_copy, replace_copy_if 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate, class _Tp> 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockreplace_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const _Tp& __new_value) { 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__first = __new_value; 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _Tp> 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIter 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockreplace_copy(_InputIter __first, _InputIter __last,_OutputIter __result, 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __old_value, const _Tp& __new_value) { 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first, ++__result) 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first == __old_value ? __new_value : *__first; 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Iterator, class _OutputIter, class _Predicate, class _Tp> 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIter 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockreplace_copy_if(_Iterator __first, _Iterator __last, 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, const _Tp& __new_value) { 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first, ++__result) 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = __pred(*__first) ? __new_value : *__first; 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// generate and generate_n 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Generator> 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockgenerate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) { 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__first = __gen(); 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _OutputIter, class _Size, class _Generator> 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockgenerate_n(_OutputIter __first, _Size __n, _Generator __gen) { 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__first) 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__first = __gen(); 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// remove, remove_if, remove_copy, remove_copy_if 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _Tp> 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIter 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockremove_copy(_InputIter __first, _InputIter __last,_OutputIter __result, const _Tp& __val) { 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) { 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!(*__first == __val)) { 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first; 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _Predicate> 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIter 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockremove_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, _Predicate __pred) { 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last; ++__first) { 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!__pred(*__first)) { 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first; 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp> 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockremove(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = find(__first, __last, __val); 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __next = __first; 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return remove_copy(++__next, __last, __first, __val); 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockremove_if(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = find_if(__first, __last, __pred); 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( __first == __last ) 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __next = __first; 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return remove_copy_if(++__next, __last, __first, __pred); 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// unique and unique_copy 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter> 2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result); 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _BinaryPredicate> 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred); 2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = adjacent_find(__first, __last); 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return unique_copy(__first, __last, __first); 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _BinaryPredicate> 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter unique(_ForwardIter __first, _ForwardIter __last, 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred) { 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = adjacent_find(__first, __last, __binary_pred); 3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return unique_copy(__first, __last, __first, __binary_pred); 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// reverse and reverse_copy, and their auxiliary functions 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 312e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_MOVE_TO_PRIV_NAMESPACE 313e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__reverse(_BidirectionalIter __first, _BidirectionalIter __last, const bidirectional_iterator_tag &) { 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __first != __last && __first != --__last; ++__first) 318e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::iter_swap(__first,__last); 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP void 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__reverse(_RandomAccessIter __first, _RandomAccessIter __last, const random_access_iterator_tag &) { 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __first < __last; ++__first) 325e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::iter_swap(__first, --__last); 3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 328e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_MOVE_TO_STD_NAMESPACE 329e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void 3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockreverse(_BidirectionalIter __first, _BidirectionalIter __last) { 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 334e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __reverse(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _BidirectionalIter)); 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _OutputIter> 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP 3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter reverse_copy(_BidirectionalIter __first, 3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result) { 3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) { 3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last; 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__last; 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last); 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _OutputIter> 3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle, 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __last, _OutputIter __result) { 357e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__first, __middle, copy(__middle, __last, __result)); 3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// random_shuffle 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last); 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _RandomNumberGenerator> 3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator& __rand); 3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_NO_EXTENSIONS) 3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// random_sample and random_sample_n (extensions, not part of the standard). 3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _OutputIter, class _Distance> 3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __out_ite, const _Distance __n); 3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _OutputIter, class _Distance, 3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _RandomNumberGenerator> 3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __out_ite, const _Distance __n, 3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator& __rand); 3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter> 3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrandom_sample(_InputIter __first, _InputIter __last, 3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __out_first, _RandomAccessIter __out_last); 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, 3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _RandomNumberGenerator> 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrandom_sample(_InputIter __first, _InputIter __last, 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __out_first, _RandomAccessIter __out_last, 3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator& __rand); 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_NO_EXTENSIONS */ 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// partition, stable_partition, and their auxiliary functions 3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred); 4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter 4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred); 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// sort() and its auxiliary functions. 4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Size> 4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Size __lg(_Size __n) { 4109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Size __k; 4119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__k = 0; __n != 1; __n >>= 1) ++__k; 4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __k; 4139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid sort(_RandomAccessIter __first, _RandomAccessIter __last); 4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp); 4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// stable_sort() and its auxiliary functions. 4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid stable_sort(_RandomAccessIter __first, 4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last); 4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid stable_sort(_RandomAccessIter __first, 4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp); 4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// partial_sort, partial_sort_copy, and auxiliary functions. 4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, 4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last); 4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp); 4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter> 4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpartial_sort_copy(_InputIter __first, _InputIter __last, 4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_first, _RandomAccessIter __result_last); 4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, class _Compare> 4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpartial_sort_copy(_InputIter __first, _InputIter __last, 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_first, 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_last, _Compare __comp); 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// nth_element() and its auxiliary functions. 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last); 4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp); 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// auxiliary class for lower_bound, etc. 4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _T1, class _T2> 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct __less_2 { 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator() (const _T1& __x, const _T2& __y) const { return __x < __y ; } 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _T1, class _T2> 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__less_2<_T1,_T2> __less2(_T1*, _T2* ) { return __less_2<_T1, _T2>(); } 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_FUNCTION_PARTIAL_ORDER) 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Tp> 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockless<_Tp> __less2(_Tp*, _Tp* ) { return less<_Tp>(); } 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Binary search (lower_bound, upper_bound, equal_range, binary_search). 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp> 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val) { 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lower_bound(__first, __last, __val, 4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0), 4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)), 4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare> 4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, 4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val, _Compare __comp) { 4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lower_bound(__first, __last, __val, __comp, __comp, 4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance> 5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare1 __comp1, _Compare2 __comp2, _Distance*); 5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp> 5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, 5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val) { 5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __upper_bound(__first, __last, __val, 5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0), 5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)), 5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare> 5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, 5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val, _Compare __comp) { 5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __upper_bound(__first, __last, __val, __comp, __comp, 5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance> 5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpair<_ForwardIter, _ForwardIter> 5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare1 __comp1, _Compare2 __comp2, _Distance*); 5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp> 5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline pair<_ForwardIter, _ForwardIter> 5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockequal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { 5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __equal_range(__first, __last, __val, 5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0), 5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)), 5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare> 5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline pair<_ForwardIter, _ForwardIter> 5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockequal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __equal_range(__first, __last, __val, __comp, __comp, 5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp> 5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool binary_search(_ForwardIter __first, _ForwardIter __last, 5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val) { 5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __i = _STLP_PRIV __lower_bound(__first, __last, __val, 5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2(_STLP_VALUE_TYPE(__first, _ForwardIter), (_Tp*)0), 5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less2((_Tp*)0, _STLP_VALUE_TYPE(__first, _ForwardIter)), 5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __i != __last && !(__val < *__i); 5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare> 5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool binary_search(_ForwardIter __first, _ForwardIter __last, 5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val, 5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __i = _STLP_PRIV __lower_bound(__first, __last, __val, __comp, __comp, 5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter)); 5709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __i != __last && !__comp(__val, *__i); 5719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// merge, with and without an explicitly supplied comparison function. 5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result); 5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 5819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp); 5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// inplace_merge and its auxiliary functions. 5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid inplace_merge(_BidirectionalIter __first, 5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last) ; 5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid inplace_merge(_BidirectionalIter __first, 5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 5989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, _Compare __comp); 5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Set algorithms: includes, set_union, set_intersection, set_difference, 6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// set_symmetric_difference. All of these algorithms have the precondition 6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// that their input ranges are sorted and the postcondition that their output 6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// ranges are sorted. 6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2> 6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool includes(_InputIter1 __first1, _InputIter1 __last1, 6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2); 6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _Compare> 6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool includes(_InputIter1 __first1, _InputIter1 __last1, 6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, _Compare __comp); 6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result); 6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp); 6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result); 6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp); 6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result); 6419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 6459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp); 6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockset_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result); 6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockset_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 6599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 6609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, 6619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 6629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// min_element and max_element, with and without an explicitly supplied 6659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// comparison function. 6669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 6689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last); 6699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Compare> 6709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, 6719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 6729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 6749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last); 6759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Compare> 6779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, 6789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 6799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// next_permutation and prev_permutation, with and without an explicitly 6819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// supplied comparison function. 6829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 6849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last); 6859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 6879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 6889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 6899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 6929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last); 6939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 6969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 6979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 6989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_NO_EXTENSIONS) 7009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// is_heap, a predicate testing whether or not a range is 7019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// a heap. This function is an extension, not part of the C++ 7029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// standard. 7039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 7059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool is_heap(_RandomAccessIter __first, _RandomAccessIter __last); 7069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _StrictWeakOrdering> 7089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 7099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _StrictWeakOrdering __comp); 7109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// is_sorted, a predicated testing whether a range is sorted in 7129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// nondescending order. This is an extension, not part of the C++ 7139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// standard. 7149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 7159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _StrictWeakOrdering> 7179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool __is_sorted(_ForwardIter __first, _ForwardIter __last, 7189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _StrictWeakOrdering __comp); 7199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 7219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 7229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool is_sorted(_ForwardIter __first, _ForwardIter __last) { 7239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __is_sorted(__first, __last, 7249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _ForwardIter))); 7259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _StrictWeakOrdering> 7289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool is_sorted(_ForwardIter __first, _ForwardIter __last, 7299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _StrictWeakOrdering __comp) { 7309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __is_sorted(__first, __last, __comp); 7319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 7339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 7359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_LINK_TIME_INSTANTIATION) 7379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_algo.c> 7389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 7399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_INTERNAL_ALGO_H */ 7419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 7439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 7449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 7459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 746