]>
Commit | Line | Data |
---|---|---|
6d0dff49 JW |
1 | // Concepts and traits for use with iterators -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2019 Free Software Foundation, Inc. | |
4 | // | |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file bits/iterator_concepts.h | |
26 | * This is an internal header file, included by other library headers. | |
27 | * Do not attempt to use it directly. @headername{iterator} | |
28 | */ | |
29 | ||
30 | #ifndef _ITERATOR_CONCEPTS_H | |
31 | #define _ITERATOR_CONCEPTS_H 1 | |
32 | ||
33 | #pragma GCC system_header | |
34 | ||
35 | #include <concepts> | |
36 | #include <bits/ptr_traits.h> // to_address | |
37 | #include <bits/range_cmp.h> // identity, ranges::less | |
38 | ||
39 | #if __cpp_lib_concepts | |
40 | namespace std _GLIBCXX_VISIBILITY(default) | |
41 | { | |
42 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
43 | ||
44 | struct input_iterator_tag; | |
45 | struct output_iterator_tag; | |
46 | struct forward_iterator_tag; | |
47 | struct bidirectional_iterator_tag; | |
48 | struct random_access_iterator_tag; | |
49 | struct contiguous_iterator_tag; | |
50 | ||
51 | template<typename _Iterator> | |
52 | struct iterator_traits; | |
53 | ||
54 | template<typename _Tp> requires is_object_v<_Tp> | |
55 | struct iterator_traits<_Tp*>; | |
56 | ||
57 | template<typename _Iterator, typename> | |
58 | struct __iterator_traits; | |
59 | ||
60 | namespace __detail | |
61 | { | |
62 | template<typename _Tp> | |
63 | using __with_ref = _Tp&; | |
64 | ||
65 | template<typename _Tp> | |
66 | concept __can_reference = requires { typename __with_ref<_Tp>; }; | |
67 | ||
68 | template<typename _Tp> | |
69 | concept __dereferenceable = requires(_Tp& __t) | |
70 | { | |
71 | { *__t } -> __can_reference; | |
72 | }; | |
73 | ||
74 | // FIXME: needed due to PR c++/67704 | |
75 | template<__detail::__dereferenceable _Tp> | |
76 | struct __iter_ref | |
77 | { | |
78 | using type = decltype(*std::declval<_Tp&>()); | |
79 | }; | |
80 | } // namespace __detail | |
81 | ||
82 | template<typename _Tp> | |
83 | using iter_reference_t = typename __detail::__iter_ref<_Tp>::type; | |
84 | ||
85 | namespace ranges | |
86 | { | |
87 | namespace __cust_imove | |
88 | { | |
89 | template<typename _Tp> | |
90 | concept __adl_imove | |
91 | = (std::__detail::__class_or_enum<remove_reference_t<_Tp>>) | |
92 | && requires(_Tp&& __t) { iter_move(static_cast<_Tp&&>(__t)); }; | |
93 | ||
94 | struct _IMove | |
95 | { | |
96 | private: | |
97 | template<typename _Tp> | |
98 | static constexpr bool | |
99 | _S_noexcept() | |
100 | { | |
101 | if constexpr (__adl_imove<_Tp>) | |
102 | return noexcept(iter_move(std::declval<_Tp>())); | |
103 | else | |
104 | return noexcept(*std::declval<_Tp>()); | |
105 | } | |
106 | ||
107 | public: | |
108 | template<typename _Tp> | |
109 | requires __adl_imove<_Tp> || requires(_Tp& __e) { *__e; } | |
110 | constexpr decltype(auto) | |
111 | operator()(_Tp&& __e) const | |
112 | noexcept(_S_noexcept<_Tp>()) | |
113 | { | |
114 | if constexpr (__adl_imove<_Tp>) | |
115 | return iter_move(static_cast<_Tp&&>(__e)); | |
116 | else if constexpr (is_reference_v<iter_reference_t<_Tp>>) | |
117 | return std::move(*__e); | |
118 | else | |
119 | return *__e; | |
120 | } | |
121 | }; | |
122 | } // namespace __cust_imove | |
123 | ||
124 | inline namespace __cust | |
125 | { | |
126 | inline constexpr __cust_imove::_IMove iter_move{}; | |
127 | } // inline namespace __cust | |
128 | } // namespace ranges | |
129 | ||
130 | namespace __detail | |
131 | { | |
132 | // FIXME: needed due to PR c++/67704 | |
133 | template<__detail::__dereferenceable _Tp> | |
134 | struct __iter_rvalue_ref | |
135 | { }; | |
136 | ||
137 | template<__detail::__dereferenceable _Tp> | |
138 | requires requires(_Tp& __t) | |
139 | { | |
140 | { ranges::iter_move(__t) } -> __detail::__can_reference; | |
141 | } | |
142 | struct __iter_rvalue_ref<_Tp> | |
143 | { using type = decltype(ranges::iter_move(std::declval<_Tp&>())); }; | |
144 | ||
145 | } // namespace __detail | |
146 | ||
147 | template<typename _Tp> | |
148 | using iter_rvalue_reference_t | |
149 | = typename __detail::__iter_rvalue_ref<_Tp>::type; | |
150 | ||
151 | template<typename> struct incrementable_traits { }; | |
152 | ||
153 | template<typename _Tp> requires is_object_v<_Tp> | |
154 | struct incrementable_traits<_Tp*> | |
155 | { using difference_type = ptrdiff_t; }; | |
156 | ||
157 | template<typename _Iter> | |
158 | struct incrementable_traits<const _Iter> | |
159 | : incrementable_traits<_Iter> { }; | |
160 | ||
161 | template<typename _Tp> requires requires { typename _Tp::difference_type; } | |
162 | struct incrementable_traits<_Tp> | |
163 | { using difference_type = typename _Tp::difference_type; }; | |
164 | ||
165 | template<typename _Tp> | |
166 | requires (!requires { typename _Tp::difference_type; } | |
167 | && requires(const _Tp& __a, const _Tp& __b) | |
168 | { | |
169 | requires (!is_void_v<remove_pointer_t<_Tp>>); // PR c++/78173 | |
170 | { __a - __b } -> integral; | |
171 | }) | |
172 | struct incrementable_traits<_Tp> | |
173 | { | |
174 | using difference_type | |
175 | = make_signed_t<decltype(std::declval<_Tp>() - std::declval<_Tp>())>; | |
176 | }; | |
177 | ||
178 | namespace __detail | |
179 | { | |
180 | // An iterator such that iterator_traits<_Iter> names a specialization | |
181 | // generated from the primary template. | |
182 | template<typename _Iter> | |
183 | concept __primary_traits_iter | |
184 | = __is_base_of(__iterator_traits<_Iter, void>, iterator_traits<_Iter>); | |
185 | ||
186 | template<typename _Iter, typename _Tp> | |
187 | struct __iter_traits_impl | |
188 | { using type = iterator_traits<_Iter>; }; | |
189 | ||
190 | template<typename _Iter, typename _Tp> | |
191 | requires __primary_traits_iter<_Iter> | |
192 | struct __iter_traits_impl<_Iter, _Tp> | |
193 | { using type = _Tp; }; | |
194 | ||
195 | // ITER_TRAITS | |
196 | template<typename _Iter, typename _Tp = _Iter> | |
197 | using __iter_traits = typename __iter_traits_impl<_Iter, _Tp>::type; | |
198 | } // namespace __detail | |
199 | ||
200 | template<typename _Tp> | |
201 | using iter_difference_t = typename | |
202 | __detail::__iter_traits<_Tp, incrementable_traits<_Tp>>::difference_type; | |
203 | ||
204 | namespace __detail | |
205 | { | |
206 | template<typename> struct __cond_value_type { }; | |
207 | ||
208 | template<typename _Tp> requires is_object_v<_Tp> | |
209 | struct __cond_value_type<_Tp> | |
210 | { using value_type = remove_cv_t<_Tp>; }; | |
211 | } // namespace __detail | |
212 | ||
213 | template<typename> struct readable_traits { }; | |
214 | ||
215 | template<typename _Tp> | |
216 | struct readable_traits<_Tp*> | |
217 | : __detail::__cond_value_type<_Tp> | |
218 | { }; | |
219 | ||
220 | template<typename _Iter> requires is_array_v<_Iter> | |
221 | struct readable_traits<_Iter> | |
222 | { using value_type = remove_cv_t<remove_extent_t<_Iter>>; }; | |
223 | ||
224 | template<typename _Iter> | |
225 | struct readable_traits<const _Iter> | |
226 | : readable_traits<_Iter> | |
227 | { }; | |
228 | ||
229 | template<typename _Tp> requires requires { typename _Tp::value_type; } | |
230 | struct readable_traits<_Tp> | |
231 | : __detail::__cond_value_type<typename _Tp::value_type> | |
232 | { }; | |
233 | ||
234 | template<typename _Tp> requires requires { typename _Tp::element_type; } | |
235 | struct readable_traits<_Tp> | |
236 | : __detail::__cond_value_type<typename _Tp::element_type> | |
237 | { }; | |
238 | ||
239 | template<typename _Tp> | |
240 | using iter_value_t = typename | |
241 | __detail::__iter_traits<_Tp, readable_traits<_Tp>>::value_type; | |
242 | ||
243 | namespace __detail | |
244 | { | |
245 | template<typename _Iter> | |
246 | concept __cpp17_iterator = copyable<_Iter> | |
247 | && requires(_Iter __it) | |
248 | { | |
249 | { *__it } -> __can_reference; | |
250 | { ++__it } -> same_as<_Iter&>; | |
251 | { *__it++ } -> __can_reference; | |
252 | }; | |
253 | ||
254 | template<typename _Iter> | |
255 | concept __cpp17_input_iterator = __cpp17_iterator<_Iter> | |
256 | && equality_comparable<_Iter> | |
257 | && requires(_Iter __it) | |
258 | { | |
259 | typename incrementable_traits<_Iter>::difference_type; | |
260 | typename readable_traits<_Iter>::value_type; | |
261 | typename common_reference_t<iter_reference_t<_Iter>&&, | |
262 | typename readable_traits<_Iter>::value_type&>; | |
263 | typename common_reference_t<decltype(*__it++)&&, | |
264 | typename readable_traits<_Iter>::value_type&>; | |
265 | requires signed_integral<typename incrementable_traits<_Iter>::difference_type>; | |
266 | }; | |
267 | ||
268 | template<typename _Iter> | |
269 | concept __cpp17_fwd_iterator = __cpp17_input_iterator<_Iter> | |
270 | && constructible_from<_Iter> | |
271 | && is_lvalue_reference_v<iter_reference_t<_Iter>> | |
272 | && same_as<remove_cvref_t<iter_reference_t<_Iter>>, | |
273 | typename readable_traits<_Iter>::value_type> | |
274 | && requires(_Iter __it) | |
275 | { | |
276 | { __it++ } -> convertible_to<const _Iter&>; | |
277 | { *__it++ } -> same_as<iter_reference_t<_Iter>>; | |
278 | }; | |
279 | ||
280 | template<typename _Iter> | |
281 | concept __cpp17_bidi_iterator = __cpp17_fwd_iterator<_Iter> | |
282 | && requires(_Iter __it) | |
283 | { | |
284 | { --__it } -> same_as<_Iter&>; | |
285 | { __it-- } -> convertible_to<const _Iter&>; | |
286 | { *__it-- } -> same_as<iter_reference_t<_Iter>>; | |
287 | }; | |
288 | ||
289 | template<typename _Iter> | |
290 | concept __cpp17_randacc_iterator = __cpp17_bidi_iterator<_Iter> | |
291 | && totally_ordered<_Iter> | |
292 | && requires(_Iter __it, | |
293 | typename incrementable_traits<_Iter>::difference_type __n) | |
294 | { | |
295 | { __it += __n } -> same_as<_Iter&>; | |
296 | { __it -= __n } -> same_as<_Iter&>; | |
297 | { __it + __n } -> same_as<_Iter>; | |
298 | { __n + __it } -> same_as<_Iter>; | |
299 | { __it - __n } -> same_as<_Iter>; | |
300 | { __it - __it } -> same_as<decltype(__n)>; | |
301 | { __it[__n] } -> convertible_to<iter_reference_t<_Iter>>; | |
302 | }; | |
303 | ||
304 | template<typename _Iter> | |
305 | concept __iter_with_nested_types = requires { | |
306 | typename _Iter::iterator_category; | |
307 | typename _Iter::value_type; | |
308 | typename _Iter::difference_type; | |
309 | typename _Iter::reference; | |
310 | }; | |
311 | ||
6d0dff49 JW |
312 | template<typename _Iter> |
313 | concept __iter_without_nested_types = !__iter_with_nested_types<_Iter>; | |
314 | ||
315 | template<typename _Iter, bool __use_arrow = false> | |
316 | struct __ptr | |
317 | { using type = void; }; | |
318 | ||
319 | template<typename _Iter> requires requires { typename _Iter::pointer; } | |
320 | struct __ptr<_Iter, true> | |
321 | { using type = typename _Iter::pointer; }; | |
322 | ||
323 | template<typename _Iter> requires requires { typename _Iter::pointer; } | |
324 | struct __ptr<_Iter, false> | |
325 | { using type = typename _Iter::pointer; }; | |
326 | ||
327 | template<typename _Iter> | |
328 | requires (!requires { typename _Iter::pointer; } | |
329 | && requires(_Iter& __it) { __it.operator->(); }) | |
330 | struct __ptr<_Iter, true> | |
331 | { using type = decltype(std::declval<_Iter&>().operator->()); }; | |
332 | ||
333 | template<typename _Iter> | |
334 | struct __ref | |
335 | { using type = iter_reference_t<_Iter>; }; | |
336 | ||
337 | template<typename _Iter> requires requires { typename _Iter::reference; } | |
338 | struct __ref<_Iter> | |
339 | { using type = typename _Iter::reference; }; | |
340 | ||
341 | template<typename _Iter> | |
342 | struct __cat | |
343 | { using type = input_iterator_tag; }; | |
344 | ||
345 | template<typename _Iter> | |
346 | requires requires { typename _Iter::iterator_category; } | |
347 | struct __cat<_Iter> | |
348 | { using type = typename _Iter::iterator_category; }; | |
349 | ||
350 | template<typename _Iter> | |
351 | requires (!requires { typename _Iter::iterator_category; } | |
352 | && __detail::__cpp17_randacc_iterator<_Iter>) | |
353 | struct __cat<_Iter> | |
354 | { using type = random_access_iterator_tag; }; | |
355 | ||
356 | template<typename _Iter> | |
357 | requires (!requires { typename _Iter::iterator_category; } | |
358 | && __detail::__cpp17_bidi_iterator<_Iter>) | |
359 | struct __cat<_Iter> | |
360 | { using type = bidirectional_iterator_tag; }; | |
361 | ||
362 | template<typename _Iter> | |
363 | requires (!requires { typename _Iter::iterator_category; } | |
364 | && __detail::__cpp17_fwd_iterator<_Iter>) | |
365 | struct __cat<_Iter> | |
366 | { using type = forward_iterator_tag; }; | |
367 | ||
368 | template<typename _Iter> | |
369 | struct __diff | |
370 | { using type = void; }; | |
371 | ||
372 | template<typename _Iter> | |
373 | requires requires { | |
374 | typename incrementable_traits<_Iter>::difference_type; | |
375 | } | |
376 | struct __diff<_Iter> | |
377 | { | |
378 | using type = typename incrementable_traits<_Iter>::difference_type; | |
379 | }; | |
380 | ||
381 | } // namespace __detail | |
382 | ||
383 | template<typename _Iterator> | |
384 | requires __detail::__iter_with_nested_types<_Iterator> | |
385 | struct __iterator_traits<_Iterator, void> | |
386 | { | |
387 | using iterator_category = typename _Iterator::iterator_category; | |
388 | using value_type = typename _Iterator::value_type; | |
389 | using difference_type = typename _Iterator::difference_type; | |
390 | using pointer = typename __detail::__ptr<_Iterator>::type; | |
391 | using reference = typename _Iterator::reference; | |
392 | }; | |
393 | ||
394 | template<typename _Iterator> | |
395 | requires __detail::__iter_without_nested_types<_Iterator> | |
396 | && __detail::__cpp17_input_iterator<_Iterator> | |
397 | struct __iterator_traits<_Iterator, void> | |
398 | { | |
399 | using iterator_category = typename __detail::__cat<_Iterator>::type; | |
400 | using value_type | |
401 | = typename readable_traits<_Iterator>::value_type; | |
402 | using difference_type | |
403 | = typename incrementable_traits<_Iterator>::difference_type; | |
404 | using pointer = typename __detail::__ptr<_Iterator, true>::type; | |
405 | using reference = typename __detail::__ref<_Iterator>::type; | |
406 | }; | |
407 | ||
408 | template<typename _Iterator> | |
409 | requires __detail::__iter_without_nested_types<_Iterator> | |
410 | && __detail::__cpp17_iterator<_Iterator> | |
411 | struct __iterator_traits<_Iterator, void> | |
412 | { | |
413 | using iterator_category = output_iterator_tag; | |
414 | using value_type = void; | |
415 | using difference_type = typename __detail::__diff<_Iterator>::type; | |
416 | using pointer = void; | |
417 | using reference = void; | |
418 | }; | |
419 | ||
420 | namespace __detail | |
421 | { | |
422 | template<typename _Iter> | |
423 | struct __iter_concept_impl | |
424 | { }; | |
425 | ||
426 | template<typename _Iter> | |
427 | requires requires { typename __iter_traits<_Iter>::iterator_concept; } | |
428 | struct __iter_concept_impl<_Iter> | |
429 | { using type = typename __iter_traits<_Iter>::iterator_concept; }; | |
430 | ||
431 | template<typename _Iter> | |
432 | requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } | |
433 | && requires { typename __iter_traits<_Iter>::iterator_category; }) | |
434 | struct __iter_concept_impl<_Iter> | |
435 | { using type = typename __iter_traits<_Iter>::iterator_category; }; | |
436 | ||
437 | template<typename _Iter> | |
438 | requires (!requires { typename __iter_traits<_Iter>::iterator_concept; } | |
439 | && !requires { typename __iter_traits<_Iter>::iterator_category; } | |
440 | && __primary_traits_iter<_Iter>) | |
441 | struct __iter_concept_impl<_Iter> | |
442 | { using type = random_access_iterator_tag; }; | |
443 | ||
444 | // ITER_TRAITS | |
445 | template<typename _Iter> | |
446 | using __iter_concept = typename __iter_concept_impl<_Iter>::type; | |
447 | } // namespace __detail | |
448 | ||
449 | /// Requirements for types that are readable by applying operator*. | |
450 | template<typename _In> | |
451 | concept readable = requires | |
452 | { | |
453 | typename iter_value_t<_In>; | |
454 | typename iter_reference_t<_In>; | |
455 | typename iter_rvalue_reference_t<_In>; | |
456 | } | |
457 | && common_reference_with<iter_reference_t<_In>&&, iter_value_t<_In>&> | |
458 | && common_reference_with<iter_reference_t<_In>&&, | |
459 | iter_rvalue_reference_t<_In>&&> | |
460 | && common_reference_with<iter_rvalue_reference_t<_In>&&, | |
461 | const iter_value_t<_In>&>; | |
462 | ||
463 | namespace __detail | |
464 | { | |
465 | // FIXME: needed due to PR c++/67704 | |
466 | template<readable _Tp> | |
467 | struct __iter_common_ref | |
468 | : common_reference<iter_reference_t<_Tp>, iter_value_t<_Tp>&> | |
469 | { }; | |
470 | ||
471 | // FIXME: needed due to PR c++/67704 | |
472 | template<typename _Fn, typename... _Is> | |
473 | struct __indirect_result | |
474 | { }; | |
475 | ||
476 | template<typename _Fn, typename... _Is> | |
477 | requires (readable<_Is> && ...) | |
478 | && invocable<_Fn, iter_reference_t<_Is>...> | |
479 | struct __indirect_result<_Fn, _Is...> | |
480 | : invoke_result<_Fn, iter_reference_t<_Is>...> | |
481 | { }; | |
482 | } // namespace __detail | |
483 | ||
484 | template<typename _Tp> | |
485 | using iter_common_reference_t | |
486 | = typename __detail::__iter_common_ref<_Tp>::type; | |
487 | ||
488 | /// Requirements for writing a value into an iterator's referenced object. | |
489 | template<typename _Out, typename _Tp> | |
490 | concept writable = requires(_Out&& __o, _Tp&& __t) | |
491 | { | |
492 | *__o = std::forward<_Tp>(__t); | |
493 | *std::forward<_Out>(__o) = std::forward<_Tp>(__t); | |
494 | const_cast<const iter_reference_t<_Out>&&>(*__o) | |
495 | = std::forward<_Tp>(__t); | |
496 | const_cast<const iter_reference_t<_Out>&&>(*std::forward<_Out>(__o)) | |
497 | = std::forward<_Tp>(__t); | |
498 | }; | |
499 | ||
500 | /// Requirements on types that can be incremented with ++. | |
501 | template<typename _Iter> | |
502 | concept weakly_incrementable = default_constructible<_Iter> | |
503 | && movable<_Iter> | |
504 | && requires(_Iter __i) | |
505 | { | |
506 | typename iter_difference_t<_Iter>; | |
507 | requires signed_integral<iter_difference_t<_Iter>>; | |
508 | { ++__i } -> same_as<_Iter&>; | |
509 | __i++; | |
510 | }; | |
511 | ||
512 | template<typename _Iter> | |
513 | concept incrementable = regular<_Iter> && weakly_incrementable<_Iter> | |
514 | && requires(_Iter __i) { { __i++ } -> same_as<_Iter>; }; | |
515 | ||
516 | template<typename _Iter> | |
517 | concept input_or_output_iterator | |
518 | = requires(_Iter __i) { { *__i } -> __detail::__can_reference; } | |
519 | && weakly_incrementable<_Iter>; | |
520 | ||
521 | template<typename _Sent, typename _Iter> | |
522 | concept sentinel_for = semiregular<_Sent> | |
523 | && input_or_output_iterator<_Iter> | |
524 | && __detail::__weakly_eq_cmp_with<_Sent, _Iter>; | |
525 | ||
526 | template<typename _Sent, typename _Iter> | |
d99828ee | 527 | inline constexpr bool disable_sized_sentinel_for = false; |
6d0dff49 JW |
528 | |
529 | template<typename _Sent, typename _Iter> | |
530 | concept sized_sentinel_for = sentinel_for<_Sent, _Iter> | |
d99828ee | 531 | && !disable_sized_sentinel_for<remove_cv_t<_Sent>, remove_cv_t<_Iter>> |
6d0dff49 JW |
532 | && requires(const _Iter& __i, const _Sent& __s) |
533 | { | |
534 | { __s - __i } -> same_as<iter_difference_t<_Iter>>; | |
535 | { __i - __s } -> same_as<iter_difference_t<_Iter>>; | |
536 | }; | |
537 | ||
538 | template<typename _Iter> | |
539 | concept input_iterator = input_or_output_iterator<_Iter> | |
540 | && readable<_Iter> | |
541 | && requires { typename __detail::__iter_concept<_Iter>; } | |
542 | && derived_from<__detail::__iter_concept<_Iter>, input_iterator_tag>; | |
543 | ||
544 | template<typename _Iter, typename _Tp> | |
545 | concept output_iterator = input_or_output_iterator<_Iter> | |
546 | && writable<_Iter, _Tp> | |
547 | && requires(_Iter __i, _Tp&& __t) { *__i++ = std::forward<_Tp>(__t); }; | |
548 | ||
549 | template<typename _Iter> | |
550 | concept forward_iterator = input_iterator<_Iter> | |
551 | && derived_from<__detail::__iter_concept<_Iter>, forward_iterator_tag> | |
552 | && incrementable<_Iter> && sentinel_for<_Iter, _Iter>; | |
553 | ||
554 | template<typename _Iter> | |
555 | concept bidirectional_iterator = forward_iterator<_Iter> | |
556 | && derived_from<__detail::__iter_concept<_Iter>, | |
557 | bidirectional_iterator_tag> | |
558 | && requires(_Iter __i) | |
559 | { | |
560 | { --__i } -> same_as<_Iter&>; | |
561 | { __i-- } -> same_as<_Iter>; | |
562 | }; | |
563 | ||
564 | template<typename _Iter> | |
565 | concept random_access_iterator = bidirectional_iterator<_Iter> | |
566 | && derived_from<__detail::__iter_concept<_Iter>, | |
567 | random_access_iterator_tag> | |
568 | && totally_ordered<_Iter> && sized_sentinel_for<_Iter, _Iter> | |
569 | && requires(_Iter __i, const _Iter __j, | |
570 | const iter_difference_t<_Iter> __n) | |
571 | { | |
572 | { __i += __n } -> same_as<_Iter&>; | |
573 | { __j + __n } -> same_as<_Iter>; | |
574 | { __n + __j } -> same_as<_Iter>; | |
575 | { __i -= __n } -> same_as<_Iter&>; | |
576 | { __j - __n } -> same_as<_Iter>; | |
577 | { __j[__n] } -> same_as<iter_reference_t<_Iter>>; | |
578 | }; | |
579 | ||
580 | template<typename _Iter> | |
581 | concept contiguous_iterator = random_access_iterator<_Iter> | |
582 | && derived_from<__detail::__iter_concept<_Iter>, contiguous_iterator_tag> | |
583 | && is_lvalue_reference_v<iter_reference_t<_Iter>> | |
584 | && same_as<iter_value_t<_Iter>, remove_cvref_t<iter_reference_t<_Iter>>> | |
585 | && requires(const _Iter& __i) | |
586 | { | |
587 | { std::to_address(__i) } | |
588 | -> same_as<add_pointer_t<iter_reference_t<_Iter>>>; | |
589 | }; | |
590 | ||
591 | // [indirectcallable], indirect callable requirements | |
592 | ||
593 | // [indirectcallable.indirectinvocable], indirect callables | |
594 | ||
595 | template<typename _Fn, typename _Iter> | |
596 | concept indirectly_unary_invocable = readable<_Iter> | |
597 | && copy_constructible<_Fn> && invocable<_Fn&, iter_value_t<_Iter>&> | |
598 | && invocable<_Fn&, iter_reference_t<_Iter>> | |
599 | && invocable<_Fn&, iter_common_reference_t<_Iter>> | |
600 | && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, | |
601 | invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; | |
602 | ||
603 | template<typename _Fn, typename _Iter> | |
604 | concept indirectly_regular_unary_invocable = readable<_Iter> | |
605 | && copy_constructible<_Fn> | |
606 | && regular_invocable<_Fn&, iter_value_t<_Iter>&> | |
607 | && regular_invocable<_Fn&, iter_reference_t<_Iter>> | |
608 | && regular_invocable<_Fn&, iter_common_reference_t<_Iter>> | |
609 | && common_reference_with<invoke_result_t<_Fn&, iter_value_t<_Iter>&>, | |
610 | invoke_result_t<_Fn&, iter_reference_t<_Iter>>>; | |
611 | ||
612 | template<typename _Fn, typename _Iter> | |
613 | concept indirect_unary_predicate = readable<_Iter> | |
614 | && copy_constructible<_Fn> && predicate<_Fn&, iter_value_t<_Iter>&> | |
615 | && predicate<_Fn&, iter_reference_t<_Iter>> | |
616 | && predicate<_Fn&, iter_common_reference_t<_Iter>>; | |
617 | ||
618 | template<typename _Fn, typename _I1, typename _I2 = _I1> | |
619 | concept indirect_relation = readable<_I1> && readable<_I2> | |
620 | && copy_constructible<_Fn> | |
621 | && relation<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> | |
622 | && relation<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> | |
623 | && relation<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> | |
624 | && relation<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> | |
625 | && relation<_Fn&, iter_common_reference_t<_I1>, | |
626 | iter_common_reference_t<_I2>>; | |
627 | ||
628 | template<typename _Fn, typename _I1, typename _I2 = _I1> | |
629 | concept indirect_strict_weak_order = readable<_I1> && readable<_I2> | |
630 | && copy_constructible<_Fn> | |
631 | && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_value_t<_I2>&> | |
632 | && strict_weak_order<_Fn&, iter_value_t<_I1>&, iter_reference_t<_I2>> | |
633 | && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_value_t<_I2>&> | |
634 | && strict_weak_order<_Fn&, iter_reference_t<_I1>, iter_reference_t<_I2>> | |
635 | && strict_weak_order<_Fn&, iter_common_reference_t<_I1>, | |
636 | iter_common_reference_t<_I2>>; | |
637 | ||
638 | template<typename _Fn, typename... _Is> | |
639 | using indirect_result_t = typename | |
640 | __detail::__indirect_result<_Fn, iter_reference_t<_Is>...>::type; | |
641 | ||
642 | /// [projected], projected | |
643 | template<readable _Iter, indirectly_regular_unary_invocable<_Iter> _Proj> | |
644 | struct projected | |
645 | { | |
646 | using value_type = remove_cvref_t<indirect_result_t<_Proj&, _Iter>>; | |
647 | indirect_result_t<_Proj&, _Iter> operator*() const; // not defined | |
648 | }; | |
649 | ||
650 | template<weakly_incrementable _Iter, typename _Proj> | |
651 | struct incrementable_traits<projected<_Iter, _Proj>> | |
652 | { using difference_type = iter_difference_t<_Iter>; }; | |
653 | ||
654 | // [alg.req], common algorithm requirements | |
655 | ||
656 | /// [alg.req.ind.move], concept `indirectly_movable` | |
657 | ||
658 | template<typename _In, typename _Out> | |
659 | concept indirectly_movable = readable<_In> | |
660 | && writable<_Out, iter_rvalue_reference_t<_In>>; | |
661 | ||
662 | template<typename _In, typename _Out> | |
663 | concept indirectly_movable_storable = indirectly_movable<_In, _Out> | |
664 | && writable<_Out, iter_value_t<_In>> && movable<iter_value_t<_In>> | |
665 | && constructible_from<iter_value_t<_In>, iter_rvalue_reference_t<_In>> | |
666 | && assignable_from<iter_value_t<_In>&, iter_rvalue_reference_t<_In>>; | |
667 | ||
668 | /// [alg.req.ind.copy], concept `indirectly_copyable` | |
669 | template<typename _In, typename _Out> | |
670 | concept indirectly_copyable = readable<_In> | |
671 | && writable<_Out, iter_reference_t<_In>>; | |
672 | ||
673 | template<typename _In, typename _Out> | |
674 | concept indirectly_copyable_storable = indirectly_copyable<_In, _Out> | |
675 | && writable<_Out, const iter_value_t<_In>&> | |
676 | && copyable<iter_value_t<_In>> | |
677 | && constructible_from<iter_value_t<_In>, iter_reference_t<_In>> | |
678 | && assignable_from<iter_value_t<_In>&, iter_reference_t<_In>>; | |
679 | ||
680 | namespace ranges | |
681 | { | |
682 | namespace __cust_iswap | |
683 | { | |
684 | template<typename _It1, typename _It2> | |
685 | void iter_swap(_It1&, _It2&) = delete; | |
686 | ||
687 | template<typename _Tp, typename _Up> | |
688 | concept __adl_iswap | |
689 | = (std::__detail::__class_or_enum<remove_reference_t<_Tp>> | |
690 | || std::__detail::__class_or_enum<remove_reference_t<_Up>>) | |
691 | && requires(_Tp&& __t, _Up&& __u) { | |
692 | iter_swap(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)); | |
693 | }; | |
694 | ||
695 | template<typename _Xp, typename _Yp> | |
696 | constexpr iter_value_t<remove_reference_t<_Xp>> | |
697 | __iter_exchange_move(_Xp&& __x, _Yp&& __y) | |
698 | noexcept(noexcept(iter_value_t<remove_reference_t<_Xp>>(iter_move(__x))) | |
699 | && noexcept(*__x = iter_move(__y))) | |
700 | { | |
701 | iter_value_t<remove_reference_t<_Xp>> __old_value(iter_move(__x)); | |
702 | *__x = iter_move(__y); | |
703 | return __old_value; | |
704 | } | |
705 | ||
706 | struct _IterSwap | |
707 | { | |
708 | private: | |
709 | template<typename _Tp, typename _Up> | |
710 | static constexpr bool | |
711 | _S_noexcept() | |
712 | { | |
713 | if constexpr (__adl_iswap<_Tp, _Up>) | |
714 | return noexcept(iter_swap(std::declval<_Tp>(), | |
715 | std::declval<_Up>())); | |
716 | else if constexpr (readable<_Tp> && readable<_Up> | |
717 | && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) | |
718 | return noexcept(ranges::swap(*std::declval<_Tp>(), | |
719 | *std::declval<_Up>())); | |
720 | else | |
721 | return noexcept(*std::declval<_Tp>() | |
722 | = __iter_exchange_move(std::declval<_Up>(), | |
723 | std::declval<_Tp>())); | |
724 | } | |
725 | ||
726 | public: | |
727 | template<typename _Tp, typename _Up> | |
728 | requires __adl_iswap<_Tp, _Up> | |
729 | || (readable<_Tp> && readable<_Up> | |
730 | && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) | |
731 | || (indirectly_movable_storable<_Tp, _Up> | |
732 | && indirectly_movable_storable<_Up, _Tp>) | |
733 | constexpr void | |
734 | operator()(_Tp&& __e1, _Up&& __e2) const | |
735 | noexcept(_S_noexcept<_Tp, _Up>()) | |
736 | { | |
737 | if constexpr (__adl_iswap<_Tp, _Up>) | |
738 | iter_swap(static_cast<_Tp&&>(__e1), static_cast<_Up&&>(__e2)); | |
739 | else if constexpr (readable<_Tp> && readable<_Up> | |
740 | && swappable_with<iter_reference_t<_Tp>, iter_reference_t<_Up>>) | |
741 | ranges::swap(*__e1, *__e2); | |
742 | else | |
743 | *__e1 = __iter_exchange_move(__e2, __e1); | |
744 | } | |
745 | }; | |
746 | } // namespace __cust_iswap | |
747 | ||
748 | inline namespace __cust | |
749 | { | |
750 | inline constexpr __cust_iswap::_IterSwap iter_swap{}; | |
751 | } // inline namespace __cust | |
752 | ||
753 | } // namespace ranges | |
754 | ||
755 | /// [alg.req.ind.swap], concept `indirectly_swappable` | |
756 | template<typename _I1, typename _I2 = _I1> | |
757 | concept indirectly_swappable = readable<_I1> && readable<_I2> | |
758 | && requires(_I1& __i1, _I2& __i2) | |
759 | { | |
760 | ranges::iter_swap(__i1, __i1); | |
761 | ranges::iter_swap(__i2, __i2); | |
762 | ranges::iter_swap(__i1, __i2); | |
763 | ranges::iter_swap(__i2, __i1); | |
764 | }; | |
765 | ||
766 | /// [alg.req.ind.cmp], concept `indirectly_comparable` | |
767 | template<typename _I1, typename _I2, typename _Rel, typename _P1 = identity, | |
768 | typename _P2 = identity> | |
769 | concept indirectly_comparable | |
770 | = indirect_relation<_Rel, projected<_I1, _P1>, projected<_I2, _P2>>; | |
771 | ||
772 | /// [alg.req.permutable], concept `permutable` | |
773 | template<typename _Iter> | |
774 | concept permutable = forward_iterator<_Iter> | |
775 | && indirectly_movable_storable<_Iter, _Iter> | |
776 | && indirectly_swappable<_Iter, _Iter>; | |
777 | ||
778 | /// [alg.req.mergeable], concept `mergeable` | |
779 | template<typename _I1, typename _I2, typename _Out, | |
780 | typename _Rel = ranges::less, typename _P1 = identity, | |
781 | typename _P2 = identity> | |
782 | concept mergeable = input_iterator<_I1> && input_iterator<_I2> | |
783 | && weakly_incrementable<_Out> && indirectly_copyable<_I1, _Out> | |
784 | && indirectly_copyable<_I2, _Out> | |
785 | && indirect_strict_weak_order<_Rel, projected<_I1, _P1>, | |
786 | projected<_I2, _P2>>; | |
787 | ||
788 | /// [alg.req.sortable], concept `sortable` | |
789 | template<typename _Iter, typename _Rel = ranges::less, | |
790 | typename _Proj = identity> | |
791 | concept sortable = permutable<_Iter> | |
792 | && indirect_strict_weak_order<_Rel, projected<_Iter, _Proj>>; | |
793 | ||
794 | struct unreachable_sentinel_t | |
795 | { | |
796 | template<weakly_incrementable _It> | |
797 | friend constexpr bool | |
798 | operator==(unreachable_sentinel_t, const _It&) noexcept | |
799 | { return false; } | |
6d0dff49 JW |
800 | }; |
801 | ||
802 | inline constexpr unreachable_sentinel_t unreachable_sentinel{}; | |
803 | ||
804 | struct default_sentinel_t { }; | |
805 | inline constexpr default_sentinel_t default_sentinel{}; | |
806 | ||
807 | _GLIBCXX_END_NAMESPACE_VERSION | |
808 | } // namespace std | |
809 | #endif // C++20 library concepts | |
810 | #endif // _ITERATOR_CONCEPTS_H |