1// Core algorithmic facilities -*- C++ -*- 
2 
3// Copyright (C) 2001-2019 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-1998 
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_algobase.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_ALGOBASE_H 
57#define _STL_ALGOBASE_H 1 
58 
59#include <bits/c++config.h> 
60#include <bits/functexcept.h> 
61#include <bits/cpp_type_traits.h> 
62#include <ext/type_traits.h> 
63#include <ext/numeric_traits.h> 
64#include <bits/stl_pair.h> 
65#include <bits/stl_iterator_base_types.h> 
66#include <bits/stl_iterator_base_funcs.h> 
67#include <bits/stl_iterator.h> 
68#include <bits/concept_check.h> 
69#include <debug/debug.h> 
70#include <bits/move.h> // For std::swap 
71#include <bits/predefined_ops.h> 
72#if __cplusplus >= 201103L 
73# include <type_traits> 
74#endif 
75 
76namespace std _GLIBCXX_VISIBILITY(default) 
77{ 
78_GLIBCXX_BEGIN_NAMESPACE_VERSION 
79 
80#if __cplusplus < 201103L 
81 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a 
82 // nutshell, we are partially implementing the resolution of DR 187, 
83 // when it's safe, i.e., the value_types are equal. 
84 template<bool _BoolType> 
85 struct __iter_swap 
86 { 
87 template<typename _ForwardIterator1, typename _ForwardIterator2> 
88 static void 
89 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 
90 { 
91 typedef typename iterator_traits<_ForwardIterator1>::value_type 
92 _ValueType1; 
93 _ValueType1 __tmp = *__a; 
94 *__a = *__b; 
95 *__b = __tmp; 
96 } 
97 }; 
98 
99 template<> 
100 struct __iter_swap<true> 
101 { 
102 template<typename _ForwardIterator1, typename _ForwardIterator2> 
103 static void 
104 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 
105 { 
106 swap(*__a, *__b); 
107 } 
108 }; 
109#endif 
110 
111 /** 
112 * @brief Swaps the contents of two iterators. 
113 * @ingroup mutating_algorithms 
114 * @param __a An iterator. 
115 * @param __b Another iterator. 
116 * @return Nothing. 
117 * 
118 * This function swaps the values pointed to by two iterators, not the 
119 * iterators themselves. 
120 */ 
121 template<typename _ForwardIterator1, typename _ForwardIterator2> 
122 inline void 
123 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 
124 { 
125 // concept requirements 
126 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 
127 _ForwardIterator1>) 
128 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 
129 _ForwardIterator2>) 
130 
131#if __cplusplus < 201103L 
132 typedef typename iterator_traits<_ForwardIterator1>::value_type 
133 _ValueType1; 
134 typedef typename iterator_traits<_ForwardIterator2>::value_type 
135 _ValueType2; 
136 
137 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 
138 _ValueType2>) 
139 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 
140 _ValueType1>) 
141 
142 typedef typename iterator_traits<_ForwardIterator1>::reference 
143 _ReferenceType1; 
144 typedef typename iterator_traits<_ForwardIterator2>::reference 
145 _ReferenceType2; 
146 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value 
147 && __are_same<_ValueType1&, _ReferenceType1>::__value 
148 && __are_same<_ValueType2&, _ReferenceType2>::__value>:: 
149 iter_swap(__a, __b); 
150#else 
151 swap(*__a, *__b); 
152#endif 
153 } 
154 
155 /** 
156 * @brief Swap the elements of two sequences. 
157 * @ingroup mutating_algorithms 
158 * @param __first1 A forward iterator. 
159 * @param __last1 A forward iterator. 
160 * @param __first2 A forward iterator. 
161 * @return An iterator equal to @p first2+(last1-first1). 
162 * 
163 * Swaps each element in the range @p [first1,last1) with the 
164 * corresponding element in the range @p [first2,(last1-first1)). 
165 * The ranges must not overlap. 
166 */ 
167 template<typename _ForwardIterator1, typename _ForwardIterator2> 
168 _ForwardIterator2 
169 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 
170 _ForwardIterator2 __first2) 
171 { 
172 // concept requirements 
173 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 
174 _ForwardIterator1>) 
175 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 
176 _ForwardIterator2>) 
177 __glibcxx_requires_valid_range(__first1, __last1); 
178 
179 for (; __first1 != __last1; ++__first1, (void)++__first2) 
180 std::iter_swap(__first1, __first2); 
181 return __first2; 
182 } 
183 
184 /** 
185 * @brief This does what you think it does. 
186 * @ingroup sorting_algorithms 
187 * @param __a A thing of arbitrary type. 
188 * @param __b Another thing of arbitrary type. 
189 * @return The lesser of the parameters. 
190 * 
191 * This is the simple classic generic implementation. It will work on 
192 * temporary expressions, since they are only evaluated once, unlike a 
193 * preprocessor macro. 
194 */ 
195 template<typename _Tp> 
196 _GLIBCXX14_CONSTEXPR 
197 inline const _Tp& 
198 min(const _Tp& __a, const _Tp& __b) 
199 { 
200 // concept requirements 
201 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 
202 //return __b < __a ? __b : __a; 
203 if (__b < __a) 
204 return __b; 
205 return __a; 
206 } 
207 
208 /** 
209 * @brief This does what you think it does. 
210 * @ingroup sorting_algorithms 
211 * @param __a A thing of arbitrary type. 
212 * @param __b Another thing of arbitrary type. 
213 * @return The greater of the parameters. 
214 * 
215 * This is the simple classic generic implementation. It will work on 
216 * temporary expressions, since they are only evaluated once, unlike a 
217 * preprocessor macro. 
218 */ 
219 template<typename _Tp> 
220 _GLIBCXX14_CONSTEXPR 
221 inline const _Tp& 
222 max(const _Tp& __a, const _Tp& __b) 
223 { 
224 // concept requirements 
225 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 
226 //return __a < __b ? __b : __a; 
227 if (__a < __b) 
228 return __b; 
229 return __a; 
230 } 
231 
232 /** 
233 * @brief This does what you think it does. 
234 * @ingroup sorting_algorithms 
235 * @param __a A thing of arbitrary type. 
236 * @param __b Another thing of arbitrary type. 
237 * @param __comp A @link comparison_functors comparison functor@endlink. 
238 * @return The lesser of the parameters. 
239 * 
240 * This will work on temporary expressions, since they are only evaluated 
241 * once, unlike a preprocessor macro. 
242 */ 
243 template<typename _Tp, typename _Compare> 
244 _GLIBCXX14_CONSTEXPR 
245 inline const _Tp& 
246 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 
247 { 
248 //return __comp(__b, __a) ? __b : __a; 
249 if (__comp(__b, __a)) 
250 return __b; 
251 return __a; 
252 } 
253 
254 /** 
255 * @brief This does what you think it does. 
256 * @ingroup sorting_algorithms 
257 * @param __a A thing of arbitrary type. 
258 * @param __b Another thing of arbitrary type. 
259 * @param __comp A @link comparison_functors comparison functor@endlink. 
260 * @return The greater of the parameters. 
261 * 
262 * This will work on temporary expressions, since they are only evaluated 
263 * once, unlike a preprocessor macro. 
264 */ 
265 template<typename _Tp, typename _Compare> 
266 _GLIBCXX14_CONSTEXPR 
267 inline const _Tp& 
268 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 
269 { 
270 //return __comp(__a, __b) ? __b : __a; 
271 if (__comp(__a, __b)) 
272 return __b; 
273 return __a; 
274 } 
275 
276 // Fallback implementation of the function in bits/stl_iterator.h used to 
277 // remove the __normal_iterator wrapper. See copy, fill, ... 
278 template<typename _Iterator> 
279 inline _Iterator 
280 __niter_base(_Iterator __it) 
281 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value) 
282 { return __it; } 
283 
284 // Reverse the __niter_base transformation to get a 
285 // __normal_iterator back again (this assumes that __normal_iterator 
286 // is only used to wrap random access iterators, like pointers). 
287 template<typename _From, typename _To> 
288 inline _From 
289 __niter_wrap(_From __from, _To __res) 
290 { return __from + (__res - std::__niter_base(__from)); } 
291 
292 // No need to wrap, iterator already has the right type. 
293 template<typename _Iterator> 
294 inline _Iterator 
295 __niter_wrap(const _Iterator&, _Iterator __res) 
296 { return __res; } 
297 
298 // All of these auxiliary structs serve two purposes. (1) Replace 
299 // calls to copy with memmove whenever possible. (Memmove, not memcpy, 
300 // because the input and output ranges are permitted to overlap.) 
301 // (2) If we're using random access iterators, then write the loop as 
302 // a for loop with an explicit count. 
303 
304 template<bool _IsMove, bool _IsSimple, typename _Category> 
305 struct __copy_move 
306 { 
307 template<typename _II, typename _OI> 
308 static _OI 
309 __copy_m(_II __first, _II __last, _OI __result) 
310 { 
311 for (; __first != __last; ++__result, (void)++__first) 
312 *__result = *__first; 
313 return __result; 
314 } 
315 }; 
316 
317#if __cplusplus >= 201103L 
318 template<typename _Category> 
319 struct __copy_move<true, false, _Category> 
320 { 
321 template<typename _II, typename _OI> 
322 static _OI 
323 __copy_m(_II __first, _II __last, _OI __result) 
324 { 
325 for (; __first != __last; ++__result, (void)++__first) 
326 *__result = std::move(*__first); 
327 return __result; 
328 } 
329 }; 
330#endif 
331 
332 template<> 
333 struct __copy_move<false, false, random_access_iterator_tag> 
334 { 
335 template<typename _II, typename _OI> 
336 static _OI 
337 __copy_m(_II __first, _II __last, _OI __result) 
338 { 
339 typedef typename iterator_traits<_II>::difference_type _Distance; 
340 for(_Distance __n = __last - __first; __n > 0; --__n) 
341 { 
342 *__result = *__first; 
343 ++__first; 
344 ++__result; 
345 } 
346 return __result; 
347 } 
348 }; 
349 
350#if __cplusplus >= 201103L 
351 template<> 
352 struct __copy_move<true, false, random_access_iterator_tag> 
353 { 
354 template<typename _II, typename _OI> 
355 static _OI 
356 __copy_m(_II __first, _II __last, _OI __result) 
357 { 
358 typedef typename iterator_traits<_II>::difference_type _Distance; 
359 for(_Distance __n = __last - __first; __n > 0; --__n) 
360 { 
361 *__result = std::move(*__first); 
362 ++__first; 
363 ++__result; 
364 } 
365 return __result; 
366 } 
367 }; 
368#endif 
369 
370 template<bool _IsMove> 
371 struct __copy_move<_IsMove, true, random_access_iterator_tag> 
372 { 
373 template<typename _Tp> 
374 static _Tp* 
375 __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) 
376 { 
377#if __cplusplus >= 201103L 
378 using __assignable = conditional<_IsMove, 
379 is_move_assignable<_Tp>, 
380 is_copy_assignable<_Tp>>; 
381 // trivial types can have deleted assignment 
382 static_assert( __assignable::type::value, "type is not assignable" ); 
383#endif 
384 const ptrdiff_t _Num = __last - __first; 
385 if (_Num) 
386 __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); 
387 return __result + _Num; 
388 } 
389 }; 
390 
391 template<bool _IsMove, typename _II, typename _OI> 
392 inline _OI 
393 __copy_move_a(_II __first, _II __last, _OI __result) 
394 { 
395 typedef typename iterator_traits<_II>::value_type _ValueTypeI; 
396 typedef typename iterator_traits<_OI>::value_type _ValueTypeO; 
397 typedef typename iterator_traits<_II>::iterator_category _Category; 
398 const bool __simple = (__is_trivially_copyable(_ValueTypeI) 
399 && __is_pointer<_II>::__value 
400 && __is_pointer<_OI>::__value 
401 && __are_same<_ValueTypeI, _ValueTypeO>::__value); 
402 
403 return std::__copy_move<_IsMove, __simple, 
404 _Category>::__copy_m(__first, __last, __result); 
405 } 
406 
407 // Helpers for streambuf iterators (either istream or ostream). 
408 // NB: avoid including <iosfwd>, relatively large. 
409 template<typename _CharT> 
410 struct char_traits; 
411 
412 template<typename _CharT, typename _Traits> 
413 class istreambuf_iterator; 
414 
415 template<typename _CharT, typename _Traits> 
416 class ostreambuf_iterator; 
417 
418 template<bool _IsMove, typename _CharT> 
419 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
420 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 
421 __copy_move_a2(_CharT*, _CharT*, 
422 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 
423 
424 template<bool _IsMove, typename _CharT> 
425 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
426 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 
427 __copy_move_a2(const _CharT*, const _CharT*, 
428 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 
429 
430 template<bool _IsMove, typename _CharT> 
431 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 
432 _CharT*>::__type 
433 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, 
434 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); 
435 
436 template<bool _IsMove, typename _II, typename _OI> 
437 inline _OI 
438 __copy_move_a2(_II __first, _II __last, _OI __result) 
439 { 
440 return std::__niter_wrap(__result, 
441 std::__copy_move_a<_IsMove>(std::__niter_base(__first), 
442 std::__niter_base(__last), 
443 std::__niter_base(__result))); 
444 } 
445 
446 /** 
447 * @brief Copies the range [first,last) into result. 
448 * @ingroup mutating_algorithms 
449 * @param __first An input iterator. 
450 * @param __last An input iterator. 
451 * @param __result An output iterator. 
452 * @return result + (first - last) 
453 * 
454 * This inline function will boil down to a call to @c memmove whenever 
455 * possible. Failing that, if random access iterators are passed, then the 
456 * loop count will be known (and therefore a candidate for compiler 
457 * optimizations such as unrolling). Result may not be contained within 
458 * [first,last); the copy_backward function should be used instead. 
459 * 
460 * Note that the end of the output range is permitted to be contained 
461 * within [first,last). 
462 */ 
463 template<typename _II, typename _OI> 
464 inline _OI 
465 copy(_II __first, _II __last, _OI __result) 
466 { 
467 // concept requirements 
468 __glibcxx_function_requires(_InputIteratorConcept<_II>) 
469 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 
470 typename iterator_traits<_II>::value_type>) 
471 __glibcxx_requires_can_increment_range(__first, __last, __result); 
472 
473 return std::__copy_move_a2<__is_move_iterator<_II>::__value> 
474 (std::__miter_base(__first), std::__miter_base(__last), __result); 
475 } 
476 
477#if __cplusplus >= 201103L 
478 /** 
479 * @brief Moves the range [first,last) into result. 
480 * @ingroup mutating_algorithms 
481 * @param __first An input iterator. 
482 * @param __last An input iterator. 
483 * @param __result An output iterator. 
484 * @return result + (first - last) 
485 * 
486 * This inline function will boil down to a call to @c memmove whenever 
487 * possible. Failing that, if random access iterators are passed, then the 
488 * loop count will be known (and therefore a candidate for compiler 
489 * optimizations such as unrolling). Result may not be contained within 
490 * [first,last); the move_backward function should be used instead. 
491 * 
492 * Note that the end of the output range is permitted to be contained 
493 * within [first,last). 
494 */ 
495 template<typename _II, typename _OI> 
496 inline _OI 
497 move(_II __first, _II __last, _OI __result) 
498 { 
499 // concept requirements 
500 __glibcxx_function_requires(_InputIteratorConcept<_II>) 
501 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 
502 typename iterator_traits<_II>::value_type>) 
503 __glibcxx_requires_can_increment_range(__first, __last, __result); 
504 
505 return std::__copy_move_a2<true>(std::__miter_base(__first), 
506 std::__miter_base(__last), __result); 
507 } 
508 
509#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) 
510#else 
511#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) 
512#endif 
513 
514 template<bool, bool, typename> 
515 struct __copy_move_backward 
516 { 
517 template<typename _BI1, typename _BI2> 
518 static _BI2 
519 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 
520 { 
521 while (__first != __last) 
522 *--__result = *--__last; 
523 return __result; 
524 } 
525 }; 
526 
527#if __cplusplus >= 201103L 
528 template<typename _Category> 
529 struct __copy_move_backward<true, false, _Category> 
530 { 
531 template<typename _BI1, typename _BI2> 
532 static _BI2 
533 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 
534 { 
535 while (__first != __last) 
536 *--__result = std::move(*--__last); 
537 return __result; 
538 } 
539 }; 
540#endif 
541 
542 template<> 
543 struct __copy_move_backward<false, false, random_access_iterator_tag> 
544 { 
545 template<typename _BI1, typename _BI2> 
546 static _BI2 
547 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 
548 { 
549 typename iterator_traits<_BI1>::difference_type __n; 
550 for (__n = __last - __first; __n > 0; --__n) 
551 *--__result = *--__last; 
552 return __result; 
553 } 
554 }; 
555 
556#if __cplusplus >= 201103L 
557 template<> 
558 struct __copy_move_backward<true, false, random_access_iterator_tag> 
559 { 
560 template<typename _BI1, typename _BI2> 
561 static _BI2 
562 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 
563 { 
564 typename iterator_traits<_BI1>::difference_type __n; 
565 for (__n = __last - __first; __n > 0; --__n) 
566 *--__result = std::move(*--__last); 
567 return __result; 
568 } 
569 }; 
570#endif 
571 
572 template<bool _IsMove> 
573 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> 
574 { 
575 template<typename _Tp> 
576 static _Tp* 
577 __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) 
578 { 
579#if __cplusplus >= 201103L 
580 using __assignable = conditional<_IsMove, 
581 is_move_assignable<_Tp>, 
582 is_copy_assignable<_Tp>>; 
583 // trivial types can have deleted assignment 
584 static_assert( __assignable::type::value, "type is not assignable" ); 
585#endif 
586 const ptrdiff_t _Num = __last - __first; 
587 if (_Num) 
588 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 
589 return __result - _Num; 
590 } 
591 }; 
592 
593 template<bool _IsMove, typename _BI1, typename _BI2> 
594 inline _BI2 
595 __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) 
596 { 
597 typedef typename iterator_traits<_BI1>::value_type _ValueType1; 
598 typedef typename iterator_traits<_BI2>::value_type _ValueType2; 
599 typedef typename iterator_traits<_BI1>::iterator_category _Category; 
600 const bool __simple = (__is_trivially_copyable(_ValueType1) 
601 && __is_pointer<_BI1>::__value 
602 && __is_pointer<_BI2>::__value 
603 && __are_same<_ValueType1, _ValueType2>::__value); 
604 
605 return std::__copy_move_backward<_IsMove, __simple, 
606 _Category>::__copy_move_b(__first, 
607 __last, 
608 __result); 
609 } 
610 
611 template<bool _IsMove, typename _BI1, typename _BI2> 
612 inline _BI2 
613 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) 
614 { 
615 return std::__niter_wrap(__result, 
616 std::__copy_move_backward_a<_IsMove> 
617 (std::__niter_base(__first), std::__niter_base(__last), 
618 std::__niter_base(__result))); 
619 } 
620 
621 /** 
622 * @brief Copies the range [first,last) into result. 
623 * @ingroup mutating_algorithms 
624 * @param __first A bidirectional iterator. 
625 * @param __last A bidirectional iterator. 
626 * @param __result A bidirectional iterator. 
627 * @return result - (first - last) 
628 * 
629 * The function has the same effect as copy, but starts at the end of the 
630 * range and works its way to the start, returning the start of the result. 
631 * This inline function will boil down to a call to @c memmove whenever 
632 * possible. Failing that, if random access iterators are passed, then the 
633 * loop count will be known (and therefore a candidate for compiler 
634 * optimizations such as unrolling). 
635 * 
636 * Result may not be in the range (first,last]. Use copy instead. Note 
637 * that the start of the output range may overlap [first,last). 
638 */ 
639 template<typename _BI1, typename _BI2> 
640 inline _BI2 
641 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 
642 { 
643 // concept requirements 
644 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 
645 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 
646 __glibcxx_function_requires(_ConvertibleConcept< 
647 typename iterator_traits<_BI1>::value_type, 
648 typename iterator_traits<_BI2>::value_type>) 
649 __glibcxx_requires_can_decrement_range(__first, __last, __result); 
650 
651 return std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> 
652 (std::__miter_base(__first), std::__miter_base(__last), __result); 
653 } 
654 
655#if __cplusplus >= 201103L 
656 /** 
657 * @brief Moves the range [first,last) into result. 
658 * @ingroup mutating_algorithms 
659 * @param __first A bidirectional iterator. 
660 * @param __last A bidirectional iterator. 
661 * @param __result A bidirectional iterator. 
662 * @return result - (first - last) 
663 * 
664 * The function has the same effect as move, but starts at the end of the 
665 * range and works its way to the start, returning the start of the result. 
666 * This inline function will boil down to a call to @c memmove whenever 
667 * possible. Failing that, if random access iterators are passed, then the 
668 * loop count will be known (and therefore a candidate for compiler 
669 * optimizations such as unrolling). 
670 * 
671 * Result may not be in the range (first,last]. Use move instead. Note 
672 * that the start of the output range may overlap [first,last). 
673 */ 
674 template<typename _BI1, typename _BI2> 
675 inline _BI2 
676 move_backward(_BI1 __first, _BI1 __last, _BI2 __result) 
677 { 
678 // concept requirements 
679 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 
680 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 
681 __glibcxx_function_requires(_ConvertibleConcept< 
682 typename iterator_traits<_BI1>::value_type, 
683 typename iterator_traits<_BI2>::value_type>) 
684 __glibcxx_requires_can_decrement_range(__first, __last, __result); 
685 
686 return std::__copy_move_backward_a2<true>(std::__miter_base(__first), 
687 std::__miter_base(__last), 
688 __result); 
689 } 
690 
691#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) 
692#else 
693#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) 
694#endif 
695 
696 template<typename _ForwardIterator, typename _Tp> 
697 inline typename 
698 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type 
699 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 
700 const _Tp& __value) 
701 { 
702 for (; __first != __last; ++__first) 
703 *__first = __value; 
704 } 
705 
706 template<typename _ForwardIterator, typename _Tp> 
707 inline typename 
708 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type 
709 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 
710 const _Tp& __value) 
711 { 
712 const _Tp __tmp = __value; 
713 for (; __first != __last; ++__first) 
714 *__first = __tmp; 
715 } 
716 
717 // Specialization: for char types we can use memset. 
718 template<typename _Tp> 
719 inline typename 
720 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type 
721 __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) 
722 { 
723 const _Tp __tmp = __c; 
724 if (const size_t __len = __last - __first) 
725 __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); 
726 } 
727 
728 /** 
729 * @brief Fills the range [first,last) with copies of value. 
730 * @ingroup mutating_algorithms 
731 * @param __first A forward iterator. 
732 * @param __last A forward iterator. 
733 * @param __value A reference-to-const of arbitrary type. 
734 * @return Nothing. 
735 * 
736 * This function fills a range with copies of the same value. For char 
737 * types filling contiguous areas of memory, this becomes an inline call 
738 * to @c memset or @c wmemset. 
739 */ 
740 template<typename _ForwardIterator, typename _Tp> 
741 inline void 
742 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 
743 { 
744 // concept requirements 
745 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 
746 _ForwardIterator>) 
747 __glibcxx_requires_valid_range(__first, __last); 
748 
749 std::__fill_a(std::__niter_base(__first), std::__niter_base(__last), 
750 __value); 
751 } 
752 
753 template<typename _OutputIterator, typename _Size, typename _Tp> 
754 inline typename 
755 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type 
756 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 
757 { 
758 for (__decltype(__n + 0) __niter = __n; 
759 __niter > 0; --__niter, (void) ++__first) 
760 *__first = __value; 
761 return __first; 
762 } 
763 
764 template<typename _OutputIterator, typename _Size, typename _Tp> 
765 inline typename 
766 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type 
767 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 
768 { 
769 const _Tp __tmp = __value; 
770 for (__decltype(__n + 0) __niter = __n; 
771 __niter > 0; --__niter, (void) ++__first) 
772 *__first = __tmp; 
773 return __first; 
774 } 
775 
776 template<typename _Size, typename _Tp> 
777 inline typename 
778 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type 
779 __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) 
780 { 
781 std::__fill_a(__first, __first + __n, __c); 
782 return __first + __n; 
783 } 
784 
785 /** 
786 * @brief Fills the range [first,first+n) with copies of value. 
787 * @ingroup mutating_algorithms 
788 * @param __first An output iterator. 
789 * @param __n The count of copies to perform. 
790 * @param __value A reference-to-const of arbitrary type. 
791 * @return The iterator at first+n. 
792 * 
793 * This function fills a range with copies of the same value. For char 
794 * types filling contiguous areas of memory, this becomes an inline call 
795 * to @c memset or @ wmemset. 
796 * 
797 * _GLIBCXX_RESOLVE_LIB_DEFECTS 
798 * DR 865. More algorithms that throw away information 
799 */ 
800 template<typename _OI, typename _Size, typename _Tp> 
801 inline _OI 
802 fill_n(_OI __first, _Size __n, const _Tp& __value) 
803 { 
804 // concept requirements 
805 __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) 
806 __glibcxx_requires_can_increment(__first, __n); 
807 
808 return std::__niter_wrap(__first, 
809 std::__fill_n_a(std::__niter_base(__first), __n, __value)); 
810 } 
811 
812 template<bool _BoolType> 
813 struct __equal 
814 { 
815 template<typename _II1, typename _II2> 
816 static bool 
817 equal(_II1 __first1, _II1 __last1, _II2 __first2) 
818 { 
819 for (; __first1 != __last1; ++__first1, (void) ++__first2) 
820 if (!(*__first1 == *__first2)) 
821 return false; 
822 return true; 
823 } 
824 }; 
825 
826 template<> 
827 struct __equal<true> 
828 { 
829 template<typename _Tp> 
830 static bool 
831 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) 
832 { 
833 if (const size_t __len = (__last1 - __first1)) 
834 return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len); 
835 return true; 
836 } 
837 }; 
838 
839 template<typename _II1, typename _II2> 
840 inline bool 
841 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) 
842 { 
843 typedef typename iterator_traits<_II1>::value_type _ValueType1; 
844 typedef typename iterator_traits<_II2>::value_type _ValueType2; 
845 const bool __simple = ((__is_integer<_ValueType1>::__value 
846 || __is_pointer<_ValueType1>::__value) 
847 && __is_pointer<_II1>::__value 
848 && __is_pointer<_II2>::__value 
849 && __are_same<_ValueType1, _ValueType2>::__value); 
850 
851 return std::__equal<__simple>::equal(__first1, __last1, __first2); 
852 } 
853 
854 template<typename, typename> 
855 struct __lc_rai 
856 { 
857 template<typename _II1, typename _II2> 
858 static _II1 
859 __newlast1(_II1, _II1 __last1, _II2, _II2) 
860 { return __last1; } 
861 
862 template<typename _II> 
863 static bool 
864 __cnd2(_II __first, _II __last) 
865 { return __first != __last; } 
866 }; 
867 
868 template<> 
869 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> 
870 { 
871 template<typename _RAI1, typename _RAI2> 
872 static _RAI1 
873 __newlast1(_RAI1 __first1, _RAI1 __last1, 
874 _RAI2 __first2, _RAI2 __last2) 
875 { 
876 const typename iterator_traits<_RAI1>::difference_type 
877 __diff1 = __last1 - __first1; 
878 const typename iterator_traits<_RAI2>::difference_type 
879 __diff2 = __last2 - __first2; 
880 return __diff2 < __diff1 ? __first1 + __diff2 : __last1; 
881 } 
882 
883 template<typename _RAI> 
884 static bool 
885 __cnd2(_RAI, _RAI) 
886 { return true; } 
887 }; 
888 
889 template<typename _II1, typename _II2, typename _Compare> 
890 bool 
891 __lexicographical_compare_impl(_II1 __first1, _II1 __last1, 
892 _II2 __first2, _II2 __last2, 
893 _Compare __comp) 
894 { 
895 typedef typename iterator_traits<_II1>::iterator_category _Category1; 
896 typedef typename iterator_traits<_II2>::iterator_category _Category2; 
897 typedef std::__lc_rai<_Category1, _Category2> __rai_type; 
898 
899 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); 
900 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); 
901 ++__first1, (void)++__first2) 
902 { 
903 if (__comp(__first1, __first2)) 
904 return true; 
905 if (__comp(__first2, __first1)) 
906 return false; 
907 } 
908 return __first1 == __last1 && __first2 != __last2; 
909 } 
910 
911 template<bool _BoolType> 
912 struct __lexicographical_compare 
913 { 
914 template<typename _II1, typename _II2> 
915 static bool __lc(_II1, _II1, _II2, _II2); 
916 }; 
917 
918 template<bool _BoolType> 
919 template<typename _II1, typename _II2> 
920 bool 
921 __lexicographical_compare<_BoolType>:: 
922 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 
923 { 
924 return std::__lexicographical_compare_impl(__first1, __last1, 
925 __first2, __last2, 
926 __gnu_cxx::__ops::__iter_less_iter()); 
927 } 
928 
929 template<> 
930 struct __lexicographical_compare<true> 
931 { 
932 template<typename _Tp, typename _Up> 
933 static bool 
934 __lc(const _Tp* __first1, const _Tp* __last1, 
935 const _Up* __first2, const _Up* __last2) 
936 { 
937 const size_t __len1 = __last1 - __first1; 
938 const size_t __len2 = __last2 - __first2; 
939 if (const size_t __len = std::min(__len1, __len2)) 
940 if (int __result = __builtin_memcmp(__first1, __first2, __len)) 
941 return __result < 0; 
942 return __len1 < __len2; 
943 } 
944 }; 
945 
946 template<typename _II1, typename _II2> 
947 inline bool 
948 __lexicographical_compare_aux(_II1 __first1, _II1 __last1, 
949 _II2 __first2, _II2 __last2) 
950 { 
951 typedef typename iterator_traits<_II1>::value_type _ValueType1; 
952 typedef typename iterator_traits<_II2>::value_type _ValueType2; 
953 const bool __simple = 
954 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value 
955 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed 
956 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed 
957 && __is_pointer<_II1>::__value 
958 && __is_pointer<_II2>::__value); 
959 
960 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, 
961 __first2, __last2); 
962 } 
963 
964 template<typename _ForwardIterator, typename _Tp, typename _Compare> 
965 _ForwardIterator 
966 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, 
967 const _Tp& __val, _Compare __comp) 
968 { 
969 typedef typename iterator_traits<_ForwardIterator>::difference_type 
970 _DistanceType; 
971 
972 _DistanceType __len = std::distance(__first, __last); 
973 
974 while (__len > 0) 
975 { 
976 _DistanceType __half = __len >> 1; 
977 _ForwardIterator __middle = __first; 
978 std::advance(__middle, __half); 
979 if (__comp(__middle, __val)) 
980 { 
981 __first = __middle; 
982 ++__first; 
983 __len = __len - __half - 1; 
984 } 
985 else 
986 __len = __half; 
987 } 
988 return __first; 
989 } 
990 
991 /** 
992 * @brief Finds the first position in which @a val could be inserted 
993 * without changing the ordering. 
994 * @param __first An iterator. 
995 * @param __last Another iterator. 
996 * @param __val The search term. 
997 * @return An iterator pointing to the first element <em>not less 
998 * than</em> @a val, or end() if every element is less than 
999 * @a val. 
1000 * @ingroup binary_search_algorithms 
1001 */ 
1002 template<typename _ForwardIterator, typename _Tp> 
1003 inline _ForwardIterator 
1004 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 
1005 const _Tp& __val) 
1006 { 
1007 // concept requirements 
1008 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 
1009 __glibcxx_function_requires(_LessThanOpConcept< 
1010 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 
1011 __glibcxx_requires_partitioned_lower(__first, __last, __val); 
1012 
1013 return std::__lower_bound(__first, __last, __val, 
1014 __gnu_cxx::__ops::__iter_less_val()); 
1015 } 
1016 
1017 /// This is a helper function for the sort routines and for random.tcc. 
1018 // Precondition: __n > 0. 
1019 inline _GLIBCXX_CONSTEXPR int 
1020 __lg(int __n) 
1021 { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } 
1022 
1023 inline _GLIBCXX_CONSTEXPR unsigned 
1024 __lg(unsigned __n) 
1025 { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } 
1026 
1027 inline _GLIBCXX_CONSTEXPR long 
1028 __lg(long __n) 
1029 { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } 
1030 
1031 inline _GLIBCXX_CONSTEXPR unsigned long 
1032 __lg(unsigned long __n) 
1033 { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } 
1034 
1035 inline _GLIBCXX_CONSTEXPR long long 
1036 __lg(long long __n) 
1037 { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } 
1038 
1039 inline _GLIBCXX_CONSTEXPR unsigned long long 
1040 __lg(unsigned long long __n) 
1041 { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } 
1042 
1043_GLIBCXX_BEGIN_NAMESPACE_ALGO 
1044 
1045 /** 
1046 * @brief Tests a range for element-wise equality. 
1047 * @ingroup non_mutating_algorithms 
1048 * @param __first1 An input iterator. 
1049 * @param __last1 An input iterator. 
1050 * @param __first2 An input iterator. 
1051 * @return A boolean true or false. 
1052 * 
1053 * This compares the elements of two ranges using @c == and returns true or 
1054 * false depending on whether all of the corresponding elements of the 
1055 * ranges are equal. 
1056 */ 
1057 template<typename _II1, typename _II2> 
1058 inline bool 
1059 equal(_II1 __first1, _II1 __last1, _II2 __first2) 
1060 { 
1061 // concept requirements 
1062 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 
1063 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 
1064 __glibcxx_function_requires(_EqualOpConcept< 
1065 typename iterator_traits<_II1>::value_type, 
1066 typename iterator_traits<_II2>::value_type>) 
1067 __glibcxx_requires_can_increment_range(__first1, __last1, __first2); 
1068 
1069 return std::__equal_aux(std::__niter_base(__first1), 
1070 std::__niter_base(__last1), 
1071 std::__niter_base(__first2)); 
1072 } 
1073 
1074 /** 
1075 * @brief Tests a range for element-wise equality. 
1076 * @ingroup non_mutating_algorithms 
1077 * @param __first1 An input iterator. 
1078 * @param __last1 An input iterator. 
1079 * @param __first2 An input iterator. 
1080 * @param __binary_pred A binary predicate @link functors 
1081 * functor@endlink. 
1082 * @return A boolean true or false. 
1083 * 
1084 * This compares the elements of two ranges using the binary_pred 
1085 * parameter, and returns true or 
1086 * false depending on whether all of the corresponding elements of the 
1087 * ranges are equal. 
1088 */ 
1089 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 
1090 inline bool 
1091 equal(_IIter1 __first1, _IIter1 __last1, 
1092 _IIter2 __first2, _BinaryPredicate __binary_pred) 
1093 { 
1094 // concept requirements 
1095 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 
1096 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 
1097 __glibcxx_requires_valid_range(__first1, __last1); 
1098 
1099 for (; __first1 != __last1; ++__first1, (void)++__first2) 
1100 if (!bool(__binary_pred(*__first1, *__first2))) 
1101 return false; 
1102 return true; 
1103 } 
1104 
1105#if __cplusplus >= 201103L 
1106 // 4-iterator version of std::equal<It1, It2> for use in C++11. 
1107 template<typename _II1, typename _II2> 
1108 inline bool 
1109 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 
1110 { 
1111 using _RATag = random_access_iterator_tag; 
1112 using _Cat1 = typename iterator_traits<_II1>::iterator_category; 
1113 using _Cat2 = typename iterator_traits<_II2>::iterator_category; 
1114 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 
1115 if (_RAIters()) 
1116 { 
1117 auto __d1 = std::distance(__first1, __last1); 
1118 auto __d2 = std::distance(__first2, __last2); 
1119 if (__d1 != __d2) 
1120 return false; 
1121 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2); 
1122 } 
1123 
1124 for (; __first1 != __last1 && __first2 != __last2; 
1125 ++__first1, (void)++__first2) 
1126 if (!(*__first1 == *__first2)) 
1127 return false; 
1128 return __first1 == __last1 && __first2 == __last2; 
1129 } 
1130 
1131 // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11. 
1132 template<typename _II1, typename _II2, typename _BinaryPredicate> 
1133 inline bool 
1134 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, 
1135 _BinaryPredicate __binary_pred) 
1136 { 
1137 using _RATag = random_access_iterator_tag; 
1138 using _Cat1 = typename iterator_traits<_II1>::iterator_category; 
1139 using _Cat2 = typename iterator_traits<_II2>::iterator_category; 
1140 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 
1141 if (_RAIters()) 
1142 { 
1143 auto __d1 = std::distance(__first1, __last1); 
1144 auto __d2 = std::distance(__first2, __last2); 
1145 if (__d1 != __d2) 
1146 return false; 
1147 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, 
1148 __binary_pred); 
1149 } 
1150 
1151 for (; __first1 != __last1 && __first2 != __last2; 
1152 ++__first1, (void)++__first2) 
1153 if (!bool(__binary_pred(*__first1, *__first2))) 
1154 return false; 
1155 return __first1 == __last1 && __first2 == __last2; 
1156 } 
1157#endif // C++11 
1158 
1159#if __cplusplus > 201103L 
1160 
1161#define __cpp_lib_robust_nonmodifying_seq_ops 201304 
1162 
1163 /** 
1164 * @brief Tests a range for element-wise equality. 
1165 * @ingroup non_mutating_algorithms 
1166 * @param __first1 An input iterator. 
1167 * @param __last1 An input iterator. 
1168 * @param __first2 An input iterator. 
1169 * @param __last2 An input iterator. 
1170 * @return A boolean true or false. 
1171 * 
1172 * This compares the elements of two ranges using @c == and returns true or 
1173 * false depending on whether all of the corresponding elements of the 
1174 * ranges are equal. 
1175 */ 
1176 template<typename _II1, typename _II2> 
1177 inline bool 
1178 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 
1179 { 
1180 // concept requirements 
1181 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 
1182 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 
1183 __glibcxx_function_requires(_EqualOpConcept< 
1184 typename iterator_traits<_II1>::value_type, 
1185 typename iterator_traits<_II2>::value_type>) 
1186 __glibcxx_requires_valid_range(__first1, __last1); 
1187 __glibcxx_requires_valid_range(__first2, __last2); 
1188 
1189 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2); 
1190 } 
1191 
1192 /** 
1193 * @brief Tests a range for element-wise equality. 
1194 * @ingroup non_mutating_algorithms 
1195 * @param __first1 An input iterator. 
1196 * @param __last1 An input iterator. 
1197 * @param __first2 An input iterator. 
1198 * @param __last2 An input iterator. 
1199 * @param __binary_pred A binary predicate @link functors 
1200 * functor@endlink. 
1201 * @return A boolean true or false. 
1202 * 
1203 * This compares the elements of two ranges using the binary_pred 
1204 * parameter, and returns true or 
1205 * false depending on whether all of the corresponding elements of the 
1206 * ranges are equal. 
1207 */ 
1208 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 
1209 inline bool 
1210 equal(_IIter1 __first1, _IIter1 __last1, 
1211 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred) 
1212 { 
1213 // concept requirements 
1214 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 
1215 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 
1216 __glibcxx_requires_valid_range(__first1, __last1); 
1217 __glibcxx_requires_valid_range(__first2, __last2); 
1218 
1219 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2, 
1220 __binary_pred); 
1221 } 
1222#endif // C++14 
1223 
1224 /** 
1225 * @brief Performs @b dictionary comparison on ranges. 
1226 * @ingroup sorting_algorithms 
1227 * @param __first1 An input iterator. 
1228 * @param __last1 An input iterator. 
1229 * @param __first2 An input iterator. 
1230 * @param __last2 An input iterator. 
1231 * @return A boolean true or false. 
1232 * 
1233 * <em>Returns true if the sequence of elements defined by the range 
1234 * [first1,last1) is lexicographically less than the sequence of elements 
1235 * defined by the range [first2,last2). Returns false otherwise.</em> 
1236 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 
1237 * then this is an inline call to @c memcmp. 
1238 */ 
1239 template<typename _II1, typename _II2> 
1240 inline bool 
1241 lexicographical_compare(_II1 __first1, _II1 __last1, 
1242 _II2 __first2, _II2 __last2) 
1243 { 
1244#ifdef _GLIBCXX_CONCEPT_CHECKS 
1245 // concept requirements 
1246 typedef typename iterator_traits<_II1>::value_type _ValueType1; 
1247 typedef typename iterator_traits<_II2>::value_type _ValueType2; 
1248#endif 
1249 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 
1250 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 
1251 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 
1252 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 
1253 __glibcxx_requires_valid_range(__first1, __last1); 
1254 __glibcxx_requires_valid_range(__first2, __last2); 
1255 
1256 return std::__lexicographical_compare_aux(std::__niter_base(__first1), 
1257 std::__niter_base(__last1), 
1258 std::__niter_base(__first2), 
1259 std::__niter_base(__last2)); 
1260 } 
1261 
1262 /** 
1263 * @brief Performs @b dictionary comparison on ranges. 
1264 * @ingroup sorting_algorithms 
1265 * @param __first1 An input iterator. 
1266 * @param __last1 An input iterator. 
1267 * @param __first2 An input iterator. 
1268 * @param __last2 An input iterator. 
1269 * @param __comp A @link comparison_functors comparison functor@endlink. 
1270 * @return A boolean true or false. 
1271 * 
1272 * The same as the four-parameter @c lexicographical_compare, but uses the 
1273 * comp parameter instead of @c <. 
1274 */ 
1275 template<typename _II1, typename _II2, typename _Compare> 
1276 inline bool 
1277 lexicographical_compare(_II1 __first1, _II1 __last1, 
1278 _II2 __first2, _II2 __last2, _Compare __comp) 
1279 { 
1280 // concept requirements 
1281 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 
1282 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 
1283 __glibcxx_requires_valid_range(__first1, __last1); 
1284 __glibcxx_requires_valid_range(__first2, __last2); 
1285 
1286 return std::__lexicographical_compare_impl 
1287 (__first1, __last1, __first2, __last2, 
1288 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 
1289 } 
1290 
1291 template<typename _InputIterator1, typename _InputIterator2, 
1292 typename _BinaryPredicate> 
1293 pair<_InputIterator1, _InputIterator2> 
1294 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 
1295 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 
1296 { 
1297 while (__first1 != __last1 && __binary_pred(__first1, __first2)) 
1298 { 
1299 ++__first1; 
1300 ++__first2; 
1301 } 
1302 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 
1303 } 
1304 
1305 /** 
1306 * @brief Finds the places in ranges which don't match. 
1307 * @ingroup non_mutating_algorithms 
1308 * @param __first1 An input iterator. 
1309 * @param __last1 An input iterator. 
1310 * @param __first2 An input iterator. 
1311 * @return A pair of iterators pointing to the first mismatch. 
1312 * 
1313 * This compares the elements of two ranges using @c == and returns a pair 
1314 * of iterators. The first iterator points into the first range, the 
1315 * second iterator points into the second range, and the elements pointed 
1316 * to by the iterators are not equal. 
1317 */ 
1318 template<typename _InputIterator1, typename _InputIterator2> 
1319 inline pair<_InputIterator1, _InputIterator2> 
1320 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 
1321 _InputIterator2 __first2) 
1322 { 
1323 // concept requirements 
1324 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 
1325 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 
1326 __glibcxx_function_requires(_EqualOpConcept< 
1327 typename iterator_traits<_InputIterator1>::value_type, 
1328 typename iterator_traits<_InputIterator2>::value_type>) 
1329 __glibcxx_requires_valid_range(__first1, __last1); 
1330 
1331 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 
1332 __gnu_cxx::__ops::__iter_equal_to_iter()); 
1333 } 
1334 
1335 /** 
1336 * @brief Finds the places in ranges which don't match. 
1337 * @ingroup non_mutating_algorithms 
1338 * @param __first1 An input iterator. 
1339 * @param __last1 An input iterator. 
1340 * @param __first2 An input iterator. 
1341 * @param __binary_pred A binary predicate @link functors 
1342 * functor@endlink. 
1343 * @return A pair of iterators pointing to the first mismatch. 
1344 * 
1345 * This compares the elements of two ranges using the binary_pred 
1346 * parameter, and returns a pair 
1347 * of iterators. The first iterator points into the first range, the 
1348 * second iterator points into the second range, and the elements pointed 
1349 * to by the iterators are not equal. 
1350 */ 
1351 template<typename _InputIterator1, typename _InputIterator2, 
1352 typename _BinaryPredicate> 
1353 inline pair<_InputIterator1, _InputIterator2> 
1354 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 
1355 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 
1356 { 
1357 // concept requirements 
1358 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 
1359 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 
1360 __glibcxx_requires_valid_range(__first1, __last1); 
1361 
1362 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 
1363 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 
1364 } 
1365 
1366#if __cplusplus > 201103L 
1367 
1368 template<typename _InputIterator1, typename _InputIterator2, 
1369 typename _BinaryPredicate> 
1370 pair<_InputIterator1, _InputIterator2> 
1371 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 
1372 _InputIterator2 __first2, _InputIterator2 __last2, 
1373 _BinaryPredicate __binary_pred) 
1374 { 
1375 while (__first1 != __last1 && __first2 != __last2 
1376 && __binary_pred(__first1, __first2)) 
1377 { 
1378 ++__first1; 
1379 ++__first2; 
1380 } 
1381 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 
1382 } 
1383 
1384 /** 
1385 * @brief Finds the places in ranges which don't match. 
1386 * @ingroup non_mutating_algorithms 
1387 * @param __first1 An input iterator. 
1388 * @param __last1 An input iterator. 
1389 * @param __first2 An input iterator. 
1390 * @param __last2 An input iterator. 
1391 * @return A pair of iterators pointing to the first mismatch. 
1392 * 
1393 * This compares the elements of two ranges using @c == and returns a pair 
1394 * of iterators. The first iterator points into the first range, the 
1395 * second iterator points into the second range, and the elements pointed 
1396 * to by the iterators are not equal. 
1397 */ 
1398 template<typename _InputIterator1, typename _InputIterator2> 
1399 inline pair<_InputIterator1, _InputIterator2> 
1400 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 
1401 _InputIterator2 __first2, _InputIterator2 __last2) 
1402 { 
1403 // concept requirements 
1404 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 
1405 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 
1406 __glibcxx_function_requires(_EqualOpConcept< 
1407 typename iterator_traits<_InputIterator1>::value_type, 
1408 typename iterator_traits<_InputIterator2>::value_type>) 
1409 __glibcxx_requires_valid_range(__first1, __last1); 
1410 __glibcxx_requires_valid_range(__first2, __last2); 
1411 
1412 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 
1413 __gnu_cxx::__ops::__iter_equal_to_iter()); 
1414 } 
1415 
1416 /** 
1417 * @brief Finds the places in ranges which don't match. 
1418 * @ingroup non_mutating_algorithms 
1419 * @param __first1 An input iterator. 
1420 * @param __last1 An input iterator. 
1421 * @param __first2 An input iterator. 
1422 * @param __last2 An input iterator. 
1423 * @param __binary_pred A binary predicate @link functors 
1424 * functor@endlink. 
1425 * @return A pair of iterators pointing to the first mismatch. 
1426 * 
1427 * This compares the elements of two ranges using the binary_pred 
1428 * parameter, and returns a pair 
1429 * of iterators. The first iterator points into the first range, the 
1430 * second iterator points into the second range, and the elements pointed 
1431 * to by the iterators are not equal. 
1432 */ 
1433 template<typename _InputIterator1, typename _InputIterator2, 
1434 typename _BinaryPredicate> 
1435 inline pair<_InputIterator1, _InputIterator2> 
1436 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 
1437 _InputIterator2 __first2, _InputIterator2 __last2, 
1438 _BinaryPredicate __binary_pred) 
1439 { 
1440 // concept requirements 
1441 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 
1442 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 
1443 __glibcxx_requires_valid_range(__first1, __last1); 
1444 __glibcxx_requires_valid_range(__first2, __last2); 
1445 
1446 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 
1447 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 
1448 } 
1449#endif 
1450 
1451_GLIBCXX_END_NAMESPACE_ALGO 
1452_GLIBCXX_END_NAMESPACE_VERSION 
1453} // namespace std 
1454 
1455// NB: This file is included within many other C++ includes, as a way 
1456// of getting the base algorithms. So, make sure that parallel bits 
1457// come in too if requested. 
1458#ifdef _GLIBCXX_PARALLEL 
1459# include <parallel/algobase.h> 
1460#endif 
1461 
1462#endif 
1463