1// Types used in iterator implementation -*- C++ -*- 2 3// Copyright (C) 2001-2022 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996-1998 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51/** @file bits/stl_iterator_base_types.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{iterator} 54 * 55 * This file contains all of the general iterator-related utility types, 56 * such as iterator_traits and struct iterator. 57 */ 58 59#ifndef _STL_ITERATOR_BASE_TYPES_H 60#define _STL_ITERATOR_BASE_TYPES_H 1 61 62#pragma GCC system_header 63 64#include <bits/c++config.h> 65 66#if __cplusplus >= 201103L 67# include <type_traits> // For __void_t, is_convertible 68#endif 69 70#if __cplusplus > 201703L && __cpp_concepts >= 201907L 71# include <bits/iterator_concepts.h> 72#endif 73 74namespace std _GLIBCXX_VISIBILITY(default) 75{ 76_GLIBCXX_BEGIN_NAMESPACE_VERSION 77 78 /** 79 * @defgroup iterators Iterators 80 * Abstractions for uniform iterating through various underlying types. 81 */ 82 ///@{ 83 84 /** 85 * @defgroup iterator_tags Iterator Tags 86 * These are empty types, used to distinguish different iterators. The 87 * distinction is not made by what they contain, but simply by what they 88 * are. Different underlying algorithms can then be used based on the 89 * different operations supported by different iterator types. 90 */ 91 ///@{ 92 /// Marking input iterators. 93 struct input_iterator_tag { }; 94 95 /// Marking output iterators. 96 struct output_iterator_tag { }; 97 98 /// Forward iterators support a superset of input iterator operations. 99 struct forward_iterator_tag : public input_iterator_tag { }; 100 101 /// Bidirectional iterators support a superset of forward iterator 102 /// operations. 103 struct bidirectional_iterator_tag : public forward_iterator_tag { }; 104 105 /// Random-access iterators support a superset of bidirectional 106 /// iterator operations. 107 struct random_access_iterator_tag : public bidirectional_iterator_tag { }; 108 109#if __cplusplus > 201703L 110 /// Contiguous iterators point to objects stored contiguously in memory. 111 struct contiguous_iterator_tag : public random_access_iterator_tag { }; 112#endif 113 ///@} 114 115 /** 116 * @brief Common %iterator class. 117 * 118 * This class does nothing but define nested typedefs. %Iterator classes 119 * can inherit from this class to save some work. The typedefs are then 120 * used in specializations and overloading. 121 * 122 * In particular, there are no default implementations of requirements 123 * such as @c operator++ and the like. (How could there be?) 124 */ 125 template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t, 126 typename _Pointer = _Tp*, typename _Reference = _Tp&> 127 struct _GLIBCXX17_DEPRECATED iterator 128 { 129 /// One of the @link iterator_tags tag types@endlink. 130 typedef _Category iterator_category; 131 /// The type "pointed to" by the iterator. 132 typedef _Tp value_type; 133 /// Distance between iterators is represented as this type. 134 typedef _Distance difference_type; 135 /// This type represents a pointer-to-value_type. 136 typedef _Pointer pointer; 137 /// This type represents a reference-to-value_type. 138 typedef _Reference reference; 139 }; 140 141 /** 142 * @brief Traits class for iterators. 143 * 144 * This class does nothing but define nested typedefs. The general 145 * version simply @a forwards the nested typedefs from the Iterator 146 * argument. Specialized versions for pointers and pointers-to-const 147 * provide tighter, more correct semantics. 148 */ 149 template<typename _Iterator> 150 struct iterator_traits; 151 152#if __cplusplus >= 201103L 153 // _GLIBCXX_RESOLVE_LIB_DEFECTS 154 // 2408. SFINAE-friendly common_type/iterator_traits is missing in C++14 155 template<typename _Iterator, typename = __void_t<>> 156 struct __iterator_traits { }; 157 158#if ! __cpp_lib_concepts 159 160 template<typename _Iterator> 161 struct __iterator_traits<_Iterator, 162 __void_t<typename _Iterator::iterator_category, 163 typename _Iterator::value_type, 164 typename _Iterator::difference_type, 165 typename _Iterator::pointer, 166 typename _Iterator::reference>> 167 { 168 typedef typename _Iterator::iterator_category iterator_category; 169 typedef typename _Iterator::value_type value_type; 170 typedef typename _Iterator::difference_type difference_type; 171 typedef typename _Iterator::pointer pointer; 172 typedef typename _Iterator::reference reference; 173 }; 174#endif // ! concepts 175 176 template<typename _Iterator> 177 struct iterator_traits 178 : public __iterator_traits<_Iterator> { }; 179 180#else // ! C++11 181 template<typename _Iterator> 182 struct iterator_traits 183 { 184 typedef typename _Iterator::iterator_category iterator_category; 185 typedef typename _Iterator::value_type value_type; 186 typedef typename _Iterator::difference_type difference_type; 187 typedef typename _Iterator::pointer pointer; 188 typedef typename _Iterator::reference reference; 189 }; 190#endif // C++11 191 192#if __cplusplus > 201703L 193 /// Partial specialization for object pointer types. 194 template<typename _Tp> 195#if __cpp_concepts >= 201907L 196 requires is_object_v<_Tp> 197#endif 198 struct iterator_traits<_Tp*> 199 { 200 using iterator_concept = contiguous_iterator_tag; 201 using iterator_category = random_access_iterator_tag; 202 using value_type = remove_cv_t<_Tp>; 203 using difference_type = ptrdiff_t; 204 using pointer = _Tp*; 205 using reference = _Tp&; 206 }; 207#else 208 /// Partial specialization for pointer types. 209 template<typename _Tp> 210 struct iterator_traits<_Tp*> 211 { 212 typedef random_access_iterator_tag iterator_category; 213 typedef _Tp value_type; 214 typedef ptrdiff_t difference_type; 215 typedef _Tp* pointer; 216 typedef _Tp& reference; 217 }; 218 219 /// Partial specialization for const pointer types. 220 template<typename _Tp> 221 struct iterator_traits<const _Tp*> 222 { 223 typedef random_access_iterator_tag iterator_category; 224 typedef _Tp value_type; 225 typedef ptrdiff_t difference_type; 226 typedef const _Tp* pointer; 227 typedef const _Tp& reference; 228 }; 229#endif 230 231 /** 232 * This function is not a part of the C++ standard but is syntactic 233 * sugar for internal library use only. 234 */ 235 template<typename _Iter> 236 inline _GLIBCXX_CONSTEXPR 237 typename iterator_traits<_Iter>::iterator_category 238 __iterator_category(const _Iter&) 239 { return typename iterator_traits<_Iter>::iterator_category(); } 240 241 ///@} 242 243#if __cplusplus >= 201103L 244 template<typename _Iter> 245 using __iterator_category_t 246 = typename iterator_traits<_Iter>::iterator_category; 247 248 template<typename _InIter> 249 using _RequireInputIter = 250 __enable_if_t<is_convertible<__iterator_category_t<_InIter>, 251 input_iterator_tag>::value>; 252 253 template<typename _It, 254 typename _Cat = __iterator_category_t<_It>> 255 struct __is_random_access_iter 256 : is_base_of<random_access_iterator_tag, _Cat> 257 { 258 typedef is_base_of<random_access_iterator_tag, _Cat> _Base; 259 enum { __value = _Base::value }; 260 }; 261#else 262 template<typename _It, typename _Traits = iterator_traits<_It>, 263 typename _Cat = typename _Traits::iterator_category> 264 struct __is_random_access_iter 265 { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; }; 266#endif 267 268_GLIBCXX_END_NAMESPACE_VERSION 269} // namespace 270 271#endif /* _STL_ITERATOR_BASE_TYPES_H */ 272