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