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