Line data Source code
1 : // Algorithm implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2016 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 <bits/uniform_int_dist.h>
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 : inline namespace _V2
1241 : {
1242 :
1243 : /// This is a helper function for the rotate algorithm.
1244 : template<typename _ForwardIterator>
1245 : _ForwardIterator
1246 : __rotate(_ForwardIterator __first,
1247 : _ForwardIterator __middle,
1248 : _ForwardIterator __last,
1249 : forward_iterator_tag)
1250 : {
1251 : if (__first == __middle)
1252 : return __last;
1253 : else if (__last == __middle)
1254 : return __first;
1255 :
1256 : _ForwardIterator __first2 = __middle;
1257 : do
1258 : {
1259 : std::iter_swap(__first, __first2);
1260 : ++__first;
1261 : ++__first2;
1262 : if (__first == __middle)
1263 : __middle = __first2;
1264 : }
1265 : while (__first2 != __last);
1266 :
1267 : _ForwardIterator __ret = __first;
1268 :
1269 : __first2 = __middle;
1270 :
1271 : while (__first2 != __last)
1272 : {
1273 : std::iter_swap(__first, __first2);
1274 : ++__first;
1275 : ++__first2;
1276 : if (__first == __middle)
1277 : __middle = __first2;
1278 : else if (__first2 == __last)
1279 : __first2 = __middle;
1280 : }
1281 : return __ret;
1282 : }
1283 :
1284 : /// This is a helper function for the rotate algorithm.
1285 : template<typename _BidirectionalIterator>
1286 : _BidirectionalIterator
1287 : __rotate(_BidirectionalIterator __first,
1288 : _BidirectionalIterator __middle,
1289 : _BidirectionalIterator __last,
1290 : bidirectional_iterator_tag)
1291 : {
1292 : // concept requirements
1293 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1294 : _BidirectionalIterator>)
1295 :
1296 : if (__first == __middle)
1297 : return __last;
1298 : else if (__last == __middle)
1299 : return __first;
1300 :
1301 : std::__reverse(__first, __middle, bidirectional_iterator_tag());
1302 : std::__reverse(__middle, __last, bidirectional_iterator_tag());
1303 :
1304 : while (__first != __middle && __middle != __last)
1305 : {
1306 : std::iter_swap(__first, --__last);
1307 : ++__first;
1308 : }
1309 :
1310 : if (__first == __middle)
1311 : {
1312 : std::__reverse(__middle, __last, bidirectional_iterator_tag());
1313 : return __last;
1314 : }
1315 : else
1316 : {
1317 : std::__reverse(__first, __middle, bidirectional_iterator_tag());
1318 : return __first;
1319 : }
1320 : }
1321 :
1322 : /// This is a helper function for the rotate algorithm.
1323 : template<typename _RandomAccessIterator>
1324 : _RandomAccessIterator
1325 : __rotate(_RandomAccessIterator __first,
1326 : _RandomAccessIterator __middle,
1327 : _RandomAccessIterator __last,
1328 : random_access_iterator_tag)
1329 : {
1330 : // concept requirements
1331 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1332 : _RandomAccessIterator>)
1333 :
1334 : if (__first == __middle)
1335 : return __last;
1336 : else if (__last == __middle)
1337 : return __first;
1338 :
1339 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1340 : _Distance;
1341 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
1342 : _ValueType;
1343 :
1344 : _Distance __n = __last - __first;
1345 : _Distance __k = __middle - __first;
1346 :
1347 : if (__k == __n - __k)
1348 : {
1349 : std::swap_ranges(__first, __middle, __middle);
1350 : return __middle;
1351 : }
1352 :
1353 : _RandomAccessIterator __p = __first;
1354 : _RandomAccessIterator __ret = __first + (__last - __middle);
1355 :
1356 : for (;;)
1357 : {
1358 : if (__k < __n - __k)
1359 : {
1360 : if (__is_pod(_ValueType) && __k == 1)
1361 : {
1362 : _ValueType __t = _GLIBCXX_MOVE(*__p);
1363 : _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1364 : *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1365 : return __ret;
1366 : }
1367 : _RandomAccessIterator __q = __p + __k;
1368 : for (_Distance __i = 0; __i < __n - __k; ++ __i)
1369 : {
1370 : std::iter_swap(__p, __q);
1371 : ++__p;
1372 : ++__q;
1373 : }
1374 : __n %= __k;
1375 : if (__n == 0)
1376 : return __ret;
1377 : std::swap(__n, __k);
1378 : __k = __n - __k;
1379 : }
1380 : else
1381 : {
1382 : __k = __n - __k;
1383 : if (__is_pod(_ValueType) && __k == 1)
1384 : {
1385 : _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1386 : _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1387 : *__p = _GLIBCXX_MOVE(__t);
1388 : return __ret;
1389 : }
1390 : _RandomAccessIterator __q = __p + __n;
1391 : __p = __q - __k;
1392 : for (_Distance __i = 0; __i < __n - __k; ++ __i)
1393 : {
1394 : --__p;
1395 : --__q;
1396 : std::iter_swap(__p, __q);
1397 : }
1398 : __n %= __k;
1399 : if (__n == 0)
1400 : return __ret;
1401 : std::swap(__n, __k);
1402 : }
1403 : }
1404 : }
1405 :
1406 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1407 : // DR 488. rotate throws away useful information
1408 : /**
1409 : * @brief Rotate the elements of a sequence.
1410 : * @ingroup mutating_algorithms
1411 : * @param __first A forward iterator.
1412 : * @param __middle A forward iterator.
1413 : * @param __last A forward iterator.
1414 : * @return first + (last - middle).
1415 : *
1416 : * Rotates the elements of the range @p [__first,__last) by
1417 : * @p (__middle - __first) positions so that the element at @p __middle
1418 : * is moved to @p __first, the element at @p __middle+1 is moved to
1419 : * @p __first+1 and so on for each element in the range
1420 : * @p [__first,__last).
1421 : *
1422 : * This effectively swaps the ranges @p [__first,__middle) and
1423 : * @p [__middle,__last).
1424 : *
1425 : * Performs
1426 : * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1427 : * for each @p n in the range @p [0,__last-__first).
1428 : */
1429 : template<typename _ForwardIterator>
1430 : inline _ForwardIterator
1431 : rotate(_ForwardIterator __first, _ForwardIterator __middle,
1432 : _ForwardIterator __last)
1433 : {
1434 : // concept requirements
1435 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1436 : _ForwardIterator>)
1437 : __glibcxx_requires_valid_range(__first, __middle);
1438 : __glibcxx_requires_valid_range(__middle, __last);
1439 :
1440 : return std::__rotate(__first, __middle, __last,
1441 : std::__iterator_category(__first));
1442 : }
1443 :
1444 : } // namespace _V2
1445 :
1446 : /**
1447 : * @brief Copy a sequence, rotating its elements.
1448 : * @ingroup mutating_algorithms
1449 : * @param __first A forward iterator.
1450 : * @param __middle A forward iterator.
1451 : * @param __last A forward iterator.
1452 : * @param __result An output iterator.
1453 : * @return An iterator designating the end of the resulting sequence.
1454 : *
1455 : * Copies the elements of the range @p [__first,__last) to the
1456 : * range beginning at @result, rotating the copied elements by
1457 : * @p (__middle-__first) positions so that the element at @p __middle
1458 : * is moved to @p __result, the element at @p __middle+1 is moved
1459 : * to @p __result+1 and so on for each element in the range @p
1460 : * [__first,__last).
1461 : *
1462 : * Performs
1463 : * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1464 : * for each @p n in the range @p [0,__last-__first).
1465 : */
1466 : template<typename _ForwardIterator, typename _OutputIterator>
1467 : inline _OutputIterator
1468 : rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1469 : _ForwardIterator __last, _OutputIterator __result)
1470 : {
1471 : // concept requirements
1472 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1473 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1474 : typename iterator_traits<_ForwardIterator>::value_type>)
1475 : __glibcxx_requires_valid_range(__first, __middle);
1476 : __glibcxx_requires_valid_range(__middle, __last);
1477 :
1478 : return std::copy(__first, __middle,
1479 : std::copy(__middle, __last, __result));
1480 : }
1481 :
1482 : /// This is a helper function...
1483 : template<typename _ForwardIterator, typename _Predicate>
1484 : _ForwardIterator
1485 : __partition(_ForwardIterator __first, _ForwardIterator __last,
1486 : _Predicate __pred, forward_iterator_tag)
1487 : {
1488 : if (__first == __last)
1489 : return __first;
1490 :
1491 : while (__pred(*__first))
1492 : if (++__first == __last)
1493 : return __first;
1494 :
1495 : _ForwardIterator __next = __first;
1496 :
1497 : while (++__next != __last)
1498 : if (__pred(*__next))
1499 : {
1500 : std::iter_swap(__first, __next);
1501 : ++__first;
1502 : }
1503 :
1504 : return __first;
1505 : }
1506 :
1507 : /// This is a helper function...
1508 : template<typename _BidirectionalIterator, typename _Predicate>
1509 : _BidirectionalIterator
1510 : __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1511 : _Predicate __pred, bidirectional_iterator_tag)
1512 : {
1513 : while (true)
1514 : {
1515 : while (true)
1516 : if (__first == __last)
1517 : return __first;
1518 : else if (__pred(*__first))
1519 : ++__first;
1520 : else
1521 : break;
1522 : --__last;
1523 : while (true)
1524 : if (__first == __last)
1525 : return __first;
1526 : else if (!bool(__pred(*__last)))
1527 : --__last;
1528 : else
1529 : break;
1530 : std::iter_swap(__first, __last);
1531 : ++__first;
1532 : }
1533 : }
1534 :
1535 : // partition
1536 :
1537 : /// This is a helper function...
1538 : /// Requires __first != __last and !__pred(__first)
1539 : /// and __len == distance(__first, __last).
1540 : ///
1541 : /// !__pred(__first) allows us to guarantee that we don't
1542 : /// move-assign an element onto itself.
1543 : template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1544 : typename _Distance>
1545 : _ForwardIterator
1546 : __stable_partition_adaptive(_ForwardIterator __first,
1547 : _ForwardIterator __last,
1548 : _Predicate __pred, _Distance __len,
1549 : _Pointer __buffer,
1550 : _Distance __buffer_size)
1551 : {
1552 : if (__len == 1)
1553 : return __first;
1554 :
1555 : if (__len <= __buffer_size)
1556 : {
1557 : _ForwardIterator __result1 = __first;
1558 : _Pointer __result2 = __buffer;
1559 :
1560 : // The precondition guarantees that !__pred(__first), so
1561 : // move that element to the buffer before starting the loop.
1562 : // This ensures that we only call __pred once per element.
1563 : *__result2 = _GLIBCXX_MOVE(*__first);
1564 : ++__result2;
1565 : ++__first;
1566 : for (; __first != __last; ++__first)
1567 : if (__pred(__first))
1568 : {
1569 : *__result1 = _GLIBCXX_MOVE(*__first);
1570 : ++__result1;
1571 : }
1572 : else
1573 : {
1574 : *__result2 = _GLIBCXX_MOVE(*__first);
1575 : ++__result2;
1576 : }
1577 :
1578 : _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1579 : return __result1;
1580 : }
1581 :
1582 : _ForwardIterator __middle = __first;
1583 : std::advance(__middle, __len / 2);
1584 : _ForwardIterator __left_split =
1585 : std::__stable_partition_adaptive(__first, __middle, __pred,
1586 : __len / 2, __buffer,
1587 : __buffer_size);
1588 :
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 :
1595 : if (__right_len)
1596 : __right_split =
1597 : std::__stable_partition_adaptive(__right_split, __last, __pred,
1598 : __right_len,
1599 : __buffer, __buffer_size);
1600 :
1601 : std::rotate(__left_split, __middle, __right_split);
1602 : std::advance(__left_split, std::distance(__middle, __right_split));
1603 : return __left_split;
1604 : }
1605 :
1606 : template<typename _ForwardIterator, typename _Predicate>
1607 : _ForwardIterator
1608 : __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1609 : _Predicate __pred)
1610 : {
1611 : __first = std::__find_if_not(__first, __last, __pred);
1612 :
1613 : if (__first == __last)
1614 : return __first;
1615 :
1616 : typedef typename iterator_traits<_ForwardIterator>::value_type
1617 : _ValueType;
1618 : typedef typename iterator_traits<_ForwardIterator>::difference_type
1619 : _DistanceType;
1620 :
1621 : _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);
1622 : return
1623 : std::__stable_partition_adaptive(__first, __last, __pred,
1624 : _DistanceType(__buf.requested_size()),
1625 : __buf.begin(),
1626 : _DistanceType(__buf.size()));
1627 : }
1628 :
1629 : /**
1630 : * @brief Move elements for which a predicate is true to the beginning
1631 : * of a sequence, preserving relative ordering.
1632 : * @ingroup mutating_algorithms
1633 : * @param __first A forward iterator.
1634 : * @param __last A forward iterator.
1635 : * @param __pred A predicate functor.
1636 : * @return An iterator @p middle such that @p __pred(i) is true for each
1637 : * iterator @p i in the range @p [first,middle) and false for each @p i
1638 : * in the range @p [middle,last).
1639 : *
1640 : * Performs the same function as @p partition() with the additional
1641 : * guarantee that the relative ordering of elements in each group is
1642 : * preserved, so any two elements @p x and @p y in the range
1643 : * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1644 : * relative ordering after calling @p stable_partition().
1645 : */
1646 : template<typename _ForwardIterator, typename _Predicate>
1647 : inline _ForwardIterator
1648 : stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1649 : _Predicate __pred)
1650 : {
1651 : // concept requirements
1652 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1653 : _ForwardIterator>)
1654 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1655 : typename iterator_traits<_ForwardIterator>::value_type>)
1656 : __glibcxx_requires_valid_range(__first, __last);
1657 :
1658 : return std::__stable_partition(__first, __last,
1659 : __gnu_cxx::__ops::__pred_iter(__pred));
1660 : }
1661 :
1662 : /// This is a helper function for the sort routines.
1663 : template<typename _RandomAccessIterator, typename _Compare>
1664 : void
1665 0 : __heap_select(_RandomAccessIterator __first,
1666 : _RandomAccessIterator __middle,
1667 : _RandomAccessIterator __last, _Compare __comp)
1668 : {
1669 0 : std::__make_heap(__first, __middle, __comp);
1670 0 : for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1671 0 : if (__comp(__i, __first))
1672 0 : std::__pop_heap(__first, __middle, __i, __comp);
1673 0 : }
1674 :
1675 : // partial_sort
1676 :
1677 : template<typename _InputIterator, typename _RandomAccessIterator,
1678 : typename _Compare>
1679 : _RandomAccessIterator
1680 : __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1681 : _RandomAccessIterator __result_first,
1682 : _RandomAccessIterator __result_last,
1683 : _Compare __comp)
1684 : {
1685 : typedef typename iterator_traits<_InputIterator>::value_type
1686 : _InputValueType;
1687 : typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1688 : typedef typename _RItTraits::difference_type _DistanceType;
1689 :
1690 : if (__result_first == __result_last)
1691 : return __result_last;
1692 : _RandomAccessIterator __result_real_last = __result_first;
1693 : while (__first != __last && __result_real_last != __result_last)
1694 : {
1695 : *__result_real_last = *__first;
1696 : ++__result_real_last;
1697 : ++__first;
1698 : }
1699 :
1700 : std::__make_heap(__result_first, __result_real_last, __comp);
1701 : while (__first != __last)
1702 : {
1703 : if (__comp(__first, __result_first))
1704 : std::__adjust_heap(__result_first, _DistanceType(0),
1705 : _DistanceType(__result_real_last
1706 : - __result_first),
1707 : _InputValueType(*__first), __comp);
1708 : ++__first;
1709 : }
1710 : std::__sort_heap(__result_first, __result_real_last, __comp);
1711 : return __result_real_last;
1712 : }
1713 :
1714 : /**
1715 : * @brief Copy the smallest elements of a sequence.
1716 : * @ingroup sorting_algorithms
1717 : * @param __first An iterator.
1718 : * @param __last Another iterator.
1719 : * @param __result_first A random-access iterator.
1720 : * @param __result_last Another random-access iterator.
1721 : * @return An iterator indicating the end of the resulting sequence.
1722 : *
1723 : * Copies and sorts the smallest N values from the range @p [__first,__last)
1724 : * to the range beginning at @p __result_first, where the number of
1725 : * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1726 : * @p (__result_last-__result_first).
1727 : * After the sort if @e i and @e j are iterators in the range
1728 : * @p [__result_first,__result_first+N) such that i precedes j then
1729 : * *j<*i is false.
1730 : * The value returned is @p __result_first+N.
1731 : */
1732 : template<typename _InputIterator, typename _RandomAccessIterator>
1733 : inline _RandomAccessIterator
1734 : partial_sort_copy(_InputIterator __first, _InputIterator __last,
1735 : _RandomAccessIterator __result_first,
1736 : _RandomAccessIterator __result_last)
1737 : {
1738 : #ifdef _GLIBCXX_CONCEPT_CHECKS
1739 : typedef typename iterator_traits<_InputIterator>::value_type
1740 : _InputValueType;
1741 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
1742 : _OutputValueType;
1743 : #endif
1744 :
1745 : // concept requirements
1746 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1747 : __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1748 : _OutputValueType>)
1749 : __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1750 : _OutputValueType>)
1751 : __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1752 : __glibcxx_requires_valid_range(__first, __last);
1753 : __glibcxx_requires_irreflexive(__first, __last);
1754 : __glibcxx_requires_valid_range(__result_first, __result_last);
1755 :
1756 : return std::__partial_sort_copy(__first, __last,
1757 : __result_first, __result_last,
1758 : __gnu_cxx::__ops::__iter_less_iter());
1759 : }
1760 :
1761 : /**
1762 : * @brief Copy the smallest elements of a sequence using a predicate for
1763 : * comparison.
1764 : * @ingroup sorting_algorithms
1765 : * @param __first An input iterator.
1766 : * @param __last Another input iterator.
1767 : * @param __result_first A random-access iterator.
1768 : * @param __result_last Another random-access iterator.
1769 : * @param __comp A comparison functor.
1770 : * @return An iterator indicating the end of the resulting sequence.
1771 : *
1772 : * Copies and sorts the smallest N values from the range @p [__first,__last)
1773 : * to the range beginning at @p result_first, where the number of
1774 : * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1775 : * @p (__result_last-__result_first).
1776 : * After the sort if @e i and @e j are iterators in the range
1777 : * @p [__result_first,__result_first+N) such that i precedes j then
1778 : * @p __comp(*j,*i) is false.
1779 : * The value returned is @p __result_first+N.
1780 : */
1781 : template<typename _InputIterator, typename _RandomAccessIterator,
1782 : typename _Compare>
1783 : inline _RandomAccessIterator
1784 : partial_sort_copy(_InputIterator __first, _InputIterator __last,
1785 : _RandomAccessIterator __result_first,
1786 : _RandomAccessIterator __result_last,
1787 : _Compare __comp)
1788 : {
1789 : #ifdef _GLIBCXX_CONCEPT_CHECKS
1790 : typedef typename iterator_traits<_InputIterator>::value_type
1791 : _InputValueType;
1792 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
1793 : _OutputValueType;
1794 : #endif
1795 :
1796 : // concept requirements
1797 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1798 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1799 : _RandomAccessIterator>)
1800 : __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1801 : _OutputValueType>)
1802 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1803 : _InputValueType, _OutputValueType>)
1804 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1805 : _OutputValueType, _OutputValueType>)
1806 : __glibcxx_requires_valid_range(__first, __last);
1807 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1808 : __glibcxx_requires_valid_range(__result_first, __result_last);
1809 :
1810 : return std::__partial_sort_copy(__first, __last,
1811 : __result_first, __result_last,
1812 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
1813 : }
1814 :
1815 : /// This is a helper function for the sort routine.
1816 : template<typename _RandomAccessIterator, typename _Compare>
1817 : void
1818 0 : __unguarded_linear_insert(_RandomAccessIterator __last,
1819 : _Compare __comp)
1820 : {
1821 : typename iterator_traits<_RandomAccessIterator>::value_type
1822 0 : __val = _GLIBCXX_MOVE(*__last);
1823 0 : _RandomAccessIterator __next = __last;
1824 0 : --__next;
1825 0 : while (__comp(__val, __next))
1826 : {
1827 0 : *__last = _GLIBCXX_MOVE(*__next);
1828 0 : __last = __next;
1829 0 : --__next;
1830 : }
1831 0 : *__last = _GLIBCXX_MOVE(__val);
1832 0 : }
1833 :
1834 : /// This is a helper function for the sort routine.
1835 : template<typename _RandomAccessIterator, typename _Compare>
1836 : void
1837 0 : __insertion_sort(_RandomAccessIterator __first,
1838 : _RandomAccessIterator __last, _Compare __comp)
1839 : {
1840 0 : if (__first == __last) return;
1841 :
1842 0 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1843 : {
1844 0 : if (__comp(__i, __first))
1845 : {
1846 : typename iterator_traits<_RandomAccessIterator>::value_type
1847 0 : __val = _GLIBCXX_MOVE(*__i);
1848 0 : _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1849 0 : *__first = _GLIBCXX_MOVE(__val);
1850 : }
1851 : else
1852 0 : std::__unguarded_linear_insert(__i,
1853 : __gnu_cxx::__ops::__val_comp_iter(__comp));
1854 : }
1855 : }
1856 :
1857 : /// This is a helper function for the sort routine.
1858 : template<typename _RandomAccessIterator, typename _Compare>
1859 : inline void
1860 0 : __unguarded_insertion_sort(_RandomAccessIterator __first,
1861 : _RandomAccessIterator __last, _Compare __comp)
1862 : {
1863 0 : for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1864 0 : std::__unguarded_linear_insert(__i,
1865 : __gnu_cxx::__ops::__val_comp_iter(__comp));
1866 0 : }
1867 :
1868 : /**
1869 : * @doctodo
1870 : * This controls some aspect of the sort routines.
1871 : */
1872 : enum { _S_threshold = 16 };
1873 :
1874 : /// This is a helper function for the sort routine.
1875 : template<typename _RandomAccessIterator, typename _Compare>
1876 : void
1877 0 : __final_insertion_sort(_RandomAccessIterator __first,
1878 : _RandomAccessIterator __last, _Compare __comp)
1879 : {
1880 0 : if (__last - __first > int(_S_threshold))
1881 : {
1882 0 : std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1883 0 : std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1884 : __comp);
1885 : }
1886 : else
1887 0 : std::__insertion_sort(__first, __last, __comp);
1888 0 : }
1889 :
1890 : /// This is a helper function...
1891 : template<typename _RandomAccessIterator, typename _Compare>
1892 : _RandomAccessIterator
1893 0 : __unguarded_partition(_RandomAccessIterator __first,
1894 : _RandomAccessIterator __last,
1895 : _RandomAccessIterator __pivot, _Compare __comp)
1896 : {
1897 0 : while (true)
1898 : {
1899 0 : while (__comp(__first, __pivot))
1900 0 : ++__first;
1901 0 : --__last;
1902 0 : while (__comp(__pivot, __last))
1903 0 : --__last;
1904 0 : if (!(__first < __last))
1905 0 : return __first;
1906 0 : std::iter_swap(__first, __last);
1907 0 : ++__first;
1908 : }
1909 : }
1910 :
1911 : /// This is a helper function...
1912 : template<typename _RandomAccessIterator, typename _Compare>
1913 : inline _RandomAccessIterator
1914 0 : __unguarded_partition_pivot(_RandomAccessIterator __first,
1915 : _RandomAccessIterator __last, _Compare __comp)
1916 : {
1917 0 : _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1918 0 : std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
1919 : __comp);
1920 0 : return std::__unguarded_partition(__first + 1, __last, __first, __comp);
1921 : }
1922 :
1923 : template<typename _RandomAccessIterator, typename _Compare>
1924 : inline void
1925 0 : __partial_sort(_RandomAccessIterator __first,
1926 : _RandomAccessIterator __middle,
1927 : _RandomAccessIterator __last,
1928 : _Compare __comp)
1929 : {
1930 0 : std::__heap_select(__first, __middle, __last, __comp);
1931 0 : std::__sort_heap(__first, __middle, __comp);
1932 0 : }
1933 :
1934 : /// This is a helper function for the sort routine.
1935 : template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1936 : void
1937 0 : __introsort_loop(_RandomAccessIterator __first,
1938 : _RandomAccessIterator __last,
1939 : _Size __depth_limit, _Compare __comp)
1940 : {
1941 0 : while (__last - __first > int(_S_threshold))
1942 : {
1943 0 : if (__depth_limit == 0)
1944 : {
1945 0 : std::__partial_sort(__first, __last, __last, __comp);
1946 0 : return;
1947 : }
1948 0 : --__depth_limit;
1949 : _RandomAccessIterator __cut =
1950 0 : std::__unguarded_partition_pivot(__first, __last, __comp);
1951 0 : std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1952 0 : __last = __cut;
1953 : }
1954 : }
1955 :
1956 : // sort
1957 :
1958 : template<typename _RandomAccessIterator, typename _Compare>
1959 : inline void
1960 0 : __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1961 : _Compare __comp)
1962 : {
1963 0 : if (__first != __last)
1964 : {
1965 0 : std::__introsort_loop(__first, __last,
1966 0 : std::__lg(__last - __first) * 2,
1967 : __comp);
1968 0 : std::__final_insertion_sort(__first, __last, __comp);
1969 : }
1970 0 : }
1971 :
1972 : template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1973 : void
1974 : __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1975 : _RandomAccessIterator __last, _Size __depth_limit,
1976 : _Compare __comp)
1977 : {
1978 : while (__last - __first > 3)
1979 : {
1980 : if (__depth_limit == 0)
1981 : {
1982 : std::__heap_select(__first, __nth + 1, __last, __comp);
1983 : // Place the nth largest element in its final position.
1984 : std::iter_swap(__first, __nth);
1985 : return;
1986 : }
1987 : --__depth_limit;
1988 : _RandomAccessIterator __cut =
1989 : std::__unguarded_partition_pivot(__first, __last, __comp);
1990 : if (__cut <= __nth)
1991 : __first = __cut;
1992 : else
1993 : __last = __cut;
1994 : }
1995 : std::__insertion_sort(__first, __last, __comp);
1996 : }
1997 :
1998 : // nth_element
1999 :
2000 : // lower_bound moved to stl_algobase.h
2001 :
2002 : /**
2003 : * @brief Finds the first position in which @p __val could be inserted
2004 : * without changing the ordering.
2005 : * @ingroup binary_search_algorithms
2006 : * @param __first An iterator.
2007 : * @param __last Another iterator.
2008 : * @param __val The search term.
2009 : * @param __comp A functor to use for comparisons.
2010 : * @return An iterator pointing to the first element <em>not less
2011 : * than</em> @p __val, or end() if every element is less
2012 : * than @p __val.
2013 : * @ingroup binary_search_algorithms
2014 : *
2015 : * The comparison function should have the same effects on ordering as
2016 : * the function used for the initial sort.
2017 : */
2018 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2019 : inline _ForwardIterator
2020 : lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2021 : const _Tp& __val, _Compare __comp)
2022 : {
2023 : // concept requirements
2024 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2025 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2026 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2027 : __glibcxx_requires_partitioned_lower_pred(__first, __last,
2028 : __val, __comp);
2029 :
2030 : return std::__lower_bound(__first, __last, __val,
2031 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2032 : }
2033 :
2034 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2035 : _ForwardIterator
2036 : __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2037 : const _Tp& __val, _Compare __comp)
2038 : {
2039 : typedef typename iterator_traits<_ForwardIterator>::difference_type
2040 : _DistanceType;
2041 :
2042 : _DistanceType __len = std::distance(__first, __last);
2043 :
2044 : while (__len > 0)
2045 : {
2046 : _DistanceType __half = __len >> 1;
2047 : _ForwardIterator __middle = __first;
2048 : std::advance(__middle, __half);
2049 : if (__comp(__val, __middle))
2050 : __len = __half;
2051 : else
2052 : {
2053 : __first = __middle;
2054 : ++__first;
2055 : __len = __len - __half - 1;
2056 : }
2057 : }
2058 : return __first;
2059 : }
2060 :
2061 : /**
2062 : * @brief Finds the last position in which @p __val could be inserted
2063 : * without changing the ordering.
2064 : * @ingroup binary_search_algorithms
2065 : * @param __first An iterator.
2066 : * @param __last Another iterator.
2067 : * @param __val The search term.
2068 : * @return An iterator pointing to the first element greater than @p __val,
2069 : * or end() if no elements are greater than @p __val.
2070 : * @ingroup binary_search_algorithms
2071 : */
2072 : template<typename _ForwardIterator, typename _Tp>
2073 : inline _ForwardIterator
2074 : upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2075 : const _Tp& __val)
2076 : {
2077 : // concept requirements
2078 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2079 : __glibcxx_function_requires(_LessThanOpConcept<
2080 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2081 : __glibcxx_requires_partitioned_upper(__first, __last, __val);
2082 :
2083 : return std::__upper_bound(__first, __last, __val,
2084 : __gnu_cxx::__ops::__val_less_iter());
2085 : }
2086 :
2087 : /**
2088 : * @brief Finds the last position in which @p __val could be inserted
2089 : * without changing the ordering.
2090 : * @ingroup binary_search_algorithms
2091 : * @param __first An iterator.
2092 : * @param __last Another iterator.
2093 : * @param __val The search term.
2094 : * @param __comp A functor to use for comparisons.
2095 : * @return An iterator pointing to the first element greater than @p __val,
2096 : * or end() if no elements are greater than @p __val.
2097 : * @ingroup binary_search_algorithms
2098 : *
2099 : * The comparison function should have the same effects on ordering as
2100 : * the function used for the initial sort.
2101 : */
2102 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2103 : inline _ForwardIterator
2104 : upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2105 : const _Tp& __val, _Compare __comp)
2106 : {
2107 : // concept requirements
2108 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2109 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2110 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2111 : __glibcxx_requires_partitioned_upper_pred(__first, __last,
2112 : __val, __comp);
2113 :
2114 : return std::__upper_bound(__first, __last, __val,
2115 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2116 : }
2117 :
2118 : template<typename _ForwardIterator, typename _Tp,
2119 : typename _CompareItTp, typename _CompareTpIt>
2120 : pair<_ForwardIterator, _ForwardIterator>
2121 : __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2122 : const _Tp& __val,
2123 : _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2124 : {
2125 : typedef typename iterator_traits<_ForwardIterator>::difference_type
2126 : _DistanceType;
2127 :
2128 : _DistanceType __len = std::distance(__first, __last);
2129 :
2130 : while (__len > 0)
2131 : {
2132 : _DistanceType __half = __len >> 1;
2133 : _ForwardIterator __middle = __first;
2134 : std::advance(__middle, __half);
2135 : if (__comp_it_val(__middle, __val))
2136 : {
2137 : __first = __middle;
2138 : ++__first;
2139 : __len = __len - __half - 1;
2140 : }
2141 : else if (__comp_val_it(__val, __middle))
2142 : __len = __half;
2143 : else
2144 : {
2145 : _ForwardIterator __left
2146 : = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2147 : std::advance(__first, __len);
2148 : _ForwardIterator __right
2149 : = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2150 : return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2151 : }
2152 : }
2153 : return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2154 : }
2155 :
2156 : /**
2157 : * @brief Finds the largest subrange in which @p __val could be inserted
2158 : * at any place in it without changing the ordering.
2159 : * @ingroup binary_search_algorithms
2160 : * @param __first An iterator.
2161 : * @param __last Another iterator.
2162 : * @param __val The search term.
2163 : * @return An pair of iterators defining the subrange.
2164 : * @ingroup binary_search_algorithms
2165 : *
2166 : * This is equivalent to
2167 : * @code
2168 : * std::make_pair(lower_bound(__first, __last, __val),
2169 : * upper_bound(__first, __last, __val))
2170 : * @endcode
2171 : * but does not actually call those functions.
2172 : */
2173 : template<typename _ForwardIterator, typename _Tp>
2174 : inline pair<_ForwardIterator, _ForwardIterator>
2175 : equal_range(_ForwardIterator __first, _ForwardIterator __last,
2176 : const _Tp& __val)
2177 : {
2178 : // concept requirements
2179 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2180 : __glibcxx_function_requires(_LessThanOpConcept<
2181 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2182 : __glibcxx_function_requires(_LessThanOpConcept<
2183 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2184 : __glibcxx_requires_partitioned_lower(__first, __last, __val);
2185 : __glibcxx_requires_partitioned_upper(__first, __last, __val);
2186 :
2187 : return std::__equal_range(__first, __last, __val,
2188 : __gnu_cxx::__ops::__iter_less_val(),
2189 : __gnu_cxx::__ops::__val_less_iter());
2190 : }
2191 :
2192 : /**
2193 : * @brief Finds the largest subrange in which @p __val could be inserted
2194 : * at any place in it without changing the ordering.
2195 : * @param __first An iterator.
2196 : * @param __last Another iterator.
2197 : * @param __val The search term.
2198 : * @param __comp A functor to use for comparisons.
2199 : * @return An pair of iterators defining the subrange.
2200 : * @ingroup binary_search_algorithms
2201 : *
2202 : * This is equivalent to
2203 : * @code
2204 : * std::make_pair(lower_bound(__first, __last, __val, __comp),
2205 : * upper_bound(__first, __last, __val, __comp))
2206 : * @endcode
2207 : * but does not actually call those functions.
2208 : */
2209 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2210 : inline pair<_ForwardIterator, _ForwardIterator>
2211 : equal_range(_ForwardIterator __first, _ForwardIterator __last,
2212 : const _Tp& __val, _Compare __comp)
2213 : {
2214 : // concept requirements
2215 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2216 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2217 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2218 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2219 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2220 : __glibcxx_requires_partitioned_lower_pred(__first, __last,
2221 : __val, __comp);
2222 : __glibcxx_requires_partitioned_upper_pred(__first, __last,
2223 : __val, __comp);
2224 :
2225 : return std::__equal_range(__first, __last, __val,
2226 : __gnu_cxx::__ops::__iter_comp_val(__comp),
2227 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2228 : }
2229 :
2230 : /**
2231 : * @brief Determines whether an element exists in a range.
2232 : * @ingroup binary_search_algorithms
2233 : * @param __first An iterator.
2234 : * @param __last Another iterator.
2235 : * @param __val The search term.
2236 : * @return True if @p __val (or its equivalent) is in [@p
2237 : * __first,@p __last ].
2238 : *
2239 : * Note that this does not actually return an iterator to @p __val. For
2240 : * that, use std::find or a container's specialized find member functions.
2241 : */
2242 : template<typename _ForwardIterator, typename _Tp>
2243 : bool
2244 : binary_search(_ForwardIterator __first, _ForwardIterator __last,
2245 : const _Tp& __val)
2246 : {
2247 : // concept requirements
2248 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2249 : __glibcxx_function_requires(_LessThanOpConcept<
2250 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2251 : __glibcxx_requires_partitioned_lower(__first, __last, __val);
2252 : __glibcxx_requires_partitioned_upper(__first, __last, __val);
2253 :
2254 : _ForwardIterator __i
2255 : = std::__lower_bound(__first, __last, __val,
2256 : __gnu_cxx::__ops::__iter_less_val());
2257 : return __i != __last && !(__val < *__i);
2258 : }
2259 :
2260 : /**
2261 : * @brief Determines whether an element exists in a range.
2262 : * @ingroup binary_search_algorithms
2263 : * @param __first An iterator.
2264 : * @param __last Another iterator.
2265 : * @param __val The search term.
2266 : * @param __comp A functor to use for comparisons.
2267 : * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2268 : *
2269 : * Note that this does not actually return an iterator to @p __val. For
2270 : * that, use std::find or a container's specialized find member functions.
2271 : *
2272 : * The comparison function should have the same effects on ordering as
2273 : * the function used for the initial sort.
2274 : */
2275 : template<typename _ForwardIterator, typename _Tp, typename _Compare>
2276 : bool
2277 : binary_search(_ForwardIterator __first, _ForwardIterator __last,
2278 : const _Tp& __val, _Compare __comp)
2279 : {
2280 : // concept requirements
2281 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2282 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2283 : _Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2284 : __glibcxx_requires_partitioned_lower_pred(__first, __last,
2285 : __val, __comp);
2286 : __glibcxx_requires_partitioned_upper_pred(__first, __last,
2287 : __val, __comp);
2288 :
2289 : _ForwardIterator __i
2290 : = std::__lower_bound(__first, __last, __val,
2291 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2292 : return __i != __last && !bool(__comp(__val, *__i));
2293 : }
2294 :
2295 : // merge
2296 :
2297 : /// This is a helper function for the __merge_adaptive routines.
2298 : template<typename _InputIterator1, typename _InputIterator2,
2299 : typename _OutputIterator, typename _Compare>
2300 : void
2301 : __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2302 : _InputIterator2 __first2, _InputIterator2 __last2,
2303 : _OutputIterator __result, _Compare __comp)
2304 : {
2305 : while (__first1 != __last1 && __first2 != __last2)
2306 : {
2307 : if (__comp(__first2, __first1))
2308 : {
2309 : *__result = _GLIBCXX_MOVE(*__first2);
2310 : ++__first2;
2311 : }
2312 : else
2313 : {
2314 : *__result = _GLIBCXX_MOVE(*__first1);
2315 : ++__first1;
2316 : }
2317 : ++__result;
2318 : }
2319 : if (__first1 != __last1)
2320 : _GLIBCXX_MOVE3(__first1, __last1, __result);
2321 : }
2322 :
2323 : /// This is a helper function for the __merge_adaptive routines.
2324 : template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2325 : typename _BidirectionalIterator3, typename _Compare>
2326 : void
2327 : __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2328 : _BidirectionalIterator1 __last1,
2329 : _BidirectionalIterator2 __first2,
2330 : _BidirectionalIterator2 __last2,
2331 : _BidirectionalIterator3 __result,
2332 : _Compare __comp)
2333 : {
2334 : if (__first1 == __last1)
2335 : {
2336 : _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2337 : return;
2338 : }
2339 : else if (__first2 == __last2)
2340 : return;
2341 :
2342 : --__last1;
2343 : --__last2;
2344 : while (true)
2345 : {
2346 : if (__comp(__last2, __last1))
2347 : {
2348 : *--__result = _GLIBCXX_MOVE(*__last1);
2349 : if (__first1 == __last1)
2350 : {
2351 : _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2352 : return;
2353 : }
2354 : --__last1;
2355 : }
2356 : else
2357 : {
2358 : *--__result = _GLIBCXX_MOVE(*__last2);
2359 : if (__first2 == __last2)
2360 : return;
2361 : --__last2;
2362 : }
2363 : }
2364 : }
2365 :
2366 : /// This is a helper function for the merge routines.
2367 : template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2368 : typename _Distance>
2369 : _BidirectionalIterator1
2370 : __rotate_adaptive(_BidirectionalIterator1 __first,
2371 : _BidirectionalIterator1 __middle,
2372 : _BidirectionalIterator1 __last,
2373 : _Distance __len1, _Distance __len2,
2374 : _BidirectionalIterator2 __buffer,
2375 : _Distance __buffer_size)
2376 : {
2377 : _BidirectionalIterator2 __buffer_end;
2378 : if (__len1 > __len2 && __len2 <= __buffer_size)
2379 : {
2380 : if (__len2)
2381 : {
2382 : __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2383 : _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2384 : return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2385 : }
2386 : else
2387 : return __first;
2388 : }
2389 : else if (__len1 <= __buffer_size)
2390 : {
2391 : if (__len1)
2392 : {
2393 : __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2394 : _GLIBCXX_MOVE3(__middle, __last, __first);
2395 : return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2396 : }
2397 : else
2398 : return __last;
2399 : }
2400 : else
2401 : {
2402 : std::rotate(__first, __middle, __last);
2403 : std::advance(__first, std::distance(__middle, __last));
2404 : return __first;
2405 : }
2406 : }
2407 :
2408 : /// This is a helper function for the merge routines.
2409 : template<typename _BidirectionalIterator, typename _Distance,
2410 : typename _Pointer, typename _Compare>
2411 : void
2412 : __merge_adaptive(_BidirectionalIterator __first,
2413 : _BidirectionalIterator __middle,
2414 : _BidirectionalIterator __last,
2415 : _Distance __len1, _Distance __len2,
2416 : _Pointer __buffer, _Distance __buffer_size,
2417 : _Compare __comp)
2418 : {
2419 : if (__len1 <= __len2 && __len1 <= __buffer_size)
2420 : {
2421 : _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2422 : std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2423 : __first, __comp);
2424 : }
2425 : else if (__len2 <= __buffer_size)
2426 : {
2427 : _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2428 : std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2429 : __buffer_end, __last, __comp);
2430 : }
2431 : else
2432 : {
2433 : _BidirectionalIterator __first_cut = __first;
2434 : _BidirectionalIterator __second_cut = __middle;
2435 : _Distance __len11 = 0;
2436 : _Distance __len22 = 0;
2437 : if (__len1 > __len2)
2438 : {
2439 : __len11 = __len1 / 2;
2440 : std::advance(__first_cut, __len11);
2441 : __second_cut
2442 : = std::__lower_bound(__middle, __last, *__first_cut,
2443 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2444 : __len22 = std::distance(__middle, __second_cut);
2445 : }
2446 : else
2447 : {
2448 : __len22 = __len2 / 2;
2449 : std::advance(__second_cut, __len22);
2450 : __first_cut
2451 : = std::__upper_bound(__first, __middle, *__second_cut,
2452 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2453 : __len11 = std::distance(__first, __first_cut);
2454 : }
2455 :
2456 : _BidirectionalIterator __new_middle
2457 : = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2458 : __len1 - __len11, __len22, __buffer,
2459 : __buffer_size);
2460 : std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
2461 : __len22, __buffer, __buffer_size, __comp);
2462 : std::__merge_adaptive(__new_middle, __second_cut, __last,
2463 : __len1 - __len11,
2464 : __len2 - __len22, __buffer,
2465 : __buffer_size, __comp);
2466 : }
2467 : }
2468 :
2469 : /// This is a helper function for the merge routines.
2470 : template<typename _BidirectionalIterator, typename _Distance,
2471 : typename _Compare>
2472 : void
2473 : __merge_without_buffer(_BidirectionalIterator __first,
2474 : _BidirectionalIterator __middle,
2475 : _BidirectionalIterator __last,
2476 : _Distance __len1, _Distance __len2,
2477 : _Compare __comp)
2478 : {
2479 : if (__len1 == 0 || __len2 == 0)
2480 : return;
2481 :
2482 : if (__len1 + __len2 == 2)
2483 : {
2484 : if (__comp(__middle, __first))
2485 : std::iter_swap(__first, __middle);
2486 : return;
2487 : }
2488 :
2489 : _BidirectionalIterator __first_cut = __first;
2490 : _BidirectionalIterator __second_cut = __middle;
2491 : _Distance __len11 = 0;
2492 : _Distance __len22 = 0;
2493 : if (__len1 > __len2)
2494 : {
2495 : __len11 = __len1 / 2;
2496 : std::advance(__first_cut, __len11);
2497 : __second_cut
2498 : = std::__lower_bound(__middle, __last, *__first_cut,
2499 : __gnu_cxx::__ops::__iter_comp_val(__comp));
2500 : __len22 = std::distance(__middle, __second_cut);
2501 : }
2502 : else
2503 : {
2504 : __len22 = __len2 / 2;
2505 : std::advance(__second_cut, __len22);
2506 : __first_cut
2507 : = std::__upper_bound(__first, __middle, *__second_cut,
2508 : __gnu_cxx::__ops::__val_comp_iter(__comp));
2509 : __len11 = std::distance(__first, __first_cut);
2510 : }
2511 :
2512 : std::rotate(__first_cut, __middle, __second_cut);
2513 : _BidirectionalIterator __new_middle = __first_cut;
2514 : std::advance(__new_middle, std::distance(__middle, __second_cut));
2515 : std::__merge_without_buffer(__first, __first_cut, __new_middle,
2516 : __len11, __len22, __comp);
2517 : std::__merge_without_buffer(__new_middle, __second_cut, __last,
2518 : __len1 - __len11, __len2 - __len22, __comp);
2519 : }
2520 :
2521 : template<typename _BidirectionalIterator, typename _Compare>
2522 : void
2523 : __inplace_merge(_BidirectionalIterator __first,
2524 : _BidirectionalIterator __middle,
2525 : _BidirectionalIterator __last,
2526 : _Compare __comp)
2527 : {
2528 : typedef typename iterator_traits<_BidirectionalIterator>::value_type
2529 : _ValueType;
2530 : typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2531 : _DistanceType;
2532 :
2533 : if (__first == __middle || __middle == __last)
2534 : return;
2535 :
2536 : const _DistanceType __len1 = std::distance(__first, __middle);
2537 : const _DistanceType __len2 = std::distance(__middle, __last);
2538 :
2539 : typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2540 : _TmpBuf __buf(__first, __last);
2541 :
2542 : if (__buf.begin() == 0)
2543 : std::__merge_without_buffer
2544 : (__first, __middle, __last, __len1, __len2, __comp);
2545 : else
2546 : std::__merge_adaptive
2547 : (__first, __middle, __last, __len1, __len2, __buf.begin(),
2548 : _DistanceType(__buf.size()), __comp);
2549 : }
2550 :
2551 : /**
2552 : * @brief Merges two sorted ranges in place.
2553 : * @ingroup sorting_algorithms
2554 : * @param __first An iterator.
2555 : * @param __middle Another iterator.
2556 : * @param __last Another iterator.
2557 : * @return Nothing.
2558 : *
2559 : * Merges two sorted and consecutive ranges, [__first,__middle) and
2560 : * [__middle,__last), and puts the result in [__first,__last). The
2561 : * output will be sorted. The sort is @e stable, that is, for
2562 : * equivalent elements in the two ranges, elements from the first
2563 : * range will always come before elements from the second.
2564 : *
2565 : * If enough additional memory is available, this takes (__last-__first)-1
2566 : * comparisons. Otherwise an NlogN algorithm is used, where N is
2567 : * distance(__first,__last).
2568 : */
2569 : template<typename _BidirectionalIterator>
2570 : inline void
2571 : inplace_merge(_BidirectionalIterator __first,
2572 : _BidirectionalIterator __middle,
2573 : _BidirectionalIterator __last)
2574 : {
2575 : // concept requirements
2576 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2577 : _BidirectionalIterator>)
2578 : __glibcxx_function_requires(_LessThanComparableConcept<
2579 : typename iterator_traits<_BidirectionalIterator>::value_type>)
2580 : __glibcxx_requires_sorted(__first, __middle);
2581 : __glibcxx_requires_sorted(__middle, __last);
2582 : __glibcxx_requires_irreflexive(__first, __last);
2583 :
2584 : std::__inplace_merge(__first, __middle, __last,
2585 : __gnu_cxx::__ops::__iter_less_iter());
2586 : }
2587 :
2588 : /**
2589 : * @brief Merges two sorted ranges in place.
2590 : * @ingroup sorting_algorithms
2591 : * @param __first An iterator.
2592 : * @param __middle Another iterator.
2593 : * @param __last Another iterator.
2594 : * @param __comp A functor to use for comparisons.
2595 : * @return Nothing.
2596 : *
2597 : * Merges two sorted and consecutive ranges, [__first,__middle) and
2598 : * [middle,last), and puts the result in [__first,__last). The output will
2599 : * be sorted. The sort is @e stable, that is, for equivalent
2600 : * elements in the two ranges, elements from the first range will always
2601 : * come before elements from the second.
2602 : *
2603 : * If enough additional memory is available, this takes (__last-__first)-1
2604 : * comparisons. Otherwise an NlogN algorithm is used, where N is
2605 : * distance(__first,__last).
2606 : *
2607 : * The comparison function should have the same effects on ordering as
2608 : * the function used for the initial sort.
2609 : */
2610 : template<typename _BidirectionalIterator, typename _Compare>
2611 : inline void
2612 : inplace_merge(_BidirectionalIterator __first,
2613 : _BidirectionalIterator __middle,
2614 : _BidirectionalIterator __last,
2615 : _Compare __comp)
2616 : {
2617 : // concept requirements
2618 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2619 : _BidirectionalIterator>)
2620 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2621 : typename iterator_traits<_BidirectionalIterator>::value_type,
2622 : typename iterator_traits<_BidirectionalIterator>::value_type>)
2623 : __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2624 : __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2625 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2626 :
2627 : std::__inplace_merge(__first, __middle, __last,
2628 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
2629 : }
2630 :
2631 :
2632 : /// This is a helper function for the __merge_sort_loop routines.
2633 : template<typename _InputIterator, typename _OutputIterator,
2634 : typename _Compare>
2635 : _OutputIterator
2636 : __move_merge(_InputIterator __first1, _InputIterator __last1,
2637 : _InputIterator __first2, _InputIterator __last2,
2638 : _OutputIterator __result, _Compare __comp)
2639 : {
2640 : while (__first1 != __last1 && __first2 != __last2)
2641 : {
2642 : if (__comp(__first2, __first1))
2643 : {
2644 : *__result = _GLIBCXX_MOVE(*__first2);
2645 : ++__first2;
2646 : }
2647 : else
2648 : {
2649 : *__result = _GLIBCXX_MOVE(*__first1);
2650 : ++__first1;
2651 : }
2652 : ++__result;
2653 : }
2654 : return _GLIBCXX_MOVE3(__first2, __last2,
2655 : _GLIBCXX_MOVE3(__first1, __last1,
2656 : __result));
2657 : }
2658 :
2659 : template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2660 : typename _Distance, typename _Compare>
2661 : void
2662 : __merge_sort_loop(_RandomAccessIterator1 __first,
2663 : _RandomAccessIterator1 __last,
2664 : _RandomAccessIterator2 __result, _Distance __step_size,
2665 : _Compare __comp)
2666 : {
2667 : const _Distance __two_step = 2 * __step_size;
2668 :
2669 : while (__last - __first >= __two_step)
2670 : {
2671 : __result = std::__move_merge(__first, __first + __step_size,
2672 : __first + __step_size,
2673 : __first + __two_step,
2674 : __result, __comp);
2675 : __first += __two_step;
2676 : }
2677 : __step_size = std::min(_Distance(__last - __first), __step_size);
2678 :
2679 : std::__move_merge(__first, __first + __step_size,
2680 : __first + __step_size, __last, __result, __comp);
2681 : }
2682 :
2683 : template<typename _RandomAccessIterator, typename _Distance,
2684 : typename _Compare>
2685 : void
2686 : __chunk_insertion_sort(_RandomAccessIterator __first,
2687 : _RandomAccessIterator __last,
2688 : _Distance __chunk_size, _Compare __comp)
2689 : {
2690 : while (__last - __first >= __chunk_size)
2691 : {
2692 : std::__insertion_sort(__first, __first + __chunk_size, __comp);
2693 : __first += __chunk_size;
2694 : }
2695 : std::__insertion_sort(__first, __last, __comp);
2696 : }
2697 :
2698 : enum { _S_chunk_size = 7 };
2699 :
2700 : template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2701 : void
2702 : __merge_sort_with_buffer(_RandomAccessIterator __first,
2703 : _RandomAccessIterator __last,
2704 : _Pointer __buffer, _Compare __comp)
2705 : {
2706 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2707 : _Distance;
2708 :
2709 : const _Distance __len = __last - __first;
2710 : const _Pointer __buffer_last = __buffer + __len;
2711 :
2712 : _Distance __step_size = _S_chunk_size;
2713 : std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2714 :
2715 : while (__step_size < __len)
2716 : {
2717 : std::__merge_sort_loop(__first, __last, __buffer,
2718 : __step_size, __comp);
2719 : __step_size *= 2;
2720 : std::__merge_sort_loop(__buffer, __buffer_last, __first,
2721 : __step_size, __comp);
2722 : __step_size *= 2;
2723 : }
2724 : }
2725 :
2726 : template<typename _RandomAccessIterator, typename _Pointer,
2727 : typename _Distance, typename _Compare>
2728 : void
2729 : __stable_sort_adaptive(_RandomAccessIterator __first,
2730 : _RandomAccessIterator __last,
2731 : _Pointer __buffer, _Distance __buffer_size,
2732 : _Compare __comp)
2733 : {
2734 : const _Distance __len = (__last - __first + 1) / 2;
2735 : const _RandomAccessIterator __middle = __first + __len;
2736 : if (__len > __buffer_size)
2737 : {
2738 : std::__stable_sort_adaptive(__first, __middle, __buffer,
2739 : __buffer_size, __comp);
2740 : std::__stable_sort_adaptive(__middle, __last, __buffer,
2741 : __buffer_size, __comp);
2742 : }
2743 : else
2744 : {
2745 : std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2746 : std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2747 : }
2748 : std::__merge_adaptive(__first, __middle, __last,
2749 : _Distance(__middle - __first),
2750 : _Distance(__last - __middle),
2751 : __buffer, __buffer_size,
2752 : __comp);
2753 : }
2754 :
2755 : /// This is a helper function for the stable sorting routines.
2756 : template<typename _RandomAccessIterator, typename _Compare>
2757 : void
2758 : __inplace_stable_sort(_RandomAccessIterator __first,
2759 : _RandomAccessIterator __last, _Compare __comp)
2760 : {
2761 : if (__last - __first < 15)
2762 : {
2763 : std::__insertion_sort(__first, __last, __comp);
2764 : return;
2765 : }
2766 : _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2767 : std::__inplace_stable_sort(__first, __middle, __comp);
2768 : std::__inplace_stable_sort(__middle, __last, __comp);
2769 : std::__merge_without_buffer(__first, __middle, __last,
2770 : __middle - __first,
2771 : __last - __middle,
2772 : __comp);
2773 : }
2774 :
2775 : // stable_sort
2776 :
2777 : // Set algorithms: includes, set_union, set_intersection, set_difference,
2778 : // set_symmetric_difference. All of these algorithms have the precondition
2779 : // that their input ranges are sorted and the postcondition that their output
2780 : // ranges are sorted.
2781 :
2782 : template<typename _InputIterator1, typename _InputIterator2,
2783 : typename _Compare>
2784 : bool
2785 : __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2786 : _InputIterator2 __first2, _InputIterator2 __last2,
2787 : _Compare __comp)
2788 : {
2789 : while (__first1 != __last1 && __first2 != __last2)
2790 : if (__comp(__first2, __first1))
2791 : return false;
2792 : else if (__comp(__first1, __first2))
2793 : ++__first1;
2794 : else
2795 : {
2796 : ++__first1;
2797 : ++__first2;
2798 : }
2799 :
2800 : return __first2 == __last2;
2801 : }
2802 :
2803 : /**
2804 : * @brief Determines whether all elements of a sequence exists in a range.
2805 : * @param __first1 Start of search range.
2806 : * @param __last1 End of search range.
2807 : * @param __first2 Start of sequence
2808 : * @param __last2 End of sequence.
2809 : * @return True if each element in [__first2,__last2) is contained in order
2810 : * within [__first1,__last1). False otherwise.
2811 : * @ingroup set_algorithms
2812 : *
2813 : * This operation expects both [__first1,__last1) and
2814 : * [__first2,__last2) to be sorted. Searches for the presence of
2815 : * each element in [__first2,__last2) within [__first1,__last1).
2816 : * The iterators over each range only move forward, so this is a
2817 : * linear algorithm. If an element in [__first2,__last2) is not
2818 : * found before the search iterator reaches @p __last2, false is
2819 : * returned.
2820 : */
2821 : template<typename _InputIterator1, typename _InputIterator2>
2822 : inline bool
2823 : includes(_InputIterator1 __first1, _InputIterator1 __last1,
2824 : _InputIterator2 __first2, _InputIterator2 __last2)
2825 : {
2826 : // concept requirements
2827 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2828 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2829 : __glibcxx_function_requires(_LessThanOpConcept<
2830 : typename iterator_traits<_InputIterator1>::value_type,
2831 : typename iterator_traits<_InputIterator2>::value_type>)
2832 : __glibcxx_function_requires(_LessThanOpConcept<
2833 : typename iterator_traits<_InputIterator2>::value_type,
2834 : typename iterator_traits<_InputIterator1>::value_type>)
2835 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2836 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2837 : __glibcxx_requires_irreflexive2(__first1, __last1);
2838 : __glibcxx_requires_irreflexive2(__first2, __last2);
2839 :
2840 : return std::__includes(__first1, __last1, __first2, __last2,
2841 : __gnu_cxx::__ops::__iter_less_iter());
2842 : }
2843 :
2844 : /**
2845 : * @brief Determines whether all elements of a sequence exists in a range
2846 : * using comparison.
2847 : * @ingroup set_algorithms
2848 : * @param __first1 Start of search range.
2849 : * @param __last1 End of search range.
2850 : * @param __first2 Start of sequence
2851 : * @param __last2 End of sequence.
2852 : * @param __comp Comparison function to use.
2853 : * @return True if each element in [__first2,__last2) is contained
2854 : * in order within [__first1,__last1) according to comp. False
2855 : * otherwise. @ingroup set_algorithms
2856 : *
2857 : * This operation expects both [__first1,__last1) and
2858 : * [__first2,__last2) to be sorted. Searches for the presence of
2859 : * each element in [__first2,__last2) within [__first1,__last1),
2860 : * using comp to decide. The iterators over each range only move
2861 : * forward, so this is a linear algorithm. If an element in
2862 : * [__first2,__last2) is not found before the search iterator
2863 : * reaches @p __last2, false is returned.
2864 : */
2865 : template<typename _InputIterator1, typename _InputIterator2,
2866 : typename _Compare>
2867 : inline bool
2868 : includes(_InputIterator1 __first1, _InputIterator1 __last1,
2869 : _InputIterator2 __first2, _InputIterator2 __last2,
2870 : _Compare __comp)
2871 : {
2872 : // concept requirements
2873 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2874 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2875 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 : typename iterator_traits<_InputIterator1>::value_type,
2877 : typename iterator_traits<_InputIterator2>::value_type>)
2878 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 : typename iterator_traits<_InputIterator2>::value_type,
2880 : typename iterator_traits<_InputIterator1>::value_type>)
2881 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2882 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2883 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2884 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2885 :
2886 : return std::__includes(__first1, __last1, __first2, __last2,
2887 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
2888 : }
2889 :
2890 : // nth_element
2891 : // merge
2892 : // set_difference
2893 : // set_intersection
2894 : // set_union
2895 : // stable_sort
2896 : // set_symmetric_difference
2897 : // min_element
2898 : // max_element
2899 :
2900 : template<typename _BidirectionalIterator, typename _Compare>
2901 : bool
2902 : __next_permutation(_BidirectionalIterator __first,
2903 : _BidirectionalIterator __last, _Compare __comp)
2904 : {
2905 : if (__first == __last)
2906 : return false;
2907 : _BidirectionalIterator __i = __first;
2908 : ++__i;
2909 : if (__i == __last)
2910 : return false;
2911 : __i = __last;
2912 : --__i;
2913 :
2914 : for(;;)
2915 : {
2916 : _BidirectionalIterator __ii = __i;
2917 : --__i;
2918 : if (__comp(__i, __ii))
2919 : {
2920 : _BidirectionalIterator __j = __last;
2921 : while (!__comp(__i, --__j))
2922 : {}
2923 : std::iter_swap(__i, __j);
2924 : std::__reverse(__ii, __last,
2925 : std::__iterator_category(__first));
2926 : return true;
2927 : }
2928 : if (__i == __first)
2929 : {
2930 : std::__reverse(__first, __last,
2931 : std::__iterator_category(__first));
2932 : return false;
2933 : }
2934 : }
2935 : }
2936 :
2937 : /**
2938 : * @brief Permute range into the next @e dictionary ordering.
2939 : * @ingroup sorting_algorithms
2940 : * @param __first Start of range.
2941 : * @param __last End of range.
2942 : * @return False if wrapped to first permutation, true otherwise.
2943 : *
2944 : * Treats all permutations of the range as a set of @e dictionary sorted
2945 : * sequences. Permutes the current sequence into the next one of this set.
2946 : * Returns true if there are more sequences to generate. If the sequence
2947 : * is the largest of the set, the smallest is generated and false returned.
2948 : */
2949 : template<typename _BidirectionalIterator>
2950 : inline bool
2951 : next_permutation(_BidirectionalIterator __first,
2952 : _BidirectionalIterator __last)
2953 : {
2954 : // concept requirements
2955 : __glibcxx_function_requires(_BidirectionalIteratorConcept<
2956 : _BidirectionalIterator>)
2957 : __glibcxx_function_requires(_LessThanComparableConcept<
2958 : typename iterator_traits<_BidirectionalIterator>::value_type>)
2959 : __glibcxx_requires_valid_range(__first, __last);
2960 : __glibcxx_requires_irreflexive(__first, __last);
2961 :
2962 : return std::__next_permutation
2963 : (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2964 : }
2965 :
2966 : /**
2967 : * @brief Permute range into the next @e dictionary ordering using
2968 : * comparison functor.
2969 : * @ingroup sorting_algorithms
2970 : * @param __first Start of range.
2971 : * @param __last End of range.
2972 : * @param __comp A comparison functor.
2973 : * @return False if wrapped to first permutation, true otherwise.
2974 : *
2975 : * Treats all permutations of the range [__first,__last) as a set of
2976 : * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
2977 : * sequence into the next one of this set. Returns true if there are more
2978 : * sequences to generate. If the sequence is the largest of the set, the
2979 : * smallest is generated and false returned.
2980 : */
2981 : template<typename _BidirectionalIterator, typename _Compare>
2982 : inline bool
2983 : next_permutation(_BidirectionalIterator __first,
2984 : _BidirectionalIterator __last, _Compare __comp)
2985 : {
2986 : // concept requirements
2987 : __glibcxx_function_requires(_BidirectionalIteratorConcept<
2988 : _BidirectionalIterator>)
2989 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2990 : typename iterator_traits<_BidirectionalIterator>::value_type,
2991 : typename iterator_traits<_BidirectionalIterator>::value_type>)
2992 : __glibcxx_requires_valid_range(__first, __last);
2993 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2994 :
2995 : return std::__next_permutation
2996 : (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2997 : }
2998 :
2999 : template<typename _BidirectionalIterator, typename _Compare>
3000 : bool
3001 : __prev_permutation(_BidirectionalIterator __first,
3002 : _BidirectionalIterator __last, _Compare __comp)
3003 : {
3004 : if (__first == __last)
3005 : return false;
3006 : _BidirectionalIterator __i = __first;
3007 : ++__i;
3008 : if (__i == __last)
3009 : return false;
3010 : __i = __last;
3011 : --__i;
3012 :
3013 : for(;;)
3014 : {
3015 : _BidirectionalIterator __ii = __i;
3016 : --__i;
3017 : if (__comp(__ii, __i))
3018 : {
3019 : _BidirectionalIterator __j = __last;
3020 : while (!__comp(--__j, __i))
3021 : {}
3022 : std::iter_swap(__i, __j);
3023 : std::__reverse(__ii, __last,
3024 : std::__iterator_category(__first));
3025 : return true;
3026 : }
3027 : if (__i == __first)
3028 : {
3029 : std::__reverse(__first, __last,
3030 : std::__iterator_category(__first));
3031 : return false;
3032 : }
3033 : }
3034 : }
3035 :
3036 : /**
3037 : * @brief Permute range into the previous @e dictionary ordering.
3038 : * @ingroup sorting_algorithms
3039 : * @param __first Start of range.
3040 : * @param __last End of range.
3041 : * @return False if wrapped to last permutation, true otherwise.
3042 : *
3043 : * Treats all permutations of the range as a set of @e dictionary sorted
3044 : * sequences. Permutes the current sequence into the previous one of this
3045 : * set. Returns true if there are more sequences to generate. If the
3046 : * sequence is the smallest of the set, the largest is generated and false
3047 : * returned.
3048 : */
3049 : template<typename _BidirectionalIterator>
3050 : inline bool
3051 : prev_permutation(_BidirectionalIterator __first,
3052 : _BidirectionalIterator __last)
3053 : {
3054 : // concept requirements
3055 : __glibcxx_function_requires(_BidirectionalIteratorConcept<
3056 : _BidirectionalIterator>)
3057 : __glibcxx_function_requires(_LessThanComparableConcept<
3058 : typename iterator_traits<_BidirectionalIterator>::value_type>)
3059 : __glibcxx_requires_valid_range(__first, __last);
3060 : __glibcxx_requires_irreflexive(__first, __last);
3061 :
3062 : return std::__prev_permutation(__first, __last,
3063 : __gnu_cxx::__ops::__iter_less_iter());
3064 : }
3065 :
3066 : /**
3067 : * @brief Permute range into the previous @e dictionary ordering using
3068 : * comparison functor.
3069 : * @ingroup sorting_algorithms
3070 : * @param __first Start of range.
3071 : * @param __last End of range.
3072 : * @param __comp A comparison functor.
3073 : * @return False if wrapped to last permutation, true otherwise.
3074 : *
3075 : * Treats all permutations of the range [__first,__last) as a set of
3076 : * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3077 : * sequence into the previous one of this set. Returns true if there are
3078 : * more sequences to generate. If the sequence is the smallest of the set,
3079 : * the largest is generated and false returned.
3080 : */
3081 : template<typename _BidirectionalIterator, typename _Compare>
3082 : inline bool
3083 : prev_permutation(_BidirectionalIterator __first,
3084 : _BidirectionalIterator __last, _Compare __comp)
3085 : {
3086 : // concept requirements
3087 : __glibcxx_function_requires(_BidirectionalIteratorConcept<
3088 : _BidirectionalIterator>)
3089 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3090 : typename iterator_traits<_BidirectionalIterator>::value_type,
3091 : typename iterator_traits<_BidirectionalIterator>::value_type>)
3092 : __glibcxx_requires_valid_range(__first, __last);
3093 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3094 :
3095 : return std::__prev_permutation(__first, __last,
3096 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
3097 : }
3098 :
3099 : // replace
3100 : // replace_if
3101 :
3102 : template<typename _InputIterator, typename _OutputIterator,
3103 : typename _Predicate, typename _Tp>
3104 : _OutputIterator
3105 : __replace_copy_if(_InputIterator __first, _InputIterator __last,
3106 : _OutputIterator __result,
3107 : _Predicate __pred, const _Tp& __new_value)
3108 : {
3109 : for (; __first != __last; ++__first, (void)++__result)
3110 : if (__pred(__first))
3111 : *__result = __new_value;
3112 : else
3113 : *__result = *__first;
3114 : return __result;
3115 : }
3116 :
3117 : /**
3118 : * @brief Copy a sequence, replacing each element of one value with another
3119 : * value.
3120 : * @param __first An input iterator.
3121 : * @param __last An input iterator.
3122 : * @param __result An output iterator.
3123 : * @param __old_value The value to be replaced.
3124 : * @param __new_value The replacement value.
3125 : * @return The end of the output sequence, @p result+(last-first).
3126 : *
3127 : * Copies each element in the input range @p [__first,__last) to the
3128 : * output range @p [__result,__result+(__last-__first)) replacing elements
3129 : * equal to @p __old_value with @p __new_value.
3130 : */
3131 : template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3132 : inline _OutputIterator
3133 : replace_copy(_InputIterator __first, _InputIterator __last,
3134 : _OutputIterator __result,
3135 : const _Tp& __old_value, const _Tp& __new_value)
3136 : {
3137 : // concept requirements
3138 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3139 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3140 : typename iterator_traits<_InputIterator>::value_type>)
3141 : __glibcxx_function_requires(_EqualOpConcept<
3142 : typename iterator_traits<_InputIterator>::value_type, _Tp>)
3143 : __glibcxx_requires_valid_range(__first, __last);
3144 :
3145 : return std::__replace_copy_if(__first, __last, __result,
3146 : __gnu_cxx::__ops::__iter_equals_val(__old_value),
3147 : __new_value);
3148 : }
3149 :
3150 : /**
3151 : * @brief Copy a sequence, replacing each value for which a predicate
3152 : * returns true with another value.
3153 : * @ingroup mutating_algorithms
3154 : * @param __first An input iterator.
3155 : * @param __last An input iterator.
3156 : * @param __result An output iterator.
3157 : * @param __pred A predicate.
3158 : * @param __new_value The replacement value.
3159 : * @return The end of the output sequence, @p __result+(__last-__first).
3160 : *
3161 : * Copies each element in the range @p [__first,__last) to the range
3162 : * @p [__result,__result+(__last-__first)) replacing elements for which
3163 : * @p __pred returns true with @p __new_value.
3164 : */
3165 : template<typename _InputIterator, typename _OutputIterator,
3166 : typename _Predicate, typename _Tp>
3167 : inline _OutputIterator
3168 : replace_copy_if(_InputIterator __first, _InputIterator __last,
3169 : _OutputIterator __result,
3170 : _Predicate __pred, const _Tp& __new_value)
3171 : {
3172 : // concept requirements
3173 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3174 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3175 : typename iterator_traits<_InputIterator>::value_type>)
3176 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3177 : typename iterator_traits<_InputIterator>::value_type>)
3178 : __glibcxx_requires_valid_range(__first, __last);
3179 :
3180 : return std::__replace_copy_if(__first, __last, __result,
3181 : __gnu_cxx::__ops::__pred_iter(__pred),
3182 : __new_value);
3183 : }
3184 :
3185 : template<typename _InputIterator, typename _Predicate>
3186 : typename iterator_traits<_InputIterator>::difference_type
3187 : __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3188 : {
3189 : typename iterator_traits<_InputIterator>::difference_type __n = 0;
3190 : for (; __first != __last; ++__first)
3191 : if (__pred(__first))
3192 : ++__n;
3193 : return __n;
3194 : }
3195 :
3196 : #if __cplusplus >= 201103L
3197 : /**
3198 : * @brief Determines whether the elements of a sequence are sorted.
3199 : * @ingroup sorting_algorithms
3200 : * @param __first An iterator.
3201 : * @param __last Another iterator.
3202 : * @return True if the elements are sorted, false otherwise.
3203 : */
3204 : template<typename _ForwardIterator>
3205 : inline bool
3206 : is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3207 : { return std::is_sorted_until(__first, __last) == __last; }
3208 :
3209 : /**
3210 : * @brief Determines whether the elements of a sequence are sorted
3211 : * according to a comparison functor.
3212 : * @ingroup sorting_algorithms
3213 : * @param __first An iterator.
3214 : * @param __last Another iterator.
3215 : * @param __comp A comparison functor.
3216 : * @return True if the elements are sorted, false otherwise.
3217 : */
3218 : template<typename _ForwardIterator, typename _Compare>
3219 : inline bool
3220 : is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3221 : _Compare __comp)
3222 : { return std::is_sorted_until(__first, __last, __comp) == __last; }
3223 :
3224 : template<typename _ForwardIterator, typename _Compare>
3225 : _ForwardIterator
3226 : __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3227 : _Compare __comp)
3228 : {
3229 : if (__first == __last)
3230 : return __last;
3231 :
3232 : _ForwardIterator __next = __first;
3233 : for (++__next; __next != __last; __first = __next, (void)++__next)
3234 : if (__comp(__next, __first))
3235 : return __next;
3236 : return __next;
3237 : }
3238 :
3239 : /**
3240 : * @brief Determines the end of a sorted sequence.
3241 : * @ingroup sorting_algorithms
3242 : * @param __first An iterator.
3243 : * @param __last Another iterator.
3244 : * @return An iterator pointing to the last iterator i in [__first, __last)
3245 : * for which the range [__first, i) is sorted.
3246 : */
3247 : template<typename _ForwardIterator>
3248 : inline _ForwardIterator
3249 : is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3250 : {
3251 : // concept requirements
3252 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3253 : __glibcxx_function_requires(_LessThanComparableConcept<
3254 : typename iterator_traits<_ForwardIterator>::value_type>)
3255 : __glibcxx_requires_valid_range(__first, __last);
3256 : __glibcxx_requires_irreflexive(__first, __last);
3257 :
3258 : return std::__is_sorted_until(__first, __last,
3259 : __gnu_cxx::__ops::__iter_less_iter());
3260 : }
3261 :
3262 : /**
3263 : * @brief Determines the end of a sorted sequence using comparison functor.
3264 : * @ingroup sorting_algorithms
3265 : * @param __first An iterator.
3266 : * @param __last Another iterator.
3267 : * @param __comp A comparison functor.
3268 : * @return An iterator pointing to the last iterator i in [__first, __last)
3269 : * for which the range [__first, i) is sorted.
3270 : */
3271 : template<typename _ForwardIterator, typename _Compare>
3272 : inline _ForwardIterator
3273 : is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3274 : _Compare __comp)
3275 : {
3276 : // concept requirements
3277 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3278 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3279 : typename iterator_traits<_ForwardIterator>::value_type,
3280 : typename iterator_traits<_ForwardIterator>::value_type>)
3281 : __glibcxx_requires_valid_range(__first, __last);
3282 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
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 : _GLIBCXX14_CONSTEXPR
3298 : inline pair<const _Tp&, const _Tp&>
3299 : minmax(const _Tp& __a, const _Tp& __b)
3300 : {
3301 : // concept requirements
3302 : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3303 :
3304 : return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3305 : : pair<const _Tp&, const _Tp&>(__a, __b);
3306 : }
3307 :
3308 : /**
3309 : * @brief Determines min and max at once as an ordered pair.
3310 : * @ingroup sorting_algorithms
3311 : * @param __a A thing of arbitrary type.
3312 : * @param __b Another thing of arbitrary type.
3313 : * @param __comp A @link comparison_functors comparison functor @endlink.
3314 : * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3315 : * __b) otherwise.
3316 : */
3317 : template<typename _Tp, typename _Compare>
3318 : _GLIBCXX14_CONSTEXPR
3319 : inline pair<const _Tp&, const _Tp&>
3320 : minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3321 : {
3322 : return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3323 : : pair<const _Tp&, const _Tp&>(__a, __b);
3324 : }
3325 :
3326 : template<typename _ForwardIterator, typename _Compare>
3327 : _GLIBCXX14_CONSTEXPR
3328 : pair<_ForwardIterator, _ForwardIterator>
3329 : __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3330 : _Compare __comp)
3331 : {
3332 : _ForwardIterator __next = __first;
3333 : if (__first == __last
3334 : || ++__next == __last)
3335 : return std::make_pair(__first, __first);
3336 :
3337 : _ForwardIterator __min{}, __max{};
3338 : if (__comp(__next, __first))
3339 : {
3340 : __min = __next;
3341 : __max = __first;
3342 : }
3343 : else
3344 : {
3345 : __min = __first;
3346 : __max = __next;
3347 : }
3348 :
3349 : __first = __next;
3350 : ++__first;
3351 :
3352 : while (__first != __last)
3353 : {
3354 : __next = __first;
3355 : if (++__next == __last)
3356 : {
3357 : if (__comp(__first, __min))
3358 : __min = __first;
3359 : else if (!__comp(__first, __max))
3360 : __max = __first;
3361 : break;
3362 : }
3363 :
3364 : if (__comp(__next, __first))
3365 : {
3366 : if (__comp(__next, __min))
3367 : __min = __next;
3368 : if (!__comp(__first, __max))
3369 : __max = __first;
3370 : }
3371 : else
3372 : {
3373 : if (__comp(__first, __min))
3374 : __min = __first;
3375 : if (!__comp(__next, __max))
3376 : __max = __next;
3377 : }
3378 :
3379 : __first = __next;
3380 : ++__first;
3381 : }
3382 :
3383 : return std::make_pair(__min, __max);
3384 : }
3385 :
3386 : /**
3387 : * @brief Return a pair of iterators pointing to the minimum and maximum
3388 : * elements in a range.
3389 : * @ingroup sorting_algorithms
3390 : * @param __first Start of range.
3391 : * @param __last End of range.
3392 : * @return make_pair(m, M), where m is the first iterator i in
3393 : * [__first, __last) such that no other element in the range is
3394 : * smaller, and where M is the last iterator i in [__first, __last)
3395 : * such that no other element in the range is larger.
3396 : */
3397 : template<typename _ForwardIterator>
3398 : _GLIBCXX14_CONSTEXPR
3399 : inline pair<_ForwardIterator, _ForwardIterator>
3400 : minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3401 : {
3402 : // concept requirements
3403 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3404 : __glibcxx_function_requires(_LessThanComparableConcept<
3405 : typename iterator_traits<_ForwardIterator>::value_type>)
3406 : __glibcxx_requires_valid_range(__first, __last);
3407 : __glibcxx_requires_irreflexive(__first, __last);
3408 :
3409 : return std::__minmax_element(__first, __last,
3410 : __gnu_cxx::__ops::__iter_less_iter());
3411 : }
3412 :
3413 : /**
3414 : * @brief Return a pair of iterators pointing to the minimum and maximum
3415 : * elements in a range.
3416 : * @ingroup sorting_algorithms
3417 : * @param __first Start of range.
3418 : * @param __last End of range.
3419 : * @param __comp Comparison functor.
3420 : * @return make_pair(m, M), where m is the first iterator i in
3421 : * [__first, __last) such that no other element in the range is
3422 : * smaller, and where M is the last iterator i in [__first, __last)
3423 : * such that no other element in the range is larger.
3424 : */
3425 : template<typename _ForwardIterator, typename _Compare>
3426 : _GLIBCXX14_CONSTEXPR
3427 : inline pair<_ForwardIterator, _ForwardIterator>
3428 : minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3429 : _Compare __comp)
3430 : {
3431 : // concept requirements
3432 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3433 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3434 : typename iterator_traits<_ForwardIterator>::value_type,
3435 : typename iterator_traits<_ForwardIterator>::value_type>)
3436 : __glibcxx_requires_valid_range(__first, __last);
3437 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3438 :
3439 : return std::__minmax_element(__first, __last,
3440 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
3441 : }
3442 :
3443 : // N2722 + DR 915.
3444 : template<typename _Tp>
3445 : _GLIBCXX14_CONSTEXPR
3446 : inline _Tp
3447 : min(initializer_list<_Tp> __l)
3448 : { return *std::min_element(__l.begin(), __l.end()); }
3449 :
3450 : template<typename _Tp, typename _Compare>
3451 : _GLIBCXX14_CONSTEXPR
3452 : inline _Tp
3453 : min(initializer_list<_Tp> __l, _Compare __comp)
3454 : { return *std::min_element(__l.begin(), __l.end(), __comp); }
3455 :
3456 : template<typename _Tp>
3457 : _GLIBCXX14_CONSTEXPR
3458 : inline _Tp
3459 : max(initializer_list<_Tp> __l)
3460 : { return *std::max_element(__l.begin(), __l.end()); }
3461 :
3462 : template<typename _Tp, typename _Compare>
3463 : _GLIBCXX14_CONSTEXPR
3464 : inline _Tp
3465 : max(initializer_list<_Tp> __l, _Compare __comp)
3466 : { return *std::max_element(__l.begin(), __l.end(), __comp); }
3467 :
3468 : template<typename _Tp>
3469 : _GLIBCXX14_CONSTEXPR
3470 : inline pair<_Tp, _Tp>
3471 : minmax(initializer_list<_Tp> __l)
3472 : {
3473 : pair<const _Tp*, const _Tp*> __p =
3474 : std::minmax_element(__l.begin(), __l.end());
3475 : return std::make_pair(*__p.first, *__p.second);
3476 : }
3477 :
3478 : template<typename _Tp, typename _Compare>
3479 : _GLIBCXX14_CONSTEXPR
3480 : inline pair<_Tp, _Tp>
3481 : minmax(initializer_list<_Tp> __l, _Compare __comp)
3482 : {
3483 : pair<const _Tp*, const _Tp*> __p =
3484 : std::minmax_element(__l.begin(), __l.end(), __comp);
3485 : return std::make_pair(*__p.first, *__p.second);
3486 : }
3487 :
3488 : template<typename _ForwardIterator1, typename _ForwardIterator2,
3489 : typename _BinaryPredicate>
3490 : bool
3491 : __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3492 : _ForwardIterator2 __first2, _BinaryPredicate __pred)
3493 : {
3494 : // Efficiently compare identical prefixes: O(N) if sequences
3495 : // have the same elements in the same order.
3496 : for (; __first1 != __last1; ++__first1, (void)++__first2)
3497 : if (!__pred(__first1, __first2))
3498 : break;
3499 :
3500 : if (__first1 == __last1)
3501 : return true;
3502 :
3503 : // Establish __last2 assuming equal ranges by iterating over the
3504 : // rest of the list.
3505 : _ForwardIterator2 __last2 = __first2;
3506 : std::advance(__last2, std::distance(__first1, __last1));
3507 : for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3508 : {
3509 : if (__scan != std::__find_if(__first1, __scan,
3510 : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3511 : continue; // We've seen this one before.
3512 :
3513 : auto __matches
3514 : = std::__count_if(__first2, __last2,
3515 : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3516 : if (0 == __matches ||
3517 : std::__count_if(__scan, __last1,
3518 : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3519 : != __matches)
3520 : return false;
3521 : }
3522 : return true;
3523 : }
3524 :
3525 : /**
3526 : * @brief Checks whether a permutation of the second sequence is equal
3527 : * to the first sequence.
3528 : * @ingroup non_mutating_algorithms
3529 : * @param __first1 Start of first range.
3530 : * @param __last1 End of first range.
3531 : * @param __first2 Start of second range.
3532 : * @return true if there exists a permutation of the elements in the range
3533 : * [__first2, __first2 + (__last1 - __first1)), beginning with
3534 : * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
3535 : * returns true; otherwise, returns false.
3536 : */
3537 : template<typename _ForwardIterator1, typename _ForwardIterator2>
3538 : inline bool
3539 : is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3540 : _ForwardIterator2 __first2)
3541 : {
3542 : // concept requirements
3543 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3544 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3545 : __glibcxx_function_requires(_EqualOpConcept<
3546 : typename iterator_traits<_ForwardIterator1>::value_type,
3547 : typename iterator_traits<_ForwardIterator2>::value_type>)
3548 : __glibcxx_requires_valid_range(__first1, __last1);
3549 :
3550 : return std::__is_permutation(__first1, __last1, __first2,
3551 : __gnu_cxx::__ops::__iter_equal_to_iter());
3552 : }
3553 :
3554 : /**
3555 : * @brief Checks whether a permutation of the second sequence is equal
3556 : * to the first sequence.
3557 : * @ingroup non_mutating_algorithms
3558 : * @param __first1 Start of first range.
3559 : * @param __last1 End of first range.
3560 : * @param __first2 Start of second range.
3561 : * @param __pred A binary predicate.
3562 : * @return true if there exists a permutation of the elements in
3563 : * the range [__first2, __first2 + (__last1 - __first1)),
3564 : * beginning with ForwardIterator2 begin, such that
3565 : * equal(__first1, __last1, __begin, __pred) returns true;
3566 : * otherwise, returns false.
3567 : */
3568 : template<typename _ForwardIterator1, typename _ForwardIterator2,
3569 : typename _BinaryPredicate>
3570 : inline bool
3571 : is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3572 : _ForwardIterator2 __first2, _BinaryPredicate __pred)
3573 : {
3574 : // concept requirements
3575 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3576 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3577 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3578 : typename iterator_traits<_ForwardIterator1>::value_type,
3579 : typename iterator_traits<_ForwardIterator2>::value_type>)
3580 : __glibcxx_requires_valid_range(__first1, __last1);
3581 :
3582 : return std::__is_permutation(__first1, __last1, __first2,
3583 : __gnu_cxx::__ops::__iter_comp_iter(__pred));
3584 : }
3585 :
3586 : #if __cplusplus > 201103L
3587 : template<typename _ForwardIterator1, typename _ForwardIterator2,
3588 : typename _BinaryPredicate>
3589 : bool
3590 : __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3591 : _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3592 : _BinaryPredicate __pred)
3593 : {
3594 : using _Cat1
3595 : = typename iterator_traits<_ForwardIterator1>::iterator_category;
3596 : using _Cat2
3597 : = typename iterator_traits<_ForwardIterator2>::iterator_category;
3598 : using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3599 : using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3600 : constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3601 : if (__ra_iters)
3602 : {
3603 : auto __d1 = std::distance(__first1, __last1);
3604 : auto __d2 = std::distance(__first2, __last2);
3605 : if (__d1 != __d2)
3606 : return false;
3607 : }
3608 :
3609 : // Efficiently compare identical prefixes: O(N) if sequences
3610 : // have the same elements in the same order.
3611 : for (; __first1 != __last1 && __first2 != __last2;
3612 : ++__first1, (void)++__first2)
3613 : if (!__pred(__first1, __first2))
3614 : break;
3615 :
3616 : if (__ra_iters)
3617 : {
3618 : if (__first1 == __last1)
3619 : return true;
3620 : }
3621 : else
3622 : {
3623 : auto __d1 = std::distance(__first1, __last1);
3624 : auto __d2 = std::distance(__first2, __last2);
3625 : if (__d1 == 0 && __d2 == 0)
3626 : return true;
3627 : if (__d1 != __d2)
3628 : return false;
3629 : }
3630 :
3631 : for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3632 : {
3633 : if (__scan != std::__find_if(__first1, __scan,
3634 : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3635 : continue; // We've seen this one before.
3636 :
3637 : auto __matches = std::__count_if(__first2, __last2,
3638 : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3639 : if (0 == __matches
3640 : || std::__count_if(__scan, __last1,
3641 : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3642 : != __matches)
3643 : return false;
3644 : }
3645 : return true;
3646 : }
3647 :
3648 : /**
3649 : * @brief Checks whether a permutaion of the second sequence is equal
3650 : * to the first sequence.
3651 : * @ingroup non_mutating_algorithms
3652 : * @param __first1 Start of first range.
3653 : * @param __last1 End of first range.
3654 : * @param __first2 Start of second range.
3655 : * @param __last2 End of first range.
3656 : * @return true if there exists a permutation of the elements in the range
3657 : * [__first2, __last2), beginning with ForwardIterator2 begin,
3658 : * such that equal(__first1, __last1, begin) returns true;
3659 : * otherwise, returns false.
3660 : */
3661 : template<typename _ForwardIterator1, typename _ForwardIterator2>
3662 : inline bool
3663 : is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3664 : _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3665 : {
3666 : __glibcxx_requires_valid_range(__first1, __last1);
3667 : __glibcxx_requires_valid_range(__first2, __last2);
3668 :
3669 : return
3670 : std::__is_permutation(__first1, __last1, __first2, __last2,
3671 : __gnu_cxx::__ops::__iter_equal_to_iter());
3672 : }
3673 :
3674 : /**
3675 : * @brief Checks whether a permutation of the second sequence is equal
3676 : * to the first sequence.
3677 : * @ingroup non_mutating_algorithms
3678 : * @param __first1 Start of first range.
3679 : * @param __last1 End of first range.
3680 : * @param __first2 Start of second range.
3681 : * @param __last2 End of first range.
3682 : * @param __pred A binary predicate.
3683 : * @return true if there exists a permutation of the elements in the range
3684 : * [__first2, __last2), beginning with ForwardIterator2 begin,
3685 : * such that equal(__first1, __last1, __begin, __pred) returns true;
3686 : * otherwise, returns false.
3687 : */
3688 : template<typename _ForwardIterator1, typename _ForwardIterator2,
3689 : typename _BinaryPredicate>
3690 : inline bool
3691 : is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3692 : _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3693 : _BinaryPredicate __pred)
3694 : {
3695 : __glibcxx_requires_valid_range(__first1, __last1);
3696 : __glibcxx_requires_valid_range(__first2, __last2);
3697 :
3698 : return std::__is_permutation(__first1, __last1, __first2, __last2,
3699 : __gnu_cxx::__ops::__iter_comp_iter(__pred));
3700 : }
3701 : #endif
3702 :
3703 : #ifdef _GLIBCXX_USE_C99_STDINT_TR1
3704 : /**
3705 : * @brief Shuffle the elements of a sequence using a uniform random
3706 : * number generator.
3707 : * @ingroup mutating_algorithms
3708 : * @param __first A forward iterator.
3709 : * @param __last A forward iterator.
3710 : * @param __g A UniformRandomNumberGenerator (26.5.1.3).
3711 : * @return Nothing.
3712 : *
3713 : * Reorders the elements in the range @p [__first,__last) using @p __g to
3714 : * provide random numbers.
3715 : */
3716 : template<typename _RandomAccessIterator,
3717 : typename _UniformRandomNumberGenerator>
3718 : void
3719 : shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3720 : _UniformRandomNumberGenerator&& __g)
3721 : {
3722 : // concept requirements
3723 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3724 : _RandomAccessIterator>)
3725 : __glibcxx_requires_valid_range(__first, __last);
3726 :
3727 : if (__first == __last)
3728 : return;
3729 :
3730 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3731 : _DistanceType;
3732 :
3733 : typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3734 : typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3735 : typedef typename __distr_type::param_type __p_type;
3736 : __distr_type __d;
3737 :
3738 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3739 : std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3740 : }
3741 : #endif
3742 :
3743 : #endif // C++11
3744 :
3745 : _GLIBCXX_END_NAMESPACE_VERSION
3746 :
3747 : _GLIBCXX_BEGIN_NAMESPACE_ALGO
3748 :
3749 : /**
3750 : * @brief Apply a function to every element of a sequence.
3751 : * @ingroup non_mutating_algorithms
3752 : * @param __first An input iterator.
3753 : * @param __last An input iterator.
3754 : * @param __f A unary function object.
3755 : * @return @p __f (std::move(@p __f) in C++0x).
3756 : *
3757 : * Applies the function object @p __f to each element in the range
3758 : * @p [first,last). @p __f must not modify the order of the sequence.
3759 : * If @p __f has a return value it is ignored.
3760 : */
3761 : template<typename _InputIterator, typename _Function>
3762 : _Function
3763 0 : for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3764 : {
3765 : // concept requirements
3766 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3767 : __glibcxx_requires_valid_range(__first, __last);
3768 0 : for (; __first != __last; ++__first)
3769 0 : __f(*__first);
3770 0 : return _GLIBCXX_MOVE(__f);
3771 : }
3772 :
3773 : /**
3774 : * @brief Find the first occurrence of a value in a sequence.
3775 : * @ingroup non_mutating_algorithms
3776 : * @param __first An input iterator.
3777 : * @param __last An input iterator.
3778 : * @param __val The value to find.
3779 : * @return The first iterator @c i in the range @p [__first,__last)
3780 : * such that @c *i == @p __val, or @p __last if no such iterator exists.
3781 : */
3782 : template<typename _InputIterator, typename _Tp>
3783 : inline _InputIterator
3784 : find(_InputIterator __first, _InputIterator __last,
3785 : const _Tp& __val)
3786 : {
3787 : // concept requirements
3788 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3789 : __glibcxx_function_requires(_EqualOpConcept<
3790 : typename iterator_traits<_InputIterator>::value_type, _Tp>)
3791 : __glibcxx_requires_valid_range(__first, __last);
3792 : return std::__find_if(__first, __last,
3793 : __gnu_cxx::__ops::__iter_equals_val(__val));
3794 : }
3795 :
3796 : /**
3797 : * @brief Find the first element in a sequence for which a
3798 : * predicate is true.
3799 : * @ingroup non_mutating_algorithms
3800 : * @param __first An input iterator.
3801 : * @param __last An input iterator.
3802 : * @param __pred A predicate.
3803 : * @return The first iterator @c i in the range @p [__first,__last)
3804 : * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3805 : */
3806 : template<typename _InputIterator, typename _Predicate>
3807 : inline _InputIterator
3808 : find_if(_InputIterator __first, _InputIterator __last,
3809 : _Predicate __pred)
3810 : {
3811 : // concept requirements
3812 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3813 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3814 : typename iterator_traits<_InputIterator>::value_type>)
3815 : __glibcxx_requires_valid_range(__first, __last);
3816 :
3817 : return std::__find_if(__first, __last,
3818 : __gnu_cxx::__ops::__pred_iter(__pred));
3819 : }
3820 :
3821 : /**
3822 : * @brief Find element from a set in a sequence.
3823 : * @ingroup non_mutating_algorithms
3824 : * @param __first1 Start of range to search.
3825 : * @param __last1 End of range to search.
3826 : * @param __first2 Start of match candidates.
3827 : * @param __last2 End of match candidates.
3828 : * @return The first iterator @c i in the range
3829 : * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
3830 : * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3831 : *
3832 : * Searches the range @p [__first1,__last1) for an element that is
3833 : * equal to some element in the range [__first2,__last2). If
3834 : * found, returns an iterator in the range [__first1,__last1),
3835 : * otherwise returns @p __last1.
3836 : */
3837 : template<typename _InputIterator, typename _ForwardIterator>
3838 : _InputIterator
3839 : find_first_of(_InputIterator __first1, _InputIterator __last1,
3840 : _ForwardIterator __first2, _ForwardIterator __last2)
3841 : {
3842 : // concept requirements
3843 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3844 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3845 : __glibcxx_function_requires(_EqualOpConcept<
3846 : typename iterator_traits<_InputIterator>::value_type,
3847 : typename iterator_traits<_ForwardIterator>::value_type>)
3848 : __glibcxx_requires_valid_range(__first1, __last1);
3849 : __glibcxx_requires_valid_range(__first2, __last2);
3850 :
3851 : for (; __first1 != __last1; ++__first1)
3852 : for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3853 : if (*__first1 == *__iter)
3854 : return __first1;
3855 : return __last1;
3856 : }
3857 :
3858 : /**
3859 : * @brief Find element from a set in a sequence using a predicate.
3860 : * @ingroup non_mutating_algorithms
3861 : * @param __first1 Start of range to search.
3862 : * @param __last1 End of range to search.
3863 : * @param __first2 Start of match candidates.
3864 : * @param __last2 End of match candidates.
3865 : * @param __comp Predicate to use.
3866 : * @return The first iterator @c i in the range
3867 : * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
3868 : * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3869 : * such iterator exists.
3870 : *
3871 :
3872 : * Searches the range @p [__first1,__last1) for an element that is
3873 : * equal to some element in the range [__first2,__last2). If
3874 : * found, returns an iterator in the range [__first1,__last1),
3875 : * otherwise returns @p __last1.
3876 : */
3877 : template<typename _InputIterator, typename _ForwardIterator,
3878 : typename _BinaryPredicate>
3879 : _InputIterator
3880 : find_first_of(_InputIterator __first1, _InputIterator __last1,
3881 : _ForwardIterator __first2, _ForwardIterator __last2,
3882 : _BinaryPredicate __comp)
3883 : {
3884 : // concept requirements
3885 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3886 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3887 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3888 : typename iterator_traits<_InputIterator>::value_type,
3889 : typename iterator_traits<_ForwardIterator>::value_type>)
3890 : __glibcxx_requires_valid_range(__first1, __last1);
3891 : __glibcxx_requires_valid_range(__first2, __last2);
3892 :
3893 : for (; __first1 != __last1; ++__first1)
3894 : for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3895 : if (__comp(*__first1, *__iter))
3896 : return __first1;
3897 : return __last1;
3898 : }
3899 :
3900 : /**
3901 : * @brief Find two adjacent values in a sequence that are equal.
3902 : * @ingroup non_mutating_algorithms
3903 : * @param __first A forward iterator.
3904 : * @param __last A forward iterator.
3905 : * @return The first iterator @c i such that @c i and @c i+1 are both
3906 : * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
3907 : * or @p __last if no such iterator exists.
3908 : */
3909 : template<typename _ForwardIterator>
3910 : inline _ForwardIterator
3911 : adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3912 : {
3913 : // concept requirements
3914 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3915 : __glibcxx_function_requires(_EqualityComparableConcept<
3916 : typename iterator_traits<_ForwardIterator>::value_type>)
3917 : __glibcxx_requires_valid_range(__first, __last);
3918 :
3919 : return std::__adjacent_find(__first, __last,
3920 : __gnu_cxx::__ops::__iter_equal_to_iter());
3921 : }
3922 :
3923 : /**
3924 : * @brief Find two adjacent values in a sequence using a predicate.
3925 : * @ingroup non_mutating_algorithms
3926 : * @param __first A forward iterator.
3927 : * @param __last A forward iterator.
3928 : * @param __binary_pred A binary predicate.
3929 : * @return The first iterator @c i such that @c i and @c i+1 are both
3930 : * valid iterators in @p [__first,__last) and such that
3931 : * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
3932 : * exists.
3933 : */
3934 : template<typename _ForwardIterator, typename _BinaryPredicate>
3935 : inline _ForwardIterator
3936 0 : adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3937 : _BinaryPredicate __binary_pred)
3938 : {
3939 : // concept requirements
3940 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3941 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3942 : typename iterator_traits<_ForwardIterator>::value_type,
3943 : typename iterator_traits<_ForwardIterator>::value_type>)
3944 : __glibcxx_requires_valid_range(__first, __last);
3945 :
3946 0 : return std::__adjacent_find(__first, __last,
3947 0 : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
3948 : }
3949 :
3950 : /**
3951 : * @brief Count the number of copies of a value in a sequence.
3952 : * @ingroup non_mutating_algorithms
3953 : * @param __first An input iterator.
3954 : * @param __last An input iterator.
3955 : * @param __value The value to be counted.
3956 : * @return The number of iterators @c i in the range @p [__first,__last)
3957 : * for which @c *i == @p __value
3958 : */
3959 : template<typename _InputIterator, typename _Tp>
3960 : inline typename iterator_traits<_InputIterator>::difference_type
3961 : count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
3962 : {
3963 : // concept requirements
3964 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3965 : __glibcxx_function_requires(_EqualOpConcept<
3966 : typename iterator_traits<_InputIterator>::value_type, _Tp>)
3967 : __glibcxx_requires_valid_range(__first, __last);
3968 :
3969 : return std::__count_if(__first, __last,
3970 : __gnu_cxx::__ops::__iter_equals_val(__value));
3971 : }
3972 :
3973 : /**
3974 : * @brief Count the elements of a sequence for which a predicate is true.
3975 : * @ingroup non_mutating_algorithms
3976 : * @param __first An input iterator.
3977 : * @param __last An input iterator.
3978 : * @param __pred A predicate.
3979 : * @return The number of iterators @c i in the range @p [__first,__last)
3980 : * for which @p __pred(*i) is true.
3981 : */
3982 : template<typename _InputIterator, typename _Predicate>
3983 : inline typename iterator_traits<_InputIterator>::difference_type
3984 : count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3985 : {
3986 : // concept requirements
3987 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3988 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3989 : typename iterator_traits<_InputIterator>::value_type>)
3990 : __glibcxx_requires_valid_range(__first, __last);
3991 :
3992 : return std::__count_if(__first, __last,
3993 : __gnu_cxx::__ops::__pred_iter(__pred));
3994 : }
3995 :
3996 : /**
3997 : * @brief Search a sequence for a matching sub-sequence.
3998 : * @ingroup non_mutating_algorithms
3999 : * @param __first1 A forward iterator.
4000 : * @param __last1 A forward iterator.
4001 : * @param __first2 A forward iterator.
4002 : * @param __last2 A forward iterator.
4003 : * @return The first iterator @c i in the range @p
4004 : * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4005 : * *(__first2+N) for each @c N in the range @p
4006 : * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4007 : *
4008 : * Searches the range @p [__first1,__last1) for a sub-sequence that
4009 : * compares equal value-by-value with the sequence given by @p
4010 : * [__first2,__last2) and returns an iterator to the first element
4011 : * of the sub-sequence, or @p __last1 if the sub-sequence is not
4012 : * found.
4013 : *
4014 : * Because the sub-sequence must lie completely within the range @p
4015 : * [__first1,__last1) it must start at a position less than @p
4016 : * __last1-(__last2-__first2) where @p __last2-__first2 is the
4017 : * length of the sub-sequence.
4018 : *
4019 : * This means that the returned iterator @c i will be in the range
4020 : * @p [__first1,__last1-(__last2-__first2))
4021 : */
4022 : template<typename _ForwardIterator1, typename _ForwardIterator2>
4023 : inline _ForwardIterator1
4024 : search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4025 : _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4026 : {
4027 : // concept requirements
4028 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4029 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4030 : __glibcxx_function_requires(_EqualOpConcept<
4031 : typename iterator_traits<_ForwardIterator1>::value_type,
4032 : typename iterator_traits<_ForwardIterator2>::value_type>)
4033 : __glibcxx_requires_valid_range(__first1, __last1);
4034 : __glibcxx_requires_valid_range(__first2, __last2);
4035 :
4036 : return std::__search(__first1, __last1, __first2, __last2,
4037 : __gnu_cxx::__ops::__iter_equal_to_iter());
4038 : }
4039 :
4040 : /**
4041 : * @brief Search a sequence for a matching sub-sequence using a predicate.
4042 : * @ingroup non_mutating_algorithms
4043 : * @param __first1 A forward iterator.
4044 : * @param __last1 A forward iterator.
4045 : * @param __first2 A forward iterator.
4046 : * @param __last2 A forward iterator.
4047 : * @param __predicate A binary predicate.
4048 : * @return The first iterator @c i in the range
4049 : * @p [__first1,__last1-(__last2-__first2)) such that
4050 : * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4051 : * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4052 : *
4053 : * Searches the range @p [__first1,__last1) for a sub-sequence that
4054 : * compares equal value-by-value with the sequence given by @p
4055 : * [__first2,__last2), using @p __predicate to determine equality,
4056 : * and returns an iterator to the first element of the
4057 : * sub-sequence, or @p __last1 if no such iterator exists.
4058 : *
4059 : * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4060 : */
4061 : template<typename _ForwardIterator1, typename _ForwardIterator2,
4062 : typename _BinaryPredicate>
4063 : inline _ForwardIterator1
4064 : search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4065 : _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4066 : _BinaryPredicate __predicate)
4067 : {
4068 : // concept requirements
4069 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4070 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4071 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4072 : typename iterator_traits<_ForwardIterator1>::value_type,
4073 : typename iterator_traits<_ForwardIterator2>::value_type>)
4074 : __glibcxx_requires_valid_range(__first1, __last1);
4075 : __glibcxx_requires_valid_range(__first2, __last2);
4076 :
4077 : return std::__search(__first1, __last1, __first2, __last2,
4078 : __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4079 : }
4080 :
4081 : /**
4082 : * @brief Search a sequence for a number of consecutive values.
4083 : * @ingroup non_mutating_algorithms
4084 : * @param __first A forward iterator.
4085 : * @param __last A forward iterator.
4086 : * @param __count The number of consecutive values.
4087 : * @param __val The value to find.
4088 : * @return The first iterator @c i in the range @p
4089 : * [__first,__last-__count) such that @c *(i+N) == @p __val for
4090 : * each @c N in the range @p [0,__count), or @p __last if no such
4091 : * iterator exists.
4092 : *
4093 : * Searches the range @p [__first,__last) for @p count consecutive elements
4094 : * equal to @p __val.
4095 : */
4096 : template<typename _ForwardIterator, typename _Integer, typename _Tp>
4097 : inline _ForwardIterator
4098 : search_n(_ForwardIterator __first, _ForwardIterator __last,
4099 : _Integer __count, const _Tp& __val)
4100 : {
4101 : // concept requirements
4102 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4103 : __glibcxx_function_requires(_EqualOpConcept<
4104 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4105 : __glibcxx_requires_valid_range(__first, __last);
4106 :
4107 : return std::__search_n(__first, __last, __count,
4108 : __gnu_cxx::__ops::__iter_equals_val(__val));
4109 : }
4110 :
4111 :
4112 : /**
4113 : * @brief Search a sequence for a number of consecutive values using a
4114 : * predicate.
4115 : * @ingroup non_mutating_algorithms
4116 : * @param __first A forward iterator.
4117 : * @param __last A forward iterator.
4118 : * @param __count The number of consecutive values.
4119 : * @param __val The value to find.
4120 : * @param __binary_pred A binary predicate.
4121 : * @return The first iterator @c i in the range @p
4122 : * [__first,__last-__count) such that @p
4123 : * __binary_pred(*(i+N),__val) is true for each @c N in the range
4124 : * @p [0,__count), or @p __last if no such iterator exists.
4125 : *
4126 : * Searches the range @p [__first,__last) for @p __count
4127 : * consecutive elements for which the predicate returns true.
4128 : */
4129 : template<typename _ForwardIterator, typename _Integer, typename _Tp,
4130 : typename _BinaryPredicate>
4131 : inline _ForwardIterator
4132 : search_n(_ForwardIterator __first, _ForwardIterator __last,
4133 : _Integer __count, const _Tp& __val,
4134 : _BinaryPredicate __binary_pred)
4135 : {
4136 : // concept requirements
4137 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4138 : __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4139 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4140 : __glibcxx_requires_valid_range(__first, __last);
4141 :
4142 : return std::__search_n(__first, __last, __count,
4143 : __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4144 : }
4145 :
4146 :
4147 : /**
4148 : * @brief Perform an operation on a sequence.
4149 : * @ingroup mutating_algorithms
4150 : * @param __first An input iterator.
4151 : * @param __last An input iterator.
4152 : * @param __result An output iterator.
4153 : * @param __unary_op A unary operator.
4154 : * @return An output iterator equal to @p __result+(__last-__first).
4155 : *
4156 : * Applies the operator to each element in the input range and assigns
4157 : * the results to successive elements of the output sequence.
4158 : * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4159 : * range @p [0,__last-__first).
4160 : *
4161 : * @p unary_op must not alter its argument.
4162 : */
4163 : template<typename _InputIterator, typename _OutputIterator,
4164 : typename _UnaryOperation>
4165 : _OutputIterator
4166 0 : transform(_InputIterator __first, _InputIterator __last,
4167 : _OutputIterator __result, _UnaryOperation __unary_op)
4168 : {
4169 : // concept requirements
4170 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4171 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4172 : // "the type returned by a _UnaryOperation"
4173 : __typeof__(__unary_op(*__first))>)
4174 : __glibcxx_requires_valid_range(__first, __last);
4175 :
4176 0 : for (; __first != __last; ++__first, (void)++__result)
4177 0 : *__result = __unary_op(*__first);
4178 0 : return __result;
4179 : }
4180 :
4181 : /**
4182 : * @brief Perform an operation on corresponding elements of two sequences.
4183 : * @ingroup mutating_algorithms
4184 : * @param __first1 An input iterator.
4185 : * @param __last1 An input iterator.
4186 : * @param __first2 An input iterator.
4187 : * @param __result An output iterator.
4188 : * @param __binary_op A binary operator.
4189 : * @return An output iterator equal to @p result+(last-first).
4190 : *
4191 : * Applies the operator to the corresponding elements in the two
4192 : * input ranges and assigns the results to successive elements of the
4193 : * output sequence.
4194 : * Evaluates @p
4195 : * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4196 : * @c N in the range @p [0,__last1-__first1).
4197 : *
4198 : * @p binary_op must not alter either of its arguments.
4199 : */
4200 : template<typename _InputIterator1, typename _InputIterator2,
4201 : typename _OutputIterator, typename _BinaryOperation>
4202 : _OutputIterator
4203 : transform(_InputIterator1 __first1, _InputIterator1 __last1,
4204 : _InputIterator2 __first2, _OutputIterator __result,
4205 : _BinaryOperation __binary_op)
4206 : {
4207 : // concept requirements
4208 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4209 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4210 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4211 : // "the type returned by a _BinaryOperation"
4212 : __typeof__(__binary_op(*__first1,*__first2))>)
4213 : __glibcxx_requires_valid_range(__first1, __last1);
4214 :
4215 : for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4216 : *__result = __binary_op(*__first1, *__first2);
4217 : return __result;
4218 : }
4219 :
4220 : /**
4221 : * @brief Replace each occurrence of one value in a sequence with another
4222 : * value.
4223 : * @ingroup mutating_algorithms
4224 : * @param __first A forward iterator.
4225 : * @param __last A forward iterator.
4226 : * @param __old_value The value to be replaced.
4227 : * @param __new_value The replacement value.
4228 : * @return replace() returns no value.
4229 : *
4230 : * For each iterator @c i in the range @p [__first,__last) if @c *i ==
4231 : * @p __old_value then the assignment @c *i = @p __new_value is performed.
4232 : */
4233 : template<typename _ForwardIterator, typename _Tp>
4234 : void
4235 : replace(_ForwardIterator __first, _ForwardIterator __last,
4236 : const _Tp& __old_value, const _Tp& __new_value)
4237 : {
4238 : // concept requirements
4239 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4240 : _ForwardIterator>)
4241 : __glibcxx_function_requires(_EqualOpConcept<
4242 : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4243 : __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4244 : typename iterator_traits<_ForwardIterator>::value_type>)
4245 : __glibcxx_requires_valid_range(__first, __last);
4246 :
4247 : for (; __first != __last; ++__first)
4248 : if (*__first == __old_value)
4249 : *__first = __new_value;
4250 : }
4251 :
4252 : /**
4253 : * @brief Replace each value in a sequence for which a predicate returns
4254 : * true with another value.
4255 : * @ingroup mutating_algorithms
4256 : * @param __first A forward iterator.
4257 : * @param __last A forward iterator.
4258 : * @param __pred A predicate.
4259 : * @param __new_value The replacement value.
4260 : * @return replace_if() returns no value.
4261 : *
4262 : * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
4263 : * is true then the assignment @c *i = @p __new_value is performed.
4264 : */
4265 : template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4266 : void
4267 : replace_if(_ForwardIterator __first, _ForwardIterator __last,
4268 : _Predicate __pred, const _Tp& __new_value)
4269 : {
4270 : // concept requirements
4271 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4272 : _ForwardIterator>)
4273 : __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4274 : typename iterator_traits<_ForwardIterator>::value_type>)
4275 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4276 : typename iterator_traits<_ForwardIterator>::value_type>)
4277 : __glibcxx_requires_valid_range(__first, __last);
4278 :
4279 : for (; __first != __last; ++__first)
4280 : if (__pred(*__first))
4281 : *__first = __new_value;
4282 : }
4283 :
4284 : /**
4285 : * @brief Assign the result of a function object to each value in a
4286 : * sequence.
4287 : * @ingroup mutating_algorithms
4288 : * @param __first A forward iterator.
4289 : * @param __last A forward iterator.
4290 : * @param __gen A function object taking no arguments and returning
4291 : * std::iterator_traits<_ForwardIterator>::value_type
4292 : * @return generate() returns no value.
4293 : *
4294 : * Performs the assignment @c *i = @p __gen() for each @c i in the range
4295 : * @p [__first,__last).
4296 : */
4297 : template<typename _ForwardIterator, typename _Generator>
4298 : void
4299 : generate(_ForwardIterator __first, _ForwardIterator __last,
4300 : _Generator __gen)
4301 : {
4302 : // concept requirements
4303 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4304 : __glibcxx_function_requires(_GeneratorConcept<_Generator,
4305 : typename iterator_traits<_ForwardIterator>::value_type>)
4306 : __glibcxx_requires_valid_range(__first, __last);
4307 :
4308 : for (; __first != __last; ++__first)
4309 : *__first = __gen();
4310 : }
4311 :
4312 : /**
4313 : * @brief Assign the result of a function object to each value in a
4314 : * sequence.
4315 : * @ingroup mutating_algorithms
4316 : * @param __first A forward iterator.
4317 : * @param __n The length of the sequence.
4318 : * @param __gen A function object taking no arguments and returning
4319 : * std::iterator_traits<_ForwardIterator>::value_type
4320 : * @return The end of the sequence, @p __first+__n
4321 : *
4322 : * Performs the assignment @c *i = @p __gen() for each @c i in the range
4323 : * @p [__first,__first+__n).
4324 : *
4325 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4326 : * DR 865. More algorithms that throw away information
4327 : */
4328 : template<typename _OutputIterator, typename _Size, typename _Generator>
4329 : _OutputIterator
4330 : generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4331 : {
4332 : // concept requirements
4333 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4334 : // "the type returned by a _Generator"
4335 : __typeof__(__gen())>)
4336 :
4337 : for (__decltype(__n + 0) __niter = __n;
4338 : __niter > 0; --__niter, ++__first)
4339 : *__first = __gen();
4340 : return __first;
4341 : }
4342 :
4343 : /**
4344 : * @brief Copy a sequence, removing consecutive duplicate values.
4345 : * @ingroup mutating_algorithms
4346 : * @param __first An input iterator.
4347 : * @param __last An input iterator.
4348 : * @param __result An output iterator.
4349 : * @return An iterator designating the end of the resulting sequence.
4350 : *
4351 : * Copies each element in the range @p [__first,__last) to the range
4352 : * beginning at @p __result, except that only the first element is copied
4353 : * from groups of consecutive elements that compare equal.
4354 : * unique_copy() is stable, so the relative order of elements that are
4355 : * copied is unchanged.
4356 : *
4357 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4358 : * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4359 : *
4360 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4361 : * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4362 : * Assignable?
4363 : */
4364 : template<typename _InputIterator, typename _OutputIterator>
4365 : inline _OutputIterator
4366 : unique_copy(_InputIterator __first, _InputIterator __last,
4367 : _OutputIterator __result)
4368 : {
4369 : // concept requirements
4370 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4371 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4372 : typename iterator_traits<_InputIterator>::value_type>)
4373 : __glibcxx_function_requires(_EqualityComparableConcept<
4374 : typename iterator_traits<_InputIterator>::value_type>)
4375 : __glibcxx_requires_valid_range(__first, __last);
4376 :
4377 : if (__first == __last)
4378 : return __result;
4379 : return std::__unique_copy(__first, __last, __result,
4380 : __gnu_cxx::__ops::__iter_equal_to_iter(),
4381 : std::__iterator_category(__first),
4382 : std::__iterator_category(__result));
4383 : }
4384 :
4385 : /**
4386 : * @brief Copy a sequence, removing consecutive values using a predicate.
4387 : * @ingroup mutating_algorithms
4388 : * @param __first An input iterator.
4389 : * @param __last An input iterator.
4390 : * @param __result An output iterator.
4391 : * @param __binary_pred A binary predicate.
4392 : * @return An iterator designating the end of the resulting sequence.
4393 : *
4394 : * Copies each element in the range @p [__first,__last) to the range
4395 : * beginning at @p __result, except that only the first element is copied
4396 : * from groups of consecutive elements for which @p __binary_pred returns
4397 : * true.
4398 : * unique_copy() is stable, so the relative order of elements that are
4399 : * copied is unchanged.
4400 : *
4401 : * _GLIBCXX_RESOLVE_LIB_DEFECTS
4402 : * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4403 : */
4404 : template<typename _InputIterator, typename _OutputIterator,
4405 : typename _BinaryPredicate>
4406 : inline _OutputIterator
4407 : unique_copy(_InputIterator __first, _InputIterator __last,
4408 : _OutputIterator __result,
4409 : _BinaryPredicate __binary_pred)
4410 : {
4411 : // concept requirements -- predicates checked later
4412 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4413 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4414 : typename iterator_traits<_InputIterator>::value_type>)
4415 : __glibcxx_requires_valid_range(__first, __last);
4416 :
4417 : if (__first == __last)
4418 : return __result;
4419 : return std::__unique_copy(__first, __last, __result,
4420 : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4421 : std::__iterator_category(__first),
4422 : std::__iterator_category(__result));
4423 : }
4424 :
4425 : #if _GLIBCXX_HOSTED
4426 : /**
4427 : * @brief Randomly shuffle the elements of a sequence.
4428 : * @ingroup mutating_algorithms
4429 : * @param __first A forward iterator.
4430 : * @param __last A forward iterator.
4431 : * @return Nothing.
4432 : *
4433 : * Reorder the elements in the range @p [__first,__last) using a random
4434 : * distribution, so that every possible ordering of the sequence is
4435 : * equally likely.
4436 : */
4437 : template<typename _RandomAccessIterator>
4438 : inline void
4439 : random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4440 : {
4441 : // concept requirements
4442 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4443 : _RandomAccessIterator>)
4444 : __glibcxx_requires_valid_range(__first, __last);
4445 :
4446 : if (__first != __last)
4447 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4448 : {
4449 : // XXX rand() % N is not uniformly distributed
4450 : _RandomAccessIterator __j = __first
4451 : + std::rand() % ((__i - __first) + 1);
4452 : if (__i != __j)
4453 : std::iter_swap(__i, __j);
4454 : }
4455 : }
4456 : #endif
4457 :
4458 : /**
4459 : * @brief Shuffle the elements of a sequence using a random number
4460 : * generator.
4461 : * @ingroup mutating_algorithms
4462 : * @param __first A forward iterator.
4463 : * @param __last A forward iterator.
4464 : * @param __rand The RNG functor or function.
4465 : * @return Nothing.
4466 : *
4467 : * Reorders the elements in the range @p [__first,__last) using @p __rand to
4468 : * provide a random distribution. Calling @p __rand(N) for a positive
4469 : * integer @p N should return a randomly chosen integer from the
4470 : * range [0,N).
4471 : */
4472 : template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4473 : void
4474 : random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4475 : #if __cplusplus >= 201103L
4476 : _RandomNumberGenerator&& __rand)
4477 : #else
4478 : _RandomNumberGenerator& __rand)
4479 : #endif
4480 : {
4481 : // concept requirements
4482 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4483 : _RandomAccessIterator>)
4484 : __glibcxx_requires_valid_range(__first, __last);
4485 :
4486 : if (__first == __last)
4487 : return;
4488 : for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4489 : {
4490 : _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4491 : if (__i != __j)
4492 : std::iter_swap(__i, __j);
4493 : }
4494 : }
4495 :
4496 :
4497 : /**
4498 : * @brief Move elements for which a predicate is true to the beginning
4499 : * of a sequence.
4500 : * @ingroup mutating_algorithms
4501 : * @param __first A forward iterator.
4502 : * @param __last A forward iterator.
4503 : * @param __pred A predicate functor.
4504 : * @return An iterator @p middle such that @p __pred(i) is true for each
4505 : * iterator @p i in the range @p [__first,middle) and false for each @p i
4506 : * in the range @p [middle,__last).
4507 : *
4508 : * @p __pred must not modify its operand. @p partition() does not preserve
4509 : * the relative ordering of elements in each group, use
4510 : * @p stable_partition() if this is needed.
4511 : */
4512 : template<typename _ForwardIterator, typename _Predicate>
4513 : inline _ForwardIterator
4514 : partition(_ForwardIterator __first, _ForwardIterator __last,
4515 : _Predicate __pred)
4516 : {
4517 : // concept requirements
4518 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4519 : _ForwardIterator>)
4520 : __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4521 : typename iterator_traits<_ForwardIterator>::value_type>)
4522 : __glibcxx_requires_valid_range(__first, __last);
4523 :
4524 : return std::__partition(__first, __last, __pred,
4525 : std::__iterator_category(__first));
4526 : }
4527 :
4528 :
4529 : /**
4530 : * @brief Sort the smallest elements of a sequence.
4531 : * @ingroup sorting_algorithms
4532 : * @param __first An iterator.
4533 : * @param __middle Another iterator.
4534 : * @param __last Another iterator.
4535 : * @return Nothing.
4536 : *
4537 : * Sorts the smallest @p (__middle-__first) elements in the range
4538 : * @p [first,last) and moves them to the range @p [__first,__middle). The
4539 : * order of the remaining elements in the range @p [__middle,__last) is
4540 : * undefined.
4541 : * After the sort if @e i and @e j are iterators in the range
4542 : * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4543 : * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
4544 : */
4545 : template<typename _RandomAccessIterator>
4546 : inline void
4547 : partial_sort(_RandomAccessIterator __first,
4548 : _RandomAccessIterator __middle,
4549 : _RandomAccessIterator __last)
4550 : {
4551 : // concept requirements
4552 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4553 : _RandomAccessIterator>)
4554 : __glibcxx_function_requires(_LessThanComparableConcept<
4555 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4556 : __glibcxx_requires_valid_range(__first, __middle);
4557 : __glibcxx_requires_valid_range(__middle, __last);
4558 : __glibcxx_requires_irreflexive(__first, __last);
4559 :
4560 : std::__partial_sort(__first, __middle, __last,
4561 : __gnu_cxx::__ops::__iter_less_iter());
4562 : }
4563 :
4564 : /**
4565 : * @brief Sort the smallest elements of a sequence using a predicate
4566 : * for comparison.
4567 : * @ingroup sorting_algorithms
4568 : * @param __first An iterator.
4569 : * @param __middle Another iterator.
4570 : * @param __last Another iterator.
4571 : * @param __comp A comparison functor.
4572 : * @return Nothing.
4573 : *
4574 : * Sorts the smallest @p (__middle-__first) elements in the range
4575 : * @p [__first,__last) and moves them to the range @p [__first,__middle). The
4576 : * order of the remaining elements in the range @p [__middle,__last) is
4577 : * undefined.
4578 : * After the sort if @e i and @e j are iterators in the range
4579 : * @p [__first,__middle) such that i precedes j and @e k is an iterator in
4580 : * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
4581 : * are both false.
4582 : */
4583 : template<typename _RandomAccessIterator, typename _Compare>
4584 : inline void
4585 : partial_sort(_RandomAccessIterator __first,
4586 : _RandomAccessIterator __middle,
4587 : _RandomAccessIterator __last,
4588 : _Compare __comp)
4589 : {
4590 : // concept requirements
4591 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4592 : _RandomAccessIterator>)
4593 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4594 : typename iterator_traits<_RandomAccessIterator>::value_type,
4595 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4596 : __glibcxx_requires_valid_range(__first, __middle);
4597 : __glibcxx_requires_valid_range(__middle, __last);
4598 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4599 :
4600 : std::__partial_sort(__first, __middle, __last,
4601 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
4602 : }
4603 :
4604 : /**
4605 : * @brief Sort a sequence just enough to find a particular position.
4606 : * @ingroup sorting_algorithms
4607 : * @param __first An iterator.
4608 : * @param __nth Another iterator.
4609 : * @param __last Another iterator.
4610 : * @return Nothing.
4611 : *
4612 : * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4613 : * is the same element that would have been in that position had the
4614 : * whole sequence been sorted. The elements either side of @p *__nth are
4615 : * not completely sorted, but for any iterator @e i in the range
4616 : * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4617 : * holds that *j < *i is false.
4618 : */
4619 : template<typename _RandomAccessIterator>
4620 : inline void
4621 : nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4622 : _RandomAccessIterator __last)
4623 : {
4624 : // concept requirements
4625 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4626 : _RandomAccessIterator>)
4627 : __glibcxx_function_requires(_LessThanComparableConcept<
4628 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4629 : __glibcxx_requires_valid_range(__first, __nth);
4630 : __glibcxx_requires_valid_range(__nth, __last);
4631 : __glibcxx_requires_irreflexive(__first, __last);
4632 :
4633 : if (__first == __last || __nth == __last)
4634 : return;
4635 :
4636 : std::__introselect(__first, __nth, __last,
4637 : std::__lg(__last - __first) * 2,
4638 : __gnu_cxx::__ops::__iter_less_iter());
4639 : }
4640 :
4641 : /**
4642 : * @brief Sort a sequence just enough to find a particular position
4643 : * using a predicate for comparison.
4644 : * @ingroup sorting_algorithms
4645 : * @param __first An iterator.
4646 : * @param __nth Another iterator.
4647 : * @param __last Another iterator.
4648 : * @param __comp A comparison functor.
4649 : * @return Nothing.
4650 : *
4651 : * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
4652 : * is the same element that would have been in that position had the
4653 : * whole sequence been sorted. The elements either side of @p *__nth are
4654 : * not completely sorted, but for any iterator @e i in the range
4655 : * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
4656 : * holds that @p __comp(*j,*i) is false.
4657 : */
4658 : template<typename _RandomAccessIterator, typename _Compare>
4659 : inline void
4660 : nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4661 : _RandomAccessIterator __last, _Compare __comp)
4662 : {
4663 : // concept requirements
4664 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4665 : _RandomAccessIterator>)
4666 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4667 : typename iterator_traits<_RandomAccessIterator>::value_type,
4668 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4669 : __glibcxx_requires_valid_range(__first, __nth);
4670 : __glibcxx_requires_valid_range(__nth, __last);
4671 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4672 :
4673 : if (__first == __last || __nth == __last)
4674 : return;
4675 :
4676 : std::__introselect(__first, __nth, __last,
4677 : std::__lg(__last - __first) * 2,
4678 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
4679 : }
4680 :
4681 : /**
4682 : * @brief Sort the elements of a sequence.
4683 : * @ingroup sorting_algorithms
4684 : * @param __first An iterator.
4685 : * @param __last Another iterator.
4686 : * @return Nothing.
4687 : *
4688 : * Sorts the elements in the range @p [__first,__last) in ascending order,
4689 : * such that for each iterator @e i in the range @p [__first,__last-1),
4690 : * *(i+1)<*i is false.
4691 : *
4692 : * The relative ordering of equivalent elements is not preserved, use
4693 : * @p stable_sort() if this is needed.
4694 : */
4695 : template<typename _RandomAccessIterator>
4696 : inline void
4697 : sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4698 : {
4699 : // concept requirements
4700 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4701 : _RandomAccessIterator>)
4702 : __glibcxx_function_requires(_LessThanComparableConcept<
4703 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4704 : __glibcxx_requires_valid_range(__first, __last);
4705 : __glibcxx_requires_irreflexive(__first, __last);
4706 :
4707 : std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4708 : }
4709 :
4710 : /**
4711 : * @brief Sort the elements of a sequence using a predicate for comparison.
4712 : * @ingroup sorting_algorithms
4713 : * @param __first An iterator.
4714 : * @param __last Another iterator.
4715 : * @param __comp A comparison functor.
4716 : * @return Nothing.
4717 : *
4718 : * Sorts the elements in the range @p [__first,__last) in ascending order,
4719 : * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
4720 : * range @p [__first,__last-1).
4721 : *
4722 : * The relative ordering of equivalent elements is not preserved, use
4723 : * @p stable_sort() if this is needed.
4724 : */
4725 : template<typename _RandomAccessIterator, typename _Compare>
4726 : inline void
4727 0 : sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4728 : _Compare __comp)
4729 : {
4730 : // concept requirements
4731 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4732 : _RandomAccessIterator>)
4733 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4734 : typename iterator_traits<_RandomAccessIterator>::value_type,
4735 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4736 : __glibcxx_requires_valid_range(__first, __last);
4737 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4738 :
4739 0 : std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4740 0 : }
4741 :
4742 : template<typename _InputIterator1, typename _InputIterator2,
4743 : typename _OutputIterator, typename _Compare>
4744 : _OutputIterator
4745 0 : __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4746 : _InputIterator2 __first2, _InputIterator2 __last2,
4747 : _OutputIterator __result, _Compare __comp)
4748 : {
4749 0 : while (__first1 != __last1 && __first2 != __last2)
4750 : {
4751 0 : if (__comp(__first2, __first1))
4752 : {
4753 0 : *__result = *__first2;
4754 0 : ++__first2;
4755 : }
4756 : else
4757 : {
4758 0 : *__result = *__first1;
4759 0 : ++__first1;
4760 : }
4761 0 : ++__result;
4762 : }
4763 0 : return std::copy(__first2, __last2,
4764 0 : std::copy(__first1, __last1, __result));
4765 : }
4766 :
4767 : /**
4768 : * @brief Merges two sorted ranges.
4769 : * @ingroup sorting_algorithms
4770 : * @param __first1 An iterator.
4771 : * @param __first2 Another iterator.
4772 : * @param __last1 Another iterator.
4773 : * @param __last2 Another iterator.
4774 : * @param __result An iterator pointing to the end of the merged range.
4775 : * @return An iterator pointing to the first element <em>not less
4776 : * than</em> @e val.
4777 : *
4778 : * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4779 : * the sorted range @p [__result, __result + (__last1-__first1) +
4780 : * (__last2-__first2)). Both input ranges must be sorted, and the
4781 : * output range must not overlap with either of the input ranges.
4782 : * The sort is @e stable, that is, for equivalent elements in the
4783 : * two ranges, elements from the first range will always come
4784 : * before elements from the second.
4785 : */
4786 : template<typename _InputIterator1, typename _InputIterator2,
4787 : typename _OutputIterator>
4788 : inline _OutputIterator
4789 : merge(_InputIterator1 __first1, _InputIterator1 __last1,
4790 : _InputIterator2 __first2, _InputIterator2 __last2,
4791 : _OutputIterator __result)
4792 : {
4793 : // concept requirements
4794 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4795 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4796 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4797 : typename iterator_traits<_InputIterator1>::value_type>)
4798 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4799 : typename iterator_traits<_InputIterator2>::value_type>)
4800 : __glibcxx_function_requires(_LessThanOpConcept<
4801 : typename iterator_traits<_InputIterator2>::value_type,
4802 : typename iterator_traits<_InputIterator1>::value_type>)
4803 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4804 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4805 : __glibcxx_requires_irreflexive2(__first1, __last1);
4806 : __glibcxx_requires_irreflexive2(__first2, __last2);
4807 :
4808 : return _GLIBCXX_STD_A::__merge(__first1, __last1,
4809 : __first2, __last2, __result,
4810 : __gnu_cxx::__ops::__iter_less_iter());
4811 : }
4812 :
4813 : /**
4814 : * @brief Merges two sorted ranges.
4815 : * @ingroup sorting_algorithms
4816 : * @param __first1 An iterator.
4817 : * @param __first2 Another iterator.
4818 : * @param __last1 Another iterator.
4819 : * @param __last2 Another iterator.
4820 : * @param __result An iterator pointing to the end of the merged range.
4821 : * @param __comp A functor to use for comparisons.
4822 : * @return An iterator pointing to the first element "not less
4823 : * than" @e val.
4824 : *
4825 : * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4826 : * the sorted range @p [__result, __result + (__last1-__first1) +
4827 : * (__last2-__first2)). Both input ranges must be sorted, and the
4828 : * output range must not overlap with either of the input ranges.
4829 : * The sort is @e stable, that is, for equivalent elements in the
4830 : * two ranges, elements from the first range will always come
4831 : * before elements from the second.
4832 : *
4833 : * The comparison function should have the same effects on ordering as
4834 : * the function used for the initial sort.
4835 : */
4836 : template<typename _InputIterator1, typename _InputIterator2,
4837 : typename _OutputIterator, typename _Compare>
4838 : inline _OutputIterator
4839 0 : merge(_InputIterator1 __first1, _InputIterator1 __last1,
4840 : _InputIterator2 __first2, _InputIterator2 __last2,
4841 : _OutputIterator __result, _Compare __comp)
4842 : {
4843 : // concept requirements
4844 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4845 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4846 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4847 : typename iterator_traits<_InputIterator1>::value_type>)
4848 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4849 : typename iterator_traits<_InputIterator2>::value_type>)
4850 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4851 : typename iterator_traits<_InputIterator2>::value_type,
4852 : typename iterator_traits<_InputIterator1>::value_type>)
4853 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4854 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4855 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4856 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4857 :
4858 0 : return _GLIBCXX_STD_A::__merge(__first1, __last1,
4859 : __first2, __last2, __result,
4860 0 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
4861 : }
4862 :
4863 : template<typename _RandomAccessIterator, typename _Compare>
4864 : inline void
4865 : __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4866 : _Compare __comp)
4867 : {
4868 : typedef typename iterator_traits<_RandomAccessIterator>::value_type
4869 : _ValueType;
4870 : typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4871 : _DistanceType;
4872 :
4873 : typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4874 : _TmpBuf __buf(__first, __last);
4875 :
4876 : if (__buf.begin() == 0)
4877 : std::__inplace_stable_sort(__first, __last, __comp);
4878 : else
4879 : std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4880 : _DistanceType(__buf.size()), __comp);
4881 : }
4882 :
4883 : /**
4884 : * @brief Sort the elements of a sequence, preserving the relative order
4885 : * of equivalent elements.
4886 : * @ingroup sorting_algorithms
4887 : * @param __first An iterator.
4888 : * @param __last Another iterator.
4889 : * @return Nothing.
4890 : *
4891 : * Sorts the elements in the range @p [__first,__last) in ascending order,
4892 : * such that for each iterator @p i in the range @p [__first,__last-1),
4893 : * @p *(i+1)<*i is false.
4894 : *
4895 : * The relative ordering of equivalent elements is preserved, so any two
4896 : * elements @p x and @p y in the range @p [__first,__last) such that
4897 : * @p x<y is false and @p y<x is false will have the same relative
4898 : * ordering after calling @p stable_sort().
4899 : */
4900 : template<typename _RandomAccessIterator>
4901 : inline void
4902 : stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4903 : {
4904 : // concept requirements
4905 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4906 : _RandomAccessIterator>)
4907 : __glibcxx_function_requires(_LessThanComparableConcept<
4908 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4909 : __glibcxx_requires_valid_range(__first, __last);
4910 : __glibcxx_requires_irreflexive(__first, __last);
4911 :
4912 : _GLIBCXX_STD_A::__stable_sort(__first, __last,
4913 : __gnu_cxx::__ops::__iter_less_iter());
4914 : }
4915 :
4916 : /**
4917 : * @brief Sort the elements of a sequence using a predicate for comparison,
4918 : * preserving the relative order of equivalent elements.
4919 : * @ingroup sorting_algorithms
4920 : * @param __first An iterator.
4921 : * @param __last Another iterator.
4922 : * @param __comp A comparison functor.
4923 : * @return Nothing.
4924 : *
4925 : * Sorts the elements in the range @p [__first,__last) in ascending order,
4926 : * such that for each iterator @p i in the range @p [__first,__last-1),
4927 : * @p __comp(*(i+1),*i) is false.
4928 : *
4929 : * The relative ordering of equivalent elements is preserved, so any two
4930 : * elements @p x and @p y in the range @p [__first,__last) such that
4931 : * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
4932 : * relative ordering after calling @p stable_sort().
4933 : */
4934 : template<typename _RandomAccessIterator, typename _Compare>
4935 : inline void
4936 : stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4937 : _Compare __comp)
4938 : {
4939 : // concept requirements
4940 : __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4941 : _RandomAccessIterator>)
4942 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4943 : typename iterator_traits<_RandomAccessIterator>::value_type,
4944 : typename iterator_traits<_RandomAccessIterator>::value_type>)
4945 : __glibcxx_requires_valid_range(__first, __last);
4946 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4947 :
4948 : _GLIBCXX_STD_A::__stable_sort(__first, __last,
4949 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
4950 : }
4951 :
4952 : template<typename _InputIterator1, typename _InputIterator2,
4953 : typename _OutputIterator,
4954 : typename _Compare>
4955 : _OutputIterator
4956 : __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4957 : _InputIterator2 __first2, _InputIterator2 __last2,
4958 : _OutputIterator __result, _Compare __comp)
4959 : {
4960 : while (__first1 != __last1 && __first2 != __last2)
4961 : {
4962 : if (__comp(__first1, __first2))
4963 : {
4964 : *__result = *__first1;
4965 : ++__first1;
4966 : }
4967 : else if (__comp(__first2, __first1))
4968 : {
4969 : *__result = *__first2;
4970 : ++__first2;
4971 : }
4972 : else
4973 : {
4974 : *__result = *__first1;
4975 : ++__first1;
4976 : ++__first2;
4977 : }
4978 : ++__result;
4979 : }
4980 : return std::copy(__first2, __last2,
4981 : std::copy(__first1, __last1, __result));
4982 : }
4983 :
4984 : /**
4985 : * @brief Return the union of two sorted ranges.
4986 : * @ingroup set_algorithms
4987 : * @param __first1 Start of first range.
4988 : * @param __last1 End of first range.
4989 : * @param __first2 Start of second range.
4990 : * @param __last2 End of second range.
4991 : * @return End of the output range.
4992 : * @ingroup set_algorithms
4993 : *
4994 : * This operation iterates over both ranges, copying elements present in
4995 : * each range in order to the output range. Iterators increment for each
4996 : * range. When the current element of one range is less than the other,
4997 : * that element is copied and the iterator advanced. If an element is
4998 : * contained in both ranges, the element from the first range is copied and
4999 : * both ranges advance. The output range may not overlap either input
5000 : * range.
5001 : */
5002 : template<typename _InputIterator1, typename _InputIterator2,
5003 : typename _OutputIterator>
5004 : inline _OutputIterator
5005 : set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5006 : _InputIterator2 __first2, _InputIterator2 __last2,
5007 : _OutputIterator __result)
5008 : {
5009 : // concept requirements
5010 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5011 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5012 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5013 : typename iterator_traits<_InputIterator1>::value_type>)
5014 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5015 : typename iterator_traits<_InputIterator2>::value_type>)
5016 : __glibcxx_function_requires(_LessThanOpConcept<
5017 : typename iterator_traits<_InputIterator1>::value_type,
5018 : typename iterator_traits<_InputIterator2>::value_type>)
5019 : __glibcxx_function_requires(_LessThanOpConcept<
5020 : typename iterator_traits<_InputIterator2>::value_type,
5021 : typename iterator_traits<_InputIterator1>::value_type>)
5022 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5023 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5024 : __glibcxx_requires_irreflexive2(__first1, __last1);
5025 : __glibcxx_requires_irreflexive2(__first2, __last2);
5026 :
5027 : return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5028 : __first2, __last2, __result,
5029 : __gnu_cxx::__ops::__iter_less_iter());
5030 : }
5031 :
5032 : /**
5033 : * @brief Return the union of two sorted ranges using a comparison functor.
5034 : * @ingroup set_algorithms
5035 : * @param __first1 Start of first range.
5036 : * @param __last1 End of first range.
5037 : * @param __first2 Start of second range.
5038 : * @param __last2 End of second range.
5039 : * @param __comp The comparison functor.
5040 : * @return End of the output range.
5041 : * @ingroup set_algorithms
5042 : *
5043 : * This operation iterates over both ranges, copying elements present in
5044 : * each range in order to the output range. Iterators increment for each
5045 : * range. When the current element of one range is less than the other
5046 : * according to @p __comp, that element is copied and the iterator advanced.
5047 : * If an equivalent element according to @p __comp is contained in both
5048 : * ranges, the element from the first range is copied and both ranges
5049 : * advance. The output range may not overlap either input range.
5050 : */
5051 : template<typename _InputIterator1, typename _InputIterator2,
5052 : typename _OutputIterator, typename _Compare>
5053 : inline _OutputIterator
5054 : set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5055 : _InputIterator2 __first2, _InputIterator2 __last2,
5056 : _OutputIterator __result, _Compare __comp)
5057 : {
5058 : // concept requirements
5059 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5060 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5061 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5062 : typename iterator_traits<_InputIterator1>::value_type>)
5063 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5064 : typename iterator_traits<_InputIterator2>::value_type>)
5065 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5066 : typename iterator_traits<_InputIterator1>::value_type,
5067 : typename iterator_traits<_InputIterator2>::value_type>)
5068 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5069 : typename iterator_traits<_InputIterator2>::value_type,
5070 : typename iterator_traits<_InputIterator1>::value_type>)
5071 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5072 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5073 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5074 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5075 :
5076 : return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5077 : __first2, __last2, __result,
5078 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5079 : }
5080 :
5081 : template<typename _InputIterator1, typename _InputIterator2,
5082 : typename _OutputIterator,
5083 : typename _Compare>
5084 : _OutputIterator
5085 : __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5086 : _InputIterator2 __first2, _InputIterator2 __last2,
5087 : _OutputIterator __result, _Compare __comp)
5088 : {
5089 : while (__first1 != __last1 && __first2 != __last2)
5090 : if (__comp(__first1, __first2))
5091 : ++__first1;
5092 : else if (__comp(__first2, __first1))
5093 : ++__first2;
5094 : else
5095 : {
5096 : *__result = *__first1;
5097 : ++__first1;
5098 : ++__first2;
5099 : ++__result;
5100 : }
5101 : return __result;
5102 : }
5103 :
5104 : /**
5105 : * @brief Return the intersection of two sorted ranges.
5106 : * @ingroup set_algorithms
5107 : * @param __first1 Start of first range.
5108 : * @param __last1 End of first range.
5109 : * @param __first2 Start of second range.
5110 : * @param __last2 End of second range.
5111 : * @return End of the output range.
5112 : * @ingroup set_algorithms
5113 : *
5114 : * This operation iterates over both ranges, copying elements present in
5115 : * both ranges in order to the output range. Iterators increment for each
5116 : * range. When the current element of one range is less than the other,
5117 : * that iterator advances. If an element is contained in both ranges, the
5118 : * element from the first range is copied and both ranges advance. The
5119 : * output range may not overlap either input range.
5120 : */
5121 : template<typename _InputIterator1, typename _InputIterator2,
5122 : typename _OutputIterator>
5123 : inline _OutputIterator
5124 : set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5125 : _InputIterator2 __first2, _InputIterator2 __last2,
5126 : _OutputIterator __result)
5127 : {
5128 : // concept requirements
5129 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5130 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5131 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5132 : typename iterator_traits<_InputIterator1>::value_type>)
5133 : __glibcxx_function_requires(_LessThanOpConcept<
5134 : typename iterator_traits<_InputIterator1>::value_type,
5135 : typename iterator_traits<_InputIterator2>::value_type>)
5136 : __glibcxx_function_requires(_LessThanOpConcept<
5137 : typename iterator_traits<_InputIterator2>::value_type,
5138 : typename iterator_traits<_InputIterator1>::value_type>)
5139 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5140 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5141 : __glibcxx_requires_irreflexive2(__first1, __last1);
5142 : __glibcxx_requires_irreflexive2(__first2, __last2);
5143 :
5144 : return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5145 : __first2, __last2, __result,
5146 : __gnu_cxx::__ops::__iter_less_iter());
5147 : }
5148 :
5149 : /**
5150 : * @brief Return the intersection of two sorted ranges using comparison
5151 : * functor.
5152 : * @ingroup set_algorithms
5153 : * @param __first1 Start of first range.
5154 : * @param __last1 End of first range.
5155 : * @param __first2 Start of second range.
5156 : * @param __last2 End of second range.
5157 : * @param __comp The comparison functor.
5158 : * @return End of the output range.
5159 : * @ingroup set_algorithms
5160 : *
5161 : * This operation iterates over both ranges, copying elements present in
5162 : * both ranges in order to the output range. Iterators increment for each
5163 : * range. When the current element of one range is less than the other
5164 : * according to @p __comp, that iterator advances. If an element is
5165 : * contained in both ranges according to @p __comp, the element from the
5166 : * first range is copied and both ranges advance. The output range may not
5167 : * overlap either input range.
5168 : */
5169 : template<typename _InputIterator1, typename _InputIterator2,
5170 : typename _OutputIterator, typename _Compare>
5171 : inline _OutputIterator
5172 : set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5173 : _InputIterator2 __first2, _InputIterator2 __last2,
5174 : _OutputIterator __result, _Compare __comp)
5175 : {
5176 : // concept requirements
5177 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5178 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5179 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5180 : typename iterator_traits<_InputIterator1>::value_type>)
5181 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5182 : typename iterator_traits<_InputIterator1>::value_type,
5183 : typename iterator_traits<_InputIterator2>::value_type>)
5184 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5185 : typename iterator_traits<_InputIterator2>::value_type,
5186 : typename iterator_traits<_InputIterator1>::value_type>)
5187 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5188 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5189 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5190 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5191 :
5192 : return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5193 : __first2, __last2, __result,
5194 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5195 : }
5196 :
5197 : template<typename _InputIterator1, typename _InputIterator2,
5198 : typename _OutputIterator,
5199 : typename _Compare>
5200 : _OutputIterator
5201 : __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5202 : _InputIterator2 __first2, _InputIterator2 __last2,
5203 : _OutputIterator __result, _Compare __comp)
5204 : {
5205 : while (__first1 != __last1 && __first2 != __last2)
5206 : if (__comp(__first1, __first2))
5207 : {
5208 : *__result = *__first1;
5209 : ++__first1;
5210 : ++__result;
5211 : }
5212 : else if (__comp(__first2, __first1))
5213 : ++__first2;
5214 : else
5215 : {
5216 : ++__first1;
5217 : ++__first2;
5218 : }
5219 : return std::copy(__first1, __last1, __result);
5220 : }
5221 :
5222 : /**
5223 : * @brief Return the difference of two sorted ranges.
5224 : * @ingroup set_algorithms
5225 : * @param __first1 Start of first range.
5226 : * @param __last1 End of first range.
5227 : * @param __first2 Start of second range.
5228 : * @param __last2 End of second range.
5229 : * @return End of the output range.
5230 : * @ingroup set_algorithms
5231 : *
5232 : * This operation iterates over both ranges, copying elements present in
5233 : * the first range but not the second in order to the output range.
5234 : * Iterators increment for each range. When the current element of the
5235 : * first range is less than the second, that element is copied and the
5236 : * iterator advances. If the current element of the second range is less,
5237 : * the iterator advances, but no element is copied. If an element is
5238 : * contained in both ranges, no elements are copied and both ranges
5239 : * advance. The output range may not overlap either input range.
5240 : */
5241 : template<typename _InputIterator1, typename _InputIterator2,
5242 : typename _OutputIterator>
5243 : inline _OutputIterator
5244 : set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5245 : _InputIterator2 __first2, _InputIterator2 __last2,
5246 : _OutputIterator __result)
5247 : {
5248 : // concept requirements
5249 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5250 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5251 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5252 : typename iterator_traits<_InputIterator1>::value_type>)
5253 : __glibcxx_function_requires(_LessThanOpConcept<
5254 : typename iterator_traits<_InputIterator1>::value_type,
5255 : typename iterator_traits<_InputIterator2>::value_type>)
5256 : __glibcxx_function_requires(_LessThanOpConcept<
5257 : typename iterator_traits<_InputIterator2>::value_type,
5258 : typename iterator_traits<_InputIterator1>::value_type>)
5259 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5260 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5261 : __glibcxx_requires_irreflexive2(__first1, __last1);
5262 : __glibcxx_requires_irreflexive2(__first2, __last2);
5263 :
5264 : return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5265 : __first2, __last2, __result,
5266 : __gnu_cxx::__ops::__iter_less_iter());
5267 : }
5268 :
5269 : /**
5270 : * @brief Return the difference of two sorted ranges using comparison
5271 : * functor.
5272 : * @ingroup set_algorithms
5273 : * @param __first1 Start of first range.
5274 : * @param __last1 End of first range.
5275 : * @param __first2 Start of second range.
5276 : * @param __last2 End of second range.
5277 : * @param __comp The comparison functor.
5278 : * @return End of the output range.
5279 : * @ingroup set_algorithms
5280 : *
5281 : * This operation iterates over both ranges, copying elements present in
5282 : * the first range but not the second in order to the output range.
5283 : * Iterators increment for each range. When the current element of the
5284 : * first range is less than the second according to @p __comp, that element
5285 : * is copied and the iterator advances. If the current element of the
5286 : * second range is less, no element is copied and the iterator advances.
5287 : * If an element is contained in both ranges according to @p __comp, no
5288 : * elements are copied and both ranges advance. The output range may not
5289 : * overlap either input range.
5290 : */
5291 : template<typename _InputIterator1, typename _InputIterator2,
5292 : typename _OutputIterator, typename _Compare>
5293 : inline _OutputIterator
5294 : set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5295 : _InputIterator2 __first2, _InputIterator2 __last2,
5296 : _OutputIterator __result, _Compare __comp)
5297 : {
5298 : // concept requirements
5299 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5300 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5301 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5302 : typename iterator_traits<_InputIterator1>::value_type>)
5303 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5304 : typename iterator_traits<_InputIterator1>::value_type,
5305 : typename iterator_traits<_InputIterator2>::value_type>)
5306 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5307 : typename iterator_traits<_InputIterator2>::value_type,
5308 : typename iterator_traits<_InputIterator1>::value_type>)
5309 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5310 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5311 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5312 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5313 :
5314 : return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5315 : __first2, __last2, __result,
5316 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5317 : }
5318 :
5319 : template<typename _InputIterator1, typename _InputIterator2,
5320 : typename _OutputIterator,
5321 : typename _Compare>
5322 : _OutputIterator
5323 : __set_symmetric_difference(_InputIterator1 __first1,
5324 : _InputIterator1 __last1,
5325 : _InputIterator2 __first2,
5326 : _InputIterator2 __last2,
5327 : _OutputIterator __result,
5328 : _Compare __comp)
5329 : {
5330 : while (__first1 != __last1 && __first2 != __last2)
5331 : if (__comp(__first1, __first2))
5332 : {
5333 : *__result = *__first1;
5334 : ++__first1;
5335 : ++__result;
5336 : }
5337 : else if (__comp(__first2, __first1))
5338 : {
5339 : *__result = *__first2;
5340 : ++__first2;
5341 : ++__result;
5342 : }
5343 : else
5344 : {
5345 : ++__first1;
5346 : ++__first2;
5347 : }
5348 : return std::copy(__first2, __last2,
5349 : std::copy(__first1, __last1, __result));
5350 : }
5351 :
5352 : /**
5353 : * @brief Return the symmetric difference of two sorted ranges.
5354 : * @ingroup set_algorithms
5355 : * @param __first1 Start of first range.
5356 : * @param __last1 End of first range.
5357 : * @param __first2 Start of second range.
5358 : * @param __last2 End of second range.
5359 : * @return End of the output range.
5360 : * @ingroup set_algorithms
5361 : *
5362 : * This operation iterates over both ranges, copying elements present in
5363 : * one range but not the other in order to the output range. Iterators
5364 : * increment for each range. When the current element of one range is less
5365 : * than the other, that element is copied and the iterator advances. If an
5366 : * element is contained in both ranges, no elements are copied and both
5367 : * ranges advance. The output range may not overlap either input range.
5368 : */
5369 : template<typename _InputIterator1, typename _InputIterator2,
5370 : typename _OutputIterator>
5371 : inline _OutputIterator
5372 : set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5373 : _InputIterator2 __first2, _InputIterator2 __last2,
5374 : _OutputIterator __result)
5375 : {
5376 : // concept requirements
5377 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5378 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5379 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5380 : typename iterator_traits<_InputIterator1>::value_type>)
5381 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5382 : typename iterator_traits<_InputIterator2>::value_type>)
5383 : __glibcxx_function_requires(_LessThanOpConcept<
5384 : typename iterator_traits<_InputIterator1>::value_type,
5385 : typename iterator_traits<_InputIterator2>::value_type>)
5386 : __glibcxx_function_requires(_LessThanOpConcept<
5387 : typename iterator_traits<_InputIterator2>::value_type,
5388 : typename iterator_traits<_InputIterator1>::value_type>)
5389 : __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5390 : __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5391 : __glibcxx_requires_irreflexive2(__first1, __last1);
5392 : __glibcxx_requires_irreflexive2(__first2, __last2);
5393 :
5394 : return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5395 : __first2, __last2, __result,
5396 : __gnu_cxx::__ops::__iter_less_iter());
5397 : }
5398 :
5399 : /**
5400 : * @brief Return the symmetric difference of two sorted ranges using
5401 : * comparison functor.
5402 : * @ingroup set_algorithms
5403 : * @param __first1 Start of first range.
5404 : * @param __last1 End of first range.
5405 : * @param __first2 Start of second range.
5406 : * @param __last2 End of second range.
5407 : * @param __comp The comparison functor.
5408 : * @return End of the output range.
5409 : * @ingroup set_algorithms
5410 : *
5411 : * This operation iterates over both ranges, copying elements present in
5412 : * one range but not the other in order to the output range. Iterators
5413 : * increment for each range. When the current element of one range is less
5414 : * than the other according to @p comp, that element is copied and the
5415 : * iterator advances. If an element is contained in both ranges according
5416 : * to @p __comp, no elements are copied and both ranges advance. The output
5417 : * range may not overlap either input range.
5418 : */
5419 : template<typename _InputIterator1, typename _InputIterator2,
5420 : typename _OutputIterator, typename _Compare>
5421 : inline _OutputIterator
5422 : set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5423 : _InputIterator2 __first2, _InputIterator2 __last2,
5424 : _OutputIterator __result,
5425 : _Compare __comp)
5426 : {
5427 : // concept requirements
5428 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5429 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5430 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5431 : typename iterator_traits<_InputIterator1>::value_type>)
5432 : __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5433 : typename iterator_traits<_InputIterator2>::value_type>)
5434 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5435 : typename iterator_traits<_InputIterator1>::value_type,
5436 : typename iterator_traits<_InputIterator2>::value_type>)
5437 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5438 : typename iterator_traits<_InputIterator2>::value_type,
5439 : typename iterator_traits<_InputIterator1>::value_type>)
5440 : __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5441 : __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5442 : __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5443 : __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5444 :
5445 : return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5446 : __first2, __last2, __result,
5447 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5448 : }
5449 :
5450 : template<typename _ForwardIterator, typename _Compare>
5451 : _GLIBCXX14_CONSTEXPR
5452 : _ForwardIterator
5453 : __min_element(_ForwardIterator __first, _ForwardIterator __last,
5454 : _Compare __comp)
5455 : {
5456 : if (__first == __last)
5457 : return __first;
5458 : _ForwardIterator __result = __first;
5459 : while (++__first != __last)
5460 : if (__comp(__first, __result))
5461 : __result = __first;
5462 : return __result;
5463 : }
5464 :
5465 : /**
5466 : * @brief Return the minimum element in a range.
5467 : * @ingroup sorting_algorithms
5468 : * @param __first Start of range.
5469 : * @param __last End of range.
5470 : * @return Iterator referencing the first instance of the smallest value.
5471 : */
5472 : template<typename _ForwardIterator>
5473 : _GLIBCXX14_CONSTEXPR
5474 : _ForwardIterator
5475 : inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5476 : {
5477 : // concept requirements
5478 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5479 : __glibcxx_function_requires(_LessThanComparableConcept<
5480 : typename iterator_traits<_ForwardIterator>::value_type>)
5481 : __glibcxx_requires_valid_range(__first, __last);
5482 : __glibcxx_requires_irreflexive(__first, __last);
5483 :
5484 : return _GLIBCXX_STD_A::__min_element(__first, __last,
5485 : __gnu_cxx::__ops::__iter_less_iter());
5486 : }
5487 :
5488 : /**
5489 : * @brief Return the minimum element in a range using comparison functor.
5490 : * @ingroup sorting_algorithms
5491 : * @param __first Start of range.
5492 : * @param __last End of range.
5493 : * @param __comp Comparison functor.
5494 : * @return Iterator referencing the first instance of the smallest value
5495 : * according to __comp.
5496 : */
5497 : template<typename _ForwardIterator, typename _Compare>
5498 : _GLIBCXX14_CONSTEXPR
5499 : inline _ForwardIterator
5500 : min_element(_ForwardIterator __first, _ForwardIterator __last,
5501 : _Compare __comp)
5502 : {
5503 : // concept requirements
5504 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5505 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5506 : typename iterator_traits<_ForwardIterator>::value_type,
5507 : typename iterator_traits<_ForwardIterator>::value_type>)
5508 : __glibcxx_requires_valid_range(__first, __last);
5509 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5510 :
5511 : return _GLIBCXX_STD_A::__min_element(__first, __last,
5512 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5513 : }
5514 :
5515 : template<typename _ForwardIterator, typename _Compare>
5516 : _GLIBCXX14_CONSTEXPR
5517 : _ForwardIterator
5518 : __max_element(_ForwardIterator __first, _ForwardIterator __last,
5519 : _Compare __comp)
5520 : {
5521 : if (__first == __last) return __first;
5522 : _ForwardIterator __result = __first;
5523 : while (++__first != __last)
5524 : if (__comp(__result, __first))
5525 : __result = __first;
5526 : return __result;
5527 : }
5528 :
5529 : /**
5530 : * @brief Return the maximum element in a range.
5531 : * @ingroup sorting_algorithms
5532 : * @param __first Start of range.
5533 : * @param __last End of range.
5534 : * @return Iterator referencing the first instance of the largest value.
5535 : */
5536 : template<typename _ForwardIterator>
5537 : _GLIBCXX14_CONSTEXPR
5538 : inline _ForwardIterator
5539 : max_element(_ForwardIterator __first, _ForwardIterator __last)
5540 : {
5541 : // concept requirements
5542 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5543 : __glibcxx_function_requires(_LessThanComparableConcept<
5544 : typename iterator_traits<_ForwardIterator>::value_type>)
5545 : __glibcxx_requires_valid_range(__first, __last);
5546 : __glibcxx_requires_irreflexive(__first, __last);
5547 :
5548 : return _GLIBCXX_STD_A::__max_element(__first, __last,
5549 : __gnu_cxx::__ops::__iter_less_iter());
5550 : }
5551 :
5552 : /**
5553 : * @brief Return the maximum element in a range using comparison functor.
5554 : * @ingroup sorting_algorithms
5555 : * @param __first Start of range.
5556 : * @param __last End of range.
5557 : * @param __comp Comparison functor.
5558 : * @return Iterator referencing the first instance of the largest value
5559 : * according to __comp.
5560 : */
5561 : template<typename _ForwardIterator, typename _Compare>
5562 : _GLIBCXX14_CONSTEXPR
5563 : inline _ForwardIterator
5564 : max_element(_ForwardIterator __first, _ForwardIterator __last,
5565 : _Compare __comp)
5566 : {
5567 : // concept requirements
5568 : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5569 : __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5570 : typename iterator_traits<_ForwardIterator>::value_type,
5571 : typename iterator_traits<_ForwardIterator>::value_type>)
5572 : __glibcxx_requires_valid_range(__first, __last);
5573 : __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5574 :
5575 : return _GLIBCXX_STD_A::__max_element(__first, __last,
5576 : __gnu_cxx::__ops::__iter_comp_iter(__comp));
5577 : }
5578 :
5579 : _GLIBCXX_END_NAMESPACE_ALGO
5580 : } // namespace std
5581 :
5582 : #endif /* _STL_ALGO_H */
|
