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