1// Types used in iterator implementation -*- C++ -*-
2
3// Copyright (C) 2001-2024 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 __attribute__((__always_inline__))
237 inline _GLIBCXX_CONSTEXPR
238 typename iterator_traits<_Iter>::iterator_category
239 __iterator_category(const _Iter&)
240 { return typename iterator_traits<_Iter>::iterator_category(); }
241
242 ///@}
243
244#if __cplusplus >= 201103L
245 template<typename _Iter>
246 using __iter_category_t
247 = typename iterator_traits<_Iter>::iterator_category;
248
249 template<typename _InIter>
250 using _RequireInputIter =
251 __enable_if_t<is_convertible<__iter_category_t<_InIter>,
252 input_iterator_tag>::value>;
253
254 template<typename _It,
255 typename _Cat = __iter_category_t<_It>>
256 struct __is_random_access_iter
257 : is_base_of<random_access_iterator_tag, _Cat>
258 {
259 typedef is_base_of<random_access_iterator_tag, _Cat> _Base;
260 enum { __value = _Base::value };
261 };
262#else
263 template<typename _It, typename _Traits = iterator_traits<_It>,
264 typename _Cat = typename _Traits::iterator_category>
265 struct __is_random_access_iter
266 { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; };
267#endif
268
269_GLIBCXX_END_NAMESPACE_VERSION
270} // namespace
271
272#endif /* _STL_ITERATOR_BASE_TYPES_H */
273