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