libstdc++
stl_iterator_base_funcs.h
Go to the documentation of this file.
1 // Functions used by iterators -*- C++ -*-
2 
3 // Copyright (C) 2001-2014 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/debug.h>
66 
67 namespace std _GLIBCXX_VISIBILITY(default)
68 {
69 _GLIBCXX_BEGIN_NAMESPACE_VERSION
70 
71  template<typename _InputIterator>
72  inline typename iterator_traits<_InputIterator>::difference_type
73  __distance(_InputIterator __first, _InputIterator __last,
74  input_iterator_tag)
75  {
76  // concept requirements
77  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
78 
79  typename iterator_traits<_InputIterator>::difference_type __n = 0;
80  while (__first != __last)
81  {
82  ++__first;
83  ++__n;
84  }
85  return __n;
86  }
87 
88  template<typename _RandomAccessIterator>
89  inline typename iterator_traits<_RandomAccessIterator>::difference_type
90  __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
91  random_access_iterator_tag)
92  {
93  // concept requirements
94  __glibcxx_function_requires(_RandomAccessIteratorConcept<
95  _RandomAccessIterator>)
96  return __last - __first;
97  }
98 
99  /**
100  * @brief A generalization of pointer arithmetic.
101  * @param __first An input iterator.
102  * @param __last An input iterator.
103  * @return The distance between them.
104  *
105  * Returns @c n such that __first + n == __last. This requires
106  * that @p __last must be reachable from @p __first. Note that @c
107  * n may be negative.
108  *
109  * For random access iterators, this uses their @c + and @c - operations
110  * and are constant time. For other %iterator classes they are linear time.
111  */
112  template<typename _InputIterator>
113  inline typename iterator_traits<_InputIterator>::difference_type
114  distance(_InputIterator __first, _InputIterator __last)
115  {
116  // concept requirements -- taken care of in __distance
117  return std::__distance(__first, __last,
118  std::__iterator_category(__first));
119  }
120 
121  template<typename _InputIterator, typename _Distance>
122  inline void
123  __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
124  {
125  // concept requirements
126  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
127  _GLIBCXX_DEBUG_ASSERT(__n >= 0);
128  while (__n--)
129  ++__i;
130  }
131 
132  template<typename _BidirectionalIterator, typename _Distance>
133  inline void
134  __advance(_BidirectionalIterator& __i, _Distance __n,
135  bidirectional_iterator_tag)
136  {
137  // concept requirements
138  __glibcxx_function_requires(_BidirectionalIteratorConcept<
139  _BidirectionalIterator>)
140  if (__n > 0)
141  while (__n--)
142  ++__i;
143  else
144  while (__n++)
145  --__i;
146  }
147 
148  template<typename _RandomAccessIterator, typename _Distance>
149  inline void
150  __advance(_RandomAccessIterator& __i, _Distance __n,
151  random_access_iterator_tag)
152  {
153  // concept requirements
154  __glibcxx_function_requires(_RandomAccessIteratorConcept<
155  _RandomAccessIterator>)
156  __i += __n;
157  }
158 
159  /**
160  * @brief A generalization of pointer arithmetic.
161  * @param __i An input iterator.
162  * @param __n The @a delta by which to change @p __i.
163  * @return Nothing.
164  *
165  * This increments @p i by @p n. For bidirectional and random access
166  * iterators, @p __n may be negative, in which case @p __i is decremented.
167  *
168  * For random access iterators, this uses their @c + and @c - operations
169  * and are constant time. For other %iterator classes they are linear time.
170  */
171  template<typename _InputIterator, typename _Distance>
172  inline void
173  advance(_InputIterator& __i, _Distance __n)
174  {
175  // concept requirements -- taken care of in __advance
176  typename iterator_traits<_InputIterator>::difference_type __d = __n;
177  std::__advance(__i, __d, std::__iterator_category(__i));
178  }
179 
180 #if __cplusplus >= 201103L
181 
182  template<typename _ForwardIterator>
183  inline _ForwardIterator
184  next(_ForwardIterator __x, typename
185  iterator_traits<_ForwardIterator>::difference_type __n = 1)
186  {
187  std::advance(__x, __n);
188  return __x;
189  }
190 
191  template<typename _BidirectionalIterator>
192  inline _BidirectionalIterator
193  prev(_BidirectionalIterator __x, typename
194  iterator_traits<_BidirectionalIterator>::difference_type __n = 1)
195  {
196  std::advance(__x, -__n);
197  return __x;
198  }
199 
200 #endif // C++11
201 
202 _GLIBCXX_END_NAMESPACE_VERSION
203 } // namespace
204 
205 #endif /* _STL_ITERATOR_BASE_FUNCS_H */
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)