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