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

Chapter 37. 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: April 06, 2022 at 21:11:07 GMT


PrevUpHomeNext