Debian Codegraph @

libcxx/include/__cxx03/__iterator/iterator_traits.h

raw
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___CXX03___ITERATOR_ITERATOR_TRAITS_H
11 #define _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H
12
13 #include <__cxx03/__config>
14 #include <__cxx03/__fwd/pair.h>
15 #include <__cxx03/__type_traits/conditional.h>
16 #include <__cxx03/__type_traits/disjunction.h>
17 #include <__cxx03/__type_traits/is_convertible.h>
18 #include <__cxx03/__type_traits/is_object.h>
19 #include <__cxx03/__type_traits/is_primary_template.h>
20 #include <__cxx03/__type_traits/is_reference.h>
21 #include <__cxx03/__type_traits/is_valid_expansion.h>
22 #include <__cxx03/__type_traits/remove_const.h>
23 #include <__cxx03/__type_traits/remove_cv.h>
24 #include <__cxx03/__type_traits/remove_cvref.h>
25 #include <__cxx03/__type_traits/void_t.h>
26 #include <__cxx03/__utility/declval.h>
27 #include <__cxx03/cstddef>
28
29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
30 # pragma GCC system_header
31 #endif
32
33 _LIBCPP_BEGIN_NAMESPACE_STD
34
35 template <class _Iter>
36 struct _LIBCPP_TEMPLATE_VIS iterator_traits;
37
38 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
39 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
40 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {};
41 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
42 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
43
44 template <class _Iter>
45 struct __iter_traits_cache {
46 using type = _If< __is_primary_template<iterator_traits<_Iter> >::value, _Iter, iterator_traits<_Iter> >;
47 };
48 template <class _Iter>
49 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type;
50
51 struct __iter_concept_concept_test {
52 template <class _Iter>
53 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept;
54 };
55 struct __iter_concept_category_test {
56 template <class _Iter>
57 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category;
58 };
59 struct __iter_concept_random_fallback {
60 template <class _Iter>
61 using _Apply = __enable_if_t< __is_primary_template<iterator_traits<_Iter> >::value, random_access_iterator_tag >;
62 };
63
64 template <class _Iter, class _Tester>
65 struct __test_iter_concept : _IsValidExpansion<_Tester::template _Apply, _Iter>, _Tester {};
66
67 template <class _Iter>
68 struct __iter_concept_cache {
69 using type = _Or< __test_iter_concept<_Iter, __iter_concept_concept_test>,
70 __test_iter_concept<_Iter, __iter_concept_category_test>,
71 __test_iter_concept<_Iter, __iter_concept_random_fallback> >;
72 };
73
74 template <class _Iter>
75 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;
76
77 template <class _Tp>
78 struct __has_iterator_typedefs {
79 private:
80 template <class _Up>
81 static false_type __test(...);
82 template <class _Up>
83 static true_type
84 __test(__void_t<typename _Up::iterator_category>* = nullptr,
85 __void_t<typename _Up::difference_type>* = nullptr,
86 __void_t<typename _Up::value_type>* = nullptr,
87 __void_t<typename _Up::reference>* = nullptr,
88 __void_t<typename _Up::pointer>* = nullptr);
89
90 public:
91 static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::value;
92 };
93
94 template <class _Tp>
95 struct __has_iterator_category {
96 private:
97 template <class _Up>
98 static false_type __test(...);
99 template <class _Up>
100 static true_type __test(typename _Up::iterator_category* = nullptr);
101
102 public:
103 static const bool value = decltype(__test<_Tp>(nullptr))::value;
104 };
105
106 template <class _Tp>
107 struct __has_iterator_concept {
108 private:
109 template <class _Up>
110 static false_type __test(...);
111 template <class _Up>
112 static true_type __test(typename _Up::iterator_concept* = nullptr);
113
114 public:
115 static const bool value = decltype(__test<_Tp>(nullptr))::value;
116 };
117
118 template <class _Iter, bool>
119 struct __iterator_traits {};
120
121 template <class _Iter, bool>
122 struct __iterator_traits_impl {};
123
124 template <class _Iter>
125 struct __iterator_traits_impl<_Iter, true> {
126 typedef typename _Iter::difference_type difference_type;
127 typedef typename _Iter::value_type value_type;
128 typedef typename _Iter::pointer pointer;
129 typedef typename _Iter::reference reference;
130 typedef typename _Iter::iterator_category iterator_category;
131 };
132
133 template <class _Iter>
134 struct __iterator_traits<_Iter, true>
135 : __iterator_traits_impl< _Iter,
136 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
137 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value > {};
138
139 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
140 // exists. Else iterator_traits<Iterator> will be an empty class. This is a
141 // conforming extension which allows some programs to compile and behave as
142 // the client expects instead of failing at compile time.
143
144 template <class _Iter>
145 struct _LIBCPP_TEMPLATE_VIS iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
146 using __primary_template = iterator_traits;
147 };
148
149 template <class _Tp>
150 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> {
151 typedef ptrdiff_t difference_type;
152 typedef __remove_cv_t<_Tp> value_type;
153 typedef _Tp* pointer;
154 typedef _Tp& reference;
155 typedef random_access_iterator_tag iterator_category;
156 };
157
158 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
159 struct __has_iterator_category_convertible_to : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> {
160 };
161
162 template <class _Tp, class _Up>
163 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
164
165 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
166 struct __has_iterator_concept_convertible_to : is_convertible<typename _Tp::iterator_concept, _Up> {};
167
168 template <class _Tp, class _Up>
169 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
170
171 template <class _Tp>
172 using __has_input_iterator_category = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;
173
174 template <class _Tp>
175 using __has_forward_iterator_category = __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;
176
177 template <class _Tp>
178 using __has_bidirectional_iterator_category = __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;
179
180 template <class _Tp>
181 using __has_random_access_iterator_category = __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>;
182
183 // __libcpp_is_contiguous_iterator determines if an iterator is known by
184 // libc++ to be contiguous, either because it advertises itself as such
185 // (in C++20) or because it is a pointer type or a known trivial wrapper
186 // around a (possibly fancy) pointer type, such as __wrap_iter<T*>.
187 // Such iterators receive special "contiguous" optimizations in
188 // std::copy and std::sort.
189 //
190 template <class _Tp>
191 struct __libcpp_is_contiguous_iterator : false_type {};
192
193 // Any native pointer which is an iterator is also a contiguous iterator.
194 template <class _Up>
195 struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};
196
197 template <class _Iter>
198 class __wrap_iter;
199
200 template <class _Tp>
201 using __has_exactly_input_iterator_category =
202 integral_constant<bool,
203 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
204 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>;
205
206 template <class _Tp>
207 using __has_exactly_forward_iterator_category =
208 integral_constant<bool,
209 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value &&
210 !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>;
211
212 template <class _Tp>
213 using __has_exactly_bidirectional_iterator_category =
214 integral_constant<bool,
215 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value &&
216 !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>;
217
218 template <class _InputIterator>
219 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
220
221 template <class _InputIterator>
222 using __iter_key_type = __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
223
224 template <class _InputIterator>
225 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
226
227 template <class _InputIterator>
228 using __iter_to_alloc_type =
229 pair<const typename iterator_traits<_InputIterator>::value_type::first_type,
230 typename iterator_traits<_InputIterator>::value_type::second_type>;
231
232 template <class _Iter>
233 using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category;
234
235 template <class _Iter>
236 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
237
238 template <class _Iter>
239 using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;
240
241 template <class _Iter>
242 using __iter_reference = typename iterator_traits<_Iter>::reference;
243
244 _LIBCPP_END_NAMESPACE_STD
245
246 #endif // _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H