• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1[section:algorithms Algorithms]
2
3[section:advance Function template `advance()`]
4
5The `boost::iterators::advance` function template is an adapted version of `std::advance` for the Boost iterator [link iterator.concepts.traversal traversal concepts].
6
7[heading Header]
8
9    <boost/iterator/advance.hpp>
10
11[heading Synopsis]
12
13    template <typename Iterator, typename Distance>
14    constexpr void advance(Iterator& it, Distance n);
15
16
17[heading Description]
18
19Moves `it` forward by `n` increments (or backward by `|n|` decrements if `n` is negative).
20
21[heading Requirements]
22
23`Iterator` should model Incrementable Iterator.
24
25[heading Preconditions]
26
27Let `it`[sub `i`] be the iterator obtained by incrementing (or decrementing if `n` is negative) `it` by `i`. All the iterators `it`[sub `i`] for `i` = 0, 1, 2, ..., `|n|` should be valid.
28
29If `Iterator` does not model [link iterator.concepts.traversal.bidirectional Bidirectional Traversal Iterator], `n` should be non-negative.
30
31[heading Complexity]
32
33If `Iterator` models [link iterator.concepts.traversal.random_access Random Access Traversal Iterator], it takes constant time; otherwise it takes linear time.
34
35[heading Notes]
36
37* This function is not a customization point and is protected against being found by argument-dependent lookup (ADL).
38* This function is `constexpr` only in C++14 or later.
39
40[heading Acknowledgements]
41
42Contributed by Michel Morin.
43
44[endsect]
45
46[section:distance Function template `distance()`]
47
48The `boost::iterators::distance` function template is an adapted version of `std::distance` for the Boost iterator [link iterator.concepts.traversal traversal concepts].
49
50[heading Header]
51
52    <boost/iterator/distance.hpp>
53
54[heading Synopsis]
55
56    template <typename Iterator>
57    constexpr typename iterator_difference<Iterator>::type
58    distance(Iterator first, Iterator last);
59
60[heading Description]
61
62Computes the (signed) distance from `first` to `last`.
63
64[heading Requirements]
65
66`Iterator` should model [link iterator.concepts.traversal.single_pass Single Pass Iterator].
67
68[heading Preconditions]
69
70If `Iterator` models [link iterator.concepts.traversal.random_access Random Access Traversal Iterator], `[first, last)` or `[last, first)` should be valid; otherwise `[first, last)` should be valid.
71
72[heading Complexity]
73
74If `Iterator` models [link iterator.concepts.traversal.random_access Random Access Traversal Iterator], it takes constant time; otherwise it takes linear time.
75
76[heading Notes]
77
78* This function is not a customization point and is protected against being found by argument-dependent lookup (ADL).
79* This function is `constexpr` only in C++14 or later.
80
81[heading Acknowledgements]
82
83Contributed by Michel Morin.
84
85[endsect]
86
87[section:next_prior Function templates `next()` and `prior()`]
88
89Certain data types, such as the C++ Standard Library's forward and bidirectional iterators, do not provide addition and subtraction via `operator+()` or `operator-()`. This means that non-modifying computation of the next or prior value requires a temporary, even though `operator++()` or `operator--()` is provided. It also means that writing code like `itr+1` inside a template restricts the iterator category to random access iterators.
90
91The `next()` and `prior()` functions defined in `boost/next_prior.hpp` provide a simple way around these problems.
92
93[heading Synopsis]
94
95    template <class T>
96    T next(T x)
97    {
98        return ++x;
99    }
100
101    template <class T, class Distance>
102    T next(T x, Distance n)
103    {
104        std::advance(x, n);
105        return x;
106    }
107
108    template <class T>
109    T prior(T x)
110    {
111        return --x;
112    }
113
114    template <class T, class Distance>
115    T prior(T x, Distance n)
116    {
117        std::advance(x, -n);
118        return x;
119    }
120
121[note Function implementations above are given for exposition only. The actual implementation has the same effect for iterators, but has different properties, as documented later.]
122
123[heading Usage]
124
125Usage is simple:
126
127    const std::list<T>::iterator p = get_some_iterator();
128    const std::list<T>::iterator prev = boost::prior(p);
129    const std::list<T>::iterator next = boost::next(prev, 2);
130
131The distance from the given iterator should be supplied as an absolute value. For example, the iterator four iterators prior to the given iterator `p` may be obtained by `prior(p, 4)`.
132
133With C++11, the Standard Library provides `std::next()` and `std::prev()` function templates, which serve the same purpose. However, there are advantages to `boost::next()` and `boost::prior()`.
134
135First, `boost::next()` and `boost::prior()` are compatible not only with iterators but with any type that provides arithmetic operators `operator++()`, `operator--()`, `operator+()`, `operator-()`, `operator+=()` or `operator-=()`. For example, this is possible:
136
137    int x = 10;
138    int y = boost::next(x, 5);
139    assert(y == 15);
140
141Second, `boost::next()` and `boost::prior()` use [link iterator.concepts.traversal traversal categories] to select the most efficient implementation. For some kinds of iterators, such as [link iterator.specialized.transform transform iterators], the standard iterator category does not reflect the traversal category correctly and therefore `std::next()` and `std::prev()` will fall back to linear complexity.
142
143[heading Acknowledgements]
144
145Contributed by [@http://www.boost.org/people/dave_abrahams.htm Dave Abrahams]. Two-argument versions by Daniel Walker.
146
147[endsect]
148
149[endsect]
150