Warning: This file is not a C or C++ file. It does not have highlighting.

1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
11#define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
12
13#include <__concepts/arithmetic.h>
14#include <__concepts/constructible.h>
15#include <__concepts/convertible_to.h>
16#include <__concepts/copyable.h>
17#include <__concepts/equality_comparable.h>
18#include <__concepts/same_as.h>
19#include <__concepts/totally_ordered.h>
20#include <__config>
21#include <__cstddef/ptrdiff_t.h>
22#include <__fwd/pair.h>
23#include <__iterator/incrementable_traits.h>
24#include <__iterator/readable_traits.h>
25#include <__tuple/tuple_element.h>
26#include <__type_traits/common_reference.h>
27#include <__type_traits/conditional.h>
28#include <__type_traits/detected_or.h>
29#include <__type_traits/disjunction.h>
30#include <__type_traits/integral_constant.h>
31#include <__type_traits/is_convertible.h>
32#include <__type_traits/is_object.h>
33#include <__type_traits/is_primary_template.h>
34#include <__type_traits/is_reference.h>
35#include <__type_traits/is_referenceable.h>
36#include <__type_traits/nat.h>
37#include <__type_traits/remove_const.h>
38#include <__type_traits/remove_cv.h>
39#include <__type_traits/remove_cvref.h>
40#include <__type_traits/void_t.h>
41#include <__utility/declval.h>
42
43#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
44# pragma GCC system_header
45#endif
46
47_LIBCPP_BEGIN_NAMESPACE_STD
48
49#if _LIBCPP_STD_VER >= 20
50
51template <class _Tp>
52concept __dereferenceable = requires(_Tp& __t) {
53 { *__t } -> __referenceable; // not required to be equality-preserving
54};
55
56// [iterator.traits]
57template <__dereferenceable _Tp>
58using iter_reference_t = decltype(*std::declval<_Tp&>());
59
60#endif // _LIBCPP_STD_VER >= 20
61
62template <class _Iter>
63struct iterator_traits;
64
65struct input_iterator_tag {};
66struct output_iterator_tag {};
67struct forward_iterator_tag : public input_iterator_tag {};
68struct bidirectional_iterator_tag : public forward_iterator_tag {};
69struct random_access_iterator_tag : public bidirectional_iterator_tag {};
70#if _LIBCPP_STD_VER >= 20
71struct contiguous_iterator_tag : public random_access_iterator_tag {};
72#endif
73
74template <class _Tp>
75struct __has_iterator_typedefs {
76private:
77 template <class _Up>
78 static false_type __test(...);
79 template <class _Up>
80 static true_type
81 __test(__void_t<typename _Up::iterator_category>* = nullptr,
82 __void_t<typename _Up::difference_type>* = nullptr,
83 __void_t<typename _Up::value_type>* = nullptr,
84 __void_t<typename _Up::reference>* = nullptr,
85 __void_t<typename _Up::pointer>* = nullptr);
86
87public:
88 static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::value;
89};
90
91#if _LIBCPP_STD_VER >= 20
92
93// The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements
94// from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to
95// a "detail" namespace indicating they have a niche use-case.
96namespace __iterator_traits_detail {
97template <class _Ip>
98concept __cpp17_iterator = requires(_Ip __i) {
99 { *__i } -> __referenceable;
100 { ++__i } -> same_as<_Ip&>;
101 { *__i++ } -> __referenceable;
102} && copyable<_Ip>;
103
104template <class _Ip>
105concept __cpp17_input_iterator = __cpp17_iterator<_Ip> && equality_comparable<_Ip> && requires(_Ip __i) {
106 typename incrementable_traits<_Ip>::difference_type;
107 typename indirectly_readable_traits<_Ip>::value_type;
108 typename common_reference_t<iter_reference_t<_Ip>&&, typename indirectly_readable_traits<_Ip>::value_type&>;
109 typename common_reference_t<decltype(*__i++)&&, typename indirectly_readable_traits<_Ip>::value_type&>;
110 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>;
111};
112
113template <class _Ip>
114concept __cpp17_forward_iterator =
115 __cpp17_input_iterator<_Ip> && constructible_from<_Ip> && is_reference_v<iter_reference_t<_Ip>> &&
116 same_as<remove_cvref_t<iter_reference_t<_Ip>>, typename indirectly_readable_traits<_Ip>::value_type> &&
117 requires(_Ip __i) {
118 { __i++ } -> convertible_to<_Ip const&>;
119 { *__i++ } -> same_as<iter_reference_t<_Ip>>;
120 };
121
122template <class _Ip>
123concept __cpp17_bidirectional_iterator = __cpp17_forward_iterator<_Ip> && requires(_Ip __i) {
124 { --__i } -> same_as<_Ip&>;
125 { __i-- } -> convertible_to<_Ip const&>;
126 { *__i-- } -> same_as<iter_reference_t<_Ip>>;
127};
128
129template <class _Ip>
130concept __cpp17_random_access_iterator =
131 __cpp17_bidirectional_iterator<_Ip> && totally_ordered<_Ip> &&
132 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {
133 { __i += __n } -> same_as<_Ip&>;
134 { __i -= __n } -> same_as<_Ip&>;
135 { __i + __n } -> same_as<_Ip>;
136 { __n + __i } -> same_as<_Ip>;
137 { __i - __n } -> same_as<_Ip>;
138 { __i - __i } -> same_as<decltype(__n)>; // NOLINT(misc-redundant-expression) ; This is llvm.org/PR54114
139 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>;
140 };
141} // namespace __iterator_traits_detail
142
143template <class _Ip>
144concept __has_member_reference = requires { typename _Ip::reference; };
145
146template <class _Ip>
147concept __has_member_pointer = requires { typename _Ip::pointer; };
148
149template <class _Ip>
150concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
151
152template <class _Ip>
153concept __specifies_members = requires {
154 typename _Ip::value_type;
155 typename _Ip::difference_type;
156 requires __has_member_reference<_Ip>;
157 requires __has_member_iterator_category<_Ip>;
158};
159
160template <class _Tp>
161concept __cpp17_iterator_missing_members = !__specifies_members<_Tp> && __iterator_traits_detail::__cpp17_iterator<_Tp>;
162
163template <class _Tp>
164concept __cpp17_input_iterator_missing_members =
165 __cpp17_iterator_missing_members<_Tp> && __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
166
167// Otherwise, `pointer` names `void`.
168template <class>
169struct __iterator_traits_member_pointer_or_arrow_or_void {
170 using type _LIBCPP_NODEBUG = void;
171};
172
173// [iterator.traits]/3.2.1
174// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
175template <__has_member_pointer _Ip>
176struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
177 using type _LIBCPP_NODEBUG = typename _Ip::pointer;
178};
179
180// Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
181// type.
182template <class _Ip>
183 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)
184struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
185 using type _LIBCPP_NODEBUG = decltype(std::declval<_Ip&>().operator->());
186};
187
188// Otherwise, `reference` names `iter-reference-t<I>`.
189template <class _Ip>
190struct __iterator_traits_member_reference {
191 using type _LIBCPP_NODEBUG = iter_reference_t<_Ip>;
192};
193
194// [iterator.traits]/3.2.2
195// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
196template <__has_member_reference _Ip>
197struct __iterator_traits_member_reference<_Ip> {
198 using type _LIBCPP_NODEBUG = typename _Ip::reference;
199};
200
201// [iterator.traits]/3.2.3.4
202// input_iterator_tag
203template <class _Ip>
204struct __deduce_iterator_category {
205 using type _LIBCPP_NODEBUG = input_iterator_tag;
206};
207
208// [iterator.traits]/3.2.3.1
209// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
210template <__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
211struct __deduce_iterator_category<_Ip> {
212 using type _LIBCPP_NODEBUG = random_access_iterator_tag;
213};
214
215// [iterator.traits]/3.2.3.2
216// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
217template <__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
218struct __deduce_iterator_category<_Ip> {
219 using type _LIBCPP_NODEBUG = bidirectional_iterator_tag;
220};
221
222// [iterator.traits]/3.2.3.3
223// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
224template <__iterator_traits_detail::__cpp17_forward_iterator _Ip>
225struct __deduce_iterator_category<_Ip> {
226 using type _LIBCPP_NODEBUG = forward_iterator_tag;
227};
228
229template <class _Ip>
230struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
231
232// [iterator.traits]/3.2.3
233// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names
234// that type.
235template <__has_member_iterator_category _Ip>
236struct __iterator_traits_iterator_category<_Ip> {
237 using type _LIBCPP_NODEBUG = typename _Ip::iterator_category;
238};
239
240// otherwise, it names void.
241template <class>
242struct __iterator_traits_difference_type {
243 using type _LIBCPP_NODEBUG = void;
244};
245
246// If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then
247// `difference_type` names that type;
248template <class _Ip>
249 requires requires { typename incrementable_traits<_Ip>::difference_type; }
250struct __iterator_traits_difference_type<_Ip> {
251 using type _LIBCPP_NODEBUG = typename incrementable_traits<_Ip>::difference_type;
252};
253
254// [iterator.traits]/3.4
255// Otherwise, `iterator_traits<I>` has no members by any of the above names.
256template <class>
257struct __iterator_traits {};
258
259template <class _Tp>
260using __pointer_member _LIBCPP_NODEBUG = typename _Tp::pointer;
261
262// [iterator.traits]/3.1
263// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and
264// `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members:
265template <__specifies_members _Ip>
266struct __iterator_traits<_Ip> {
267 using iterator_category = typename _Ip::iterator_category;
268 using value_type = typename _Ip::value_type;
269 using difference_type = typename _Ip::difference_type;
270 using pointer = __detected_or_t<void, __pointer_member, _Ip>;
271 using reference = typename _Ip::reference;
272};
273
274// [iterator.traits]/3.2
275// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,
276// `iterator-traits<I>` has the following publicly accessible members:
277template <__cpp17_input_iterator_missing_members _Ip>
278struct __iterator_traits<_Ip> {
279 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;
280 using value_type = typename indirectly_readable_traits<_Ip>::value_type;
281 using difference_type = typename incrementable_traits<_Ip>::difference_type;
282 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type;
283 using reference = typename __iterator_traits_member_reference<_Ip>::type;
284};
285
286// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then
287// `iterator_traits<I>` has the following publicly accessible members:
288template <__cpp17_iterator_missing_members _Ip>
289struct __iterator_traits<_Ip> {
290 using iterator_category = output_iterator_tag;
291 using value_type = void;
292 using difference_type = typename __iterator_traits_difference_type<_Ip>::type;
293 using pointer = void;
294 using reference = void;
295};
296
297template <class _Ip>
298struct iterator_traits : __iterator_traits<_Ip> {
299 using __primary_template _LIBCPP_NODEBUG = iterator_traits;
300};
301
302#else // _LIBCPP_STD_VER >= 20
303
304template <class _Iter, bool>
305struct __iterator_traits {};
306
307template <class _Iter, bool>
308struct __iterator_traits_impl {};
309
310template <class _Iter>
311struct __iterator_traits_impl<_Iter, true> {
312 typedef typename _Iter::difference_type difference_type;
313 typedef typename _Iter::value_type value_type;
314 typedef typename _Iter::pointer pointer;
315 typedef typename _Iter::reference reference;
316 typedef typename _Iter::iterator_category iterator_category;
317};
318
319template <class _Iter>
320struct __iterator_traits<_Iter, true>
321 : __iterator_traits_impl< _Iter,
322 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
323 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value > {};
324
325// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
326// exists. Else iterator_traits<Iterator> will be an empty class. This is a
327// conforming extension which allows some programs to compile and behave as
328// the client expects instead of failing at compile time.
329
330template <class _Iter>
331struct iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
332 using __primary_template _LIBCPP_NODEBUG = iterator_traits;
333};
334#endif // _LIBCPP_STD_VER >= 20
335
336template <class _Tp>
337#if _LIBCPP_STD_VER >= 20
338 requires is_object_v<_Tp>
339#endif
340struct iterator_traits<_Tp*> {
341 typedef ptrdiff_t difference_type;
342 typedef __remove_cv_t<_Tp> value_type;
343 typedef _Tp* pointer;
344 typedef _Tp& reference;
345 typedef random_access_iterator_tag iterator_category;
346#if _LIBCPP_STD_VER >= 20
347 typedef contiguous_iterator_tag iterator_concept;
348#endif
349};
350
351template <class _Tp>
352using __iterator_category _LIBCPP_NODEBUG = typename _Tp::iterator_category;
353
354template <class _Tp>
355using __iterator_concept _LIBCPP_NODEBUG = typename _Tp::iterator_concept;
356
357template <class _Tp, class _Up>
358using __has_iterator_category_convertible_to _LIBCPP_NODEBUG =
359 is_convertible<__detected_or_t<__nat, __iterator_category, iterator_traits<_Tp> >, _Up>;
360
361template <class _Tp, class _Up>
362using __has_iterator_concept_convertible_to _LIBCPP_NODEBUG =
363 is_convertible<__detected_or_t<__nat, __iterator_concept, _Tp>, _Up>;
364
365template <class _Tp>
366using __has_input_iterator_category _LIBCPP_NODEBUG = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;
367
368template <class _Tp>
369using __has_forward_iterator_category _LIBCPP_NODEBUG =
370 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;
371
372template <class _Tp>
373using __has_bidirectional_iterator_category _LIBCPP_NODEBUG =
374 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;
375
376template <class _Tp>
377using __has_random_access_iterator_category _LIBCPP_NODEBUG =
378 __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>;
379
380// __libcpp_is_contiguous_iterator determines if an iterator is known by
381// libc++ to be contiguous, either because it advertises itself as such
382// (in C++20) or because it is a pointer type or a known trivial wrapper
383// around a (possibly fancy) pointer type, such as __wrap_iter<T*>.
384// Such iterators receive special "contiguous" optimizations in
385// std::copy and std::sort.
386//
387#if _LIBCPP_STD_VER >= 20
388template <class _Tp>
389struct __libcpp_is_contiguous_iterator
390 : _Or< __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
391 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> > {};
392#else
393template <class _Tp>
394struct __libcpp_is_contiguous_iterator : false_type {};
395#endif
396
397// Any native pointer which is an iterator is also a contiguous iterator.
398template <class _Up>
399struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};
400
401template <class _Iter>
402class __wrap_iter;
403
404template <class _Tp>
405using __has_exactly_input_iterator_category _LIBCPP_NODEBUG =
406 integral_constant<bool,
407 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
408 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>;
409
410template <class _Tp>
411using __has_exactly_forward_iterator_category _LIBCPP_NODEBUG =
412 integral_constant<bool,
413 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value &&
414 !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>;
415
416template <class _Tp>
417using __has_exactly_bidirectional_iterator_category _LIBCPP_NODEBUG =
418 integral_constant<bool,
419 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value &&
420 !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>;
421
422template <class _InputIterator>
423using __iter_value_type _LIBCPP_NODEBUG = typename iterator_traits<_InputIterator>::value_type;
424
425#if _LIBCPP_STD_VER >= 23
426template <class _InputIterator>
427using __iter_key_type _LIBCPP_NODEBUG = remove_const_t<tuple_element_t<0, __iter_value_type<_InputIterator>>>;
428
429template <class _InputIterator>
430using __iter_mapped_type _LIBCPP_NODEBUG = tuple_element_t<1, __iter_value_type<_InputIterator>>;
431
432template <class _InputIterator>
433using __iter_to_alloc_type _LIBCPP_NODEBUG =
434 pair<const tuple_element_t<0, __iter_value_type<_InputIterator>>,
435 tuple_element_t<1, __iter_value_type<_InputIterator>>>;
436#else
437template <class _InputIterator>
438using __iter_key_type _LIBCPP_NODEBUG =
439 __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
440
441template <class _InputIterator>
442using __iter_mapped_type _LIBCPP_NODEBUG = typename iterator_traits<_InputIterator>::value_type::second_type;
443
444template <class _InputIterator>
445using __iter_to_alloc_type _LIBCPP_NODEBUG =
446 pair<const typename iterator_traits<_InputIterator>::value_type::first_type,
447 typename iterator_traits<_InputIterator>::value_type::second_type>;
448#endif // _LIBCPP_STD_VER >= 23
449
450template <class _Iter>
451using __iterator_category_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category;
452
453template <class _Iter>
454using __iterator_pointer_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::pointer;
455
456template <class _Iter>
457using __iter_diff_t _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type;
458
459template <class _Iter>
460using __iter_reference _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::reference;
461
462#if _LIBCPP_STD_VER >= 20
463
464// [readable.traits]
465
466// Let `RI` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes
467// `indirectly_readable_traits<RI>::value_type` if `iterator_traits<RI>` names a specialization
468// generated from the primary template, and `iterator_traits<RI>::value_type` otherwise.
469// This has to be in this file and not readable_traits.h to break the include cycle between the two.
470template <class _Ip>
471using iter_value_t =
472 typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,
473 indirectly_readable_traits<remove_cvref_t<_Ip> >,
474 iterator_traits<remove_cvref_t<_Ip> > >::value_type;
475
476#endif // _LIBCPP_STD_VER >= 20
477
478_LIBCPP_END_NAMESPACE_STD
479
480#endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
481

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__iterator/iterator_traits.h