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