libstdc++
stl_algo.h
Go to the documentation of this file.
1 // Algorithm implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file stl_algo.h
53  * This is an internal header file, included by other library headers.
54  * You should not attempt to use it directly.
55  */
56 
57 #ifndef _STL_ALGO_H
58 #define _STL_ALGO_H 1
59 
60 #include <cstdlib> // for rand
61 #include <bits/algorithmfwd.h>
62 #include <bits/stl_heap.h>
63 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
64 #include <debug/debug.h>
65 #include <initializer_list>
66 
67 // See concept_check.h for the __glibcxx_*_requires macros.
68 
69 _GLIBCXX_BEGIN_NAMESPACE(std)
70 
71  /**
72  * @brief Find the median of three values.
73  * @param a A value.
74  * @param b A value.
75  * @param c A value.
76  * @return One of @p a, @p b or @p c.
77  *
78  * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
79  * then the value returned will be @c m.
80  * This is an SGI extension.
81  * @ingroup SGIextensions
82  */
83  template<typename _Tp>
84  inline const _Tp&
85  __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
86  {
87  // concept requirements
88  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
89  if (__a < __b)
90  if (__b < __c)
91  return __b;
92  else if (__a < __c)
93  return __c;
94  else
95  return __a;
96  else if (__a < __c)
97  return __a;
98  else if (__b < __c)
99  return __c;
100  else
101  return __b;
102  }
103 
104  /**
105  * @brief Find the median of three values using a predicate for comparison.
106  * @param a A value.
107  * @param b A value.
108  * @param c A value.
109  * @param comp A binary predicate.
110  * @return One of @p a, @p b or @p c.
111  *
112  * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
113  * and @p comp(m,n) are both true then the value returned will be @c m.
114  * This is an SGI extension.
115  * @ingroup SGIextensions
116  */
117  template<typename _Tp, typename _Compare>
118  inline const _Tp&
119  __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
120  {
121  // concept requirements
122  __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
123  _Tp, _Tp>)
124  if (__comp(__a, __b))
125  if (__comp(__b, __c))
126  return __b;
127  else if (__comp(__a, __c))
128  return __c;
129  else
130  return __a;
131  else if (__comp(__a, __c))
132  return __a;
133  else if (__comp(__b, __c))
134  return __c;
135  else
136  return __b;
137  }
138 
139  // for_each
140 
141  /// This is an overload used by find() for the Input Iterator case.
142  template<typename _InputIterator, typename _Tp>
143  inline _InputIterator
144  __find(_InputIterator __first, _InputIterator __last,
145  const _Tp& __val, input_iterator_tag)
146  {
147  while (__first != __last && !(*__first == __val))
148  ++__first;
149  return __first;
150  }
151 
152  /// This is an overload used by find_if() for the Input Iterator case.
153  template<typename _InputIterator, typename _Predicate>
154  inline _InputIterator
155  __find_if(_InputIterator __first, _InputIterator __last,
156  _Predicate __pred, input_iterator_tag)
157  {
158  while (__first != __last && !bool(__pred(*__first)))
159  ++__first;
160  return __first;
161  }
162 
163  /// This is an overload used by find() for the RAI case.
164  template<typename _RandomAccessIterator, typename _Tp>
165  _RandomAccessIterator
166  __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
167  const _Tp& __val, random_access_iterator_tag)
168  {
169  typename iterator_traits<_RandomAccessIterator>::difference_type
170  __trip_count = (__last - __first) >> 2;
171 
172  for (; __trip_count > 0; --__trip_count)
173  {
174  if (*__first == __val)
175  return __first;
176  ++__first;
177 
178  if (*__first == __val)
179  return __first;
180  ++__first;
181 
182  if (*__first == __val)
183  return __first;
184  ++__first;
185 
186  if (*__first == __val)
187  return __first;
188  ++__first;
189  }
190 
191  switch (__last - __first)
192  {
193  case 3:
194  if (*__first == __val)
195  return __first;
196  ++__first;
197  case 2:
198  if (*__first == __val)
199  return __first;
200  ++__first;
201  case 1:
202  if (*__first == __val)
203  return __first;
204  ++__first;
205  case 0:
206  default:
207  return __last;
208  }
209  }
210 
211  /// This is an overload used by find_if() for the RAI case.
212  template<typename _RandomAccessIterator, typename _Predicate>
213  _RandomAccessIterator
214  __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
215  _Predicate __pred, random_access_iterator_tag)
216  {
217  typename iterator_traits<_RandomAccessIterator>::difference_type
218  __trip_count = (__last - __first) >> 2;
219 
220  for (; __trip_count > 0; --__trip_count)
221  {
222  if (__pred(*__first))
223  return __first;
224  ++__first;
225 
226  if (__pred(*__first))
227  return __first;
228  ++__first;
229 
230  if (__pred(*__first))
231  return __first;
232  ++__first;
233 
234  if (__pred(*__first))
235  return __first;
236  ++__first;
237  }
238 
239  switch (__last - __first)
240  {
241  case 3:
242  if (__pred(*__first))
243  return __first;
244  ++__first;
245  case 2:
246  if (__pred(*__first))
247  return __first;
248  ++__first;
249  case 1:
250  if (__pred(*__first))
251  return __first;
252  ++__first;
253  case 0:
254  default:
255  return __last;
256  }
257  }
258 
259 #ifdef __GXX_EXPERIMENTAL_CXX0X__
260  /// This is an overload used by find_if_not() for the Input Iterator case.
261  template<typename _InputIterator, typename _Predicate>
262  inline _InputIterator
263  __find_if_not(_InputIterator __first, _InputIterator __last,
264  _Predicate __pred, input_iterator_tag)
265  {
266  while (__first != __last && bool(__pred(*__first)))
267  ++__first;
268  return __first;
269  }
270 
271  /// This is an overload used by find_if_not() for the RAI case.
272  template<typename _RandomAccessIterator, typename _Predicate>
273  _RandomAccessIterator
274  __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
275  _Predicate __pred, random_access_iterator_tag)
276  {
277  typename iterator_traits<_RandomAccessIterator>::difference_type
278  __trip_count = (__last - __first) >> 2;
279 
280  for (; __trip_count > 0; --__trip_count)
281  {
282  if (!bool(__pred(*__first)))
283  return __first;
284  ++__first;
285 
286  if (!bool(__pred(*__first)))
287  return __first;
288  ++__first;
289 
290  if (!bool(__pred(*__first)))
291  return __first;
292  ++__first;
293 
294  if (!bool(__pred(*__first)))
295  return __first;
296  ++__first;
297  }
298 
299  switch (__last - __first)
300  {
301  case 3:
302  if (!bool(__pred(*__first)))
303  return __first;
304  ++__first;
305  case 2:
306  if (!bool(__pred(*__first)))
307  return __first;
308  ++__first;
309  case 1:
310  if (!bool(__pred(*__first)))
311  return __first;
312  ++__first;
313  case 0:
314  default:
315  return __last;
316  }
317  }
318 #endif
319 
320  // set_difference
321  // set_intersection
322  // set_symmetric_difference
323  // set_union
324  // for_each
325  // find
326  // find_if
327  // find_first_of
328  // adjacent_find
329  // count
330  // count_if
331  // search
332 
333  /**
334  * This is an uglified
335  * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
336  * overloaded for forward iterators.
337  */
338  template<typename _ForwardIterator, typename _Integer, typename _Tp>
339  _ForwardIterator
340  __search_n(_ForwardIterator __first, _ForwardIterator __last,
341  _Integer __count, const _Tp& __val,
343  {
344  __first = _GLIBCXX_STD_P::find(__first, __last, __val);
345  while (__first != __last)
346  {
347  typename iterator_traits<_ForwardIterator>::difference_type
348  __n = __count;
349  _ForwardIterator __i = __first;
350  ++__i;
351  while (__i != __last && __n != 1 && *__i == __val)
352  {
353  ++__i;
354  --__n;
355  }
356  if (__n == 1)
357  return __first;
358  if (__i == __last)
359  return __last;
360  __first = _GLIBCXX_STD_P::find(++__i, __last, __val);
361  }
362  return __last;
363  }
364 
365  /**
366  * This is an uglified
367  * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
368  * overloaded for random access iterators.
369  */
370  template<typename _RandomAccessIter, typename _Integer, typename _Tp>
371  _RandomAccessIter
372  __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
373  _Integer __count, const _Tp& __val,
375  {
376 
377  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
378  _DistanceType;
379 
380  _DistanceType __tailSize = __last - __first;
381  const _DistanceType __pattSize = __count;
382 
383  if (__tailSize < __pattSize)
384  return __last;
385 
386  const _DistanceType __skipOffset = __pattSize - 1;
387  _RandomAccessIter __lookAhead = __first + __skipOffset;
388  __tailSize -= __pattSize;
389 
390  while (1) // the main loop...
391  {
392  // __lookAhead here is always pointing to the last element of next
393  // possible match.
394  while (!(*__lookAhead == __val)) // the skip loop...
395  {
396  if (__tailSize < __pattSize)
397  return __last; // Failure
398  __lookAhead += __pattSize;
399  __tailSize -= __pattSize;
400  }
401  _DistanceType __remainder = __skipOffset;
402  for (_RandomAccessIter __backTrack = __lookAhead - 1;
403  *__backTrack == __val; --__backTrack)
404  {
405  if (--__remainder == 0)
406  return (__lookAhead - __skipOffset); // Success
407  }
408  if (__remainder > __tailSize)
409  return __last; // Failure
410  __lookAhead += __remainder;
411  __tailSize -= __remainder;
412  }
413  }
414 
415  // search_n
416 
417  /**
418  * This is an uglified
419  * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
420  * _BinaryPredicate)
421  * overloaded for forward iterators.
422  */
423  template<typename _ForwardIterator, typename _Integer, typename _Tp,
424  typename _BinaryPredicate>
425  _ForwardIterator
426  __search_n(_ForwardIterator __first, _ForwardIterator __last,
427  _Integer __count, const _Tp& __val,
428  _BinaryPredicate __binary_pred, std::forward_iterator_tag)
429  {
430  while (__first != __last && !bool(__binary_pred(*__first, __val)))
431  ++__first;
432 
433  while (__first != __last)
434  {
435  typename iterator_traits<_ForwardIterator>::difference_type
436  __n = __count;
437  _ForwardIterator __i = __first;
438  ++__i;
439  while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
440  {
441  ++__i;
442  --__n;
443  }
444  if (__n == 1)
445  return __first;
446  if (__i == __last)
447  return __last;
448  __first = ++__i;
449  while (__first != __last
450  && !bool(__binary_pred(*__first, __val)))
451  ++__first;
452  }
453  return __last;
454  }
455 
456  /**
457  * This is an uglified
458  * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
459  * _BinaryPredicate)
460  * overloaded for random access iterators.
461  */
462  template<typename _RandomAccessIter, typename _Integer, typename _Tp,
463  typename _BinaryPredicate>
464  _RandomAccessIter
465  __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
466  _Integer __count, const _Tp& __val,
467  _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
468  {
469 
470  typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
471  _DistanceType;
472 
473  _DistanceType __tailSize = __last - __first;
474  const _DistanceType __pattSize = __count;
475 
476  if (__tailSize < __pattSize)
477  return __last;
478 
479  const _DistanceType __skipOffset = __pattSize - 1;
480  _RandomAccessIter __lookAhead = __first + __skipOffset;
481  __tailSize -= __pattSize;
482 
483  while (1) // the main loop...
484  {
485  // __lookAhead here is always pointing to the last element of next
486  // possible match.
487  while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
488  {
489  if (__tailSize < __pattSize)
490  return __last; // Failure
491  __lookAhead += __pattSize;
492  __tailSize -= __pattSize;
493  }
494  _DistanceType __remainder = __skipOffset;
495  for (_RandomAccessIter __backTrack = __lookAhead - 1;
496  __binary_pred(*__backTrack, __val); --__backTrack)
497  {
498  if (--__remainder == 0)
499  return (__lookAhead - __skipOffset); // Success
500  }
501  if (__remainder > __tailSize)
502  return __last; // Failure
503  __lookAhead += __remainder;
504  __tailSize -= __remainder;
505  }
506  }
507 
508  // find_end for forward iterators.
509  template<typename _ForwardIterator1, typename _ForwardIterator2>
510  _ForwardIterator1
511  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
512  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
513  forward_iterator_tag, forward_iterator_tag)
514  {
515  if (__first2 == __last2)
516  return __last1;
517  else
518  {
519  _ForwardIterator1 __result = __last1;
520  while (1)
521  {
522  _ForwardIterator1 __new_result
523  = _GLIBCXX_STD_P::search(__first1, __last1, __first2, __last2);
524  if (__new_result == __last1)
525  return __result;
526  else
527  {
528  __result = __new_result;
529  __first1 = __new_result;
530  ++__first1;
531  }
532  }
533  }
534  }
535 
536  template<typename _ForwardIterator1, typename _ForwardIterator2,
537  typename _BinaryPredicate>
538  _ForwardIterator1
539  __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
540  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
541  forward_iterator_tag, forward_iterator_tag,
542  _BinaryPredicate __comp)
543  {
544  if (__first2 == __last2)
545  return __last1;
546  else
547  {
548  _ForwardIterator1 __result = __last1;
549  while (1)
550  {
551  _ForwardIterator1 __new_result
552  = _GLIBCXX_STD_P::search(__first1, __last1, __first2,
553  __last2, __comp);
554  if (__new_result == __last1)
555  return __result;
556  else
557  {
558  __result = __new_result;
559  __first1 = __new_result;
560  ++__first1;
561  }
562  }
563  }
564  }
565 
566  // find_end for bidirectional iterators (much faster).
567  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
568  _BidirectionalIterator1
569  __find_end(_BidirectionalIterator1 __first1,
570  _BidirectionalIterator1 __last1,
571  _BidirectionalIterator2 __first2,
572  _BidirectionalIterator2 __last2,
573  bidirectional_iterator_tag, bidirectional_iterator_tag)
574  {
575  // concept requirements
576  __glibcxx_function_requires(_BidirectionalIteratorConcept<
577  _BidirectionalIterator1>)
578  __glibcxx_function_requires(_BidirectionalIteratorConcept<
579  _BidirectionalIterator2>)
580 
581  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
582  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
583 
584  _RevIterator1 __rlast1(__first1);
585  _RevIterator2 __rlast2(__first2);
586  _RevIterator1 __rresult = _GLIBCXX_STD_P::search(_RevIterator1(__last1),
587  __rlast1,
588  _RevIterator2(__last2),
589  __rlast2);
590 
591  if (__rresult == __rlast1)
592  return __last1;
593  else
594  {
595  _BidirectionalIterator1 __result = __rresult.base();
596  std::advance(__result, -std::distance(__first2, __last2));
597  return __result;
598  }
599  }
600 
601  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
602  typename _BinaryPredicate>
603  _BidirectionalIterator1
604  __find_end(_BidirectionalIterator1 __first1,
605  _BidirectionalIterator1 __last1,
606  _BidirectionalIterator2 __first2,
607  _BidirectionalIterator2 __last2,
608  bidirectional_iterator_tag, bidirectional_iterator_tag,
609  _BinaryPredicate __comp)
610  {
611  // concept requirements
612  __glibcxx_function_requires(_BidirectionalIteratorConcept<
613  _BidirectionalIterator1>)
614  __glibcxx_function_requires(_BidirectionalIteratorConcept<
615  _BidirectionalIterator2>)
616 
617  typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
618  typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
619 
620  _RevIterator1 __rlast1(__first1);
621  _RevIterator2 __rlast2(__first2);
622  _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
623  _RevIterator2(__last2), __rlast2,
624  __comp);
625 
626  if (__rresult == __rlast1)
627  return __last1;
628  else
629  {
630  _BidirectionalIterator1 __result = __rresult.base();
631  std::advance(__result, -std::distance(__first2, __last2));
632  return __result;
633  }
634  }
635 
636  /**
637  * @brief Find last matching subsequence in a sequence.
638  * @ingroup non_mutating_algorithms
639  * @param first1 Start of range to search.
640  * @param last1 End of range to search.
641  * @param first2 Start of sequence to match.
642  * @param last2 End of sequence to match.
643  * @return The last iterator @c i in the range
644  * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
645  * for each @c N in the range @p [0,last2-first2), or @p last1 if no
646  * such iterator exists.
647  *
648  * Searches the range @p [first1,last1) for a sub-sequence that compares
649  * equal value-by-value with the sequence given by @p [first2,last2) and
650  * returns an iterator to the first element of the sub-sequence, or
651  * @p last1 if the sub-sequence is not found. The sub-sequence will be the
652  * last such subsequence contained in [first,last1).
653  *
654  * Because the sub-sequence must lie completely within the range
655  * @p [first1,last1) it must start at a position less than
656  * @p last1-(last2-first2) where @p last2-first2 is the length of the
657  * sub-sequence.
658  * This means that the returned iterator @c i will be in the range
659  * @p [first1,last1-(last2-first2))
660  */
661  template<typename _ForwardIterator1, typename _ForwardIterator2>
662  inline _ForwardIterator1
663  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
664  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
665  {
666  // concept requirements
667  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
668  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
669  __glibcxx_function_requires(_EqualOpConcept<
670  typename iterator_traits<_ForwardIterator1>::value_type,
671  typename iterator_traits<_ForwardIterator2>::value_type>)
672  __glibcxx_requires_valid_range(__first1, __last1);
673  __glibcxx_requires_valid_range(__first2, __last2);
674 
675  return std::__find_end(__first1, __last1, __first2, __last2,
676  std::__iterator_category(__first1),
677  std::__iterator_category(__first2));
678  }
679 
680  /**
681  * @brief Find last matching subsequence in a sequence using a predicate.
682  * @ingroup non_mutating_algorithms
683  * @param first1 Start of range to search.
684  * @param last1 End of range to search.
685  * @param first2 Start of sequence to match.
686  * @param last2 End of sequence to match.
687  * @param comp The predicate to use.
688  * @return The last iterator @c i in the range
689  * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
690  * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
691  * @p last1 if no such iterator exists.
692  *
693  * Searches the range @p [first1,last1) for a sub-sequence that compares
694  * equal value-by-value with the sequence given by @p [first2,last2) using
695  * comp as a predicate and returns an iterator to the first element of the
696  * sub-sequence, or @p last1 if the sub-sequence is not found. The
697  * sub-sequence will be the last such subsequence contained in
698  * [first,last1).
699  *
700  * Because the sub-sequence must lie completely within the range
701  * @p [first1,last1) it must start at a position less than
702  * @p last1-(last2-first2) where @p last2-first2 is the length of the
703  * sub-sequence.
704  * This means that the returned iterator @c i will be in the range
705  * @p [first1,last1-(last2-first2))
706  */
707  template<typename _ForwardIterator1, typename _ForwardIterator2,
708  typename _BinaryPredicate>
709  inline _ForwardIterator1
710  find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
711  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
712  _BinaryPredicate __comp)
713  {
714  // concept requirements
715  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
716  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
717  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
718  typename iterator_traits<_ForwardIterator1>::value_type,
719  typename iterator_traits<_ForwardIterator2>::value_type>)
720  __glibcxx_requires_valid_range(__first1, __last1);
721  __glibcxx_requires_valid_range(__first2, __last2);
722 
723  return std::__find_end(__first1, __last1, __first2, __last2,
724  std::__iterator_category(__first1),
725  std::__iterator_category(__first2),
726  __comp);
727  }
728 
729 #ifdef __GXX_EXPERIMENTAL_CXX0X__
730  /**
731  * @brief Checks that a predicate is true for all the elements
732  * of a sequence.
733  * @ingroup non_mutating_algorithms
734  * @param first An input iterator.
735  * @param last An input iterator.
736  * @param pred A predicate.
737  * @return True if the check is true, false otherwise.
738  *
739  * Returns true if @p pred is true for each element in the range
740  * @p [first,last), and false otherwise.
741  */
742  template<typename _InputIterator, typename _Predicate>
743  inline bool
744  all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
745  { return __last == std::find_if_not(__first, __last, __pred); }
746 
747  /**
748  * @brief Checks that a predicate is false for all the elements
749  * of a sequence.
750  * @ingroup non_mutating_algorithms
751  * @param first An input iterator.
752  * @param last An input iterator.
753  * @param pred A predicate.
754  * @return True if the check is true, false otherwise.
755  *
756  * Returns true if @p pred is false for each element in the range
757  * @p [first,last), and false otherwise.
758  */
759  template<typename _InputIterator, typename _Predicate>
760  inline bool
761  none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
762  { return __last == _GLIBCXX_STD_P::find_if(__first, __last, __pred); }
763 
764  /**
765  * @brief Checks that a predicate is false for at least an element
766  * of a sequence.
767  * @ingroup non_mutating_algorithms
768  * @param first An input iterator.
769  * @param last An input iterator.
770  * @param pred A predicate.
771  * @return True if the check is true, false otherwise.
772  *
773  * Returns true if an element exists in the range @p [first,last) such that
774  * @p pred is true, and false otherwise.
775  */
776  template<typename _InputIterator, typename _Predicate>
777  inline bool
778  any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
779  { return !std::none_of(__first, __last, __pred); }
780 
781  /**
782  * @brief Find the first element in a sequence for which a
783  * predicate is false.
784  * @ingroup non_mutating_algorithms
785  * @param first An input iterator.
786  * @param last An input iterator.
787  * @param pred A predicate.
788  * @return The first iterator @c i in the range @p [first,last)
789  * such that @p pred(*i) is false, or @p last if no such iterator exists.
790  */
791  template<typename _InputIterator, typename _Predicate>
792  inline _InputIterator
793  find_if_not(_InputIterator __first, _InputIterator __last,
794  _Predicate __pred)
795  {
796  // concept requirements
797  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
798  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
799  typename iterator_traits<_InputIterator>::value_type>)
800  __glibcxx_requires_valid_range(__first, __last);
801  return std::__find_if_not(__first, __last, __pred,
802  std::__iterator_category(__first));
803  }
804 
805  /**
806  * @brief Checks whether the sequence is partitioned.
807  * @ingroup mutating_algorithms
808  * @param first An input iterator.
809  * @param last An input iterator.
810  * @param pred A predicate.
811  * @return True if the range @p [first,last) is partioned by @p pred,
812  * i.e. if all elements that satisfy @p pred appear before those that
813  * do not.
814  */
815  template<typename _InputIterator, typename _Predicate>
816  inline bool
817  is_partitioned(_InputIterator __first, _InputIterator __last,
818  _Predicate __pred)
819  {
820  __first = std::find_if_not(__first, __last, __pred);
821  return std::none_of(__first, __last, __pred);
822  }
823 
824  /**
825  * @brief Find the partition point of a partitioned range.
826  * @ingroup mutating_algorithms
827  * @param first An iterator.
828  * @param last Another iterator.
829  * @param pred A predicate.
830  * @return An iterator @p mid such that @p all_of(first, mid, pred)
831  * and @p none_of(mid, last, pred) are both true.
832  */
833  template<typename _ForwardIterator, typename _Predicate>
834  _ForwardIterator
835  partition_point(_ForwardIterator __first, _ForwardIterator __last,
836  _Predicate __pred)
837  {
838  // concept requirements
839  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
840  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
841  typename iterator_traits<_ForwardIterator>::value_type>)
842 
843  // A specific debug-mode test will be necessary...
844  __glibcxx_requires_valid_range(__first, __last);
845 
846  typedef typename iterator_traits<_ForwardIterator>::difference_type
847  _DistanceType;
848 
849  _DistanceType __len = std::distance(__first, __last);
850  _DistanceType __half;
851  _ForwardIterator __middle;
852 
853  while (__len > 0)
854  {
855  __half = __len >> 1;
856  __middle = __first;
857  std::advance(__middle, __half);
858  if (__pred(*__middle))
859  {
860  __first = __middle;
861  ++__first;
862  __len = __len - __half - 1;
863  }
864  else
865  __len = __half;
866  }
867  return __first;
868  }
869 #endif
870 
871 
872  /**
873  * @brief Copy a sequence, removing elements of a given value.
874  * @ingroup mutating_algorithms
875  * @param first An input iterator.
876  * @param last An input iterator.
877  * @param result An output iterator.
878  * @param value The value to be removed.
879  * @return An iterator designating the end of the resulting sequence.
880  *
881  * Copies each element in the range @p [first,last) not equal to @p value
882  * to the range beginning at @p result.
883  * remove_copy() is stable, so the relative order of elements that are
884  * copied is unchanged.
885  */
886  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
887  _OutputIterator
888  remove_copy(_InputIterator __first, _InputIterator __last,
889  _OutputIterator __result, const _Tp& __value)
890  {
891  // concept requirements
892  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
893  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
894  typename iterator_traits<_InputIterator>::value_type>)
895  __glibcxx_function_requires(_EqualOpConcept<
896  typename iterator_traits<_InputIterator>::value_type, _Tp>)
897  __glibcxx_requires_valid_range(__first, __last);
898 
899  for (; __first != __last; ++__first)
900  if (!(*__first == __value))
901  {
902  *__result = *__first;
903  ++__result;
904  }
905  return __result;
906  }
907 
908  /**
909  * @brief Copy a sequence, removing elements for which a predicate is true.
910  * @ingroup mutating_algorithms
911  * @param first An input iterator.
912  * @param last An input iterator.
913  * @param result An output iterator.
914  * @param pred A predicate.
915  * @return An iterator designating the end of the resulting sequence.
916  *
917  * Copies each element in the range @p [first,last) for which
918  * @p pred returns false to the range beginning at @p result.
919  *
920  * remove_copy_if() is stable, so the relative order of elements that are
921  * copied is unchanged.
922  */
923  template<typename _InputIterator, typename _OutputIterator,
924  typename _Predicate>
925  _OutputIterator
926  remove_copy_if(_InputIterator __first, _InputIterator __last,
927  _OutputIterator __result, _Predicate __pred)
928  {
929  // concept requirements
930  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
931  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
932  typename iterator_traits<_InputIterator>::value_type>)
933  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
934  typename iterator_traits<_InputIterator>::value_type>)
935  __glibcxx_requires_valid_range(__first, __last);
936 
937  for (; __first != __last; ++__first)
938  if (!bool(__pred(*__first)))
939  {
940  *__result = *__first;
941  ++__result;
942  }
943  return __result;
944  }
945 
946 #ifdef __GXX_EXPERIMENTAL_CXX0X__
947  /**
948  * @brief Copy the elements of a sequence for which a predicate is true.
949  * @ingroup mutating_algorithms
950  * @param first An input iterator.
951  * @param last An input iterator.
952  * @param result An output iterator.
953  * @param pred A predicate.
954  * @return An iterator designating the end of the resulting sequence.
955  *
956  * Copies each element in the range @p [first,last) for which
957  * @p pred returns true to the range beginning at @p result.
958  *
959  * copy_if() is stable, so the relative order of elements that are
960  * copied is unchanged.
961  */
962  template<typename _InputIterator, typename _OutputIterator,
963  typename _Predicate>
964  _OutputIterator
965  copy_if(_InputIterator __first, _InputIterator __last,
966  _OutputIterator __result, _Predicate __pred)
967  {
968  // concept requirements
969  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
970  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
971  typename iterator_traits<_InputIterator>::value_type>)
972  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
973  typename iterator_traits<_InputIterator>::value_type>)
974  __glibcxx_requires_valid_range(__first, __last);
975 
976  for (; __first != __last; ++__first)
977  if (__pred(*__first))
978  {
979  *__result = *__first;
980  ++__result;
981  }
982  return __result;
983  }
984 
985 
986  template<typename _InputIterator, typename _Size, typename _OutputIterator>
987  _OutputIterator
988  __copy_n(_InputIterator __first, _Size __n,
989  _OutputIterator __result, input_iterator_tag)
990  {
991  for (; __n > 0; --__n)
992  {
993  *__result = *__first;
994  ++__first;
995  ++__result;
996  }
997  return __result;
998  }
999 
1000  template<typename _RandomAccessIterator, typename _Size,
1001  typename _OutputIterator>
1002  inline _OutputIterator
1003  __copy_n(_RandomAccessIterator __first, _Size __n,
1004  _OutputIterator __result, random_access_iterator_tag)
1005  { return std::copy(__first, __first + __n, __result); }
1006 
1007  /**
1008  * @brief Copies the range [first,first+n) into [result,result+n).
1009  * @ingroup mutating_algorithms
1010  * @param first An input iterator.
1011  * @param n The number of elements to copy.
1012  * @param result An output iterator.
1013  * @return result+n.
1014  *
1015  * This inline function will boil down to a call to @c memmove whenever
1016  * possible. Failing that, if random access iterators are passed, then the
1017  * loop count will be known (and therefore a candidate for compiler
1018  * optimizations such as unrolling).
1019  */
1020  template<typename _InputIterator, typename _Size, typename _OutputIterator>
1021  inline _OutputIterator
1022  copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1023  {
1024  // concept requirements
1025  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1026  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1027  typename iterator_traits<_InputIterator>::value_type>)
1028 
1029  return std::__copy_n(__first, __n, __result,
1030  std::__iterator_category(__first));
1031  }
1032 
1033  /**
1034  * @brief Copy the elements of a sequence to separate output sequences
1035  * depending on the truth value of a predicate.
1036  * @ingroup mutating_algorithms
1037  * @param first An input iterator.
1038  * @param last An input iterator.
1039  * @param out_true An output iterator.
1040  * @param out_false An output iterator.
1041  * @param pred A predicate.
1042  * @return A pair designating the ends of the resulting sequences.
1043  *
1044  * Copies each element in the range @p [first,last) for which
1045  * @p pred returns true to the range beginning at @p out_true
1046  * and each element for which @p pred returns false to @p out_false.
1047  */
1048  template<typename _InputIterator, typename _OutputIterator1,
1049  typename _OutputIterator2, typename _Predicate>
1050  pair<_OutputIterator1, _OutputIterator2>
1051  partition_copy(_InputIterator __first, _InputIterator __last,
1052  _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1053  _Predicate __pred)
1054  {
1055  // concept requirements
1056  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1057  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1058  typename iterator_traits<_InputIterator>::value_type>)
1059  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1060  typename iterator_traits<_InputIterator>::value_type>)
1061  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1062  typename iterator_traits<_InputIterator>::value_type>)
1063  __glibcxx_requires_valid_range(__first, __last);
1064 
1065  for (; __first != __last; ++__first)
1066  if (__pred(*__first))
1067  {
1068  *__out_true = *__first;
1069  ++__out_true;
1070  }
1071  else
1072  {
1073  *__out_false = *__first;
1074  ++__out_false;
1075  }
1076 
1077  return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1078  }
1079 #endif
1080 
1081  /**
1082  * @brief Remove elements from a sequence.
1083  * @ingroup mutating_algorithms
1084  * @param first An input iterator.
1085  * @param last An input iterator.
1086  * @param value The value to be removed.
1087  * @return An iterator designating the end of the resulting sequence.
1088  *
1089  * All elements equal to @p value are removed from the range
1090  * @p [first,last).
1091  *
1092  * remove() is stable, so the relative order of elements that are
1093  * not removed is unchanged.
1094  *
1095  * Elements between the end of the resulting sequence and @p last
1096  * are still present, but their value is unspecified.
1097  */
1098  template<typename _ForwardIterator, typename _Tp>
1099  _ForwardIterator
1100  remove(_ForwardIterator __first, _ForwardIterator __last,
1101  const _Tp& __value)
1102  {
1103  // concept requirements
1104  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1105  _ForwardIterator>)
1106  __glibcxx_function_requires(_EqualOpConcept<
1107  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1108  __glibcxx_requires_valid_range(__first, __last);
1109 
1110  __first = _GLIBCXX_STD_P::find(__first, __last, __value);
1111  if(__first == __last)
1112  return __first;
1113  _ForwardIterator __result = __first;
1114  ++__first;
1115  for(; __first != __last; ++__first)
1116  if(!(*__first == __value))
1117  {
1118  *__result = _GLIBCXX_MOVE(*__first);
1119  ++__result;
1120  }
1121  return __result;
1122  }
1123 
1124  /**
1125  * @brief Remove elements from a sequence using a predicate.
1126  * @ingroup mutating_algorithms
1127  * @param first A forward iterator.
1128  * @param last A forward iterator.
1129  * @param pred A predicate.
1130  * @return An iterator designating the end of the resulting sequence.
1131  *
1132  * All elements for which @p pred returns true are removed from the range
1133  * @p [first,last).
1134  *
1135  * remove_if() is stable, so the relative order of elements that are
1136  * not removed is unchanged.
1137  *
1138  * Elements between the end of the resulting sequence and @p last
1139  * are still present, but their value is unspecified.
1140  */
1141  template<typename _ForwardIterator, typename _Predicate>
1142  _ForwardIterator
1143  remove_if(_ForwardIterator __first, _ForwardIterator __last,
1144  _Predicate __pred)
1145  {
1146  // concept requirements
1147  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1148  _ForwardIterator>)
1149  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1150  typename iterator_traits<_ForwardIterator>::value_type>)
1151  __glibcxx_requires_valid_range(__first, __last);
1152 
1153  __first = _GLIBCXX_STD_P::find_if(__first, __last, __pred);
1154  if(__first == __last)
1155  return __first;
1156  _ForwardIterator __result = __first;
1157  ++__first;
1158  for(; __first != __last; ++__first)
1159  if(!bool(__pred(*__first)))
1160  {
1161  *__result = _GLIBCXX_MOVE(*__first);
1162  ++__result;
1163  }
1164  return __result;
1165  }
1166 
1167  /**
1168  * @brief Remove consecutive duplicate values from a sequence.
1169  * @ingroup mutating_algorithms
1170  * @param first A forward iterator.
1171  * @param last A forward iterator.
1172  * @return An iterator designating the end of the resulting sequence.
1173  *
1174  * Removes all but the first element from each group of consecutive
1175  * values that compare equal.
1176  * unique() is stable, so the relative order of elements that are
1177  * not removed is unchanged.
1178  * Elements between the end of the resulting sequence and @p last
1179  * are still present, but their value is unspecified.
1180  */
1181  template<typename _ForwardIterator>
1182  _ForwardIterator
1183  unique(_ForwardIterator __first, _ForwardIterator __last)
1184  {
1185  // concept requirements
1186  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1187  _ForwardIterator>)
1188  __glibcxx_function_requires(_EqualityComparableConcept<
1189  typename iterator_traits<_ForwardIterator>::value_type>)
1190  __glibcxx_requires_valid_range(__first, __last);
1191 
1192  // Skip the beginning, if already unique.
1193  __first = _GLIBCXX_STD_P::adjacent_find(__first, __last);
1194  if (__first == __last)
1195  return __last;
1196 
1197  // Do the real copy work.
1198  _ForwardIterator __dest = __first;
1199  ++__first;
1200  while (++__first != __last)
1201  if (!(*__dest == *__first))
1202  *++__dest = _GLIBCXX_MOVE(*__first);
1203  return ++__dest;
1204  }
1205 
1206  /**
1207  * @brief Remove consecutive values from a sequence using a predicate.
1208  * @ingroup mutating_algorithms
1209  * @param first A forward iterator.
1210  * @param last A forward iterator.
1211  * @param binary_pred A binary predicate.
1212  * @return An iterator designating the end of the resulting sequence.
1213  *
1214  * Removes all but the first element from each group of consecutive
1215  * values for which @p binary_pred returns true.
1216  * unique() is stable, so the relative order of elements that are
1217  * not removed is unchanged.
1218  * Elements between the end of the resulting sequence and @p last
1219  * are still present, but their value is unspecified.
1220  */
1221  template<typename _ForwardIterator, typename _BinaryPredicate>
1222  _ForwardIterator
1223  unique(_ForwardIterator __first, _ForwardIterator __last,
1224  _BinaryPredicate __binary_pred)
1225  {
1226  // concept requirements
1227  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1228  _ForwardIterator>)
1229  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1230  typename iterator_traits<_ForwardIterator>::value_type,
1231  typename iterator_traits<_ForwardIterator>::value_type>)
1232  __glibcxx_requires_valid_range(__first, __last);
1233 
1234  // Skip the beginning, if already unique.
1235  __first = _GLIBCXX_STD_P::adjacent_find(__first, __last, __binary_pred);
1236  if (__first == __last)
1237  return __last;
1238 
1239  // Do the real copy work.
1240  _ForwardIterator __dest = __first;
1241  ++__first;
1242  while (++__first != __last)
1243  if (!bool(__binary_pred(*__dest, *__first)))
1244  *++__dest = _GLIBCXX_MOVE(*__first);
1245  return ++__dest;
1246  }
1247 
1248  /**
1249  * This is an uglified unique_copy(_InputIterator, _InputIterator,
1250  * _OutputIterator)
1251  * overloaded for forward iterators and output iterator as result.
1252  */
1253  template<typename _ForwardIterator, typename _OutputIterator>
1254  _OutputIterator
1255  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1256  _OutputIterator __result,
1258  {
1259  // concept requirements -- taken care of in dispatching function
1260  _ForwardIterator __next = __first;
1261  *__result = *__first;
1262  while (++__next != __last)
1263  if (!(*__first == *__next))
1264  {
1265  __first = __next;
1266  *++__result = *__first;
1267  }
1268  return ++__result;
1269  }
1270 
1271  /**
1272  * This is an uglified unique_copy(_InputIterator, _InputIterator,
1273  * _OutputIterator)
1274  * overloaded for input iterators and output iterator as result.
1275  */
1276  template<typename _InputIterator, typename _OutputIterator>
1277  _OutputIterator
1278  __unique_copy(_InputIterator __first, _InputIterator __last,
1279  _OutputIterator __result,
1281  {
1282  // concept requirements -- taken care of in dispatching function
1283  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1284  *__result = __value;
1285  while (++__first != __last)
1286  if (!(__value == *__first))
1287  {
1288  __value = *__first;
1289  *++__result = __value;
1290  }
1291  return ++__result;
1292  }
1293 
1294  /**
1295  * This is an uglified unique_copy(_InputIterator, _InputIterator,
1296  * _OutputIterator)
1297  * overloaded for input iterators and forward iterator as result.
1298  */
1299  template<typename _InputIterator, typename _ForwardIterator>
1300  _ForwardIterator
1301  __unique_copy(_InputIterator __first, _InputIterator __last,
1302  _ForwardIterator __result,
1304  {
1305  // concept requirements -- taken care of in dispatching function
1306  *__result = *__first;
1307  while (++__first != __last)
1308  if (!(*__result == *__first))
1309  *++__result = *__first;
1310  return ++__result;
1311  }
1312 
1313  /**
1314  * This is an uglified
1315  * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1316  * _BinaryPredicate)
1317  * overloaded for forward iterators and output iterator as result.
1318  */
1319  template<typename _ForwardIterator, typename _OutputIterator,
1320  typename _BinaryPredicate>
1321  _OutputIterator
1322  __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1323  _OutputIterator __result, _BinaryPredicate __binary_pred,
1325  {
1326  // concept requirements -- iterators already checked
1327  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1328  typename iterator_traits<_ForwardIterator>::value_type,
1329  typename iterator_traits<_ForwardIterator>::value_type>)
1330 
1331  _ForwardIterator __next = __first;
1332  *__result = *__first;
1333  while (++__next != __last)
1334  if (!bool(__binary_pred(*__first, *__next)))
1335  {
1336  __first = __next;
1337  *++__result = *__first;
1338  }
1339  return ++__result;
1340  }
1341 
1342  /**
1343  * This is an uglified
1344  * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1345  * _BinaryPredicate)
1346  * overloaded for input iterators and output iterator as result.
1347  */
1348  template<typename _InputIterator, typename _OutputIterator,
1349  typename _BinaryPredicate>
1350  _OutputIterator
1351  __unique_copy(_InputIterator __first, _InputIterator __last,
1352  _OutputIterator __result, _BinaryPredicate __binary_pred,
1354  {
1355  // concept requirements -- iterators already checked
1356  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1357  typename iterator_traits<_InputIterator>::value_type,
1358  typename iterator_traits<_InputIterator>::value_type>)
1359 
1360  typename iterator_traits<_InputIterator>::value_type __value = *__first;
1361  *__result = __value;
1362  while (++__first != __last)
1363  if (!bool(__binary_pred(__value, *__first)))
1364  {
1365  __value = *__first;
1366  *++__result = __value;
1367  }
1368  return ++__result;
1369  }
1370 
1371  /**
1372  * This is an uglified
1373  * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1374  * _BinaryPredicate)
1375  * overloaded for input iterators and forward iterator as result.
1376  */
1377  template<typename _InputIterator, typename _ForwardIterator,
1378  typename _BinaryPredicate>
1379  _ForwardIterator
1380  __unique_copy(_InputIterator __first, _InputIterator __last,
1381  _ForwardIterator __result, _BinaryPredicate __binary_pred,
1383  {
1384  // concept requirements -- iterators already checked
1385  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1386  typename iterator_traits<_ForwardIterator>::value_type,
1387  typename iterator_traits<_InputIterator>::value_type>)
1388 
1389  *__result = *__first;
1390  while (++__first != __last)
1391  if (!bool(__binary_pred(*__result, *__first)))
1392  *++__result = *__first;
1393  return ++__result;
1394  }
1395 
1396  /**
1397  * This is an uglified reverse(_BidirectionalIterator,
1398  * _BidirectionalIterator)
1399  * overloaded for bidirectional iterators.
1400  */
1401  template<typename _BidirectionalIterator>
1402  void
1403  __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1405  {
1406  while (true)
1407  if (__first == __last || __first == --__last)
1408  return;
1409  else
1410  {
1411  std::iter_swap(__first, __last);
1412  ++__first;
1413  }
1414  }
1415 
1416  /**
1417  * This is an uglified reverse(_BidirectionalIterator,
1418  * _BidirectionalIterator)
1419  * overloaded for random access iterators.
1420  */
1421  template<typename _RandomAccessIterator>
1422  void
1423  __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1425  {
1426  if (__first == __last)
1427  return;
1428  --__last;
1429  while (__first < __last)
1430  {
1431  std::iter_swap(__first, __last);
1432  ++__first;
1433  --__last;
1434  }
1435  }
1436 
1437  /**
1438  * @brief Reverse a sequence.
1439  * @ingroup mutating_algorithms
1440  * @param first A bidirectional iterator.
1441  * @param last A bidirectional iterator.
1442  * @return reverse() returns no value.
1443  *
1444  * Reverses the order of the elements in the range @p [first,last),
1445  * so that the first element becomes the last etc.
1446  * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1447  * swaps @p *(first+i) and @p *(last-(i+1))
1448  */
1449  template<typename _BidirectionalIterator>
1450  inline void
1451  reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1452  {
1453  // concept requirements
1454  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1455  _BidirectionalIterator>)
1456  __glibcxx_requires_valid_range(__first, __last);
1457  std::__reverse(__first, __last, std::__iterator_category(__first));
1458  }
1459 
1460  /**
1461  * @brief Copy a sequence, reversing its elements.
1462  * @ingroup mutating_algorithms
1463  * @param first A bidirectional iterator.
1464  * @param last A bidirectional iterator.
1465  * @param result An output iterator.
1466  * @return An iterator designating the end of the resulting sequence.
1467  *
1468  * Copies the elements in the range @p [first,last) to the range
1469  * @p [result,result+(last-first)) such that the order of the
1470  * elements is reversed.
1471  * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1472  * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1473  * The ranges @p [first,last) and @p [result,result+(last-first))
1474  * must not overlap.
1475  */
1476  template<typename _BidirectionalIterator, typename _OutputIterator>
1477  _OutputIterator
1478  reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1479  _OutputIterator __result)
1480  {
1481  // concept requirements
1482  __glibcxx_function_requires(_BidirectionalIteratorConcept<
1483  _BidirectionalIterator>)
1484  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1485  typename iterator_traits<_BidirectionalIterator>::value_type>)
1486  __glibcxx_requires_valid_range(__first, __last);
1487 
1488  while (__first != __last)
1489  {
1490  --__last;
1491  *__result = *__last;
1492  ++__result;
1493  }
1494  return __result;
1495  }
1496 
1497  /**
1498  * This is a helper function for the rotate algorithm specialized on RAIs.
1499  * It returns the greatest common divisor of two integer values.
1500  */
1501  template<typename _EuclideanRingElement>
1502  _EuclideanRingElement
1503  __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1504  {
1505  while (__n != 0)
1506  {
1507  _EuclideanRingElement __t = __m % __n;
1508  __m = __n;
1509  __n = __t;
1510  }
1511  return __m;
1512  }
1513 
1514  /// This is a helper function for the rotate algorithm.
1515  template<typename _ForwardIterator>
1516  void
1517  __rotate(_ForwardIterator __first,
1518  _ForwardIterator __middle,
1519  _ForwardIterator __last,
1521  {
1522  if (__first == __middle || __last == __middle)
1523  return;
1524 
1525  _ForwardIterator __first2 = __middle;
1526  do
1527  {
1528  std::iter_swap(__first, __first2);
1529  ++__first;
1530  ++__first2;
1531  if (__first == __middle)
1532  __middle = __first2;
1533  }
1534  while (__first2 != __last);
1535 
1536  __first2 = __middle;
1537 
1538  while (__first2 != __last)
1539  {
1540  std::iter_swap(__first, __first2);
1541  ++__first;
1542  ++__first2;
1543  if (__first == __middle)
1544  __middle = __first2;
1545  else if (__first2 == __last)
1546  __first2 = __middle;
1547  }
1548  }
1549 
1550  /// This is a helper function for the rotate algorithm.
1551  template<typename _BidirectionalIterator>
1552  void
1553  __rotate(_BidirectionalIterator __first,
1554  _BidirectionalIterator __middle,
1555  _BidirectionalIterator __last,
1557  {
1558  // concept requirements
1559  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1560  _BidirectionalIterator>)
1561 
1562  if (__first == __middle || __last == __middle)
1563  return;
1564 
1565  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1566  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1567 
1568  while (__first != __middle && __middle != __last)
1569  {
1570  std::iter_swap(__first, --__last);
1571  ++__first;
1572  }
1573 
1574  if (__first == __middle)
1575  std::__reverse(__middle, __last, bidirectional_iterator_tag());
1576  else
1577  std::__reverse(__first, __middle, bidirectional_iterator_tag());
1578  }
1579 
1580  /// This is a helper function for the rotate algorithm.
1581  template<typename _RandomAccessIterator>
1582  void
1583  __rotate(_RandomAccessIterator __first,
1584  _RandomAccessIterator __middle,
1585  _RandomAccessIterator __last,
1587  {
1588  // concept requirements
1589  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1590  _RandomAccessIterator>)
1591 
1592  if (__first == __middle || __last == __middle)
1593  return;
1594 
1595  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1596  _Distance;
1597  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1598  _ValueType;
1599 
1600  const _Distance __n = __last - __first;
1601  const _Distance __k = __middle - __first;
1602  const _Distance __l = __n - __k;
1603 
1604  if (__k == __l)
1605  {
1606  std::swap_ranges(__first, __middle, __middle);
1607  return;
1608  }
1609 
1610  const _Distance __d = std::__gcd(__n, __k);
1611 
1612  for (_Distance __i = 0; __i < __d; __i++)
1613  {
1614  _ValueType __tmp = _GLIBCXX_MOVE(*__first);
1615  _RandomAccessIterator __p = __first;
1616 
1617  if (__k < __l)
1618  {
1619  for (_Distance __j = 0; __j < __l / __d; __j++)
1620  {
1621  if (__p > __first + __l)
1622  {
1623  *__p = _GLIBCXX_MOVE(*(__p - __l));
1624  __p -= __l;
1625  }
1626 
1627  *__p = _GLIBCXX_MOVE(*(__p + __k));
1628  __p += __k;
1629  }
1630  }
1631  else
1632  {
1633  for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
1634  {
1635  if (__p < __last - __k)
1636  {
1637  *__p = _GLIBCXX_MOVE(*(__p + __k));
1638  __p += __k;
1639  }
1640  *__p = _GLIBCXX_MOVE(*(__p - __l));
1641  __p -= __l;
1642  }
1643  }
1644 
1645  *__p = _GLIBCXX_MOVE(__tmp);
1646  ++__first;
1647  }
1648  }
1649 
1650  /**
1651  * @brief Rotate the elements of a sequence.
1652  * @ingroup mutating_algorithms
1653  * @param first A forward iterator.
1654  * @param middle A forward iterator.
1655  * @param last A forward iterator.
1656  * @return Nothing.
1657  *
1658  * Rotates the elements of the range @p [first,last) by @p (middle-first)
1659  * positions so that the element at @p middle is moved to @p first, the
1660  * element at @p middle+1 is moved to @first+1 and so on for each element
1661  * in the range @p [first,last).
1662  *
1663  * This effectively swaps the ranges @p [first,middle) and
1664  * @p [middle,last).
1665  *
1666  * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1667  * each @p n in the range @p [0,last-first).
1668  */
1669  template<typename _ForwardIterator>
1670  inline void
1671  rotate(_ForwardIterator __first, _ForwardIterator __middle,
1672  _ForwardIterator __last)
1673  {
1674  // concept requirements
1675  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1676  _ForwardIterator>)
1677  __glibcxx_requires_valid_range(__first, __middle);
1678  __glibcxx_requires_valid_range(__middle, __last);
1679 
1680  typedef typename iterator_traits<_ForwardIterator>::iterator_category
1681  _IterType;
1682  std::__rotate(__first, __middle, __last, _IterType());
1683  }
1684 
1685  /**
1686  * @brief Copy a sequence, rotating its elements.
1687  * @ingroup mutating_algorithms
1688  * @param first A forward iterator.
1689  * @param middle A forward iterator.
1690  * @param last A forward iterator.
1691  * @param result An output iterator.
1692  * @return An iterator designating the end of the resulting sequence.
1693  *
1694  * Copies the elements of the range @p [first,last) to the range
1695  * beginning at @result, rotating the copied elements by @p (middle-first)
1696  * positions so that the element at @p middle is moved to @p result, the
1697  * element at @p middle+1 is moved to @result+1 and so on for each element
1698  * in the range @p [first,last).
1699  *
1700  * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1701  * each @p n in the range @p [0,last-first).
1702  */
1703  template<typename _ForwardIterator, typename _OutputIterator>
1704  _OutputIterator
1705  rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1706  _ForwardIterator __last, _OutputIterator __result)
1707  {
1708  // concept requirements
1709  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1710  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1711  typename iterator_traits<_ForwardIterator>::value_type>)
1712  __glibcxx_requires_valid_range(__first, __middle);
1713  __glibcxx_requires_valid_range(__middle, __last);
1714 
1715  return std::copy(__first, __middle,
1716  std::copy(__middle, __last, __result));
1717  }
1718 
1719  /// This is a helper function...
1720  template<typename _ForwardIterator, typename _Predicate>
1721  _ForwardIterator
1722  __partition(_ForwardIterator __first, _ForwardIterator __last,
1723  _Predicate __pred, forward_iterator_tag)
1724  {
1725  if (__first == __last)
1726  return __first;
1727 
1728  while (__pred(*__first))
1729  if (++__first == __last)
1730  return __first;
1731 
1732  _ForwardIterator __next = __first;
1733 
1734  while (++__next != __last)
1735  if (__pred(*__next))
1736  {
1737  std::iter_swap(__first, __next);
1738  ++__first;
1739  }
1740 
1741  return __first;
1742  }
1743 
1744  /// This is a helper function...
1745  template<typename _BidirectionalIterator, typename _Predicate>
1746  _BidirectionalIterator
1747  __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1748  _Predicate __pred, bidirectional_iterator_tag)
1749  {
1750  while (true)
1751  {
1752  while (true)
1753  if (__first == __last)
1754  return __first;
1755  else if (__pred(*__first))
1756  ++__first;
1757  else
1758  break;
1759  --__last;
1760  while (true)
1761  if (__first == __last)
1762  return __first;
1763  else if (!bool(__pred(*__last)))
1764  --__last;
1765  else
1766  break;
1767  std::iter_swap(__first, __last);
1768  ++__first;
1769  }
1770  }
1771 
1772  // partition
1773 
1774  /// This is a helper function...
1775  template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1776  _ForwardIterator
1777  __inplace_stable_partition(_ForwardIterator __first,
1778  _ForwardIterator __last,
1779  _Predicate __pred, _Distance __len)
1780  {
1781  if (__len == 1)
1782  return __pred(*__first) ? __last : __first;
1783  _ForwardIterator __middle = __first;
1784  std::advance(__middle, __len / 2);
1785  _ForwardIterator __begin = std::__inplace_stable_partition(__first,
1786  __middle,
1787  __pred,
1788  __len / 2);
1789  _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
1790  __pred,
1791  __len
1792  - __len / 2);
1793  std::rotate(__begin, __middle, __end);
1794  std::advance(__begin, std::distance(__middle, __end));
1795  return __begin;
1796  }
1797 
1798  /// This is a helper function...
1799  template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1800  typename _Distance>
1801  _ForwardIterator
1802  __stable_partition_adaptive(_ForwardIterator __first,
1803  _ForwardIterator __last,
1804  _Predicate __pred, _Distance __len,
1805  _Pointer __buffer,
1806  _Distance __buffer_size)
1807  {
1808  if (__len <= __buffer_size)
1809  {
1810  _ForwardIterator __result1 = __first;
1811  _Pointer __result2 = __buffer;
1812  for (; __first != __last; ++__first)
1813  if (__pred(*__first))
1814  {
1815  *__result1 = *__first;
1816  ++__result1;
1817  }
1818  else
1819  {
1820  *__result2 = *__first;
1821  ++__result2;
1822  }
1823  std::copy(__buffer, __result2, __result1);
1824  return __result1;
1825  }
1826  else
1827  {
1828  _ForwardIterator __middle = __first;
1829  std::advance(__middle, __len / 2);
1830  _ForwardIterator __begin =
1831  std::__stable_partition_adaptive(__first, __middle, __pred,
1832  __len / 2, __buffer,
1833  __buffer_size);
1834  _ForwardIterator __end =
1835  std::__stable_partition_adaptive(__middle, __last, __pred,
1836  __len - __len / 2,
1837  __buffer, __buffer_size);
1838  std::rotate(__begin, __middle, __end);
1839  std::advance(__begin, std::distance(__middle, __end));
1840  return __begin;
1841  }
1842  }
1843 
1844  /**
1845  * @brief Move elements for which a predicate is true to the beginning
1846  * of a sequence, preserving relative ordering.
1847  * @ingroup mutating_algorithms
1848  * @param first A forward iterator.
1849  * @param last A forward iterator.
1850  * @param pred A predicate functor.
1851  * @return An iterator @p middle such that @p pred(i) is true for each
1852  * iterator @p i in the range @p [first,middle) and false for each @p i
1853  * in the range @p [middle,last).
1854  *
1855  * Performs the same function as @p partition() with the additional
1856  * guarantee that the relative ordering of elements in each group is
1857  * preserved, so any two elements @p x and @p y in the range
1858  * @p [first,last) such that @p pred(x)==pred(y) will have the same
1859  * relative ordering after calling @p stable_partition().
1860  */
1861  template<typename _ForwardIterator, typename _Predicate>
1862  _ForwardIterator
1863  stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1864  _Predicate __pred)
1865  {
1866  // concept requirements
1867  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1868  _ForwardIterator>)
1869  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1870  typename iterator_traits<_ForwardIterator>::value_type>)
1871  __glibcxx_requires_valid_range(__first, __last);
1872 
1873  if (__first == __last)
1874  return __first;
1875  else
1876  {
1877  typedef typename iterator_traits<_ForwardIterator>::value_type
1878  _ValueType;
1879  typedef typename iterator_traits<_ForwardIterator>::difference_type
1880  _DistanceType;
1881 
1883  __last);
1884  if (__buf.size() > 0)
1885  return
1886  std::__stable_partition_adaptive(__first, __last, __pred,
1887  _DistanceType(__buf.requested_size()),
1888  __buf.begin(),
1889  _DistanceType(__buf.size()));
1890  else
1891  return
1892  std::__inplace_stable_partition(__first, __last, __pred,
1893  _DistanceType(__buf.requested_size()));
1894  }
1895  }
1896 
1897  /// This is a helper function for the sort routines.
1898  template<typename _RandomAccessIterator>
1899  void
1900  __heap_select(_RandomAccessIterator __first,
1901  _RandomAccessIterator __middle,
1902  _RandomAccessIterator __last)
1903  {
1904  std::make_heap(__first, __middle);
1905  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1906  if (*__i < *__first)
1907  std::__pop_heap(__first, __middle, __i);
1908  }
1909 
1910  /// This is a helper function for the sort routines.
1911  template<typename _RandomAccessIterator, typename _Compare>
1912  void
1913  __heap_select(_RandomAccessIterator __first,
1914  _RandomAccessIterator __middle,
1915  _RandomAccessIterator __last, _Compare __comp)
1916  {
1917  std::make_heap(__first, __middle, __comp);
1918  for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1919  if (__comp(*__i, *__first))
1920  std::__pop_heap(__first, __middle, __i, __comp);
1921  }
1922 
1923  // partial_sort
1924 
1925  /**
1926  * @brief Copy the smallest elements of a sequence.
1927  * @ingroup sorting_algorithms
1928  * @param first An iterator.
1929  * @param last Another iterator.
1930  * @param result_first A random-access iterator.
1931  * @param result_last Another random-access iterator.
1932  * @return An iterator indicating the end of the resulting sequence.
1933  *
1934  * Copies and sorts the smallest N values from the range @p [first,last)
1935  * to the range beginning at @p result_first, where the number of
1936  * elements to be copied, @p N, is the smaller of @p (last-first) and
1937  * @p (result_last-result_first).
1938  * After the sort if @p i and @j are iterators in the range
1939  * @p [result_first,result_first+N) such that @i precedes @j then
1940  * @p *j<*i is false.
1941  * The value returned is @p result_first+N.
1942  */
1943  template<typename _InputIterator, typename _RandomAccessIterator>
1944  _RandomAccessIterator
1945  partial_sort_copy(_InputIterator __first, _InputIterator __last,
1946  _RandomAccessIterator __result_first,
1947  _RandomAccessIterator __result_last)
1948  {
1949  typedef typename iterator_traits<_InputIterator>::value_type
1950  _InputValueType;
1951  typedef typename iterator_traits<_RandomAccessIterator>::value_type
1952  _OutputValueType;
1953  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1954  _DistanceType;
1955 
1956  // concept requirements
1957  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1958  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1959  _OutputValueType>)
1960  __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1961  _OutputValueType>)
1962  __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1963  __glibcxx_requires_valid_range(__first, __last);
1964  __glibcxx_requires_valid_range(__result_first, __result_last);
1965 
1966  if (__result_first == __result_last)
1967  return __result_last;
1968  _RandomAccessIterator __result_real_last = __result_first;
1969  while(__first != __last && __result_real_last != __result_last)
1970  {
1971  *__result_real_last = *__first;
1972  ++__result_real_last;
1973  ++__first;
1974  }
1975  std::make_heap(__result_first, __result_real_last);
1976  while (__first != __last)
1977  {
1978  if (*__first < *__result_first)
1979  std::__adjust_heap(__result_first, _DistanceType(0),
1980  _DistanceType(__result_real_last
1981  - __result_first),
1982  _InputValueType(*__first));
1983  ++__first;
1984  }
1985  std::sort_heap(__result_first, __result_real_last);
1986  return __result_real_last;
1987  }
1988 
1989  /**
1990  * @brief Copy the smallest elements of a sequence using a predicate for
1991  * comparison.
1992  * @ingroup sorting_algorithms
1993  * @param first An input iterator.
1994  * @param last Another input iterator.
1995  * @param result_first A random-access iterator.
1996  * @param result_last Another random-access iterator.
1997  * @param comp A comparison functor.
1998  * @return An iterator indicating the end of the resulting sequence.
1999  *
2000  * Copies and sorts the smallest N values from the range @p [first,last)
2001  * to the range beginning at @p result_first, where the number of
2002  * elements to be copied, @p N, is the smaller of @p (last-first) and
2003  * @p (result_last-result_first).
2004  * After the sort if @p i and @j are iterators in the range
2005  * @p [result_first,result_first+N) such that @i precedes @j then
2006  * @p comp(*j,*i) is false.
2007  * The value returned is @p result_first+N.
2008  */
2009  template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2010  _RandomAccessIterator
2011  partial_sort_copy(_InputIterator __first, _InputIterator __last,
2012  _RandomAccessIterator __result_first,
2013  _RandomAccessIterator __result_last,
2014  _Compare __comp)
2015  {
2016  typedef typename iterator_traits<_InputIterator>::value_type
2017  _InputValueType;
2018  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2019  _OutputValueType;
2020  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2021  _DistanceType;
2022 
2023  // concept requirements
2024  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2025  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2026  _RandomAccessIterator>)
2027  __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2028  _OutputValueType>)
2029  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2030  _InputValueType, _OutputValueType>)
2031  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2032  _OutputValueType, _OutputValueType>)
2033  __glibcxx_requires_valid_range(__first, __last);
2034  __glibcxx_requires_valid_range(__result_first, __result_last);
2035 
2036  if (__result_first == __result_last)
2037  return __result_last;
2038  _RandomAccessIterator __result_real_last = __result_first;
2039  while(__first != __last && __result_real_last != __result_last)
2040  {
2041  *__result_real_last = *__first;
2042  ++__result_real_last;
2043  ++__first;
2044  }
2045  std::make_heap(__result_first, __result_real_last, __comp);
2046  while (__first != __last)
2047  {
2048  if (__comp(*__first, *__result_first))
2049  std::__adjust_heap(__result_first, _DistanceType(0),
2050  _DistanceType(__result_real_last
2051  - __result_first),
2052  _InputValueType(*__first),
2053  __comp);
2054  ++__first;
2055  }
2056  std::sort_heap(__result_first, __result_real_last, __comp);
2057  return __result_real_last;
2058  }
2059 
2060  /// This is a helper function for the sort routine.
2061  template<typename _RandomAccessIterator, typename _Tp>
2062  void
2063  __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
2064  {
2065  _RandomAccessIterator __next = __last;
2066  --__next;
2067  while (__val < *__next)
2068  {
2069  *__last = *__next;
2070  __last = __next;
2071  --__next;
2072  }
2073  *__last = __val;
2074  }
2075 
2076  /// This is a helper function for the sort routine.
2077  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2078  void
2079  __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
2080  _Compare __comp)
2081  {
2082  _RandomAccessIterator __next = __last;
2083  --__next;
2084  while (__comp(__val, *__next))
2085  {
2086  *__last = *__next;
2087  __last = __next;
2088  --__next;
2089  }
2090  *__last = __val;
2091  }
2092 
2093  /// This is a helper function for the sort routine.
2094  template<typename _RandomAccessIterator>
2095  void
2096  __insertion_sort(_RandomAccessIterator __first,
2097  _RandomAccessIterator __last)
2098  {
2099  if (__first == __last)
2100  return;
2101 
2102  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2103  {
2104  typename iterator_traits<_RandomAccessIterator>::value_type
2105  __val = *__i;
2106  if (__val < *__first)
2107  {
2108  std::copy_backward(__first, __i, __i + 1);
2109  *__first = __val;
2110  }
2111  else
2112  std::__unguarded_linear_insert(__i, __val);
2113  }
2114  }
2115 
2116  /// This is a helper function for the sort routine.
2117  template<typename _RandomAccessIterator, typename _Compare>
2118  void
2119  __insertion_sort(_RandomAccessIterator __first,
2120  _RandomAccessIterator __last, _Compare __comp)
2121  {
2122  if (__first == __last) return;
2123 
2124  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2125  {
2126  typename iterator_traits<_RandomAccessIterator>::value_type
2127  __val = *__i;
2128  if (__comp(__val, *__first))
2129  {
2130  std::copy_backward(__first, __i, __i + 1);
2131  *__first = __val;
2132  }
2133  else
2134  std::__unguarded_linear_insert(__i, __val, __comp);
2135  }
2136  }
2137 
2138  /// This is a helper function for the sort routine.
2139  template<typename _RandomAccessIterator>
2140  inline void
2141  __unguarded_insertion_sort(_RandomAccessIterator __first,
2142  _RandomAccessIterator __last)
2143  {
2144  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2145  _ValueType;
2146 
2147  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2148  std::__unguarded_linear_insert(__i, _ValueType(*__i));
2149  }
2150 
2151  /// This is a helper function for the sort routine.
2152  template<typename _RandomAccessIterator, typename _Compare>
2153  inline void
2154  __unguarded_insertion_sort(_RandomAccessIterator __first,
2155  _RandomAccessIterator __last, _Compare __comp)
2156  {
2157  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2158  _ValueType;
2159 
2160  for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2161  std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
2162  }
2163 
2164  /**
2165  * @doctodo
2166  * This controls some aspect of the sort routines.
2167  */
2168  enum { _S_threshold = 16 };
2169 
2170  /// This is a helper function for the sort routine.
2171  template<typename _RandomAccessIterator>
2172  void
2173  __final_insertion_sort(_RandomAccessIterator __first,
2174  _RandomAccessIterator __last)
2175  {
2176  if (__last - __first > int(_S_threshold))
2177  {
2178  std::__insertion_sort(__first, __first + int(_S_threshold));
2179  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2180  }
2181  else
2182  std::__insertion_sort(__first, __last);
2183  }
2184 
2185  /// This is a helper function for the sort routine.
2186  template<typename _RandomAccessIterator, typename _Compare>
2187  void
2188  __final_insertion_sort(_RandomAccessIterator __first,
2189  _RandomAccessIterator __last, _Compare __comp)
2190  {
2191  if (__last - __first > int(_S_threshold))
2192  {
2193  std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2194  std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2195  __comp);
2196  }
2197  else
2198  std::__insertion_sort(__first, __last, __comp);
2199  }
2200 
2201  /// This is a helper function...
2202  template<typename _RandomAccessIterator, typename _Tp>
2203  _RandomAccessIterator
2204  __unguarded_partition(_RandomAccessIterator __first,
2205  _RandomAccessIterator __last, _Tp __pivot)
2206  {
2207  while (true)
2208  {
2209  while (*__first < __pivot)
2210  ++__first;
2211  --__last;
2212  while (__pivot < *__last)
2213  --__last;
2214  if (!(__first < __last))
2215  return __first;
2216  std::iter_swap(__first, __last);
2217  ++__first;
2218  }
2219  }
2220 
2221  /// This is a helper function...
2222  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2223  _RandomAccessIterator
2224  __unguarded_partition(_RandomAccessIterator __first,
2225  _RandomAccessIterator __last,
2226  _Tp __pivot, _Compare __comp)
2227  {
2228  while (true)
2229  {
2230  while (__comp(*__first, __pivot))
2231  ++__first;
2232  --__last;
2233  while (__comp(__pivot, *__last))
2234  --__last;
2235  if (!(__first < __last))
2236  return __first;
2237  std::iter_swap(__first, __last);
2238  ++__first;
2239  }
2240  }
2241 
2242  /// This is a helper function for the sort routine.
2243  template<typename _RandomAccessIterator, typename _Size>
2244  void
2245  __introsort_loop(_RandomAccessIterator __first,
2246  _RandomAccessIterator __last,
2247  _Size __depth_limit)
2248  {
2249  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2250  _ValueType;
2251 
2252  while (__last - __first > int(_S_threshold))
2253  {
2254  if (__depth_limit == 0)
2255  {
2256  _GLIBCXX_STD_P::partial_sort(__first, __last, __last);
2257  return;
2258  }
2259  --__depth_limit;
2260  _RandomAccessIterator __cut =
2261  std::__unguarded_partition(__first, __last,
2262  _ValueType(std::__median(*__first,
2263  *(__first
2264  + (__last
2265  - __first)
2266  / 2),
2267  *(__last
2268  - 1))));
2269  std::__introsort_loop(__cut, __last, __depth_limit);
2270  __last = __cut;
2271  }
2272  }
2273 
2274  /// This is a helper function for the sort routine.
2275  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2276  void
2277  __introsort_loop(_RandomAccessIterator __first,
2278  _RandomAccessIterator __last,
2279  _Size __depth_limit, _Compare __comp)
2280  {
2281  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2282  _ValueType;
2283 
2284  while (__last - __first > int(_S_threshold))
2285  {
2286  if (__depth_limit == 0)
2287  {
2288  _GLIBCXX_STD_P::partial_sort(__first, __last, __last, __comp);
2289  return;
2290  }
2291  --__depth_limit;
2292  _RandomAccessIterator __cut =
2293  std::__unguarded_partition(__first, __last,
2294  _ValueType(std::__median(*__first,
2295  *(__first
2296  + (__last
2297  - __first)
2298  / 2),
2299  *(__last - 1),
2300  __comp)),
2301  __comp);
2302  std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2303  __last = __cut;
2304  }
2305  }
2306 
2307  /// This is a helper function for the sort routines. Precondition: __n > 0.
2308  template<typename _Size>
2309  inline _Size
2310  __lg(_Size __n)
2311  {
2312  _Size __k;
2313  for (__k = 0; __n != 0; __n >>= 1)
2314  ++__k;
2315  return __k - 1;
2316  }
2317 
2318  inline int
2319  __lg(int __n)
2320  { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
2321 
2322  inline long
2323  __lg(long __n)
2324  { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
2325 
2326  inline long long
2327  __lg(long long __n)
2328  { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
2329 
2330  // sort
2331 
2332  template<typename _RandomAccessIterator, typename _Size>
2333  void
2334  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2335  _RandomAccessIterator __last, _Size __depth_limit)
2336  {
2337  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2338  _ValueType;
2339 
2340  while (__last - __first > 3)
2341  {
2342  if (__depth_limit == 0)
2343  {
2344  std::__heap_select(__first, __nth + 1, __last);
2345 
2346  // Place the nth largest element in its final position.
2347  std::iter_swap(__first, __nth);
2348  return;
2349  }
2350  --__depth_limit;
2351  _RandomAccessIterator __cut =
2352  std::__unguarded_partition(__first, __last,
2353  _ValueType(std::__median(*__first,
2354  *(__first
2355  + (__last
2356  - __first)
2357  / 2),
2358  *(__last
2359  - 1))));
2360  if (__cut <= __nth)
2361  __first = __cut;
2362  else
2363  __last = __cut;
2364  }
2365  std::__insertion_sort(__first, __last);
2366  }
2367 
2368  template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2369  void
2370  __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2371  _RandomAccessIterator __last, _Size __depth_limit,
2372  _Compare __comp)
2373  {
2374  typedef typename iterator_traits<_RandomAccessIterator>::value_type
2375  _ValueType;
2376 
2377  while (__last - __first > 3)
2378  {
2379  if (__depth_limit == 0)
2380  {
2381  std::__heap_select(__first, __nth + 1, __last, __comp);
2382  // Place the nth largest element in its final position.
2383  std::iter_swap(__first, __nth);
2384  return;
2385  }
2386  --__depth_limit;
2387  _RandomAccessIterator __cut =
2388  std::__unguarded_partition(__first, __last,
2389  _ValueType(std::__median(*__first,
2390  *(__first
2391  + (__last
2392  - __first)
2393  / 2),
2394  *(__last - 1),
2395  __comp)),
2396  __comp);
2397  if (__cut <= __nth)
2398  __first = __cut;
2399  else
2400  __last = __cut;
2401  }
2402  std::__insertion_sort(__first, __last, __comp);
2403  }
2404 
2405  // nth_element
2406 
2407  /**
2408  * @brief Finds the first position in which @a val could be inserted
2409  * without changing the ordering.
2410  * @param first An iterator.
2411  * @param last Another iterator.
2412  * @param val The search term.
2413  * @return An iterator pointing to the first element "not less
2414  * than" @a val, or end() if every element is less than
2415  * @a val.
2416  * @ingroup binary_search_algorithms
2417  */
2418  template<typename _ForwardIterator, typename _Tp>
2419  _ForwardIterator
2420  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2421  const _Tp& __val)
2422  {
2423  typedef typename iterator_traits<_ForwardIterator>::value_type
2424  _ValueType;
2425  typedef typename iterator_traits<_ForwardIterator>::difference_type
2426  _DistanceType;
2427 
2428  // concept requirements
2429  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2430  __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2431  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2432 
2433  _DistanceType __len = std::distance(__first, __last);
2434  _DistanceType __half;
2435  _ForwardIterator __middle;
2436 
2437  while (__len > 0)
2438  {
2439  __half = __len >> 1;
2440  __middle = __first;
2441  std::advance(__middle, __half);
2442  if (*__middle < __val)
2443  {
2444  __first = __middle;
2445  ++__first;
2446  __len = __len - __half - 1;
2447  }
2448  else
2449  __len = __half;
2450  }
2451  return __first;
2452  }
2453 
2454  /**
2455  * @brief Finds the first position in which @a val could be inserted
2456  * without changing the ordering.
2457  * @ingroup binary_search_algorithms
2458  * @param first An iterator.
2459  * @param last Another iterator.
2460  * @param val The search term.
2461  * @param comp A functor to use for comparisons.
2462  * @return An iterator pointing to the first element "not less than" @a val,
2463  * or end() if every element is less than @a val.
2464  * @ingroup binary_search_algorithms
2465  *
2466  * The comparison function should have the same effects on ordering as
2467  * the function used for the initial sort.
2468  */
2469  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2470  _ForwardIterator
2471  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2472  const _Tp& __val, _Compare __comp)
2473  {
2474  typedef typename iterator_traits<_ForwardIterator>::value_type
2475  _ValueType;
2476  typedef typename iterator_traits<_ForwardIterator>::difference_type
2477  _DistanceType;
2478 
2479  // concept requirements
2480  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2481  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2482  _ValueType, _Tp>)
2483  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2484  __val, __comp);
2485 
2486  _DistanceType __len = std::distance(__first, __last);
2487  _DistanceType __half;
2488  _ForwardIterator __middle;
2489 
2490  while (__len > 0)
2491  {
2492  __half = __len >> 1;
2493  __middle = __first;
2494  std::advance(__middle, __half);
2495  if (__comp(*__middle, __val))
2496  {
2497  __first = __middle;
2498  ++__first;
2499  __len = __len - __half - 1;
2500  }
2501  else
2502  __len = __half;
2503  }
2504  return __first;
2505  }
2506 
2507  /**
2508  * @brief Finds the last position in which @a val could be inserted
2509  * without changing the ordering.
2510  * @ingroup binary_search_algorithms
2511  * @param first An iterator.
2512  * @param last Another iterator.
2513  * @param val The search term.
2514  * @return An iterator pointing to the first element greater than @a val,
2515  * or end() if no elements are greater than @a val.
2516  * @ingroup binary_search_algorithms
2517  */
2518  template<typename _ForwardIterator, typename _Tp>
2519  _ForwardIterator
2520  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2521  const _Tp& __val)
2522  {
2523  typedef typename iterator_traits<_ForwardIterator>::value_type
2524  _ValueType;
2525  typedef typename iterator_traits<_ForwardIterator>::difference_type
2526  _DistanceType;
2527 
2528  // concept requirements
2529  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2530  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2531  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2532 
2533  _DistanceType __len = std::distance(__first, __last);
2534  _DistanceType __half;
2535  _ForwardIterator __middle;
2536 
2537  while (__len > 0)
2538  {
2539  __half = __len >> 1;
2540  __middle = __first;
2541  std::advance(__middle, __half);
2542  if (__val < *__middle)
2543  __len = __half;
2544  else
2545  {
2546  __first = __middle;
2547  ++__first;
2548  __len = __len - __half - 1;
2549  }
2550  }
2551  return __first;
2552  }
2553 
2554  /**
2555  * @brief Finds the last position in which @a val could be inserted
2556  * without changing the ordering.
2557  * @ingroup binary_search_algorithms
2558  * @param first An iterator.
2559  * @param last Another iterator.
2560  * @param val The search term.
2561  * @param comp A functor to use for comparisons.
2562  * @return An iterator pointing to the first element greater than @a val,
2563  * or end() if no elements are greater than @a val.
2564  * @ingroup binary_search_algorithms
2565  *
2566  * The comparison function should have the same effects on ordering as
2567  * the function used for the initial sort.
2568  */
2569  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2570  _ForwardIterator
2571  upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2572  const _Tp& __val, _Compare __comp)
2573  {
2574  typedef typename iterator_traits<_ForwardIterator>::value_type
2575  _ValueType;
2576  typedef typename iterator_traits<_ForwardIterator>::difference_type
2577  _DistanceType;
2578 
2579  // concept requirements
2580  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2581  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2582  _Tp, _ValueType>)
2583  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2584  __val, __comp);
2585 
2586  _DistanceType __len = std::distance(__first, __last);
2587  _DistanceType __half;
2588  _ForwardIterator __middle;
2589 
2590  while (__len > 0)
2591  {
2592  __half = __len >> 1;
2593  __middle = __first;
2594  std::advance(__middle, __half);
2595  if (__comp(__val, *__middle))
2596  __len = __half;
2597  else
2598  {
2599  __first = __middle;
2600  ++__first;
2601  __len = __len - __half - 1;
2602  }
2603  }
2604  return __first;
2605  }
2606 
2607  /**
2608  * @brief Finds the largest subrange in which @a val could be inserted
2609  * at any place in it without changing the ordering.
2610  * @ingroup binary_search_algorithms
2611  * @param first An iterator.
2612  * @param last Another iterator.
2613  * @param val The search term.
2614  * @return An pair of iterators defining the subrange.
2615  * @ingroup binary_search_algorithms
2616  *
2617  * This is equivalent to
2618  * @code
2619  * std::make_pair(lower_bound(first, last, val),
2620  * upper_bound(first, last, val))
2621  * @endcode
2622  * but does not actually call those functions.
2623  */
2624  template<typename _ForwardIterator, typename _Tp>
2625  pair<_ForwardIterator, _ForwardIterator>
2626  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2627  const _Tp& __val)
2628  {
2629  typedef typename iterator_traits<_ForwardIterator>::value_type
2630  _ValueType;
2631  typedef typename iterator_traits<_ForwardIterator>::difference_type
2632  _DistanceType;
2633 
2634  // concept requirements
2635  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2636  __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2637  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2638  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2639  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2640 
2641  _DistanceType __len = std::distance(__first, __last);
2642  _DistanceType __half;
2643  _ForwardIterator __middle, __left, __right;
2644 
2645  while (__len > 0)
2646  {
2647  __half = __len >> 1;
2648  __middle = __first;
2649  std::advance(__middle, __half);
2650  if (*__middle < __val)
2651  {
2652  __first = __middle;
2653  ++__first;
2654  __len = __len - __half - 1;
2655  }
2656  else if (__val < *__middle)
2657  __len = __half;
2658  else
2659  {
2660  __left = std::lower_bound(__first, __middle, __val);
2661  std::advance(__first, __len);
2662  __right = std::upper_bound(++__middle, __first, __val);
2663  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2664  }
2665  }
2666  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2667  }
2668 
2669  /**
2670  * @brief Finds the largest subrange in which @a val could be inserted
2671  * at any place in it without changing the ordering.
2672  * @param first An iterator.
2673  * @param last Another iterator.
2674  * @param val The search term.
2675  * @param comp A functor to use for comparisons.
2676  * @return An pair of iterators defining the subrange.
2677  * @ingroup binary_search_algorithms
2678  *
2679  * This is equivalent to
2680  * @code
2681  * std::make_pair(lower_bound(first, last, val, comp),
2682  * upper_bound(first, last, val, comp))
2683  * @endcode
2684  * but does not actually call those functions.
2685  */
2686  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2687  pair<_ForwardIterator, _ForwardIterator>
2688  equal_range(_ForwardIterator __first, _ForwardIterator __last,
2689  const _Tp& __val,
2690  _Compare __comp)
2691  {
2692  typedef typename iterator_traits<_ForwardIterator>::value_type
2693  _ValueType;
2694  typedef typename iterator_traits<_ForwardIterator>::difference_type
2695  _DistanceType;
2696 
2697  // concept requirements
2698  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2699  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2700  _ValueType, _Tp>)
2701  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2702  _Tp, _ValueType>)
2703  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2704  __val, __comp);
2705  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2706  __val, __comp);
2707 
2708  _DistanceType __len = std::distance(__first, __last);
2709  _DistanceType __half;
2710  _ForwardIterator __middle, __left, __right;
2711 
2712  while (__len > 0)
2713  {
2714  __half = __len >> 1;
2715  __middle = __first;
2716  std::advance(__middle, __half);
2717  if (__comp(*__middle, __val))
2718  {
2719  __first = __middle;
2720  ++__first;
2721  __len = __len - __half - 1;
2722  }
2723  else if (__comp(__val, *__middle))
2724  __len = __half;
2725  else
2726  {
2727  __left = std::lower_bound(__first, __middle, __val, __comp);
2728  std::advance(__first, __len);
2729  __right = std::upper_bound(++__middle, __first, __val, __comp);
2730  return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2731  }
2732  }
2733  return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2734  }
2735 
2736  /**
2737  * @brief Determines whether an element exists in a range.
2738  * @ingroup binary_search_algorithms
2739  * @param first An iterator.
2740  * @param last Another iterator.
2741  * @param val The search term.
2742  * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2743  *
2744  * Note that this does not actually return an iterator to @a val. For
2745  * that, use std::find or a container's specialized find member functions.
2746  */
2747  template<typename _ForwardIterator, typename _Tp>
2748  bool
2749  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2750  const _Tp& __val)
2751  {
2752  typedef typename iterator_traits<_ForwardIterator>::value_type
2753  _ValueType;
2754 
2755  // concept requirements
2756  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2757  __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2758  __glibcxx_requires_partitioned_lower(__first, __last, __val);
2759  __glibcxx_requires_partitioned_upper(__first, __last, __val);
2760 
2761  _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2762  return __i != __last && !(__val < *__i);
2763  }
2764 
2765  /**
2766  * @brief Determines whether an element exists in a range.
2767  * @ingroup binary_search_algorithms
2768  * @param first An iterator.
2769  * @param last Another iterator.
2770  * @param val The search term.
2771  * @param comp A functor to use for comparisons.
2772  * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2773  *
2774  * Note that this does not actually return an iterator to @a val. For
2775  * that, use std::find or a container's specialized find member functions.
2776  *
2777  * The comparison function should have the same effects on ordering as
2778  * the function used for the initial sort.
2779  */
2780  template<typename _ForwardIterator, typename _Tp, typename _Compare>
2781  bool
2782  binary_search(_ForwardIterator __first, _ForwardIterator __last,
2783  const _Tp& __val, _Compare __comp)
2784  {
2785  typedef typename iterator_traits<_ForwardIterator>::value_type
2786  _ValueType;
2787 
2788  // concept requirements
2789  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2790  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2791  _Tp, _ValueType>)
2792  __glibcxx_requires_partitioned_lower_pred(__first, __last,
2793  __val, __comp);
2794  __glibcxx_requires_partitioned_upper_pred(__first, __last,
2795  __val, __comp);
2796 
2797  _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2798  return __i != __last && !bool(__comp(__val, *__i));
2799  }
2800 
2801  // merge
2802 
2803  /// This is a helper function for the merge routines.
2804  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2805  typename _BidirectionalIterator3>
2806  _BidirectionalIterator3
2807  __merge_backward(_BidirectionalIterator1 __first1,
2808  _BidirectionalIterator1 __last1,
2809  _BidirectionalIterator2 __first2,
2810  _BidirectionalIterator2 __last2,
2811  _BidirectionalIterator3 __result)
2812  {
2813  if (__first1 == __last1)
2814  return std::copy_backward(__first2, __last2, __result);
2815  if (__first2 == __last2)
2816  return std::copy_backward(__first1, __last1, __result);
2817  --__last1;
2818  --__last2;
2819  while (true)
2820  {
2821  if (*__last2 < *__last1)
2822  {
2823  *--__result = *__last1;
2824  if (__first1 == __last1)
2825  return std::copy_backward(__first2, ++__last2, __result);
2826  --__last1;
2827  }
2828  else
2829  {
2830  *--__result = *__last2;
2831  if (__first2 == __last2)
2832  return std::copy_backward(__first1, ++__last1, __result);
2833  --__last2;
2834  }
2835  }
2836  }
2837 
2838  /// This is a helper function for the merge routines.
2839  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2840  typename _BidirectionalIterator3, typename _Compare>
2841  _BidirectionalIterator3
2842  __merge_backward(_BidirectionalIterator1 __first1,
2843  _BidirectionalIterator1 __last1,
2844  _BidirectionalIterator2 __first2,
2845  _BidirectionalIterator2 __last2,
2846  _BidirectionalIterator3 __result,
2847  _Compare __comp)
2848  {
2849  if (__first1 == __last1)
2850  return std::copy_backward(__first2, __last2, __result);
2851  if (__first2 == __last2)
2852  return std::copy_backward(__first1, __last1, __result);
2853  --__last1;
2854  --__last2;
2855  while (true)
2856  {
2857  if (__comp(*__last2, *__last1))
2858  {
2859  *--__result = *__last1;
2860  if (__first1 == __last1)
2861  return std::copy_backward(__first2, ++__last2, __result);
2862  --__last1;
2863  }
2864  else
2865  {
2866  *--__result = *__last2;
2867  if (__first2 == __last2)
2868  return std::copy_backward(__first1, ++__last1, __result);
2869  --__last2;
2870  }
2871  }
2872  }
2873 
2874  /// This is a helper function for the merge routines.
2875  template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2876  typename _Distance>
2877  _BidirectionalIterator1
2878  __rotate_adaptive(_BidirectionalIterator1 __first,
2879  _BidirectionalIterator1 __middle,
2880  _BidirectionalIterator1 __last,
2881  _Distance __len1, _Distance __len2,
2882  _BidirectionalIterator2 __buffer,
2883  _Distance __buffer_size)
2884  {
2885  _BidirectionalIterator2 __buffer_end;
2886  if (__len1 > __len2 && __len2 <= __buffer_size)
2887  {
2888  __buffer_end = std::copy(__middle, __last, __buffer);
2889  std::copy_backward(__first, __middle, __last);
2890  return std::copy(__buffer, __buffer_end, __first);
2891  }
2892  else if (__len1 <= __buffer_size)
2893  {
2894  __buffer_end = std::copy(__first, __middle, __buffer);
2895  std::copy(__middle, __last, __first);
2896  return std::copy_backward(__buffer, __buffer_end, __last);
2897  }
2898  else
2899  {
2900  std::rotate(__first, __middle, __last);
2901  std::advance(__first, std::distance(__middle, __last));
2902  return __first;
2903  }
2904  }
2905 
2906  /// This is a helper function for the merge routines.
2907  template<typename _BidirectionalIterator, typename _Distance,
2908  typename _Pointer>
2909  void
2910  __merge_adaptive(_BidirectionalIterator __first,
2911  _BidirectionalIterator __middle,
2912  _BidirectionalIterator __last,
2913  _Distance __len1, _Distance __len2,
2914  _Pointer __buffer, _Distance __buffer_size)
2915  {
2916  if (__len1 <= __len2 && __len1 <= __buffer_size)
2917  {
2918  _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
2919  _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last,
2920  __first);
2921  }
2922  else if (__len2 <= __buffer_size)
2923  {
2924  _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
2925  std::__merge_backward(__first, __middle, __buffer,
2926  __buffer_end, __last);
2927  }
2928  else
2929  {
2930  _BidirectionalIterator __first_cut = __first;
2931  _BidirectionalIterator __second_cut = __middle;
2932  _Distance __len11 = 0;
2933  _Distance __len22 = 0;
2934  if (__len1 > __len2)
2935  {
2936  __len11 = __len1 / 2;
2937  std::advance(__first_cut, __len11);
2938  __second_cut = std::lower_bound(__middle, __last,
2939  *__first_cut);
2940  __len22 = std::distance(__middle, __second_cut);
2941  }
2942  else
2943  {
2944  __len22 = __len2 / 2;
2945  std::advance(__second_cut, __len22);
2946  __first_cut = std::upper_bound(__first, __middle,
2947  *__second_cut);
2948  __len11 = std::distance(__first, __first_cut);
2949  }
2950  _BidirectionalIterator __new_middle =
2951  std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2952  __len1 - __len11, __len22, __buffer,
2953  __buffer_size);
2954  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2955  __len22, __buffer, __buffer_size);
2956  std::__merge_adaptive(__new_middle, __second_cut, __last,
2957  __len1 - __len11,
2958  __len2 - __len22, __buffer, __buffer_size);
2959  }
2960  }
2961 
2962  /// This is a helper function for the merge routines.
2963  template<typename _BidirectionalIterator, typename _Distance,
2964  typename _Pointer, typename _Compare>
2965  void
2966  __merge_adaptive(_BidirectionalIterator __first,
2967  _BidirectionalIterator __middle,
2968  _BidirectionalIterator __last,
2969  _Distance __len1, _Distance __len2,
2970  _Pointer __buffer, _Distance __buffer_size,
2971  _Compare __comp)
2972  {
2973  if (__len1 <= __len2 && __len1 <= __buffer_size)
2974  {
2975  _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
2976  _GLIBCXX_STD_P::merge(__buffer, __buffer_end, __middle, __last,
2977  __first, __comp);
2978  }
2979  else if (__len2 <= __buffer_size)
2980  {
2981  _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
2982  std::__merge_backward(__first, __middle, __buffer, __buffer_end,
2983  __last, __comp);
2984  }
2985  else
2986  {
2987  _BidirectionalIterator __first_cut = __first;
2988  _BidirectionalIterator __second_cut = __middle;
2989  _Distance __len11 = 0;
2990  _Distance __len22 = 0;
2991  if (__len1 > __len2)
2992  {
2993  __len11 = __len1 / 2;
2994  std::advance(__first_cut, __len11);
2995  __second_cut = std::lower_bound(__middle, __last, *__first_cut,
2996  __comp);
2997  __len22 = std::distance(__middle, __second_cut);
2998  }
2999  else
3000  {
3001  __len22 = __len2 / 2;
3002  std::advance(__second_cut, __len22);
3003  __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3004  __comp);
3005  __len11 = std::distance(__first, __first_cut);
3006  }
3007  _BidirectionalIterator __new_middle =
3008  std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3009  __len1 - __len11, __len22, __buffer,
3010  __buffer_size);
3011  std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3012  __len22, __buffer, __buffer_size, __comp);
3013  std::__merge_adaptive(__new_middle, __second_cut, __last,
3014  __len1 - __len11,
3015  __len2 - __len22, __buffer,
3016  __buffer_size, __comp);
3017  }
3018  }
3019 
3020  /// This is a helper function for the merge routines.
3021  template<typename _BidirectionalIterator, typename _Distance>
3022  void
3023  __merge_without_buffer(_BidirectionalIterator __first,
3024  _BidirectionalIterator __middle,
3025  _BidirectionalIterator __last,
3026  _Distance __len1, _Distance __len2)
3027  {
3028  if (__len1 == 0 || __len2 == 0)
3029  return;
3030  if (__len1 + __len2 == 2)
3031  {
3032  if (*__middle < *__first)
3033  std::iter_swap(__first, __middle);
3034  return;
3035  }
3036  _BidirectionalIterator __first_cut = __first;
3037  _BidirectionalIterator __second_cut = __middle;
3038  _Distance __len11 = 0;
3039  _Distance __len22 = 0;
3040  if (__len1 > __len2)
3041  {
3042  __len11 = __len1 / 2;
3043  std::advance(__first_cut, __len11);
3044  __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3045  __len22 = std::distance(__middle, __second_cut);
3046  }
3047  else
3048  {
3049  __len22 = __len2 / 2;
3050  std::advance(__second_cut, __len22);
3051  __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3052  __len11 = std::distance(__first, __first_cut);
3053  }
3054  std::rotate(__first_cut, __middle, __second_cut);
3055  _BidirectionalIterator __new_middle = __first_cut;
3056  std::advance(__new_middle, std::distance(__middle, __second_cut));
3057  std::__merge_without_buffer(__first, __first_cut, __new_middle,
3058  __len11, __len22);
3059  std::__merge_without_buffer(__new_middle, __second_cut, __last,
3060  __len1 - __len11, __len2 - __len22);
3061  }
3062 
3063  /// This is a helper function for the merge routines.
3064  template<typename _BidirectionalIterator, typename _Distance,
3065  typename _Compare>
3066  void
3067  __merge_without_buffer(_BidirectionalIterator __first,
3068  _BidirectionalIterator __middle,
3069  _BidirectionalIterator __last,
3070  _Distance __len1, _Distance __len2,
3071  _Compare __comp)
3072  {
3073  if (__len1 == 0 || __len2 == 0)
3074  return;
3075  if (__len1 + __len2 == 2)
3076  {
3077  if (__comp(*__middle, *__first))
3078  std::iter_swap(__first, __middle);
3079  return;
3080  }
3081  _BidirectionalIterator __first_cut = __first;
3082  _BidirectionalIterator __second_cut = __middle;
3083  _Distance __len11 = 0;
3084  _Distance __len22 = 0;
3085  if (__len1 > __len2)
3086  {
3087  __len11 = __len1 / 2;
3088  std::advance(__first_cut, __len11);
3089  __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3090  __comp);
3091  __len22 = std::distance(__middle, __second_cut);
3092  }
3093  else
3094  {
3095  __len22 = __len2 / 2;
3096  std::advance(__second_cut, __len22);
3097  __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3098  __comp);
3099  __len11 = std::distance(__first, __first_cut);
3100  }
3101  std::rotate(__first_cut, __middle, __second_cut);
3102  _BidirectionalIterator __new_middle = __first_cut;
3103  std::advance(__new_middle, std::distance(__middle, __second_cut));
3104  std::__merge_without_buffer(__first, __first_cut, __new_middle,
3105  __len11, __len22, __comp);
3106  std::__merge_without_buffer(__new_middle, __second_cut, __last,
3107  __len1 - __len11, __len2 - __len22, __comp);
3108  }
3109 
3110  /**
3111  * @brief Merges two sorted ranges in place.
3112  * @ingroup sorting_algorithms
3113  * @param first An iterator.
3114  * @param middle Another iterator.
3115  * @param last Another iterator.
3116  * @return Nothing.
3117  *
3118  * Merges two sorted and consecutive ranges, [first,middle) and
3119  * [middle,last), and puts the result in [first,last). The output will
3120  * be sorted. The sort is @e stable, that is, for equivalent
3121  * elements in the two ranges, elements from the first range will always
3122  * come before elements from the second.
3123  *
3124  * If enough additional memory is available, this takes (last-first)-1
3125  * comparisons. Otherwise an NlogN algorithm is used, where N is
3126  * distance(first,last).
3127  */
3128  template<typename _BidirectionalIterator>
3129  void
3130  inplace_merge(_BidirectionalIterator __first,
3131  _BidirectionalIterator __middle,
3132  _BidirectionalIterator __last)
3133  {
3134  typedef typename iterator_traits<_BidirectionalIterator>::value_type
3135  _ValueType;
3136  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3137  _DistanceType;
3138 
3139  // concept requirements
3140  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3141  _BidirectionalIterator>)
3142  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3143  __glibcxx_requires_sorted(__first, __middle);
3144  __glibcxx_requires_sorted(__middle, __last);
3145 
3146  if (__first == __middle || __middle == __last)
3147  return;
3148 
3149  _DistanceType __len1 = std::distance(__first, __middle);
3150  _DistanceType __len2 = std::distance(__middle, __last);
3151 
3153  __last);
3154  if (__buf.begin() == 0)
3155  std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3156  else
3157  std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3158  __buf.begin(), _DistanceType(__buf.size()));
3159  }
3160 
3161  /**
3162  * @brief Merges two sorted ranges in place.
3163  * @ingroup sorting_algorithms
3164  * @param first An iterator.
3165  * @param middle Another iterator.
3166  * @param last Another iterator.
3167  * @param comp A functor to use for comparisons.
3168  * @return Nothing.
3169  *
3170  * Merges two sorted and consecutive ranges, [first,middle) and
3171  * [middle,last), and puts the result in [first,last). The output will
3172  * be sorted. The sort is @e stable, that is, for equivalent
3173  * elements in the two ranges, elements from the first range will always
3174  * come before elements from the second.
3175  *
3176  * If enough additional memory is available, this takes (last-first)-1
3177  * comparisons. Otherwise an NlogN algorithm is used, where N is
3178  * distance(first,last).
3179  *
3180  * The comparison function should have the same effects on ordering as
3181  * the function used for the initial sort.
3182  */
3183  template<typename _BidirectionalIterator, typename _Compare>
3184  void
3185  inplace_merge(_BidirectionalIterator __first,
3186  _BidirectionalIterator __middle,
3187  _BidirectionalIterator __last,
3188  _Compare __comp)
3189  {
3190  typedef typename iterator_traits<_BidirectionalIterator>::value_type
3191  _ValueType;
3192  typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3193  _DistanceType;
3194 
3195  // concept requirements
3196  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3197  _BidirectionalIterator>)
3198  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3199  _ValueType, _ValueType>)
3200  __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3201  __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3202 
3203  if (__first == __middle || __middle == __last)
3204  return;
3205 
3206  const _DistanceType __len1 = std::distance(__first, __middle);
3207  const _DistanceType __len2 = std::distance(__middle, __last);
3208 
3210  __last);
3211  if (__buf.begin() == 0)
3212  std::__merge_without_buffer(__first, __middle, __last, __len1,
3213  __len2, __comp);
3214  else
3215  std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3216  __buf.begin(), _DistanceType(__buf.size()),
3217  __comp);
3218  }
3219 
3220  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3221  typename _Distance>
3222  void
3223  __merge_sort_loop(_RandomAccessIterator1 __first,
3224  _RandomAccessIterator1 __last,
3225  _RandomAccessIterator2 __result,
3226  _Distance __step_size)
3227  {
3228  const _Distance __two_step = 2 * __step_size;
3229 
3230  while (__last - __first >= __two_step)
3231  {
3232  __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3233  __first + __step_size,
3234  __first + __two_step,
3235  __result);
3236  __first += __two_step;
3237  }
3238 
3239  __step_size = std::min(_Distance(__last - __first), __step_size);
3240  _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3241  __first + __step_size, __last,
3242  __result);
3243  }
3244 
3245  template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3246  typename _Distance, typename _Compare>
3247  void
3248  __merge_sort_loop(_RandomAccessIterator1 __first,
3249  _RandomAccessIterator1 __last,
3250  _RandomAccessIterator2 __result, _Distance __step_size,
3251  _Compare __comp)
3252  {
3253  const _Distance __two_step = 2 * __step_size;
3254 
3255  while (__last - __first >= __two_step)
3256  {
3257  __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3258  __first + __step_size, __first + __two_step,
3259  __result,
3260  __comp);
3261  __first += __two_step;
3262  }
3263  __step_size = std::min(_Distance(__last - __first), __step_size);
3264 
3265  _GLIBCXX_STD_P::merge(__first, __first + __step_size,
3266  __first + __step_size, __last, __result, __comp);
3267  }
3268 
3269  template<typename _RandomAccessIterator, typename _Distance>
3270  void
3271  __chunk_insertion_sort(_RandomAccessIterator __first,
3272  _RandomAccessIterator __last,
3273  _Distance __chunk_size)
3274  {
3275  while (__last - __first >= __chunk_size)
3276  {
3277  std::__insertion_sort(__first, __first + __chunk_size);
3278  __first += __chunk_size;
3279  }
3280  std::__insertion_sort(__first, __last);
3281  }
3282 
3283  template<typename _RandomAccessIterator, typename _Distance,
3284  typename _Compare>
3285  void
3286  __chunk_insertion_sort(_RandomAccessIterator __first,
3287  _RandomAccessIterator __last,
3288  _Distance __chunk_size, _Compare __comp)
3289  {
3290  while (__last - __first >= __chunk_size)
3291  {
3292  std::__insertion_sort(__first, __first + __chunk_size, __comp);
3293  __first += __chunk_size;
3294  }
3295  std::__insertion_sort(__first, __last, __comp);
3296  }
3297 
3298  enum { _S_chunk_size = 7 };
3299 
3300  template<typename _RandomAccessIterator, typename _Pointer>
3301  void
3302  __merge_sort_with_buffer(_RandomAccessIterator __first,
3303  _RandomAccessIterator __last,
3304  _Pointer __buffer)
3305  {
3306  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3307  _Distance;
3308 
3309  const _Distance __len = __last - __first;
3310  const _Pointer __buffer_last = __buffer + __len;
3311 
3312  _Distance __step_size = _S_chunk_size;
3313  std::__chunk_insertion_sort(__first, __last, __step_size);
3314 
3315  while (__step_size < __len)
3316  {
3317  std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3318  __step_size *= 2;
3319  std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3320  __step_size *= 2;
3321  }
3322  }
3323 
3324  template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3325  void
3326  __merge_sort_with_buffer(_RandomAccessIterator __first,
3327  _RandomAccessIterator __last,
3328  _Pointer __buffer, _Compare __comp)
3329  {
3330  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3331  _Distance;
3332 
3333  const _Distance __len = __last - __first;
3334  const _Pointer __buffer_last = __buffer + __len;
3335 
3336  _Distance __step_size = _S_chunk_size;
3337  std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3338 
3339  while (__step_size < __len)
3340  {
3341  std::__merge_sort_loop(__first, __last, __buffer,
3342  __step_size, __comp);
3343  __step_size *= 2;
3344  std::__merge_sort_loop(__buffer, __buffer_last, __first,
3345  __step_size, __comp);
3346  __step_size *= 2;
3347  }
3348  }
3349 
3350  template<typename _RandomAccessIterator, typename _Pointer,
3351  typename _Distance>
3352  void
3353  __stable_sort_adaptive(_RandomAccessIterator __first,
3354  _RandomAccessIterator __last,
3355  _Pointer __buffer, _Distance __buffer_size)
3356  {
3357  const _Distance __len = (__last - __first + 1) / 2;
3358  const _RandomAccessIterator __middle = __first + __len;
3359  if (__len > __buffer_size)
3360  {
3361  std::__stable_sort_adaptive(__first, __middle,
3362  __buffer, __buffer_size);
3363  std::__stable_sort_adaptive(__middle, __last,
3364  __buffer, __buffer_size);
3365  }
3366  else
3367  {
3368  std::__merge_sort_with_buffer(__first, __middle, __buffer);
3369  std::__merge_sort_with_buffer(__middle, __last, __buffer);
3370  }
3371  std::__merge_adaptive(__first, __middle, __last,
3372  _Distance(__middle - __first),
3373  _Distance(__last - __middle),
3374  __buffer, __buffer_size);
3375  }
3376 
3377  template<typename _RandomAccessIterator, typename _Pointer,
3378  typename _Distance, typename _Compare>
3379  void
3380  __stable_sort_adaptive(_RandomAccessIterator __first,
3381  _RandomAccessIterator __last,
3382  _Pointer __buffer, _Distance __buffer_size,
3383  _Compare __comp)
3384  {
3385  const _Distance __len = (__last - __first + 1) / 2;
3386  const _RandomAccessIterator __middle = __first + __len;
3387  if (__len > __buffer_size)
3388  {
3389  std::__stable_sort_adaptive(__first, __middle, __buffer,
3390  __buffer_size, __comp);
3391  std::__stable_sort_adaptive(__middle, __last, __buffer,
3392  __buffer_size, __comp);
3393  }
3394  else
3395  {
3396  std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3397  std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3398  }
3399  std::__merge_adaptive(__first, __middle, __last,
3400  _Distance(__middle - __first),
3401  _Distance(__last - __middle),
3402  __buffer, __buffer_size,
3403  __comp);
3404  }
3405 
3406  /// This is a helper function for the stable sorting routines.
3407  template<typename _RandomAccessIterator>
3408  void
3409  __inplace_stable_sort(_RandomAccessIterator __first,
3410  _RandomAccessIterator __last)
3411  {
3412  if (__last - __first < 15)
3413  {
3414  std::__insertion_sort(__first, __last);
3415  return;
3416  }
3417  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3418  std::__inplace_stable_sort(__first, __middle);
3419  std::__inplace_stable_sort(__middle, __last);
3420  std::__merge_without_buffer(__first, __middle, __last,
3421  __middle - __first,
3422  __last - __middle);
3423  }
3424 
3425  /// This is a helper function for the stable sorting routines.
3426  template<typename _RandomAccessIterator, typename _Compare>
3427  void
3428  __inplace_stable_sort(_RandomAccessIterator __first,
3429  _RandomAccessIterator __last, _Compare __comp)
3430  {
3431  if (__last - __first < 15)
3432  {
3433  std::__insertion_sort(__first, __last, __comp);
3434  return;
3435  }
3436  _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3437  std::__inplace_stable_sort(__first, __middle, __comp);
3438  std::__inplace_stable_sort(__middle, __last, __comp);
3439  std::__merge_without_buffer(__first, __middle, __last,
3440  __middle - __first,
3441  __last - __middle,
3442  __comp);
3443  }
3444 
3445  // stable_sort
3446 
3447  // Set algorithms: includes, set_union, set_intersection, set_difference,
3448  // set_symmetric_difference. All of these algorithms have the precondition
3449  // that their input ranges are sorted and the postcondition that their output
3450  // ranges are sorted.
3451 
3452  /**
3453  * @brief Determines whether all elements of a sequence exists in a range.
3454  * @param first1 Start of search range.
3455  * @param last1 End of search range.
3456  * @param first2 Start of sequence
3457  * @param last2 End of sequence.
3458  * @return True if each element in [first2,last2) is contained in order
3459  * within [first1,last1). False otherwise.
3460  * @ingroup set_algorithms
3461  *
3462  * This operation expects both [first1,last1) and [first2,last2) to be
3463  * sorted. Searches for the presence of each element in [first2,last2)
3464  * within [first1,last1). The iterators over each range only move forward,
3465  * so this is a linear algorithm. If an element in [first2,last2) is not
3466  * found before the search iterator reaches @a last2, false is returned.
3467  */
3468  template<typename _InputIterator1, typename _InputIterator2>
3469  bool
3470  includes(_InputIterator1 __first1, _InputIterator1 __last1,
3471  _InputIterator2 __first2, _InputIterator2 __last2)
3472  {
3473  typedef typename iterator_traits<_InputIterator1>::value_type
3474  _ValueType1;
3475  typedef typename iterator_traits<_InputIterator2>::value_type
3476  _ValueType2;
3477 
3478  // concept requirements
3479  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3480  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3481  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3482  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3483  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3484  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3485 
3486  while (__first1 != __last1 && __first2 != __last2)
3487  if (*__first2 < *__first1)
3488  return false;
3489  else if(*__first1 < *__first2)
3490  ++__first1;
3491  else
3492  ++__first1, ++__first2;
3493 
3494  return __first2 == __last2;
3495  }
3496 
3497  /**
3498  * @brief Determines whether all elements of a sequence exists in a range
3499  * using comparison.
3500  * @ingroup set_algorithms
3501  * @param first1 Start of search range.
3502  * @param last1 End of search range.
3503  * @param first2 Start of sequence
3504  * @param last2 End of sequence.
3505  * @param comp Comparison function to use.
3506  * @return True if each element in [first2,last2) is contained in order
3507  * within [first1,last1) according to comp. False otherwise.
3508  * @ingroup set_algorithms
3509  *
3510  * This operation expects both [first1,last1) and [first2,last2) to be
3511  * sorted. Searches for the presence of each element in [first2,last2)
3512  * within [first1,last1), using comp to decide. The iterators over each
3513  * range only move forward, so this is a linear algorithm. If an element
3514  * in [first2,last2) is not found before the search iterator reaches @a
3515  * last2, false is returned.
3516  */
3517  template<typename _InputIterator1, typename _InputIterator2,
3518  typename _Compare>
3519  bool
3520  includes(_InputIterator1 __first1, _InputIterator1 __last1,
3521  _InputIterator2 __first2, _InputIterator2 __last2,
3522  _Compare __comp)
3523  {
3524  typedef typename iterator_traits<_InputIterator1>::value_type
3525  _ValueType1;
3526  typedef typename iterator_traits<_InputIterator2>::value_type
3527  _ValueType2;
3528 
3529  // concept requirements
3530  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3531  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3532  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3533  _ValueType1, _ValueType2>)
3534  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3535  _ValueType2, _ValueType1>)
3536  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3537  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3538 
3539  while (__first1 != __last1 && __first2 != __last2)
3540  if (__comp(*__first2, *__first1))
3541  return false;
3542  else if(__comp(*__first1, *__first2))
3543  ++__first1;
3544  else
3545  ++__first1, ++__first2;
3546 
3547  return __first2 == __last2;
3548  }
3549 
3550  // nth_element
3551  // merge
3552  // set_difference
3553  // set_intersection
3554  // set_union
3555  // stable_sort
3556  // set_symmetric_difference
3557  // min_element
3558  // max_element
3559 
3560  /**
3561  * @brief Permute range into the next "dictionary" ordering.
3562  * @ingroup sorting_algorithms
3563  * @param first Start of range.
3564  * @param last End of range.
3565  * @return False if wrapped to first permutation, true otherwise.
3566  *
3567  * Treats all permutations of the range as a set of "dictionary" sorted
3568  * sequences. Permutes the current sequence into the next one of this set.
3569  * Returns true if there are more sequences to generate. If the sequence
3570  * is the largest of the set, the smallest is generated and false returned.
3571  */
3572  template<typename _BidirectionalIterator>
3573  bool
3574  next_permutation(_BidirectionalIterator __first,
3575  _BidirectionalIterator __last)
3576  {
3577  // concept requirements
3578  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3579  _BidirectionalIterator>)
3580  __glibcxx_function_requires(_LessThanComparableConcept<
3581  typename iterator_traits<_BidirectionalIterator>::value_type>)
3582  __glibcxx_requires_valid_range(__first, __last);
3583 
3584  if (__first == __last)
3585  return false;
3586  _BidirectionalIterator __i = __first;
3587  ++__i;
3588  if (__i == __last)
3589  return false;
3590  __i = __last;
3591  --__i;
3592 
3593  for(;;)
3594  {
3595  _BidirectionalIterator __ii = __i;
3596  --__i;
3597  if (*__i < *__ii)
3598  {
3599  _BidirectionalIterator __j = __last;
3600  while (!(*__i < *--__j))
3601  {}
3602  std::iter_swap(__i, __j);
3603  std::reverse(__ii, __last);
3604  return true;
3605  }
3606  if (__i == __first)
3607  {
3608  std::reverse(__first, __last);
3609  return false;
3610  }
3611  }
3612  }
3613 
3614  /**
3615  * @brief Permute range into the next "dictionary" ordering using
3616  * comparison functor.
3617  * @ingroup sorting_algorithms
3618  * @param first Start of range.
3619  * @param last End of range.
3620  * @param comp A comparison functor.
3621  * @return False if wrapped to first permutation, true otherwise.
3622  *
3623  * Treats all permutations of the range [first,last) as a set of
3624  * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3625  * sequence into the next one of this set. Returns true if there are more
3626  * sequences to generate. If the sequence is the largest of the set, the
3627  * smallest is generated and false returned.
3628  */
3629  template<typename _BidirectionalIterator, typename _Compare>
3630  bool
3631  next_permutation(_BidirectionalIterator __first,
3632  _BidirectionalIterator __last, _Compare __comp)
3633  {
3634  // concept requirements
3635  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3636  _BidirectionalIterator>)
3637  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3638  typename iterator_traits<_BidirectionalIterator>::value_type,
3639  typename iterator_traits<_BidirectionalIterator>::value_type>)
3640  __glibcxx_requires_valid_range(__first, __last);
3641 
3642  if (__first == __last)
3643  return false;
3644  _BidirectionalIterator __i = __first;
3645  ++__i;
3646  if (__i == __last)
3647  return false;
3648  __i = __last;
3649  --__i;
3650 
3651  for(;;)
3652  {
3653  _BidirectionalIterator __ii = __i;
3654  --__i;
3655  if (__comp(*__i, *__ii))
3656  {
3657  _BidirectionalIterator __j = __last;
3658  while (!bool(__comp(*__i, *--__j)))
3659  {}
3660  std::iter_swap(__i, __j);
3661  std::reverse(__ii, __last);
3662  return true;
3663  }
3664  if (__i == __first)
3665  {
3666  std::reverse(__first, __last);
3667  return false;
3668  }
3669  }
3670  }
3671 
3672  /**
3673  * @brief Permute range into the previous "dictionary" ordering.
3674  * @ingroup sorting_algorithms
3675  * @param first Start of range.
3676  * @param last End of range.
3677  * @return False if wrapped to last permutation, true otherwise.
3678  *
3679  * Treats all permutations of the range as a set of "dictionary" sorted
3680  * sequences. Permutes the current sequence into the previous one of this
3681  * set. Returns true if there are more sequences to generate. If the
3682  * sequence is the smallest of the set, the largest is generated and false
3683  * returned.
3684  */
3685  template<typename _BidirectionalIterator>
3686  bool
3687  prev_permutation(_BidirectionalIterator __first,
3688  _BidirectionalIterator __last)
3689  {
3690  // concept requirements
3691  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3692  _BidirectionalIterator>)
3693  __glibcxx_function_requires(_LessThanComparableConcept<
3694  typename iterator_traits<_BidirectionalIterator>::value_type>)
3695  __glibcxx_requires_valid_range(__first, __last);
3696 
3697  if (__first == __last)
3698  return false;
3699  _BidirectionalIterator __i = __first;
3700  ++__i;
3701  if (__i == __last)
3702  return false;
3703  __i = __last;
3704  --__i;
3705 
3706  for(;;)
3707  {
3708  _BidirectionalIterator __ii = __i;
3709  --__i;
3710  if (*__ii < *__i)
3711  {
3712  _BidirectionalIterator __j = __last;
3713  while (!(*--__j < *__i))
3714  {}
3715  std::iter_swap(__i, __j);
3716  std::reverse(__ii, __last);
3717  return true;
3718  }
3719  if (__i == __first)
3720  {
3721  std::reverse(__first, __last);
3722  return false;
3723  }
3724  }
3725  }
3726 
3727  /**
3728  * @brief Permute range into the previous "dictionary" ordering using
3729  * comparison functor.
3730  * @ingroup sorting_algorithms
3731  * @param first Start of range.
3732  * @param last End of range.
3733  * @param comp A comparison functor.
3734  * @return False if wrapped to last permutation, true otherwise.
3735  *
3736  * Treats all permutations of the range [first,last) as a set of
3737  * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3738  * sequence into the previous one of this set. Returns true if there are
3739  * more sequences to generate. If the sequence is the smallest of the set,
3740  * the largest is generated and false returned.
3741  */
3742  template<typename _BidirectionalIterator, typename _Compare>
3743  bool
3744  prev_permutation(_BidirectionalIterator __first,
3745  _BidirectionalIterator __last, _Compare __comp)
3746  {
3747  // concept requirements
3748  __glibcxx_function_requires(_BidirectionalIteratorConcept<
3749  _BidirectionalIterator>)
3750  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3751  typename iterator_traits<_BidirectionalIterator>::value_type,
3752  typename iterator_traits<_BidirectionalIterator>::value_type>)
3753  __glibcxx_requires_valid_range(__first, __last);
3754 
3755  if (__first == __last)
3756  return false;
3757  _BidirectionalIterator __i = __first;
3758  ++__i;
3759  if (__i == __last)
3760  return false;
3761  __i = __last;
3762  --__i;
3763 
3764  for(;;)
3765  {
3766  _BidirectionalIterator __ii = __i;
3767  --__i;
3768  if (__comp(*__ii, *__i))
3769  {
3770  _BidirectionalIterator __j = __last;
3771  while (!bool(__comp(*--__j, *__i)))
3772  {}
3773  std::iter_swap(__i, __j);
3774  std::reverse(__ii, __last);
3775  return true;
3776  }
3777  if (__i == __first)
3778  {
3779  std::reverse(__first, __last);
3780  return false;
3781  }
3782  }
3783  }
3784 
3785  // replace
3786  // replace_if
3787 
3788  /**
3789  * @brief Copy a sequence, replacing each element of one value with another
3790  * value.
3791  * @param first An input iterator.
3792  * @param last An input iterator.
3793  * @param result An output iterator.
3794  * @param old_value The value to be replaced.
3795  * @param new_value The replacement value.
3796  * @return The end of the output sequence, @p result+(last-first).
3797  *
3798  * Copies each element in the input range @p [first,last) to the
3799  * output range @p [result,result+(last-first)) replacing elements
3800  * equal to @p old_value with @p new_value.
3801  */
3802  template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3803  _OutputIterator
3804  replace_copy(_InputIterator __first, _InputIterator __last,
3805  _OutputIterator __result,
3806  const _Tp& __old_value, const _Tp& __new_value)
3807  {
3808  // concept requirements
3809  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3810  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3811  typename iterator_traits<_InputIterator>::value_type>)
3812  __glibcxx_function_requires(_EqualOpConcept<
3813  typename iterator_traits<_InputIterator>::value_type, _Tp>)
3814  __glibcxx_requires_valid_range(__first, __last);
3815 
3816  for (; __first != __last; ++__first, ++__result)
3817  if (*__first == __old_value)
3818  *__result = __new_value;
3819  else
3820  *__result = *__first;
3821  return __result;
3822  }
3823 
3824  /**
3825  * @brief Copy a sequence, replacing each value for which a predicate
3826  * returns true with another value.
3827  * @ingroup mutating_algorithms
3828  * @param first An input iterator.
3829  * @param last An input iterator.
3830  * @param result An output iterator.
3831  * @param pred A predicate.
3832  * @param new_value The replacement value.
3833  * @return The end of the output sequence, @p result+(last-first).
3834  *
3835  * Copies each element in the range @p [first,last) to the range
3836  * @p [result,result+(last-first)) replacing elements for which
3837  * @p pred returns true with @p new_value.
3838  */
3839  template<typename _InputIterator, typename _OutputIterator,
3840  typename _Predicate, typename _Tp>
3841  _OutputIterator
3842  replace_copy_if(_InputIterator __first, _InputIterator __last,
3843  _OutputIterator __result,
3844  _Predicate __pred, const _Tp& __new_value)
3845  {
3846  // concept requirements
3847  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3848  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3849  typename iterator_traits<_InputIterator>::value_type>)
3850  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3851  typename iterator_traits<_InputIterator>::value_type>)
3852  __glibcxx_requires_valid_range(__first, __last);
3853 
3854  for (; __first != __last; ++__first, ++__result)
3855  if (__pred(*__first))
3856  *__result = __new_value;
3857  else
3858  *__result = *__first;
3859  return __result;
3860  }
3861 
3862 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3863  /**
3864  * @brief Determines whether the elements of a sequence are sorted.
3865  * @ingroup sorting_algorithms
3866  * @param first An iterator.
3867  * @param last Another iterator.
3868  * @return True if the elements are sorted, false otherwise.
3869  */
3870  template<typename _ForwardIterator>
3871  inline bool
3872  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3873  { return std::is_sorted_until(__first, __last) == __last; }
3874 
3875  /**
3876  * @brief Determines whether the elements of a sequence are sorted
3877  * according to a comparison functor.
3878  * @ingroup sorting_algorithms
3879  * @param first An iterator.
3880  * @param last Another iterator.
3881  * @param comp A comparison functor.
3882  * @return True if the elements are sorted, false otherwise.
3883  */
3884  template<typename _ForwardIterator, typename _Compare>
3885  inline bool
3886  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3887  _Compare __comp)
3888  { return std::is_sorted_until(__first, __last, __comp) == __last; }
3889 
3890  /**
3891  * @brief Determines the end of a sorted sequence.
3892  * @ingroup sorting_algorithms
3893  * @param first An iterator.
3894  * @param last Another iterator.
3895  * @return An iterator pointing to the last iterator i in [first, last)
3896  * for which the range [first, i) is sorted.
3897  */
3898  template<typename _ForwardIterator>
3899  _ForwardIterator
3900  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3901  {
3902  // concept requirements
3903  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3904  __glibcxx_function_requires(_LessThanComparableConcept<
3905  typename iterator_traits<_ForwardIterator>::value_type>)
3906  __glibcxx_requires_valid_range(__first, __last);
3907 
3908  if (__first == __last)
3909  return __last;
3910 
3911  _ForwardIterator __next = __first;
3912  for (++__next; __next != __last; __first = __next, ++__next)
3913  if (*__next < *__first)
3914  return __next;
3915  return __next;
3916  }
3917 
3918  /**
3919  * @brief Determines the end of a sorted sequence using comparison functor.
3920  * @ingroup sorting_algorithms
3921  * @param first An iterator.
3922  * @param last Another iterator.
3923  * @param comp A comparison functor.
3924  * @return An iterator pointing to the last iterator i in [first, last)
3925  * for which the range [first, i) is sorted.
3926  */
3927  template<typename _ForwardIterator, typename _Compare>
3928  _ForwardIterator
3929  is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3930  _Compare __comp)
3931  {
3932  // concept requirements
3933  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3934  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3935  typename iterator_traits<_ForwardIterator>::value_type,
3936  typename iterator_traits<_ForwardIterator>::value_type>)
3937  __glibcxx_requires_valid_range(__first, __last);
3938 
3939  if (__first == __last)
3940  return __last;
3941 
3942  _ForwardIterator __next = __first;
3943  for (++__next; __next != __last; __first = __next, ++__next)
3944  if (__comp(*__next, *__first))
3945  return __next;
3946  return __next;
3947  }
3948 
3949  /**
3950  * @brief Determines min and max at once as an ordered pair.
3951  * @ingroup sorting_algorithms
3952  * @param a A thing of arbitrary type.
3953  * @param b Another thing of arbitrary type.
3954  * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3955  */
3956  template<typename _Tp>
3957  inline pair<const _Tp&, const _Tp&>
3958  minmax(const _Tp& __a, const _Tp& __b)
3959  {
3960  // concept requirements
3961  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3962 
3963  return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3964  : pair<const _Tp&, const _Tp&>(__a, __b);
3965  }
3966 
3967  /**
3968  * @brief Determines min and max at once as an ordered pair.
3969  * @ingroup sorting_algorithms
3970  * @param a A thing of arbitrary type.
3971  * @param b Another thing of arbitrary type.
3972  * @param comp A @link comparison_functor comparison functor@endlink.
3973  * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3974  */
3975  template<typename _Tp, typename _Compare>
3976  inline pair<const _Tp&, const _Tp&>
3977  minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3978  {
3979  return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3980  : pair<const _Tp&, const _Tp&>(__a, __b);
3981  }
3982 
3983  /**
3984  * @brief Return a pair of iterators pointing to the minimum and maximum
3985  * elements in a range.
3986  * @ingroup sorting_algorithms
3987  * @param first Start of range.
3988  * @param last End of range.
3989  * @return make_pair(m, M), where m is the first iterator i in
3990  * [first, last) such that no other element in the range is
3991  * smaller, and where M is the last iterator i in [first, last)
3992  * such that no other element in the range is larger.
3993  */
3994  template<typename _ForwardIterator>
3995  pair<_ForwardIterator, _ForwardIterator>
3996  minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3997  {
3998  // concept requirements
3999  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4000  __glibcxx_function_requires(_LessThanComparableConcept<
4001  typename iterator_traits<_ForwardIterator>::value_type>)
4002  __glibcxx_requires_valid_range(__first, __last);
4003 
4004  _ForwardIterator __next = __first;
4005  if (__first == __last
4006  || ++__next == __last)
4007  return std::make_pair(__first, __first);
4008 
4009  _ForwardIterator __min, __max;
4010  if (*__next < *__first)
4011  {
4012  __min = __next;
4013  __max = __first;
4014  }
4015  else
4016  {
4017  __min = __first;
4018  __max = __next;
4019  }
4020 
4021  __first = __next;
4022  ++__first;
4023 
4024  while (__first != __last)
4025  {
4026  __next = __first;
4027  if (++__next == __last)
4028  {
4029  if (*__first < *__min)
4030  __min = __first;
4031  else if (!(*__first < *__max))
4032  __max = __first;
4033  break;
4034  }
4035 
4036  if (*__next < *__first)
4037  {
4038  if (*__next < *__min)
4039  __min = __next;
4040  if (!(*__first < *__max))
4041  __max = __first;
4042  }
4043  else
4044  {
4045  if (*__first < *__min)
4046  __min = __first;
4047  if (!(*__next < *__max))
4048  __max = __next;
4049  }
4050 
4051  __first = __next;
4052  ++__first;
4053  }
4054 
4055  return std::make_pair(__min, __max);
4056  }
4057 
4058  /**
4059  * @brief Return a pair of iterators pointing to the minimum and maximum
4060  * elements in a range.
4061  * @ingroup sorting_algorithms
4062  * @param first Start of range.
4063  * @param last End of range.
4064  * @param comp Comparison functor.
4065  * @return make_pair(m, M), where m is the first iterator i in
4066  * [first, last) such that no other element in the range is
4067  * smaller, and where M is the last iterator i in [first, last)
4068  * such that no other element in the range is larger.
4069  */
4070  template<typename _ForwardIterator, typename _Compare>
4071  pair<_ForwardIterator, _ForwardIterator>
4072  minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4073  _Compare __comp)
4074  {
4075  // concept requirements
4076  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4077  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4078  typename iterator_traits<_ForwardIterator>::value_type,
4079  typename iterator_traits<_ForwardIterator>::value_type>)
4080  __glibcxx_requires_valid_range(__first, __last);
4081 
4082  _ForwardIterator __next = __first;
4083  if (__first == __last
4084  || ++__next == __last)
4085  return std::make_pair(__first, __first);
4086 
4087  _ForwardIterator __min, __max;
4088  if (__comp(*__next, *__first))
4089  {
4090  __min = __next;
4091  __max = __first;
4092  }
4093  else
4094  {
4095  __min = __first;
4096  __max = __next;
4097  }
4098 
4099  __first = __next;
4100  ++__first;
4101 
4102  while (__first != __last)
4103  {
4104  __next = __first;
4105  if (++__next == __last)
4106  {
4107  if (__comp(*__first, *__min))
4108  __min = __first;
4109  else if (!__comp(*__first, *__max))
4110  __max = __first;
4111  break;
4112  }
4113 
4114  if (__comp(*__next, *__first))
4115  {
4116  if (__comp(*__next, *__min))
4117  __min = __next;
4118  if (!__comp(*__first, *__max))
4119  __max = __first;
4120  }
4121  else
4122  {
4123  if (__comp(*__first, *__min))
4124  __min = __first;
4125  if (!__comp(*__next, *__max))
4126  __max = __next;
4127  }
4128 
4129  __first = __next;
4130  ++__first;
4131  }
4132 
4133  return std::make_pair(__min, __max);
4134  }
4135 
4136  // N2722 + fixes.
4137  template<typename _Tp>
4138  inline _Tp
4139  min(initializer_list<_Tp> __l)
4140  { return *std::min_element(__l.begin(), __l.end()); }
4141 
4142  template<typename _Tp, typename _Compare>
4143  inline _Tp
4144  min(initializer_list<_Tp> __l, _Compare __comp)
4145  { return *std::min_element(__l.begin(), __l.end(), __comp); }
4146 
4147  template<typename _Tp>
4148  inline _Tp
4149  max(initializer_list<_Tp> __l)
4150  { return *std::max_element(__l.begin(), __l.end()); }
4151 
4152  template<typename _Tp, typename _Compare>
4153  inline _Tp
4154  max(initializer_list<_Tp> __l, _Compare __comp)
4155  { return *std::max_element(__l.begin(), __l.end(), __comp); }
4156 
4157  template<typename _Tp>
4158  inline pair<_Tp, _Tp>
4159  minmax(initializer_list<_Tp> __l)
4160  {
4161  pair<const _Tp*, const _Tp*> __p =
4162  std::minmax_element(__l.begin(), __l.end());
4163  return std::make_pair(*__p.first, *__p.second);
4164  }
4165 
4166  template<typename _Tp, typename _Compare>
4167  inline pair<_Tp, _Tp>
4168  minmax(initializer_list<_Tp> __l, _Compare __comp)
4169  {
4170  pair<const _Tp*, const _Tp*> __p =
4171  std::minmax_element(__l.begin(), __l.end(), __comp);
4172  return std::make_pair(*__p.first, *__p.second);
4173  }
4174 #endif // __GXX_EXPERIMENTAL_CXX0X__
4175 
4176 _GLIBCXX_END_NAMESPACE
4177 
4178 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
4179 
4180  /**
4181  * @brief Apply a function to every element of a sequence.
4182  * @ingroup non_mutating_algorithms
4183  * @param first An input iterator.
4184  * @param last An input iterator.
4185  * @param f A unary function object.
4186  * @return @p f.
4187  *
4188  * Applies the function object @p f to each element in the range
4189  * @p [first,last). @p f must not modify the order of the sequence.
4190  * If @p f has a return value it is ignored.
4191  */
4192  template<typename _InputIterator, typename _Function>
4193  _Function
4194  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4195  {
4196  // concept requirements
4197  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4198  __glibcxx_requires_valid_range(__first, __last);
4199  for (; __first != __last; ++__first)
4200  __f(*__first);
4201  return __f;
4202  }
4203 
4204  /**
4205  * @brief Find the first occurrence of a value in a sequence.
4206  * @ingroup non_mutating_algorithms
4207  * @param first An input iterator.
4208  * @param last An input iterator.
4209  * @param val The value to find.
4210  * @return The first iterator @c i in the range @p [first,last)
4211  * such that @c *i == @p val, or @p last if no such iterator exists.
4212  */
4213  template<typename _InputIterator, typename _Tp>
4214  inline _InputIterator
4215  find(_InputIterator __first, _InputIterator __last,
4216  const _Tp& __val)
4217  {
4218  // concept requirements
4219  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4220  __glibcxx_function_requires(_EqualOpConcept<
4221  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4222  __glibcxx_requires_valid_range(__first, __last);
4223  return std::__find(__first, __last, __val,
4224  std::__iterator_category(__first));
4225  }
4226 
4227  /**
4228  * @brief Find the first element in a sequence for which a
4229  * predicate is true.
4230  * @ingroup non_mutating_algorithms
4231  * @param first An input iterator.
4232  * @param last An input iterator.
4233  * @param pred A predicate.
4234  * @return The first iterator @c i in the range @p [first,last)
4235  * such that @p pred(*i) is true, or @p last if no such iterator exists.
4236  */
4237  template<typename _InputIterator, typename _Predicate>
4238  inline _InputIterator
4239  find_if(_InputIterator __first, _InputIterator __last,
4240  _Predicate __pred)
4241  {
4242  // concept requirements
4243  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4244  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4245  typename iterator_traits<_InputIterator>::value_type>)
4246  __glibcxx_requires_valid_range(__first, __last);
4247  return std::__find_if(__first, __last, __pred,
4248  std::__iterator_category(__first));
4249  }
4250 
4251  /**
4252  * @brief Find element from a set in a sequence.
4253  * @ingroup non_mutating_algorithms
4254  * @param first1 Start of range to search.
4255  * @param last1 End of range to search.
4256  * @param first2 Start of match candidates.
4257  * @param last2 End of match candidates.
4258  * @return The first iterator @c i in the range
4259  * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4260  * iterator in [first2,last2), or @p last1 if no such iterator exists.
4261  *
4262  * Searches the range @p [first1,last1) for an element that is equal to
4263  * some element in the range [first2,last2). If found, returns an iterator
4264  * in the range [first1,last1), otherwise returns @p last1.
4265  */
4266  template<typename _InputIterator, typename _ForwardIterator>
4267  _InputIterator
4268  find_first_of(_InputIterator __first1, _InputIterator __last1,
4269  _ForwardIterator __first2, _ForwardIterator __last2)
4270  {
4271  // concept requirements
4272  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4273  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4274  __glibcxx_function_requires(_EqualOpConcept<
4275  typename iterator_traits<_InputIterator>::value_type,
4276  typename iterator_traits<_ForwardIterator>::value_type>)
4277  __glibcxx_requires_valid_range(__first1, __last1);
4278  __glibcxx_requires_valid_range(__first2, __last2);
4279 
4280  for (; __first1 != __last1; ++__first1)
4281  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4282  if (*__first1 == *__iter)
4283  return __first1;
4284  return __last1;
4285  }
4286 
4287  /**
4288  * @brief Find element from a set in a sequence using a predicate.
4289  * @ingroup non_mutating_algorithms
4290  * @param first1 Start of range to search.
4291  * @param last1 End of range to search.
4292  * @param first2 Start of match candidates.
4293  * @param last2 End of match candidates.
4294  * @param comp Predicate to use.
4295  * @return The first iterator @c i in the range
4296  * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4297  * iterator in [first2,last2), or @p last1 if no such iterator exists.
4298  *
4299 
4300  * Searches the range @p [first1,last1) for an element that is
4301  * equal to some element in the range [first2,last2). If found,
4302  * returns an iterator in the range [first1,last1), otherwise
4303  * returns @p last1.
4304  */
4305  template<typename _InputIterator, typename _ForwardIterator,
4306  typename _BinaryPredicate>
4307  _InputIterator
4308  find_first_of(_InputIterator __first1, _InputIterator __last1,
4309  _ForwardIterator __first2, _ForwardIterator __last2,
4310  _BinaryPredicate __comp)
4311  {
4312  // concept requirements
4313  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4314  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4315  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4316  typename iterator_traits<_InputIterator>::value_type,
4317  typename iterator_traits<_ForwardIterator>::value_type>)
4318  __glibcxx_requires_valid_range(__first1, __last1);
4319  __glibcxx_requires_valid_range(__first2, __last2);
4320 
4321  for (; __first1 != __last1; ++__first1)
4322  for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4323  if (__comp(*__first1, *__iter))
4324  return __first1;
4325  return __last1;
4326  }
4327 
4328  /**
4329  * @brief Find two adjacent values in a sequence that are equal.
4330  * @ingroup non_mutating_algorithms
4331  * @param first A forward iterator.
4332  * @param last A forward iterator.
4333  * @return The first iterator @c i such that @c i and @c i+1 are both
4334  * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
4335  * or @p last if no such iterator exists.
4336  */
4337  template<typename _ForwardIterator>
4338  _ForwardIterator
4339  adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4340  {
4341  // concept requirements
4342  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4343  __glibcxx_function_requires(_EqualityComparableConcept<
4344  typename iterator_traits<_ForwardIterator>::value_type>)
4345  __glibcxx_requires_valid_range(__first, __last);
4346  if (__first == __last)
4347  return __last;
4348  _ForwardIterator __next = __first;
4349  while(++__next != __last)
4350  {
4351  if (*__first == *__next)
4352  return __first;
4353  __first = __next;
4354  }
4355  return __last;
4356  }
4357 
4358  /**
4359  * @brief Find two adjacent values in a sequence using a predicate.
4360  * @ingroup non_mutating_algorithms
4361  * @param first A forward iterator.
4362  * @param last A forward iterator.
4363  * @param binary_pred A binary predicate.
4364  * @return The first iterator @c i such that @c i and @c i+1 are both
4365  * valid iterators in @p [first,last) and such that
4366  * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
4367  * exists.
4368  */
4369  template<typename _ForwardIterator, typename _BinaryPredicate>
4370  _ForwardIterator
4371  adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4372  _BinaryPredicate __binary_pred)
4373  {
4374  // concept requirements
4375  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4376  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4377  typename iterator_traits<_ForwardIterator>::value_type,
4378  typename iterator_traits<_ForwardIterator>::value_type>)
4379  __glibcxx_requires_valid_range(__first, __last);
4380  if (__first == __last)
4381  return __last;
4382  _ForwardIterator __next = __first;
4383  while(++__next != __last)
4384  {
4385  if (__binary_pred(*__first, *__next))
4386  return __first;
4387  __first = __next;
4388  }
4389  return __last;
4390  }
4391 
4392  /**
4393  * @brief Count the number of copies of a value in a sequence.
4394  * @ingroup non_mutating_algorithms
4395  * @param first An input iterator.
4396  * @param last An input iterator.
4397  * @param value The value to be counted.
4398  * @return The number of iterators @c i in the range @p [first,last)
4399  * for which @c *i == @p value
4400  */
4401  template<typename _InputIterator, typename _Tp>
4402  typename iterator_traits<_InputIterator>::difference_type
4403  count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4404  {
4405  // concept requirements
4406  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4407  __glibcxx_function_requires(_EqualOpConcept<
4408  typename iterator_traits<_InputIterator>::value_type, _Tp>)
4409  __glibcxx_requires_valid_range(__first, __last);
4410  typename iterator_traits<_InputIterator>::difference_type __n = 0;
4411  for (; __first != __last; ++__first)
4412  if (*__first == __value)
4413  ++__n;
4414  return __n;
4415  }
4416 
4417  /**
4418  * @brief Count the elements of a sequence for which a predicate is true.
4419  * @ingroup non_mutating_algorithms
4420  * @param first An input iterator.
4421  * @param last An input iterator.
4422  * @param pred A predicate.
4423  * @return The number of iterators @c i in the range @p [first,last)
4424  * for which @p pred(*i) is true.
4425  */
4426  template<typename _InputIterator, typename _Predicate>
4427  typename iterator_traits<_InputIterator>::difference_type
4428  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4429  {
4430  // concept requirements
4431  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4432  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4433  typename iterator_traits<_InputIterator>::value_type>)
4434  __glibcxx_requires_valid_range(__first, __last);
4435  typename iterator_traits<_InputIterator>::difference_type __n = 0;
4436  for (; __first != __last; ++__first)
4437  if (__pred(*__first))
4438  ++__n;
4439  return __n;
4440  }
4441 
4442  /**
4443  * @brief Search a sequence for a matching sub-sequence.
4444  * @ingroup non_mutating_algorithms
4445  * @param first1 A forward iterator.
4446  * @param last1 A forward iterator.
4447  * @param first2 A forward iterator.
4448  * @param last2 A forward iterator.
4449  * @return The first iterator @c i in the range
4450  * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
4451  * for each @c N in the range @p [0,last2-first2), or @p last1 if no
4452  * such iterator exists.
4453  *
4454  * Searches the range @p [first1,last1) for a sub-sequence that compares
4455  * equal value-by-value with the sequence given by @p [first2,last2) and
4456  * returns an iterator to the first element of the sub-sequence, or
4457  * @p last1 if the sub-sequence is not found.
4458  *
4459  * Because the sub-sequence must lie completely within the range
4460  * @p [first1,last1) it must start at a position less than
4461  * @p last1-(last2-first2) where @p last2-first2 is the length of the
4462  * sub-sequence.
4463  * This means that the returned iterator @c i will be in the range
4464  * @p [first1,last1-(last2-first2))
4465  */
4466  template<typename _ForwardIterator1, typename _ForwardIterator2>
4467  _ForwardIterator1
4468  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4469  _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4470  {
4471  // concept requirements
4472  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4473  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4474  __glibcxx_function_requires(_EqualOpConcept<
4475  typename iterator_traits<_ForwardIterator1>::value_type,
4476  typename iterator_traits<_ForwardIterator2>::value_type>)
4477  __glibcxx_requires_valid_range(__first1, __last1);
4478  __glibcxx_requires_valid_range(__first2, __last2);
4479 
4480  // Test for empty ranges
4481  if (__first1 == __last1 || __first2 == __last2)
4482  return __first1;
4483 
4484  // Test for a pattern of length 1.
4485  _ForwardIterator2 __p1(__first2);
4486  if (++__p1 == __last2)
4487  return _GLIBCXX_STD_P::find(__first1, __last1, *__first2);
4488 
4489  // General case.
4490  _ForwardIterator2 __p;
4491  _ForwardIterator1 __current = __first1;
4492 
4493  for (;;)
4494  {
4495  __first1 = _GLIBCXX_STD_P::find(__first1, __last1, *__first2);
4496  if (__first1 == __last1)
4497  return __last1;
4498 
4499  __p = __p1;
4500  __current = __first1;
4501  if (++__current == __last1)
4502  return __last1;
4503 
4504  while (*__current == *__p)
4505  {
4506  if (++__p == __last2)
4507  return __first1;
4508  if (++__current == __last1)
4509  return __last1;
4510  }
4511  ++__first1;
4512  }
4513  return __first1;
4514  }
4515 
4516  /**
4517  * @brief Search a sequence for a matching sub-sequence using a predicate.
4518  * @ingroup non_mutating_algorithms
4519  * @param first1 A forward iterator.
4520  * @param last1 A forward iterator.
4521  * @param first2 A forward iterator.
4522  * @param last2 A forward iterator.
4523  * @param predicate A binary predicate.
4524  * @return The first iterator @c i in the range
4525  * @p [first1,last1-(last2-first2)) such that
4526  * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
4527  * @p [0,last2-first2), or @p last1 if no such iterator exists.
4528  *
4529  * Searches the range @p [first1,last1) for a sub-sequence that compares
4530  * equal value-by-value with the sequence given by @p [first2,last2),
4531  * using @p predicate to determine equality, and returns an iterator
4532  * to the first element of the sub-sequence, or @p last1 if no such
4533  * iterator exists.
4534  *
4535  * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4536  */
4537  template<typename _ForwardIterator1, typename _ForwardIterator2,
4538  typename _BinaryPredicate>
4539  _ForwardIterator1
4540  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4541  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4542  _BinaryPredicate __predicate)
4543  {
4544  // concept requirements
4545  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4546  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4547  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4548  typename iterator_traits<_ForwardIterator1>::value_type,
4549  typename iterator_traits<_ForwardIterator2>::value_type>)
4550  __glibcxx_requires_valid_range(__first1, __last1);
4551  __glibcxx_requires_valid_range(__first2, __last2);
4552 
4553  // Test for empty ranges
4554  if (__first1 == __last1 || __first2 == __last2)
4555  return __first1;
4556 
4557  // Test for a pattern of length 1.
4558  _ForwardIterator2 __p1(__first2);
4559  if (++__p1 == __last2)
4560  {
4561  while (__first1 != __last1
4562  && !bool(__predicate(*__first1, *__first2)))
4563  ++__first1;
4564  return __first1;
4565  }
4566 
4567  // General case.
4568  _ForwardIterator2 __p;
4569  _ForwardIterator1 __current = __first1;
4570 
4571  for (;;)
4572  {
4573  while (__first1 != __last1
4574  && !bool(__predicate(*__first1, *__first2)))
4575  ++__first1;
4576  if (__first1 == __last1)
4577  return __last1;
4578 
4579  __p = __p1;
4580  __current = __first1;
4581  if (++__current == __last1)
4582  return __last1;
4583 
4584  while (__predicate(*__current, *__p))
4585  {
4586  if (++__p == __last2)
4587  return __first1;
4588  if (++__current == __last1)
4589  return __last1;
4590  }
4591  ++__first1;
4592  }
4593  return __first1;
4594  }
4595 
4596 
4597  /**
4598  * @brief Search a sequence for a number of consecutive values.
4599  * @ingroup non_mutating_algorithms
4600  * @param first A forward iterator.
4601  * @param last A forward iterator.
4602  * @param count The number of consecutive values.
4603  * @param val The value to find.
4604  * @return The first iterator @c i in the range @p [first,last-count)
4605  * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
4606  * or @p last if no such iterator exists.
4607  *
4608  * Searches the range @p [first,last) for @p count consecutive elements
4609  * equal to @p val.
4610  */
4611  template<typename _ForwardIterator, typename _Integer, typename _Tp>
4612  _ForwardIterator
4613  search_n(_ForwardIterator __first, _ForwardIterator __last,
4614  _Integer __count, const _Tp& __val)
4615  {
4616  // concept requirements
4617  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4618  __glibcxx_function_requires(_EqualOpConcept<
4619  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4620  __glibcxx_requires_valid_range(__first, __last);
4621 
4622  if (__count <= 0)
4623  return __first;
4624  if (__count == 1)
4625  return _GLIBCXX_STD_P::find(__first, __last, __val);
4626  return std::__search_n(__first, __last, __count, __val,
4627  std::__iterator_category(__first));
4628  }
4629 
4630 
4631  /**
4632  * @brief Search a sequence for a number of consecutive values using a
4633  * predicate.
4634  * @ingroup non_mutating_algorithms
4635  * @param first A forward iterator.
4636  * @param last A forward iterator.
4637  * @param count The number of consecutive values.
4638  * @param val The value to find.
4639  * @param binary_pred A binary predicate.
4640  * @return The first iterator @c i in the range @p [first,last-count)
4641  * such that @p binary_pred(*(i+N),val) is true for each @c N in the
4642  * range @p [0,count), or @p last if no such iterator exists.
4643  *
4644  * Searches the range @p [first,last) for @p count consecutive elements
4645  * for which the predicate returns true.
4646  */
4647  template<typename _ForwardIterator, typename _Integer, typename _Tp,
4648  typename _BinaryPredicate>
4649  _ForwardIterator
4650  search_n(_ForwardIterator __first, _ForwardIterator __last,
4651  _Integer __count, const _Tp& __val,
4652  _BinaryPredicate __binary_pred)
4653  {
4654  // concept requirements
4655  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4656  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4657  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4658  __glibcxx_requires_valid_range(__first, __last);
4659 
4660  if (__count <= 0)
4661  return __first;
4662  if (__count == 1)
4663  {
4664  while (__first != __last && !bool(__binary_pred(*__first, __val)))
4665  ++__first;
4666  return __first;
4667  }
4668  return std::__search_n(__first, __last, __count, __val, __binary_pred,
4669  std::__iterator_category(__first));
4670  }
4671 
4672 
4673  /**
4674  * @brief Perform an operation on a sequence.
4675  * @ingroup mutating_algorithms
4676  * @param first An input iterator.
4677  * @param last An input iterator.
4678  * @param result An output iterator.
4679  * @param unary_op A unary operator.
4680  * @return An output iterator equal to @p result+(last-first).
4681  *
4682  * Applies the operator to each element in the input range and assigns
4683  * the results to successive elements of the output sequence.
4684  * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
4685  * range @p [0,last-first).
4686  *
4687  * @p unary_op must not alter its argument.
4688  */
4689  template<typename _InputIterator, typename _OutputIterator,
4690  typename _UnaryOperation>
4691  _OutputIterator
4692  transform(_InputIterator __first, _InputIterator __last,
4693  _OutputIterator __result, _UnaryOperation __unary_op)
4694  {
4695  // concept requirements
4696  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4697  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4698  // "the type returned by a _UnaryOperation"
4699  __typeof__(__unary_op(*__first))>)
4700  __glibcxx_requires_valid_range(__first, __last);
4701 
4702  for (; __first != __last; ++__first, ++__result)
4703  *__result = __unary_op(*__first);
4704  return __result;
4705  }
4706 
4707  /**
4708  * @brief Perform an operation on corresponding elements of two sequences.
4709  * @ingroup mutating_algorithms
4710  * @param first1 An input iterator.
4711  * @param last1 An input iterator.
4712  * @param first2 An input iterator.
4713  * @param result An output iterator.
4714  * @param binary_op A binary operator.
4715  * @return An output iterator equal to @p result+(last-first).
4716  *
4717  * Applies the operator to the corresponding elements in the two
4718  * input ranges and assigns the results to successive elements of the
4719  * output sequence.
4720  * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
4721  * @c N in the range @p [0,last1-first1).
4722  *
4723  * @p binary_op must not alter either of its arguments.
4724  */
4725  template<typename _InputIterator1, typename _InputIterator2,
4726  typename _OutputIterator, typename _BinaryOperation>
4727  _OutputIterator
4728  transform(_InputIterator1 __first1, _InputIterator1 __last1,
4729  _InputIterator2 __first2, _OutputIterator __result,
4730  _BinaryOperation __binary_op)
4731  {
4732  // concept requirements
4733  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4734  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4735  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4736  // "the type returned by a _BinaryOperation"
4737  __typeof__(__binary_op(*__first1,*__first2))>)
4738  __glibcxx_requires_valid_range(__first1, __last1);
4739 
4740  for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4741  *__result = __binary_op(*__first1, *__first2);
4742  return __result;
4743  }
4744 
4745  /**
4746  * @brief Replace each occurrence of one value in a sequence with another
4747  * value.
4748  * @ingroup mutating_algorithms
4749  * @param first A forward iterator.
4750  * @param last A forward iterator.
4751  * @param old_value The value to be replaced.
4752  * @param new_value The replacement value.
4753  * @return replace() returns no value.
4754  *
4755  * For each iterator @c i in the range @p [first,last) if @c *i ==
4756  * @p old_value then the assignment @c *i = @p new_value is performed.
4757  */
4758  template<typename _ForwardIterator, typename _Tp>
4759  void
4760  replace(_ForwardIterator __first, _ForwardIterator __last,
4761  const _Tp& __old_value, const _Tp& __new_value)
4762  {
4763  // concept requirements
4764  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4765  _ForwardIterator>)
4766  __glibcxx_function_requires(_EqualOpConcept<
4767  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4768  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4769  typename iterator_traits<_ForwardIterator>::value_type>)
4770  __glibcxx_requires_valid_range(__first, __last);
4771 
4772  for (; __first != __last; ++__first)
4773  if (*__first == __old_value)
4774  *__first = __new_value;
4775  }
4776 
4777  /**
4778  * @brief Replace each value in a sequence for which a predicate returns
4779  * true with another value.
4780  * @ingroup mutating_algorithms
4781  * @param first A forward iterator.
4782  * @param last A forward iterator.
4783  * @param pred A predicate.
4784  * @param new_value The replacement value.
4785  * @return replace_if() returns no value.
4786  *
4787  * For each iterator @c i in the range @p [first,last) if @p pred(*i)
4788  * is true then the assignment @c *i = @p new_value is performed.
4789  */
4790  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4791  void
4792  replace_if(_ForwardIterator __first, _ForwardIterator __last,
4793  _Predicate __pred, const _Tp& __new_value)
4794  {
4795  // concept requirements
4796  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4797  _ForwardIterator>)
4798  __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4799  typename iterator_traits<_ForwardIterator>::value_type>)
4800  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4801  typename iterator_traits<_ForwardIterator>::value_type>)
4802  __glibcxx_requires_valid_range(__first, __last);
4803 
4804  for (; __first != __last; ++__first)
4805  if (__pred(*__first))
4806  *__first = __new_value;
4807  }
4808 
4809  /**
4810  * @brief Assign the result of a function object to each value in a
4811  * sequence.
4812  * @ingroup mutating_algorithms
4813  * @param first A forward iterator.
4814  * @param last A forward iterator.
4815  * @param gen A function object taking no arguments and returning
4816  * std::iterator_traits<_ForwardIterator>::value_type
4817  * @return generate() returns no value.
4818  *
4819  * Performs the assignment @c *i = @p gen() for each @c i in the range
4820  * @p [first,last).
4821  */
4822  template<typename _ForwardIterator, typename _Generator>
4823  void
4824  generate(_ForwardIterator __first, _ForwardIterator __last,
4825  _Generator __gen)
4826  {
4827  // concept requirements
4828  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4829  __glibcxx_function_requires(_GeneratorConcept<_Generator,
4830  typename iterator_traits<_ForwardIterator>::value_type>)
4831  __glibcxx_requires_valid_range(__first, __last);
4832 
4833  for (; __first != __last; ++__first)
4834  *__first = __gen();
4835  }
4836 
4837  /**
4838  * @brief Assign the result of a function object to each value in a
4839  * sequence.
4840  * @ingroup mutating_algorithms
4841  * @param first A forward iterator.
4842  * @param n The length of the sequence.
4843  * @param gen A function object taking no arguments and returning
4844  * std::iterator_traits<_ForwardIterator>::value_type
4845  * @return The end of the sequence, @p first+n
4846  *
4847  * Performs the assignment @c *i = @p gen() for each @c i in the range
4848  * @p [first,first+n).
4849  */
4850  template<typename _OutputIterator, typename _Size, typename _Generator>
4851  _OutputIterator
4852  generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4853  {
4854  // concept requirements
4855  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4856  // "the type returned by a _Generator"
4857  __typeof__(__gen())>)
4858 
4859  for (; __n > 0; --__n, ++__first)
4860  *__first = __gen();
4861  return __first;
4862  }
4863 
4864 
4865  /**
4866  * @brief Copy a sequence, removing consecutive duplicate values.
4867  * @ingroup mutating_algorithms
4868  * @param first An input iterator.
4869  * @param last An input iterator.
4870  * @param result An output iterator.
4871  * @return An iterator designating the end of the resulting sequence.
4872  *
4873  * Copies each element in the range @p [first,last) to the range
4874  * beginning at @p result, except that only the first element is copied
4875  * from groups of consecutive elements that compare equal.
4876  * unique_copy() is stable, so the relative order of elements that are
4877  * copied is unchanged.
4878  *
4879  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4880  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4881  *
4882  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4883  * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4884  * Assignable?
4885  */
4886  template<typename _InputIterator, typename _OutputIterator>
4887  inline _OutputIterator
4888  unique_copy(_InputIterator __first, _InputIterator __last,
4889  _OutputIterator __result)
4890  {
4891  // concept requirements
4892  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4893  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4894  typename iterator_traits<_InputIterator>::value_type>)
4895  __glibcxx_function_requires(_EqualityComparableConcept<
4896  typename iterator_traits<_InputIterator>::value_type>)
4897  __glibcxx_requires_valid_range(__first, __last);
4898 
4899  if (__first == __last)
4900  return __result;
4901  return std::__unique_copy(__first, __last, __result,
4902  std::__iterator_category(__first),
4903  std::__iterator_category(__result));
4904  }
4905 
4906  /**
4907  * @brief Copy a sequence, removing consecutive values using a predicate.
4908  * @ingroup mutating_algorithms
4909  * @param first An input iterator.
4910  * @param last An input iterator.
4911  * @param result An output iterator.
4912  * @param binary_pred A binary predicate.
4913  * @return An iterator designating the end of the resulting sequence.
4914  *
4915  * Copies each element in the range @p [first,last) to the range
4916  * beginning at @p result, except that only the first element is copied
4917  * from groups of consecutive elements for which @p binary_pred returns
4918  * true.
4919  * unique_copy() is stable, so the relative order of elements that are
4920  * copied is unchanged.
4921  *
4922  * _GLIBCXX_RESOLVE_LIB_DEFECTS
4923  * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4924  */
4925  template<typename _InputIterator, typename _OutputIterator,
4926  typename _BinaryPredicate>
4927  inline _OutputIterator
4928  unique_copy(_InputIterator __first, _InputIterator __last,
4929  _OutputIterator __result,
4930  _BinaryPredicate __binary_pred)
4931  {
4932  // concept requirements -- predicates checked later
4933  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4934  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4935  typename iterator_traits<_InputIterator>::value_type>)
4936  __glibcxx_requires_valid_range(__first, __last);
4937 
4938  if (__first == __last)
4939  return __result;
4940  return std::__unique_copy(__first, __last, __result, __binary_pred,
4941  std::__iterator_category(__first),
4942  std::__iterator_category(__result));
4943  }
4944 
4945 
4946  /**
4947  * @brief Randomly shuffle the elements of a sequence.
4948  * @ingroup mutating_algorithms
4949  * @param first A forward iterator.
4950  * @param last A forward iterator.
4951  * @return Nothing.
4952  *
4953  * Reorder the elements in the range @p [first,last) using a random
4954  * distribution, so that every possible ordering of the sequence is
4955  * equally likely.
4956  */
4957  template<typename _RandomAccessIterator>
4958  inline void
4959  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4960  {
4961  // concept requirements
4962  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4963  _RandomAccessIterator>)
4964  __glibcxx_requires_valid_range(__first, __last);
4965 
4966  if (__first != __last)
4967  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4968  std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
4969  }
4970 
4971  /**
4972  * @brief Shuffle the elements of a sequence using a random number
4973  * generator.
4974  * @ingroup mutating_algorithms
4975  * @param first A forward iterator.
4976  * @param last A forward iterator.
4977  * @param rand The RNG functor or function.
4978  * @return Nothing.
4979  *
4980  * Reorders the elements in the range @p [first,last) using @p rand to
4981  * provide a random distribution. Calling @p rand(N) for a positive
4982  * integer @p N should return a randomly chosen integer from the
4983  * range [0,N).
4984  */
4985  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4986  void
4987  random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4988  _RandomNumberGenerator& __rand)
4989  {
4990  // concept requirements
4991  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4992  _RandomAccessIterator>)
4993  __glibcxx_requires_valid_range(__first, __last);
4994 
4995  if (__first == __last)
4996  return;
4997  for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4998  std::iter_swap(__i, __first + __rand((__i - __first) + 1));
4999  }
5000 
5001 
5002  /**
5003  * @brief Move elements for which a predicate is true to the beginning
5004  * of a sequence.
5005  * @ingroup mutating_algorithms
5006  * @param first A forward iterator.
5007  * @param last A forward iterator.
5008  * @param pred A predicate functor.
5009  * @return An iterator @p middle such that @p pred(i) is true for each
5010  * iterator @p i in the range @p [first,middle) and false for each @p i
5011  * in the range @p [middle,last).
5012  *
5013  * @p pred must not modify its operand. @p partition() does not preserve
5014  * the relative ordering of elements in each group, use
5015  * @p stable_partition() if this is needed.
5016  */
5017  template<typename _ForwardIterator, typename _Predicate>
5018  inline _ForwardIterator
5019  partition(_ForwardIterator __first, _ForwardIterator __last,
5020  _Predicate __pred)
5021  {
5022  // concept requirements
5023  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5024  _ForwardIterator>)
5025  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5026  typename iterator_traits<_ForwardIterator>::value_type>)
5027  __glibcxx_requires_valid_range(__first, __last);
5028 
5029  return std::__partition(__first, __last, __pred,
5030  std::__iterator_category(__first));
5031  }
5032 
5033 
5034 
5035  /**
5036  * @brief Sort the smallest elements of a sequence.
5037  * @ingroup sorting_algorithms
5038  * @param first An iterator.
5039  * @param middle Another iterator.
5040  * @param last Another iterator.
5041  * @return Nothing.
5042  *
5043  * Sorts the smallest @p (middle-first) elements in the range
5044  * @p [first,last) and moves them to the range @p [first,middle). The
5045  * order of the remaining elements in the range @p [middle,last) is
5046  * undefined.
5047  * After the sort if @p i and @j are iterators in the range
5048  * @p [first,middle) such that @i precedes @j and @k is an iterator in
5049  * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
5050  */
5051  template<typename _RandomAccessIterator>
5052  inline void
5053  partial_sort(_RandomAccessIterator __first,
5054  _RandomAccessIterator __middle,
5055  _RandomAccessIterator __last)
5056  {
5057  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5058  _ValueType;
5059 
5060  // concept requirements
5061  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5062  _RandomAccessIterator>)
5063  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5064  __glibcxx_requires_valid_range(__first, __middle);
5065  __glibcxx_requires_valid_range(__middle, __last);
5066 
5067  std::__heap_select(__first, __middle, __last);
5068  std::sort_heap(__first, __middle);
5069  }
5070 
5071  /**
5072  * @brief Sort the smallest elements of a sequence using a predicate
5073  * for comparison.
5074  * @ingroup sorting_algorithms
5075  * @param first An iterator.
5076  * @param middle Another iterator.
5077  * @param last Another iterator.
5078  * @param comp A comparison functor.
5079  * @return Nothing.
5080  *
5081  * Sorts the smallest @p (middle-first) elements in the range
5082  * @p [first,last) and moves them to the range @p [first,middle). The
5083  * order of the remaining elements in the range @p [middle,last) is
5084  * undefined.
5085  * After the sort if @p i and @j are iterators in the range
5086  * @p [first,middle) such that @i precedes @j and @k is an iterator in
5087  * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
5088  * are both false.
5089  */
5090  template<typename _RandomAccessIterator, typename _Compare>
5091  inline void
5092  partial_sort(_RandomAccessIterator __first,
5093  _RandomAccessIterator __middle,
5094  _RandomAccessIterator __last,
5095  _Compare __comp)
5096  {
5097  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5098  _ValueType;
5099 
5100  // concept requirements
5101  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5102  _RandomAccessIterator>)
5103  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5104  _ValueType, _ValueType>)
5105  __glibcxx_requires_valid_range(__first, __middle);
5106  __glibcxx_requires_valid_range(__middle, __last);
5107 
5108  std::__heap_select(__first, __middle, __last, __comp);
5109  std::sort_heap(__first, __middle, __comp);
5110  }
5111 
5112  /**
5113  * @brief Sort a sequence just enough to find a particular position.
5114  * @ingroup sorting_algorithms
5115  * @param first An iterator.
5116  * @param nth Another iterator.
5117  * @param last Another iterator.
5118  * @return Nothing.
5119  *
5120  * Rearranges the elements in the range @p [first,last) so that @p *nth
5121  * is the same element that would have been in that position had the
5122  * whole sequence been sorted.
5123  * whole sequence been sorted. The elements either side of @p *nth are
5124  * not completely sorted, but for any iterator @i in the range
5125  * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5126  * holds that @p *j<*i is false.
5127  */
5128  template<typename _RandomAccessIterator>
5129  inline void
5130  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5131  _RandomAccessIterator __last)
5132  {
5133  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5134  _ValueType;
5135 
5136  // concept requirements
5137  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5138  _RandomAccessIterator>)
5139  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5140  __glibcxx_requires_valid_range(__first, __nth);
5141  __glibcxx_requires_valid_range(__nth, __last);
5142 
5143  if (__first == __last || __nth == __last)
5144  return;
5145 
5146  std::__introselect(__first, __nth, __last,
5147  std::__lg(__last - __first) * 2);
5148  }
5149 
5150  /**
5151  * @brief Sort a sequence just enough to find a particular position
5152  * using a predicate for comparison.
5153  * @ingroup sorting_algorithms
5154  * @param first An iterator.
5155  * @param nth Another iterator.
5156  * @param last Another iterator.
5157  * @param comp A comparison functor.
5158  * @return Nothing.
5159  *
5160  * Rearranges the elements in the range @p [first,last) so that @p *nth
5161  * is the same element that would have been in that position had the
5162  * whole sequence been sorted. The elements either side of @p *nth are
5163  * not completely sorted, but for any iterator @i in the range
5164  * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5165  * holds that @p comp(*j,*i) is false.
5166  */
5167  template<typename _RandomAccessIterator, typename _Compare>
5168  inline void
5169  nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5170  _RandomAccessIterator __last, _Compare __comp)
5171  {
5172  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5173  _ValueType;
5174 
5175  // concept requirements
5176  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5177  _RandomAccessIterator>)
5178  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5179  _ValueType, _ValueType>)
5180  __glibcxx_requires_valid_range(__first, __nth);
5181  __glibcxx_requires_valid_range(__nth, __last);
5182 
5183  if (__first == __last || __nth == __last)
5184  return;
5185 
5186  std::__introselect(__first, __nth, __last,
5187  std::__lg(__last - __first) * 2, __comp);
5188  }
5189 
5190 
5191  /**
5192  * @brief Sort the elements of a sequence.
5193  * @ingroup sorting_algorithms
5194  * @param first An iterator.
5195  * @param last Another iterator.
5196  * @return Nothing.
5197  *
5198  * Sorts the elements in the range @p [first,last) in ascending order,
5199  * such that @p *(i+1)<*i is false for each iterator @p i in the range
5200  * @p [first,last-1).
5201  *
5202  * The relative ordering of equivalent elements is not preserved, use
5203  * @p stable_sort() if this is needed.
5204  */
5205  template<typename _RandomAccessIterator>
5206  inline void
5207  sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5208  {
5209  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5210  _ValueType;
5211 
5212  // concept requirements
5213  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5214  _RandomAccessIterator>)
5215  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5216  __glibcxx_requires_valid_range(__first, __last);
5217 
5218  if (__first != __last)
5219  {
5220  std::__introsort_loop(__first, __last,
5221  std::__lg(__last - __first) * 2);
5222  std::__final_insertion_sort(__first, __last);
5223  }
5224  }
5225 
5226  /**
5227  * @brief Sort the elements of a sequence using a predicate for comparison.
5228  * @ingroup sorting_algorithms
5229  * @param first An iterator.
5230  * @param last Another iterator.
5231  * @param comp A comparison functor.
5232  * @return Nothing.
5233  *
5234  * Sorts the elements in the range @p [first,last) in ascending order,
5235  * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
5236  * range @p [first,last-1).
5237  *
5238  * The relative ordering of equivalent elements is not preserved, use
5239  * @p stable_sort() if this is needed.
5240  */
5241  template<typename _RandomAccessIterator, typename _Compare>
5242  inline void
5243  sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5244  _Compare __comp)
5245  {
5246  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5247  _ValueType;
5248 
5249  // concept requirements
5250  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5251  _RandomAccessIterator>)
5252  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5253  _ValueType>)
5254  __glibcxx_requires_valid_range(__first, __last);
5255 
5256  if (__first != __last)
5257  {
5258  std::__introsort_loop(__first, __last,
5259  std::__lg(__last - __first) * 2, __comp);
5260  std::__final_insertion_sort(__first, __last, __comp);
5261  }
5262  }
5263 
5264  /**
5265  * @brief Merges two sorted ranges.
5266  * @ingroup sorting_algorithms
5267  * @param first1 An iterator.
5268  * @param first2 Another iterator.
5269  * @param last1 Another iterator.
5270  * @param last2 Another iterator.
5271  * @param result An iterator pointing to the end of the merged range.
5272  * @return An iterator pointing to the first element "not less
5273  * than" @a val.
5274  *
5275  * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5276  * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5277  * must be sorted, and the output range must not overlap with either of
5278  * the input ranges. The sort is @e stable, that is, for equivalent
5279  * elements in the two ranges, elements from the first range will always
5280  * come before elements from the second.
5281  */
5282  template<typename _InputIterator1, typename _InputIterator2,
5283  typename _OutputIterator>
5284  _OutputIterator
5285  merge(_InputIterator1 __first1, _InputIterator1 __last1,
5286  _InputIterator2 __first2, _InputIterator2 __last2,
5287  _OutputIterator __result)
5288  {
5289  typedef typename iterator_traits<_InputIterator1>::value_type
5290  _ValueType1;
5291  typedef typename iterator_traits<_InputIterator2>::value_type
5292  _ValueType2;
5293 
5294  // concept requirements
5295  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5296  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5297  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5298  _ValueType1>)
5299  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5300  _ValueType2>)
5301  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5302  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5303  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5304 
5305  while (__first1 != __last1 && __first2 != __last2)
5306  {
5307  if (*__first2 < *__first1)
5308  {
5309  *__result = *__first2;
5310  ++__first2;
5311  }
5312  else
5313  {
5314  *__result = *__first1;
5315  ++__first1;
5316  }
5317  ++__result;
5318  }
5319  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5320  __result));
5321  }
5322 
5323  /**
5324  * @brief Merges two sorted ranges.
5325  * @ingroup sorting_algorithms
5326  * @param first1 An iterator.
5327  * @param first2 Another iterator.
5328  * @param last1 Another iterator.
5329  * @param last2 Another iterator.
5330  * @param result An iterator pointing to the end of the merged range.
5331  * @param comp A functor to use for comparisons.
5332  * @return An iterator pointing to the first element "not less
5333  * than" @a val.
5334  *
5335  * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5336  * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5337  * must be sorted, and the output range must not overlap with either of
5338  * the input ranges. The sort is @e stable, that is, for equivalent
5339  * elements in the two ranges, elements from the first range will always
5340  * come before elements from the second.
5341  *
5342  * The comparison function should have the same effects on ordering as
5343  * the function used for the initial sort.
5344  */
5345  template<typename _InputIterator1, typename _InputIterator2,
5346  typename _OutputIterator, typename _Compare>
5347  _OutputIterator
5348  merge(_InputIterator1 __first1, _InputIterator1 __last1,
5349  _InputIterator2 __first2, _InputIterator2 __last2,
5350  _OutputIterator __result, _Compare __comp)
5351  {
5352  typedef typename iterator_traits<_InputIterator1>::value_type
5353  _ValueType1;
5354  typedef typename iterator_traits<_InputIterator2>::value_type
5355  _ValueType2;
5356 
5357  // concept requirements
5358  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5359  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5360  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5361  _ValueType1>)
5362  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5363  _ValueType2>)
5364  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5365  _ValueType2, _ValueType1>)
5366  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5367  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5368 
5369  while (__first1 != __last1 && __first2 != __last2)
5370  {
5371  if (__comp(*__first2, *__first1))
5372  {
5373  *__result = *__first2;
5374  ++__first2;
5375  }
5376  else
5377  {
5378  *__result = *__first1;
5379  ++__first1;
5380  }
5381  ++__result;
5382  }
5383  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5384  __result));
5385  }
5386 
5387 
5388  /**
5389  * @brief Sort the elements of a sequence, preserving the relative order
5390  * of equivalent elements.
5391  * @ingroup sorting_algorithms
5392  * @param first An iterator.
5393  * @param last Another iterator.
5394  * @return Nothing.
5395  *
5396  * Sorts the elements in the range @p [first,last) in ascending order,
5397  * such that @p *(i+1)<*i is false for each iterator @p i in the range
5398  * @p [first,last-1).
5399  *
5400  * The relative ordering of equivalent elements is preserved, so any two
5401  * elements @p x and @p y in the range @p [first,last) such that
5402  * @p x<y is false and @p y<x is false will have the same relative
5403  * ordering after calling @p stable_sort().
5404  */
5405  template<typename _RandomAccessIterator>
5406  inline void
5407  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5408  {
5409  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5410  _ValueType;
5411  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5412  _DistanceType;
5413 
5414  // concept requirements
5415  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5416  _RandomAccessIterator>)
5417  __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5418  __glibcxx_requires_valid_range(__first, __last);
5419 
5421  __last);
5422  if (__buf.begin() == 0)
5423  std::__inplace_stable_sort(__first, __last);
5424  else
5425  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5426  _DistanceType(__buf.size()));
5427  }
5428 
5429  /**
5430  * @brief Sort the elements of a sequence using a predicate for comparison,
5431  * preserving the relative order of equivalent elements.
5432  * @ingroup sorting_algorithms
5433  * @param first An iterator.
5434  * @param last Another iterator.
5435  * @param comp A comparison functor.
5436  * @return Nothing.
5437  *
5438  * Sorts the elements in the range @p [first,last) in ascending order,
5439  * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
5440  * range @p [first,last-1).
5441  *
5442  * The relative ordering of equivalent elements is preserved, so any two
5443  * elements @p x and @p y in the range @p [first,last) such that
5444  * @p comp(x,y) is false and @p comp(y,x) is false will have the same
5445  * relative ordering after calling @p stable_sort().
5446  */
5447  template<typename _RandomAccessIterator, typename _Compare>
5448  inline void
5449  stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5450  _Compare __comp)
5451  {
5452  typedef typename iterator_traits<_RandomAccessIterator>::value_type
5453  _ValueType;
5454  typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5455  _DistanceType;
5456 
5457  // concept requirements
5458  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5459  _RandomAccessIterator>)
5460  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5461  _ValueType,
5462  _ValueType>)
5463  __glibcxx_requires_valid_range(__first, __last);
5464 
5466  __last);
5467  if (__buf.begin() == 0)
5468  std::__inplace_stable_sort(__first, __last, __comp);
5469  else
5470  std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5471  _DistanceType(__buf.size()), __comp);
5472  }
5473 
5474 
5475  /**
5476  * @brief Return the union of two sorted ranges.
5477  * @ingroup set_algorithms
5478  * @param first1 Start of first range.
5479  * @param last1 End of first range.
5480  * @param first2 Start of second range.
5481  * @param last2 End of second range.
5482  * @return End of the output range.
5483  * @ingroup set_algorithms
5484  *
5485  * This operation iterates over both ranges, copying elements present in
5486  * each range in order to the output range. Iterators increment for each
5487  * range. When the current element of one range is less than the other,
5488  * that element is copied and the iterator advanced. If an element is
5489  * contained in both ranges, the element from the first range is copied and
5490  * both ranges advance. The output range may not overlap either input
5491  * range.
5492  */
5493  template<typename _InputIterator1, typename _InputIterator2,
5494  typename _OutputIterator>
5495  _OutputIterator
5496  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5497  _InputIterator2 __first2, _InputIterator2 __last2,
5498  _OutputIterator __result)
5499  {
5500  typedef typename iterator_traits<_InputIterator1>::value_type
5501  _ValueType1;
5502  typedef typename iterator_traits<_InputIterator2>::value_type
5503  _ValueType2;
5504 
5505  // concept requirements
5506  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5507  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5508  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5509  _ValueType1>)
5510  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5511  _ValueType2>)
5512  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5513  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5514  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5515  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5516 
5517  while (__first1 != __last1 && __first2 != __last2)
5518  {
5519  if (*__first1 < *__first2)
5520  {
5521  *__result = *__first1;
5522  ++__first1;
5523  }
5524  else if (*__first2 < *__first1)
5525  {
5526  *__result = *__first2;
5527  ++__first2;
5528  }
5529  else
5530  {
5531  *__result = *__first1;
5532  ++__first1;
5533  ++__first2;
5534  }
5535  ++__result;
5536  }
5537  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5538  __result));
5539  }
5540 
5541  /**
5542  * @brief Return the union of two sorted ranges using a comparison functor.
5543  * @ingroup set_algorithms
5544  * @param first1 Start of first range.
5545  * @param last1 End of first range.
5546  * @param first2 Start of second range.
5547  * @param last2 End of second range.
5548  * @param comp The comparison functor.
5549  * @return End of the output range.
5550  * @ingroup set_algorithms
5551  *
5552  * This operation iterates over both ranges, copying elements present in
5553  * each range in order to the output range. Iterators increment for each
5554  * range. When the current element of one range is less than the other
5555  * according to @a comp, that element is copied and the iterator advanced.
5556  * If an equivalent element according to @a comp is contained in both
5557  * ranges, the element from the first range is copied and both ranges
5558  * advance. The output range may not overlap either input range.
5559  */
5560  template<typename _InputIterator1, typename _InputIterator2,
5561  typename _OutputIterator, typename _Compare>
5562  _OutputIterator
5563  set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5564  _InputIterator2 __first2, _InputIterator2 __last2,
5565  _OutputIterator __result, _Compare __comp)
5566  {
5567  typedef typename iterator_traits<_InputIterator1>::value_type
5568  _ValueType1;
5569  typedef typename iterator_traits<_InputIterator2>::value_type
5570  _ValueType2;
5571 
5572  // concept requirements
5573  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5574  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5575  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5576  _ValueType1>)
5577  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5578  _ValueType2>)
5579  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5580  _ValueType1, _ValueType2>)
5581  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5582  _ValueType2, _ValueType1>)
5583  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5584  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5585 
5586  while (__first1 != __last1 && __first2 != __last2)
5587  {
5588  if (__comp(*__first1, *__first2))
5589  {
5590  *__result = *__first1;
5591  ++__first1;
5592  }
5593  else if (__comp(*__first2, *__first1))
5594  {
5595  *__result = *__first2;
5596  ++__first2;
5597  }
5598  else
5599  {
5600  *__result = *__first1;
5601  ++__first1;
5602  ++__first2;
5603  }
5604  ++__result;
5605  }
5606  return std::copy(__first2, __last2, std::copy(__first1, __last1,
5607  __result));
5608  }
5609 
5610  /**
5611  * @brief Return the intersection of two sorted ranges.
5612  * @ingroup set_algorithms
5613  * @param first1 Start of first range.
5614  * @param last1 End of first range.
5615  * @param first2 Start of second range.
5616  * @param last2 End of second range.
5617  * @return End of the output range.
5618  * @ingroup set_algorithms
5619  *
5620  * This operation iterates over both ranges, copying elements present in
5621  * both ranges in order to the output range. Iterators increment for each
5622  * range. When the current element of one range is less than the other,
5623  * that iterator advances. If an element is contained in both ranges, the
5624  * element from the first range is copied and both ranges advance. The
5625  * output range may not overlap either input range.
5626  */
5627  template<typename _InputIterator1, typename _InputIterator2,
5628  typename _OutputIterator>
5629  _OutputIterator
5630  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5631  _InputIterator2 __first2, _InputIterator2 __last2,
5632  _OutputIterator __result)
5633  {
5634  typedef typename iterator_traits<_InputIterator1>::value_type
5635  _ValueType1;
5636  typedef typename iterator_traits<_InputIterator2>::value_type
5637  _ValueType2;
5638 
5639  // concept requirements
5640  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5641  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5642  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5643  _ValueType1>)
5644  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5645  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5646  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5647  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5648 
5649  while (__first1 != __last1 && __first2 != __last2)
5650  if (*__first1 < *__first2)
5651  ++__first1;
5652  else if (*__first2 < *__first1)
5653  ++__first2;
5654  else
5655  {
5656  *__result = *__first1;
5657  ++__first1;
5658  ++__first2;
5659  ++__result;
5660  }
5661  return __result;
5662  }
5663 
5664  /**
5665  * @brief Return the intersection of two sorted ranges using comparison
5666  * functor.
5667  * @ingroup set_algorithms
5668  * @param first1 Start of first range.
5669  * @param last1 End of first range.
5670  * @param first2 Start of second range.
5671  * @param last2 End of second range.
5672  * @param comp The comparison functor.
5673  * @return End of the output range.
5674  * @ingroup set_algorithms
5675  *
5676  * This operation iterates over both ranges, copying elements present in
5677  * both ranges in order to the output range. Iterators increment for each
5678  * range. When the current element of one range is less than the other
5679  * according to @a comp, that iterator advances. If an element is
5680  * contained in both ranges according to @a comp, the element from the
5681  * first range is copied and both ranges advance. The output range may not
5682  * overlap either input range.
5683  */
5684  template<typename _InputIterator1, typename _InputIterator2,
5685  typename _OutputIterator, typename _Compare>
5686  _OutputIterator
5687  set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5688  _InputIterator2 __first2, _InputIterator2 __last2,
5689  _OutputIterator __result, _Compare __comp)
5690  {
5691  typedef typename iterator_traits<_InputIterator1>::value_type
5692  _ValueType1;
5693  typedef typename iterator_traits<_InputIterator2>::value_type
5694  _ValueType2;
5695 
5696  // concept requirements
5697  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5698  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5699  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5700  _ValueType1>)
5701  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5702  _ValueType1, _ValueType2>)
5703  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5704  _ValueType2, _ValueType1>)
5705  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5706  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5707 
5708  while (__first1 != __last1 && __first2 != __last2)
5709  if (__comp(*__first1, *__first2))
5710  ++__first1;
5711  else if (__comp(*__first2, *__first1))
5712  ++__first2;
5713  else
5714  {
5715  *__result = *__first1;
5716  ++__first1;
5717  ++__first2;
5718  ++__result;
5719  }
5720  return __result;
5721  }
5722 
5723  /**
5724  * @brief Return the difference of two sorted ranges.
5725  * @ingroup set_algorithms
5726  * @param first1 Start of first range.
5727  * @param last1 End of first range.
5728  * @param first2 Start of second range.
5729  * @param last2 End of second range.
5730  * @return End of the output range.
5731  * @ingroup set_algorithms
5732  *
5733  * This operation iterates over both ranges, copying elements present in
5734  * the first range but not the second in order to the output range.
5735  * Iterators increment for each range. When the current element of the
5736  * first range is less than the second, that element is copied and the
5737  * iterator advances. If the current element of the second range is less,
5738  * the iterator advances, but no element is copied. If an element is
5739  * contained in both ranges, no elements are copied and both ranges
5740  * advance. The output range may not overlap either input range.
5741  */
5742  template<typename _InputIterator1, typename _InputIterator2,
5743  typename _OutputIterator>
5744  _OutputIterator
5745  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5746  _InputIterator2 __first2, _InputIterator2 __last2,
5747  _OutputIterator __result)
5748  {
5749  typedef typename iterator_traits<_InputIterator1>::value_type
5750  _ValueType1;
5751  typedef typename iterator_traits<_InputIterator2>::value_type
5752  _ValueType2;
5753 
5754  // concept requirements
5755  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5756  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5757  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5758  _ValueType1>)
5759  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5760  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5761  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5762  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5763 
5764  while (__first1 != __last1 && __first2 != __last2)
5765  if (*__first1 < *__first2)
5766  {
5767  *__result = *__first1;
5768  ++__first1;
5769  ++__result;
5770  }
5771  else if (*__first2 < *__first1)
5772  ++__first2;
5773  else
5774  {
5775  ++__first1;
5776  ++__first2;
5777  }
5778  return std::copy(__first1, __last1, __result);
5779  }
5780 
5781  /**
5782  * @brief Return the difference of two sorted ranges using comparison
5783  * functor.
5784  * @ingroup set_algorithms
5785  * @param first1 Start of first range.
5786  * @param last1 End of first range.
5787  * @param first2 Start of second range.
5788  * @param last2 End of second range.
5789  * @param comp The comparison functor.
5790  * @return End of the output range.
5791  * @ingroup set_algorithms
5792  *
5793  * This operation iterates over both ranges, copying elements present in
5794  * the first range but not the second in order to the output range.
5795  * Iterators increment for each range. When the current element of the
5796  * first range is less than the second according to @a comp, that element
5797  * is copied and the iterator advances. If the current element of the
5798  * second range is less, no element is copied and the iterator advances.
5799  * If an element is contained in both ranges according to @a comp, no
5800  * elements are copied and both ranges advance. The output range may not
5801  * overlap either input range.
5802  */
5803  template<typename _InputIterator1, typename _InputIterator2,
5804  typename _OutputIterator, typename _Compare>
5805  _OutputIterator
5806  set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5807  _InputIterator2 __first2, _InputIterator2 __last2,
5808  _OutputIterator __result, _Compare __comp)
5809  {
5810  typedef typename iterator_traits<_InputIterator1>::value_type
5811  _ValueType1;
5812  typedef typename iterator_traits<_InputIterator2>::value_type
5813  _ValueType2;
5814 
5815  // concept requirements
5816  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5817  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5818  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5819  _ValueType1>)
5820  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5821  _ValueType1, _ValueType2>)
5822  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5823  _ValueType2, _ValueType1>)
5824  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5825  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5826 
5827  while (__first1 != __last1 && __first2 != __last2)
5828  if (__comp(*__first1, *__first2))
5829  {
5830  *__result = *__first1;
5831  ++__first1;
5832  ++__result;
5833  }
5834  else if (__comp(*__first2, *__first1))
5835  ++__first2;
5836  else
5837  {
5838  ++__first1;
5839  ++__first2;
5840  }
5841  return std::copy(__first1, __last1, __result);
5842  }
5843 
5844  /**
5845  * @brief Return the symmetric difference of two sorted ranges.
5846  * @ingroup set_algorithms
5847  * @param first1 Start of first range.
5848  * @param last1 End of first range.
5849  * @param first2 Start of second range.
5850  * @param last2 End of second range.
5851  * @return End of the output range.
5852  * @ingroup set_algorithms
5853  *
5854  * This operation iterates over both ranges, copying elements present in
5855  * one range but not the other in order to the output range. Iterators
5856  * increment for each range. When the current element of one range is less
5857  * than the other, that element is copied and the iterator advances. If an
5858  * element is contained in both ranges, no elements are copied and both
5859  * ranges advance. The output range may not overlap either input range.
5860  */
5861  template<typename _InputIterator1, typename _InputIterator2,
5862  typename _OutputIterator>
5863  _OutputIterator
5864  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5865  _InputIterator2 __first2, _InputIterator2 __last2,
5866  _OutputIterator __result)
5867  {
5868  typedef typename iterator_traits<_InputIterator1>::value_type
5869  _ValueType1;
5870  typedef typename iterator_traits<_InputIterator2>::value_type
5871  _ValueType2;
5872 
5873  // concept requirements
5874  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5875  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5876  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5877  _ValueType1>)
5878  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5879  _ValueType2>)
5880  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5881  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5882  __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5883  __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5884 
5885  while (__first1 != __last1 && __first2 != __last2)
5886  if (*__first1 < *__first2)
5887  {
5888  *__result = *__first1;
5889  ++__first1;
5890  ++__result;
5891  }
5892  else if (*__first2 < *__first1)
5893  {
5894  *__result = *__first2;
5895  ++__first2;
5896  ++__result;
5897  }
5898  else
5899  {
5900  ++__first1;
5901  ++__first2;
5902  }
5903  return std::copy(__first2, __last2, std::copy(__first1,
5904  __last1, __result));
5905  }
5906 
5907  /**
5908  * @brief Return the symmetric difference of two sorted ranges using
5909  * comparison functor.
5910  * @ingroup set_algorithms
5911  * @param first1 Start of first range.
5912  * @param last1 End of first range.
5913  * @param first2 Start of second range.
5914  * @param last2 End of second range.
5915  * @param comp The comparison functor.
5916  * @return End of the output range.
5917  * @ingroup set_algorithms
5918  *
5919  * This operation iterates over both ranges, copying elements present in
5920  * one range but not the other in order to the output range. Iterators
5921  * increment for each range. When the current element of one range is less
5922  * than the other according to @a comp, that element is copied and the
5923  * iterator advances. If an element is contained in both ranges according
5924  * to @a comp, no elements are copied and both ranges advance. The output
5925  * range may not overlap either input range.
5926  */
5927  template<typename _InputIterator1, typename _InputIterator2,
5928  typename _OutputIterator, typename _Compare>
5929  _OutputIterator
5930  set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5931  _InputIterator2 __first2, _InputIterator2 __last2,
5932  _OutputIterator __result,
5933  _Compare __comp)
5934  {
5935  typedef typename iterator_traits<_InputIterator1>::value_type
5936  _ValueType1;
5937  typedef typename iterator_traits<_InputIterator2>::value_type
5938  _ValueType2;
5939 
5940  // concept requirements
5941  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5942  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5943  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5944  _ValueType1>)
5945  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5946  _ValueType2>)
5947  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5948  _ValueType1, _ValueType2>)
5949  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5950  _ValueType2, _ValueType1>)
5951  __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5952  __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5953 
5954  while (__first1 != __last1 && __first2 != __last2)
5955  if (__comp(*__first1, *__first2))
5956  {
5957  *__result = *__first1;
5958  ++__first1;
5959  ++__result;
5960  }
5961  else if (__comp(*__first2, *__first1))
5962  {
5963  *__result = *__first2;
5964  ++__first2;
5965  ++__result;
5966  }
5967  else
5968  {
5969  ++__first1;
5970  ++__first2;
5971  }
5972  return std::copy(__first2, __last2,
5973  std::copy(__first1, __last1, __result));
5974  }
5975 
5976 
5977  /**
5978  * @brief Return the minimum element in a range.
5979  * @ingroup sorting_algorithms
5980  * @param first Start of range.
5981  * @param last End of range.
5982  * @return Iterator referencing the first instance of the smallest value.
5983  */
5984  template<typename _ForwardIterator>
5985  _ForwardIterator
5986  min_element(_ForwardIterator __first, _ForwardIterator __last)
5987  {
5988  // concept requirements
5989  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5990  __glibcxx_function_requires(_LessThanComparableConcept<
5991  typename iterator_traits<_ForwardIterator>::value_type>)
5992  __glibcxx_requires_valid_range(__first, __last);
5993 
5994  if (__first == __last)
5995  return __first;
5996  _ForwardIterator __result = __first;
5997  while (++__first != __last)
5998  if (*__first < *__result)
5999  __result = __first;
6000  return __result;
6001  }
6002 
6003  /**
6004  * @brief Return the minimum element in a range using comparison functor.
6005  * @ingroup sorting_algorithms
6006  * @param first Start of range.
6007  * @param last End of range.
6008  * @param comp Comparison functor.
6009  * @return Iterator referencing the first instance of the smallest value
6010  * according to comp.
6011  */
6012  template<typename _ForwardIterator, typename _Compare>
6013  _ForwardIterator
6014  min_element(_ForwardIterator __first, _ForwardIterator __last,
6015  _Compare __comp)
6016  {
6017  // concept requirements
6018  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6019  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6020  typename iterator_traits<_ForwardIterator>::value_type,
6021  typename iterator_traits<_ForwardIterator>::value_type>)
6022  __glibcxx_requires_valid_range(__first, __last);
6023 
6024  if (__first == __last)
6025  return __first;
6026  _ForwardIterator __result = __first;
6027  while (++__first != __last)
6028  if (__comp(*__first, *__result))
6029  __result = __first;
6030  return __result;
6031  }
6032 
6033  /**
6034  * @brief Return the maximum element in a range.
6035  * @ingroup sorting_algorithms
6036  * @param first Start of range.
6037  * @param last End of range.
6038  * @return Iterator referencing the first instance of the largest value.
6039  */
6040  template<typename _ForwardIterator>
6041  _ForwardIterator
6042  max_element(_ForwardIterator __first, _ForwardIterator __last)
6043  {
6044  // concept requirements
6045  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6046  __glibcxx_function_requires(_LessThanComparableConcept<
6047  typename iterator_traits<_ForwardIterator>::value_type>)
6048  __glibcxx_requires_valid_range(__first, __last);
6049 
6050  if (__first == __last)
6051  return __first;
6052  _ForwardIterator __result = __first;
6053  while (++__first != __last)
6054  if (*__result < *__first)
6055  __result = __first;
6056  return __result;
6057  }
6058 
6059  /**
6060  * @brief Return the maximum element in a range using comparison functor.
6061  * @ingroup sorting_algorithms
6062  * @param first Start of range.
6063  * @param last End of range.
6064  * @param comp Comparison functor.
6065  * @return Iterator referencing the first instance of the largest value
6066  * according to comp.
6067  */
6068  template<typename _ForwardIterator, typename _Compare>
6069  _ForwardIterator
6070  max_element(_ForwardIterator __first, _ForwardIterator __last,
6071  _Compare __comp)
6072  {
6073  // concept requirements
6074  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6075  __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6076  typename iterator_traits<_ForwardIterator>::value_type,
6077  typename iterator_traits<_ForwardIterator>::value_type>)
6078  __glibcxx_requires_valid_range(__first, __last);
6079 
6080  if (__first == __last) return __first;
6081  _ForwardIterator __result = __first;
6082  while (++__first != __last)
6083  if (__comp(*__result, *__first))
6084  __result = __first;
6085  return __result;
6086  }
6087 
6088 _GLIBCXX_END_NESTED_NAMESPACE
6089 
6090 #endif /* _STL_ALGO_H */
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
Definition: stl_algo.h:761
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:3067
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
size_type size() const
As per Table mumble.
Definition: stl_tempbuf.h:141
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
Definition: stl_algo.h:1503
_BidirectionalIterator __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag)
This is a helper function...
Definition: stl_algo.h:1747
_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __comp)
Find last matching subsequence in a sequence using a predicate.
Definition: stl_algo.h:710
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
This is a helper function for the sort routines.
Definition: stl_algo.h:1900
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp __pivot, _Compare __comp)
This is a helper function...
Definition: stl_algo.h:2224
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
Definition: stl_heap.h:413
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:2966
_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, _Integer __count, const _Tp &__val, _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
Definition: stl_algo.h:465
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2)
This is a helper function for the merge routines.
Definition: stl_algo.h:3023
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67
_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Finds the first position in which val could be inserted without changing the ordering.
Definition: stl_algo.h:2471
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:2154
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
Definition: stl_algobase.h:158
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison.
Definition: stl_algo.h:5243
_RandomAccessIterator __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred, random_access_iterator_tag)
This is an overload used by find_if_not() for the RAI case.
Definition: stl_algo.h:274
Bidirectional iterators support a superset of forward iterator operations.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
Definition: stl_algobase.h:117
_OutputIterator merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Merges two sorted ranges.
Definition: stl_algo.h:5348
void inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp)
Merges two sorted ranges in place.
Definition: stl_algo.h:3185
_Function for_each(_InputIterator __first, _InputIterator __last, _Function __f)
Apply a function to every element of a sequence.
Definition: stl_algo.h:4194
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
Definition: stl_algo.h:3929
void __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, random_access_iterator_tag)
This is a helper function for the rotate algorithm.
Definition: stl_algo.h:1583
_ForwardIterator __inplace_stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len)
This is a helper function...
Definition: stl_algo.h:1777
_RandomAccessIterator partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
Copy the smallest elements of a sequence using a predicate for comparison.
Definition: stl_algo.h:2011
_OutputIterator unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
Copy a sequence, removing consecutive values using a predicate.
Definition: stl_algo.h:4928
_ForwardIterator stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Move elements for which a predicate is true to the beginning of a sequence, preserving relative order...
Definition: stl_algo.h:1863
_ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
Definition: stl_algo.h:6014
_OutputIterator replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred, const _Tp &__new_value)
Copy a sequence, replacing each value for which a predicate returns true with another value...
Definition: stl_algo.h:3842
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit)
This is a helper function for the sort routine.
Definition: stl_algo.h:2245
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp __pivot)
This is a helper function...
Definition: stl_algo.h:2204
bool is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks whether the sequence is partitioned.
Definition: stl_algo.h:817
_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp &__val, _BinaryPredicate __binary_pred)
Search a sequence for a number of consecutive values using a predicate.
Definition: stl_algo.h:4650
_BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Copies the range [first,last) into result.
Definition: stl_algobase.h:628
_ForwardIterator unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred)
Remove consecutive values from a sequence using a predicate.
Definition: stl_algo.h:1223
Marking input iterators.
bool any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for at least an element of a sequence.
Definition: stl_algo.h:778
const _Tp & __median(const _Tp &__a, const _Tp &__b, const _Tp &__c, _Compare __comp)
Find the median of three values using a predicate for comparison.
Definition: stl_algo.h:119
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the sort routine.
Definition: stl_algo.h:2173
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find_if_not() for the Input Iterator case.
Definition: stl_algo.h:263
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:209
size_type requested_size() const
Returns the size requested by the constructor; may be >size().
Definition: stl_tempbuf.h:146
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
pair< _ForwardIterator, _ForwardIterator > equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Finds the largest subrange in which val could be inserted at any place in it without changing the ord...
Definition: stl_algo.h:2688
_ForwardIterator __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __binary_pred, input_iterator_tag, forward_iterator_tag)
Definition: stl_algo.h:1380
_BidirectionalIterator3 __merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result)
This is a helper function for the merge routines.
Definition: stl_algo.h:2807
_OutputIterator set_union(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the union of two sorted ranges using a comparison functor.
Definition: stl_algo.h:5563
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function...
Definition: stl_algo.h:1802
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
Definition: stl_algo.h:1913
bool is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines whether the elements of a sequence are sorted according to a comparison functor...
Definition: stl_algo.h:3886
pair< _OutputIterator1, _OutputIterator2 > partition_copy(_InputIterator __first, _InputIterator __last, _OutputIterator1 __out_true, _OutputIterator2 __out_false, _Predicate __pred)
Copy the elements of a sequence to separate output sequences depending on the truth value of a predic...
Definition: stl_algo.h:1051
void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:2079
_OutputIterator set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the intersection of two sorted ranges using comparison functor.
Definition: stl_algo.h:5687
void __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
Definition: stl_algo.h:1517
void rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
Definition: stl_algo.h:1671
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, forward_iterator_tag, output_iterator_tag)
Definition: stl_algo.h:1255
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
Definition: stl_algo.h:2878
_ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp &__val, std::forward_iterator_tag)
Definition: stl_algo.h:340
_RandomAccessIterator __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred, random_access_iterator_tag)
This is an overload used by find_if() for the RAI case.
Definition: stl_algo.h:214
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the sort routine.
Definition: stl_algo.h:2096
_RandomAccessIterator __find(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp &__val, random_access_iterator_tag)
This is an overload used by find() for the RAI case.
Definition: stl_algo.h:166
_OutputIterator set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the symmetric difference of two sorted ranges using comparison functor.
Definition: stl_algo.h:5930
const _Tp & __median(const _Tp &__a, const _Tp &__b, const _Tp &__c)
Find the median of three values.
Definition: stl_algo.h:85
void generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
Assign the result of a function object to each value in a sequence.
Definition: stl_algo.h:4824
iterator_traits< _InputIterator >::difference_type count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Count the elements of a sequence for which a predicate is true.
Definition: stl_algo.h:4428
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
Definition: stl_algo.h:2910
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort a heap using comparison functor.
Definition: stl_heap.h:481
_ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Finds the last position in which val could be inserted without changing the ordering.
Definition: stl_algo.h:2571
Marking output iterators.
bool includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
Determines whether all elements of a sequence exists in a range using comparison. ...
Definition: stl_algo.h:3520
void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomNumberGenerator &__rand)
Shuffle the elements of a sequence using a random number generator.
Definition: stl_algo.h:4987
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:2188
bool next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
Permute range into the next "dictionary" ordering using comparison functor.
Definition: stl_algo.h:3631
_OutputIterator transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _OutputIterator __result, _BinaryOperation __binary_op)
Perform an operation on corresponding elements of two sequences.
Definition: stl_algo.h:4728
_ForwardIterator remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Remove elements from a sequence using a predicate.
Definition: stl_algo.h:1143
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the stable sorting routines.
Definition: stl_algo.h:3409
_BidirectionalIterator3 __merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the merge routines.
Definition: stl_algo.h:2842
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
Definition: stl_algo.h:6070
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the sort routine.
Definition: stl_algo.h:2141
bool prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
Permute range into the previous "dictionary" ordering using comparison functor.
Definition: stl_algo.h:3744
_OutputIterator rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
Copy a sequence, rotating its elements.
Definition: stl_algo.h:1705
_OutputIterator copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
Copies the range [first,first+n) into [result,result+n).
Definition: stl_algo.h:1022
_OutputIterator replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp &__old_value, const _Tp &__new_value)
Copy a sequence, replacing each element of one value with another value.
Definition: stl_algo.h:3804
pair< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
Definition: stl_algo.h:4072
_ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred)
Find two adjacent values in a sequence using a predicate.
Definition: stl_algo.h:4371
_InputIterator find_first_of(_InputIterator __first1, _InputIterator __last1, _ForwardIterator __first2, _ForwardIterator __last2, _BinaryPredicate __comp)
Find element from a set in a sequence using a predicate.
Definition: stl_algo.h:4308
iterator begin()
As per Table mumble.
Definition: stl_tempbuf.h:151
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:186
_OutputIterator generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
Assign the result of a function object to each value in a sequence.
Definition: stl_algo.h:4852
_OutputIterator copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
Copy the elements of a sequence for which a predicate is true.
Definition: stl_algo.h:965
void __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
Definition: stl_algo.h:1423
_Size __lg(_Size __n)
This is a helper function for the sort routines. Precondition: __n > 0.
Definition: stl_algo.h:2310
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:2277
pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
Definition: stl_algo.h:3958
iterator_traits< _InputIterator >::difference_type count(_InputIterator __first, _InputIterator __last, const _Tp &__value)
Count the number of copies of a value in a sequence.
Definition: stl_algo.h:4403
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
Definition: stl_algo.h:793
void reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
Reverse a sequence.
Definition: stl_algo.h:1451
Random-access iterators support a superset of bidirectional iterator operations.
bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Determines whether an element exists in a range.
Definition: stl_algo.h:2782
_OutputIterator set_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the difference of two sorted ranges using comparison functor.
Definition: stl_algo.h:5806
void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison, preserving the relative order of eq...
Definition: stl_algo.h:5449
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate)
Search a sequence for a matching sub-sequence using a predicate.
Definition: stl_algo.h:4540
_InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find_if() for the Input Iterator case.
Definition: stl_algo.h:155
bool all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is true for all the elements of a sequence.
Definition: stl_algo.h:744
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
Definition: stl_algo.h:3428
_InputIterator __find(_InputIterator __first, _InputIterator __last, const _Tp &__val, input_iterator_tag)
This is an overload used by find() for the Input Iterator case.
Definition: stl_algo.h:144
void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
Sort a sequence just enough to find a particular position using a predicate for comparison.
Definition: stl_algo.h:5169
_InputIterator find(_InputIterator __first, _InputIterator __last, const _Tp &__val)
Find the first occurrence of a value in a sequence.
Definition: stl_algo.h:4215
_OutputIterator reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
Copy a sequence, reversing its elements.
Definition: stl_algo.h:1478
Forward iterators support a superset of input iterator operations.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
This is a helper function for the sort routine.
Definition: stl_algo.h:2063
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Definition: stl_algo.h:2119
_OutputIterator remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
Copy a sequence, removing elements for which a predicate is true.
Definition: stl_algo.h:926
_ForwardIterator partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Move elements for which a predicate is true to the beginning of a sequence.
Definition: stl_algo.h:5019
void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
Sort the smallest elements of a sequence using a predicate for comparison.
Definition: stl_algo.h:5092
void replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp &__new_value)
Replace each value in a sequence for which a predicate returns true with another value.
Definition: stl_algo.h:4792
_OutputIterator remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp &__value)
Copy a sequence, removing elements of a given value.
Definition: stl_algo.h:888
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
Definition: stl_algo.h:4239
_ForwardIterator partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Find the partition point of a partitioned range.
Definition: stl_algo.h:835
void replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__old_value, const _Tp &__new_value)
Replace each occurrence of one value in a sequence with another value.
Definition: stl_algo.h:4760
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
Definition: stl_algo.h:1722
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
Definition: stl_algo.h:1403