Line data Source code
1 : // Core algorithmic facilities -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 : // Free Software Foundation, Inc.
5 : //
6 : // This file is part of the GNU ISO C++ Library. This library is free
7 : // software; you can redistribute it and/or modify it under the
8 : // terms of the GNU General Public License as published by the
9 : // Free Software Foundation; either version 3, or (at your option)
10 : // any later version.
11 :
12 : // This library is distributed in the hope that it will be useful,
13 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : // GNU General Public License for more details.
16 :
17 : // Under Section 7 of GPL version 3, you are granted additional
18 : // permissions described in the GCC Runtime Library Exception, version
19 : // 3.1, as published by the Free Software Foundation.
20 :
21 : // You should have received a copy of the GNU General Public License and
22 : // a copy of the GCC Runtime Library Exception along with this program;
23 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 : // <http://www.gnu.org/licenses/>.
25 :
26 : /*
27 : *
28 : * Copyright (c) 1994
29 : * Hewlett-Packard Company
30 : *
31 : * Permission to use, copy, modify, distribute and sell this software
32 : * and its documentation for any purpose is hereby granted without fee,
33 : * provided that the above copyright notice appear in all copies and
34 : * that both that copyright notice and this permission notice appear
35 : * in supporting documentation. Hewlett-Packard Company makes no
36 : * representations about the suitability of this software for any
37 : * purpose. It is provided "as is" without express or implied warranty.
38 : *
39 : *
40 : * Copyright (c) 1996-1998
41 : * Silicon Graphics Computer Systems, Inc.
42 : *
43 : * Permission to use, copy, modify, distribute and sell this software
44 : * and its documentation for any purpose is hereby granted without fee,
45 : * provided that the above copyright notice appear in all copies and
46 : * that both that copyright notice and this permission notice appear
47 : * in supporting documentation. Silicon Graphics makes no
48 : * representations about the suitability of this software for any
49 : * purpose. It is provided "as is" without express or implied warranty.
50 : */
51 :
52 : /** @file stl_algobase.h
53 : * This is an internal header file, included by other library headers.
54 : * You should not attempt to use it directly.
55 : */
56 :
57 : #ifndef _STL_ALGOBASE_H
58 : #define _STL_ALGOBASE_H 1
59 :
60 : #include <bits/c++config.h>
61 : #include <cstddef>
62 : #include <bits/functexcept.h>
63 : #include <bits/cpp_type_traits.h>
64 : #include <ext/type_traits.h>
65 : #include <ext/numeric_traits.h>
66 : #include <bits/stl_pair.h>
67 : #include <bits/stl_iterator_base_types.h>
68 : #include <bits/stl_iterator_base_funcs.h>
69 : #include <bits/stl_iterator.h>
70 : #include <bits/concept_check.h>
71 : #include <debug/debug.h>
72 : #include <bits/move.h> // For std::swap and _GLIBCXX_MOVE
73 :
74 : _GLIBCXX_BEGIN_NAMESPACE(std)
75 :
76 : // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
77 : // nutshell, we are partially implementing the resolution of DR 187,
78 : // when it's safe, i.e., the value_types are equal.
79 : template<bool _BoolType>
80 : struct __iter_swap
81 : {
82 : template<typename _ForwardIterator1, typename _ForwardIterator2>
83 : static void
84 : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
85 : {
86 : typedef typename iterator_traits<_ForwardIterator1>::value_type
87 : _ValueType1;
88 : _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
89 : *__a = _GLIBCXX_MOVE(*__b);
90 : *__b = _GLIBCXX_MOVE(__tmp);
91 : }
92 : };
93 :
94 : template<>
95 : struct __iter_swap<true>
96 : {
97 : template<typename _ForwardIterator1, typename _ForwardIterator2>
98 : static void
99 : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
100 : {
101 : swap(*__a, *__b);
102 : }
103 : };
104 :
105 : /**
106 : * @brief Swaps the contents of two iterators.
107 : * @ingroup mutating_algorithms
108 : * @param a An iterator.
109 : * @param b Another iterator.
110 : * @return Nothing.
111 : *
112 : * This function swaps the values pointed to by two iterators, not the
113 : * iterators themselves.
114 : */
115 : template<typename _ForwardIterator1, typename _ForwardIterator2>
116 : inline void
117 : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
118 : {
119 : typedef typename iterator_traits<_ForwardIterator1>::value_type
120 : _ValueType1;
121 : typedef typename iterator_traits<_ForwardIterator2>::value_type
122 : _ValueType2;
123 :
124 : // concept requirements
125 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
126 : _ForwardIterator1>)
127 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
128 : _ForwardIterator2>)
129 : __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
130 : _ValueType2>)
131 : __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
132 : _ValueType1>)
133 :
134 : typedef typename iterator_traits<_ForwardIterator1>::reference
135 : _ReferenceType1;
136 : typedef typename iterator_traits<_ForwardIterator2>::reference
137 : _ReferenceType2;
138 : std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
139 : && __are_same<_ValueType1&, _ReferenceType1>::__value
140 : && __are_same<_ValueType2&, _ReferenceType2>::__value>::
141 : iter_swap(__a, __b);
142 : }
143 :
144 : /**
145 : * @brief Swap the elements of two sequences.
146 : * @ingroup mutating_algorithms
147 : * @param first1 A forward iterator.
148 : * @param last1 A forward iterator.
149 : * @param first2 A forward iterator.
150 : * @return An iterator equal to @p first2+(last1-first1).
151 : *
152 : * Swaps each element in the range @p [first1,last1) with the
153 : * corresponding element in the range @p [first2,(last1-first1)).
154 : * The ranges must not overlap.
155 : */
156 : template<typename _ForwardIterator1, typename _ForwardIterator2>
157 : _ForwardIterator2
158 : swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
159 : _ForwardIterator2 __first2)
160 : {
161 : // concept requirements
162 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
163 : _ForwardIterator1>)
164 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
165 : _ForwardIterator2>)
166 : __glibcxx_requires_valid_range(__first1, __last1);
167 :
168 : for (; __first1 != __last1; ++__first1, ++__first2)
169 : std::iter_swap(__first1, __first2);
170 : return __first2;
171 : }
172 :
173 : /**
174 : * @brief This does what you think it does.
175 : * @ingroup sorting_algorithms
176 : * @param a A thing of arbitrary type.
177 : * @param b Another thing of arbitrary type.
178 : * @return The lesser of the parameters.
179 : *
180 : * This is the simple classic generic implementation. It will work on
181 : * temporary expressions, since they are only evaluated once, unlike a
182 : * preprocessor macro.
183 : */
184 : template<typename _Tp>
185 : inline const _Tp&
186 : min(const _Tp& __a, const _Tp& __b)
187 : {
188 : // concept requirements
189 : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
190 : //return __b < __a ? __b : __a;
191 : if (__b < __a)
192 : return __b;
193 : return __a;
194 : }
195 :
196 : /**
197 : * @brief This does what you think it does.
198 : * @ingroup sorting_algorithms
199 : * @param a A thing of arbitrary type.
200 : * @param b Another thing of arbitrary type.
201 : * @return The greater of the parameters.
202 : *
203 : * This is the simple classic generic implementation. It will work on
204 : * temporary expressions, since they are only evaluated once, unlike a
205 : * preprocessor macro.
206 : */
207 : template<typename _Tp>
208 : inline const _Tp&
209 1523413 : max(const _Tp& __a, const _Tp& __b)
210 : {
211 : // concept requirements
212 : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
213 : //return __a < __b ? __b : __a;
214 1523413 : if (__a < __b)
215 1305222 : return __b;
216 218191 : return __a;
217 : }
218 :
219 : /**
220 : * @brief This does what you think it does.
221 : * @ingroup sorting_algorithms
222 : * @param a A thing of arbitrary type.
223 : * @param b Another thing of arbitrary type.
224 : * @param comp A @link comparison_functors comparison functor@endlink.
225 : * @return The lesser of the parameters.
226 : *
227 : * This will work on temporary expressions, since they are only evaluated
228 : * once, unlike a preprocessor macro.
229 : */
230 : template<typename _Tp, typename _Compare>
231 : inline const _Tp&
232 : min(const _Tp& __a, const _Tp& __b, _Compare __comp)
233 : {
234 : //return __comp(__b, __a) ? __b : __a;
235 : if (__comp(__b, __a))
236 : return __b;
237 : return __a;
238 : }
239 :
240 : /**
241 : * @brief This does what you think it does.
242 : * @ingroup sorting_algorithms
243 : * @param a A thing of arbitrary type.
244 : * @param b Another thing of arbitrary type.
245 : * @param comp A @link comparison_functors comparison functor@endlink.
246 : * @return The greater of the parameters.
247 : *
248 : * This will work on temporary expressions, since they are only evaluated
249 : * once, unlike a preprocessor macro.
250 : */
251 : template<typename _Tp, typename _Compare>
252 : inline const _Tp&
253 : max(const _Tp& __a, const _Tp& __b, _Compare __comp)
254 : {
255 : //return __comp(__a, __b) ? __b : __a;
256 : if (__comp(__a, __b))
257 : return __b;
258 : return __a;
259 : }
260 :
261 :
262 : // If _Iterator is a __normal_iterator return its base (a plain pointer,
263 : // normally) otherwise return it untouched. See copy, fill, ...
264 : template<typename _Iterator,
265 : bool _IsNormal = __is_normal_iterator<_Iterator>::__value>
266 : struct __niter_base
267 : {
268 : static _Iterator
269 27161646 : __b(_Iterator __it)
270 27161646 : { return __it; }
271 : };
272 :
273 : template<typename _Iterator>
274 : struct __niter_base<_Iterator, true>
275 : {
276 : static typename _Iterator::iterator_type
277 : __b(_Iterator __it)
278 : { return __it.base(); }
279 : };
280 :
281 : // Likewise, for move_iterator.
282 : template<typename _Iterator,
283 : bool _IsMove = __is_move_iterator<_Iterator>::__value>
284 : struct __miter_base
285 : {
286 : static _Iterator
287 9880736 : __b(_Iterator __it)
288 9880736 : { return __it; }
289 : };
290 :
291 : template<typename _Iterator>
292 : struct __miter_base<_Iterator, true>
293 : {
294 : static typename _Iterator::iterator_type
295 : __b(_Iterator __it)
296 : { return __it.base(); }
297 : };
298 :
299 : // All of these auxiliary structs serve two purposes. (1) Replace
300 : // calls to copy with memmove whenever possible. (Memmove, not memcpy,
301 : // because the input and output ranges are permitted to overlap.)
302 : // (2) If we're using random access iterators, then write the loop as
303 : // a for loop with an explicit count.
304 :
305 : template<bool, bool, typename>
306 : struct __copy_move
307 : {
308 : template<typename _II, typename _OI>
309 : static _OI
310 3617 : __copy_m(_II __first, _II __last, _OI __result)
311 : {
312 58770 : for (; __first != __last; ++__result, ++__first)
313 55153 : *__result = *__first;
314 3617 : return __result;
315 : }
316 : };
317 :
318 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
319 : template<typename _Category>
320 : struct __copy_move<true, false, _Category>
321 : {
322 : template<typename _II, typename _OI>
323 : static _OI
324 : __copy_m(_II __first, _II __last, _OI __result)
325 : {
326 : for (; __first != __last; ++__result, ++__first)
327 : *__result = std::move(*__first);
328 : return __result;
329 : }
330 : };
331 : #endif
332 :
333 : template<>
334 : struct __copy_move<false, false, random_access_iterator_tag>
335 : {
336 : template<typename _II, typename _OI>
337 : static _OI
338 165 : __copy_m(_II __first, _II __last, _OI __result)
339 : {
340 : typedef typename iterator_traits<_II>::difference_type _Distance;
341 165 : for(_Distance __n = __last - __first; __n > 0; --__n)
342 : {
343 0 : *__result = *__first;
344 0 : ++__first;
345 0 : ++__result;
346 : }
347 165 : return __result;
348 : }
349 : };
350 :
351 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
352 : template<>
353 : struct __copy_move<true, false, random_access_iterator_tag>
354 : {
355 : template<typename _II, typename _OI>
356 : static _OI
357 : __copy_m(_II __first, _II __last, _OI __result)
358 : {
359 : typedef typename iterator_traits<_II>::difference_type _Distance;
360 : for(_Distance __n = __last - __first; __n > 0; --__n)
361 : {
362 : *__result = std::move(*__first);
363 : ++__first;
364 : ++__result;
365 : }
366 : return __result;
367 : }
368 : };
369 : #endif
370 :
371 : template<bool _IsMove>
372 : struct __copy_move<_IsMove, true, random_access_iterator_tag>
373 : {
374 : template<typename _Tp>
375 : static _Tp*
376 4936578 : __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
377 : {
378 4936578 : __builtin_memmove(__result, __first,
379 : sizeof(_Tp) * (__last - __first));
380 4936578 : return __result + (__last - __first);
381 : }
382 : };
383 :
384 : template<bool _IsMove, typename _II, typename _OI>
385 : inline _OI
386 4940345 : __copy_move_a(_II __first, _II __last, _OI __result)
387 : {
388 : typedef typename iterator_traits<_II>::value_type _ValueTypeI;
389 : typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
390 : typedef typename iterator_traits<_II>::iterator_category _Category;
391 : const bool __simple = (__is_pod(_ValueTypeI)
392 : && __is_pointer<_II>::__value
393 : && __is_pointer<_OI>::__value
394 4940345 : && __are_same<_ValueTypeI, _ValueTypeO>::__value);
395 :
396 : return std::__copy_move<_IsMove, __simple,
397 4940345 : _Category>::__copy_m(__first, __last, __result);
398 : }
399 :
400 : // Helpers for streambuf iterators (either istream or ostream).
401 : // NB: avoid including <iosfwd>, relatively large.
402 : template<typename _CharT>
403 : struct char_traits;
404 :
405 : template<typename _CharT, typename _Traits>
406 : class istreambuf_iterator;
407 :
408 : template<typename _CharT, typename _Traits>
409 : class ostreambuf_iterator;
410 :
411 : template<bool _IsMove, typename _CharT>
412 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
413 : ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
414 : __copy_move_a2(_CharT*, _CharT*,
415 : ostreambuf_iterator<_CharT, char_traits<_CharT> >);
416 :
417 : template<bool _IsMove, typename _CharT>
418 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
419 : ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
420 : __copy_move_a2(const _CharT*, const _CharT*,
421 : ostreambuf_iterator<_CharT, char_traits<_CharT> >);
422 :
423 : template<bool _IsMove, typename _CharT>
424 : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
425 : _CharT*>::__type
426 : __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
427 : istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
428 :
429 : template<bool _IsMove, typename _II, typename _OI>
430 : inline _OI
431 4940369 : __copy_move_a2(_II __first, _II __last, _OI __result)
432 : {
433 : return _OI(std::__copy_move_a<_IsMove>
434 : (std::__niter_base<_II>::__b(__first),
435 : std::__niter_base<_II>::__b(__last),
436 4940369 : std::__niter_base<_OI>::__b(__result)));
437 : }
438 :
439 : /**
440 : * @brief Copies the range [first,last) into result.
441 : * @ingroup mutating_algorithms
442 : * @param first An input iterator.
443 : * @param last An input iterator.
444 : * @param result An output iterator.
445 : * @return result + (first - last)
446 : *
447 : * This inline function will boil down to a call to @c memmove whenever
448 : * possible. Failing that, if random access iterators are passed, then the
449 : * loop count will be known (and therefore a candidate for compiler
450 : * optimizations such as unrolling). Result may not be contained within
451 : * [first,last); the copy_backward function should be used instead.
452 : *
453 : * Note that the end of the output range is permitted to be contained
454 : * within [first,last).
455 : */
456 : template<typename _II, typename _OI>
457 : inline _OI
458 4940378 : copy(_II __first, _II __last, _OI __result)
459 : {
460 : // concept requirements
461 : __glibcxx_function_requires(_InputIteratorConcept<_II>)
462 : __glibcxx_function_requires(_OutputIteratorConcept<_OI,
463 : typename iterator_traits<_II>::value_type>)
464 : __glibcxx_requires_valid_range(__first, __last);
465 :
466 : return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
467 : (std::__miter_base<_II>::__b(__first),
468 4940378 : std::__miter_base<_II>::__b(__last), __result));
469 : }
470 :
471 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
472 : /**
473 : * @brief Moves the range [first,last) into result.
474 : * @ingroup mutating_algorithms
475 : * @param first An input iterator.
476 : * @param last An input iterator.
477 : * @param result An output iterator.
478 : * @return result + (first - last)
479 : *
480 : * This inline function will boil down to a call to @c memmove whenever
481 : * possible. Failing that, if random access iterators are passed, then the
482 : * loop count will be known (and therefore a candidate for compiler
483 : * optimizations such as unrolling). Result may not be contained within
484 : * [first,last); the move_backward function should be used instead.
485 : *
486 : * Note that the end of the output range is permitted to be contained
487 : * within [first,last).
488 : */
489 : template<typename _II, typename _OI>
490 : inline _OI
491 : move(_II __first, _II __last, _OI __result)
492 : {
493 : // concept requirements
494 : __glibcxx_function_requires(_InputIteratorConcept<_II>)
495 : __glibcxx_function_requires(_OutputIteratorConcept<_OI,
496 : typename iterator_traits<_II>::value_type>)
497 : __glibcxx_requires_valid_range(__first, __last);
498 :
499 : return (std::__copy_move_a2<true>
500 : (std::__miter_base<_II>::__b(__first),
501 : std::__miter_base<_II>::__b(__last), __result));
502 : }
503 :
504 : #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
505 : #else
506 : #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
507 : #endif
508 :
509 : template<bool, bool, typename>
510 : struct __copy_move_backward
511 : {
512 : template<typename _BI1, typename _BI2>
513 : static _BI2
514 : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
515 : {
516 : while (__first != __last)
517 : *--__result = *--__last;
518 : return __result;
519 : }
520 : };
521 :
522 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
523 : template<typename _Category>
524 : struct __copy_move_backward<true, false, _Category>
525 : {
526 : template<typename _BI1, typename _BI2>
527 : static _BI2
528 : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
529 : {
530 : while (__first != __last)
531 : *--__result = std::move(*--__last);
532 : return __result;
533 : }
534 : };
535 : #endif
536 :
537 : template<>
538 : struct __copy_move_backward<false, false, random_access_iterator_tag>
539 : {
540 : template<typename _BI1, typename _BI2>
541 : static _BI2
542 0 : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
543 : {
544 : typename iterator_traits<_BI1>::difference_type __n;
545 0 : for (__n = __last - __first; __n > 0; --__n)
546 0 : *--__result = *--__last;
547 0 : return __result;
548 : }
549 : };
550 :
551 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
552 : template<>
553 : struct __copy_move_backward<true, false, random_access_iterator_tag>
554 : {
555 : template<typename _BI1, typename _BI2>
556 : static _BI2
557 : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
558 : {
559 : typename iterator_traits<_BI1>::difference_type __n;
560 : for (__n = __last - __first; __n > 0; --__n)
561 : *--__result = std::move(*--__last);
562 : return __result;
563 : }
564 : };
565 : #endif
566 :
567 : template<bool _IsMove>
568 : struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
569 : {
570 : template<typename _Tp>
571 : static _Tp*
572 0 : __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
573 : {
574 0 : const ptrdiff_t _Num = __last - __first;
575 0 : __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
576 0 : return __result - _Num;
577 : }
578 : };
579 :
580 : template<bool _IsMove, typename _BI1, typename _BI2>
581 : inline _BI2
582 0 : __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
583 : {
584 : typedef typename iterator_traits<_BI1>::value_type _ValueType1;
585 : typedef typename iterator_traits<_BI2>::value_type _ValueType2;
586 : typedef typename iterator_traits<_BI1>::iterator_category _Category;
587 : const bool __simple = (__is_pod(_ValueType1)
588 : && __is_pointer<_BI1>::__value
589 : && __is_pointer<_BI2>::__value
590 0 : && __are_same<_ValueType1, _ValueType2>::__value);
591 :
592 : return std::__copy_move_backward<_IsMove, __simple,
593 : _Category>::__copy_move_b(__first,
594 : __last,
595 0 : __result);
596 : }
597 :
598 : template<bool _IsMove, typename _BI1, typename _BI2>
599 : inline _BI2
600 0 : __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
601 : {
602 : return _BI2(std::__copy_move_backward_a<_IsMove>
603 : (std::__niter_base<_BI1>::__b(__first),
604 : std::__niter_base<_BI1>::__b(__last),
605 0 : std::__niter_base<_BI2>::__b(__result)));
606 : }
607 :
608 : /**
609 : * @brief Copies the range [first,last) into result.
610 : * @ingroup mutating_algorithms
611 : * @param first A bidirectional iterator.
612 : * @param last A bidirectional iterator.
613 : * @param result A bidirectional iterator.
614 : * @return result - (first - last)
615 : *
616 : * The function has the same effect as copy, but starts at the end of the
617 : * range and works its way to the start, returning the start of the result.
618 : * This inline function will boil down to a call to @c memmove whenever
619 : * possible. Failing that, if random access iterators are passed, then the
620 : * loop count will be known (and therefore a candidate for compiler
621 : * optimizations such as unrolling).
622 : *
623 : * Result may not be in the range [first,last). Use copy instead. Note
624 : * that the start of the output range may overlap [first,last).
625 : */
626 : template<typename _BI1, typename _BI2>
627 : inline _BI2
628 0 : copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
629 : {
630 : // concept requirements
631 : __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
632 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
633 : __glibcxx_function_requires(_ConvertibleConcept<
634 : typename iterator_traits<_BI1>::value_type,
635 : typename iterator_traits<_BI2>::value_type>)
636 : __glibcxx_requires_valid_range(__first, __last);
637 :
638 : return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
639 : (std::__miter_base<_BI1>::__b(__first),
640 0 : std::__miter_base<_BI1>::__b(__last), __result));
641 : }
642 :
643 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
644 : /**
645 : * @brief Moves the range [first,last) into result.
646 : * @ingroup mutating_algorithms
647 : * @param first A bidirectional iterator.
648 : * @param last A bidirectional iterator.
649 : * @param result A bidirectional iterator.
650 : * @return result - (first - last)
651 : *
652 : * The function has the same effect as move, but starts at the end of the
653 : * range and works its way to the start, returning the start of the result.
654 : * This inline function will boil down to a call to @c memmove whenever
655 : * possible. Failing that, if random access iterators are passed, then the
656 : * loop count will be known (and therefore a candidate for compiler
657 : * optimizations such as unrolling).
658 : *
659 : * Result may not be in the range [first,last). Use move instead. Note
660 : * that the start of the output range may overlap [first,last).
661 : */
662 : template<typename _BI1, typename _BI2>
663 : inline _BI2
664 : move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
665 : {
666 : // concept requirements
667 : __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
668 : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
669 : __glibcxx_function_requires(_ConvertibleConcept<
670 : typename iterator_traits<_BI1>::value_type,
671 : typename iterator_traits<_BI2>::value_type>)
672 : __glibcxx_requires_valid_range(__first, __last);
673 :
674 : return (std::__copy_move_backward_a2<true>
675 : (std::__miter_base<_BI1>::__b(__first),
676 : std::__miter_base<_BI1>::__b(__last), __result));
677 : }
678 :
679 : #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
680 : #else
681 : #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
682 : #endif
683 :
684 : template<typename _ForwardIterator, typename _Tp>
685 : inline typename
686 : __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
687 : __fill_a(_ForwardIterator __first, _ForwardIterator __last,
688 : const _Tp& __value)
689 : {
690 : for (; __first != __last; ++__first)
691 : *__first = __value;
692 : }
693 :
694 : template<typename _ForwardIterator, typename _Tp>
695 : inline typename
696 : __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
697 : __fill_a(_ForwardIterator __first, _ForwardIterator __last,
698 : const _Tp& __value)
699 : {
700 : const _Tp __tmp = __value;
701 : for (; __first != __last; ++__first)
702 : *__first = __tmp;
703 : }
704 :
705 : // Specialization: for char types we can use memset.
706 : template<typename _Tp>
707 : inline typename
708 : __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
709 : __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
710 : {
711 : const _Tp __tmp = __c;
712 : __builtin_memset(__first, static_cast<unsigned char>(__tmp),
713 : __last - __first);
714 : }
715 :
716 : /**
717 : * @brief Fills the range [first,last) with copies of value.
718 : * @ingroup mutating_algorithms
719 : * @param first A forward iterator.
720 : * @param last A forward iterator.
721 : * @param value A reference-to-const of arbitrary type.
722 : * @return Nothing.
723 : *
724 : * This function fills a range with copies of the same value. For char
725 : * types filling contiguous areas of memory, this becomes an inline call
726 : * to @c memset or @c wmemset.
727 : */
728 : template<typename _ForwardIterator, typename _Tp>
729 : inline void
730 : fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
731 : {
732 : // concept requirements
733 : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
734 : _ForwardIterator>)
735 : __glibcxx_requires_valid_range(__first, __last);
736 :
737 : std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first),
738 : std::__niter_base<_ForwardIterator>::__b(__last), __value);
739 : }
740 :
741 : template<typename _OutputIterator, typename _Size, typename _Tp>
742 : inline typename
743 : __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
744 : __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
745 : {
746 : for (; __n > 0; --__n, ++__first)
747 : *__first = __value;
748 : return __first;
749 : }
750 :
751 : template<typename _OutputIterator, typename _Size, typename _Tp>
752 : inline typename
753 : __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
754 : __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
755 : {
756 : const _Tp __tmp = __value;
757 : for (; __n > 0; --__n, ++__first)
758 : *__first = __tmp;
759 : return __first;
760 : }
761 :
762 : template<typename _Size, typename _Tp>
763 : inline typename
764 : __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
765 : __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
766 : {
767 : std::__fill_a(__first, __first + __n, __c);
768 : return __first + __n;
769 : }
770 :
771 : /**
772 : * @brief Fills the range [first,first+n) with copies of value.
773 : * @ingroup mutating_algorithms
774 : * @param first An output iterator.
775 : * @param n The count of copies to perform.
776 : * @param value A reference-to-const of arbitrary type.
777 : * @return The iterator at first+n.
778 : *
779 : * This function fills a range with copies of the same value. For char
780 : * types filling contiguous areas of memory, this becomes an inline call
781 : * to @c memset or @ wmemset.
782 : */
783 : template<typename _OI, typename _Size, typename _Tp>
784 : inline _OI
785 : fill_n(_OI __first, _Size __n, const _Tp& __value)
786 : {
787 : // concept requirements
788 : __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
789 :
790 : return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first),
791 : __n, __value));
792 : }
793 :
794 : template<bool _BoolType>
795 : struct __equal
796 : {
797 : template<typename _II1, typename _II2>
798 : static bool
799 81596 : equal(_II1 __first1, _II1 __last1, _II2 __first2)
800 : {
801 1062053 : for (; __first1 != __last1; ++__first1, ++__first2)
802 980457 : if (!(*__first1 == *__first2))
803 0 : return false;
804 81596 : return true;
805 : }
806 : };
807 :
808 : template<>
809 : struct __equal<true>
810 : {
811 : template<typename _Tp>
812 : static bool
813 4031943 : equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
814 : {
815 : return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
816 4031943 : * (__last1 - __first1));
817 : }
818 : };
819 :
820 : template<typename _II1, typename _II2>
821 : inline bool
822 4113539 : __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
823 : {
824 : typedef typename iterator_traits<_II1>::value_type _ValueType1;
825 : typedef typename iterator_traits<_II2>::value_type _ValueType2;
826 : const bool __simple = (__is_integer<_ValueType1>::__value
827 : && __is_pointer<_II1>::__value
828 : && __is_pointer<_II2>::__value
829 4113539 : && __are_same<_ValueType1, _ValueType2>::__value);
830 :
831 4113539 : return std::__equal<__simple>::equal(__first1, __last1, __first2);
832 : }
833 :
834 :
835 : template<typename, typename>
836 : struct __lc_rai
837 : {
838 : template<typename _II1, typename _II2>
839 : static _II1
840 : __newlast1(_II1, _II1 __last1, _II2, _II2)
841 : { return __last1; }
842 :
843 : template<typename _II>
844 : static bool
845 : __cnd2(_II __first, _II __last)
846 : { return __first != __last; }
847 : };
848 :
849 : template<>
850 : struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
851 : {
852 : template<typename _RAI1, typename _RAI2>
853 : static _RAI1
854 : __newlast1(_RAI1 __first1, _RAI1 __last1,
855 : _RAI2 __first2, _RAI2 __last2)
856 : {
857 : const typename iterator_traits<_RAI1>::difference_type
858 : __diff1 = __last1 - __first1;
859 : const typename iterator_traits<_RAI2>::difference_type
860 : __diff2 = __last2 - __first2;
861 : return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
862 : }
863 :
864 : template<typename _RAI>
865 : static bool
866 : __cnd2(_RAI, _RAI)
867 : { return true; }
868 : };
869 :
870 : template<bool _BoolType>
871 : struct __lexicographical_compare
872 : {
873 : template<typename _II1, typename _II2>
874 : static bool __lc(_II1, _II1, _II2, _II2);
875 : };
876 :
877 : template<bool _BoolType>
878 : template<typename _II1, typename _II2>
879 : bool
880 : __lexicographical_compare<_BoolType>::
881 : __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
882 : {
883 : typedef typename iterator_traits<_II1>::iterator_category _Category1;
884 : typedef typename iterator_traits<_II2>::iterator_category _Category2;
885 : typedef std::__lc_rai<_Category1, _Category2> __rai_type;
886 :
887 : __last1 = __rai_type::__newlast1(__first1, __last1,
888 : __first2, __last2);
889 : for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
890 : ++__first1, ++__first2)
891 : {
892 : if (*__first1 < *__first2)
893 : return true;
894 : if (*__first2 < *__first1)
895 : return false;
896 : }
897 : return __first1 == __last1 && __first2 != __last2;
898 : }
899 :
900 : template<>
901 : struct __lexicographical_compare<true>
902 : {
903 : template<typename _Tp, typename _Up>
904 : static bool
905 : __lc(const _Tp* __first1, const _Tp* __last1,
906 : const _Up* __first2, const _Up* __last2)
907 : {
908 : const size_t __len1 = __last1 - __first1;
909 : const size_t __len2 = __last2 - __first2;
910 : const int __result = __builtin_memcmp(__first1, __first2,
911 : std::min(__len1, __len2));
912 : return __result != 0 ? __result < 0 : __len1 < __len2;
913 : }
914 : };
915 :
916 : template<typename _II1, typename _II2>
917 : inline bool
918 : __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
919 : _II2 __first2, _II2 __last2)
920 : {
921 : typedef typename iterator_traits<_II1>::value_type _ValueType1;
922 : typedef typename iterator_traits<_II2>::value_type _ValueType2;
923 : const bool __simple =
924 : (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
925 : && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
926 : && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
927 : && __is_pointer<_II1>::__value
928 : && __is_pointer<_II2>::__value);
929 :
930 : return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
931 : __first2, __last2);
932 : }
933 :
934 : _GLIBCXX_END_NAMESPACE
935 :
936 : _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
937 :
938 : /**
939 : * @brief Tests a range for element-wise equality.
940 : * @ingroup non_mutating_algorithms
941 : * @param first1 An input iterator.
942 : * @param last1 An input iterator.
943 : * @param first2 An input iterator.
944 : * @return A boolean true or false.
945 : *
946 : * This compares the elements of two ranges using @c == and returns true or
947 : * false depending on whether all of the corresponding elements of the
948 : * ranges are equal.
949 : */
950 : template<typename _II1, typename _II2>
951 : inline bool
952 4113539 : equal(_II1 __first1, _II1 __last1, _II2 __first2)
953 : {
954 : // concept requirements
955 : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
956 : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
957 : __glibcxx_function_requires(_EqualOpConcept<
958 : typename iterator_traits<_II1>::value_type,
959 : typename iterator_traits<_II2>::value_type>)
960 : __glibcxx_requires_valid_range(__first1, __last1);
961 :
962 : return std::__equal_aux(std::__niter_base<_II1>::__b(__first1),
963 : std::__niter_base<_II1>::__b(__last1),
964 4113539 : std::__niter_base<_II2>::__b(__first2));
965 : }
966 :
967 : /**
968 : * @brief Tests a range for element-wise equality.
969 : * @ingroup non_mutating_algorithms
970 : * @param first1 An input iterator.
971 : * @param last1 An input iterator.
972 : * @param first2 An input iterator.
973 : * @param binary_pred A binary predicate @link functors
974 : * functor@endlink.
975 : * @return A boolean true or false.
976 : *
977 : * This compares the elements of two ranges using the binary_pred
978 : * parameter, and returns true or
979 : * false depending on whether all of the corresponding elements of the
980 : * ranges are equal.
981 : */
982 : template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
983 : inline bool
984 : equal(_IIter1 __first1, _IIter1 __last1,
985 : _IIter2 __first2, _BinaryPredicate __binary_pred)
986 : {
987 : // concept requirements
988 : __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
989 : __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
990 : __glibcxx_requires_valid_range(__first1, __last1);
991 :
992 : for (; __first1 != __last1; ++__first1, ++__first2)
993 : if (!bool(__binary_pred(*__first1, *__first2)))
994 : return false;
995 : return true;
996 : }
997 :
998 : /**
999 : * @brief Performs "dictionary" comparison on ranges.
1000 : * @ingroup sorting_algorithms
1001 : * @param first1 An input iterator.
1002 : * @param last1 An input iterator.
1003 : * @param first2 An input iterator.
1004 : * @param last2 An input iterator.
1005 : * @return A boolean true or false.
1006 : *
1007 : * "Returns true if the sequence of elements defined by the range
1008 : * [first1,last1) is lexicographically less than the sequence of elements
1009 : * defined by the range [first2,last2). Returns false otherwise."
1010 : * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1011 : * then this is an inline call to @c memcmp.
1012 : */
1013 : template<typename _II1, typename _II2>
1014 : inline bool
1015 : lexicographical_compare(_II1 __first1, _II1 __last1,
1016 : _II2 __first2, _II2 __last2)
1017 : {
1018 : // concept requirements
1019 : typedef typename iterator_traits<_II1>::value_type _ValueType1;
1020 : typedef typename iterator_traits<_II2>::value_type _ValueType2;
1021 : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1022 : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1023 : __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1024 : __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1025 : __glibcxx_requires_valid_range(__first1, __last1);
1026 : __glibcxx_requires_valid_range(__first2, __last2);
1027 :
1028 : return std::__lexicographical_compare_aux
1029 : (std::__niter_base<_II1>::__b(__first1),
1030 : std::__niter_base<_II1>::__b(__last1),
1031 : std::__niter_base<_II2>::__b(__first2),
1032 : std::__niter_base<_II2>::__b(__last2));
1033 : }
1034 :
1035 : /**
1036 : * @brief Performs "dictionary" comparison on ranges.
1037 : * @ingroup sorting_algorithms
1038 : * @param first1 An input iterator.
1039 : * @param last1 An input iterator.
1040 : * @param first2 An input iterator.
1041 : * @param last2 An input iterator.
1042 : * @param comp A @link comparison_functors comparison functor@endlink.
1043 : * @return A boolean true or false.
1044 : *
1045 : * The same as the four-parameter @c lexicographical_compare, but uses the
1046 : * comp parameter instead of @c <.
1047 : */
1048 : template<typename _II1, typename _II2, typename _Compare>
1049 : bool
1050 : lexicographical_compare(_II1 __first1, _II1 __last1,
1051 : _II2 __first2, _II2 __last2, _Compare __comp)
1052 : {
1053 : typedef typename iterator_traits<_II1>::iterator_category _Category1;
1054 : typedef typename iterator_traits<_II2>::iterator_category _Category2;
1055 : typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1056 :
1057 : // concept requirements
1058 : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1059 : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1060 : __glibcxx_requires_valid_range(__first1, __last1);
1061 : __glibcxx_requires_valid_range(__first2, __last2);
1062 :
1063 : __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1064 : for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1065 : ++__first1, ++__first2)
1066 : {
1067 : if (__comp(*__first1, *__first2))
1068 : return true;
1069 : if (__comp(*__first2, *__first1))
1070 : return false;
1071 : }
1072 : return __first1 == __last1 && __first2 != __last2;
1073 : }
1074 :
1075 : /**
1076 : * @brief Finds the places in ranges which don't match.
1077 : * @ingroup non_mutating_algorithms
1078 : * @param first1 An input iterator.
1079 : * @param last1 An input iterator.
1080 : * @param first2 An input iterator.
1081 : * @return A pair of iterators pointing to the first mismatch.
1082 : *
1083 : * This compares the elements of two ranges using @c == and returns a pair
1084 : * of iterators. The first iterator points into the first range, the
1085 : * second iterator points into the second range, and the elements pointed
1086 : * to by the iterators are not equal.
1087 : */
1088 : template<typename _InputIterator1, typename _InputIterator2>
1089 : pair<_InputIterator1, _InputIterator2>
1090 : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1091 : _InputIterator2 __first2)
1092 : {
1093 : // concept requirements
1094 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1095 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1096 : __glibcxx_function_requires(_EqualOpConcept<
1097 : typename iterator_traits<_InputIterator1>::value_type,
1098 : typename iterator_traits<_InputIterator2>::value_type>)
1099 : __glibcxx_requires_valid_range(__first1, __last1);
1100 :
1101 : while (__first1 != __last1 && *__first1 == *__first2)
1102 : {
1103 : ++__first1;
1104 : ++__first2;
1105 : }
1106 : return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1107 : }
1108 :
1109 : /**
1110 : * @brief Finds the places in ranges which don't match.
1111 : * @ingroup non_mutating_algorithms
1112 : * @param first1 An input iterator.
1113 : * @param last1 An input iterator.
1114 : * @param first2 An input iterator.
1115 : * @param binary_pred A binary predicate @link functors
1116 : * functor@endlink.
1117 : * @return A pair of iterators pointing to the first mismatch.
1118 : *
1119 : * This compares the elements of two ranges using the binary_pred
1120 : * parameter, and returns a pair
1121 : * of iterators. The first iterator points into the first range, the
1122 : * second iterator points into the second range, and the elements pointed
1123 : * to by the iterators are not equal.
1124 : */
1125 : template<typename _InputIterator1, typename _InputIterator2,
1126 : typename _BinaryPredicate>
1127 : pair<_InputIterator1, _InputIterator2>
1128 : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1129 : _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1130 : {
1131 : // concept requirements
1132 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1133 : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1134 : __glibcxx_requires_valid_range(__first1, __last1);
1135 :
1136 : while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
1137 : {
1138 : ++__first1;
1139 : ++__first2;
1140 : }
1141 : return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1142 : }
1143 :
1144 : _GLIBCXX_END_NESTED_NAMESPACE
1145 :
1146 : // NB: This file is included within many other C++ includes, as a way
1147 : // of getting the base algorithms. So, make sure that parallel bits
1148 : // come in too if requested.
1149 : #ifdef _GLIBCXX_PARALLEL
1150 : # include <parallel/algobase.h>
1151 : #endif
1152 :
1153 : #endif
|
