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