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