...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
#include <boost/stl_interfaces/iterator_interface.hpp> #include <algorithm> #include <array> #include <cassert> // This is a minimal random access iterator. It uses default template // parameters for most stl_interfaces template parameters. struct simple_random_access_iterator : boost::stl_interfaces::iterator_interface< #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS simple_random_access_iterator, #endif std::random_access_iterator_tag, int> { // This default constructor does not initialize it_, since that's how int * // works as well. This allows optimum performance in code paths where // initializing a single pointer may be measurable. It is also a // reasonable choice to initialize with nullptr. simple_random_access_iterator() noexcept {} simple_random_access_iterator(int * it) noexcept : it_(it) {} int & operator*() const noexcept { return *it_; } simple_random_access_iterator & operator+=(std::ptrdiff_t i) noexcept { it_ += i; return *this; } auto operator-(simple_random_access_iterator other) const noexcept { return it_ - other.it_; } private: int * it_; }; int main() { std::array<int, 10> ints = {{0, 2, 1, 3, 4, 5, 7, 6, 8, 9}}; simple_random_access_iterator first(ints.data()); simple_random_access_iterator last(ints.data() + ints.size()); std::sort(first, last); assert(ints == (std::array<int, 10>{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}})); }
#include <boost/stl_interfaces/iterator_interface.hpp> #include <algorithm> #include <array> #include <numeric> #include <cassert> // This is a random access iterator templated on a value type. The ValueType // template parameter allows us easily to define const and non-const iterators // from the same template. template<typename ValueType> struct random_access_iterator : boost::stl_interfaces::iterator_interface< #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS random_access_iterator<ValueType>, #endif std::random_access_iterator_tag, ValueType> { static_assert(std::is_object<ValueType>::value, ""); // Default constructor. constexpr random_access_iterator() noexcept {} // Construction from an underlying pointer. constexpr random_access_iterator(ValueType * it) noexcept : it_(it) {} // Implicit conversion from an existing random_access_iterator with a // possibly different value type. The enable_if logic here just enforces // that this constructor only participates in overload resolution when the // expression it_ = other.it_ is well-formed. template< typename ValueType2, typename E = std::enable_if_t< std::is_convertible<ValueType2 *, ValueType *>::value>> constexpr random_access_iterator( random_access_iterator<ValueType2> other) noexcept : it_(other.it_) {} constexpr ValueType & operator*() const noexcept { return *it_; } constexpr random_access_iterator & operator+=(std::ptrdiff_t i) noexcept { it_ += i; return *this; } constexpr auto operator-(random_access_iterator other) const noexcept { return it_ - other.it_; } private: ValueType * it_; // This friendship is necessary to enable the implicit conversion // constructor above to work. template<typename ValueType2> friend struct random_access_iterator; }; using iterator = random_access_iterator<int>; using const_iterator = random_access_iterator<int const>; int main() { std::array<int, 10> ints = {{0, 2, 1, 3, 4, 5, 7, 6, 8, 9}}; // Create and use two mutable iterators. iterator first(ints.data()); iterator last(ints.data() + ints.size()); std::sort(first, last); assert(ints == (std::array<int, 10>{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}})); // Create and use two constant iterators, one from an existing mutable // iterator. std::array<int, 10> int_sums; const_iterator cfirst(ints.data()); const_iterator clast = last; std::partial_sum(cfirst, clast, int_sums.begin()); assert(int_sums == (std::array<int, 10>{{0, 1, 3, 6, 10, 15, 21, 28, 36, 45}})); }
#include <boost/stl_interfaces/iterator_interface.hpp> #include <algorithm> #include <array> #include <tuple> #include <cassert> // This is a zip iterator, meaning that it iterates over a notional sequence // of pairs that is formed from two actual sequences of scalars. To make this // iterator writable, it needs to have a reference type that is not actually a // reference -- the reference type is a pair of references, std::tuple<int &, // int &>. struct zip_iterator : boost::stl_interfaces::proxy_iterator_interface< #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS zip_iterator, #endif std::random_access_iterator_tag, std::tuple<int, int>, std::tuple<int &, int &>> { constexpr zip_iterator() noexcept : it1_(), it2_() {} constexpr zip_iterator(int * it1, int * it2) noexcept : it1_(it1), it2_(it2) {} constexpr std::tuple<int &, int &> operator*() const noexcept { return std::tuple<int &, int &>{*it1_, *it2_}; } constexpr zip_iterator & operator += (std::ptrdiff_t i) noexcept { it1_ += i; it2_ += i; return *this; } constexpr auto operator-(zip_iterator other) const noexcept { return it1_ - other.it1_; } private: int * it1_; int * it2_; }; namespace std { // Required for std::sort to work with zip_iterator. Without this // overload, std::sort eventually tries to call std::swap(*it1, *it2), // *it1 and *it2 are rvalues, and std::swap() takes mutable lvalue // references. That makes std::swap(*it1, *it2) ill-formed. // // Note that this overload does not conflict with any other swap() // overloads, since this one takes rvalue reference parameters. // // Also note that this overload has to be in namespace std only because // ADL cannot find it anywhere else. If // zip_iterator::reference/std::tuple's template parameters were not // builtins, this overload could be in whatever namespace those template // parameters were declared in. void swap(zip_iterator::reference && lhs, zip_iterator::reference && rhs) { using std::swap; swap(std::get<0>(lhs), std::get<0>(rhs)); swap(std::get<1>(lhs), std::get<1>(rhs)); } } int main() { std::array<int, 10> ints = {{2, 0, 1, 5, 3, 6, 8, 4, 9, 7}}; std::array<int, 10> ones = {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}}; { std::array<std::tuple<int, int>, 10> const result = {{ {2, 1}, {0, 1}, {1, 1}, {5, 1}, {3, 1}, {6, 1}, {8, 1}, {4, 1}, {9, 1}, {7, 1}, }}; zip_iterator first(ints.data(), ones.data()); zip_iterator last(ints.data() + ints.size(), ones.data() + ones.size()); assert(std::equal(first, last, result.begin(), result.end())); } { std::array<std::tuple<int, int>, 10> const result = {{ {0, 1}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {7, 1}, {8, 1}, {9, 1}, }}; zip_iterator first(ints.data(), ones.data()); zip_iterator last(ints.data() + ints.size(), ones.data() + ones.size()); assert(!std::equal(first, last, result.begin(), result.end())); std::sort(first, last); assert(std::equal(first, last, result.begin(), result.end())); } }
#include <boost/stl_interfaces/iterator_interface.hpp> #include <algorithm> #include <vector> #include <cassert> // This is an output iterator that holds a reference to a container, and calls // push_back() on that container when it is written to, just like // std::back_insert_iterator. This is not a lot less code to write than the // implementation of std::back_insert_iterator, but it demonstrates that // iterator_interface is flexible enough to handle this odd kind of iterator. template<typename Container> struct back_insert_iterator : boost::stl_interfaces::iterator_interface< #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS back_insert_iterator<Container>, #endif std::output_iterator_tag, typename Container::value_type, back_insert_iterator<Container> &> { // For concept requirements. back_insert_iterator() : c_(nullptr) {} // Construct from a container. explicit back_insert_iterator(Container & c) : c_(std::addressof(c)) {} // When writing to *this, copy v into the container via push_back(). back_insert_iterator & operator=(typename Container::value_type const & v) { c_->push_back(v); return *this; } // When writing to *this, move v into the container via push_back(). back_insert_iterator & operator=(typename Container::value_type && v) { c_->push_back(std::move(v)); return *this; } // Dereferencing *this just returns a reference to *this, so that the // expression *it = value uses the operator=() overloads above. back_insert_iterator & operator*() { return *this; } // There is no underlying sequence over which we are iterating, so there's // nowhere to go in next(). Do nothing. back_insert_iterator & operator++() { return *this; } using base_type = boost::stl_interfaces::iterator_interface< #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS back_insert_iterator<Container>, #endif std::output_iterator_tag, typename Container::value_type, back_insert_iterator<Container> &>; using base_type::operator++; private: Container * c_; }; // A convenience function that creates a back_insert_iterator<Container>. template<typename Container> back_insert_iterator<Container> back_inserter(Container & c) { return back_insert_iterator<Container>(c); } int main() { std::vector<int> ints = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}; std::vector<int> ints_copy; std::copy(ints.begin(), ints.end(), ::back_inserter(ints_copy)); assert(ints_copy == ints); }
#include <boost/stl_interfaces/iterator_interface.hpp> #include <algorithm> #include <list> #include <vector> #include <cassert> // In all the previous examples, we only had to implement a subset of the six // possible user-defined basis operations that was needed for one particular // iterator concept. For reverse_iterator, we want to support bidirectional, // random access, and contiguous iterators. We therefore need to provide all // the basis operations that might be needed. template<typename BidiIter> struct reverse_iterator : boost::stl_interfaces::iterator_interface< #if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS reverse_iterator<BidiIter>, #endif #if 201703L < __cplusplus && defined(__cpp_lib_ranges) boost::stl_interfaces::v2::v2_dtl::iter_concept_t<BidiIter>, #else typename std::iterator_traits<BidiIter>::iterator_category, #endif typename std::iterator_traits<BidiIter>::value_type> { reverse_iterator() : it_() {} reverse_iterator(BidiIter it) : it_(it) {} using ref_t = typename std::iterator_traits<BidiIter>::reference; using diff_t = typename std::iterator_traits<BidiIter>::difference_type; ref_t operator*() const { return *std::prev(it_); } // These three are used only when BidiIter::iterator_category is // std::bidirectional_iterator_tag. bool operator==(reverse_iterator other) const { return it_ == other.it_; } // Even though iterator_interface-derived bidirectional iterators are // usually given operator++() and operator--() members, it turns out that // operator+=() below amounts to the same thing. That's good, since // having operator++() and operator+=() in this class would have lead to // ambiguities in iterator_interface. // These two are only used when BidiIter::iterator_category is // std::random_access_iterator_tag or std::contiguous_iterator_tag. Even // so, they need to compile even when BidiIter::iterator_category is // std::bidirectional_iterator_tag. That means we have to use // std::distance() and std::advance() instead of operator-() and // operator+=(). // // Don't worry, the O(n) bidirectional implementations of std::distance() // and std::advance() are dead code, because compare() and advance() are // never even called when BidiIter::iterator_category is // std::bidirectional_iterator_tag. diff_t operator-(reverse_iterator other) const { return -std::distance(other.it_, it_); } reverse_iterator & operator+=(diff_t n) { std::advance(it_, -n); return *this; } // No need for a using declaration to make // iterator_interface::operator++(int) visible, because we're not defining // operator++() in this template. private: BidiIter it_; }; using rev_bidi_iter = reverse_iterator<std::list<int>::iterator>; using rev_ra_iter = reverse_iterator<std::vector<int>::iterator>; int main() { { std::list<int> ints = {4, 3, 2}; std::list<int> ints_copy; std::copy( rev_bidi_iter(ints.end()), rev_bidi_iter(ints.begin()), std::back_inserter(ints_copy)); std::reverse(ints.begin(), ints.end()); assert(ints_copy == ints); } { std::vector<int> ints = {4, 3, 2}; std::vector<int> ints_copy(ints.size()); std::copy( rev_ra_iter(ints.end()), rev_ra_iter(ints.begin()), ints_copy.begin()); std::reverse(ints.begin(), ints.end()); assert(ints_copy == ints); } { using rev_ptr_iter = reverse_iterator<int *>; int ints[3] = {4, 3, 2}; int ints_copy[3]; std::copy( rev_ptr_iter(std::end(ints)), rev_ptr_iter(std::begin(ints)), std::begin(ints_copy)); std::reverse(std::begin(ints), std::end(ints)); assert(std::equal( std::begin(ints_copy), std::end(ints_copy), std::begin(ints), std::end(ints))); } }