ceph/src/boost/libs/stl_interfaces/example/reverse_iterator.cpp

   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 {
  32     reverse_iterator() : it_() {}
  33     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
  38     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.
  42     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.
  61     diff_t operator-(reverse_iterator other) const
  62     {
  63         return -std::distance(other.it_, it_);
  64     }
  65     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
  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 //]