diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -12,6 +12,7 @@ __functional_base_03 __hash_table __iterator/concepts.h + __iterator/iterator_traits.h __iterator/incrementable_traits.h __iterator/readable_traits.h __libcpp_version diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/iterator_traits.h @@ -0,0 +1,490 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H +#define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H + +#include <__config> +#include +#include <__iterator/incrementable_traits.h> +#include <__iterator/readable_traits.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +// [iterator.traits] +template<__dereferenceable _Tp> +using iter_reference_t = decltype(*declval<_Tp&>()); +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +template +struct _LIBCPP_TEMPLATE_VIS iterator_traits; + +struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; +struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; +struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; +struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; +struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; +#if _LIBCPP_STD_VER > 17 +struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; +#endif + +template +struct __iter_traits_cache { + using type = _If< + __is_primary_template >::value, + _Iter, + iterator_traits<_Iter> + >; +}; +template +using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; + +struct __iter_concept_concept_test { + template + using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; +}; +struct __iter_concept_category_test { + template + using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; +}; +struct __iter_concept_random_fallback { + template + using _Apply = _EnableIf< + __is_primary_template >::value, + random_access_iterator_tag + >; +}; + +template struct __test_iter_concept + : _IsValidExpansion<_Tester::template _Apply, _Iter>, + _Tester +{ +}; + +template +struct __iter_concept_cache { + using type = _Or< + __test_iter_concept<_Iter, __iter_concept_concept_test>, + __test_iter_concept<_Iter, __iter_concept_category_test>, + __test_iter_concept<_Iter, __iter_concept_random_fallback> + >; +}; + +template +using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; + + +template +struct __has_iterator_typedefs +{ +private: + struct __two {char __lx; char __lxx;}; + template static __two __test(...); + template static char __test(typename __void_t::type* = 0, + typename __void_t::type* = 0, + typename __void_t::type* = 0, + typename __void_t::type* = 0, + typename __void_t::type* = 0); +public: + static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1; +}; + + +template +struct __has_iterator_category +{ +private: + struct __two {char __lx; char __lxx;}; + template static __two __test(...); + template static char __test(typename _Up::iterator_category* = nullptr); +public: + static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; +}; + +template +struct __has_iterator_concept +{ +private: + struct __two {char __lx; char __lxx;}; + template static __two __test(...); + template static char __test(typename _Up::iterator_concept* = nullptr); +public: + static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; +}; + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +// The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables, +// so they've been banished to a namespace that makes it obvious they have a niche use-case. +namespace __iterator_traits_detail { +template +concept __cpp17_iterator = + requires(_Ip __i) { + { *__i } -> __referenceable; + { ++__i } -> same_as<_Ip&>; + { *__i++ } -> __referenceable; + } && + copyable<_Ip>; + +template +concept __cpp17_input_iterator = + __cpp17_iterator<_Ip> && + equality_comparable<_Ip> && + requires(_Ip __i) { + typename incrementable_traits<_Ip>::difference_type; + typename indirectly_readable_traits<_Ip>::value_type; + typename common_reference_t&&, + typename indirectly_readable_traits<_Ip>::value_type&>; + typename common_reference_t::value_type&>; + requires signed_integral::difference_type>; + }; + +template +concept __cpp17_forward_iterator = + __cpp17_input_iterator<_Ip> && + constructible_from<_Ip> && + is_lvalue_reference_v> && + same_as>, + typename indirectly_readable_traits<_Ip>::value_type> && + requires(_Ip __i) { + { __i++ } -> convertible_to<_Ip const&>; + { *__i++ } -> same_as>; + }; + +template +concept __cpp17_bidirectional_iterator = + __cpp17_forward_iterator<_Ip> && + requires(_Ip __i) { + { --__i } -> same_as<_Ip&>; + { __i-- } -> convertible_to<_Ip const&>; + { *__i-- } -> same_as>; + }; + +template +concept __cpp17_random_access_iterator = + __cpp17_bidirectional_iterator<_Ip> and + totally_ordered<_Ip> and + requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { + { __i += __n } -> same_as<_Ip&>; + { __i -= __n } -> same_as<_Ip&>; + { __i + __n } -> same_as<_Ip>; + { __n + __i } -> same_as<_Ip>; + { __i - __n } -> same_as<_Ip>; + { __i - __i } -> same_as; + { __i[__n] } -> convertible_to>; + }; +} // namespace __iterator_traits_detail + +template +concept __has_member_reference = requires { typename _Ip::reference; }; + +template +concept __has_member_pointer = requires { typename _Ip::pointer; }; + +template +concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; + +template +concept __specifies_members = requires { + typename _Ip::value_type; + typename _Ip::difference_type; + requires __has_member_reference<_Ip>; + requires __has_member_iterator_category<_Ip>; + }; + +template +struct __iterator_traits_member_pointer_or_void { + using type = void; +}; + +template<__has_member_pointer _Tp> +struct __iterator_traits_member_pointer_or_void<_Tp> { + using type = typename _Tp::pointer; +}; + +template +concept __cpp17_iterator_missing_members = + !__specifies_members<_Tp> && + __iterator_traits_detail::__cpp17_iterator<_Tp>; + +template +concept __cpp17_input_iterator_missing_members = + __cpp17_iterator_missing_members<_Tp> && + __iterator_traits_detail::__cpp17_input_iterator<_Tp>; + +// Otherwise, `pointer` names `void`. +template +struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; + +// [iterator.traits]/3.2.1 +// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. +template<__has_member_pointer _Ip> +struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; + +// Otherwise, if `decltype(declval().operator->())` is well-formed, then `pointer` names that +// type. +template +concept __has_arrow = + requires(_Ip& __i) { + __i.operator->(); + }; + +template + requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>) +struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { + using type = decltype(declval<_Ip&>().operator->()); +}; + +// Otherwise, `reference` names `iter-reference-t`. +template +struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; + +// [iterator.traits]/3.2.2 +// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. +template<__has_member_reference _Ip> +struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; + +// [iterator.traits]/3.2.3.4 +// input_iterator_tag +template +struct __deduce_iterator_category { + using type = input_iterator_tag; +}; + +// [iterator.traits]/3.2.3.1 +// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise +template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip> +struct __deduce_iterator_category<_Ip> { + using type = random_access_iterator_tag; +}; + +// [iterator.traits]/3.2.3.2 +// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise +template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip> +struct __deduce_iterator_category<_Ip> { + using type = bidirectional_iterator_tag; +}; + +// [iterator.traits]/3.2.3.3 +// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise +template<__iterator_traits_detail::__cpp17_forward_iterator _Ip> +struct __deduce_iterator_category<_Ip> { + using type = forward_iterator_tag; +}; + +template +struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; + +// [iterator.traits]/3.2.3 +// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names +// that type. +template<__has_member_iterator_category _Ip> +struct __iterator_traits_iterator_category<_Ip> { + using type = typename _Ip::iterator_category; +}; + +// otherwise, it names void. +template +struct __iterator_traits_difference_type { using type = void; }; + +// If the qualified-id `incrementable_traits::difference_type` is valid and denotes a type, then +// `difference_type` names that type; +template +requires requires { typename incrementable_traits<_Ip>::difference_type; } +struct __iterator_traits_difference_type<_Ip> { + using type = typename incrementable_traits<_Ip>::difference_type; +}; + +// [iterator.traits]/3.4 +// Otherwise, `iterator_traits` has no members by any of the above names. +template +struct __iterator_traits {}; + +// [iterator.traits]/3.1 +// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and +// `iterator-category`, then `iterator-traits` has the following publicly accessible members: +template<__specifies_members _Ip> +struct __iterator_traits<_Ip> { + using iterator_category = typename _Ip::iterator_category; + using value_type = typename _Ip::value_type; + using difference_type = typename _Ip::difference_type; + using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type; + using reference = typename _Ip::reference; +}; + +// [iterator.traits]/3.2 +// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, +// `iterator-traits` has the following publicly accessible members: +template<__cpp17_input_iterator_missing_members _Ip> +struct __iterator_traits<_Ip> { + using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; + using value_type = typename indirectly_readable_traits<_Ip>::value_type; + using difference_type = typename incrementable_traits<_Ip>::difference_type; + using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type; + using reference = typename __iterator_traits_member_reference<_Ip>::type; +}; + +// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then +// `iterator_traits` has the following publicly accessible members: +template<__cpp17_iterator_missing_members _Ip> +struct __iterator_traits<_Ip> { + using iterator_category = output_iterator_tag; + using value_type = void; + using difference_type = typename __iterator_traits_difference_type<_Ip>::type; + using pointer = void; + using reference = void; +}; + +template +struct iterator_traits : __iterator_traits<_Ip> { + using __primary_template = iterator_traits; +}; + +#else // !defined(_LIBCPP_HAS_NO_RANGES) + +template struct __iterator_traits {}; + +template struct __iterator_traits_impl {}; + +template +struct __iterator_traits_impl<_Iter, true> +{ + typedef typename _Iter::difference_type difference_type; + typedef typename _Iter::value_type value_type; + typedef typename _Iter::pointer pointer; + typedef typename _Iter::reference reference; + typedef typename _Iter::iterator_category iterator_category; +}; + +template +struct __iterator_traits<_Iter, true> + : __iterator_traits_impl + < + _Iter, + is_convertible::value || + is_convertible::value + > +{}; + +// iterator_traits will only have the nested types if Iterator::iterator_category +// exists. Else iterator_traits will be an empty class. This is a +// conforming extension which allows some programs to compile and behave as +// the client expects instead of failing at compile time. + +template +struct _LIBCPP_TEMPLATE_VIS iterator_traits + : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { + + using __primary_template = iterator_traits; +}; +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +template +#if !defined(_LIBCPP_HAS_NO_RANGES) +requires is_object_v<_Tp> +#endif +struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> +{ + typedef ptrdiff_t difference_type; + typedef typename remove_cv<_Tp>::type value_type; + typedef _Tp* pointer; + typedef _Tp& reference; + typedef random_access_iterator_tag iterator_category; +#if _LIBCPP_STD_VER > 17 + typedef contiguous_iterator_tag iterator_concept; +#endif +}; + +template >::value> +struct __has_iterator_category_convertible_to + : _BoolConstant::iterator_category, _Up>::value> +{}; + +template +struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; + +template ::value> +struct __has_iterator_concept_convertible_to + : _BoolConstant::value> +{}; + +template +struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {}; + +template +struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; + +template +struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; + +template +struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; + +template +struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; + +// __is_cpp17_contiguous_iterator determines if an iterator is contiguous, +// either because it advertises itself as such (in C++20) or because it +// is a pointer type or a known trivial wrapper around a pointer type, +// such as __wrap_iter. +// +#if _LIBCPP_STD_VER > 17 +template +struct __is_cpp17_contiguous_iterator : _Or< + __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, + __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> +> {}; +#else +template +struct __is_cpp17_contiguous_iterator : false_type {}; +#endif + +// Any native pointer which is an iterator is also a contiguous iterator. +template +struct __is_cpp17_contiguous_iterator<_Up*> : true_type {}; + + +template +struct __is_exactly_cpp17_input_iterator + : public integral_constant::value && + !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {}; + +#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES +template +using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; + +template +using __iter_key_type = remove_const_t::value_type::first_type>; + +template +using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; + +template +using __iter_to_alloc_type = pair< + add_const_t::value_type::first_type>, + typename iterator_traits<_InputIterator>::value_type::second_type>; +#endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -413,10 +413,11 @@ #include <__functional_base> #include #include -#include +#include // Mandated by the Standard. #include #include #include <__iterator/incrementable_traits.h> +#include <__iterator/iterator_traits.h> #include <__iterator/readable_traits.h> #include <__memory/addressof.h> #include <__memory/pointer_traits.h> @@ -430,464 +431,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD -#if !defined(_LIBCPP_HAS_NO_RANGES) - -// [iterator.traits] -template<__dereferenceable _Tp> -using iter_reference_t = decltype(*declval<_Tp&>()); -#endif // !defined(_LIBCPP_HAS_NO_RANGES) - -template -struct _LIBCPP_TEMPLATE_VIS iterator_traits; - -struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {}; -struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {}; -struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {}; -struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {}; -struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {}; -#if _LIBCPP_STD_VER > 17 -struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {}; -#endif - -template -struct __iter_traits_cache { - using type = _If< - __is_primary_template >::value, - _Iter, - iterator_traits<_Iter> - >; -}; -template -using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type; - -struct __iter_concept_concept_test { - template - using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept; -}; -struct __iter_concept_category_test { - template - using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category; -}; -struct __iter_concept_random_fallback { - template - using _Apply = _EnableIf< - __is_primary_template >::value, - random_access_iterator_tag - >; -}; - -template struct __test_iter_concept - : _IsValidExpansion<_Tester::template _Apply, _Iter>, - _Tester -{ -}; - -template -struct __iter_concept_cache { - using type = _Or< - __test_iter_concept<_Iter, __iter_concept_concept_test>, - __test_iter_concept<_Iter, __iter_concept_category_test>, - __test_iter_concept<_Iter, __iter_concept_random_fallback> - >; -}; - -template -using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>; - - -template -struct __has_iterator_typedefs -{ -private: - struct __two {char __lx; char __lxx;}; - template static __two __test(...); - template static char __test(typename __void_t::type* = 0, - typename __void_t::type* = 0, - typename __void_t::type* = 0, - typename __void_t::type* = 0, - typename __void_t::type* = 0); -public: - static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1; -}; - - -template -struct __has_iterator_category -{ -private: - struct __two {char __lx; char __lxx;}; - template static __two __test(...); - template static char __test(typename _Up::iterator_category* = nullptr); -public: - static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; -}; - -template -struct __has_iterator_concept -{ -private: - struct __two {char __lx; char __lxx;}; - template static __two __test(...); - template static char __test(typename _Up::iterator_concept* = nullptr); -public: - static const bool value = sizeof(__test<_Tp>(nullptr)) == 1; -}; - -#if !defined(_LIBCPP_HAS_NO_RANGES) - -// The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables, -// so they've been banished to a namespace that makes it obvious they have a niche use-case. -namespace __iterator_traits_detail { -template -concept __cpp17_iterator = - requires(_Ip __i) { - { *__i } -> __referenceable; - { ++__i } -> same_as<_Ip&>; - { *__i++ } -> __referenceable; - } && - copyable<_Ip>; - -template -concept __cpp17_input_iterator = - __cpp17_iterator<_Ip> && - equality_comparable<_Ip> && - requires(_Ip __i) { - typename incrementable_traits<_Ip>::difference_type; - typename indirectly_readable_traits<_Ip>::value_type; - typename common_reference_t&&, - typename indirectly_readable_traits<_Ip>::value_type&>; - typename common_reference_t::value_type&>; - requires signed_integral::difference_type>; - }; - -template -concept __cpp17_forward_iterator = - __cpp17_input_iterator<_Ip> && - constructible_from<_Ip> && - is_lvalue_reference_v> && - same_as>, - typename indirectly_readable_traits<_Ip>::value_type> && - requires(_Ip __i) { - { __i++ } -> convertible_to<_Ip const&>; - { *__i++ } -> same_as>; - }; - -template -concept __cpp17_bidirectional_iterator = - __cpp17_forward_iterator<_Ip> && - requires(_Ip __i) { - { --__i } -> same_as<_Ip&>; - { __i-- } -> convertible_to<_Ip const&>; - { *__i-- } -> same_as>; - }; - -template -concept __cpp17_random_access_iterator = - __cpp17_bidirectional_iterator<_Ip> and - totally_ordered<_Ip> and - requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) { - { __i += __n } -> same_as<_Ip&>; - { __i -= __n } -> same_as<_Ip&>; - { __i + __n } -> same_as<_Ip>; - { __n + __i } -> same_as<_Ip>; - { __i - __n } -> same_as<_Ip>; - { __i - __i } -> same_as; - { __i[__n] } -> convertible_to>; - }; -} // namespace __iterator_traits_detail - -template -concept __has_member_reference = requires { typename _Ip::reference; }; - -template -concept __has_member_pointer = requires { typename _Ip::pointer; }; - -template -concept __has_member_iterator_category = requires { typename _Ip::iterator_category; }; - -template -concept __specifies_members = requires { - typename _Ip::value_type; - typename _Ip::difference_type; - requires __has_member_reference<_Ip>; - requires __has_member_iterator_category<_Ip>; - }; - -template -struct __iterator_traits_member_pointer_or_void { - using type = void; -}; - -template<__has_member_pointer _Tp> -struct __iterator_traits_member_pointer_or_void<_Tp> { - using type = typename _Tp::pointer; -}; - -template -concept __cpp17_iterator_missing_members = - !__specifies_members<_Tp> && - __iterator_traits_detail::__cpp17_iterator<_Tp>; - -template -concept __cpp17_input_iterator_missing_members = - __cpp17_iterator_missing_members<_Tp> && - __iterator_traits_detail::__cpp17_input_iterator<_Tp>; - -// Otherwise, `pointer` names `void`. -template -struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; }; - -// [iterator.traits]/3.2.1 -// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type. -template<__has_member_pointer _Ip> -struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; }; - -// Otherwise, if `decltype(declval().operator->())` is well-formed, then `pointer` names that -// type. -template -concept __has_arrow = - requires(_Ip& __i) { - __i.operator->(); - }; - -template - requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>) -struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { - using type = decltype(declval<_Ip&>().operator->()); -}; - -// Otherwise, `reference` names `iter-reference-t`. -template -struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; }; - -// [iterator.traits]/3.2.2 -// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type. -template<__has_member_reference _Ip> -struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; }; - -// [iterator.traits]/3.2.3.4 -// input_iterator_tag -template -struct __deduce_iterator_category { - using type = input_iterator_tag; -}; - -// [iterator.traits]/3.2.3.1 -// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise -template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip> -struct __deduce_iterator_category<_Ip> { - using type = random_access_iterator_tag; -}; - -// [iterator.traits]/3.2.3.2 -// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise -template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip> -struct __deduce_iterator_category<_Ip> { - using type = bidirectional_iterator_tag; -}; - -// [iterator.traits]/3.2.3.3 -// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise -template<__iterator_traits_detail::__cpp17_forward_iterator _Ip> -struct __deduce_iterator_category<_Ip> { - using type = forward_iterator_tag; -}; - -template -struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {}; - -// [iterator.traits]/3.2.3 -// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names -// that type. -template<__has_member_iterator_category _Ip> -struct __iterator_traits_iterator_category<_Ip> { - using type = typename _Ip::iterator_category; -}; - -// otherwise, it names void. -template -struct __iterator_traits_difference_type { using type = void; }; - -// If the qualified-id `incrementable_traits::difference_type` is valid and denotes a type, then -// `difference_type` names that type; -template -requires requires { typename incrementable_traits<_Ip>::difference_type; } -struct __iterator_traits_difference_type<_Ip> { - using type = typename incrementable_traits<_Ip>::difference_type; -}; - -// [iterator.traits]/3.4 -// Otherwise, `iterator_traits` has no members by any of the above names. -template -struct __iterator_traits {}; - -// [iterator.traits]/3.1 -// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and -// `iterator-category`, then `iterator-traits` has the following publicly accessible members: -template<__specifies_members _Ip> -struct __iterator_traits<_Ip> { - using iterator_category = typename _Ip::iterator_category; - using value_type = typename _Ip::value_type; - using difference_type = typename _Ip::difference_type; - using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type; - using reference = typename _Ip::reference; -}; - -// [iterator.traits]/3.2 -// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`, -// `iterator-traits` has the following publicly accessible members: -template<__cpp17_input_iterator_missing_members _Ip> -struct __iterator_traits<_Ip> { - using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type; - using value_type = typename indirectly_readable_traits<_Ip>::value_type; - using difference_type = typename incrementable_traits<_Ip>::difference_type; - using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type; - using reference = typename __iterator_traits_member_reference<_Ip>::type; -}; - -// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then -// `iterator_traits` has the following publicly accessible members: -template<__cpp17_iterator_missing_members _Ip> -struct __iterator_traits<_Ip> { - using iterator_category = output_iterator_tag; - using value_type = void; - using difference_type = typename __iterator_traits_difference_type<_Ip>::type; - using pointer = void; - using reference = void; -}; - -template -struct iterator_traits : __iterator_traits<_Ip> { - using __primary_template = iterator_traits; -}; - -#else // !defined(_LIBCPP_HAS_NO_RANGES) - -template struct __iterator_traits {}; - -template struct __iterator_traits_impl {}; - -template -struct __iterator_traits_impl<_Iter, true> -{ - typedef typename _Iter::difference_type difference_type; - typedef typename _Iter::value_type value_type; - typedef typename _Iter::pointer pointer; - typedef typename _Iter::reference reference; - typedef typename _Iter::iterator_category iterator_category; -}; - -template -struct __iterator_traits<_Iter, true> - : __iterator_traits_impl - < - _Iter, - is_convertible::value || - is_convertible::value - > -{}; - -// iterator_traits will only have the nested types if Iterator::iterator_category -// exists. Else iterator_traits will be an empty class. This is a -// conforming extension which allows some programs to compile and behave as -// the client expects instead of failing at compile time. - -template -struct _LIBCPP_TEMPLATE_VIS iterator_traits - : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { - - using __primary_template = iterator_traits; -}; -#endif // !defined(_LIBCPP_HAS_NO_RANGES) - -template -#if !defined(_LIBCPP_HAS_NO_RANGES) -requires is_object_v<_Tp> -#endif -struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> -{ - typedef ptrdiff_t difference_type; - typedef typename remove_cv<_Tp>::type value_type; - typedef _Tp* pointer; - typedef _Tp& reference; - typedef random_access_iterator_tag iterator_category; -#if _LIBCPP_STD_VER > 17 - typedef contiguous_iterator_tag iterator_concept; -#endif -}; - -template >::value> -struct __has_iterator_category_convertible_to - : _BoolConstant::iterator_category, _Up>::value> -{}; - -template -struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {}; - -template ::value> -struct __has_iterator_concept_convertible_to - : _BoolConstant::value> -{}; - -template -struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {}; - -template -struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; - -template -struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; - -template -struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; - -template -struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; - -// __is_cpp17_contiguous_iterator determines if an iterator is contiguous, -// either because it advertises itself as such (in C++20) or because it -// is a pointer type or a known trivial wrapper around a pointer type, -// such as __wrap_iter. -// -#if _LIBCPP_STD_VER > 17 -template -struct __is_cpp17_contiguous_iterator : _Or< - __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>, - __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> -> {}; -#else -template -struct __is_cpp17_contiguous_iterator : false_type {}; -#endif - -// Any native pointer which is an iterator is also a contiguous iterator. -template -struct __is_cpp17_contiguous_iterator<_Up*> : true_type {}; - - -template -struct __is_exactly_cpp17_input_iterator - : public integral_constant::value && - !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {}; - -#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES -template -using __iter_value_type = typename iterator_traits<_InputIterator>::value_type; - -template -using __iter_key_type = remove_const_t::value_type::first_type>; - -template -using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type; - -template -using __iter_to_alloc_type = pair< - add_const_t::value_type::first_type>, - typename iterator_traits<_InputIterator>::value_type::second_type>; -#endif - template struct _LIBCPP_TEMPLATE_VIS iterator