File indexing completed on 2026-05-03 08:13:32
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010 #ifndef _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H
0011 #define _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H
0012
0013 #include <__cxx03/__concepts/arithmetic.h>
0014 #include <__cxx03/__concepts/constructible.h>
0015 #include <__cxx03/__concepts/convertible_to.h>
0016 #include <__cxx03/__concepts/copyable.h>
0017 #include <__cxx03/__concepts/equality_comparable.h>
0018 #include <__cxx03/__concepts/same_as.h>
0019 #include <__cxx03/__concepts/totally_ordered.h>
0020 #include <__cxx03/__config>
0021 #include <__cxx03/__fwd/pair.h>
0022 #include <__cxx03/__iterator/incrementable_traits.h>
0023 #include <__cxx03/__iterator/readable_traits.h>
0024 #include <__cxx03/__type_traits/common_reference.h>
0025 #include <__cxx03/__type_traits/conditional.h>
0026 #include <__cxx03/__type_traits/disjunction.h>
0027 #include <__cxx03/__type_traits/is_convertible.h>
0028 #include <__cxx03/__type_traits/is_object.h>
0029 #include <__cxx03/__type_traits/is_primary_template.h>
0030 #include <__cxx03/__type_traits/is_reference.h>
0031 #include <__cxx03/__type_traits/is_valid_expansion.h>
0032 #include <__cxx03/__type_traits/remove_const.h>
0033 #include <__cxx03/__type_traits/remove_cv.h>
0034 #include <__cxx03/__type_traits/remove_cvref.h>
0035 #include <__cxx03/__type_traits/void_t.h>
0036 #include <__cxx03/__utility/declval.h>
0037 #include <__cxx03/cstddef>
0038
0039 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0040 # pragma GCC system_header
0041 #endif
0042
0043 _LIBCPP_BEGIN_NAMESPACE_STD
0044
0045 #if _LIBCPP_STD_VER >= 20
0046
0047 template <class _Tp>
0048 using __with_reference = _Tp&;
0049
0050 template <class _Tp>
0051 concept __can_reference = requires { typename __with_reference<_Tp>; };
0052
0053 template <class _Tp>
0054 concept __dereferenceable = requires(_Tp& __t) {
0055 { *__t } -> __can_reference;
0056 };
0057
0058
0059 template <__dereferenceable _Tp>
0060 using iter_reference_t = decltype(*std::declval<_Tp&>());
0061
0062 #endif
0063
0064 template <class _Iter>
0065 struct _LIBCPP_TEMPLATE_VIS iterator_traits;
0066
0067 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
0068 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
0069 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {};
0070 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
0071 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
0072 #if _LIBCPP_STD_VER >= 20
0073 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {};
0074 #endif
0075
0076 template <class _Iter>
0077 struct __iter_traits_cache {
0078 using type = _If< __is_primary_template<iterator_traits<_Iter> >::value, _Iter, iterator_traits<_Iter> >;
0079 };
0080 template <class _Iter>
0081 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type;
0082
0083 struct __iter_concept_concept_test {
0084 template <class _Iter>
0085 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept;
0086 };
0087 struct __iter_concept_category_test {
0088 template <class _Iter>
0089 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category;
0090 };
0091 struct __iter_concept_random_fallback {
0092 template <class _Iter>
0093 using _Apply = __enable_if_t< __is_primary_template<iterator_traits<_Iter> >::value, random_access_iterator_tag >;
0094 };
0095
0096 template <class _Iter, class _Tester>
0097 struct __test_iter_concept : _IsValidExpansion<_Tester::template _Apply, _Iter>, _Tester {};
0098
0099 template <class _Iter>
0100 struct __iter_concept_cache {
0101 using type = _Or< __test_iter_concept<_Iter, __iter_concept_concept_test>,
0102 __test_iter_concept<_Iter, __iter_concept_category_test>,
0103 __test_iter_concept<_Iter, __iter_concept_random_fallback> >;
0104 };
0105
0106 template <class _Iter>
0107 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;
0108
0109 template <class _Tp>
0110 struct __has_iterator_typedefs {
0111 private:
0112 template <class _Up>
0113 static false_type __test(...);
0114 template <class _Up>
0115 static true_type
0116 __test(__void_t<typename _Up::iterator_category>* = nullptr,
0117 __void_t<typename _Up::difference_type>* = nullptr,
0118 __void_t<typename _Up::value_type>* = nullptr,
0119 __void_t<typename _Up::reference>* = nullptr,
0120 __void_t<typename _Up::pointer>* = nullptr);
0121
0122 public:
0123 static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::value;
0124 };
0125
0126 template <class _Tp>
0127 struct __has_iterator_category {
0128 private:
0129 template <class _Up>
0130 static false_type __test(...);
0131 template <class _Up>
0132 static true_type __test(typename _Up::iterator_category* = nullptr);
0133
0134 public:
0135 static const bool value = decltype(__test<_Tp>(nullptr))::value;
0136 };
0137
0138 template <class _Tp>
0139 struct __has_iterator_concept {
0140 private:
0141 template <class _Up>
0142 static false_type __test(...);
0143 template <class _Up>
0144 static true_type __test(typename _Up::iterator_concept* = nullptr);
0145
0146 public:
0147 static const bool value = decltype(__test<_Tp>(nullptr))::value;
0148 };
0149
0150 #if _LIBCPP_STD_VER >= 20
0151
0152
0153
0154
0155 namespace __iterator_traits_detail {
0156 template <class _Ip>
0157 concept __cpp17_iterator = requires(_Ip __i) {
0158 { *__i } -> __can_reference;
0159 { ++__i } -> same_as<_Ip&>;
0160 { *__i++ } -> __can_reference;
0161 } && copyable<_Ip>;
0162
0163 template <class _Ip>
0164 concept __cpp17_input_iterator = __cpp17_iterator<_Ip> && equality_comparable<_Ip> && requires(_Ip __i) {
0165 typename incrementable_traits<_Ip>::difference_type;
0166 typename indirectly_readable_traits<_Ip>::value_type;
0167 typename common_reference_t<iter_reference_t<_Ip>&&, typename indirectly_readable_traits<_Ip>::value_type&>;
0168 typename common_reference_t<decltype(*__i++)&&, typename indirectly_readable_traits<_Ip>::value_type&>;
0169 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>;
0170 };
0171
0172 template <class _Ip>
0173 concept __cpp17_forward_iterator =
0174 __cpp17_input_iterator<_Ip> && constructible_from<_Ip> && is_reference_v<iter_reference_t<_Ip>> &&
0175 same_as<remove_cvref_t<iter_reference_t<_Ip>>, typename indirectly_readable_traits<_Ip>::value_type> &&
0176 requires(_Ip __i) {
0177 { __i++ } -> convertible_to<_Ip const&>;
0178 { *__i++ } -> same_as<iter_reference_t<_Ip>>;
0179 };
0180
0181 template <class _Ip>
0182 concept __cpp17_bidirectional_iterator = __cpp17_forward_iterator<_Ip> && requires(_Ip __i) {
0183 { --__i } -> same_as<_Ip&>;
0184 { __i-- } -> convertible_to<_Ip const&>;
0185 { *__i-- } -> same_as<iter_reference_t<_Ip>>;
0186 };
0187
0188 template <class _Ip>
0189 concept __cpp17_random_access_iterator =
0190 __cpp17_bidirectional_iterator<_Ip> && totally_ordered<_Ip> &&
0191 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {
0192 { __i += __n } -> same_as<_Ip&>;
0193 { __i -= __n } -> same_as<_Ip&>;
0194 { __i + __n } -> same_as<_Ip>;
0195 { __n + __i } -> same_as<_Ip>;
0196 { __i - __n } -> same_as<_Ip>;
0197 { __i - __i } -> same_as<decltype(__n)>;
0198 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>;
0199 };
0200 }
0201
0202 template <class _Ip>
0203 concept __has_member_reference = requires { typename _Ip::reference; };
0204
0205 template <class _Ip>
0206 concept __has_member_pointer = requires { typename _Ip::pointer; };
0207
0208 template <class _Ip>
0209 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
0210
0211 template <class _Ip>
0212 concept __specifies_members = requires {
0213 typename _Ip::value_type;
0214 typename _Ip::difference_type;
0215 requires __has_member_reference<_Ip>;
0216 requires __has_member_iterator_category<_Ip>;
0217 };
0218
0219 template <class>
0220 struct __iterator_traits_member_pointer_or_void {
0221 using type = void;
0222 };
0223
0224 template <__has_member_pointer _Tp>
0225 struct __iterator_traits_member_pointer_or_void<_Tp> {
0226 using type = typename _Tp::pointer;
0227 };
0228
0229 template <class _Tp>
0230 concept __cpp17_iterator_missing_members = !__specifies_members<_Tp> && __iterator_traits_detail::__cpp17_iterator<_Tp>;
0231
0232 template <class _Tp>
0233 concept __cpp17_input_iterator_missing_members =
0234 __cpp17_iterator_missing_members<_Tp> && __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
0235
0236
0237 template <class>
0238 struct __iterator_traits_member_pointer_or_arrow_or_void {
0239 using type = void;
0240 };
0241
0242
0243
0244 template <__has_member_pointer _Ip>
0245 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
0246 using type = typename _Ip::pointer;
0247 };
0248
0249
0250
0251 template <class _Ip>
0252 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)
0253 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
0254 using type = decltype(std::declval<_Ip&>().operator->());
0255 };
0256
0257
0258 template <class _Ip>
0259 struct __iterator_traits_member_reference {
0260 using type = iter_reference_t<_Ip>;
0261 };
0262
0263
0264
0265 template <__has_member_reference _Ip>
0266 struct __iterator_traits_member_reference<_Ip> {
0267 using type = typename _Ip::reference;
0268 };
0269
0270
0271
0272 template <class _Ip>
0273 struct __deduce_iterator_category {
0274 using type = input_iterator_tag;
0275 };
0276
0277
0278
0279 template <__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
0280 struct __deduce_iterator_category<_Ip> {
0281 using type = random_access_iterator_tag;
0282 };
0283
0284
0285
0286 template <__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
0287 struct __deduce_iterator_category<_Ip> {
0288 using type = bidirectional_iterator_tag;
0289 };
0290
0291
0292
0293 template <__iterator_traits_detail::__cpp17_forward_iterator _Ip>
0294 struct __deduce_iterator_category<_Ip> {
0295 using type = forward_iterator_tag;
0296 };
0297
0298 template <class _Ip>
0299 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
0300
0301
0302
0303
0304 template <__has_member_iterator_category _Ip>
0305 struct __iterator_traits_iterator_category<_Ip> {
0306 using type = typename _Ip::iterator_category;
0307 };
0308
0309
0310 template <class>
0311 struct __iterator_traits_difference_type {
0312 using type = void;
0313 };
0314
0315
0316
0317 template <class _Ip>
0318 requires requires { typename incrementable_traits<_Ip>::difference_type; }
0319 struct __iterator_traits_difference_type<_Ip> {
0320 using type = typename incrementable_traits<_Ip>::difference_type;
0321 };
0322
0323
0324
0325 template <class>
0326 struct __iterator_traits {};
0327
0328
0329
0330
0331 template <__specifies_members _Ip>
0332 struct __iterator_traits<_Ip> {
0333 using iterator_category = typename _Ip::iterator_category;
0334 using value_type = typename _Ip::value_type;
0335 using difference_type = typename _Ip::difference_type;
0336 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type;
0337 using reference = typename _Ip::reference;
0338 };
0339
0340
0341
0342
0343 template <__cpp17_input_iterator_missing_members _Ip>
0344 struct __iterator_traits<_Ip> {
0345 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;
0346 using value_type = typename indirectly_readable_traits<_Ip>::value_type;
0347 using difference_type = typename incrementable_traits<_Ip>::difference_type;
0348 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type;
0349 using reference = typename __iterator_traits_member_reference<_Ip>::type;
0350 };
0351
0352
0353
0354 template <__cpp17_iterator_missing_members _Ip>
0355 struct __iterator_traits<_Ip> {
0356 using iterator_category = output_iterator_tag;
0357 using value_type = void;
0358 using difference_type = typename __iterator_traits_difference_type<_Ip>::type;
0359 using pointer = void;
0360 using reference = void;
0361 };
0362
0363 template <class _Ip>
0364 struct iterator_traits : __iterator_traits<_Ip> {
0365 using __primary_template = iterator_traits;
0366 };
0367
0368 #else
0369
0370 template <class _Iter, bool>
0371 struct __iterator_traits {};
0372
0373 template <class _Iter, bool>
0374 struct __iterator_traits_impl {};
0375
0376 template <class _Iter>
0377 struct __iterator_traits_impl<_Iter, true> {
0378 typedef typename _Iter::difference_type difference_type;
0379 typedef typename _Iter::value_type value_type;
0380 typedef typename _Iter::pointer pointer;
0381 typedef typename _Iter::reference reference;
0382 typedef typename _Iter::iterator_category iterator_category;
0383 };
0384
0385 template <class _Iter>
0386 struct __iterator_traits<_Iter, true>
0387 : __iterator_traits_impl< _Iter,
0388 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
0389 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value > {};
0390
0391
0392
0393
0394
0395
0396 template <class _Iter>
0397 struct _LIBCPP_TEMPLATE_VIS iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
0398 using __primary_template = iterator_traits;
0399 };
0400 #endif
0401
0402 template <class _Tp>
0403 #if _LIBCPP_STD_VER >= 20
0404 requires is_object_v<_Tp>
0405 #endif
0406 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> {
0407 typedef ptrdiff_t difference_type;
0408 typedef __remove_cv_t<_Tp> value_type;
0409 typedef _Tp* pointer;
0410 typedef _Tp& reference;
0411 typedef random_access_iterator_tag iterator_category;
0412 #if _LIBCPP_STD_VER >= 20
0413 typedef contiguous_iterator_tag iterator_concept;
0414 #endif
0415 };
0416
0417 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
0418 struct __has_iterator_category_convertible_to : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> {
0419 };
0420
0421 template <class _Tp, class _Up>
0422 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
0423
0424 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
0425 struct __has_iterator_concept_convertible_to : is_convertible<typename _Tp::iterator_concept, _Up> {};
0426
0427 template <class _Tp, class _Up>
0428 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
0429
0430 template <class _Tp>
0431 using __has_input_iterator_category = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;
0432
0433 template <class _Tp>
0434 using __has_forward_iterator_category = __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;
0435
0436 template <class _Tp>
0437 using __has_bidirectional_iterator_category = __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;
0438
0439 template <class _Tp>
0440 using __has_random_access_iterator_category = __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>;
0441
0442
0443
0444
0445
0446
0447
0448
0449 #if _LIBCPP_STD_VER >= 20
0450 template <class _Tp>
0451 struct __libcpp_is_contiguous_iterator
0452 : _Or< __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
0453 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> > {};
0454 #else
0455 template <class _Tp>
0456 struct __libcpp_is_contiguous_iterator : false_type {};
0457 #endif
0458
0459
0460 template <class _Up>
0461 struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};
0462
0463 template <class _Iter>
0464 class __wrap_iter;
0465
0466 template <class _Tp>
0467 using __has_exactly_input_iterator_category =
0468 integral_constant<bool,
0469 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
0470 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>;
0471
0472 template <class _Tp>
0473 using __has_exactly_forward_iterator_category =
0474 integral_constant<bool,
0475 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value &&
0476 !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>;
0477
0478 template <class _Tp>
0479 using __has_exactly_bidirectional_iterator_category =
0480 integral_constant<bool,
0481 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value &&
0482 !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>;
0483
0484 template <class _InputIterator>
0485 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
0486
0487 template <class _InputIterator>
0488 using __iter_key_type = __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
0489
0490 template <class _InputIterator>
0491 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
0492
0493 template <class _InputIterator>
0494 using __iter_to_alloc_type =
0495 pair<const typename iterator_traits<_InputIterator>::value_type::first_type,
0496 typename iterator_traits<_InputIterator>::value_type::second_type>;
0497
0498 template <class _Iter>
0499 using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category;
0500
0501 template <class _Iter>
0502 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
0503
0504 template <class _Iter>
0505 using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;
0506
0507 template <class _Iter>
0508 using __iter_reference = typename iterator_traits<_Iter>::reference;
0509
0510 #if _LIBCPP_STD_VER >= 20
0511
0512
0513
0514
0515
0516
0517
0518 template <class _Ip>
0519 using iter_value_t =
0520 typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,
0521 indirectly_readable_traits<remove_cvref_t<_Ip> >,
0522 iterator_traits<remove_cvref_t<_Ip> > >::value_type;
0523
0524 #endif
0525
0526 _LIBCPP_END_NAMESPACE_STD
0527
0528 #endif