1 // Copyright (C) 2019 T. Zachary Laine
2 //
3 // Distributed under the Boost Software License, Version 1.0. (See
4 // accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6 //[ reverse_iterator
7 #include <boost/stl_interfaces/iterator_interface.hpp>
8
9 #include <algorithm>
10 #include <list>
11 #include <vector>
12
13 #include <cassert>
14
15
16 // In all the previous examples, we only had to implement a subset of the six
17 // possible user-defined basis operations that was needed for one particular
18 // iterator concept. For reverse_iterator, we want to support bidirectional,
19 // random access, and contiguous iterators. We therefore need to provide all
20 // the basis operations that might be needed.
21 template<typename BidiIter>
22 struct reverse_iterator
23 : boost::stl_interfaces::iterator_interface<
24 reverse_iterator<BidiIter>,
25 #if 201703L < __cplusplus && defined(__cpp_lib_ranges)
26 boost::stl_interfaces::v2::detail::iter_concept_t<BidiIter>,
27 #else
28 typename std::iterator_traits<BidiIter>::iterator_category,
29 #endif
30 typename std::iterator_traits<BidiIter>::value_type>
31 {
reverse_iteratorreverse_iterator32 reverse_iterator() : it_() {}
reverse_iteratorreverse_iterator33 reverse_iterator(BidiIter it) : it_(it) {}
34
35 using ref_t = typename std::iterator_traits<BidiIter>::reference;
36 using diff_t = typename std::iterator_traits<BidiIter>::difference_type;
37
operator *reverse_iterator38 ref_t operator*() const { return *std::prev(it_); }
39
40 // These three are used only when BidiIter::iterator_category is
41 // std::bidirectional_iterator_tag.
operator ==reverse_iterator42 bool operator==(reverse_iterator other) const { return it_ == other.it_; }
43
44 // Even though iterator_interface-derived bidirectional iterators are
45 // usually given operator++() and operator--() members, it turns out that
46 // operator+=() below amounts to the same thing. That's good, since
47 // having operator++() and operator+=() in this class would have lead to
48 // ambiguities in iterator_interface.
49
50 // These two are only used when BidiIter::iterator_category is
51 // std::random_access_iterator_tag or std::contiguous_iterator_tag. Even
52 // so, they need to compile even when BidiIter::iterator_category is
53 // std::bidirectional_iterator_tag. That means we have to use
54 // std::distance() and std::advance() instead of operator-() and
55 // operator+=().
56 //
57 // Don't worry, the O(n) bidirectional implementations of std::distance()
58 // and std::advance() are dead code, because compare() and advance() are
59 // never even called when BidiIter::iterator_category is
60 // std::bidirectional_iterator_tag.
operator -reverse_iterator61 diff_t operator-(reverse_iterator other) const
62 {
63 return -std::distance(other.it_, it_);
64 }
operator +=reverse_iterator65 reverse_iterator & operator+=(diff_t n)
66 {
67 std::advance(it_, -n);
68 return *this;
69 }
70
71 // No need for a using declaration to make
72 // iterator_interface::operator++(int) visible, because we're not defining
73 // operator++() in this template.
74
75 private:
76 BidiIter it_;
77 };
78
79 using rev_bidi_iter = reverse_iterator<std::list<int>::iterator>;
80 using rev_ra_iter = reverse_iterator<std::vector<int>::iterator>;
81
82
main()83 int main()
84 {
85 {
86 std::list<int> ints = {4, 3, 2};
87 std::list<int> ints_copy;
88 std::copy(
89 rev_bidi_iter(ints.end()),
90 rev_bidi_iter(ints.begin()),
91 std::back_inserter(ints_copy));
92 std::reverse(ints.begin(), ints.end());
93 assert(ints_copy == ints);
94 }
95
96 {
97 std::vector<int> ints = {4, 3, 2};
98 std::vector<int> ints_copy(ints.size());
99 std::copy(
100 rev_ra_iter(ints.end()),
101 rev_ra_iter(ints.begin()),
102 ints_copy.begin());
103 std::reverse(ints.begin(), ints.end());
104 assert(ints_copy == ints);
105 }
106
107 {
108 using rev_ptr_iter = reverse_iterator<int *>;
109
110 int ints[3] = {4, 3, 2};
111 int ints_copy[3];
112 std::copy(
113 rev_ptr_iter(std::end(ints)),
114 rev_ptr_iter(std::begin(ints)),
115 std::begin(ints_copy));
116 std::reverse(std::begin(ints), std::end(ints));
117 assert(std::equal(
118 std::begin(ints_copy),
119 std::end(ints_copy),
120 std::begin(ints),
121 std::end(ints)));
122 }
123 }
124 //]
125