Branch data Line data Source code
1 : : // Core algorithmic facilities -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001-2023 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 : : #if __cplusplus >= 201402L
76 : : # include <bit> // std::__bit_width
77 : : #endif
78 : : #if __cplusplus >= 202002L
79 : : # include <compare>
80 : : #endif
81 : :
82 : : namespace std _GLIBCXX_VISIBILITY(default)
83 : : {
84 : : _GLIBCXX_BEGIN_NAMESPACE_VERSION
85 : :
86 : : /*
87 : : * A constexpr wrapper for __builtin_memcmp.
88 : : * @param __num The number of elements of type _Tp (not bytes).
89 : : */
90 : : template<typename _Tp, typename _Up>
91 : : _GLIBCXX14_CONSTEXPR
92 : : inline int
93 : : __memcmp(const _Tp* __first1, const _Up* __first2, size_t __num)
94 : : {
95 : : #if __cplusplus >= 201103L
96 : : static_assert(sizeof(_Tp) == sizeof(_Up), "can be compared with memcmp");
97 : : #endif
98 : : #ifdef __cpp_lib_is_constant_evaluated
99 : : if (std::is_constant_evaluated())
100 : : {
101 : : for(; __num > 0; ++__first1, ++__first2, --__num)
102 : : if (*__first1 != *__first2)
103 : : return *__first1 < *__first2 ? -1 : 1;
104 : : return 0;
105 : : }
106 : : else
107 : : #endif
108 : : return __builtin_memcmp(__first1, __first2, sizeof(_Tp) * __num);
109 : : }
110 : :
111 : : #if __cplusplus < 201103L
112 : : // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
113 : : // nutshell, we are partially implementing the resolution of DR 187,
114 : : // when it's safe, i.e., the value_types are equal.
115 : : template<bool _BoolType>
116 : : struct __iter_swap
117 : : {
118 : : template<typename _ForwardIterator1, typename _ForwardIterator2>
119 : : static void
120 : : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
121 : : {
122 : : typedef typename iterator_traits<_ForwardIterator1>::value_type
123 : : _ValueType1;
124 : : _ValueType1 __tmp = *__a;
125 : : *__a = *__b;
126 : : *__b = __tmp;
127 : : }
128 : : };
129 : :
130 : : template<>
131 : : struct __iter_swap<true>
132 : : {
133 : : template<typename _ForwardIterator1, typename _ForwardIterator2>
134 : : static void
135 : : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
136 : : {
137 : : swap(*__a, *__b);
138 : : }
139 : : };
140 : : #endif // C++03
141 : :
142 : : /**
143 : : * @brief Swaps the contents of two iterators.
144 : : * @ingroup mutating_algorithms
145 : : * @param __a An iterator.
146 : : * @param __b Another iterator.
147 : : * @return Nothing.
148 : : *
149 : : * This function swaps the values pointed to by two iterators, not the
150 : : * iterators themselves.
151 : : */
152 : : template<typename _ForwardIterator1, typename _ForwardIterator2>
153 : : _GLIBCXX20_CONSTEXPR
154 : : inline void
155 : : iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
156 : : {
157 : : // concept requirements
158 : : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
159 : : _ForwardIterator1>)
160 : : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
161 : : _ForwardIterator2>)
162 : :
163 : : #if __cplusplus < 201103L
164 : : typedef typename iterator_traits<_ForwardIterator1>::value_type
165 : : _ValueType1;
166 : : typedef typename iterator_traits<_ForwardIterator2>::value_type
167 : : _ValueType2;
168 : :
169 : : __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
170 : : _ValueType2>)
171 : : __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
172 : : _ValueType1>)
173 : :
174 : : typedef typename iterator_traits<_ForwardIterator1>::reference
175 : : _ReferenceType1;
176 : : typedef typename iterator_traits<_ForwardIterator2>::reference
177 : : _ReferenceType2;
178 : : std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
179 : : && __are_same<_ValueType1&, _ReferenceType1>::__value
180 : : && __are_same<_ValueType2&, _ReferenceType2>::__value>::
181 : : iter_swap(__a, __b);
182 : : #else
183 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
184 : : // 187. iter_swap underspecified
185 : : swap(*__a, *__b);
186 : : #endif
187 : : }
188 : :
189 : : /**
190 : : * @brief Swap the elements of two sequences.
191 : : * @ingroup mutating_algorithms
192 : : * @param __first1 A forward iterator.
193 : : * @param __last1 A forward iterator.
194 : : * @param __first2 A forward iterator.
195 : : * @return An iterator equal to @p first2+(last1-first1).
196 : : *
197 : : * Swaps each element in the range @p [first1,last1) with the
198 : : * corresponding element in the range @p [first2,(last1-first1)).
199 : : * The ranges must not overlap.
200 : : */
201 : : template<typename _ForwardIterator1, typename _ForwardIterator2>
202 : : _GLIBCXX20_CONSTEXPR
203 : : _ForwardIterator2
204 : : swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
205 : : _ForwardIterator2 __first2)
206 : : {
207 : : // concept requirements
208 : : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
209 : : _ForwardIterator1>)
210 : : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
211 : : _ForwardIterator2>)
212 : : __glibcxx_requires_valid_range(__first1, __last1);
213 : :
214 : : for (; __first1 != __last1; ++__first1, (void)++__first2)
215 : : std::iter_swap(__first1, __first2);
216 : : return __first2;
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 : : * @return The lesser of the parameters.
225 : : *
226 : : * This is the simple classic generic implementation. It will work on
227 : : * temporary expressions, since they are only evaluated once, unlike a
228 : : * preprocessor macro.
229 : : */
230 : : template<typename _Tp>
231 : : _GLIBCXX14_CONSTEXPR
232 : : inline const _Tp&
233 : 32690 : min(const _Tp& __a, const _Tp& __b)
234 : : {
235 : : // concept requirements
236 : : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
237 : : //return __b < __a ? __b : __a;
238 : 32690 : if (__b < __a)
239 : 9558 : return __b;
240 : 23132 : return __a;
241 : : }
242 : :
243 : : /**
244 : : * @brief This does what you think it does.
245 : : * @ingroup sorting_algorithms
246 : : * @param __a A thing of arbitrary type.
247 : : * @param __b Another thing of arbitrary type.
248 : : * @return The greater of the parameters.
249 : : *
250 : : * This is the simple classic generic implementation. It will work on
251 : : * temporary expressions, since they are only evaluated once, unlike a
252 : : * preprocessor macro.
253 : : */
254 : : template<typename _Tp>
255 : : _GLIBCXX14_CONSTEXPR
256 : : inline const _Tp&
257 : 32384 : max(const _Tp& __a, const _Tp& __b)
258 : : {
259 : : // concept requirements
260 : : __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
261 : : //return __a < __b ? __b : __a;
262 : 32384 : if (__a < __b)
263 : 9152 : return __b;
264 : 23232 : return __a;
265 : : }
266 : :
267 : : /**
268 : : * @brief This does what you think it does.
269 : : * @ingroup sorting_algorithms
270 : : * @param __a A thing of arbitrary type.
271 : : * @param __b Another thing of arbitrary type.
272 : : * @param __comp A @link comparison_functors comparison functor@endlink.
273 : : * @return The lesser of the parameters.
274 : : *
275 : : * This will work on temporary expressions, since they are only evaluated
276 : : * once, unlike a preprocessor macro.
277 : : */
278 : : template<typename _Tp, typename _Compare>
279 : : _GLIBCXX14_CONSTEXPR
280 : : inline const _Tp&
281 : : min(const _Tp& __a, const _Tp& __b, _Compare __comp)
282 : : {
283 : : //return __comp(__b, __a) ? __b : __a;
284 : : if (__comp(__b, __a))
285 : : return __b;
286 : : return __a;
287 : : }
288 : :
289 : : /**
290 : : * @brief This does what you think it does.
291 : : * @ingroup sorting_algorithms
292 : : * @param __a A thing of arbitrary type.
293 : : * @param __b Another thing of arbitrary type.
294 : : * @param __comp A @link comparison_functors comparison functor@endlink.
295 : : * @return The greater of the parameters.
296 : : *
297 : : * This will work on temporary expressions, since they are only evaluated
298 : : * once, unlike a preprocessor macro.
299 : : */
300 : : template<typename _Tp, typename _Compare>
301 : : _GLIBCXX14_CONSTEXPR
302 : : inline const _Tp&
303 : : max(const _Tp& __a, const _Tp& __b, _Compare __comp)
304 : : {
305 : : //return __comp(__a, __b) ? __b : __a;
306 : : if (__comp(__a, __b))
307 : : return __b;
308 : : return __a;
309 : : }
310 : :
311 : : // Fallback implementation of the function in bits/stl_iterator.h used to
312 : : // remove the __normal_iterator wrapper. See copy, fill, ...
313 : : template<typename _Iterator>
314 : : _GLIBCXX20_CONSTEXPR
315 : : inline _Iterator
316 : : __niter_base(_Iterator __it)
317 : : _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
318 : : { return __it; }
319 : :
320 : : template<typename _Ite, typename _Seq>
321 : : _Ite
322 : : __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
323 : : std::random_access_iterator_tag>&);
324 : :
325 : : // Reverse the __niter_base transformation to get a
326 : : // __normal_iterator back again (this assumes that __normal_iterator
327 : : // is only used to wrap random access iterators, like pointers).
328 : : template<typename _From, typename _To>
329 : : _GLIBCXX20_CONSTEXPR
330 : : inline _From
331 : : __niter_wrap(_From __from, _To __res)
332 : : { return __from + (__res - std::__niter_base(__from)); }
333 : :
334 : : // No need to wrap, iterator already has the right type.
335 : : template<typename _Iterator>
336 : : _GLIBCXX20_CONSTEXPR
337 : : inline _Iterator
338 : : __niter_wrap(const _Iterator&, _Iterator __res)
339 : : { return __res; }
340 : :
341 : : // All of these auxiliary structs serve two purposes. (1) Replace
342 : : // calls to copy with memmove whenever possible. (Memmove, not memcpy,
343 : : // because the input and output ranges are permitted to overlap.)
344 : : // (2) If we're using random access iterators, then write the loop as
345 : : // a for loop with an explicit count.
346 : :
347 : : template<bool _IsMove, bool _IsSimple, typename _Category>
348 : : struct __copy_move
349 : : {
350 : : template<typename _II, typename _OI>
351 : : _GLIBCXX20_CONSTEXPR
352 : : static _OI
353 : : __copy_m(_II __first, _II __last, _OI __result)
354 : : {
355 : : for (; __first != __last; ++__result, (void)++__first)
356 : : *__result = *__first;
357 : : return __result;
358 : : }
359 : : };
360 : :
361 : : #if __cplusplus >= 201103L
362 : : template<typename _Category>
363 : : struct __copy_move<true, false, _Category>
364 : : {
365 : : template<typename _II, typename _OI>
366 : : _GLIBCXX20_CONSTEXPR
367 : : static _OI
368 : : __copy_m(_II __first, _II __last, _OI __result)
369 : : {
370 : : for (; __first != __last; ++__result, (void)++__first)
371 : : *__result = std::move(*__first);
372 : : return __result;
373 : : }
374 : : };
375 : : #endif
376 : :
377 : : template<>
378 : : struct __copy_move<false, false, random_access_iterator_tag>
379 : : {
380 : : template<typename _II, typename _OI>
381 : : _GLIBCXX20_CONSTEXPR
382 : : static _OI
383 : : __copy_m(_II __first, _II __last, _OI __result)
384 : : {
385 : : typedef typename iterator_traits<_II>::difference_type _Distance;
386 : : for(_Distance __n = __last - __first; __n > 0; --__n)
387 : : {
388 : : *__result = *__first;
389 : : ++__first;
390 : : ++__result;
391 : : }
392 : : return __result;
393 : : }
394 : :
395 : : template<typename _Tp, typename _Up>
396 : : static void
397 : : __assign_one(_Tp* __to, _Up* __from)
398 : : { *__to = *__from; }
399 : : };
400 : :
401 : : #if __cplusplus >= 201103L
402 : : template<>
403 : : struct __copy_move<true, false, random_access_iterator_tag>
404 : : {
405 : : template<typename _II, typename _OI>
406 : : _GLIBCXX20_CONSTEXPR
407 : : static _OI
408 : : __copy_m(_II __first, _II __last, _OI __result)
409 : : {
410 : : typedef typename iterator_traits<_II>::difference_type _Distance;
411 : : for(_Distance __n = __last - __first; __n > 0; --__n)
412 : : {
413 : : *__result = std::move(*__first);
414 : : ++__first;
415 : : ++__result;
416 : : }
417 : : return __result;
418 : : }
419 : :
420 : : template<typename _Tp, typename _Up>
421 : : static void
422 : : __assign_one(_Tp* __to, _Up* __from)
423 : : { *__to = std::move(*__from); }
424 : : };
425 : : #endif
426 : :
427 : : template<bool _IsMove>
428 : : struct __copy_move<_IsMove, true, random_access_iterator_tag>
429 : : {
430 : : template<typename _Tp, typename _Up>
431 : : _GLIBCXX20_CONSTEXPR
432 : : static _Up*
433 : : __copy_m(_Tp* __first, _Tp* __last, _Up* __result)
434 : : {
435 : : const ptrdiff_t _Num = __last - __first;
436 : : if (__builtin_expect(_Num > 1, true))
437 : : __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
438 : : else if (_Num == 1)
439 : : std::__copy_move<_IsMove, false, random_access_iterator_tag>::
440 : : __assign_one(__result, __first);
441 : : return __result + _Num;
442 : : }
443 : : };
444 : :
445 : : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
446 : :
447 : : template<typename _Tp, typename _Ref, typename _Ptr>
448 : : struct _Deque_iterator;
449 : :
450 : : struct _Bit_iterator;
451 : :
452 : : _GLIBCXX_END_NAMESPACE_CONTAINER
453 : :
454 : : #if _GLIBCXX_HOSTED
455 : : // Helpers for streambuf iterators (either istream or ostream).
456 : : // NB: avoid including <iosfwd>, relatively large.
457 : : template<typename _CharT>
458 : : struct char_traits;
459 : :
460 : : template<typename _CharT, typename _Traits>
461 : : class istreambuf_iterator;
462 : :
463 : : template<typename _CharT, typename _Traits>
464 : : class ostreambuf_iterator;
465 : :
466 : : template<bool _IsMove, typename _CharT>
467 : : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
468 : : ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
469 : : __copy_move_a2(_CharT*, _CharT*,
470 : : ostreambuf_iterator<_CharT, char_traits<_CharT> >);
471 : :
472 : : template<bool _IsMove, typename _CharT>
473 : : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
474 : : ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
475 : : __copy_move_a2(const _CharT*, const _CharT*,
476 : : ostreambuf_iterator<_CharT, char_traits<_CharT> >);
477 : :
478 : : template<bool _IsMove, typename _CharT>
479 : : typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
480 : : _CharT*>::__type
481 : : __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
482 : : istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
483 : :
484 : : template<bool _IsMove, typename _CharT>
485 : : typename __gnu_cxx::__enable_if<
486 : : __is_char<_CharT>::__value,
487 : : _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
488 : : __copy_move_a2(
489 : : istreambuf_iterator<_CharT, char_traits<_CharT> >,
490 : : istreambuf_iterator<_CharT, char_traits<_CharT> >,
491 : : _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
492 : : #endif // HOSTED
493 : :
494 : : template<bool _IsMove, typename _II, typename _OI>
495 : : _GLIBCXX20_CONSTEXPR
496 : : inline _OI
497 : : __copy_move_a2(_II __first, _II __last, _OI __result)
498 : : {
499 : : typedef typename iterator_traits<_II>::iterator_category _Category;
500 : : #ifdef __cpp_lib_is_constant_evaluated
501 : : if (std::is_constant_evaluated())
502 : : return std::__copy_move<_IsMove, false, _Category>::
503 : : __copy_m(__first, __last, __result);
504 : : #endif
505 : : return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
506 : : _Category>::__copy_m(__first, __last, __result);
507 : : }
508 : :
509 : : template<bool _IsMove,
510 : : typename _Tp, typename _Ref, typename _Ptr, typename _OI>
511 : : _OI
512 : : __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
513 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
514 : : _OI);
515 : :
516 : : template<bool _IsMove,
517 : : typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
518 : : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
519 : : __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
520 : : _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
521 : : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
522 : :
523 : : template<bool _IsMove, typename _II, typename _Tp>
524 : : typename __gnu_cxx::__enable_if<
525 : : __is_random_access_iter<_II>::__value,
526 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
527 : : __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
528 : :
529 : : template<bool _IsMove, typename _II, typename _OI>
530 : : _GLIBCXX20_CONSTEXPR
531 : : inline _OI
532 : : __copy_move_a1(_II __first, _II __last, _OI __result)
533 : : { return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
534 : :
535 : : template<bool _IsMove, typename _II, typename _OI>
536 : : _GLIBCXX20_CONSTEXPR
537 : : inline _OI
538 : : __copy_move_a(_II __first, _II __last, _OI __result)
539 : : {
540 : : return std::__niter_wrap(__result,
541 : : std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
542 : : std::__niter_base(__last),
543 : : std::__niter_base(__result)));
544 : : }
545 : :
546 : : template<bool _IsMove,
547 : : typename _Ite, typename _Seq, typename _Cat, typename _OI>
548 : : _OI
549 : : __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
550 : : const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
551 : : _OI);
552 : :
553 : : template<bool _IsMove,
554 : : typename _II, typename _Ite, typename _Seq, typename _Cat>
555 : : __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
556 : : __copy_move_a(_II, _II,
557 : : const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
558 : :
559 : : template<bool _IsMove,
560 : : typename _IIte, typename _ISeq, typename _ICat,
561 : : typename _OIte, typename _OSeq, typename _OCat>
562 : : ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
563 : : __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
564 : : const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
565 : : const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
566 : :
567 : : template<typename _InputIterator, typename _Size, typename _OutputIterator>
568 : : _GLIBCXX20_CONSTEXPR
569 : : _OutputIterator
570 : : __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
571 : : bool)
572 : : {
573 : : if (__n > 0)
574 : : {
575 : : while (true)
576 : : {
577 : : *__result = *__first;
578 : : ++__result;
579 : : if (--__n > 0)
580 : : ++__first;
581 : : else
582 : : break;
583 : : }
584 : : }
585 : : return __result;
586 : : }
587 : :
588 : : #if _GLIBCXX_HOSTED
589 : : template<typename _CharT, typename _Size>
590 : : typename __gnu_cxx::__enable_if<
591 : : __is_char<_CharT>::__value, _CharT*>::__type
592 : : __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
593 : : _Size, _CharT*, bool);
594 : :
595 : : template<typename _CharT, typename _Size>
596 : : typename __gnu_cxx::__enable_if<
597 : : __is_char<_CharT>::__value,
598 : : _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
599 : : __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
600 : : _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
601 : : bool);
602 : : #endif
603 : :
604 : : /**
605 : : * @brief Copies the range [first,last) into result.
606 : : * @ingroup mutating_algorithms
607 : : * @param __first An input iterator.
608 : : * @param __last An input iterator.
609 : : * @param __result An output iterator.
610 : : * @return result + (last - first)
611 : : *
612 : : * This inline function will boil down to a call to @c memmove whenever
613 : : * possible. Failing that, if random access iterators are passed, then the
614 : : * loop count will be known (and therefore a candidate for compiler
615 : : * optimizations such as unrolling). Result may not be contained within
616 : : * [first,last); the copy_backward function should be used instead.
617 : : *
618 : : * Note that the end of the output range is permitted to be contained
619 : : * within [first,last).
620 : : */
621 : : template<typename _II, typename _OI>
622 : : _GLIBCXX20_CONSTEXPR
623 : : inline _OI
624 : : copy(_II __first, _II __last, _OI __result)
625 : : {
626 : : // concept requirements
627 : : __glibcxx_function_requires(_InputIteratorConcept<_II>)
628 : : __glibcxx_function_requires(_OutputIteratorConcept<_OI,
629 : : typename iterator_traits<_II>::reference>)
630 : : __glibcxx_requires_can_increment_range(__first, __last, __result);
631 : :
632 : : return std::__copy_move_a<__is_move_iterator<_II>::__value>
633 : : (std::__miter_base(__first), std::__miter_base(__last), __result);
634 : : }
635 : :
636 : : #if __cplusplus >= 201103L
637 : : /**
638 : : * @brief Moves the range [first,last) into result.
639 : : * @ingroup mutating_algorithms
640 : : * @param __first An input iterator.
641 : : * @param __last An input iterator.
642 : : * @param __result An output iterator.
643 : : * @return result + (last - first)
644 : : *
645 : : * This inline function will boil down to a call to @c memmove whenever
646 : : * possible. Failing that, if random access iterators are passed, then the
647 : : * loop count will be known (and therefore a candidate for compiler
648 : : * optimizations such as unrolling). Result may not be contained within
649 : : * [first,last); the move_backward function should be used instead.
650 : : *
651 : : * Note that the end of the output range is permitted to be contained
652 : : * within [first,last).
653 : : */
654 : : template<typename _II, typename _OI>
655 : : _GLIBCXX20_CONSTEXPR
656 : : inline _OI
657 : : move(_II __first, _II __last, _OI __result)
658 : : {
659 : : // concept requirements
660 : : __glibcxx_function_requires(_InputIteratorConcept<_II>)
661 : : __glibcxx_function_requires(_OutputIteratorConcept<_OI,
662 : : typename iterator_traits<_II>::value_type&&>)
663 : : __glibcxx_requires_can_increment_range(__first, __last, __result);
664 : :
665 : : return std::__copy_move_a<true>(std::__miter_base(__first),
666 : : std::__miter_base(__last), __result);
667 : : }
668 : :
669 : : #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
670 : : #else
671 : : #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
672 : : #endif
673 : :
674 : : template<bool _IsMove, bool _IsSimple, typename _Category>
675 : : struct __copy_move_backward
676 : : {
677 : : template<typename _BI1, typename _BI2>
678 : : _GLIBCXX20_CONSTEXPR
679 : : static _BI2
680 : : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
681 : : {
682 : : while (__first != __last)
683 : : *--__result = *--__last;
684 : : return __result;
685 : : }
686 : : };
687 : :
688 : : #if __cplusplus >= 201103L
689 : : template<typename _Category>
690 : : struct __copy_move_backward<true, false, _Category>
691 : : {
692 : : template<typename _BI1, typename _BI2>
693 : : _GLIBCXX20_CONSTEXPR
694 : : static _BI2
695 : : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
696 : : {
697 : : while (__first != __last)
698 : : *--__result = std::move(*--__last);
699 : : return __result;
700 : : }
701 : : };
702 : : #endif
703 : :
704 : : template<>
705 : : struct __copy_move_backward<false, false, random_access_iterator_tag>
706 : : {
707 : : template<typename _BI1, typename _BI2>
708 : : _GLIBCXX20_CONSTEXPR
709 : : static _BI2
710 : : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
711 : : {
712 : : typename iterator_traits<_BI1>::difference_type
713 : : __n = __last - __first;
714 : : for (; __n > 0; --__n)
715 : : *--__result = *--__last;
716 : : return __result;
717 : : }
718 : : };
719 : :
720 : : #if __cplusplus >= 201103L
721 : : template<>
722 : : struct __copy_move_backward<true, false, random_access_iterator_tag>
723 : : {
724 : : template<typename _BI1, typename _BI2>
725 : : _GLIBCXX20_CONSTEXPR
726 : : static _BI2
727 : : __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
728 : : {
729 : : typename iterator_traits<_BI1>::difference_type
730 : : __n = __last - __first;
731 : : for (; __n > 0; --__n)
732 : : *--__result = std::move(*--__last);
733 : : return __result;
734 : : }
735 : : };
736 : : #endif
737 : :
738 : : template<bool _IsMove>
739 : : struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
740 : : {
741 : : template<typename _Tp, typename _Up>
742 : : _GLIBCXX20_CONSTEXPR
743 : : static _Up*
744 : : __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
745 : : {
746 : : const ptrdiff_t _Num = __last - __first;
747 : : if (__builtin_expect(_Num > 1, true))
748 : : __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
749 : : else if (_Num == 1)
750 : : std::__copy_move<_IsMove, false, random_access_iterator_tag>::
751 : : __assign_one(__result - 1, __first);
752 : : return __result - _Num;
753 : : }
754 : : };
755 : :
756 : : template<bool _IsMove, typename _BI1, typename _BI2>
757 : : _GLIBCXX20_CONSTEXPR
758 : : inline _BI2
759 : : __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
760 : : {
761 : : typedef typename iterator_traits<_BI1>::iterator_category _Category;
762 : : #ifdef __cpp_lib_is_constant_evaluated
763 : : if (std::is_constant_evaluated())
764 : : return std::__copy_move_backward<_IsMove, false, _Category>::
765 : : __copy_move_b(__first, __last, __result);
766 : : #endif
767 : : return std::__copy_move_backward<_IsMove,
768 : : __memcpyable<_BI2, _BI1>::__value,
769 : : _Category>::__copy_move_b(__first,
770 : : __last,
771 : : __result);
772 : : }
773 : :
774 : : template<bool _IsMove, typename _BI1, typename _BI2>
775 : : _GLIBCXX20_CONSTEXPR
776 : : inline _BI2
777 : : __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
778 : : { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
779 : :
780 : : template<bool _IsMove,
781 : : typename _Tp, typename _Ref, typename _Ptr, typename _OI>
782 : : _OI
783 : : __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
784 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
785 : : _OI);
786 : :
787 : : template<bool _IsMove,
788 : : typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
789 : : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
790 : : __copy_move_backward_a1(
791 : : _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
792 : : _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
793 : : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
794 : :
795 : : template<bool _IsMove, typename _II, typename _Tp>
796 : : typename __gnu_cxx::__enable_if<
797 : : __is_random_access_iter<_II>::__value,
798 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
799 : : __copy_move_backward_a1(_II, _II,
800 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
801 : :
802 : : template<bool _IsMove, typename _II, typename _OI>
803 : : _GLIBCXX20_CONSTEXPR
804 : : inline _OI
805 : : __copy_move_backward_a(_II __first, _II __last, _OI __result)
806 : : {
807 : : return std::__niter_wrap(__result,
808 : : std::__copy_move_backward_a1<_IsMove>
809 : : (std::__niter_base(__first), std::__niter_base(__last),
810 : : std::__niter_base(__result)));
811 : : }
812 : :
813 : : template<bool _IsMove,
814 : : typename _Ite, typename _Seq, typename _Cat, typename _OI>
815 : : _OI
816 : : __copy_move_backward_a(
817 : : const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
818 : : const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
819 : : _OI);
820 : :
821 : : template<bool _IsMove,
822 : : typename _II, typename _Ite, typename _Seq, typename _Cat>
823 : : __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
824 : : __copy_move_backward_a(_II, _II,
825 : : const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
826 : :
827 : : template<bool _IsMove,
828 : : typename _IIte, typename _ISeq, typename _ICat,
829 : : typename _OIte, typename _OSeq, typename _OCat>
830 : : ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
831 : : __copy_move_backward_a(
832 : : const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
833 : : const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
834 : : const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
835 : :
836 : : /**
837 : : * @brief Copies the range [first,last) into result.
838 : : * @ingroup mutating_algorithms
839 : : * @param __first A bidirectional iterator.
840 : : * @param __last A bidirectional iterator.
841 : : * @param __result A bidirectional iterator.
842 : : * @return result - (last - first)
843 : : *
844 : : * The function has the same effect as copy, but starts at the end of the
845 : : * range and works its way to the start, returning the start of the result.
846 : : * This inline function will boil down to a call to @c memmove whenever
847 : : * possible. Failing that, if random access iterators are passed, then the
848 : : * loop count will be known (and therefore a candidate for compiler
849 : : * optimizations such as unrolling).
850 : : *
851 : : * Result may not be in the range (first,last]. Use copy instead. Note
852 : : * that the start of the output range may overlap [first,last).
853 : : */
854 : : template<typename _BI1, typename _BI2>
855 : : _GLIBCXX20_CONSTEXPR
856 : : inline _BI2
857 : : copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
858 : : {
859 : : // concept requirements
860 : : __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
861 : : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
862 : : __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
863 : : typename iterator_traits<_BI1>::reference>)
864 : : __glibcxx_requires_can_decrement_range(__first, __last, __result);
865 : :
866 : : return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
867 : : (std::__miter_base(__first), std::__miter_base(__last), __result);
868 : : }
869 : :
870 : : #if __cplusplus >= 201103L
871 : : /**
872 : : * @brief Moves the range [first,last) into result.
873 : : * @ingroup mutating_algorithms
874 : : * @param __first A bidirectional iterator.
875 : : * @param __last A bidirectional iterator.
876 : : * @param __result A bidirectional iterator.
877 : : * @return result - (last - first)
878 : : *
879 : : * The function has the same effect as move, but starts at the end of the
880 : : * range and works its way to the start, returning the start of the result.
881 : : * This inline function will boil down to a call to @c memmove whenever
882 : : * possible. Failing that, if random access iterators are passed, then the
883 : : * loop count will be known (and therefore a candidate for compiler
884 : : * optimizations such as unrolling).
885 : : *
886 : : * Result may not be in the range (first,last]. Use move instead. Note
887 : : * that the start of the output range may overlap [first,last).
888 : : */
889 : : template<typename _BI1, typename _BI2>
890 : : _GLIBCXX20_CONSTEXPR
891 : : inline _BI2
892 : : move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
893 : : {
894 : : // concept requirements
895 : : __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
896 : : __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
897 : : __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
898 : : typename iterator_traits<_BI1>::value_type&&>)
899 : : __glibcxx_requires_can_decrement_range(__first, __last, __result);
900 : :
901 : : return std::__copy_move_backward_a<true>(std::__miter_base(__first),
902 : : std::__miter_base(__last),
903 : : __result);
904 : : }
905 : :
906 : : #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
907 : : #else
908 : : #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
909 : : #endif
910 : :
911 : : template<typename _ForwardIterator, typename _Tp>
912 : : _GLIBCXX20_CONSTEXPR
913 : : inline typename
914 : : __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
915 : : __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
916 : : const _Tp& __value)
917 : : {
918 : : for (; __first != __last; ++__first)
919 : : *__first = __value;
920 : : }
921 : :
922 : : template<typename _ForwardIterator, typename _Tp>
923 : : _GLIBCXX20_CONSTEXPR
924 : : inline typename
925 : : __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
926 : : __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
927 : : const _Tp& __value)
928 : : {
929 : : const _Tp __tmp = __value;
930 : : for (; __first != __last; ++__first)
931 : : *__first = __tmp;
932 : : }
933 : :
934 : : // Specialization: for char types we can use memset.
935 : : template<typename _Tp>
936 : : _GLIBCXX20_CONSTEXPR
937 : : inline typename
938 : : __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
939 : : __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c)
940 : : {
941 : : const _Tp __tmp = __c;
942 : : #if __cpp_lib_is_constant_evaluated
943 : : if (std::is_constant_evaluated())
944 : : {
945 : : for (; __first != __last; ++__first)
946 : : *__first = __tmp;
947 : : return;
948 : : }
949 : : #endif
950 : : if (const size_t __len = __last - __first)
951 : : __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
952 : : }
953 : :
954 : : template<typename _Ite, typename _Cont, typename _Tp>
955 : : _GLIBCXX20_CONSTEXPR
956 : : inline void
957 : : __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
958 : : ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
959 : : const _Tp& __value)
960 : : { std::__fill_a1(__first.base(), __last.base(), __value); }
961 : :
962 : : template<typename _Tp, typename _VTp>
963 : : void
964 : : __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
965 : : const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
966 : : const _VTp&);
967 : :
968 : : _GLIBCXX20_CONSTEXPR
969 : : void
970 : : __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
971 : : const bool&);
972 : :
973 : : template<typename _FIte, typename _Tp>
974 : : _GLIBCXX20_CONSTEXPR
975 : : inline void
976 : : __fill_a(_FIte __first, _FIte __last, const _Tp& __value)
977 : : { std::__fill_a1(__first, __last, __value); }
978 : :
979 : : template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
980 : : void
981 : : __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
982 : : const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
983 : : const _Tp&);
984 : :
985 : : /**
986 : : * @brief Fills the range [first,last) with copies of value.
987 : : * @ingroup mutating_algorithms
988 : : * @param __first A forward iterator.
989 : : * @param __last A forward iterator.
990 : : * @param __value A reference-to-const of arbitrary type.
991 : : * @return Nothing.
992 : : *
993 : : * This function fills a range with copies of the same value. For char
994 : : * types filling contiguous areas of memory, this becomes an inline call
995 : : * to @c memset or @c wmemset.
996 : : */
997 : : template<typename _ForwardIterator, typename _Tp>
998 : : _GLIBCXX20_CONSTEXPR
999 : : inline void
1000 : : fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1001 : : {
1002 : : // concept requirements
1003 : : __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1004 : : _ForwardIterator>)
1005 : : __glibcxx_requires_valid_range(__first, __last);
1006 : :
1007 : : std::__fill_a(__first, __last, __value);
1008 : : }
1009 : :
1010 : : // Used by fill_n, generate_n, etc. to convert _Size to an integral type:
1011 : : inline _GLIBCXX_CONSTEXPR int
1012 : : __size_to_integer(int __n) { return __n; }
1013 : : inline _GLIBCXX_CONSTEXPR unsigned
1014 : : __size_to_integer(unsigned __n) { return __n; }
1015 : : inline _GLIBCXX_CONSTEXPR long
1016 : : __size_to_integer(long __n) { return __n; }
1017 : : inline _GLIBCXX_CONSTEXPR unsigned long
1018 : : __size_to_integer(unsigned long __n) { return __n; }
1019 : : inline _GLIBCXX_CONSTEXPR long long
1020 : : __size_to_integer(long long __n) { return __n; }
1021 : : inline _GLIBCXX_CONSTEXPR unsigned long long
1022 : : __size_to_integer(unsigned long long __n) { return __n; }
1023 : :
1024 : : #if defined(__GLIBCXX_TYPE_INT_N_0)
1025 : : __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1026 : : __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
1027 : : __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0
1028 : : __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
1029 : : #endif
1030 : : #if defined(__GLIBCXX_TYPE_INT_N_1)
1031 : : __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1032 : : __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
1033 : : __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1
1034 : : __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
1035 : : #endif
1036 : : #if defined(__GLIBCXX_TYPE_INT_N_2)
1037 : : __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1038 : : __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
1039 : : __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2
1040 : : __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
1041 : : #endif
1042 : : #if defined(__GLIBCXX_TYPE_INT_N_3)
1043 : : __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3
1044 : : __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
1045 : : __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1046 : : __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
1047 : : #endif
1048 : :
1049 : : inline _GLIBCXX_CONSTEXPR long long
1050 : : __size_to_integer(float __n) { return (long long)__n; }
1051 : : inline _GLIBCXX_CONSTEXPR long long
1052 : : __size_to_integer(double __n) { return (long long)__n; }
1053 : : inline _GLIBCXX_CONSTEXPR long long
1054 : : __size_to_integer(long double __n) { return (long long)__n; }
1055 : : #if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
1056 : : __extension__ inline _GLIBCXX_CONSTEXPR long long
1057 : : __size_to_integer(__float128 __n) { return (long long)__n; }
1058 : : #endif
1059 : :
1060 : : template<typename _OutputIterator, typename _Size, typename _Tp>
1061 : : _GLIBCXX20_CONSTEXPR
1062 : : inline typename
1063 : : __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1064 : : __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
1065 : : {
1066 : : for (; __n > 0; --__n, (void) ++__first)
1067 : : *__first = __value;
1068 : : return __first;
1069 : : }
1070 : :
1071 : : template<typename _OutputIterator, typename _Size, typename _Tp>
1072 : : _GLIBCXX20_CONSTEXPR
1073 : : inline typename
1074 : : __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1075 : : __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
1076 : : {
1077 : : const _Tp __tmp = __value;
1078 : : for (; __n > 0; --__n, (void) ++__first)
1079 : : *__first = __tmp;
1080 : : return __first;
1081 : : }
1082 : :
1083 : : template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
1084 : : typename _Tp>
1085 : : ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1086 : : __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1087 : : _Size __n, const _Tp& __value,
1088 : : std::input_iterator_tag);
1089 : :
1090 : : template<typename _OutputIterator, typename _Size, typename _Tp>
1091 : : _GLIBCXX20_CONSTEXPR
1092 : : inline _OutputIterator
1093 : : __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1094 : : std::output_iterator_tag)
1095 : : {
1096 : : #if __cplusplus >= 201103L
1097 : : static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1098 : : #endif
1099 : : return __fill_n_a1(__first, __n, __value);
1100 : : }
1101 : :
1102 : : template<typename _OutputIterator, typename _Size, typename _Tp>
1103 : : _GLIBCXX20_CONSTEXPR
1104 : : inline _OutputIterator
1105 : : __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1106 : : std::input_iterator_tag)
1107 : : {
1108 : : #if __cplusplus >= 201103L
1109 : : static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1110 : : #endif
1111 : : return __fill_n_a1(__first, __n, __value);
1112 : : }
1113 : :
1114 : : template<typename _OutputIterator, typename _Size, typename _Tp>
1115 : : _GLIBCXX20_CONSTEXPR
1116 : : inline _OutputIterator
1117 : : __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1118 : : std::random_access_iterator_tag)
1119 : : {
1120 : : #if __cplusplus >= 201103L
1121 : : static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1122 : : #endif
1123 : : if (__n <= 0)
1124 : : return __first;
1125 : :
1126 : : __glibcxx_requires_can_increment(__first, __n);
1127 : :
1128 : : std::__fill_a(__first, __first + __n, __value);
1129 : : return __first + __n;
1130 : : }
1131 : :
1132 : : /**
1133 : : * @brief Fills the range [first,first+n) with copies of value.
1134 : : * @ingroup mutating_algorithms
1135 : : * @param __first An output iterator.
1136 : : * @param __n The count of copies to perform.
1137 : : * @param __value A reference-to-const of arbitrary type.
1138 : : * @return The iterator at first+n.
1139 : : *
1140 : : * This function fills a range with copies of the same value. For char
1141 : : * types filling contiguous areas of memory, this becomes an inline call
1142 : : * to @c memset or @c wmemset.
1143 : : *
1144 : : * If @p __n is negative, the function does nothing.
1145 : : */
1146 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1147 : : // DR 865. More algorithms that throw away information
1148 : : // DR 426. search_n(), fill_n(), and generate_n() with negative n
1149 : : template<typename _OI, typename _Size, typename _Tp>
1150 : : _GLIBCXX20_CONSTEXPR
1151 : : inline _OI
1152 : : fill_n(_OI __first, _Size __n, const _Tp& __value)
1153 : : {
1154 : : // concept requirements
1155 : : __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1156 : :
1157 : : return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1158 : : std::__iterator_category(__first));
1159 : : }
1160 : :
1161 : : template<bool _BoolType>
1162 : : struct __equal
1163 : : {
1164 : : template<typename _II1, typename _II2>
1165 : : _GLIBCXX20_CONSTEXPR
1166 : : static bool
1167 : : equal(_II1 __first1, _II1 __last1, _II2 __first2)
1168 : : {
1169 : : for (; __first1 != __last1; ++__first1, (void) ++__first2)
1170 : : if (!(*__first1 == *__first2))
1171 : : return false;
1172 : : return true;
1173 : : }
1174 : : };
1175 : :
1176 : : template<>
1177 : : struct __equal<true>
1178 : : {
1179 : : template<typename _Tp>
1180 : : _GLIBCXX20_CONSTEXPR
1181 : : static bool
1182 : : equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
1183 : : {
1184 : : if (const size_t __len = (__last1 - __first1))
1185 : : return !std::__memcmp(__first1, __first2, __len);
1186 : : return true;
1187 : : }
1188 : : };
1189 : :
1190 : : template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1191 : : typename __gnu_cxx::__enable_if<
1192 : : __is_random_access_iter<_II>::__value, bool>::__type
1193 : : __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1194 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1195 : : _II);
1196 : :
1197 : : template<typename _Tp1, typename _Ref1, typename _Ptr1,
1198 : : typename _Tp2, typename _Ref2, typename _Ptr2>
1199 : : bool
1200 : : __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1201 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1202 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1203 : :
1204 : : template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
1205 : : typename __gnu_cxx::__enable_if<
1206 : : __is_random_access_iter<_II>::__value, bool>::__type
1207 : : __equal_aux1(_II, _II,
1208 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1209 : :
1210 : : template<typename _II1, typename _II2>
1211 : : _GLIBCXX20_CONSTEXPR
1212 : : inline bool
1213 : : __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1214 : : {
1215 : : typedef typename iterator_traits<_II1>::value_type _ValueType1;
1216 : : const bool __simple = ((__is_integer<_ValueType1>::__value
1217 : : || __is_pointer<_ValueType1>::__value)
1218 : : && __memcmpable<_II1, _II2>::__value);
1219 : : return std::__equal<__simple>::equal(__first1, __last1, __first2);
1220 : : }
1221 : :
1222 : : template<typename _II1, typename _II2>
1223 : : _GLIBCXX20_CONSTEXPR
1224 : : inline bool
1225 : : __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1226 : : {
1227 : : return std::__equal_aux1(std::__niter_base(__first1),
1228 : : std::__niter_base(__last1),
1229 : : std::__niter_base(__first2));
1230 : : }
1231 : :
1232 : : template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
1233 : : bool
1234 : : __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1235 : : const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1236 : : _II2);
1237 : :
1238 : : template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
1239 : : bool
1240 : : __equal_aux(_II1, _II1,
1241 : : const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1242 : :
1243 : : template<typename _II1, typename _Seq1, typename _Cat1,
1244 : : typename _II2, typename _Seq2, typename _Cat2>
1245 : : bool
1246 : : __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1247 : : const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1248 : : const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1249 : :
1250 : : template<typename, typename>
1251 : : struct __lc_rai
1252 : : {
1253 : : template<typename _II1, typename _II2>
1254 : : _GLIBCXX20_CONSTEXPR
1255 : : static _II1
1256 : : __newlast1(_II1, _II1 __last1, _II2, _II2)
1257 : : { return __last1; }
1258 : :
1259 : : template<typename _II>
1260 : : _GLIBCXX20_CONSTEXPR
1261 : : static bool
1262 : : __cnd2(_II __first, _II __last)
1263 : : { return __first != __last; }
1264 : : };
1265 : :
1266 : : template<>
1267 : : struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1268 : : {
1269 : : template<typename _RAI1, typename _RAI2>
1270 : : _GLIBCXX20_CONSTEXPR
1271 : : static _RAI1
1272 : : __newlast1(_RAI1 __first1, _RAI1 __last1,
1273 : : _RAI2 __first2, _RAI2 __last2)
1274 : : {
1275 : : const typename iterator_traits<_RAI1>::difference_type
1276 : : __diff1 = __last1 - __first1;
1277 : : const typename iterator_traits<_RAI2>::difference_type
1278 : : __diff2 = __last2 - __first2;
1279 : : return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1280 : : }
1281 : :
1282 : : template<typename _RAI>
1283 : : static _GLIBCXX20_CONSTEXPR bool
1284 : : __cnd2(_RAI, _RAI)
1285 : : { return true; }
1286 : : };
1287 : :
1288 : : template<typename _II1, typename _II2, typename _Compare>
1289 : : _GLIBCXX20_CONSTEXPR
1290 : : bool
1291 : : __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1292 : : _II2 __first2, _II2 __last2,
1293 : : _Compare __comp)
1294 : : {
1295 : : typedef typename iterator_traits<_II1>::iterator_category _Category1;
1296 : : typedef typename iterator_traits<_II2>::iterator_category _Category2;
1297 : : typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1298 : :
1299 : : __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1300 : : for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1301 : : ++__first1, (void)++__first2)
1302 : : {
1303 : : if (__comp(__first1, __first2))
1304 : : return true;
1305 : : if (__comp(__first2, __first1))
1306 : : return false;
1307 : : }
1308 : : return __first1 == __last1 && __first2 != __last2;
1309 : : }
1310 : :
1311 : : template<bool _BoolType>
1312 : : struct __lexicographical_compare
1313 : : {
1314 : : template<typename _II1, typename _II2>
1315 : : _GLIBCXX20_CONSTEXPR
1316 : : static bool
1317 : : __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1318 : : {
1319 : : using __gnu_cxx::__ops::__iter_less_iter;
1320 : : return std::__lexicographical_compare_impl(__first1, __last1,
1321 : : __first2, __last2,
1322 : : __iter_less_iter());
1323 : : }
1324 : :
1325 : : template<typename _II1, typename _II2>
1326 : : _GLIBCXX20_CONSTEXPR
1327 : : static int
1328 : : __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1329 : : {
1330 : : while (__first1 != __last1)
1331 : : {
1332 : : if (__first2 == __last2)
1333 : : return +1;
1334 : : if (*__first1 < *__first2)
1335 : : return -1;
1336 : : if (*__first2 < *__first1)
1337 : : return +1;
1338 : : ++__first1;
1339 : : ++__first2;
1340 : : }
1341 : : return int(__first2 == __last2) - 1;
1342 : : }
1343 : : };
1344 : :
1345 : : template<>
1346 : : struct __lexicographical_compare<true>
1347 : : {
1348 : : template<typename _Tp, typename _Up>
1349 : : _GLIBCXX20_CONSTEXPR
1350 : : static bool
1351 : : __lc(const _Tp* __first1, const _Tp* __last1,
1352 : : const _Up* __first2, const _Up* __last2)
1353 : : { return __3way(__first1, __last1, __first2, __last2) < 0; }
1354 : :
1355 : : template<typename _Tp, typename _Up>
1356 : : _GLIBCXX20_CONSTEXPR
1357 : : static ptrdiff_t
1358 : : __3way(const _Tp* __first1, const _Tp* __last1,
1359 : : const _Up* __first2, const _Up* __last2)
1360 : : {
1361 : : const size_t __len1 = __last1 - __first1;
1362 : : const size_t __len2 = __last2 - __first2;
1363 : : if (const size_t __len = std::min(__len1, __len2))
1364 : : if (int __result = std::__memcmp(__first1, __first2, __len))
1365 : : return __result;
1366 : : return ptrdiff_t(__len1 - __len2);
1367 : : }
1368 : : };
1369 : :
1370 : : template<typename _II1, typename _II2>
1371 : : _GLIBCXX20_CONSTEXPR
1372 : : inline bool
1373 : : __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1374 : : _II2 __first2, _II2 __last2)
1375 : : {
1376 : : typedef typename iterator_traits<_II1>::value_type _ValueType1;
1377 : : typedef typename iterator_traits<_II2>::value_type _ValueType2;
1378 : : const bool __simple =
1379 : : (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1380 : : && __is_pointer<_II1>::__value
1381 : : && __is_pointer<_II2>::__value
1382 : : #if __cplusplus > 201703L && __cpp_lib_concepts
1383 : : // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
1384 : : // so __is_byte<T> could be true, but we can't use memcmp with
1385 : : // volatile data.
1386 : : && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1387 : : && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1388 : : #endif
1389 : : );
1390 : :
1391 : : return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1392 : : __first2, __last2);
1393 : : }
1394 : :
1395 : : template<typename _Tp1, typename _Ref1, typename _Ptr1,
1396 : : typename _Tp2>
1397 : : bool
1398 : : __lexicographical_compare_aux1(
1399 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1400 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1401 : : _Tp2*, _Tp2*);
1402 : :
1403 : : template<typename _Tp1,
1404 : : typename _Tp2, typename _Ref2, typename _Ptr2>
1405 : : bool
1406 : : __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1407 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1408 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1409 : :
1410 : : template<typename _Tp1, typename _Ref1, typename _Ptr1,
1411 : : typename _Tp2, typename _Ref2, typename _Ptr2>
1412 : : bool
1413 : : __lexicographical_compare_aux1(
1414 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1415 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1416 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1417 : : _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1418 : :
1419 : : template<typename _II1, typename _II2>
1420 : : _GLIBCXX20_CONSTEXPR
1421 : : inline bool
1422 : : __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1423 : : _II2 __first2, _II2 __last2)
1424 : : {
1425 : : return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1426 : : std::__niter_base(__last1),
1427 : : std::__niter_base(__first2),
1428 : : std::__niter_base(__last2));
1429 : : }
1430 : :
1431 : : template<typename _Iter1, typename _Seq1, typename _Cat1,
1432 : : typename _II2>
1433 : : bool
1434 : : __lexicographical_compare_aux(
1435 : : const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1436 : : const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1437 : : _II2, _II2);
1438 : :
1439 : : template<typename _II1,
1440 : : typename _Iter2, typename _Seq2, typename _Cat2>
1441 : : bool
1442 : : __lexicographical_compare_aux(
1443 : : _II1, _II1,
1444 : : const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1445 : : const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1446 : :
1447 : : template<typename _Iter1, typename _Seq1, typename _Cat1,
1448 : : typename _Iter2, typename _Seq2, typename _Cat2>
1449 : : bool
1450 : : __lexicographical_compare_aux(
1451 : : const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1452 : : const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1453 : : const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1454 : : const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1455 : :
1456 : : template<typename _ForwardIterator, typename _Tp, typename _Compare>
1457 : : _GLIBCXX20_CONSTEXPR
1458 : : _ForwardIterator
1459 : : __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1460 : : const _Tp& __val, _Compare __comp)
1461 : : {
1462 : : typedef typename iterator_traits<_ForwardIterator>::difference_type
1463 : : _DistanceType;
1464 : :
1465 : : _DistanceType __len = std::distance(__first, __last);
1466 : :
1467 : : while (__len > 0)
1468 : : {
1469 : : _DistanceType __half = __len >> 1;
1470 : : _ForwardIterator __middle = __first;
1471 : : std::advance(__middle, __half);
1472 : : if (__comp(__middle, __val))
1473 : : {
1474 : : __first = __middle;
1475 : : ++__first;
1476 : : __len = __len - __half - 1;
1477 : : }
1478 : : else
1479 : : __len = __half;
1480 : : }
1481 : : return __first;
1482 : : }
1483 : :
1484 : : /**
1485 : : * @brief Finds the first position in which @a val could be inserted
1486 : : * without changing the ordering.
1487 : : * @param __first An iterator.
1488 : : * @param __last Another iterator.
1489 : : * @param __val The search term.
1490 : : * @return An iterator pointing to the first element <em>not less
1491 : : * than</em> @a val, or end() if every element is less than
1492 : : * @a val.
1493 : : * @ingroup binary_search_algorithms
1494 : : */
1495 : : template<typename _ForwardIterator, typename _Tp>
1496 : : _GLIBCXX20_CONSTEXPR
1497 : : inline _ForwardIterator
1498 : : lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1499 : : const _Tp& __val)
1500 : : {
1501 : : // concept requirements
1502 : : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1503 : : __glibcxx_function_requires(_LessThanOpConcept<
1504 : : typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1505 : : __glibcxx_requires_partitioned_lower(__first, __last, __val);
1506 : :
1507 : : return std::__lower_bound(__first, __last, __val,
1508 : : __gnu_cxx::__ops::__iter_less_val());
1509 : : }
1510 : :
1511 : : /// This is a helper function for the sort routines and for random.tcc.
1512 : : // Precondition: __n > 0.
1513 : : template<typename _Tp>
1514 : : inline _GLIBCXX_CONSTEXPR _Tp
1515 : : __lg(_Tp __n)
1516 : : {
1517 : : #if __cplusplus >= 201402L
1518 : : return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1;
1519 : : #else
1520 : : // Use +__n so it promotes to at least int.
1521 : : const int __sz = sizeof(+__n);
1522 : : int __w = __sz * __CHAR_BIT__ - 1;
1523 : : if (__sz == sizeof(long long))
1524 : : __w -= __builtin_clzll(+__n);
1525 : : else if (__sz == sizeof(long))
1526 : : __w -= __builtin_clzl(+__n);
1527 : : else if (__sz == sizeof(int))
1528 : : __w -= __builtin_clz(+__n);
1529 : : return __w;
1530 : : #endif
1531 : : }
1532 : :
1533 : : _GLIBCXX_BEGIN_NAMESPACE_ALGO
1534 : :
1535 : : /**
1536 : : * @brief Tests a range for element-wise equality.
1537 : : * @ingroup non_mutating_algorithms
1538 : : * @param __first1 An input iterator.
1539 : : * @param __last1 An input iterator.
1540 : : * @param __first2 An input iterator.
1541 : : * @return A boolean true or false.
1542 : : *
1543 : : * This compares the elements of two ranges using @c == and returns true or
1544 : : * false depending on whether all of the corresponding elements of the
1545 : : * ranges are equal.
1546 : : */
1547 : : template<typename _II1, typename _II2>
1548 : : _GLIBCXX20_CONSTEXPR
1549 : : inline bool
1550 : : equal(_II1 __first1, _II1 __last1, _II2 __first2)
1551 : : {
1552 : : // concept requirements
1553 : : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1554 : : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1555 : : __glibcxx_function_requires(_EqualOpConcept<
1556 : : typename iterator_traits<_II1>::value_type,
1557 : : typename iterator_traits<_II2>::value_type>)
1558 : : __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1559 : :
1560 : : return std::__equal_aux(__first1, __last1, __first2);
1561 : : }
1562 : :
1563 : : /**
1564 : : * @brief Tests a range for element-wise equality.
1565 : : * @ingroup non_mutating_algorithms
1566 : : * @param __first1 An input iterator.
1567 : : * @param __last1 An input iterator.
1568 : : * @param __first2 An input iterator.
1569 : : * @param __binary_pred A binary predicate @link functors
1570 : : * functor@endlink.
1571 : : * @return A boolean true or false.
1572 : : *
1573 : : * This compares the elements of two ranges using the binary_pred
1574 : : * parameter, and returns true or
1575 : : * false depending on whether all of the corresponding elements of the
1576 : : * ranges are equal.
1577 : : */
1578 : : template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1579 : : _GLIBCXX20_CONSTEXPR
1580 : : inline bool
1581 : : equal(_IIter1 __first1, _IIter1 __last1,
1582 : : _IIter2 __first2, _BinaryPredicate __binary_pred)
1583 : : {
1584 : : // concept requirements
1585 : : __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1586 : : __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1587 : : __glibcxx_requires_valid_range(__first1, __last1);
1588 : :
1589 : : for (; __first1 != __last1; ++__first1, (void)++__first2)
1590 : : if (!bool(__binary_pred(*__first1, *__first2)))
1591 : : return false;
1592 : : return true;
1593 : : }
1594 : :
1595 : : #if __cplusplus >= 201103L
1596 : : // 4-iterator version of std::equal<It1, It2> for use in C++11.
1597 : : template<typename _II1, typename _II2>
1598 : : _GLIBCXX20_CONSTEXPR
1599 : : inline bool
1600 : : __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1601 : : {
1602 : : using _RATag = random_access_iterator_tag;
1603 : : using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1604 : : using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1605 : : using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1606 : : if (_RAIters())
1607 : : {
1608 : : auto __d1 = std::distance(__first1, __last1);
1609 : : auto __d2 = std::distance(__first2, __last2);
1610 : : if (__d1 != __d2)
1611 : : return false;
1612 : : return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1613 : : }
1614 : :
1615 : : for (; __first1 != __last1 && __first2 != __last2;
1616 : : ++__first1, (void)++__first2)
1617 : : if (!(*__first1 == *__first2))
1618 : : return false;
1619 : : return __first1 == __last1 && __first2 == __last2;
1620 : : }
1621 : :
1622 : : // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
1623 : : template<typename _II1, typename _II2, typename _BinaryPredicate>
1624 : : _GLIBCXX20_CONSTEXPR
1625 : : inline bool
1626 : : __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1627 : : _BinaryPredicate __binary_pred)
1628 : : {
1629 : : using _RATag = random_access_iterator_tag;
1630 : : using _Cat1 = typename iterator_traits<_II1>::iterator_category;
1631 : : using _Cat2 = typename iterator_traits<_II2>::iterator_category;
1632 : : using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1633 : : if (_RAIters())
1634 : : {
1635 : : auto __d1 = std::distance(__first1, __last1);
1636 : : auto __d2 = std::distance(__first2, __last2);
1637 : : if (__d1 != __d2)
1638 : : return false;
1639 : : return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1640 : : __binary_pred);
1641 : : }
1642 : :
1643 : : for (; __first1 != __last1 && __first2 != __last2;
1644 : : ++__first1, (void)++__first2)
1645 : : if (!bool(__binary_pred(*__first1, *__first2)))
1646 : : return false;
1647 : : return __first1 == __last1 && __first2 == __last2;
1648 : : }
1649 : : #endif // C++11
1650 : :
1651 : : #if __cplusplus > 201103L
1652 : :
1653 : : #define __cpp_lib_robust_nonmodifying_seq_ops 201304L
1654 : :
1655 : : /**
1656 : : * @brief Tests a range for element-wise equality.
1657 : : * @ingroup non_mutating_algorithms
1658 : : * @param __first1 An input iterator.
1659 : : * @param __last1 An input iterator.
1660 : : * @param __first2 An input iterator.
1661 : : * @param __last2 An input iterator.
1662 : : * @return A boolean true or false.
1663 : : *
1664 : : * This compares the elements of two ranges using @c == and returns true or
1665 : : * false depending on whether all of the corresponding elements of the
1666 : : * ranges are equal.
1667 : : */
1668 : : template<typename _II1, typename _II2>
1669 : : _GLIBCXX20_CONSTEXPR
1670 : : inline bool
1671 : : equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1672 : : {
1673 : : // concept requirements
1674 : : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1675 : : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1676 : : __glibcxx_function_requires(_EqualOpConcept<
1677 : : typename iterator_traits<_II1>::value_type,
1678 : : typename iterator_traits<_II2>::value_type>)
1679 : : __glibcxx_requires_valid_range(__first1, __last1);
1680 : : __glibcxx_requires_valid_range(__first2, __last2);
1681 : :
1682 : : return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1683 : : }
1684 : :
1685 : : /**
1686 : : * @brief Tests a range for element-wise equality.
1687 : : * @ingroup non_mutating_algorithms
1688 : : * @param __first1 An input iterator.
1689 : : * @param __last1 An input iterator.
1690 : : * @param __first2 An input iterator.
1691 : : * @param __last2 An input iterator.
1692 : : * @param __binary_pred A binary predicate @link functors
1693 : : * functor@endlink.
1694 : : * @return A boolean true or false.
1695 : : *
1696 : : * This compares the elements of two ranges using the binary_pred
1697 : : * parameter, and returns true or
1698 : : * false depending on whether all of the corresponding elements of the
1699 : : * ranges are equal.
1700 : : */
1701 : : template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1702 : : _GLIBCXX20_CONSTEXPR
1703 : : inline bool
1704 : : equal(_IIter1 __first1, _IIter1 __last1,
1705 : : _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1706 : : {
1707 : : // concept requirements
1708 : : __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1709 : : __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1710 : : __glibcxx_requires_valid_range(__first1, __last1);
1711 : : __glibcxx_requires_valid_range(__first2, __last2);
1712 : :
1713 : : return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1714 : : __binary_pred);
1715 : : }
1716 : : #endif // C++14
1717 : :
1718 : : /**
1719 : : * @brief Performs @b dictionary comparison on ranges.
1720 : : * @ingroup sorting_algorithms
1721 : : * @param __first1 An input iterator.
1722 : : * @param __last1 An input iterator.
1723 : : * @param __first2 An input iterator.
1724 : : * @param __last2 An input iterator.
1725 : : * @return A boolean true or false.
1726 : : *
1727 : : * <em>Returns true if the sequence of elements defined by the range
1728 : : * [first1,last1) is lexicographically less than the sequence of elements
1729 : : * defined by the range [first2,last2). Returns false otherwise.</em>
1730 : : * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1731 : : * then this is an inline call to @c memcmp.
1732 : : */
1733 : : template<typename _II1, typename _II2>
1734 : : _GLIBCXX20_CONSTEXPR
1735 : : inline bool
1736 : : lexicographical_compare(_II1 __first1, _II1 __last1,
1737 : : _II2 __first2, _II2 __last2)
1738 : : {
1739 : : #ifdef _GLIBCXX_CONCEPT_CHECKS
1740 : : // concept requirements
1741 : : typedef typename iterator_traits<_II1>::value_type _ValueType1;
1742 : : typedef typename iterator_traits<_II2>::value_type _ValueType2;
1743 : : #endif
1744 : : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1745 : : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1746 : : __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1747 : : __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1748 : : __glibcxx_requires_valid_range(__first1, __last1);
1749 : : __glibcxx_requires_valid_range(__first2, __last2);
1750 : :
1751 : : return std::__lexicographical_compare_aux(__first1, __last1,
1752 : : __first2, __last2);
1753 : : }
1754 : :
1755 : : /**
1756 : : * @brief Performs @b dictionary comparison on ranges.
1757 : : * @ingroup sorting_algorithms
1758 : : * @param __first1 An input iterator.
1759 : : * @param __last1 An input iterator.
1760 : : * @param __first2 An input iterator.
1761 : : * @param __last2 An input iterator.
1762 : : * @param __comp A @link comparison_functors comparison functor@endlink.
1763 : : * @return A boolean true or false.
1764 : : *
1765 : : * The same as the four-parameter @c lexicographical_compare, but uses the
1766 : : * comp parameter instead of @c <.
1767 : : */
1768 : : template<typename _II1, typename _II2, typename _Compare>
1769 : : _GLIBCXX20_CONSTEXPR
1770 : : inline bool
1771 : : lexicographical_compare(_II1 __first1, _II1 __last1,
1772 : : _II2 __first2, _II2 __last2, _Compare __comp)
1773 : : {
1774 : : // concept requirements
1775 : : __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1776 : : __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1777 : : __glibcxx_requires_valid_range(__first1, __last1);
1778 : : __glibcxx_requires_valid_range(__first2, __last2);
1779 : :
1780 : : return std::__lexicographical_compare_impl
1781 : : (__first1, __last1, __first2, __last2,
1782 : : __gnu_cxx::__ops::__iter_comp_iter(__comp));
1783 : : }
1784 : :
1785 : : #if __cpp_lib_three_way_comparison
1786 : : // Iter points to a contiguous range of unsigned narrow character type
1787 : : // or std::byte, suitable for comparison by memcmp.
1788 : : template<typename _Iter>
1789 : : concept __is_byte_iter = contiguous_iterator<_Iter>
1790 : : && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
1791 : :
1792 : : // Return a struct with two members, initialized to the smaller of x and y
1793 : : // (or x if they compare equal) and the result of the comparison x <=> y.
1794 : : template<typename _Tp>
1795 : : constexpr auto
1796 : : __min_cmp(_Tp __x, _Tp __y)
1797 : : {
1798 : : struct _Res {
1799 : : _Tp _M_min;
1800 : : decltype(__x <=> __y) _M_cmp;
1801 : : };
1802 : : auto __c = __x <=> __y;
1803 : : if (__c > 0)
1804 : : return _Res{__y, __c};
1805 : : return _Res{__x, __c};
1806 : : }
1807 : :
1808 : : /**
1809 : : * @brief Performs dictionary comparison on ranges.
1810 : : * @ingroup sorting_algorithms
1811 : : * @param __first1 An input iterator.
1812 : : * @param __last1 An input iterator.
1813 : : * @param __first2 An input iterator.
1814 : : * @param __last2 An input iterator.
1815 : : * @param __comp A @link comparison_functors comparison functor@endlink.
1816 : : * @return The comparison category that `__comp(*__first1, *__first2)`
1817 : : * returns.
1818 : : */
1819 : : template<typename _InputIter1, typename _InputIter2, typename _Comp>
1820 : : constexpr auto
1821 : : lexicographical_compare_three_way(_InputIter1 __first1,
1822 : : _InputIter1 __last1,
1823 : : _InputIter2 __first2,
1824 : : _InputIter2 __last2,
1825 : : _Comp __comp)
1826 : : -> decltype(__comp(*__first1, *__first2))
1827 : : {
1828 : : // concept requirements
1829 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1830 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1831 : : __glibcxx_requires_valid_range(__first1, __last1);
1832 : : __glibcxx_requires_valid_range(__first2, __last2);
1833 : :
1834 : : using _Cat = decltype(__comp(*__first1, *__first2));
1835 : : static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1836 : :
1837 : : if (!std::__is_constant_evaluated())
1838 : : if constexpr (same_as<_Comp, __detail::_Synth3way>
1839 : : || same_as<_Comp, compare_three_way>)
1840 : : if constexpr (__is_byte_iter<_InputIter1>)
1841 : : if constexpr (__is_byte_iter<_InputIter2>)
1842 : : {
1843 : : const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1844 : : __min_cmp(__last1 - __first1, __last2 - __first2);
1845 : : if (__len)
1846 : : {
1847 : : const auto __c
1848 : : = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
1849 : : if (__c != 0)
1850 : : return __c;
1851 : : }
1852 : : return __lencmp;
1853 : : }
1854 : :
1855 : : while (__first1 != __last1)
1856 : : {
1857 : : if (__first2 == __last2)
1858 : : return strong_ordering::greater;
1859 : : if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1860 : : return __cmp;
1861 : : ++__first1;
1862 : : ++__first2;
1863 : : }
1864 : : return (__first2 == __last2) <=> true; // See PR 94006
1865 : : }
1866 : :
1867 : : template<typename _InputIter1, typename _InputIter2>
1868 : : constexpr auto
1869 : : lexicographical_compare_three_way(_InputIter1 __first1,
1870 : : _InputIter1 __last1,
1871 : : _InputIter2 __first2,
1872 : : _InputIter2 __last2)
1873 : : {
1874 : : return _GLIBCXX_STD_A::
1875 : : lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1876 : : compare_three_way{});
1877 : : }
1878 : : #endif // three_way_comparison
1879 : :
1880 : : template<typename _InputIterator1, typename _InputIterator2,
1881 : : typename _BinaryPredicate>
1882 : : _GLIBCXX20_CONSTEXPR
1883 : : pair<_InputIterator1, _InputIterator2>
1884 : : __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1885 : : _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1886 : : {
1887 : : while (__first1 != __last1 && __binary_pred(__first1, __first2))
1888 : : {
1889 : : ++__first1;
1890 : : ++__first2;
1891 : : }
1892 : : return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1893 : : }
1894 : :
1895 : : /**
1896 : : * @brief Finds the places in ranges which don't match.
1897 : : * @ingroup non_mutating_algorithms
1898 : : * @param __first1 An input iterator.
1899 : : * @param __last1 An input iterator.
1900 : : * @param __first2 An input iterator.
1901 : : * @return A pair of iterators pointing to the first mismatch.
1902 : : *
1903 : : * This compares the elements of two ranges using @c == and returns a pair
1904 : : * of iterators. The first iterator points into the first range, the
1905 : : * second iterator points into the second range, and the elements pointed
1906 : : * to by the iterators are not equal.
1907 : : */
1908 : : template<typename _InputIterator1, typename _InputIterator2>
1909 : : _GLIBCXX20_CONSTEXPR
1910 : : inline pair<_InputIterator1, _InputIterator2>
1911 : : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1912 : : _InputIterator2 __first2)
1913 : : {
1914 : : // concept requirements
1915 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1916 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1917 : : __glibcxx_function_requires(_EqualOpConcept<
1918 : : typename iterator_traits<_InputIterator1>::value_type,
1919 : : typename iterator_traits<_InputIterator2>::value_type>)
1920 : : __glibcxx_requires_valid_range(__first1, __last1);
1921 : :
1922 : : return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1923 : : __gnu_cxx::__ops::__iter_equal_to_iter());
1924 : : }
1925 : :
1926 : : /**
1927 : : * @brief Finds the places in ranges which don't match.
1928 : : * @ingroup non_mutating_algorithms
1929 : : * @param __first1 An input iterator.
1930 : : * @param __last1 An input iterator.
1931 : : * @param __first2 An input iterator.
1932 : : * @param __binary_pred A binary predicate @link functors
1933 : : * functor@endlink.
1934 : : * @return A pair of iterators pointing to the first mismatch.
1935 : : *
1936 : : * This compares the elements of two ranges using the binary_pred
1937 : : * parameter, and returns a pair
1938 : : * of iterators. The first iterator points into the first range, the
1939 : : * second iterator points into the second range, and the elements pointed
1940 : : * to by the iterators are not equal.
1941 : : */
1942 : : template<typename _InputIterator1, typename _InputIterator2,
1943 : : typename _BinaryPredicate>
1944 : : _GLIBCXX20_CONSTEXPR
1945 : : inline pair<_InputIterator1, _InputIterator2>
1946 : : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1947 : : _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1948 : : {
1949 : : // concept requirements
1950 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1951 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1952 : : __glibcxx_requires_valid_range(__first1, __last1);
1953 : :
1954 : : return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1955 : : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1956 : : }
1957 : :
1958 : : #if __cplusplus > 201103L
1959 : :
1960 : : template<typename _InputIterator1, typename _InputIterator2,
1961 : : typename _BinaryPredicate>
1962 : : _GLIBCXX20_CONSTEXPR
1963 : : pair<_InputIterator1, _InputIterator2>
1964 : : __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1965 : : _InputIterator2 __first2, _InputIterator2 __last2,
1966 : : _BinaryPredicate __binary_pred)
1967 : : {
1968 : : while (__first1 != __last1 && __first2 != __last2
1969 : : && __binary_pred(__first1, __first2))
1970 : : {
1971 : : ++__first1;
1972 : : ++__first2;
1973 : : }
1974 : : return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1975 : : }
1976 : :
1977 : : /**
1978 : : * @brief Finds the places in ranges which don't match.
1979 : : * @ingroup non_mutating_algorithms
1980 : : * @param __first1 An input iterator.
1981 : : * @param __last1 An input iterator.
1982 : : * @param __first2 An input iterator.
1983 : : * @param __last2 An input iterator.
1984 : : * @return A pair of iterators pointing to the first mismatch.
1985 : : *
1986 : : * This compares the elements of two ranges using @c == and returns a pair
1987 : : * of iterators. The first iterator points into the first range, the
1988 : : * second iterator points into the second range, and the elements pointed
1989 : : * to by the iterators are not equal.
1990 : : */
1991 : : template<typename _InputIterator1, typename _InputIterator2>
1992 : : _GLIBCXX20_CONSTEXPR
1993 : : inline pair<_InputIterator1, _InputIterator2>
1994 : : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1995 : : _InputIterator2 __first2, _InputIterator2 __last2)
1996 : : {
1997 : : // concept requirements
1998 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1999 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2000 : : __glibcxx_function_requires(_EqualOpConcept<
2001 : : typename iterator_traits<_InputIterator1>::value_type,
2002 : : typename iterator_traits<_InputIterator2>::value_type>)
2003 : : __glibcxx_requires_valid_range(__first1, __last1);
2004 : : __glibcxx_requires_valid_range(__first2, __last2);
2005 : :
2006 : : return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2007 : : __gnu_cxx::__ops::__iter_equal_to_iter());
2008 : : }
2009 : :
2010 : : /**
2011 : : * @brief Finds the places in ranges which don't match.
2012 : : * @ingroup non_mutating_algorithms
2013 : : * @param __first1 An input iterator.
2014 : : * @param __last1 An input iterator.
2015 : : * @param __first2 An input iterator.
2016 : : * @param __last2 An input iterator.
2017 : : * @param __binary_pred A binary predicate @link functors
2018 : : * functor@endlink.
2019 : : * @return A pair of iterators pointing to the first mismatch.
2020 : : *
2021 : : * This compares the elements of two ranges using the binary_pred
2022 : : * parameter, and returns a pair
2023 : : * of iterators. The first iterator points into the first range, the
2024 : : * second iterator points into the second range, and the elements pointed
2025 : : * to by the iterators are not equal.
2026 : : */
2027 : : template<typename _InputIterator1, typename _InputIterator2,
2028 : : typename _BinaryPredicate>
2029 : : _GLIBCXX20_CONSTEXPR
2030 : : inline pair<_InputIterator1, _InputIterator2>
2031 : : mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2032 : : _InputIterator2 __first2, _InputIterator2 __last2,
2033 : : _BinaryPredicate __binary_pred)
2034 : : {
2035 : : // concept requirements
2036 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2037 : : __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2038 : : __glibcxx_requires_valid_range(__first1, __last1);
2039 : : __glibcxx_requires_valid_range(__first2, __last2);
2040 : :
2041 : : return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2042 : : __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2043 : : }
2044 : : #endif
2045 : :
2046 : : _GLIBCXX_END_NAMESPACE_ALGO
2047 : :
2048 : : /// This is an overload used by find algos for the Input Iterator case.
2049 : : template<typename _InputIterator, typename _Predicate>
2050 : : _GLIBCXX20_CONSTEXPR
2051 : : inline _InputIterator
2052 : : __find_if(_InputIterator __first, _InputIterator __last,
2053 : : _Predicate __pred, input_iterator_tag)
2054 : : {
2055 : : while (__first != __last && !__pred(__first))
2056 : : ++__first;
2057 : : return __first;
2058 : : }
2059 : :
2060 : : /// This is an overload used by find algos for the RAI case.
2061 : : template<typename _RandomAccessIterator, typename _Predicate>
2062 : : _GLIBCXX20_CONSTEXPR
2063 : : _RandomAccessIterator
2064 : : __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2065 : : _Predicate __pred, random_access_iterator_tag)
2066 : : {
2067 : : typename iterator_traits<_RandomAccessIterator>::difference_type
2068 : : __trip_count = (__last - __first) >> 2;
2069 : :
2070 : : for (; __trip_count > 0; --__trip_count)
2071 : : {
2072 : : if (__pred(__first))
2073 : : return __first;
2074 : : ++__first;
2075 : :
2076 : : if (__pred(__first))
2077 : : return __first;
2078 : : ++__first;
2079 : :
2080 : : if (__pred(__first))
2081 : : return __first;
2082 : : ++__first;
2083 : :
2084 : : if (__pred(__first))
2085 : : return __first;
2086 : : ++__first;
2087 : : }
2088 : :
2089 : : switch (__last - __first)
2090 : : {
2091 : : case 3:
2092 : : if (__pred(__first))
2093 : : return __first;
2094 : : ++__first;
2095 : : // FALLTHRU
2096 : : case 2:
2097 : : if (__pred(__first))
2098 : : return __first;
2099 : : ++__first;
2100 : : // FALLTHRU
2101 : : case 1:
2102 : : if (__pred(__first))
2103 : : return __first;
2104 : : ++__first;
2105 : : // FALLTHRU
2106 : : case 0:
2107 : : default:
2108 : : return __last;
2109 : : }
2110 : : }
2111 : :
2112 : : template<typename _Iterator, typename _Predicate>
2113 : : _GLIBCXX20_CONSTEXPR
2114 : : inline _Iterator
2115 : : __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2116 : : {
2117 : : return __find_if(__first, __last, __pred,
2118 : : std::__iterator_category(__first));
2119 : : }
2120 : :
2121 : : template<typename _InputIterator, typename _Predicate>
2122 : : _GLIBCXX20_CONSTEXPR
2123 : : typename iterator_traits<_InputIterator>::difference_type
2124 : : __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2125 : : {
2126 : : typename iterator_traits<_InputIterator>::difference_type __n = 0;
2127 : : for (; __first != __last; ++__first)
2128 : : if (__pred(__first))
2129 : : ++__n;
2130 : : return __n;
2131 : : }
2132 : :
2133 : : template<typename _ForwardIterator, typename _Predicate>
2134 : : _GLIBCXX20_CONSTEXPR
2135 : : _ForwardIterator
2136 : : __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2137 : : _Predicate __pred)
2138 : : {
2139 : : __first = std::__find_if(__first, __last, __pred);
2140 : : if (__first == __last)
2141 : : return __first;
2142 : : _ForwardIterator __result = __first;
2143 : : ++__first;
2144 : : for (; __first != __last; ++__first)
2145 : : if (!__pred(__first))
2146 : : {
2147 : : *__result = _GLIBCXX_MOVE(*__first);
2148 : : ++__result;
2149 : : }
2150 : : return __result;
2151 : : }
2152 : :
2153 : : #if __cplusplus >= 201103L
2154 : : template<typename _ForwardIterator1, typename _ForwardIterator2,
2155 : : typename _BinaryPredicate>
2156 : : _GLIBCXX20_CONSTEXPR
2157 : : bool
2158 : : __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2159 : : _ForwardIterator2 __first2, _BinaryPredicate __pred)
2160 : : {
2161 : : // Efficiently compare identical prefixes: O(N) if sequences
2162 : : // have the same elements in the same order.
2163 : : for (; __first1 != __last1; ++__first1, (void)++__first2)
2164 : : if (!__pred(__first1, __first2))
2165 : : break;
2166 : :
2167 : : if (__first1 == __last1)
2168 : : return true;
2169 : :
2170 : : // Establish __last2 assuming equal ranges by iterating over the
2171 : : // rest of the list.
2172 : : _ForwardIterator2 __last2 = __first2;
2173 : : std::advance(__last2, std::distance(__first1, __last1));
2174 : : for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2175 : : {
2176 : : if (__scan != std::__find_if(__first1, __scan,
2177 : : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2178 : : continue; // We've seen this one before.
2179 : :
2180 : : auto __matches
2181 : : = std::__count_if(__first2, __last2,
2182 : : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2183 : : if (0 == __matches ||
2184 : : std::__count_if(__scan, __last1,
2185 : : __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2186 : : != __matches)
2187 : : return false;
2188 : : }
2189 : : return true;
2190 : : }
2191 : :
2192 : : /**
2193 : : * @brief Checks whether a permutation of the second sequence is equal
2194 : : * to the first sequence.
2195 : : * @ingroup non_mutating_algorithms
2196 : : * @param __first1 Start of first range.
2197 : : * @param __last1 End of first range.
2198 : : * @param __first2 Start of second range.
2199 : : * @return true if there exists a permutation of the elements in the range
2200 : : * [__first2, __first2 + (__last1 - __first1)), beginning with
2201 : : * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
2202 : : * returns true; otherwise, returns false.
2203 : : */
2204 : : template<typename _ForwardIterator1, typename _ForwardIterator2>
2205 : : _GLIBCXX20_CONSTEXPR
2206 : : inline bool
2207 : : is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2208 : : _ForwardIterator2 __first2)
2209 : : {
2210 : : // concept requirements
2211 : : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2212 : : __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2213 : : __glibcxx_function_requires(_EqualOpConcept<
2214 : : typename iterator_traits<_ForwardIterator1>::value_type,
2215 : : typename iterator_traits<_ForwardIterator2>::value_type>)
2216 : : __glibcxx_requires_valid_range(__first1, __last1);
2217 : :
2218 : : return std::__is_permutation(__first1, __last1, __first2,
2219 : : __gnu_cxx::__ops::__iter_equal_to_iter());
2220 : : }
2221 : : #endif // C++11
2222 : :
2223 : : _GLIBCXX_END_NAMESPACE_VERSION
2224 : : } // namespace std
2225 : :
2226 : : // NB: This file is included within many other C++ includes, as a way
2227 : : // of getting the base algorithms. So, make sure that parallel bits
2228 : : // come in too if requested.
2229 : : #ifdef _GLIBCXX_PARALLEL
2230 : : # include <parallel/algobase.h>
2231 : : #endif
2232 : :
2233 : : #endif
|
