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 a snapshot of the develop branch, built from commit 9d207d7553.
PrevUpHomeNext

Chapter 39. Boost.STLInterfaces

Zach Laine

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Table of Contents

Introduction
This Library's Relationship to Boost.Iterator
The v1 and v2 Namespaces, and the Use of C++20 Concepts
Tutorial: iterator_interface
Tutorial: view_interface
Tutorial: sequence_container_interface
Tutorial: reverse_iterator
Examples
Random Access Iterator
Mutable and Constant Iterator Interoperability
Zip Iterator / Proxy Iterator
Reimplementing back_insert_iterator
Reimplementing reverse_iterator
Compiler Support
Reference
Headers
Rationale

Writing STL iterators, views, and containers is surprisingly hard. There are a lot of things that can subtly go wrong. It is also very tedious, which of course makes it error-prone.

Iterators have numerous typedefs and operations, even though all the operations of a given iterator can be implemented in terms of at most four operations (and usually only three). Writing all the other operations yields very similar-looking code that is hard to review, and all but requires that you write full-coverage tests for each iterator.

Writing view types like those found in std::ranges is also laborious, considering that most of each view type's API can be derived from begin() and end(). C++20 has a template that does exactly this, std::ranges::view_interface; Boost.STLInterfaces provides a pre-C++20-friendly implementation.

Most daunting of all is the task of writing a type or template that meets the container requirements in the standard. Boost.STLInterfaces provides another template called sequence_container_interface that reduces the implementation and testing burden dramatically.

[Note] Note

C++20 versions of iterator_interface and sequence_container_interface are provided (C++20 provides std::view_interface). These are constrained templates using C++20 concepts. These are in the boost::stl_interfaces::v2 namespace, and are considered experimental, because at the time of this writing, no C++20-conforming compiler exists.

A Quick Example

Here is an example of the iterator portion of the library. Let's say that we wanted to make a random access iterator that represents a string of arbitrary length constructed by repeating a shorter string. Let's call this iterator repeated_chars_iterator. Here it is in action:

repeated_chars_iterator first("foo", 3, 0); // 3 is the length of "foo", 0 is this iterator's position.
repeated_chars_iterator last("foo", 3, 7);  // Same as above, but now the iterator's position is 7.
std::string result;
std::copy(first, last, std::back_inserter(result));
assert(result == "foofoof");

There's nothing in the standard library that gets us that kind of behavior, so we have to write it. This library seeks to turn what we write from this:

struct repeated_chars_iterator
{
    using value_type = char;
    using difference_type = std::ptrdiff_t;
    using pointer = char const *;
    using reference = char const;
    using iterator_category = std::random_access_iterator_tag;

    constexpr repeated_chars_iterator() noexcept :
        first_(nullptr),
        size_(0),
        n_(0)
    {}
    constexpr repeated_chars_iterator(
        char const * first,
        difference_type size,
        difference_type n) noexcept :
        first_(first),
        size_(size),
        n_(n)
    {}

    constexpr reference operator*() const noexcept
    {
        return first_[n_ % size_];
    }

    constexpr value_type operator[](difference_type n) const noexcept
    {
        return first_[(n_ + n) % size_];
    }

    constexpr repeated_chars_iterator & operator++() noexcept
    {
        ++n_;
        return *this;
    }
    constexpr repeated_chars_iterator operator++(int)noexcept
    {
        repeated_chars_iterator retval = *this;
        ++*this;
        return retval;
    }
    constexpr repeated_chars_iterator & operator+=(difference_type n) noexcept
    {
        n_ += n;
        return *this;
    }

    constexpr repeated_chars_iterator & operator--() noexcept
    {
        --n_;
        return *this;
    }
    constexpr repeated_chars_iterator operator--(int)noexcept
    {
        repeated_chars_iterator retval = *this;
        --*this;
        return retval;
    }
    constexpr repeated_chars_iterator & operator-=(difference_type n) noexcept
    {
        n_ -= n;
        return *this;
    }

    friend constexpr bool operator==(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return lhs.first_ == rhs.first_ && lhs.n_ == rhs.n_;
    }
    friend constexpr bool operator!=(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return !(lhs == rhs);
    }
    friend constexpr bool operator<(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return lhs.first_ == rhs.first_ && lhs.n_ < rhs.n_;
    }
    friend constexpr bool operator<=(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return lhs == rhs || lhs < rhs;
    }
    friend constexpr bool operator>(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return rhs < lhs;
    }
    friend constexpr bool operator>=(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return rhs <= lhs;
    }

    friend constexpr repeated_chars_iterator
    operator+(repeated_chars_iterator lhs, difference_type rhs) noexcept
    {
        return lhs += rhs;
    }
    friend constexpr repeated_chars_iterator
    operator+(difference_type lhs, repeated_chars_iterator rhs) noexcept
    {
        return rhs += lhs;
    }
    friend constexpr repeated_chars_iterator
    operator-(repeated_chars_iterator lhs, difference_type rhs) noexcept
    {
        return lhs -= rhs;
    }
    friend constexpr difference_type operator-(
        repeated_chars_iterator lhs, repeated_chars_iterator rhs) noexcept
    {
        return lhs.n_ - rhs.n_;
    }

private:
    char const * first_;
    difference_type size_;
    difference_type n_;
};

(that's a lot of code!) into this:

struct repeated_chars_iterator : boost::stl_interfaces::iterator_interface<
                                     repeated_chars_iterator,
                                     std::random_access_iterator_tag,
                                     char,
                                     char>
{
    constexpr repeated_chars_iterator() noexcept :
        first_(nullptr),
        size_(0),
        n_(0)
    {}
    constexpr repeated_chars_iterator(
        char const * first, difference_type size, difference_type n) noexcept :
        first_(first),
        size_(size),
        n_(n)
    {}

    constexpr char operator*() const noexcept { return first_[n_ % size_]; }
    constexpr repeated_chars_iterator & operator+=(std::ptrdiff_t i) noexcept
    {
        n_ += i;
        return *this;
    }
    constexpr auto operator-(repeated_chars_iterator other) const noexcept
    {
        return n_ - other.n_;
    }

private:
    char const * first_;
    difference_type size_;
    difference_type n_;
};

Ah, that's better. Both of these definitions for repeated_chars_iterator have the same semantics and performance profile. It's just a lot less code to write the second one, and writing the second one is more novice-friendly.

[Note] Note

Boost.STLInterfaces's iterator_interface implements iterators that model the C++20 iterator concepts.

Last revised: October 30, 2020 at 09:09:08 GMT


PrevUpHomeNext