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