libstdc++
stl_iterator_base_funcs.h
Go to the documentation of this file.
1 // Functions used by iterators -*- C++ -*-
2 
3 // Copyright (C) 2001-2020 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_funcs.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
56  * functions, such as distance() and advance().
57  */
58 
59 #ifndef _STL_ITERATOR_BASE_FUNCS_H
60 #define _STL_ITERATOR_BASE_FUNCS_H 1
61 
62 #pragma GCC system_header
63 
64 #include <bits/concept_check.h>
65 #include <debug/assertions.h>
66 
67 namespace std _GLIBCXX_VISIBILITY(default)
68 {
69 _GLIBCXX_BEGIN_NAMESPACE_VERSION
70 
71 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
72  // Forward declaration for the overloads of __distance.
73  template <typename> struct _List_iterator;
74  template <typename> struct _List_const_iterator;
75 _GLIBCXX_END_NAMESPACE_CONTAINER
76 
77  template<typename _InputIterator>
78  inline _GLIBCXX14_CONSTEXPR
79  typename iterator_traits<_InputIterator>::difference_type
80  __distance(_InputIterator __first, _InputIterator __last,
81  input_iterator_tag)
82  {
83  // concept requirements
84  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
85 
86  typename iterator_traits<_InputIterator>::difference_type __n = 0;
87  while (__first != __last)
88  {
89  ++__first;
90  ++__n;
91  }
92  return __n;
93  }
94 
95  template<typename _RandomAccessIterator>
96  inline _GLIBCXX14_CONSTEXPR
97  typename iterator_traits<_RandomAccessIterator>::difference_type
98  __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
99  random_access_iterator_tag)
100  {
101  // concept requirements
102  __glibcxx_function_requires(_RandomAccessIteratorConcept<
103  _RandomAccessIterator>)
104  return __last - __first;
105  }
106 
107 #if _GLIBCXX_USE_CXX11_ABI
108  // Forward declaration because of the qualified call in distance.
109  template<typename _Tp>
110  ptrdiff_t
111  __distance(_GLIBCXX_STD_C::_List_iterator<_Tp>,
112  _GLIBCXX_STD_C::_List_iterator<_Tp>,
113  input_iterator_tag);
114 
115  template<typename _Tp>
116  ptrdiff_t
117  __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp>,
118  _GLIBCXX_STD_C::_List_const_iterator<_Tp>,
119  input_iterator_tag);
120 #endif
121 
122  /**
123  * @brief A generalization of pointer arithmetic.
124  * @param __first An input iterator.
125  * @param __last An input iterator.
126  * @return The distance between them.
127  *
128  * Returns @c n such that __first + n == __last. This requires
129  * that @p __last must be reachable from @p __first. Note that @c
130  * n may be negative.
131  *
132  * For random access iterators, this uses their @c + and @c - operations
133  * and are constant time. For other %iterator classes they are linear time.
134  */
135  template<typename _InputIterator>
136  inline _GLIBCXX17_CONSTEXPR
137  typename iterator_traits<_InputIterator>::difference_type
138  distance(_InputIterator __first, _InputIterator __last)
139  {
140  // concept requirements -- taken care of in __distance
141  return std::__distance(__first, __last,
142  std::__iterator_category(__first));
143  }
144 
145  template<typename _InputIterator, typename _Distance>
146  inline _GLIBCXX14_CONSTEXPR void
147  __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
148  {
149  // concept requirements
150  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
151  __glibcxx_assert(__n >= 0);
152  while (__n--)
153  ++__i;
154  }
155 
156  template<typename _BidirectionalIterator, typename _Distance>
157  inline _GLIBCXX14_CONSTEXPR void
158  __advance(_BidirectionalIterator& __i, _Distance __n,
159  bidirectional_iterator_tag)
160  {
161  // concept requirements
162  __glibcxx_function_requires(_BidirectionalIteratorConcept<
163  _BidirectionalIterator>)
164  if (__n > 0)
165  while (__n--)
166  ++__i;
167  else
168  while (__n++)
169  --__i;
170  }
171 
172  template<typename _RandomAccessIterator, typename _Distance>
173  inline _GLIBCXX14_CONSTEXPR void
174  __advance(_RandomAccessIterator& __i, _Distance __n,
175  random_access_iterator_tag)
176  {
177  // concept requirements
178  __glibcxx_function_requires(_RandomAccessIteratorConcept<
179  _RandomAccessIterator>)
180  if (__builtin_constant_p(__n) && __n == 1)
181  ++__i;
182  else if (__builtin_constant_p(__n) && __n == -1)
183  --__i;
184  else
185  __i += __n;
186  }
187 
188  /**
189  * @brief A generalization of pointer arithmetic.
190  * @param __i An input iterator.
191  * @param __n The @a delta by which to change @p __i.
192  * @return Nothing.
193  *
194  * This increments @p i by @p n. For bidirectional and random access
195  * iterators, @p __n may be negative, in which case @p __i is decremented.
196  *
197  * For random access iterators, this uses their @c + and @c - operations
198  * and are constant time. For other %iterator classes they are linear time.
199  */
200  template<typename _InputIterator, typename _Distance>
201  inline _GLIBCXX17_CONSTEXPR void
202  advance(_InputIterator& __i, _Distance __n)
203  {
204  // concept requirements -- taken care of in __advance
206  std::__advance(__i, __d, std::__iterator_category(__i));
207  }
208 
209 #if __cplusplus >= 201103L
210 
211  template<typename _InputIterator>
212  inline _GLIBCXX17_CONSTEXPR _InputIterator
213  next(_InputIterator __x, typename
214  iterator_traits<_InputIterator>::difference_type __n = 1)
215  {
216  // concept requirements
217  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
218  std::advance(__x, __n);
219  return __x;
220  }
221 
222  template<typename _BidirectionalIterator>
223  inline _GLIBCXX17_CONSTEXPR _BidirectionalIterator
224  prev(_BidirectionalIterator __x, typename
225  iterator_traits<_BidirectionalIterator>::difference_type __n = 1)
226  {
227  // concept requirements
228  __glibcxx_function_requires(_BidirectionalIteratorConcept<
229  _BidirectionalIterator>)
230  std::advance(__x, -__n);
231  return __x;
232  }
233 
234 #endif // C++11
235 
236 _GLIBCXX_END_NAMESPACE_VERSION
237 } // namespace
238 
239 #endif /* _STL_ITERATOR_BASE_FUNCS_H */
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Traits class for iterators.