247 lines · c
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H11#define _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H12 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_header31#endif32 33_LIBCPP_BEGIN_NAMESPACE_STD34 35template <class _Iter>36struct _LIBCPP_TEMPLATE_VIS iterator_traits;37 38struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};39struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};40struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {};41struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};42struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};43 44template <class _Iter>45struct __iter_traits_cache {46 using type = _If< __is_primary_template<iterator_traits<_Iter> >::value, _Iter, iterator_traits<_Iter> >;47};48template <class _Iter>49using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type;50 51struct __iter_concept_concept_test {52 template <class _Iter>53 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept;54};55struct __iter_concept_category_test {56 template <class _Iter>57 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category;58};59struct __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 64template <class _Iter, class _Tester>65struct __test_iter_concept : _IsValidExpansion<_Tester::template _Apply, _Iter>, _Tester {};66 67template <class _Iter>68struct __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 74template <class _Iter>75using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;76 77template <class _Tp>78struct __has_iterator_typedefs {79private:80 template <class _Up>81 static false_type __test(...);82 template <class _Up>83 static true_type84 __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 90public:91 static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::value;92};93 94template <class _Tp>95struct __has_iterator_category {96private:97 template <class _Up>98 static false_type __test(...);99 template <class _Up>100 static true_type __test(typename _Up::iterator_category* = nullptr);101 102public:103 static const bool value = decltype(__test<_Tp>(nullptr))::value;104};105 106template <class _Tp>107struct __has_iterator_concept {108private:109 template <class _Up>110 static false_type __test(...);111 template <class _Up>112 static true_type __test(typename _Up::iterator_concept* = nullptr);113 114public:115 static const bool value = decltype(__test<_Tp>(nullptr))::value;116};117 118template <class _Iter, bool>119struct __iterator_traits {};120 121template <class _Iter, bool>122struct __iterator_traits_impl {};123 124template <class _Iter>125struct __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 133template <class _Iter>134struct __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_category140// exists. Else iterator_traits<Iterator> will be an empty class. This is a141// conforming extension which allows some programs to compile and behave as142// the client expects instead of failing at compile time.143 144template <class _Iter>145struct _LIBCPP_TEMPLATE_VIS iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {146 using __primary_template = iterator_traits;147};148 149template <class _Tp>150struct _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 158template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>159struct __has_iterator_category_convertible_to : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> {160};161 162template <class _Tp, class _Up>163struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};164 165template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>166struct __has_iterator_concept_convertible_to : is_convertible<typename _Tp::iterator_concept, _Up> {};167 168template <class _Tp, class _Up>169struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};170 171template <class _Tp>172using __has_input_iterator_category = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;173 174template <class _Tp>175using __has_forward_iterator_category = __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;176 177template <class _Tp>178using __has_bidirectional_iterator_category = __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;179 180template <class _Tp>181using __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 by184// libc++ to be contiguous, either because it advertises itself as such185// (in C++20) or because it is a pointer type or a known trivial wrapper186// around a (possibly fancy) pointer type, such as __wrap_iter<T*>.187// Such iterators receive special "contiguous" optimizations in188// std::copy and std::sort.189//190template <class _Tp>191struct __libcpp_is_contiguous_iterator : false_type {};192 193// Any native pointer which is an iterator is also a contiguous iterator.194template <class _Up>195struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};196 197template <class _Iter>198class __wrap_iter;199 200template <class _Tp>201using __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 206template <class _Tp>207using __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 212template <class _Tp>213using __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 218template <class _InputIterator>219using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;220 221template <class _InputIterator>222using __iter_key_type = __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;223 224template <class _InputIterator>225using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;226 227template <class _InputIterator>228using __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 232template <class _Iter>233using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category;234 235template <class _Iter>236using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;237 238template <class _Iter>239using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;240 241template <class _Iter>242using __iter_reference = typename iterator_traits<_Iter>::reference;243 244_LIBCPP_END_NAMESPACE_STD245 246#endif // _LIBCPP___CXX03___ITERATOR_ITERATOR_TRAITS_H247