libstdc++
stl_iterator_base_funcs.h
Go to the documentation of this file.
1 // Functions used by iterators -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996-1998
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file stl_iterator_base_funcs.h
53  * This is an internal header file, included by other library headers.
54  * You should not attempt to use it directly.
55  *
56  * This file contains all of the general iterator-related utility
57  * functions, such as distance() and advance().
58  */
59 
60 #ifndef _STL_ITERATOR_BASE_FUNCS_H
61 #define _STL_ITERATOR_BASE_FUNCS_H 1
62 
63 #pragma GCC system_header
64 #include <bits/concept_check.h>
65 
66 _GLIBCXX_BEGIN_NAMESPACE(std)
67 
68  template<typename _InputIterator>
69  inline typename iterator_traits<_InputIterator>::difference_type
70  __distance(_InputIterator __first, _InputIterator __last,
71  input_iterator_tag)
72  {
73  // concept requirements
74  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
75 
76  typename iterator_traits<_InputIterator>::difference_type __n = 0;
77  while (__first != __last)
78  {
79  ++__first;
80  ++__n;
81  }
82  return __n;
83  }
84 
85  template<typename _RandomAccessIterator>
86  inline typename iterator_traits<_RandomAccessIterator>::difference_type
87  __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
88  random_access_iterator_tag)
89  {
90  // concept requirements
91  __glibcxx_function_requires(_RandomAccessIteratorConcept<
92  _RandomAccessIterator>)
93  return __last - __first;
94  }
95 
96  /**
97  * @brief A generalization of pointer arithmetic.
98  * @param first An input iterator.
99  * @param last An input iterator.
100  * @return The distance between them.
101  *
102  * Returns @c n such that first + n == last. This requires that @p last
103  * must be reachable from @p first. Note that @c n may be negative.
104  *
105  * For random access iterators, this uses their @c + and @c - operations
106  * and are constant time. For other %iterator classes they are linear time.
107  */
108  template<typename _InputIterator>
109  inline typename iterator_traits<_InputIterator>::difference_type
110  distance(_InputIterator __first, _InputIterator __last)
111  {
112  // concept requirements -- taken care of in __distance
113  return std::__distance(__first, __last,
114  std::__iterator_category(__first));
115  }
116 
117  template<typename _InputIterator, typename _Distance>
118  inline void
119  __advance(_InputIterator& __i, _Distance __n, input_iterator_tag)
120  {
121  // concept requirements
122  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
123  while (__n--)
124  ++__i;
125  }
126 
127  template<typename _BidirectionalIterator, typename _Distance>
128  inline void
129  __advance(_BidirectionalIterator& __i, _Distance __n,
130  bidirectional_iterator_tag)
131  {
132  // concept requirements
133  __glibcxx_function_requires(_BidirectionalIteratorConcept<
134  _BidirectionalIterator>)
135  if (__n > 0)
136  while (__n--)
137  ++__i;
138  else
139  while (__n++)
140  --__i;
141  }
142 
143  template<typename _RandomAccessIterator, typename _Distance>
144  inline void
145  __advance(_RandomAccessIterator& __i, _Distance __n,
146  random_access_iterator_tag)
147  {
148  // concept requirements
149  __glibcxx_function_requires(_RandomAccessIteratorConcept<
150  _RandomAccessIterator>)
151  __i += __n;
152  }
153 
154  /**
155  * @brief A generalization of pointer arithmetic.
156  * @param i An input iterator.
157  * @param n The "delta" by which to change @p i.
158  * @return Nothing.
159  *
160  * This increments @p i by @p n. For bidirectional and random access
161  * iterators, @p n may be negative, in which case @p i is decremented.
162  *
163  * For random access iterators, this uses their @c + and @c - operations
164  * and are constant time. For other %iterator classes they are linear time.
165  */
166  template<typename _InputIterator, typename _Distance>
167  inline void
168  advance(_InputIterator& __i, _Distance __n)
169  {
170  // concept requirements -- taken care of in __advance
171  typename iterator_traits<_InputIterator>::difference_type __d = __n;
172  std::__advance(__i, __d, std::__iterator_category(__i));
173  }
174 
175 #ifdef __GXX_EXPERIMENTAL_CXX0X__
176  template<typename _InputIterator>
177  inline _InputIterator
178  next(_InputIterator __x, typename
179  iterator_traits<_InputIterator>::difference_type __n = 1)
180  {
181  std::advance(__x, __n);
182  return __x;
183  }
184 
185  template<typename _BidirectionalIterator>
186  inline _BidirectionalIterator
187  prev(_BidirectionalIterator __x, typename
188  iterator_traits<_BidirectionalIterator>::difference_type __n = 1)
189  {
190  std::advance(__x, -__n);
191  return __x;
192  }
193 #endif
194 
195 _GLIBCXX_END_NAMESPACE
196 
197 #endif /* _STL_ITERATOR_BASE_FUNCS_H */