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