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