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 <__config> 14 #include <__iterator/incrementable_traits.h> 15 #include <__iterator/readable_traits.h> 16 #include <concepts> 17 #include <type_traits> 18 19 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 20 #pragma GCC system_header 21 #endif 22 23 _LIBCPP_PUSH_MACROS 24 #include <__undef_macros> 25 26 _LIBCPP_BEGIN_NAMESPACE_STD 27 28 #if !defined(_LIBCPP_HAS_NO_RANGES) 29 30 template <class _Tp> 31 using __with_reference = _Tp&; 32 33 template <class _Tp> 34 concept __referenceable = requires { 35 typename __with_reference<_Tp>; 36 }; 37 38 template <class _Tp> 39 concept __dereferenceable = requires(_Tp& __t) { 40 { *__t } -> __referenceable; // not required to be equality-preserving 41 }; 42 43 // [iterator.traits] 44 template<__dereferenceable _Tp> 45 using iter_reference_t = decltype(*declval<_Tp&>()); 46 47 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 48 49 template <class _Iter> 50 struct _LIBCPP_TEMPLATE_VIS iterator_traits; 51 52 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; 53 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; 54 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; 55 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; 56 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; 57 #if _LIBCPP_STD_VER > 17 58 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; 59 #endif 60 61 template <class _Iter> 62 struct __iter_traits_cache { 63 using type = _If< 64 __is_primary_template<iterator_traits<_Iter> >::value, 65 _Iter, 66 iterator_traits<_Iter> 67 >; 68 }; 69 template <class _Iter> 70 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; 71 72 struct __iter_concept_concept_test { 73 template <class _Iter> 74 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; 75 }; 76 struct __iter_concept_category_test { 77 template <class _Iter> 78 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; 79 }; 80 struct __iter_concept_random_fallback { 81 template <class _Iter> 82 using _Apply = _EnableIf< 83 __is_primary_template<iterator_traits<_Iter> >::value, 84 random_access_iterator_tag 85 >; 86 }; 87 88 template <class _Iter, class _Tester> struct __test_iter_concept 89 : _IsValidExpansion<_Tester::template _Apply, _Iter>, 90 _Tester 91 { 92 }; 93 94 template <class _Iter> 95 struct __iter_concept_cache { 96 using type = _Or< 97 __test_iter_concept<_Iter, __iter_concept_concept_test>, 98 __test_iter_concept<_Iter, __iter_concept_category_test>, 99 __test_iter_concept<_Iter, __iter_concept_random_fallback> 100 >; 101 }; 102 103 template <class _Iter> 104 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; 105 106 107 template <class _Tp> 108 struct __has_iterator_typedefs 109 { 110 private: 111 struct __two {char __lx; char __lxx;}; 112 template <class _Up> static __two __test(...); 113 template <class _Up> static char __test(typename __void_t<typename _Up::iterator_category>::type* = 0, 114 typename __void_t<typename _Up::difference_type>::type* = 0, 115 typename __void_t<typename _Up::value_type>::type* = 0, 116 typename __void_t<typename _Up::reference>::type* = 0, 117 typename __void_t<typename _Up::pointer>::type* = 0); 118 public: 119 static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1; 120 }; 121 122 123 template <class _Tp> 124 struct __has_iterator_category 125 { 126 private: 127 struct __two {char __lx; char __lxx;}; 128 template <class _Up> static __two __test(...); 129 template <class _Up> static char __test(typename _Up::iterator_category* = nullptr); 130 public: 131 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 132 }; 133 134 template <class _Tp> 135 struct __has_iterator_concept 136 { 137 private: 138 struct __two {char __lx; char __lxx;}; 139 template <class _Up> static __two __test(...); 140 template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr); 141 public: 142 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; 143 }; 144 145 #if !defined(_LIBCPP_HAS_NO_RANGES) 146 147 // The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables, 148 // so they've been banished to a namespace that makes it obvious they have a niche use-case. 149 namespace __iterator_traits_detail { 150 template<class _Ip> 151 concept __cpp17_iterator = 152 requires(_Ip __i) { 153 { *__i } -> __referenceable; 154 { ++__i } -> same_as<_Ip&>; 155 { *__i++ } -> __referenceable; 156 } && 157 copyable<_Ip>; 158 159 template<class _Ip> 160 concept __cpp17_input_iterator = 161 __cpp17_iterator<_Ip> && 162 equality_comparable<_Ip> && 163 requires(_Ip __i) { 164 typename incrementable_traits<_Ip>::difference_type; 165 typename indirectly_readable_traits<_Ip>::value_type; 166 typename common_reference_t<iter_reference_t<_Ip>&&, 167 typename indirectly_readable_traits<_Ip>::value_type&>; 168 typename common_reference_t<decltype(*__i++)&&, 169 typename indirectly_readable_traits<_Ip>::value_type&>; 170 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>; 171 }; 172 173 template<class _Ip> 174 concept __cpp17_forward_iterator = 175 __cpp17_input_iterator<_Ip> && 176 constructible_from<_Ip> && 177 is_lvalue_reference_v<iter_reference_t<_Ip>> && 178 same_as<remove_cvref_t<iter_reference_t<_Ip>>, 179 typename indirectly_readable_traits<_Ip>::value_type> && 180 requires(_Ip __i) { 181 { __i++ } -> convertible_to<_Ip const&>; 182 { *__i++ } -> same_as<iter_reference_t<_Ip>>; 183 }; 184 185 template<class _Ip> 186 concept __cpp17_bidirectional_iterator = 187 __cpp17_forward_iterator<_Ip> && 188 requires(_Ip __i) { 189 { --__i } -> same_as<_Ip&>; 190 { __i-- } -> convertible_to<_Ip const&>; 191 { *__i-- } -> same_as<iter_reference_t<_Ip>>; 192 }; 193 194 template<class _Ip> 195 concept __cpp17_random_access_iterator = 196 __cpp17_bidirectional_iterator<_Ip> and 197 totally_ordered<_Ip> and 198 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { 199 { __i += __n } -> same_as<_Ip&>; 200 { __i -= __n } -> same_as<_Ip&>; 201 { __i + __n } -> same_as<_Ip>; 202 { __n + __i } -> same_as<_Ip>; 203 { __i - __n } -> same_as<_Ip>; 204 { __i - __i } -> same_as<decltype(__n)>; 205 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>; 206 }; 207 } // namespace __iterator_traits_detail 208 209 template<class _Ip> 210 concept __has_member_reference = requires { typename _Ip::reference; }; 211 212 template<class _Ip> 213 concept __has_member_pointer = requires { typename _Ip::pointer; }; 214 215 template<class _Ip> 216 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; 217 218 template<class _Ip> 219 concept __specifies_members = requires { 220 typename _Ip::value_type; 221 typename _Ip::difference_type; 222 requires __has_member_reference<_Ip>; 223 requires __has_member_iterator_category<_Ip>; 224 }; 225 226 template<class> 227 struct __iterator_traits_member_pointer_or_void { 228 using type = void; 229 }; 230 231 template<__has_member_pointer _Tp> 232 struct __iterator_traits_member_pointer_or_void<_Tp> { 233 using type = typename _Tp::pointer; 234 }; 235 236 template<class _Tp> 237 concept __cpp17_iterator_missing_members = 238 !__specifies_members<_Tp> && 239 __iterator_traits_detail::__cpp17_iterator<_Tp>; 240 241 template<class _Tp> 242 concept __cpp17_input_iterator_missing_members = 243 __cpp17_iterator_missing_members<_Tp> && 244 __iterator_traits_detail::__cpp17_input_iterator<_Tp>; 245 246 // Otherwise, `pointer` names `void`. 247 template<class> 248 struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; 249 250 // [iterator.traits]/3.2.1 251 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. 252 template<__has_member_pointer _Ip> 253 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; 254 255 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that 256 // type. 257 template<class _Ip> 258 concept __has_arrow = 259 requires(_Ip& __i) { 260 __i.operator->(); 261 }; 262 263 template<class _Ip> 264 requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>) 265 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { 266 using type = decltype(declval<_Ip&>().operator->()); 267 }; 268 269 // Otherwise, `reference` names `iter-reference-t<I>`. 270 template<class _Ip> 271 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; 272 273 // [iterator.traits]/3.2.2 274 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. 275 template<__has_member_reference _Ip> 276 struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; 277 278 // [iterator.traits]/3.2.3.4 279 // input_iterator_tag 280 template<class _Ip> 281 struct __deduce_iterator_category { 282 using type = input_iterator_tag; 283 }; 284 285 // [iterator.traits]/3.2.3.1 286 // `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise 287 template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip> 288 struct __deduce_iterator_category<_Ip> { 289 using type = random_access_iterator_tag; 290 }; 291 292 // [iterator.traits]/3.2.3.2 293 // `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise 294 template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip> 295 struct __deduce_iterator_category<_Ip> { 296 using type = bidirectional_iterator_tag; 297 }; 298 299 // [iterator.traits]/3.2.3.3 300 // `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise 301 template<__iterator_traits_detail::__cpp17_forward_iterator _Ip> 302 struct __deduce_iterator_category<_Ip> { 303 using type = forward_iterator_tag; 304 }; 305 306 template<class _Ip> 307 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; 308 309 // [iterator.traits]/3.2.3 310 // If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names 311 // that type. 312 template<__has_member_iterator_category _Ip> 313 struct __iterator_traits_iterator_category<_Ip> { 314 using type = typename _Ip::iterator_category; 315 }; 316 317 // otherwise, it names void. 318 template<class> 319 struct __iterator_traits_difference_type { using type = void; }; 320 321 // If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then 322 // `difference_type` names that type; 323 template<class _Ip> 324 requires requires { typename incrementable_traits<_Ip>::difference_type; } 325 struct __iterator_traits_difference_type<_Ip> { 326 using type = typename incrementable_traits<_Ip>::difference_type; 327 }; 328 329 // [iterator.traits]/3.4 330 // Otherwise, `iterator_traits<I>` has no members by any of the above names. 331 template<class> 332 struct __iterator_traits {}; 333 334 // [iterator.traits]/3.1 335 // If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and 336 // `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members: 337 template<__specifies_members _Ip> 338 struct __iterator_traits<_Ip> { 339 using iterator_category = typename _Ip::iterator_category; 340 using value_type = typename _Ip::value_type; 341 using difference_type = typename _Ip::difference_type; 342 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type; 343 using reference = typename _Ip::reference; 344 }; 345 346 // [iterator.traits]/3.2 347 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, 348 // `iterator-traits<I>` has the following publicly accessible members: 349 template<__cpp17_input_iterator_missing_members _Ip> 350 struct __iterator_traits<_Ip> { 351 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; 352 using value_type = typename indirectly_readable_traits<_Ip>::value_type; 353 using difference_type = typename incrementable_traits<_Ip>::difference_type; 354 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type; 355 using reference = typename __iterator_traits_member_reference<_Ip>::type; 356 }; 357 358 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then 359 // `iterator_traits<I>` has the following publicly accessible members: 360 template<__cpp17_iterator_missing_members _Ip> 361 struct __iterator_traits<_Ip> { 362 using iterator_category = output_iterator_tag; 363 using value_type = void; 364 using difference_type = typename __iterator_traits_difference_type<_Ip>::type; 365 using pointer = void; 366 using reference = void; 367 }; 368 369 template<class _Ip> 370 struct iterator_traits : __iterator_traits<_Ip> { 371 using __primary_template = iterator_traits; 372 }; 373 374 #else // !defined(_LIBCPP_HAS_NO_RANGES) 375 376 template <class _Iter, bool> struct __iterator_traits {}; 377 378 template <class _Iter, bool> struct __iterator_traits_impl {}; 379 380 template <class _Iter> 381 struct __iterator_traits_impl<_Iter, true> 382 { 383 typedef typename _Iter::difference_type difference_type; 384 typedef typename _Iter::value_type value_type; 385 typedef typename _Iter::pointer pointer; 386 typedef typename _Iter::reference reference; 387 typedef typename _Iter::iterator_category iterator_category; 388 }; 389 390 template <class _Iter> 391 struct __iterator_traits<_Iter, true> 392 : __iterator_traits_impl 393 < 394 _Iter, 395 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value || 396 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value 397 > 398 {}; 399 400 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category 401 // exists. Else iterator_traits<Iterator> will be an empty class. This is a 402 // conforming extension which allows some programs to compile and behave as 403 // the client expects instead of failing at compile time. 404 405 template <class _Iter> 406 struct _LIBCPP_TEMPLATE_VIS iterator_traits 407 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { 408 409 using __primary_template = iterator_traits; 410 }; 411 #endif // !defined(_LIBCPP_HAS_NO_RANGES) 412 413 template<class _Tp> 414 #if !defined(_LIBCPP_HAS_NO_RANGES) 415 requires is_object_v<_Tp> 416 #endif 417 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> 418 { 419 typedef ptrdiff_t difference_type; 420 typedef typename remove_cv<_Tp>::type value_type; 421 typedef _Tp* pointer; 422 typedef _Tp& reference; 423 typedef random_access_iterator_tag iterator_category; 424 #if _LIBCPP_STD_VER > 17 425 typedef contiguous_iterator_tag iterator_concept; 426 #endif 427 }; 428 429 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 430 struct __has_iterator_category_convertible_to 431 : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value> 432 {}; 433 434 template <class _Tp, class _Up> 435 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; 436 437 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value> 438 struct __has_iterator_concept_convertible_to 439 : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value> 440 {}; 441 442 template <class _Tp, class _Up> 443 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {}; 444 445 template <class _Tp> 446 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; 447 448 template <class _Tp> 449 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; 450 451 template <class _Tp> 452 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; 453 454 template <class _Tp> 455 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; 456 457 // __is_cpp17_contiguous_iterator determines if an iterator is contiguous, 458 // either because it advertises itself as such (in C++20) or because it 459 // is a pointer type or a known trivial wrapper around a pointer type, 460 // such as __wrap_iter<T*>. 461 // 462 #if _LIBCPP_STD_VER > 17 463 template <class _Tp> 464 struct __is_cpp17_contiguous_iterator : _Or< 465 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, 466 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> 467 > {}; 468 #else 469 template <class _Tp> 470 struct __is_cpp17_contiguous_iterator : false_type {}; 471 #endif 472 473 // Any native pointer which is an iterator is also a contiguous iterator. 474 template <class _Up> 475 struct __is_cpp17_contiguous_iterator<_Up*> : true_type {}; 476 477 478 template <class _Tp> 479 struct __is_exactly_cpp17_input_iterator 480 : public integral_constant<bool, 481 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 482 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {}; 483 484 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 485 template<class _InputIterator> 486 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; 487 488 template<class _InputIterator> 489 using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>; 490 491 template<class _InputIterator> 492 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; 493 494 template<class _InputIterator> 495 using __iter_to_alloc_type = pair< 496 add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>, 497 typename iterator_traits<_InputIterator>::value_type::second_type>; 498 #endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES 499 500 _LIBCPP_END_NAMESPACE_STD 501 502 _LIBCPP_POP_MACROS 503 504 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H 505
Indexes created Tue Feb 24 08:35:24 UTC 2026