Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Examples

Random Access Iterator
Mutable and Constant Iterator Interoperability
Zip Iterator / Proxy Iterator
Reimplementing back_insert_iterator
Reimplementing reverse_iterator

#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)));
    }
}


PrevUpHomeNext