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