...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Copyright © 2019 T. Zachary 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
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 | |
---|---|
C++20 versions of |
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 | |
---|---|
Boost.STLInterfaces's |
Last revised: December 02, 2021 at 06:54:13 GMT |