Line data Source code
1 : // Algorithm implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2019 Free Software Foundation, Inc.
4 : //
5 : // This file is part of the GNU ISO C++ Library. This library is free
6 : // software; you can redistribute it and/or modify it under the
7 : // terms of the GNU General Public License as published by the
8 : // Free Software Foundation; either version 3, or (at your option)
9 : // any later version.
10 :
11 : // This library is distributed in the hope that it will be useful,
12 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : // GNU General Public License for more details.
15 :
16 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /*
26 : *
27 : * Copyright (c) 1994
28 : * Hewlett-Packard Company
29 : *
30 : * Permission to use, copy, modify, distribute and sell this software
31 : * and its documentation for any purpose is hereby granted without fee,
32 : * provided that the above copyright notice appear in all copies and
33 : * that both that copyright notice and this permission notice appear
34 : * in supporting documentation. Hewlett-Packard Company makes no
35 : * representations about the suitability of this software for any
36 : * purpose. It is provided "as is" without express or implied warranty.
37 : *
38 : *
39 : * Copyright (c) 1996
40 : * Silicon Graphics Computer Systems, Inc.
41 : *
42 : * Permission to use, copy, modify, distribute and sell this software
43 : * and its documentation for any purpose is hereby granted without fee,
44 : * provided that the above copyright notice appear in all copies and
45 : * that both that copyright notice and this permission notice appear
46 : * in supporting documentation. Silicon Graphics makes no
47 : * representations about the suitability of this software for any
48 : * purpose. It is provided "as is" without express or implied warranty.
49 : */
50 :
51 : /** @file bits/stl_algo.h
52 : * This is an internal header file, included by other library headers.
53 : * Do not attempt to use it directly. @headername{algorithm}
54 : */
55 :
56 : #ifndef _STL_ALGO_H
57 : #define _STL_ALGO_H 1
58 :
59 : #include <cstdlib> // for rand
60 : #include <bits/algorithmfwd.h>
61 : #include <bits/stl_heap.h>
62 : #include <bits/stl_tempbuf.h> // for _Temporary_buffer
63 : #include <bits/predefined_ops.h>
64 :
65 : #if __cplusplus >= 201103L
66 : #include <bits/uniform_int_dist.h>
67 : #endif
68 :
69 : // See concept_check.h for the __glibcxx_*_requires macros.
70 :
71 : namespace std _GLIBCXX_VISIBILITY(default)
72 : {
73 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
74 :
75 : /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
76 : template<typename _Iterator, typename _Compare>
77 : void
78 0 : __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
79 : _Iterator __c, _Compare __comp)
80 : {
81 0 : if (__comp(__a, __b))
82 : {
83 0 : if (__comp(__b, __c))
84 0 : std::iter_swap(__result, __b);
85 0 : else if (__comp(__a, __c))
86 0 : std::iter_swap(__result, __c);
87 : else
88 0 : std::iter_swap(__result, __a);
89 : }
90 0 : else if (__comp(__a, __c))
91 0 : std::iter_swap(__result, __a);
92 0 : else if (__comp(__b, __c))
93 0 : std::iter_swap(__result, __c);
94 : else
95 0 : std::iter_swap(__result, __b);
96 0 : }
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 24999 : __find_if(_InputIterator __first, _InputIterator __last,
102 : _Predicate __pred, input_iterator_tag)
103 : {
104 269912 : while (__first != __last && !__pred(__first))
105 291859 : ++__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 115819613 : __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
113 : _Predicate __pred, random_access_iterator_tag)
114 : {
115 : typename iterator_traits<_RandomAccessIterator>::difference_type
116 115819613 : __trip_count = (__last - __first) >> 2;
117 :
118 1235297345 : for (; __trip_count > 0; --__trip_count)
119 : {
120 1121132596 : if (__pred(__first))
121 334923 : return __first;
122 1120797362 : ++__first;
123 :
124 1120797369 : if (__pred(__first))
125 334924 : return __first;
126 1120463117 : ++__first;
127 :
128 1120463127 : if (__pred(__first))
129 335059 : return __first;
130 1120127779 : ++__first;
131 :
132 1120127795 : if (__pred(__first))
133 649420 : return __first;
134 1119477728 : ++__first;
135 : }
136 :
137 114165295 : switch (__last - __first)
138 : {
139 12130182 : case 3:
140 12130184 : if (__pred(__first))
141 304637 : return __first;
142 16828188 : ++__first;
143 16828188 : case 2:
144 16828194 : if (__pred(__first))
145 633818 : return __first;
146 66768330 : ++__first;
147 66768330 : case 1:
148 66768472 : if (__pred(__first))
149 1869700 : return __first;
150 111357129 : ++__first;
151 111357129 : case 0:
152 : default:
153 111357129 : return __last;
154 : }
155 : }
156 :
157 : template<typename _Iterator, typename _Predicate>
158 : inline _Iterator
159 115844549 : __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
160 : {
161 115844549 : return __find_if(__first, __last, __pred,
162 0 : 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 0 : __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206 : _ForwardIterator2 __first2, _ForwardIterator2 __last2,
207 : _BinaryPredicate __predicate)
208 : {
209 : // Test for empty ranges
210 0 : if (__first1 == __last1 || __first2 == __last2)
211 0 : return __first1;
212 :
213 : // Test for a pattern of length 1.
214 0 : _ForwardIterator2 __p1(__first2);
215 0 : if (++__p1 == __last2)
216 0 : return std::__find_if(__first1, __last1,
217 : __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
218 :
219 : // General case.
220 0 : _ForwardIterator2 __p;
221 0 : _ForwardIterator1 __current = __first1;
222 :
223 : for (;;)
224 : {
225 : __first1 =
226 0 : std::__find_if(__first1, __last1,
227 : __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
228 :
229 0 : if (__first1 == __last1)
230 0 : return __last1;
231 :
232 0 : __p = __p1;
233 0 : __current = __first1;
234 0 : if (++__current == __last1)
235 0 : return __last1;
236 :
237 0 : while (__predicate(__current, __p))
238 : {
239 0 : if (++__p == __last2)
240 0 : return __first1;
241 0 : if (++__current == __last1)
242 0 : return __last1;
243 : }
244 0 : ++__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 true for at least one 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 0 : __remove_copy_if(_InputIterator __first, _InputIterator __last,
643 : _OutputIterator __result, _Predicate __pred)
644 : {
645 0 : for (; __first != __last; ++__first)
646 0 : if (!__pred(__first))
647 : {
648 0 : *__result = *__first;
649 0 : ++__result;
650 : }
651 0 : 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 0 : 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 0 : 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 : if (__n <= 0)
807 : return __result;
808 :
809 : __glibcxx_requires_can_increment(__first, __n);
810 : __glibcxx_requires_can_increment(__result, __n);
811 :
812 : return std::__copy_n(__first, __n, __result,
813 : std::__iterator_category(__first));
814 : }
815 :
816 : /**
817 : * @brief Copy the elements of a sequence to separate output sequences
818 : * depending on the truth value of a predicate.
819 : * @ingroup mutating_algorithms
820 : * @param __first An input iterator.
821 : * @param __last An input iterator.
822 : * @param __out_true An output iterator.
823 : * @param __out_false An output iterator.
824 : * @param __pred A predicate.
825 : * @return A pair designating the ends of the resulting sequences.
826 : *
827 : * Copies each element in the range @p [__first,__last) for which
828 : * @p __pred returns true to the range beginning at @p out_true
829 : * and each element for which @p __pred returns false to @p __out_false.
830 : */
831 : template<typename _InputIterator, typename _OutputIterator1,
832 : typename _OutputIterator2, typename _Predicate>
833 : pair<_OutputIterator1, _OutputIterator2>
834 : partition_copy(_InputIterator __first, _InputIterator __last,
835 : _OutputIterator1 __out_true, _OutputIterator2 __out_false,
836 : _Predicate __pred)
837 : {
838 : // concept requirements
839 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
840 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
841 : typename iterator_traits<_InputIterator>::value_type>)
842 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
843 : typename iterator_traits<_InputIterator>::value_type>)
844 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
845 : typename iterator_traits<_InputIterator>::value_type>)
846 : __glibcxx_requires_valid_range(__first, __last);
847 :
848 : for (; __first != __last; ++__first)
849 : if (__pred(*__first))
850 : {
851 : *__out_true = *__first;
852 : ++__out_true;
853 : }
854 : else
855 : {
856 : *__out_false = *__first;
857 : ++__out_false;
858 : }
859 :
860 : return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
861 : }
862 : #endif
863 :
864 : template<typename _ForwardIterator, typename _Predicate>
865 : _ForwardIterator
866 758 : __remove_if(_ForwardIterator __first, _ForwardIterator __last,
867 : _Predicate __pred)
868 : {
869 758 : __first = std::__find_if(__first, __last, __pred);
870 758 : if (__first == __last)
871 731 : return __first;
872 27 : _ForwardIterator __result = __first;
873 118 : ++__first;
874 118 : for (; __first != __last; ++__first)
875 91 : if (!__pred(__first))
876 : {
877 61 : *__result = _GLIBCXX_MOVE(*__first);
878 91 : ++__result;
879 : }
880 27 : return __result;
881 : }
882 :
883 : /**
884 : * @brief Remove elements from a sequence.
885 : * @ingroup mutating_algorithms
886 : * @param __first An input iterator.
887 : * @param __last An input iterator.
888 : * @param __value The value to be removed.
889 : * @return An iterator designating the end of the resulting sequence.
890 : *
891 : * All elements equal to @p __value are removed from the range
892 : * @p [__first,__last).
893 : *
894 : * remove() is stable, so the relative order of elements that are
895 : * not removed is unchanged.
896 : *
897 : * Elements between the end of the resulting sequence and @p __last
898 : * are still present, but their value is unspecified.
899 : */
900 : template<typename _ForwardIterator, typename _Tp>
901 : inline _ForwardIterator
902 714 : remove(_ForwardIterator __first, _ForwardIterator __last,
903 : const _Tp& __value)
904 : {
905 : // concept requirements
906 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
907 : _ForwardIterator>)
908 : __glibcxx_function_requires(_EqualOpConcept<
909 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
910 : __glibcxx_requires_valid_range(__first, __last);
911 :
912 714 : return std::__remove_if(__first, __last,
913 : __gnu_cxx::__ops::__iter_equals_val(__value));
914 : }
915 :
916 : /**
917 : * @brief Remove elements from a sequence using a predicate.
918 : * @ingroup mutating_algorithms
919 : * @param __first A forward iterator.
920 : * @param __last A forward iterator.
921 : * @param __pred A predicate.
922 : * @return An iterator designating the end of the resulting sequence.
923 : *
924 : * All elements for which @p __pred returns true are removed from the range
925 : * @p [__first,__last).
926 : *
927 : * remove_if() is stable, so the relative order of elements that are
928 : * not removed is unchanged.
929 : *
930 : * Elements between the end of the resulting sequence and @p __last
931 : * are still present, but their value is unspecified.
932 : */
933 : template<typename _ForwardIterator, typename _Predicate>
934 : inline _ForwardIterator
935 44 : remove_if(_ForwardIterator __first, _ForwardIterator __last,
936 : _Predicate __pred)
937 : {
938 : // concept requirements
939 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
940 : _ForwardIterator>)
941 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
942 : typename iterator_traits<_ForwardIterator>::value_type>)
943 : __glibcxx_requires_valid_range(__first, __last);
944 :
945 44 : return std::__remove_if(__first, __last,
946 : __gnu_cxx::__ops::__pred_iter(__pred));
947 : }
948 :
949 : template<typename _ForwardIterator, typename _BinaryPredicate>
950 : _ForwardIterator
951 4779 : __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
952 : _BinaryPredicate __binary_pred)
953 : {
954 4779 : if (__first == __last)
955 : return __last;
956 : _ForwardIterator __next = __first;
957 9570 : while (++__next != __last)
958 : {
959 4791 : if (__binary_pred(__first, __next))
960 : return __first;
961 : __first = __next;
962 : }
963 : return __last;
964 : }
965 :
966 : template<typename _ForwardIterator, typename _BinaryPredicate>
967 : _ForwardIterator
968 4779 : __unique(_ForwardIterator __first, _ForwardIterator __last,
969 : _BinaryPredicate __binary_pred)
970 : {
971 : // Skip the beginning, if already unique.
972 9558 : __first = std::__adjacent_find(__first, __last, __binary_pred);
973 4779 : if (__first == __last)
974 4779 : return __last;
975 :
976 : // Do the real copy work.
977 0 : _ForwardIterator __dest = __first;
978 0 : ++__first;
979 0 : while (++__first != __last)
980 0 : if (!__binary_pred(__dest, __first))
981 0 : *++__dest = _GLIBCXX_MOVE(*__first);
982 0 : return ++__dest;
983 : }
984 :
985 : /**
986 : * @brief Remove consecutive duplicate values from a sequence.
987 : * @ingroup mutating_algorithms
988 : * @param __first A forward iterator.
989 : * @param __last A forward iterator.
990 : * @return An iterator designating the end of the resulting sequence.
991 : *
992 : * Removes all but the first element from each group of consecutive
993 : * values that compare equal.
994 : * unique() is stable, so the relative order of elements that are
995 : * not removed is unchanged.
996 : * Elements between the end of the resulting sequence and @p __last
997 : * are still present, but their value is unspecified.
998 : */
999 : template<typename _ForwardIterator>
1000 : inline _ForwardIterator
1001 4779 : unique(_ForwardIterator __first, _ForwardIterator __last)
1002 : {
1003 : // concept requirements
1004 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1005 : _ForwardIterator>)
1006 : __glibcxx_function_requires(_EqualityComparableConcept<
1007 : typename iterator_traits<_ForwardIterator>::value_type>)
1008 : __glibcxx_requires_valid_range(__first, __last);
1009 :
1010 4779 : return std::__unique(__first, __last,
1011 : __gnu_cxx::__ops::__iter_equal_to_iter());
1012 : }
1013 :
1014 : /**
1015 : * @brief Remove consecutive values from a sequence using a predicate.
1016 : * @ingroup mutating_algorithms
1017 : * @param __first A forward iterator.
1018 : * @param __last A forward iterator.
1019 : * @param __binary_pred A binary predicate.
1020 : * @return An iterator designating the end of the resulting sequence.
1021 : *
1022 : * Removes all but the first element from each group of consecutive
1023 : * values for which @p __binary_pred returns true.
1024 : * unique() is stable, so the relative order of elements that are
1025 : * not removed is unchanged.
1026 : * Elements between the end of the resulting sequence and @p __last
1027 : * are still present, but their value is unspecified.
1028 : */
1029 : template<typename _ForwardIterator, typename _BinaryPredicate>
1030 : inline _ForwardIterator
1031 0 : unique(_ForwardIterator __first, _ForwardIterator __last,
1032 : _BinaryPredicate __binary_pred)
1033 : {
1034 : // concept requirements
1035 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1036 : _ForwardIterator>)
1037 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1038 : typename iterator_traits<_ForwardIterator>::value_type,
1039 : typename iterator_traits<_ForwardIterator>::value_type>)
1040 : __glibcxx_requires_valid_range(__first, __last);
1041 :
1042 0 : return std::__unique(__first, __last,
1043 : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1044 : }
1045 :
1046 : /**
1047 : * This is an uglified
1048 : * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1049 : * _BinaryPredicate)
1050 : * overloaded for forward iterators and output iterator as result.
1051 : */
1052 : template<typename _ForwardIterator, typename _OutputIterator,
1053 : typename _BinaryPredicate>
1054 : _OutputIterator
1055 : __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1056 : _OutputIterator __result, _BinaryPredicate __binary_pred,
1057 : forward_iterator_tag, output_iterator_tag)
1058 : {
1059 : // concept requirements -- iterators already checked
1060 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1061 : typename iterator_traits<_ForwardIterator>::value_type,
1062 : typename iterator_traits<_ForwardIterator>::value_type>)
1063 :
1064 : _ForwardIterator __next = __first;
1065 : *__result = *__first;
1066 : while (++__next != __last)
1067 : if (!__binary_pred(__first, __next))
1068 : {
1069 : __first = __next;
1070 : *++__result = *__first;
1071 : }
1072 : return ++__result;
1073 : }
1074 :
1075 : /**
1076 : * This is an uglified
1077 : * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1078 : * _BinaryPredicate)
1079 : * overloaded for input iterators and output iterator as result.
1080 : */
1081 : template<typename _InputIterator, typename _OutputIterator,
1082 : typename _BinaryPredicate>
1083 : _OutputIterator
1084 : __unique_copy(_InputIterator __first, _InputIterator __last,
1085 : _OutputIterator __result, _BinaryPredicate __binary_pred,
1086 : input_iterator_tag, output_iterator_tag)
1087 : {
1088 : // concept requirements -- iterators already checked
1089 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1090 : typename iterator_traits<_InputIterator>::value_type,
1091 : typename iterator_traits<_InputIterator>::value_type>)
1092 :
1093 : typename iterator_traits<_InputIterator>::value_type __value = *__first;
1094 : __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1095 : __rebound_pred
1096 : = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1097 : *__result = __value;
1098 : while (++__first != __last)
1099 : if (!__rebound_pred(__first, __value))
1100 : {
1101 : __value = *__first;
1102 : *++__result = __value;
1103 : }
1104 : return ++__result;
1105 : }
1106 :
1107 : /**
1108 : * This is an uglified
1109 : * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1110 : * _BinaryPredicate)
1111 : * overloaded for input iterators and forward iterator as result.
1112 : */
1113 : template<typename _InputIterator, typename _ForwardIterator,
1114 : typename _BinaryPredicate>
1115 : _ForwardIterator
1116 : __unique_copy(_InputIterator __first, _InputIterator __last,
1117 : _ForwardIterator __result, _BinaryPredicate __binary_pred,
1118 : input_iterator_tag, forward_iterator_tag)
1119 : {
1120 : // concept requirements -- iterators already checked
1121 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1122 : typename iterator_traits<_ForwardIterator>::value_type,
1123 : typename iterator_traits<_InputIterator>::value_type>)
1124 : *__result = *__first;
1125 : while (++__first != __last)
1126 : if (!__binary_pred(__result, __first))
1127 : *++__result = *__first;
1128 : return ++__result;
1129 : }
1130 :
1131 : /**
1132 : * This is an uglified reverse(_BidirectionalIterator,
1133 : * _BidirectionalIterator)
1134 : * overloaded for bidirectional iterators.
1135 : */
1136 : template<typename _BidirectionalIterator>
1137 : void
1138 : __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1139 : bidirectional_iterator_tag)
1140 : {
1141 : while (true)
1142 : if (__first == __last || __first == --__last)
1143 : return;
1144 : else
1145 : {
1146 : std::iter_swap(__first, __last);
1147 : ++__first;
1148 : }
1149 : }
1150 :
1151 : /**
1152 : * This is an uglified reverse(_BidirectionalIterator,
1153 : * _BidirectionalIterator)
1154 : * overloaded for random access iterators.
1155 : */
1156 : template<typename _RandomAccessIterator>
1157 : void
1158 0 : __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1159 : random_access_iterator_tag)
1160 : {
1161 0 : if (__first == __last)
1162 : return;
1163 0 : --__last;
1164 0 : while (__first < __last)
1165 : {
1166 0 : std::iter_swap(__first, __last);
1167 0 : ++__first;
1168 0 : --__last;
1169 : }
1170 : }
1171 :
1172 : /**
1173 : * @brief Reverse a sequence.
1174 : * @ingroup mutating_algorithms
1175 : * @param __first A bidirectional iterator.
1176 : * @param __last A bidirectional iterator.
1177 : * @return reverse() returns no value.
1178 : *
1179 : * Reverses the order of the elements in the range @p [__first,__last),
1180 : * so that the first element becomes the last etc.
1181 : * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1182 : * swaps @p *(__first+i) and @p *(__last-(i+1))
1183 : */
1184 : template<typename _BidirectionalIterator>
1185 : inline void
1186 0 : reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1187 : {
1188 : // concept requirements
1189 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1190 : _BidirectionalIterator>)
1191 : __glibcxx_requires_valid_range(__first, __last);
1192 0 : std::__reverse(__first, __last, std::__iterator_category(__first));
1193 : }
1194 :
1195 : /**
1196 : * @brief Copy a sequence, reversing its elements.
1197 : * @ingroup mutating_algorithms
1198 : * @param __first A bidirectional iterator.
1199 : * @param __last A bidirectional iterator.
1200 : * @param __result An output iterator.
1201 : * @return An iterator designating the end of the resulting sequence.
1202 : *
1203 : * Copies the elements in the range @p [__first,__last) to the
1204 : * range @p [__result,__result+(__last-__first)) such that the
1205 : * order of the elements is reversed. For every @c i such that @p
1206 : * 0<=i<=(__last-__first), @p reverse_copy() performs the
1207 : * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1208 : * The ranges @p [__first,__last) and @p
1209 : * [__result,__result+(__last-__first)) must not overlap.
1210 : */
1211 : template<typename _BidirectionalIterator, typename _OutputIterator>
1212 : _OutputIterator
1213 : reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1214 : _OutputIterator __result)
1215 : {
1216 : // concept requirements
1217 : __glibcxx_function_requires(_BidirectionalIteratorConcept<
1218 : _BidirectionalIterator>)
1219 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1220 : typename iterator_traits<_BidirectionalIterator>::value_type>)
1221 : __glibcxx_requires_valid_range(__first, __last);
1222 :
1223 : while (__first != __last)
1224 : {
1225 : --__last;
1226 : *__result = *__last;
1227 : ++__result;
1228 : }
1229 : return __result;
1230 : }
1231 :
1232 : /**
1233 : * This is a helper function for the rotate algorithm specialized on RAIs.
1234 : * It returns the greatest common divisor of two integer values.
1235 : */
1236 : template<typename _EuclideanRingElement>
1237 : _EuclideanRingElement
1238 : __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1239 : {
1240 : while (__n != 0)
1241 : {
1242 : _EuclideanRingElement __t = __m % __n;
1243 : __m = __n;
1244 : __n = __t;
1245 : }
1246 : return __m;
1247 : }
1248 :
1249 : inline namespace _V2
1250 : {
1251 :
1252 : /// This is a helper function for the rotate algorithm.
1253 : template<typename _ForwardIterator>
1254 : _ForwardIterator
1255 : __rotate(_ForwardIterator __first,
1256 : _ForwardIterator __middle,
1257 : _ForwardIterator __last,
1258 : forward_iterator_tag)
1259 : {
1260 : if (__first == __middle)
1261 : return __last;
1262 : else if (__last == __middle)
1263 : return __first;
1264 :
1265 : _ForwardIterator __first2 = __middle;
1266 : do
1267 : {
1268 : std::iter_swap(__first, __first2);
1269 : ++__first;
1270 : ++__first2;
1271 : if (__first == __middle)
1272 : __middle = __first2;
1273 : }
1274 : while (__first2 != __last);
1275 :
1276 : _ForwardIterator __ret = __first;
1277 :
1278 : __first2 = __middle;
1279 :
1280 : while (__first2 != __last)
1281 : {
1282 : std::iter_swap(__first, __first2);
1283 : ++__first;
1284 : ++__first2;
1285 : if (__first == __middle)
1286 : __middle = __first2;
1287 : else if (__first2 == __last)
1288 : __first2 = __middle;
1289 : }
1290 : return __ret;
1291 : }
1292 :
1293 : /// This is a helper function for the rotate algorithm.
1294 : template<typename _BidirectionalIterator>
1295 : _BidirectionalIterator
1296 : __rotate(_BidirectionalIterator __first,
1297 : _BidirectionalIterator __middle,
1298 : _BidirectionalIterator __last,
1299 : bidirectional_iterator_tag)
1300 : {
1301 : // concept requirements
1302 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1303 : _BidirectionalIterator>)
1304 :
1305 : if (__first == __middle)
1306 : return __last;
1307 : else if (__last == __middle)
1308 : return __first;
1309 :
1310 : std::__reverse(__first, __middle, bidirectional_iterator_tag());
1311 : std::__reverse(__middle, __last, bidirectional_iterator_tag());
1312 :
1313 : while (__first != __middle && __middle != __last)
1314 : {
1315 : std::iter_swap(__first, --__last);
1316 : ++__first;
1317 : }
1318 :
1319 : if (__first == __middle)
1320 : {
1321 : std::__reverse(__middle, __last, bidirectional_iterator_tag());
1322 : return __last;
1323 : }
1324 : else
1325 : {
1326 : std::__reverse(__first, __middle, bidirectional_iterator_tag());
1327 : return __first;
1328 : }
1329 : }
1330 :
1331 : /// This is a helper function for the rotate algorithm.
1332 : template<typename _RandomAccessIterator>
1333 : _RandomAccessIterator
1334 : __rotate(_RandomAccessIterator __first,
1335 : _RandomAccessIterator __middle,
1336 : _RandomAccessIterator __last,
1337 : random_access_iterator_tag)
1338 : {
1339 : // concept requirements
1340 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1341 : _RandomAccessIterator>)
1342 :
1343 : if (__first == __middle)
1344 : return __last;
1345 : else if (__last == __middle)
1346 : return __first;
1347 :
1348 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1349 : _Distance;
1350 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
1351 : _ValueType;
1352 :
1353 : _Distance __n = __last - __first;
1354 : _Distance __k = __middle - __first;
1355 :
1356 : if (__k == __n - __k)
1357 : {
1358 : std::swap_ranges(__first, __middle, __middle);
1359 : return __middle;
1360 : }
1361 :
1362 : _RandomAccessIterator __p = __first;
1363 : _RandomAccessIterator __ret = __first + (__last - __middle);
1364 :
1365 : for (;;)
1366 : {
1367 : if (__k < __n - __k)
1368 : {
1369 : if (__is_pod(_ValueType) && __k == 1)
1370 : {
1371 : _ValueType __t = _GLIBCXX_MOVE(*__p);
1372 : _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1373 : *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1374 : return __ret;
1375 : }
1376 : _RandomAccessIterator __q = __p + __k;
1377 : for (_Distance __i = 0; __i < __n - __k; ++ __i)
1378 : {
1379 : std::iter_swap(__p, __q);
1380 : ++__p;
1381 : ++__q;
1382 : }
1383 : __n %= __k;
1384 : if (__n == 0)
1385 : return __ret;
1386 : std::swap(__n, __k);
1387 : __k = __n - __k;
1388 : }
1389 : else
1390 : {
1391 : __k = __n - __k;
1392 : if (__is_pod(_ValueType) && __k == 1)
1393 : {
1394 : _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1395 : _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1396 : *__p = _GLIBCXX_MOVE(__t);
1397 : return __ret;
1398 : }
1399 : _RandomAccessIterator __q = __p + __n;
1400 : __p = __q - __k;
1401 : for (_Distance __i = 0; __i < __n - __k; ++ __i)
1402 : {
1403 : --__p;
1404 : --__q;
1405 : std::iter_swap(__p, __q);
1406 : }
1407 : __n %= __k;
1408 : if (__n == 0)
1409 : return __ret;
1410 : std::swap(__n, __k);
1411 : }
1412 : }
1413 : }
1414 :
1415 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1416 : // DR 488. rotate throws away useful information
1417 : /**
1418 : * @brief Rotate the elements of a sequence.
1419 : * @ingroup mutating_algorithms
1420 : * @param __first A forward iterator.
1421 : * @param __middle A forward iterator.
1422 : * @param __last A forward iterator.
1423 : * @return first + (last - middle).
1424 : *
1425 : * Rotates the elements of the range @p [__first,__last) by
1426 : * @p (__middle - __first) positions so that the element at @p __middle
1427 : * is moved to @p __first, the element at @p __middle+1 is moved to
1428 : * @p __first+1 and so on for each element in the range
1429 : * @p [__first,__last).
1430 : *
1431 : * This effectively swaps the ranges @p [__first,__middle) and
1432 : * @p [__middle,__last).
1433 : *
1434 : * Performs
1435 : * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1436 : * for each @p n in the range @p [0,__last-__first).
1437 : */
1438 : template<typename _ForwardIterator>
1439 : inline _ForwardIterator
1440 : rotate(_ForwardIterator __first, _ForwardIterator __middle,
1441 : _ForwardIterator __last)
1442 : {
1443 : // concept requirements
1444 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1445 : _ForwardIterator>)
1446 : __glibcxx_requires_valid_range(__first, __middle);
1447 : __glibcxx_requires_valid_range(__middle, __last);
1448 :
1449 : return std::__rotate(__first, __middle, __last,
1450 : std::__iterator_category(__first));
1451 : }
1452 :
1453 : } // namespace _V2
1454 :
1455 : /**
1456 : * @brief Copy a sequence, rotating its elements.
1457 : * @ingroup mutating_algorithms
1458 : * @param __first A forward iterator.
1459 : * @param __middle A forward iterator.
1460 : * @param __last A forward iterator.
1461 : * @param __result An output iterator.
1462 : * @return An iterator designating the end of the resulting sequence.
1463 : *
1464 : * Copies the elements of the range @p [__first,__last) to the
1465 : * range beginning at @result, rotating the copied elements by
1466 : * @p (__middle-__first) positions so that the element at @p __middle
1467 : * is moved to @p __result, the element at @p __middle+1 is moved
1468 : * to @p __result+1 and so on for each element in the range @p
1469 : * [__first,__last).
1470 : *
1471 : * Performs
1472 : * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1473 : * for each @p n in the range @p [0,__last-__first).
1474 : */
1475 : template<typename _ForwardIterator, typename _OutputIterator>
1476 : inline _OutputIterator
1477 : rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1478 : _ForwardIterator __last, _OutputIterator __result)
1479 : {
1480 : // concept requirements
1481 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1482 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1483 : typename iterator_traits<_ForwardIterator>::value_type>)
1484 : __glibcxx_requires_valid_range(__first, __middle);
1485 : __glibcxx_requires_valid_range(__middle, __last);
1486 :
1487 : return std::copy(__first, __middle,
1488 : std::copy(__middle, __last, __result));
1489 : }
1490 :
1491 : /// This is a helper function...
1492 : template<typename _ForwardIterator, typename _Predicate>
1493 : _ForwardIterator
1494 : __partition(_ForwardIterator __first, _ForwardIterator __last,
1495 : _Predicate __pred, forward_iterator_tag)
1496 : {
1497 : if (__first == __last)
1498 : return __first;
1499 :
1500 : while (__pred(*__first))
1501 : if (++__first == __last)
1502 : return __first;
1503 :
1504 : _ForwardIterator __next = __first;
1505 :
1506 : while (++__next != __last)
1507 : if (__pred(*__next))
1508 : {
1509 : std::iter_swap(__first, __next);
1510 : ++__first;
1511 : }
1512 :
1513 : return __first;
1514 : }
1515 :
1516 : /// This is a helper function...
1517 : template<typename _BidirectionalIterator, typename _Predicate>
1518 : _BidirectionalIterator
1519 : __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1520 : _Predicate __pred, bidirectional_iterator_tag)
1521 : {
1522 : while (true)
1523 : {
1524 : while (true)
1525 : if (__first == __last)
1526 : return __first;
1527 : else if (__pred(*__first))
1528 : ++__first;
1529 : else
1530 : break;
1531 : --__last;
1532 : while (true)
1533 : if (__first == __last)
1534 : return __first;
1535 : else if (!bool(__pred(*__last)))
1536 : --__last;
1537 : else
1538 : break;
1539 : std::iter_swap(__first, __last);
1540 : ++__first;
1541 : }
1542 : }
1543 :
1544 : // partition
1545 :
1546 : /// This is a helper function...
1547 : /// Requires __first != __last and !__pred(__first)
1548 : /// and __len == distance(__first, __last).
1549 : ///
1550 : /// !__pred(__first) allows us to guarantee that we don't
1551 : /// move-assign an element onto itself.
1552 : template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1553 : typename _Distance>
1554 : _ForwardIterator
1555 : __stable_partition_adaptive(_ForwardIterator __first,
1556 : _ForwardIterator __last,
1557 : _Predicate __pred, _Distance __len,
1558 : _Pointer __buffer,
1559 : _Distance __buffer_size)
1560 : {
1561 : if (__len == 1)
1562 : return __first;
1563 :
1564 : if (__len <= __buffer_size)
1565 : {
1566 : _ForwardIterator __result1 = __first;
1567 : _Pointer __result2 = __buffer;
1568 :
1569 : // The precondition guarantees that !__pred(__first), so
1570 : // move that element to the buffer before starting the loop.
1571 : // This ensures that we only call __pred once per element.
1572 : *__result2 = _GLIBCXX_MOVE(*__first);
1573 : ++__result2;
1574 : ++__first;
1575 : for (; __first != __last; ++__first)
1576 : if (__pred(__first))
1577 : {
1578 : *__result1 = _GLIBCXX_MOVE(*__first);
1579 : ++__result1;
1580 : }
1581 : else
1582 : {
1583 : *__result2 = _GLIBCXX_MOVE(*__first);
1584 : ++__result2;
1585 : }
1586 :
1587 : _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1588 : return __result1;
1589 : }
1590 :
1591 : _ForwardIterator __middle = __first;
1592 : std::advance(__middle, __len / 2);
1593 : _ForwardIterator __left_split =
1594 : std::__stable_partition_adaptive(__first, __middle, __pred,
1595 : __len / 2, __buffer,
1596 : __buffer_size);
1597 :
1598 : // Advance past true-predicate values to satisfy this
1599 : // function's preconditions.
1600 : _Distance __right_len = __len - __len / 2;
1601 : _ForwardIterator __right_split =
1602 : std::__find_if_not_n(__middle, __right_len, __pred);
1603 :
1604 : if (__right_len)
1605 : __right_split =
1606 : std::__stable_partition_adaptive(__right_split, __last, __pred,
1607 : __right_len,
1608 : __buffer, __buffer_size);
1609 :
1610 : return std::rotate(__left_split, __middle, __right_split);
1611 : }
1612 :
1613 : template<typename _ForwardIterator, typename _Predicate>
1614 : _ForwardIterator
1615 : __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1616 : _Predicate __pred)
1617 : {
1618 : __first = std::__find_if_not(__first, __last, __pred);
1619 :
1620 : if (__first == __last)
1621 : return __first;
1622 :
1623 : typedef typename iterator_traits<_ForwardIterator>::value_type
1624 : _ValueType;
1625 : typedef typename iterator_traits<_ForwardIterator>::difference_type
1626 : _DistanceType;
1627 :
1628 : _Temporary_buffer<_ForwardIterator, _ValueType>
1629 : __buf(__first, std::distance(__first, __last));
1630 : return
1631 : std::__stable_partition_adaptive(__first, __last, __pred,
1632 : _DistanceType(__buf.requested_size()),
1633 : __buf.begin(),
1634 : _DistanceType(__buf.size()));
1635 : }
1636 :
1637 : /**
1638 : * @brief Move elements for which a predicate is true to the beginning
1639 : * of a sequence, preserving relative ordering.
1640 : * @ingroup mutating_algorithms
1641 : * @param __first A forward iterator.
1642 : * @param __last A forward iterator.
1643 : * @param __pred A predicate functor.
1644 : * @return An iterator @p middle such that @p __pred(i) is true for each
1645 : * iterator @p i in the range @p [first,middle) and false for each @p i
1646 : * in the range @p [middle,last).
1647 : *
1648 : * Performs the same function as @p partition() with the additional
1649 : * guarantee that the relative ordering of elements in each group is
1650 : * preserved, so any two elements @p x and @p y in the range
1651 : * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1652 : * relative ordering after calling @p stable_partition().
1653 : */
1654 : template<typename _ForwardIterator, typename _Predicate>
1655 : inline _ForwardIterator
1656 : stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1657 : _Predicate __pred)
1658 : {
1659 : // concept requirements
1660 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1661 : _ForwardIterator>)
1662 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1663 : typename iterator_traits<_ForwardIterator>::value_type>)
1664 : __glibcxx_requires_valid_range(__first, __last);
1665 :
1666 : return std::__stable_partition(__first, __last,
1667 : __gnu_cxx::__ops::__pred_iter(__pred));
1668 : }
1669 :
1670 : /// This is a helper function for the sort routines.
1671 : template<typename _RandomAccessIterator, typename _Compare>
1672 : void
1673 0 : __heap_select(_RandomAccessIterator __first,
1674 : _RandomAccessIterator __middle,
1675 : _RandomAccessIterator __last, _Compare __comp)
1676 : {
1677 0 : std::__make_heap(__first, __middle, __comp);
1678 0 : for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1679 0 : if (__comp(__i, __first))
1680 0 : std::__pop_heap(__first, __middle, __i, __comp);
1681 0 : }
1682 :
1683 : // partial_sort
1684 :
1685 : template<typename _InputIterator, typename _RandomAccessIterator,
1686 : typename _Compare>
1687 : _RandomAccessIterator
1688 : __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1689 : _RandomAccessIterator __result_first,
1690 : _RandomAccessIterator __result_last,
1691 : _Compare __comp)
1692 : {
1693 : typedef typename iterator_traits<_InputIterator>::value_type
1694 : _InputValueType;
1695 : typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1696 : typedef typename _RItTraits::difference_type _DistanceType;
1697 :
1698 : if (__result_first == __result_last)
1699 : return __result_last;
1700 : _RandomAccessIterator __result_real_last = __result_first;
1701 : while (__first != __last && __result_real_last != __result_last)
1702 : {
1703 : *__result_real_last = *__first;
1704 : ++__result_real_last;
1705 : ++__first;
1706 : }
1707 :
1708 : std::__make_heap(__result_first, __result_real_last, __comp);
1709 : while (__first != __last)
1710 : {
1711 : if (__comp(__first, __result_first))
1712 : std::__adjust_heap(__result_first, _DistanceType(0),
1713 : _DistanceType(__result_real_last
1714 : - __result_first),
1715 : _InputValueType(*__first), __comp);
1716 : ++__first;
1717 : }
1718 : std::__sort_heap(__result_first, __result_real_last, __comp);
1719 : return __result_real_last;
1720 : }
1721 :
1722 : /**
1723 : * @brief Copy the smallest elements of a sequence.
1724 : * @ingroup sorting_algorithms
1725 : * @param __first An iterator.
1726 : * @param __last Another iterator.
1727 : * @param __result_first A random-access iterator.
1728 : * @param __result_last Another random-access iterator.
1729 : * @return An iterator indicating the end of the resulting sequence.
1730 : *
1731 : * Copies and sorts the smallest N values from the range @p [__first,__last)
1732 : * to the range beginning at @p __result_first, where the number of
1733 : * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1734 : * @p (__result_last-__result_first).
1735 : * After the sort if @e i and @e j are iterators in the range
1736 : * @p [__result_first,__result_first+N) such that i precedes j then
1737 : * *j<*i is false.
1738 : * The value returned is @p __result_first+N.
1739 : */
1740 : template<typename _InputIterator, typename _RandomAccessIterator>
1741 : inline _RandomAccessIterator
1742 : partial_sort_copy(_InputIterator __first, _InputIterator __last,
1743 : _RandomAccessIterator __result_first,
1744 : _RandomAccessIterator __result_last)
1745 : {
1746 : #ifdef _GLIBCXX_CONCEPT_CHECKS
1747 : typedef typename iterator_traits<_InputIterator>::value_type
1748 : _InputValueType;
1749 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
1750 : _OutputValueType;
1751 : #endif
1752 :
1753 : // concept requirements
1754 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1755 : __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1756 : _OutputValueType>)
1757 : __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1758 : _OutputValueType>)
1759 : __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1760 : __glibcxx_requires_valid_range(__first, __last);
1761 : __glibcxx_requires_irreflexive(__first, __last);
1762 : __glibcxx_requires_valid_range(__result_first, __result_last);
1763 :
1764 : return std::__partial_sort_copy(__first, __last,
1765 : __result_first, __result_last,
1766 : __gnu_cxx::__ops::__iter_less_iter());
1767 : }
1768 :
1769 : /**
1770 : * @brief Copy the smallest elements of a sequence using a predicate for
1771 : * comparison.
1772 : * @ingroup sorting_algorithms
1773 : * @param __first An input iterator.
1774 : * @param __last Another input iterator.
1775 : * @param __result_first A random-access iterator.
1776 : * @param __result_last Another random-access iterator.
1777 : * @param __comp A comparison functor.
1778 : * @return An iterator indicating the end of the resulting sequence.
1779 : *
1780 : * Copies and sorts the smallest N values from the range @p [__first,__last)
1781 : * to the range beginning at @p result_first, where the number of
1782 : * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1783 : * @p (__result_last-__result_first).
1784 : * After the sort if @e i and @e j are iterators in the range
1785 : * @p [__result_first,__result_first+N) such that i precedes j then
1786 : * @p __comp(*j,*i) is false.
1787 : * The value returned is @p __result_first+N.
1788 : */
1789 : template<typename _InputIterator, typename _RandomAccessIterator,
1790 : typename _Compare>
1791 : inline _RandomAccessIterator
1792 : partial_sort_copy(_InputIterator __first, _InputIterator __last,
1793 : _RandomAccessIterator __result_first,
1794 : _RandomAccessIterator __result_last,
1795 : _Compare __comp)
1796 : {
1797 : #ifdef _GLIBCXX_CONCEPT_CHECKS
1798 : typedef typename iterator_traits<_InputIterator>::value_type
1799 : _InputValueType;
1800 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
1801 : _OutputValueType;
1802 : #endif
1803 :
1804 : // concept requirements
1805 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1806 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1807 : _RandomAccessIterator>)
1808 : __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1809 : _OutputValueType>)
1810 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1811 : _InputValueType, _OutputValueType>)
1812 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1813 : _OutputValueType, _OutputValueType>)
1814 : __glibcxx_requires_valid_range(__first, __last);
1815 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1816 : __glibcxx_requires_valid_range(__result_first, __result_last);
1817 :
1818 : return std::__partial_sort_copy(__first, __last,
1819 : __result_first, __result_last,
1820 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
1821 : }
1822 :
1823 : /// This is a helper function for the sort routine.
1824 : template<typename _RandomAccessIterator, typename _Compare>
1825 : void
1826 5204 : __unguarded_linear_insert(_RandomAccessIterator __last,
1827 : _Compare __comp)
1828 : {
1829 : typename iterator_traits<_RandomAccessIterator>::value_type
1830 417 : __val = _GLIBCXX_MOVE(*__last);
1831 5204 : _RandomAccessIterator __next = __last;
1832 6172 : --__next;
1833 6172 : while (__comp(__val, __next))
1834 : {
1835 968 : *__last = _GLIBCXX_MOVE(*__next);
1836 968 : __last = __next;
1837 6172 : --__next;
1838 : }
1839 5204 : *__last = _GLIBCXX_MOVE(__val);
1840 0 : }
1841 :
1842 : /// This is a helper function for the sort routine.
1843 : template<typename _RandomAccessIterator, typename _Compare>
1844 : void
1845 31436 : __insertion_sort(_RandomAccessIterator __first,
1846 : _RandomAccessIterator __last, _Compare __comp)
1847 : {
1848 31436 : if (__first == __last) return;
1849 :
1850 36648 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1851 : {
1852 5212 : if (__comp(__i, __first))
1853 : {
1854 : typename iterator_traits<_RandomAccessIterator>::value_type
1855 8 : __val = _GLIBCXX_MOVE(*__i);
1856 16 : _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1857 8 : *__first = _GLIBCXX_MOVE(__val);
1858 : }
1859 : else
1860 10408 : std::__unguarded_linear_insert(__i,
1861 4787 : __gnu_cxx::__ops::__val_comp_iter(__comp));
1862 : }
1863 : }
1864 :
1865 : /// This is a helper function for the sort routine.
1866 : template<typename _RandomAccessIterator, typename _Compare>
1867 : inline void
1868 0 : __unguarded_insertion_sort(_RandomAccessIterator __first,
1869 : _RandomAccessIterator __last, _Compare __comp)
1870 : {
1871 0 : for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1872 0 : std::__unguarded_linear_insert(__i,
1873 : __gnu_cxx::__ops::__val_comp_iter(__comp));
1874 : }
1875 :
1876 : /**
1877 : * @doctodo
1878 : * This controls some aspect of the sort routines.
1879 : */
1880 : enum { _S_threshold = 16 };
1881 :
1882 : /// This is a helper function for the sort routine.
1883 : template<typename _RandomAccessIterator, typename _Compare>
1884 : void
1885 31436 : __final_insertion_sort(_RandomAccessIterator __first,
1886 : _RandomAccessIterator __last, _Compare __comp)
1887 : {
1888 31436 : if (__last - __first > int(_S_threshold))
1889 : {
1890 0 : std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1891 0 : std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1892 : __comp);
1893 : }
1894 : else
1895 31436 : std::__insertion_sort(__first, __last, __comp);
1896 31436 : }
1897 :
1898 : /// This is a helper function...
1899 : template<typename _RandomAccessIterator, typename _Compare>
1900 : _RandomAccessIterator
1901 0 : __unguarded_partition(_RandomAccessIterator __first,
1902 : _RandomAccessIterator __last,
1903 : _RandomAccessIterator __pivot, _Compare __comp)
1904 : {
1905 0 : while (true)
1906 : {
1907 0 : while (__comp(__first, __pivot))
1908 0 : ++__first;
1909 0 : --__last;
1910 0 : while (__comp(__pivot, __last))
1911 0 : --__last;
1912 0 : if (!(__first < __last))
1913 0 : return __first;
1914 0 : std::iter_swap(__first, __last);
1915 0 : ++__first;
1916 : }
1917 : }
1918 :
1919 : /// This is a helper function...
1920 : template<typename _RandomAccessIterator, typename _Compare>
1921 : inline _RandomAccessIterator
1922 0 : __unguarded_partition_pivot(_RandomAccessIterator __first,
1923 : _RandomAccessIterator __last, _Compare __comp)
1924 : {
1925 0 : _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1926 0 : std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1927 : __comp);
1928 0 : return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1929 : }
1930 :
1931 : template<typename _RandomAccessIterator, typename _Compare>
1932 : inline void
1933 0 : __partial_sort(_RandomAccessIterator __first,
1934 : _RandomAccessIterator __middle,
1935 : _RandomAccessIterator __last,
1936 : _Compare __comp)
1937 : {
1938 0 : std::__heap_select(__first, __middle, __last, __comp);
1939 0 : std::__sort_heap(__first, __middle, __comp);
1940 0 : }
1941 :
1942 : /// This is a helper function for the sort routine.
1943 : template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1944 : void
1945 31436 : __introsort_loop(_RandomAccessIterator __first,
1946 : _RandomAccessIterator __last,
1947 : _Size __depth_limit, _Compare __comp)
1948 : {
1949 31436 : while (__last - __first > int(_S_threshold))
1950 : {
1951 0 : if (__depth_limit == 0)
1952 : {
1953 0 : std::__partial_sort(__first, __last, __last, __comp);
1954 0 : return;
1955 : }
1956 0 : --__depth_limit;
1957 : _RandomAccessIterator __cut =
1958 0 : std::__unguarded_partition_pivot(__first, __last, __comp);
1959 0 : std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1960 0 : __last = __cut;
1961 : }
1962 : }
1963 :
1964 : // sort
1965 :
1966 : template<typename _RandomAccessIterator, typename _Compare>
1967 : inline void
1968 26684 : __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1969 : _Compare __comp)
1970 : {
1971 26684 : if (__first != __last)
1972 : {
1973 26657 : std::__introsort_loop(__first, __last,
1974 26657 : std::__lg(__last - __first) * 2,
1975 : __comp);
1976 26657 : std::__final_insertion_sort(__first, __last, __comp);
1977 : }
1978 26684 : }
1979 :
1980 : template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1981 : void
1982 : __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1983 : _RandomAccessIterator __last, _Size __depth_limit,
1984 : _Compare __comp)
1985 : {
1986 : while (__last - __first > 3)
1987 : {
1988 : if (__depth_limit == 0)
1989 : {
1990 : std::__heap_select(__first, __nth + 1, __last, __comp);
1991 : // Place the nth largest element in its final position.
1992 : std::iter_swap(__first, __nth);
1993 : return;
1994 : }
1995 : --__depth_limit;
1996 : _RandomAccessIterator __cut =
1997 : std::__unguarded_partition_pivot(__first, __last, __comp);
1998 : if (__cut <= __nth)
1999 : __first = __cut;
2000 : else
2001 : __last = __cut;
2002 : }
2003 : std::__insertion_sort(__first, __last, __comp);
2004 : }
2005 :
2006 : // nth_element
2007 :
2008 : // lower_bound moved to stl_algobase.h
2009 :
2010 : /**
2011 : * @brief Finds the first position in which @p __val could be inserted
2012 : * without changing the ordering.
2013 : * @ingroup binary_search_algorithms
2014 : * @param __first An iterator.
2015 : * @param __last Another iterator.
2016 : * @param __val The search term.
2017 : * @param __comp A functor to use for comparisons.
2018 : * @return An iterator pointing to the first element <em>not less
2019 : * than</em> @p __val, or end() if every element is less
2020 : * than @p __val.
2021 : * @ingroup binary_search_algorithms
2022 : *
2023 : * The comparison function should have the same effects on ordering as
2024 : * the function used for the initial sort.
2025 : */
2026 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2027 : inline _ForwardIterator
2028 : lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2029 : const _Tp& __val, _Compare __comp)
2030 : {
2031 : // concept requirements
2032 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2033 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2034 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2035 : __glibcxx_requires_partitioned_lower_pred(__first, __last,
2036 : __val, __comp);
2037 :
2038 : return std::__lower_bound(__first, __last, __val,
2039 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2040 : }
2041 :
2042 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2043 : _ForwardIterator
2044 0 : __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2045 : const _Tp& __val, _Compare __comp)
2046 : {
2047 : typedef typename iterator_traits<_ForwardIterator>::difference_type
2048 : _DistanceType;
2049 :
2050 0 : _DistanceType __len = std::distance(__first, __last);
2051 :
2052 0 : while (__len > 0)
2053 : {
2054 0 : _DistanceType __half = __len >> 1;
2055 0 : _ForwardIterator __middle = __first;
2056 0 : std::advance(__middle, __half);
2057 0 : if (__comp(__val, __middle))
2058 : __len = __half;
2059 : else
2060 : {
2061 0 : __first = __middle;
2062 0 : ++__first;
2063 0 : __len = __len - __half - 1;
2064 : }
2065 : }
2066 : return __first;
2067 : }
2068 :
2069 : /**
2070 : * @brief Finds the last position in which @p __val could be inserted
2071 : * without changing the ordering.
2072 : * @ingroup binary_search_algorithms
2073 : * @param __first An iterator.
2074 : * @param __last Another iterator.
2075 : * @param __val The search term.
2076 : * @return An iterator pointing to the first element greater than @p __val,
2077 : * or end() if no elements are greater than @p __val.
2078 : * @ingroup binary_search_algorithms
2079 : */
2080 : template<typename _ForwardIterator, typename _Tp>
2081 : inline _ForwardIterator
2082 : upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2083 : const _Tp& __val)
2084 : {
2085 : // concept requirements
2086 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2087 : __glibcxx_function_requires(_LessThanOpConcept<
2088 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2089 : __glibcxx_requires_partitioned_upper(__first, __last, __val);
2090 :
2091 : return std::__upper_bound(__first, __last, __val,
2092 : __gnu_cxx::__ops::__val_less_iter());
2093 : }
2094 :
2095 : /**
2096 : * @brief Finds the last position in which @p __val could be inserted
2097 : * without changing the ordering.
2098 : * @ingroup binary_search_algorithms
2099 : * @param __first An iterator.
2100 : * @param __last Another iterator.
2101 : * @param __val The search term.
2102 : * @param __comp A functor to use for comparisons.
2103 : * @return An iterator pointing to the first element greater than @p __val,
2104 : * or end() if no elements are greater than @p __val.
2105 : * @ingroup binary_search_algorithms
2106 : *
2107 : * The comparison function should have the same effects on ordering as
2108 : * the function used for the initial sort.
2109 : */
2110 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2111 : inline _ForwardIterator
2112 : upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2113 : const _Tp& __val, _Compare __comp)
2114 : {
2115 : // concept requirements
2116 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2117 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2118 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2119 : __glibcxx_requires_partitioned_upper_pred(__first, __last,
2120 : __val, __comp);
2121 :
2122 : return std::__upper_bound(__first, __last, __val,
2123 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2124 : }
2125 :
2126 : template<typename _ForwardIterator, typename _Tp,
2127 : typename _CompareItTp, typename _CompareTpIt>
2128 : pair<_ForwardIterator, _ForwardIterator>
2129 0 : __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2130 : const _Tp& __val,
2131 : _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2132 : {
2133 : typedef typename iterator_traits<_ForwardIterator>::difference_type
2134 : _DistanceType;
2135 :
2136 0 : _DistanceType __len = std::distance(__first, __last);
2137 :
2138 0 : while (__len > 0)
2139 : {
2140 0 : _DistanceType __half = __len >> 1;
2141 0 : _ForwardIterator __middle = __first;
2142 0 : std::advance(__middle, __half);
2143 0 : if (__comp_it_val(__middle, __val))
2144 : {
2145 0 : __first = __middle;
2146 0 : ++__first;
2147 0 : __len = __len - __half - 1;
2148 : }
2149 0 : else if (__comp_val_it(__val, __middle))
2150 : __len = __half;
2151 : else
2152 : {
2153 : _ForwardIterator __left
2154 0 : = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2155 0 : std::advance(__first, __len);
2156 : _ForwardIterator __right
2157 0 : = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2158 0 : return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2159 : }
2160 : }
2161 0 : return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2162 : }
2163 :
2164 : /**
2165 : * @brief Finds the largest subrange in which @p __val could be inserted
2166 : * at any place in it without changing the ordering.
2167 : * @ingroup binary_search_algorithms
2168 : * @param __first An iterator.
2169 : * @param __last Another iterator.
2170 : * @param __val The search term.
2171 : * @return An pair of iterators defining the subrange.
2172 : * @ingroup binary_search_algorithms
2173 : *
2174 : * This is equivalent to
2175 : * @code
2176 : * std::make_pair(lower_bound(__first, __last, __val),
2177 : * upper_bound(__first, __last, __val))
2178 : * @endcode
2179 : * but does not actually call those functions.
2180 : */
2181 : template<typename _ForwardIterator, typename _Tp>
2182 : inline pair<_ForwardIterator, _ForwardIterator>
2183 0 : equal_range(_ForwardIterator __first, _ForwardIterator __last,
2184 : const _Tp& __val)
2185 : {
2186 : // concept requirements
2187 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2188 : __glibcxx_function_requires(_LessThanOpConcept<
2189 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2190 : __glibcxx_function_requires(_LessThanOpConcept<
2191 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2192 : __glibcxx_requires_partitioned_lower(__first, __last, __val);
2193 : __glibcxx_requires_partitioned_upper(__first, __last, __val);
2194 :
2195 0 : return std::__equal_range(__first, __last, __val,
2196 : __gnu_cxx::__ops::__iter_less_val(),
2197 : __gnu_cxx::__ops::__val_less_iter());
2198 : }
2199 :
2200 : /**
2201 : * @brief Finds the largest subrange in which @p __val could be inserted
2202 : * at any place in it without changing the ordering.
2203 : * @param __first An iterator.
2204 : * @param __last Another iterator.
2205 : * @param __val The search term.
2206 : * @param __comp A functor to use for comparisons.
2207 : * @return An pair of iterators defining the subrange.
2208 : * @ingroup binary_search_algorithms
2209 : *
2210 : * This is equivalent to
2211 : * @code
2212 : * std::make_pair(lower_bound(__first, __last, __val, __comp),
2213 : * upper_bound(__first, __last, __val, __comp))
2214 : * @endcode
2215 : * but does not actually call those functions.
2216 : */
2217 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2218 : inline pair<_ForwardIterator, _ForwardIterator>
2219 : equal_range(_ForwardIterator __first, _ForwardIterator __last,
2220 : const _Tp& __val, _Compare __comp)
2221 : {
2222 : // concept requirements
2223 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2224 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2225 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2226 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2227 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2228 : __glibcxx_requires_partitioned_lower_pred(__first, __last,
2229 : __val, __comp);
2230 : __glibcxx_requires_partitioned_upper_pred(__first, __last,
2231 : __val, __comp);
2232 :
2233 : return std::__equal_range(__first, __last, __val,
2234 : __gnu_cxx::__ops::__iter_comp_val(__comp),
2235 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2236 : }
2237 :
2238 : /**
2239 : * @brief Determines whether an element exists in a range.
2240 : * @ingroup binary_search_algorithms
2241 : * @param __first An iterator.
2242 : * @param __last Another iterator.
2243 : * @param __val The search term.
2244 : * @return True if @p __val (or its equivalent) is in [@p
2245 : * __first,@p __last ].
2246 : *
2247 : * Note that this does not actually return an iterator to @p __val. For
2248 : * that, use std::find or a container's specialized find member functions.
2249 : */
2250 : template<typename _ForwardIterator, typename _Tp>
2251 : bool
2252 1222400 : binary_search(_ForwardIterator __first, _ForwardIterator __last,
2253 : const _Tp& __val)
2254 : {
2255 : // concept requirements
2256 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2257 : __glibcxx_function_requires(_LessThanOpConcept<
2258 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2259 : __glibcxx_requires_partitioned_lower(__first, __last, __val);
2260 : __glibcxx_requires_partitioned_upper(__first, __last, __val);
2261 :
2262 : _ForwardIterator __i
2263 1222400 : = std::__lower_bound(__first, __last, __val,
2264 0 : __gnu_cxx::__ops::__iter_less_val());
2265 1222400 : return __i != __last && !(__val < *__i);
2266 : }
2267 :
2268 : /**
2269 : * @brief Determines whether an element exists in a range.
2270 : * @ingroup binary_search_algorithms
2271 : * @param __first An iterator.
2272 : * @param __last Another iterator.
2273 : * @param __val The search term.
2274 : * @param __comp A functor to use for comparisons.
2275 : * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2276 : *
2277 : * Note that this does not actually return an iterator to @p __val. For
2278 : * that, use std::find or a container's specialized find member functions.
2279 : *
2280 : * The comparison function should have the same effects on ordering as
2281 : * the function used for the initial sort.
2282 : */
2283 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2284 : bool
2285 : binary_search(_ForwardIterator __first, _ForwardIterator __last,
2286 : const _Tp& __val, _Compare __comp)
2287 : {
2288 : // concept requirements
2289 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2290 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2291 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2292 : __glibcxx_requires_partitioned_lower_pred(__first, __last,
2293 : __val, __comp);
2294 : __glibcxx_requires_partitioned_upper_pred(__first, __last,
2295 : __val, __comp);
2296 :
2297 : _ForwardIterator __i
2298 : = std::__lower_bound(__first, __last, __val,
2299 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2300 : return __i != __last && !bool(__comp(__val, *__i));
2301 : }
2302 :
2303 : // merge
2304 :
2305 : /// This is a helper function for the __merge_adaptive routines.
2306 : template<typename _InputIterator1, typename _InputIterator2,
2307 : typename _OutputIterator, typename _Compare>
2308 : void
2309 : __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2310 : _InputIterator2 __first2, _InputIterator2 __last2,
2311 : _OutputIterator __result, _Compare __comp)
2312 : {
2313 : while (__first1 != __last1 && __first2 != __last2)
2314 : {
2315 : if (__comp(__first2, __first1))
2316 : {
2317 : *__result = _GLIBCXX_MOVE(*__first2);
2318 : ++__first2;
2319 : }
2320 : else
2321 : {
2322 : *__result = _GLIBCXX_MOVE(*__first1);
2323 : ++__first1;
2324 : }
2325 : ++__result;
2326 : }
2327 : if (__first1 != __last1)
2328 : _GLIBCXX_MOVE3(__first1, __last1, __result);
2329 : }
2330 :
2331 : /// This is a helper function for the __merge_adaptive routines.
2332 : template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2333 : typename _BidirectionalIterator3, typename _Compare>
2334 : void
2335 : __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2336 : _BidirectionalIterator1 __last1,
2337 : _BidirectionalIterator2 __first2,
2338 : _BidirectionalIterator2 __last2,
2339 : _BidirectionalIterator3 __result,
2340 : _Compare __comp)
2341 : {
2342 : if (__first1 == __last1)
2343 : {
2344 : _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2345 : return;
2346 : }
2347 : else if (__first2 == __last2)
2348 : return;
2349 :
2350 : --__last1;
2351 : --__last2;
2352 : while (true)
2353 : {
2354 : if (__comp(__last2, __last1))
2355 : {
2356 : *--__result = _GLIBCXX_MOVE(*__last1);
2357 : if (__first1 == __last1)
2358 : {
2359 : _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2360 : return;
2361 : }
2362 : --__last1;
2363 : }
2364 : else
2365 : {
2366 : *--__result = _GLIBCXX_MOVE(*__last2);
2367 : if (__first2 == __last2)
2368 : return;
2369 : --__last2;
2370 : }
2371 : }
2372 : }
2373 :
2374 : /// This is a helper function for the merge routines.
2375 : template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2376 : typename _Distance>
2377 : _BidirectionalIterator1
2378 : __rotate_adaptive(_BidirectionalIterator1 __first,
2379 : _BidirectionalIterator1 __middle,
2380 : _BidirectionalIterator1 __last,
2381 : _Distance __len1, _Distance __len2,
2382 : _BidirectionalIterator2 __buffer,
2383 : _Distance __buffer_size)
2384 : {
2385 : _BidirectionalIterator2 __buffer_end;
2386 : if (__len1 > __len2 && __len2 <= __buffer_size)
2387 : {
2388 : if (__len2)
2389 : {
2390 : __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2391 : _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2392 : return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2393 : }
2394 : else
2395 : return __first;
2396 : }
2397 : else if (__len1 <= __buffer_size)
2398 : {
2399 : if (__len1)
2400 : {
2401 : __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2402 : _GLIBCXX_MOVE3(__middle, __last, __first);
2403 : return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2404 : }
2405 : else
2406 : return __last;
2407 : }
2408 : else
2409 : return std::rotate(__first, __middle, __last);
2410 : }
2411 :
2412 : /// This is a helper function for the merge routines.
2413 : template<typename _BidirectionalIterator, typename _Distance,
2414 : typename _Pointer, typename _Compare>
2415 : void
2416 : __merge_adaptive(_BidirectionalIterator __first,
2417 : _BidirectionalIterator __middle,
2418 : _BidirectionalIterator __last,
2419 : _Distance __len1, _Distance __len2,
2420 : _Pointer __buffer, _Distance __buffer_size,
2421 : _Compare __comp)
2422 : {
2423 : if (__len1 <= __len2 && __len1 <= __buffer_size)
2424 : {
2425 : _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2426 : std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2427 : __first, __comp);
2428 : }
2429 : else if (__len2 <= __buffer_size)
2430 : {
2431 : _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2432 : std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2433 : __buffer_end, __last, __comp);
2434 : }
2435 : else
2436 : {
2437 : _BidirectionalIterator __first_cut = __first;
2438 : _BidirectionalIterator __second_cut = __middle;
2439 : _Distance __len11 = 0;
2440 : _Distance __len22 = 0;
2441 : if (__len1 > __len2)
2442 : {
2443 : __len11 = __len1 / 2;
2444 : std::advance(__first_cut, __len11);
2445 : __second_cut
2446 : = std::__lower_bound(__middle, __last, *__first_cut,
2447 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2448 : __len22 = std::distance(__middle, __second_cut);
2449 : }
2450 : else
2451 : {
2452 : __len22 = __len2 / 2;
2453 : std::advance(__second_cut, __len22);
2454 : __first_cut
2455 : = std::__upper_bound(__first, __middle, *__second_cut,
2456 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2457 : __len11 = std::distance(__first, __first_cut);
2458 : }
2459 :
2460 : _BidirectionalIterator __new_middle
2461 : = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2462 : __len1 - __len11, __len22, __buffer,
2463 : __buffer_size);
2464 : std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2465 : __len22, __buffer, __buffer_size, __comp);
2466 : std::__merge_adaptive(__new_middle, __second_cut, __last,
2467 : __len1 - __len11,
2468 : __len2 - __len22, __buffer,
2469 : __buffer_size, __comp);
2470 : }
2471 : }
2472 :
2473 : /// This is a helper function for the merge routines.
2474 : template<typename _BidirectionalIterator, typename _Distance,
2475 : typename _Compare>
2476 : void
2477 : __merge_without_buffer(_BidirectionalIterator __first,
2478 : _BidirectionalIterator __middle,
2479 : _BidirectionalIterator __last,
2480 : _Distance __len1, _Distance __len2,
2481 : _Compare __comp)
2482 : {
2483 : if (__len1 == 0 || __len2 == 0)
2484 : return;
2485 :
2486 : if (__len1 + __len2 == 2)
2487 : {
2488 : if (__comp(__middle, __first))
2489 : std::iter_swap(__first, __middle);
2490 : return;
2491 : }
2492 :
2493 : _BidirectionalIterator __first_cut = __first;
2494 : _BidirectionalIterator __second_cut = __middle;
2495 : _Distance __len11 = 0;
2496 : _Distance __len22 = 0;
2497 : if (__len1 > __len2)
2498 : {
2499 : __len11 = __len1 / 2;
2500 : std::advance(__first_cut, __len11);
2501 : __second_cut
2502 : = std::__lower_bound(__middle, __last, *__first_cut,
2503 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2504 : __len22 = std::distance(__middle, __second_cut);
2505 : }
2506 : else
2507 : {
2508 : __len22 = __len2 / 2;
2509 : std::advance(__second_cut, __len22);
2510 : __first_cut
2511 : = std::__upper_bound(__first, __middle, *__second_cut,
2512 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2513 : __len11 = std::distance(__first, __first_cut);
2514 : }
2515 :
2516 : _BidirectionalIterator __new_middle
2517 : = std::rotate(__first_cut, __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, __len1 + __len2);
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 0 : __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3191 : {
3192 0 : typename iterator_traits<_InputIterator>::difference_type __n = 0;
3193 0 : for (; __first != __last; ++__first)
3194 0 : if (__pred(__first))
3195 0 : ++__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 0 : 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 0 : for (; __first != __last; ++__first)
3882 0 : __f(*__first);
3883 : return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3884 : }
3885 :
3886 : #if __cplusplus >= 201703L
3887 : /**
3888 : * @brief Apply a function to every element of a sequence.
3889 : * @ingroup non_mutating_algorithms
3890 : * @param __first An input iterator.
3891 : * @param __n A value convertible to an integer.
3892 : * @param __f A unary function object.
3893 : * @return `__first+__n`
3894 : *
3895 : * Applies the function object `__f` to each element in the range
3896 : * `[first, first+n)`. `__f` must not modify the order of the sequence.
3897 : * If `__f` has a return value it is ignored.
3898 : */
3899 : template<typename _InputIterator, typename _Size, typename _Function>
3900 : _InputIterator
3901 : for_each_n(_InputIterator __first, _Size __n, _Function __f)
3902 : {
3903 : typename iterator_traits<_InputIterator>::difference_type __n2 = __n;
3904 : using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
3905 : if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3906 : {
3907 : if (__n2 <= 0)
3908 : return __first;
3909 : auto __last = __first + __n2;
3910 : std::for_each(__first, __last, std::move(__f));
3911 : return __last;
3912 : }
3913 : else
3914 : {
3915 : while (__n2-->0)
3916 : {
3917 : __f(*__first);
3918 : ++__first;
3919 : }
3920 : return __first;
3921 : }
3922 : }
3923 : #endif // C++17
3924 :
3925 : /**
3926 : * @brief Find the first occurrence of a value in a sequence.
3927 : * @ingroup non_mutating_algorithms
3928 : * @param __first An input iterator.
3929 : * @param __last An input iterator.
3930 : * @param __val The value to find.
3931 : * @return The first iterator @c i in the range @p [__first,__last)
3932 : * such that @c *i == @p __val, or @p __last if no such iterator exists.
3933 : */
3934 : template<typename _InputIterator, typename _Tp>
3935 : inline _InputIterator
3936 115843850 : find(_InputIterator __first, _InputIterator __last,
3937 : const _Tp& __val)
3938 : {
3939 : // concept requirements
3940 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3941 : __glibcxx_function_requires(_EqualOpConcept<
3942 : typename iterator_traits<_InputIterator>::value_type, _Tp>)
3943 : __glibcxx_requires_valid_range(__first, __last);
3944 115868805 : return std::__find_if(__first, __last,
3945 115818851 : __gnu_cxx::__ops::__iter_equals_val(__val));
3946 : }
3947 :
3948 : /**
3949 : * @brief Find the first element in a sequence for which a
3950 : * predicate is true.
3951 : * @ingroup non_mutating_algorithms
3952 : * @param __first An input iterator.
3953 : * @param __last An input iterator.
3954 : * @param __pred A predicate.
3955 : * @return The first iterator @c i in the range @p [__first,__last)
3956 : * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3957 : */
3958 : template<typename _InputIterator, typename _Predicate>
3959 : inline _InputIterator
3960 0 : find_if(_InputIterator __first, _InputIterator __last,
3961 : _Predicate __pred)
3962 : {
3963 : // concept requirements
3964 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3965 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3966 : typename iterator_traits<_InputIterator>::value_type>)
3967 : __glibcxx_requires_valid_range(__first, __last);
3968 :
3969 0 : return std::__find_if(__first, __last,
3970 0 : __gnu_cxx::__ops::__pred_iter(__pred));
3971 : }
3972 :
3973 : /**
3974 : * @brief Find element from a set in a sequence.
3975 : * @ingroup non_mutating_algorithms
3976 : * @param __first1 Start of range to search.
3977 : * @param __last1 End of range to search.
3978 : * @param __first2 Start of match candidates.
3979 : * @param __last2 End of match candidates.
3980 : * @return The first iterator @c i in the range
3981 : * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3982 : * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3983 : *
3984 : * Searches the range @p [__first1,__last1) for an element that is
3985 : * equal to some element in the range [__first2,__last2). If
3986 : * found, returns an iterator in the range [__first1,__last1),
3987 : * otherwise returns @p __last1.
3988 : */
3989 : template<typename _InputIterator, typename _ForwardIterator>
3990 : _InputIterator
3991 : find_first_of(_InputIterator __first1, _InputIterator __last1,
3992 : _ForwardIterator __first2, _ForwardIterator __last2)
3993 : {
3994 : // concept requirements
3995 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3996 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3997 : __glibcxx_function_requires(_EqualOpConcept<
3998 : typename iterator_traits<_InputIterator>::value_type,
3999 : typename iterator_traits<_ForwardIterator>::value_type>)
4000 : __glibcxx_requires_valid_range(__first1, __last1);
4001 : __glibcxx_requires_valid_range(__first2, __last2);
4002 :
4003 : for (; __first1 != __last1; ++__first1)
4004 : for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4005 : if (*__first1 == *__iter)
4006 : return __first1;
4007 : return __last1;
4008 : }
4009 :
4010 : /**
4011 : * @brief Find element from a set in a sequence using a predicate.
4012 : * @ingroup non_mutating_algorithms
4013 : * @param __first1 Start of range to search.
4014 : * @param __last1 End of range to search.
4015 : * @param __first2 Start of match candidates.
4016 : * @param __last2 End of match candidates.
4017 : * @param __comp Predicate to use.
4018 : * @return The first iterator @c i in the range
4019 : * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4020 : * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4021 : * such iterator exists.
4022 : *
4023 :
4024 : * Searches the range @p [__first1,__last1) for an element that is
4025 : * equal to some element in the range [__first2,__last2). If
4026 : * found, returns an iterator in the range [__first1,__last1),
4027 : * otherwise returns @p __last1.
4028 : */
4029 : template<typename _InputIterator, typename _ForwardIterator,
4030 : typename _BinaryPredicate>
4031 : _InputIterator
4032 : find_first_of(_InputIterator __first1, _InputIterator __last1,
4033 : _ForwardIterator __first2, _ForwardIterator __last2,
4034 : _BinaryPredicate __comp)
4035 : {
4036 : // concept requirements
4037 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4038 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4039 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4040 : typename iterator_traits<_InputIterator>::value_type,
4041 : typename iterator_traits<_ForwardIterator>::value_type>)
4042 : __glibcxx_requires_valid_range(__first1, __last1);
4043 : __glibcxx_requires_valid_range(__first2, __last2);
4044 :
4045 : for (; __first1 != __last1; ++__first1)
4046 : for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4047 : if (__comp(*__first1, *__iter))
4048 : return __first1;
4049 : return __last1;
4050 : }
4051 :
4052 : /**
4053 : * @brief Find two adjacent values in a sequence that are equal.
4054 : * @ingroup non_mutating_algorithms
4055 : * @param __first A forward iterator.
4056 : * @param __last A forward iterator.
4057 : * @return The first iterator @c i such that @c i and @c i+1 are both
4058 : * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4059 : * or @p __last if no such iterator exists.
4060 : */
4061 : template<typename _ForwardIterator>
4062 : inline _ForwardIterator
4063 : adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4064 : {
4065 : // concept requirements
4066 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4067 : __glibcxx_function_requires(_EqualityComparableConcept<
4068 : typename iterator_traits<_ForwardIterator>::value_type>)
4069 : __glibcxx_requires_valid_range(__first, __last);
4070 :
4071 : return std::__adjacent_find(__first, __last,
4072 : __gnu_cxx::__ops::__iter_equal_to_iter());
4073 : }
4074 :
4075 : /**
4076 : * @brief Find two adjacent values in a sequence using a predicate.
4077 : * @ingroup non_mutating_algorithms
4078 : * @param __first A forward iterator.
4079 : * @param __last A forward iterator.
4080 : * @param __binary_pred A binary predicate.
4081 : * @return The first iterator @c i such that @c i and @c i+1 are both
4082 : * valid iterators in @p [__first,__last) and such that
4083 : * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4084 : * exists.
4085 : */
4086 : template<typename _ForwardIterator, typename _BinaryPredicate>
4087 : inline _ForwardIterator
4088 : adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4089 : _BinaryPredicate __binary_pred)
4090 : {
4091 : // concept requirements
4092 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4093 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4094 : typename iterator_traits<_ForwardIterator>::value_type,
4095 : typename iterator_traits<_ForwardIterator>::value_type>)
4096 : __glibcxx_requires_valid_range(__first, __last);
4097 :
4098 : return std::__adjacent_find(__first, __last,
4099 : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4100 : }
4101 :
4102 : /**
4103 : * @brief Count the number of copies of a value in a sequence.
4104 : * @ingroup non_mutating_algorithms
4105 : * @param __first An input iterator.
4106 : * @param __last An input iterator.
4107 : * @param __value The value to be counted.
4108 : * @return The number of iterators @c i in the range @p [__first,__last)
4109 : * for which @c *i == @p __value
4110 : */
4111 : template<typename _InputIterator, typename _Tp>
4112 : inline typename iterator_traits<_InputIterator>::difference_type
4113 0 : count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4114 : {
4115 : // concept requirements
4116 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4117 : __glibcxx_function_requires(_EqualOpConcept<
4118 : typename iterator_traits<_InputIterator>::value_type, _Tp>)
4119 : __glibcxx_requires_valid_range(__first, __last);
4120 :
4121 0 : return std::__count_if(__first, __last,
4122 : __gnu_cxx::__ops::__iter_equals_val(__value));
4123 : }
4124 :
4125 : /**
4126 : * @brief Count the elements of a sequence for which a predicate is true.
4127 : * @ingroup non_mutating_algorithms
4128 : * @param __first An input iterator.
4129 : * @param __last An input iterator.
4130 : * @param __pred A predicate.
4131 : * @return The number of iterators @c i in the range @p [__first,__last)
4132 : * for which @p __pred(*i) is true.
4133 : */
4134 : template<typename _InputIterator, typename _Predicate>
4135 : inline typename iterator_traits<_InputIterator>::difference_type
4136 : count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4137 : {
4138 : // concept requirements
4139 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4140 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4141 : typename iterator_traits<_InputIterator>::value_type>)
4142 : __glibcxx_requires_valid_range(__first, __last);
4143 :
4144 : return std::__count_if(__first, __last,
4145 : __gnu_cxx::__ops::__pred_iter(__pred));
4146 : }
4147 :
4148 : /**
4149 : * @brief Search a sequence for a matching sub-sequence.
4150 : * @ingroup non_mutating_algorithms
4151 : * @param __first1 A forward iterator.
4152 : * @param __last1 A forward iterator.
4153 : * @param __first2 A forward iterator.
4154 : * @param __last2 A forward iterator.
4155 : * @return The first iterator @c i in the range @p
4156 : * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4157 : * *(__first2+N) for each @c N in the range @p
4158 : * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4159 : *
4160 : * Searches the range @p [__first1,__last1) for a sub-sequence that
4161 : * compares equal value-by-value with the sequence given by @p
4162 : * [__first2,__last2) and returns an iterator to the first element
4163 : * of the sub-sequence, or @p __last1 if the sub-sequence is not
4164 : * found.
4165 : *
4166 : * Because the sub-sequence must lie completely within the range @p
4167 : * [__first1,__last1) it must start at a position less than @p
4168 : * __last1-(__last2-__first2) where @p __last2-__first2 is the
4169 : * length of the sub-sequence.
4170 : *
4171 : * This means that the returned iterator @c i will be in the range
4172 : * @p [__first1,__last1-(__last2-__first2))
4173 : */
4174 : template<typename _ForwardIterator1, typename _ForwardIterator2>
4175 : inline _ForwardIterator1
4176 0 : search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4177 : _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4178 : {
4179 : // concept requirements
4180 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4181 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4182 : __glibcxx_function_requires(_EqualOpConcept<
4183 : typename iterator_traits<_ForwardIterator1>::value_type,
4184 : typename iterator_traits<_ForwardIterator2>::value_type>)
4185 : __glibcxx_requires_valid_range(__first1, __last1);
4186 : __glibcxx_requires_valid_range(__first2, __last2);
4187 :
4188 0 : return std::__search(__first1, __last1, __first2, __last2,
4189 : __gnu_cxx::__ops::__iter_equal_to_iter());
4190 : }
4191 :
4192 : /**
4193 : * @brief Search a sequence for a matching sub-sequence using a predicate.
4194 : * @ingroup non_mutating_algorithms
4195 : * @param __first1 A forward iterator.
4196 : * @param __last1 A forward iterator.
4197 : * @param __first2 A forward iterator.
4198 : * @param __last2 A forward iterator.
4199 : * @param __predicate A binary predicate.
4200 : * @return The first iterator @c i in the range
4201 : * @p [__first1,__last1-(__last2-__first2)) such that
4202 : * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4203 : * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4204 : *
4205 : * Searches the range @p [__first1,__last1) for a sub-sequence that
4206 : * compares equal value-by-value with the sequence given by @p
4207 : * [__first2,__last2), using @p __predicate to determine equality,
4208 : * and returns an iterator to the first element of the
4209 : * sub-sequence, or @p __last1 if no such iterator exists.
4210 : *
4211 : * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4212 : */
4213 : template<typename _ForwardIterator1, typename _ForwardIterator2,
4214 : typename _BinaryPredicate>
4215 : inline _ForwardIterator1
4216 : search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4217 : _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4218 : _BinaryPredicate __predicate)
4219 : {
4220 : // concept requirements
4221 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4222 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4223 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4224 : typename iterator_traits<_ForwardIterator1>::value_type,
4225 : typename iterator_traits<_ForwardIterator2>::value_type>)
4226 : __glibcxx_requires_valid_range(__first1, __last1);
4227 : __glibcxx_requires_valid_range(__first2, __last2);
4228 :
4229 : return std::__search(__first1, __last1, __first2, __last2,
4230 : __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4231 : }
4232 :
4233 : /**
4234 : * @brief Search a sequence for a number of consecutive values.
4235 : * @ingroup non_mutating_algorithms
4236 : * @param __first A forward iterator.
4237 : * @param __last A forward iterator.
4238 : * @param __count The number of consecutive values.
4239 : * @param __val The value to find.
4240 : * @return The first iterator @c i in the range @p
4241 : * [__first,__last-__count) such that @c *(i+N) == @p __val for
4242 : * each @c N in the range @p [0,__count), or @p __last if no such
4243 : * iterator exists.
4244 : *
4245 : * Searches the range @p [__first,__last) for @p count consecutive elements
4246 : * equal to @p __val.
4247 : */
4248 : template<typename _ForwardIterator, typename _Integer, typename _Tp>
4249 : inline _ForwardIterator
4250 : search_n(_ForwardIterator __first, _ForwardIterator __last,
4251 : _Integer __count, const _Tp& __val)
4252 : {
4253 : // concept requirements
4254 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4255 : __glibcxx_function_requires(_EqualOpConcept<
4256 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4257 : __glibcxx_requires_valid_range(__first, __last);
4258 :
4259 : return std::__search_n(__first, __last, __count,
4260 : __gnu_cxx::__ops::__iter_equals_val(__val));
4261 : }
4262 :
4263 :
4264 : /**
4265 : * @brief Search a sequence for a number of consecutive values using a
4266 : * predicate.
4267 : * @ingroup non_mutating_algorithms
4268 : * @param __first A forward iterator.
4269 : * @param __last A forward iterator.
4270 : * @param __count The number of consecutive values.
4271 : * @param __val The value to find.
4272 : * @param __binary_pred A binary predicate.
4273 : * @return The first iterator @c i in the range @p
4274 : * [__first,__last-__count) such that @p
4275 : * __binary_pred(*(i+N),__val) is true for each @c N in the range
4276 : * @p [0,__count), or @p __last if no such iterator exists.
4277 : *
4278 : * Searches the range @p [__first,__last) for @p __count
4279 : * consecutive elements for which the predicate returns true.
4280 : */
4281 : template<typename _ForwardIterator, typename _Integer, typename _Tp,
4282 : typename _BinaryPredicate>
4283 : inline _ForwardIterator
4284 : search_n(_ForwardIterator __first, _ForwardIterator __last,
4285 : _Integer __count, const _Tp& __val,
4286 : _BinaryPredicate __binary_pred)
4287 : {
4288 : // concept requirements
4289 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4290 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4291 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4292 : __glibcxx_requires_valid_range(__first, __last);
4293 :
4294 : return std::__search_n(__first, __last, __count,
4295 : __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4296 : }
4297 :
4298 : #if __cplusplus > 201402L
4299 : /** @brief Search a sequence using a Searcher object.
4300 : *
4301 : * @param __first A forward iterator.
4302 : * @param __last A forward iterator.
4303 : * @param __searcher A callable object.
4304 : * @return @p __searcher(__first,__last).first
4305 : */
4306 : template<typename _ForwardIterator, typename _Searcher>
4307 : inline _ForwardIterator
4308 : search(_ForwardIterator __first, _ForwardIterator __last,
4309 : const _Searcher& __searcher)
4310 : { return __searcher(__first, __last).first; }
4311 : #endif
4312 :
4313 : /**
4314 : * @brief Perform an operation on a sequence.
4315 : * @ingroup mutating_algorithms
4316 : * @param __first An input iterator.
4317 : * @param __last An input iterator.
4318 : * @param __result An output iterator.
4319 : * @param __unary_op A unary operator.
4320 : * @return An output iterator equal to @p __result+(__last-__first).
4321 : *
4322 : * Applies the operator to each element in the input range and assigns
4323 : * the results to successive elements of the output sequence.
4324 : * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4325 : * range @p [0,__last-__first).
4326 : *
4327 : * @p unary_op must not alter its argument.
4328 : */
4329 : template<typename _InputIterator, typename _OutputIterator,
4330 : typename _UnaryOperation>
4331 : _OutputIterator
4332 13268 : transform(_InputIterator __first, _InputIterator __last,
4333 : _OutputIterator __result, _UnaryOperation __unary_op)
4334 : {
4335 : // concept requirements
4336 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4337 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4338 : // "the type returned by a _UnaryOperation"
4339 : __typeof__(__unary_op(*__first))>)
4340 : __glibcxx_requires_valid_range(__first, __last);
4341 :
4342 187817 : for (; __first != __last; ++__first, (void)++__result)
4343 174549 : *__result = __unary_op(*__first);
4344 : return __result;
4345 : }
4346 :
4347 : /**
4348 : * @brief Perform an operation on corresponding elements of two sequences.
4349 : * @ingroup mutating_algorithms
4350 : * @param __first1 An input iterator.
4351 : * @param __last1 An input iterator.
4352 : * @param __first2 An input iterator.
4353 : * @param __result An output iterator.
4354 : * @param __binary_op A binary operator.
4355 : * @return An output iterator equal to @p result+(last-first).
4356 : *
4357 : * Applies the operator to the corresponding elements in the two
4358 : * input ranges and assigns the results to successive elements of the
4359 : * output sequence.
4360 : * Evaluates @p
4361 : * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4362 : * @c N in the range @p [0,__last1-__first1).
4363 : *
4364 : * @p binary_op must not alter either of its arguments.
4365 : */
4366 : template<typename _InputIterator1, typename _InputIterator2,
4367 : typename _OutputIterator, typename _BinaryOperation>
4368 : _OutputIterator
4369 : transform(_InputIterator1 __first1, _InputIterator1 __last1,
4370 : _InputIterator2 __first2, _OutputIterator __result,
4371 : _BinaryOperation __binary_op)
4372 : {
4373 : // concept requirements
4374 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4375 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4376 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4377 : // "the type returned by a _BinaryOperation"
4378 : __typeof__(__binary_op(*__first1,*__first2))>)
4379 : __glibcxx_requires_valid_range(__first1, __last1);
4380 :
4381 : for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4382 : *__result = __binary_op(*__first1, *__first2);
4383 : return __result;
4384 : }
4385 :
4386 : /**
4387 : * @brief Replace each occurrence of one value in a sequence with another
4388 : * value.
4389 : * @ingroup mutating_algorithms
4390 : * @param __first A forward iterator.
4391 : * @param __last A forward iterator.
4392 : * @param __old_value The value to be replaced.
4393 : * @param __new_value The replacement value.
4394 : * @return replace() returns no value.
4395 : *
4396 : * For each iterator @c i in the range @p [__first,__last) if @c *i ==
4397 : * @p __old_value then the assignment @c *i = @p __new_value is performed.
4398 : */
4399 : template<typename _ForwardIterator, typename _Tp>
4400 : void
4401 0 : replace(_ForwardIterator __first, _ForwardIterator __last,
4402 : const _Tp& __old_value, const _Tp& __new_value)
4403 : {
4404 : // concept requirements
4405 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4406 : _ForwardIterator>)
4407 : __glibcxx_function_requires(_EqualOpConcept<
4408 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4409 : __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4410 : typename iterator_traits<_ForwardIterator>::value_type>)
4411 : __glibcxx_requires_valid_range(__first, __last);
4412 :
4413 0 : for (; __first != __last; ++__first)
4414 0 : if (*__first == __old_value)
4415 0 : *__first = __new_value;
4416 : }
4417 :
4418 : /**
4419 : * @brief Replace each value in a sequence for which a predicate returns
4420 : * true with another value.
4421 : * @ingroup mutating_algorithms
4422 : * @param __first A forward iterator.
4423 : * @param __last A forward iterator.
4424 : * @param __pred A predicate.
4425 : * @param __new_value The replacement value.
4426 : * @return replace_if() returns no value.
4427 : *
4428 : * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4429 : * is true then the assignment @c *i = @p __new_value is performed.
4430 : */
4431 : template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4432 : void
4433 : replace_if(_ForwardIterator __first, _ForwardIterator __last,
4434 : _Predicate __pred, const _Tp& __new_value)
4435 : {
4436 : // concept requirements
4437 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4438 : _ForwardIterator>)
4439 : __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4440 : typename iterator_traits<_ForwardIterator>::value_type>)
4441 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4442 : typename iterator_traits<_ForwardIterator>::value_type>)
4443 : __glibcxx_requires_valid_range(__first, __last);
4444 :
4445 : for (; __first != __last; ++__first)
4446 : if (__pred(*__first))
4447 : *__first = __new_value;
4448 : }
4449 :
4450 : /**
4451 : * @brief Assign the result of a function object to each value in a
4452 : * sequence.
4453 : * @ingroup mutating_algorithms
4454 : * @param __first A forward iterator.
4455 : * @param __last A forward iterator.
4456 : * @param __gen A function object taking no arguments and returning
4457 : * std::iterator_traits<_ForwardIterator>::value_type
4458 : * @return generate() returns no value.
4459 : *
4460 : * Performs the assignment @c *i = @p __gen() for each @c i in the range
4461 : * @p [__first,__last).
4462 : */
4463 : template<typename _ForwardIterator, typename _Generator>
4464 : void
4465 : generate(_ForwardIterator __first, _ForwardIterator __last,
4466 : _Generator __gen)
4467 : {
4468 : // concept requirements
4469 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4470 : __glibcxx_function_requires(_GeneratorConcept<_Generator,
4471 : typename iterator_traits<_ForwardIterator>::value_type>)
4472 : __glibcxx_requires_valid_range(__first, __last);
4473 :
4474 : for (; __first != __last; ++__first)
4475 : *__first = __gen();
4476 : }
4477 :
4478 : /**
4479 : * @brief Assign the result of a function object to each value in a
4480 : * sequence.
4481 : * @ingroup mutating_algorithms
4482 : * @param __first A forward iterator.
4483 : * @param __n The length of the sequence.
4484 : * @param __gen A function object taking no arguments and returning
4485 : * std::iterator_traits<_ForwardIterator>::value_type
4486 : * @return The end of the sequence, @p __first+__n
4487 : *
4488 : * Performs the assignment @c *i = @p __gen() for each @c i in the range
4489 : * @p [__first,__first+__n).
4490 : *
4491 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4492 : * DR 865. More algorithms that throw away information
4493 : */
4494 : template<typename _OutputIterator, typename _Size, typename _Generator>
4495 : _OutputIterator
4496 : generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4497 : {
4498 : // concept requirements
4499 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4500 : // "the type returned by a _Generator"
4501 : __typeof__(__gen())>)
4502 :
4503 : for (__decltype(__n + 0) __niter = __n;
4504 : __niter > 0; --__niter, (void) ++__first)
4505 : *__first = __gen();
4506 : return __first;
4507 : }
4508 :
4509 : /**
4510 : * @brief Copy a sequence, removing consecutive duplicate values.
4511 : * @ingroup mutating_algorithms
4512 : * @param __first An input iterator.
4513 : * @param __last An input iterator.
4514 : * @param __result An output iterator.
4515 : * @return An iterator designating the end of the resulting sequence.
4516 : *
4517 : * Copies each element in the range @p [__first,__last) to the range
4518 : * beginning at @p __result, except that only the first element is copied
4519 : * from groups of consecutive elements that compare equal.
4520 : * unique_copy() is stable, so the relative order of elements that are
4521 : * copied is unchanged.
4522 : *
4523 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4524 : * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4525 : *
4526 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4527 : * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4528 : * Assignable?
4529 : */
4530 : template<typename _InputIterator, typename _OutputIterator>
4531 : inline _OutputIterator
4532 : unique_copy(_InputIterator __first, _InputIterator __last,
4533 : _OutputIterator __result)
4534 : {
4535 : // concept requirements
4536 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4537 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4538 : typename iterator_traits<_InputIterator>::value_type>)
4539 : __glibcxx_function_requires(_EqualityComparableConcept<
4540 : typename iterator_traits<_InputIterator>::value_type>)
4541 : __glibcxx_requires_valid_range(__first, __last);
4542 :
4543 : if (__first == __last)
4544 : return __result;
4545 : return std::__unique_copy(__first, __last, __result,
4546 : __gnu_cxx::__ops::__iter_equal_to_iter(),
4547 : std::__iterator_category(__first),
4548 : std::__iterator_category(__result));
4549 : }
4550 :
4551 : /**
4552 : * @brief Copy a sequence, removing consecutive values using a predicate.
4553 : * @ingroup mutating_algorithms
4554 : * @param __first An input iterator.
4555 : * @param __last An input iterator.
4556 : * @param __result An output iterator.
4557 : * @param __binary_pred A binary predicate.
4558 : * @return An iterator designating the end of the resulting sequence.
4559 : *
4560 : * Copies each element in the range @p [__first,__last) to the range
4561 : * beginning at @p __result, except that only the first element is copied
4562 : * from groups of consecutive elements for which @p __binary_pred returns
4563 : * true.
4564 : * unique_copy() is stable, so the relative order of elements that are
4565 : * copied is unchanged.
4566 : *
4567 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4568 : * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4569 : */
4570 : template<typename _InputIterator, typename _OutputIterator,
4571 : typename _BinaryPredicate>
4572 : inline _OutputIterator
4573 : unique_copy(_InputIterator __first, _InputIterator __last,
4574 : _OutputIterator __result,
4575 : _BinaryPredicate __binary_pred)
4576 : {
4577 : // concept requirements -- predicates checked later
4578 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4579 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4580 : typename iterator_traits<_InputIterator>::value_type>)
4581 : __glibcxx_requires_valid_range(__first, __last);
4582 :
4583 : if (__first == __last)
4584 : return __result;
4585 : return std::__unique_copy(__first, __last, __result,
4586 : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4587 : std::__iterator_category(__first),
4588 : std::__iterator_category(__result));
4589 : }
4590 :
4591 : #if _GLIBCXX_HOSTED
4592 : /**
4593 : * @brief Randomly shuffle the elements of a sequence.
4594 : * @ingroup mutating_algorithms
4595 : * @param __first A forward iterator.
4596 : * @param __last A forward iterator.
4597 : * @return Nothing.
4598 : *
4599 : * Reorder the elements in the range @p [__first,__last) using a random
4600 : * distribution, so that every possible ordering of the sequence is
4601 : * equally likely.
4602 : */
4603 : template<typename _RandomAccessIterator>
4604 : inline void
4605 : random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4606 : {
4607 : // concept requirements
4608 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4609 : _RandomAccessIterator>)
4610 : __glibcxx_requires_valid_range(__first, __last);
4611 :
4612 : if (__first != __last)
4613 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4614 : {
4615 : // XXX rand() % N is not uniformly distributed
4616 : _RandomAccessIterator __j = __first
4617 : + std::rand() % ((__i - __first) + 1);
4618 : if (__i != __j)
4619 : std::iter_swap(__i, __j);
4620 : }
4621 : }
4622 : #endif
4623 :
4624 : /**
4625 : * @brief Shuffle the elements of a sequence using a random number
4626 : * generator.
4627 : * @ingroup mutating_algorithms
4628 : * @param __first A forward iterator.
4629 : * @param __last A forward iterator.
4630 : * @param __rand The RNG functor or function.
4631 : * @return Nothing.
4632 : *
4633 : * Reorders the elements in the range @p [__first,__last) using @p __rand to
4634 : * provide a random distribution. Calling @p __rand(N) for a positive
4635 : * integer @p N should return a randomly chosen integer from the
4636 : * range [0,N).
4637 : */
4638 : template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4639 : void
4640 : random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4641 : #if __cplusplus >= 201103L
4642 : _RandomNumberGenerator&& __rand)
4643 : #else
4644 : _RandomNumberGenerator& __rand)
4645 : #endif
4646 : {
4647 : // concept requirements
4648 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4649 : _RandomAccessIterator>)
4650 : __glibcxx_requires_valid_range(__first, __last);
4651 :
4652 : if (__first == __last)
4653 : return;
4654 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4655 : {
4656 : _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4657 : if (__i != __j)
4658 : std::iter_swap(__i, __j);
4659 : }
4660 : }
4661 :
4662 :
4663 : /**
4664 : * @brief Move elements for which a predicate is true to the beginning
4665 : * of a sequence.
4666 : * @ingroup mutating_algorithms
4667 : * @param __first A forward iterator.
4668 : * @param __last A forward iterator.
4669 : * @param __pred A predicate functor.
4670 : * @return An iterator @p middle such that @p __pred(i) is true for each
4671 : * iterator @p i in the range @p [__first,middle) and false for each @p i
4672 : * in the range @p [middle,__last).
4673 : *
4674 : * @p __pred must not modify its operand. @p partition() does not preserve
4675 : * the relative ordering of elements in each group, use
4676 : * @p stable_partition() if this is needed.
4677 : */
4678 : template<typename _ForwardIterator, typename _Predicate>
4679 : inline _ForwardIterator
4680 : partition(_ForwardIterator __first, _ForwardIterator __last,
4681 : _Predicate __pred)
4682 : {
4683 : // concept requirements
4684 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4685 : _ForwardIterator>)
4686 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4687 : typename iterator_traits<_ForwardIterator>::value_type>)
4688 : __glibcxx_requires_valid_range(__first, __last);
4689 :
4690 : return std::__partition(__first, __last, __pred,
4691 : std::__iterator_category(__first));
4692 : }
4693 :
4694 :
4695 : /**
4696 : * @brief Sort the smallest elements of a sequence.
4697 : * @ingroup sorting_algorithms
4698 : * @param __first An iterator.
4699 : * @param __middle Another iterator.
4700 : * @param __last Another iterator.
4701 : * @return Nothing.
4702 : *
4703 : * Sorts the smallest @p (__middle-__first) elements in the range
4704 : * @p [first,last) and moves them to the range @p [__first,__middle). The
4705 : * order of the remaining elements in the range @p [__middle,__last) is
4706 : * undefined.
4707 : * After the sort if @e i and @e j are iterators in the range
4708 : * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4709 : * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4710 : */
4711 : template<typename _RandomAccessIterator>
4712 : inline void
4713 : partial_sort(_RandomAccessIterator __first,
4714 : _RandomAccessIterator __middle,
4715 : _RandomAccessIterator __last)
4716 : {
4717 : // concept requirements
4718 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4719 : _RandomAccessIterator>)
4720 : __glibcxx_function_requires(_LessThanComparableConcept<
4721 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4722 : __glibcxx_requires_valid_range(__first, __middle);
4723 : __glibcxx_requires_valid_range(__middle, __last);
4724 : __glibcxx_requires_irreflexive(__first, __last);
4725 :
4726 : std::__partial_sort(__first, __middle, __last,
4727 : __gnu_cxx::__ops::__iter_less_iter());
4728 : }
4729 :
4730 : /**
4731 : * @brief Sort the smallest elements of a sequence using a predicate
4732 : * for comparison.
4733 : * @ingroup sorting_algorithms
4734 : * @param __first An iterator.
4735 : * @param __middle Another iterator.
4736 : * @param __last Another iterator.
4737 : * @param __comp A comparison functor.
4738 : * @return Nothing.
4739 : *
4740 : * Sorts the smallest @p (__middle-__first) elements in the range
4741 : * @p [__first,__last) and moves them to the range @p [__first,__middle). The
4742 : * order of the remaining elements in the range @p [__middle,__last) is
4743 : * undefined.
4744 : * After the sort if @e i and @e j are iterators in the range
4745 : * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4746 : * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4747 : * are both false.
4748 : */
4749 : template<typename _RandomAccessIterator, typename _Compare>
4750 : inline void
4751 : partial_sort(_RandomAccessIterator __first,
4752 : _RandomAccessIterator __middle,
4753 : _RandomAccessIterator __last,
4754 : _Compare __comp)
4755 : {
4756 : // concept requirements
4757 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4758 : _RandomAccessIterator>)
4759 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4760 : typename iterator_traits<_RandomAccessIterator>::value_type,
4761 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4762 : __glibcxx_requires_valid_range(__first, __middle);
4763 : __glibcxx_requires_valid_range(__middle, __last);
4764 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4765 :
4766 : std::__partial_sort(__first, __middle, __last,
4767 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
4768 : }
4769 :
4770 : /**
4771 : * @brief Sort a sequence just enough to find a particular position.
4772 : * @ingroup sorting_algorithms
4773 : * @param __first An iterator.
4774 : * @param __nth Another iterator.
4775 : * @param __last Another iterator.
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 *j < *i is false.
4784 : */
4785 : template<typename _RandomAccessIterator>
4786 : inline void
4787 : nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4788 : _RandomAccessIterator __last)
4789 : {
4790 : // concept requirements
4791 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4792 : _RandomAccessIterator>)
4793 : __glibcxx_function_requires(_LessThanComparableConcept<
4794 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4795 : __glibcxx_requires_valid_range(__first, __nth);
4796 : __glibcxx_requires_valid_range(__nth, __last);
4797 : __glibcxx_requires_irreflexive(__first, __last);
4798 :
4799 : if (__first == __last || __nth == __last)
4800 : return;
4801 :
4802 : std::__introselect(__first, __nth, __last,
4803 : std::__lg(__last - __first) * 2,
4804 : __gnu_cxx::__ops::__iter_less_iter());
4805 : }
4806 :
4807 : /**
4808 : * @brief Sort a sequence just enough to find a particular position
4809 : * using a predicate for comparison.
4810 : * @ingroup sorting_algorithms
4811 : * @param __first An iterator.
4812 : * @param __nth Another iterator.
4813 : * @param __last Another iterator.
4814 : * @param __comp A comparison functor.
4815 : * @return Nothing.
4816 : *
4817 : * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4818 : * is the same element that would have been in that position had the
4819 : * whole sequence been sorted. The elements either side of @p *__nth are
4820 : * not completely sorted, but for any iterator @e i in the range
4821 : * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4822 : * holds that @p __comp(*j,*i) is false.
4823 : */
4824 : template<typename _RandomAccessIterator, typename _Compare>
4825 : inline void
4826 : nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4827 : _RandomAccessIterator __last, _Compare __comp)
4828 : {
4829 : // concept requirements
4830 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4831 : _RandomAccessIterator>)
4832 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4833 : typename iterator_traits<_RandomAccessIterator>::value_type,
4834 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4835 : __glibcxx_requires_valid_range(__first, __nth);
4836 : __glibcxx_requires_valid_range(__nth, __last);
4837 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4838 :
4839 : if (__first == __last || __nth == __last)
4840 : return;
4841 :
4842 : std::__introselect(__first, __nth, __last,
4843 : std::__lg(__last - __first) * 2,
4844 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
4845 : }
4846 :
4847 : /**
4848 : * @brief Sort the elements of a sequence.
4849 : * @ingroup sorting_algorithms
4850 : * @param __first An iterator.
4851 : * @param __last Another iterator.
4852 : * @return Nothing.
4853 : *
4854 : * Sorts the elements in the range @p [__first,__last) in ascending order,
4855 : * such that for each iterator @e i in the range @p [__first,__last-1),
4856 : * *(i+1)<*i is false.
4857 : *
4858 : * The relative ordering of equivalent elements is not preserved, use
4859 : * @p stable_sort() if this is needed.
4860 : */
4861 : template<typename _RandomAccessIterator>
4862 : inline void
4863 4779 : sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4864 : {
4865 : // concept requirements
4866 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4867 : _RandomAccessIterator>)
4868 : __glibcxx_function_requires(_LessThanComparableConcept<
4869 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4870 : __glibcxx_requires_valid_range(__first, __last);
4871 : __glibcxx_requires_irreflexive(__first, __last);
4872 :
4873 4779 : std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4874 0 : }
4875 :
4876 : /**
4877 : * @brief Sort the elements of a sequence using a predicate for comparison.
4878 : * @ingroup sorting_algorithms
4879 : * @param __first An iterator.
4880 : * @param __last Another iterator.
4881 : * @param __comp A comparison functor.
4882 : * @return Nothing.
4883 : *
4884 : * Sorts the elements in the range @p [__first,__last) in ascending order,
4885 : * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4886 : * range @p [__first,__last-1).
4887 : *
4888 : * The relative ordering of equivalent elements is not preserved, use
4889 : * @p stable_sort() if this is needed.
4890 : */
4891 : template<typename _RandomAccessIterator, typename _Compare>
4892 : inline void
4893 26684 : sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4894 : _Compare __comp)
4895 : {
4896 : // concept requirements
4897 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4898 : _RandomAccessIterator>)
4899 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4900 : typename iterator_traits<_RandomAccessIterator>::value_type,
4901 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4902 : __glibcxx_requires_valid_range(__first, __last);
4903 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4904 :
4905 26684 : std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4906 26684 : }
4907 :
4908 : template<typename _InputIterator1, typename _InputIterator2,
4909 : typename _OutputIterator, typename _Compare>
4910 : _OutputIterator
4911 0 : __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4912 : _InputIterator2 __first2, _InputIterator2 __last2,
4913 : _OutputIterator __result, _Compare __comp)
4914 : {
4915 0 : while (__first1 != __last1 && __first2 != __last2)
4916 : {
4917 0 : if (__comp(__first2, __first1))
4918 : {
4919 0 : *__result = *__first2;
4920 0 : ++__first2;
4921 : }
4922 : else
4923 : {
4924 0 : *__result = *__first1;
4925 0 : ++__first1;
4926 : }
4927 0 : ++__result;
4928 : }
4929 0 : return std::copy(__first2, __last2,
4930 0 : std::copy(__first1, __last1, __result));
4931 : }
4932 :
4933 : /**
4934 : * @brief Merges two sorted ranges.
4935 : * @ingroup sorting_algorithms
4936 : * @param __first1 An iterator.
4937 : * @param __first2 Another iterator.
4938 : * @param __last1 Another iterator.
4939 : * @param __last2 Another iterator.
4940 : * @param __result An iterator pointing to the end of the merged range.
4941 : * @return An iterator pointing to the first element <em>not less
4942 : * than</em> @e val.
4943 : *
4944 : * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4945 : * the sorted range @p [__result, __result + (__last1-__first1) +
4946 : * (__last2-__first2)). Both input ranges must be sorted, and the
4947 : * output range must not overlap with either of the input ranges.
4948 : * The sort is @e stable, that is, for equivalent elements in the
4949 : * two ranges, elements from the first range will always come
4950 : * before elements from the second.
4951 : */
4952 : template<typename _InputIterator1, typename _InputIterator2,
4953 : typename _OutputIterator>
4954 : inline _OutputIterator
4955 0 : merge(_InputIterator1 __first1, _InputIterator1 __last1,
4956 : _InputIterator2 __first2, _InputIterator2 __last2,
4957 : _OutputIterator __result)
4958 : {
4959 : // concept requirements
4960 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4961 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4962 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4963 : typename iterator_traits<_InputIterator1>::value_type>)
4964 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4965 : typename iterator_traits<_InputIterator2>::value_type>)
4966 : __glibcxx_function_requires(_LessThanOpConcept<
4967 : typename iterator_traits<_InputIterator2>::value_type,
4968 : typename iterator_traits<_InputIterator1>::value_type>)
4969 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4970 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4971 : __glibcxx_requires_irreflexive2(__first1, __last1);
4972 : __glibcxx_requires_irreflexive2(__first2, __last2);
4973 :
4974 0 : return _GLIBCXX_STD_A::__merge(__first1, __last1,
4975 : __first2, __last2, __result,
4976 : __gnu_cxx::__ops::__iter_less_iter());
4977 : }
4978 :
4979 : /**
4980 : * @brief Merges two sorted ranges.
4981 : * @ingroup sorting_algorithms
4982 : * @param __first1 An iterator.
4983 : * @param __first2 Another iterator.
4984 : * @param __last1 Another iterator.
4985 : * @param __last2 Another iterator.
4986 : * @param __result An iterator pointing to the end of the merged range.
4987 : * @param __comp A functor to use for comparisons.
4988 : * @return An iterator pointing to the first element "not less
4989 : * than" @e val.
4990 : *
4991 : * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4992 : * the sorted range @p [__result, __result + (__last1-__first1) +
4993 : * (__last2-__first2)). Both input ranges must be sorted, and the
4994 : * output range must not overlap with either of the input ranges.
4995 : * The sort is @e stable, that is, for equivalent elements in the
4996 : * two ranges, elements from the first range will always come
4997 : * before elements from the second.
4998 : *
4999 : * The comparison function should have the same effects on ordering as
5000 : * the function used for the initial sort.
5001 : */
5002 : template<typename _InputIterator1, typename _InputIterator2,
5003 : typename _OutputIterator, typename _Compare>
5004 : inline _OutputIterator
5005 : merge(_InputIterator1 __first1, _InputIterator1 __last1,
5006 : _InputIterator2 __first2, _InputIterator2 __last2,
5007 : _OutputIterator __result, _Compare __comp)
5008 : {
5009 : // concept requirements
5010 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5011 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5012 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5013 : typename iterator_traits<_InputIterator1>::value_type>)
5014 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5015 : typename iterator_traits<_InputIterator2>::value_type>)
5016 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5017 : typename iterator_traits<_InputIterator2>::value_type,
5018 : typename iterator_traits<_InputIterator1>::value_type>)
5019 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5020 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5021 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5022 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5023 :
5024 : return _GLIBCXX_STD_A::__merge(__first1, __last1,
5025 : __first2, __last2, __result,
5026 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5027 : }
5028 :
5029 : template<typename _RandomAccessIterator, typename _Compare>
5030 : inline void
5031 : __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5032 : _Compare __comp)
5033 : {
5034 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
5035 : _ValueType;
5036 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5037 : _DistanceType;
5038 :
5039 : typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5040 : _TmpBuf __buf(__first, std::distance(__first, __last));
5041 :
5042 : if (__buf.begin() == 0)
5043 : std::__inplace_stable_sort(__first, __last, __comp);
5044 : else
5045 : std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5046 : _DistanceType(__buf.size()), __comp);
5047 : }
5048 :
5049 : /**
5050 : * @brief Sort the elements of a sequence, preserving the relative order
5051 : * of equivalent elements.
5052 : * @ingroup sorting_algorithms
5053 : * @param __first An iterator.
5054 : * @param __last Another iterator.
5055 : * @return Nothing.
5056 : *
5057 : * Sorts the elements in the range @p [__first,__last) in ascending order,
5058 : * such that for each iterator @p i in the range @p [__first,__last-1),
5059 : * @p *(i+1)<*i is false.
5060 : *
5061 : * The relative ordering of equivalent elements is preserved, so any two
5062 : * elements @p x and @p y in the range @p [__first,__last) such that
5063 : * @p x<y is false and @p y<x is false will have the same relative
5064 : * ordering after calling @p stable_sort().
5065 : */
5066 : template<typename _RandomAccessIterator>
5067 : inline void
5068 : stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5069 : {
5070 : // concept requirements
5071 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5072 : _RandomAccessIterator>)
5073 : __glibcxx_function_requires(_LessThanComparableConcept<
5074 : typename iterator_traits<_RandomAccessIterator>::value_type>)
5075 : __glibcxx_requires_valid_range(__first, __last);
5076 : __glibcxx_requires_irreflexive(__first, __last);
5077 :
5078 : _GLIBCXX_STD_A::__stable_sort(__first, __last,
5079 : __gnu_cxx::__ops::__iter_less_iter());
5080 : }
5081 :
5082 : /**
5083 : * @brief Sort the elements of a sequence using a predicate for comparison,
5084 : * preserving the relative order of equivalent elements.
5085 : * @ingroup sorting_algorithms
5086 : * @param __first An iterator.
5087 : * @param __last Another iterator.
5088 : * @param __comp A comparison functor.
5089 : * @return Nothing.
5090 : *
5091 : * Sorts the elements in the range @p [__first,__last) in ascending order,
5092 : * such that for each iterator @p i in the range @p [__first,__last-1),
5093 : * @p __comp(*(i+1),*i) is false.
5094 : *
5095 : * The relative ordering of equivalent elements is preserved, so any two
5096 : * elements @p x and @p y in the range @p [__first,__last) such that
5097 : * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5098 : * relative ordering after calling @p stable_sort().
5099 : */
5100 : template<typename _RandomAccessIterator, typename _Compare>
5101 : inline void
5102 : stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5103 : _Compare __comp)
5104 : {
5105 : // concept requirements
5106 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5107 : _RandomAccessIterator>)
5108 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5109 : typename iterator_traits<_RandomAccessIterator>::value_type,
5110 : typename iterator_traits<_RandomAccessIterator>::value_type>)
5111 : __glibcxx_requires_valid_range(__first, __last);
5112 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5113 :
5114 : _GLIBCXX_STD_A::__stable_sort(__first, __last,
5115 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5116 : }
5117 :
5118 : template<typename _InputIterator1, typename _InputIterator2,
5119 : typename _OutputIterator,
5120 : typename _Compare>
5121 : _OutputIterator
5122 0 : __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5123 : _InputIterator2 __first2, _InputIterator2 __last2,
5124 : _OutputIterator __result, _Compare __comp)
5125 : {
5126 0 : while (__first1 != __last1 && __first2 != __last2)
5127 : {
5128 0 : if (__comp(__first1, __first2))
5129 : {
5130 0 : *__result = *__first1;
5131 0 : ++__first1;
5132 : }
5133 0 : else if (__comp(__first2, __first1))
5134 : {
5135 0 : *__result = *__first2;
5136 0 : ++__first2;
5137 : }
5138 : else
5139 : {
5140 0 : *__result = *__first1;
5141 0 : ++__first1;
5142 0 : ++__first2;
5143 : }
5144 0 : ++__result;
5145 : }
5146 0 : return std::copy(__first2, __last2,
5147 0 : std::copy(__first1, __last1, __result));
5148 : }
5149 :
5150 : /**
5151 : * @brief Return the union of two sorted ranges.
5152 : * @ingroup set_algorithms
5153 : * @param __first1 Start of first range.
5154 : * @param __last1 End of first range.
5155 : * @param __first2 Start of second range.
5156 : * @param __last2 End of second range.
5157 : * @param __result Start of output range.
5158 : * @return End of the output range.
5159 : * @ingroup set_algorithms
5160 : *
5161 : * This operation iterates over both ranges, copying elements present in
5162 : * each range in order to the output range. Iterators increment for each
5163 : * range. When the current element of one range is less than the other,
5164 : * that element is copied and the iterator advanced. If an element is
5165 : * contained in both ranges, the element from the first range is copied and
5166 : * both ranges advance. The output range may not overlap either input
5167 : * range.
5168 : */
5169 : template<typename _InputIterator1, typename _InputIterator2,
5170 : typename _OutputIterator>
5171 : inline _OutputIterator
5172 0 : set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5173 : _InputIterator2 __first2, _InputIterator2 __last2,
5174 : _OutputIterator __result)
5175 : {
5176 : // concept requirements
5177 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5178 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5179 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5180 : typename iterator_traits<_InputIterator1>::value_type>)
5181 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5182 : typename iterator_traits<_InputIterator2>::value_type>)
5183 : __glibcxx_function_requires(_LessThanOpConcept<
5184 : typename iterator_traits<_InputIterator1>::value_type,
5185 : typename iterator_traits<_InputIterator2>::value_type>)
5186 : __glibcxx_function_requires(_LessThanOpConcept<
5187 : typename iterator_traits<_InputIterator2>::value_type,
5188 : typename iterator_traits<_InputIterator1>::value_type>)
5189 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5190 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5191 : __glibcxx_requires_irreflexive2(__first1, __last1);
5192 : __glibcxx_requires_irreflexive2(__first2, __last2);
5193 :
5194 0 : return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5195 : __first2, __last2, __result,
5196 : __gnu_cxx::__ops::__iter_less_iter());
5197 : }
5198 :
5199 : /**
5200 : * @brief Return the union of two sorted ranges using a comparison functor.
5201 : * @ingroup set_algorithms
5202 : * @param __first1 Start of first range.
5203 : * @param __last1 End of first range.
5204 : * @param __first2 Start of second range.
5205 : * @param __last2 End of second range.
5206 : * @param __result Start of output range.
5207 : * @param __comp The comparison functor.
5208 : * @return End of the output range.
5209 : * @ingroup set_algorithms
5210 : *
5211 : * This operation iterates over both ranges, copying elements present in
5212 : * each range in order to the output range. Iterators increment for each
5213 : * range. When the current element of one range is less than the other
5214 : * according to @p __comp, that element is copied and the iterator advanced.
5215 : * If an equivalent element according to @p __comp is contained in both
5216 : * ranges, the element from the first range is copied and both ranges
5217 : * advance. The output range may not overlap either input range.
5218 : */
5219 : template<typename _InputIterator1, typename _InputIterator2,
5220 : typename _OutputIterator, typename _Compare>
5221 : inline _OutputIterator
5222 : set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5223 : _InputIterator2 __first2, _InputIterator2 __last2,
5224 : _OutputIterator __result, _Compare __comp)
5225 : {
5226 : // concept requirements
5227 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5228 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5229 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5230 : typename iterator_traits<_InputIterator1>::value_type>)
5231 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5232 : typename iterator_traits<_InputIterator2>::value_type>)
5233 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5234 : typename iterator_traits<_InputIterator1>::value_type,
5235 : typename iterator_traits<_InputIterator2>::value_type>)
5236 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5237 : typename iterator_traits<_InputIterator2>::value_type,
5238 : typename iterator_traits<_InputIterator1>::value_type>)
5239 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5240 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5241 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5242 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5243 :
5244 : return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5245 : __first2, __last2, __result,
5246 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5247 : }
5248 :
5249 : template<typename _InputIterator1, typename _InputIterator2,
5250 : typename _OutputIterator,
5251 : typename _Compare>
5252 : _OutputIterator
5253 0 : __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5254 : _InputIterator2 __first2, _InputIterator2 __last2,
5255 : _OutputIterator __result, _Compare __comp)
5256 : {
5257 0 : while (__first1 != __last1 && __first2 != __last2)
5258 0 : if (__comp(__first1, __first2))
5259 0 : ++__first1;
5260 0 : else if (__comp(__first2, __first1))
5261 0 : ++__first2;
5262 : else
5263 : {
5264 0 : *__result = *__first1;
5265 0 : ++__first1;
5266 0 : ++__first2;
5267 0 : ++__result;
5268 : }
5269 0 : return __result;
5270 : }
5271 :
5272 : /**
5273 : * @brief Return the intersection of two sorted ranges.
5274 : * @ingroup set_algorithms
5275 : * @param __first1 Start of first range.
5276 : * @param __last1 End of first range.
5277 : * @param __first2 Start of second range.
5278 : * @param __last2 End of second range.
5279 : * @param __result Start of output range.
5280 : * @return End of the output range.
5281 : * @ingroup set_algorithms
5282 : *
5283 : * This operation iterates over both ranges, copying elements present in
5284 : * both ranges in order to the output range. Iterators increment for each
5285 : * range. When the current element of one range is less than the other,
5286 : * that iterator advances. If an element is contained in both ranges, the
5287 : * element from the first range is copied and both ranges advance. The
5288 : * output range may not overlap either input range.
5289 : */
5290 : template<typename _InputIterator1, typename _InputIterator2,
5291 : typename _OutputIterator>
5292 : inline _OutputIterator
5293 0 : set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5294 : _InputIterator2 __first2, _InputIterator2 __last2,
5295 : _OutputIterator __result)
5296 : {
5297 : // concept requirements
5298 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5299 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5300 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5301 : typename iterator_traits<_InputIterator1>::value_type>)
5302 : __glibcxx_function_requires(_LessThanOpConcept<
5303 : typename iterator_traits<_InputIterator1>::value_type,
5304 : typename iterator_traits<_InputIterator2>::value_type>)
5305 : __glibcxx_function_requires(_LessThanOpConcept<
5306 : typename iterator_traits<_InputIterator2>::value_type,
5307 : typename iterator_traits<_InputIterator1>::value_type>)
5308 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5309 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5310 : __glibcxx_requires_irreflexive2(__first1, __last1);
5311 : __glibcxx_requires_irreflexive2(__first2, __last2);
5312 :
5313 0 : return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5314 : __first2, __last2, __result,
5315 : __gnu_cxx::__ops::__iter_less_iter());
5316 : }
5317 :
5318 : /**
5319 : * @brief Return the intersection of two sorted ranges using comparison
5320 : * functor.
5321 : * @ingroup set_algorithms
5322 : * @param __first1 Start of first range.
5323 : * @param __last1 End of first range.
5324 : * @param __first2 Start of second range.
5325 : * @param __last2 End of second range.
5326 : * @param __result Start of output range.
5327 : * @param __comp The comparison functor.
5328 : * @return End of the output range.
5329 : * @ingroup set_algorithms
5330 : *
5331 : * This operation iterates over both ranges, copying elements present in
5332 : * both ranges in order to the output range. Iterators increment for each
5333 : * range. When the current element of one range is less than the other
5334 : * according to @p __comp, that iterator advances. If an element is
5335 : * contained in both ranges according to @p __comp, the element from the
5336 : * first range is copied and both ranges advance. The output range may not
5337 : * overlap either input range.
5338 : */
5339 : template<typename _InputIterator1, typename _InputIterator2,
5340 : typename _OutputIterator, typename _Compare>
5341 : inline _OutputIterator
5342 : set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5343 : _InputIterator2 __first2, _InputIterator2 __last2,
5344 : _OutputIterator __result, _Compare __comp)
5345 : {
5346 : // concept requirements
5347 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5348 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5349 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5350 : typename iterator_traits<_InputIterator1>::value_type>)
5351 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5352 : typename iterator_traits<_InputIterator1>::value_type,
5353 : typename iterator_traits<_InputIterator2>::value_type>)
5354 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5355 : typename iterator_traits<_InputIterator2>::value_type,
5356 : typename iterator_traits<_InputIterator1>::value_type>)
5357 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5358 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5359 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5360 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5361 :
5362 : return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5363 : __first2, __last2, __result,
5364 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5365 : }
5366 :
5367 : template<typename _InputIterator1, typename _InputIterator2,
5368 : typename _OutputIterator,
5369 : typename _Compare>
5370 : _OutputIterator
5371 3 : __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5372 : _InputIterator2 __first2, _InputIterator2 __last2,
5373 : _OutputIterator __result, _Compare __comp)
5374 : {
5375 7 : while (__first1 != __last1 && __first2 != __last2)
5376 7 : if (__comp(__first1, __first2))
5377 : {
5378 3 : *__result = *__first1;
5379 3 : ++__first1;
5380 10 : ++__result;
5381 : }
5382 4 : else if (__comp(__first2, __first1))
5383 10 : ++__first2;
5384 : else
5385 : {
5386 3 : ++__first1;
5387 10 : ++__first2;
5388 : }
5389 3 : return std::copy(__first1, __last1, __result);
5390 : }
5391 :
5392 : /**
5393 : * @brief Return the difference of two sorted ranges.
5394 : * @ingroup set_algorithms
5395 : * @param __first1 Start of first range.
5396 : * @param __last1 End of first range.
5397 : * @param __first2 Start of second range.
5398 : * @param __last2 End of second range.
5399 : * @param __result Start of output range.
5400 : * @return End of the output range.
5401 : * @ingroup set_algorithms
5402 : *
5403 : * This operation iterates over both ranges, copying elements present in
5404 : * the first range but not the second in order to the output range.
5405 : * Iterators increment for each range. When the current element of the
5406 : * first range is less than the second, that element is copied and the
5407 : * iterator advances. If the current element of the second range is less,
5408 : * the iterator advances, but no element is copied. If an element is
5409 : * contained in both ranges, no elements are copied and both ranges
5410 : * advance. The output range may not overlap either input range.
5411 : */
5412 : template<typename _InputIterator1, typename _InputIterator2,
5413 : typename _OutputIterator>
5414 : inline _OutputIterator
5415 3 : set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5416 : _InputIterator2 __first2, _InputIterator2 __last2,
5417 : _OutputIterator __result)
5418 : {
5419 : // concept requirements
5420 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5421 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5422 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5423 : typename iterator_traits<_InputIterator1>::value_type>)
5424 : __glibcxx_function_requires(_LessThanOpConcept<
5425 : typename iterator_traits<_InputIterator1>::value_type,
5426 : typename iterator_traits<_InputIterator2>::value_type>)
5427 : __glibcxx_function_requires(_LessThanOpConcept<
5428 : typename iterator_traits<_InputIterator2>::value_type,
5429 : typename iterator_traits<_InputIterator1>::value_type>)
5430 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5431 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5432 : __glibcxx_requires_irreflexive2(__first1, __last1);
5433 : __glibcxx_requires_irreflexive2(__first2, __last2);
5434 :
5435 3 : return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5436 : __first2, __last2, __result,
5437 : __gnu_cxx::__ops::__iter_less_iter());
5438 : }
5439 :
5440 : /**
5441 : * @brief Return the difference of two sorted ranges using comparison
5442 : * functor.
5443 : * @ingroup set_algorithms
5444 : * @param __first1 Start of first range.
5445 : * @param __last1 End of first range.
5446 : * @param __first2 Start of second range.
5447 : * @param __last2 End of second range.
5448 : * @param __result Start of output range.
5449 : * @param __comp The comparison functor.
5450 : * @return End of the output range.
5451 : * @ingroup set_algorithms
5452 : *
5453 : * This operation iterates over both ranges, copying elements present in
5454 : * the first range but not the second in order to the output range.
5455 : * Iterators increment for each range. When the current element of the
5456 : * first range is less than the second according to @p __comp, that element
5457 : * is copied and the iterator advances. If the current element of the
5458 : * second range is less, no element is copied and the iterator advances.
5459 : * If an element is contained in both ranges according to @p __comp, no
5460 : * elements are copied and both ranges advance. The output range may not
5461 : * overlap either input range.
5462 : */
5463 : template<typename _InputIterator1, typename _InputIterator2,
5464 : typename _OutputIterator, typename _Compare>
5465 : inline _OutputIterator
5466 : set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5467 : _InputIterator2 __first2, _InputIterator2 __last2,
5468 : _OutputIterator __result, _Compare __comp)
5469 : {
5470 : // concept requirements
5471 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5472 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5473 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5474 : typename iterator_traits<_InputIterator1>::value_type>)
5475 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5476 : typename iterator_traits<_InputIterator1>::value_type,
5477 : typename iterator_traits<_InputIterator2>::value_type>)
5478 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5479 : typename iterator_traits<_InputIterator2>::value_type,
5480 : typename iterator_traits<_InputIterator1>::value_type>)
5481 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5482 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5483 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5484 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5485 :
5486 : return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5487 : __first2, __last2, __result,
5488 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5489 : }
5490 :
5491 : template<typename _InputIterator1, typename _InputIterator2,
5492 : typename _OutputIterator,
5493 : typename _Compare>
5494 : _OutputIterator
5495 : __set_symmetric_difference(_InputIterator1 __first1,
5496 : _InputIterator1 __last1,
5497 : _InputIterator2 __first2,
5498 : _InputIterator2 __last2,
5499 : _OutputIterator __result,
5500 : _Compare __comp)
5501 : {
5502 : while (__first1 != __last1 && __first2 != __last2)
5503 : if (__comp(__first1, __first2))
5504 : {
5505 : *__result = *__first1;
5506 : ++__first1;
5507 : ++__result;
5508 : }
5509 : else if (__comp(__first2, __first1))
5510 : {
5511 : *__result = *__first2;
5512 : ++__first2;
5513 : ++__result;
5514 : }
5515 : else
5516 : {
5517 : ++__first1;
5518 : ++__first2;
5519 : }
5520 : return std::copy(__first2, __last2,
5521 : std::copy(__first1, __last1, __result));
5522 : }
5523 :
5524 : /**
5525 : * @brief Return the symmetric difference of two sorted ranges.
5526 : * @ingroup set_algorithms
5527 : * @param __first1 Start of first range.
5528 : * @param __last1 End of first range.
5529 : * @param __first2 Start of second range.
5530 : * @param __last2 End of second range.
5531 : * @param __result Start of output range.
5532 : * @return End of the output range.
5533 : * @ingroup set_algorithms
5534 : *
5535 : * This operation iterates over both ranges, copying elements present in
5536 : * one range but not the other in order to the output range. Iterators
5537 : * increment for each range. When the current element of one range is less
5538 : * than the other, that element is copied and the iterator advances. If an
5539 : * element is contained in both ranges, no elements are copied and both
5540 : * ranges advance. The output range may not overlap either input range.
5541 : */
5542 : template<typename _InputIterator1, typename _InputIterator2,
5543 : typename _OutputIterator>
5544 : inline _OutputIterator
5545 : set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5546 : _InputIterator2 __first2, _InputIterator2 __last2,
5547 : _OutputIterator __result)
5548 : {
5549 : // concept requirements
5550 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5551 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5552 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5553 : typename iterator_traits<_InputIterator1>::value_type>)
5554 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5555 : typename iterator_traits<_InputIterator2>::value_type>)
5556 : __glibcxx_function_requires(_LessThanOpConcept<
5557 : typename iterator_traits<_InputIterator1>::value_type,
5558 : typename iterator_traits<_InputIterator2>::value_type>)
5559 : __glibcxx_function_requires(_LessThanOpConcept<
5560 : typename iterator_traits<_InputIterator2>::value_type,
5561 : typename iterator_traits<_InputIterator1>::value_type>)
5562 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5563 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5564 : __glibcxx_requires_irreflexive2(__first1, __last1);
5565 : __glibcxx_requires_irreflexive2(__first2, __last2);
5566 :
5567 : return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5568 : __first2, __last2, __result,
5569 : __gnu_cxx::__ops::__iter_less_iter());
5570 : }
5571 :
5572 : /**
5573 : * @brief Return the symmetric difference of two sorted ranges using
5574 : * comparison functor.
5575 : * @ingroup set_algorithms
5576 : * @param __first1 Start of first range.
5577 : * @param __last1 End of first range.
5578 : * @param __first2 Start of second range.
5579 : * @param __last2 End of second range.
5580 : * @param __result Start of output range.
5581 : * @param __comp The comparison functor.
5582 : * @return End of the output range.
5583 : * @ingroup set_algorithms
5584 : *
5585 : * This operation iterates over both ranges, copying elements present in
5586 : * one range but not the other in order to the output range. Iterators
5587 : * increment for each range. When the current element of one range is less
5588 : * than the other according to @p comp, that element is copied and the
5589 : * iterator advances. If an element is contained in both ranges according
5590 : * to @p __comp, no elements are copied and both ranges advance. The output
5591 : * range may not overlap either input range.
5592 : */
5593 : template<typename _InputIterator1, typename _InputIterator2,
5594 : typename _OutputIterator, typename _Compare>
5595 : inline _OutputIterator
5596 : set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5597 : _InputIterator2 __first2, _InputIterator2 __last2,
5598 : _OutputIterator __result,
5599 : _Compare __comp)
5600 : {
5601 : // concept requirements
5602 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5603 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5604 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5605 : typename iterator_traits<_InputIterator1>::value_type>)
5606 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5607 : typename iterator_traits<_InputIterator2>::value_type>)
5608 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5609 : typename iterator_traits<_InputIterator1>::value_type,
5610 : typename iterator_traits<_InputIterator2>::value_type>)
5611 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5612 : typename iterator_traits<_InputIterator2>::value_type,
5613 : typename iterator_traits<_InputIterator1>::value_type>)
5614 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5615 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5616 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5617 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5618 :
5619 : return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5620 : __first2, __last2, __result,
5621 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5622 : }
5623 :
5624 : template<typename _ForwardIterator, typename _Compare>
5625 : _GLIBCXX14_CONSTEXPR
5626 : _ForwardIterator
5627 : __min_element(_ForwardIterator __first, _ForwardIterator __last,
5628 : _Compare __comp)
5629 : {
5630 : if (__first == __last)
5631 : return __first;
5632 : _ForwardIterator __result = __first;
5633 : while (++__first != __last)
5634 : if (__comp(__first, __result))
5635 : __result = __first;
5636 : return __result;
5637 : }
5638 :
5639 : /**
5640 : * @brief Return the minimum element in a range.
5641 : * @ingroup sorting_algorithms
5642 : * @param __first Start of range.
5643 : * @param __last End of range.
5644 : * @return Iterator referencing the first instance of the smallest value.
5645 : */
5646 : template<typename _ForwardIterator>
5647 : _GLIBCXX14_CONSTEXPR
5648 : _ForwardIterator
5649 : inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5650 : {
5651 : // concept requirements
5652 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5653 : __glibcxx_function_requires(_LessThanComparableConcept<
5654 : typename iterator_traits<_ForwardIterator>::value_type>)
5655 : __glibcxx_requires_valid_range(__first, __last);
5656 : __glibcxx_requires_irreflexive(__first, __last);
5657 :
5658 : return _GLIBCXX_STD_A::__min_element(__first, __last,
5659 : __gnu_cxx::__ops::__iter_less_iter());
5660 : }
5661 :
5662 : /**
5663 : * @brief Return the minimum element in a range using comparison functor.
5664 : * @ingroup sorting_algorithms
5665 : * @param __first Start of range.
5666 : * @param __last End of range.
5667 : * @param __comp Comparison functor.
5668 : * @return Iterator referencing the first instance of the smallest value
5669 : * according to __comp.
5670 : */
5671 : template<typename _ForwardIterator, typename _Compare>
5672 : _GLIBCXX14_CONSTEXPR
5673 : inline _ForwardIterator
5674 : min_element(_ForwardIterator __first, _ForwardIterator __last,
5675 : _Compare __comp)
5676 : {
5677 : // concept requirements
5678 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5679 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5680 : typename iterator_traits<_ForwardIterator>::value_type,
5681 : typename iterator_traits<_ForwardIterator>::value_type>)
5682 : __glibcxx_requires_valid_range(__first, __last);
5683 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5684 :
5685 : return _GLIBCXX_STD_A::__min_element(__first, __last,
5686 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5687 : }
5688 :
5689 : template<typename _ForwardIterator, typename _Compare>
5690 : _GLIBCXX14_CONSTEXPR
5691 : _ForwardIterator
5692 : __max_element(_ForwardIterator __first, _ForwardIterator __last,
5693 : _Compare __comp)
5694 : {
5695 : if (__first == __last) return __first;
5696 : _ForwardIterator __result = __first;
5697 : while (++__first != __last)
5698 : if (__comp(__result, __first))
5699 : __result = __first;
5700 : return __result;
5701 : }
5702 :
5703 : /**
5704 : * @brief Return the maximum element in a range.
5705 : * @ingroup sorting_algorithms
5706 : * @param __first Start of range.
5707 : * @param __last End of range.
5708 : * @return Iterator referencing the first instance of the largest value.
5709 : */
5710 : template<typename _ForwardIterator>
5711 : _GLIBCXX14_CONSTEXPR
5712 : inline _ForwardIterator
5713 : max_element(_ForwardIterator __first, _ForwardIterator __last)
5714 : {
5715 : // concept requirements
5716 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5717 : __glibcxx_function_requires(_LessThanComparableConcept<
5718 : typename iterator_traits<_ForwardIterator>::value_type>)
5719 : __glibcxx_requires_valid_range(__first, __last);
5720 : __glibcxx_requires_irreflexive(__first, __last);
5721 :
5722 : return _GLIBCXX_STD_A::__max_element(__first, __last,
5723 : __gnu_cxx::__ops::__iter_less_iter());
5724 : }
5725 :
5726 : /**
5727 : * @brief Return the maximum element in a range using comparison functor.
5728 : * @ingroup sorting_algorithms
5729 : * @param __first Start of range.
5730 : * @param __last End of range.
5731 : * @param __comp Comparison functor.
5732 : * @return Iterator referencing the first instance of the largest value
5733 : * according to __comp.
5734 : */
5735 : template<typename _ForwardIterator, typename _Compare>
5736 : _GLIBCXX14_CONSTEXPR
5737 : inline _ForwardIterator
5738 : max_element(_ForwardIterator __first, _ForwardIterator __last,
5739 : _Compare __comp)
5740 : {
5741 : // concept requirements
5742 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5743 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5744 : typename iterator_traits<_ForwardIterator>::value_type,
5745 : typename iterator_traits<_ForwardIterator>::value_type>)
5746 : __glibcxx_requires_valid_range(__first, __last);
5747 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5748 :
5749 : return _GLIBCXX_STD_A::__max_element(__first, __last,
5750 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5751 : }
5752 :
5753 : #if __cplusplus >= 201402L
5754 : /// Reservoir sampling algorithm.
5755 : template<typename _InputIterator, typename _RandomAccessIterator,
5756 : typename _Size, typename _UniformRandomBitGenerator>
5757 : _RandomAccessIterator
5758 : __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5759 : _RandomAccessIterator __out, random_access_iterator_tag,
5760 : _Size __n, _UniformRandomBitGenerator&& __g)
5761 : {
5762 : using __distrib_type = uniform_int_distribution<_Size>;
5763 : using __param_type = typename __distrib_type::param_type;
5764 : __distrib_type __d{};
5765 : _Size __sample_sz = 0;
5766 : while (__first != __last && __sample_sz != __n)
5767 : {
5768 : __out[__sample_sz++] = *__first;
5769 : ++__first;
5770 : }
5771 : for (auto __pop_sz = __sample_sz; __first != __last;
5772 : ++__first, (void) ++__pop_sz)
5773 : {
5774 : const auto __k = __d(__g, __param_type{0, __pop_sz});
5775 : if (__k < __n)
5776 : __out[__k] = *__first;
5777 : }
5778 : return __out + __sample_sz;
5779 : }
5780 :
5781 : /// Selection sampling algorithm.
5782 : template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5783 : typename _Size, typename _UniformRandomBitGenerator>
5784 : _OutputIterator
5785 : __sample(_ForwardIterator __first, _ForwardIterator __last,
5786 : forward_iterator_tag,
5787 : _OutputIterator __out, _Cat,
5788 : _Size __n, _UniformRandomBitGenerator&& __g)
5789 : {
5790 : using __distrib_type = uniform_int_distribution<_Size>;
5791 : using __param_type = typename __distrib_type::param_type;
5792 : using _USize = make_unsigned_t<_Size>;
5793 : using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5794 : using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5795 :
5796 : if (__first == __last)
5797 : return __out;
5798 :
5799 : __distrib_type __d{};
5800 : _Size __unsampled_sz = std::distance(__first, __last);
5801 : __n = std::min(__n, __unsampled_sz);
5802 :
5803 : // If possible, we use __gen_two_uniform_ints to efficiently produce
5804 : // two random numbers using a single distribution invocation:
5805 :
5806 : const __uc_type __urngrange = __g.max() - __g.min();
5807 : if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5808 : // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without
5809 : // wrapping issues.
5810 : {
5811 : while (__n != 0 && __unsampled_sz >= 2)
5812 : {
5813 : const pair<_Size, _Size> __p =
5814 : __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g);
5815 :
5816 : --__unsampled_sz;
5817 : if (__p.first < __n)
5818 : {
5819 : *__out++ = *__first;
5820 : --__n;
5821 : }
5822 :
5823 : ++__first;
5824 :
5825 : if (__n == 0) break;
5826 :
5827 : --__unsampled_sz;
5828 : if (__p.second < __n)
5829 : {
5830 : *__out++ = *__first;
5831 : --__n;
5832 : }
5833 :
5834 : ++__first;
5835 : }
5836 : }
5837 :
5838 : // The loop above is otherwise equivalent to this one-at-a-time version:
5839 :
5840 : for (; __n != 0; ++__first)
5841 : if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5842 : {
5843 : *__out++ = *__first;
5844 : --__n;
5845 : }
5846 : return __out;
5847 : }
5848 :
5849 : #if __cplusplus > 201402L
5850 : #define __cpp_lib_sample 201603
5851 : /// Take a random sample from a population.
5852 : template<typename _PopulationIterator, typename _SampleIterator,
5853 : typename _Distance, typename _UniformRandomBitGenerator>
5854 : _SampleIterator
5855 : sample(_PopulationIterator __first, _PopulationIterator __last,
5856 : _SampleIterator __out, _Distance __n,
5857 : _UniformRandomBitGenerator&& __g)
5858 : {
5859 : using __pop_cat = typename
5860 : std::iterator_traits<_PopulationIterator>::iterator_category;
5861 : using __samp_cat = typename
5862 : std::iterator_traits<_SampleIterator>::iterator_category;
5863 :
5864 : static_assert(
5865 : __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5866 : is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5867 : "output range must use a RandomAccessIterator when input range"
5868 : " does not meet the ForwardIterator requirements");
5869 :
5870 : static_assert(is_integral<_Distance>::value,
5871 : "sample size must be an integer type");
5872 :
5873 : typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5874 : return _GLIBCXX_STD_A::
5875 : __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5876 : std::forward<_UniformRandomBitGenerator>(__g));
5877 : }
5878 : #endif // C++17
5879 : #endif // C++14
5880 :
5881 : _GLIBCXX_END_NAMESPACE_ALGO
5882 : _GLIBCXX_END_NAMESPACE_VERSION
5883 : } // namespace std
5884 :
5885 : #endif /* _STL_ALGO_H */
|
