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