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