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 0f79ae966a.
PrevUpHomeNext

Tutorial: sequence_container_interface

[Note] Note

All the member functions provided by sequence_container_interface are in your container's base class — sequence_container_interface — and can therefore be hidden if you define a member function with the same name in your derived container. If you don't like the semantics of any sequence_container_interface-provided member function, feel free to replace it.

The sequence_container_interface Template

As mentioned earlier, writing containers is very tedious. The container requirements tables in the C++ standard are long and complicated, and there are a lot of them. The requirements often call for multiple overloads of a function, all of which could be implemented in terms of just one overload.

There is a large development cost associated with implementing a standard-compliant container. As a result very few people do so. sequence_container_interface exists to make bring that large development time way, way down.

Here is its declaration:

template<typename Derived, element_layout Contiguity = element_layout::discontiguous>
struct sequence_container_interface;

Just as with view_interface, sequence_container_interface takes the derived type and an optional non-type template parameter that indicates whether Derived's iterators are contiguous. The non-type parameter is necessary to support pre-C++20 code.

How sequence_container_interface is Organized

The tables below represent a subset of the operations needed for each of the container requirements tables in the standard. Here are the tables that apply to sequence containers (from [container.requirements] in the standard):

Each requirements table lists all the types and operations required by a standard-conforming container. All of these sets of requirements are supported by sequence_container_interface, except the allocator-aware container requirements. The container and sequence container requirements are required for any sequence container. sequence_container_interface provides each member in any table above (again, except the allocator-aware ones). Each member is individually constrained, so if a given member (say, a particular insert() overload) is ill-formed, it will not be usable in the resulting container.

[Note] Note

All table requirements satisfied by Boost.STLInterfaces use the 2017 version of the C++ Standard. See your favorite online resource for the contents of these tables. Many people like eel.is, which is really easy to navigate.

Note that sequence_container_interface does not interact at all with the allocator-aware container requirements, the associative container requirements, or the unordered associative container requirements. Specifically, nothing precludes you from satisfying any of those sets or requirements — it's just that sequence_container_interface does not.

How sequence_container_interface Works

To use sequence_container_interface, you provide certain operations yourself, and sequence_container_interface fills in the rest. If any provided operation O is not to your liking — say, because you know of a way to do O directly in a way that is more efficient than the way that sequence_container_interface does it — you can implement O yourself. Since your implementation is in a class D derived from sequence_container_interface, it will hide the O from sequence_container_interface.

Below, there are tables that show what user-defined types and operations are required for sequence_container_interface to fulfill all the requirements from one of the C++ Standard's requirements tables. For instance, the table "Optional User-Defined Types and Operations for Containers" below shows what you need to provide to fulfill all the requirements in the standard's "Container requirements [tab:container.req]" table.

So, to use sequence_container_interface to make a std::array-like container (which is not a sequence container, because it has no insert(), erase(), etc.), you need to define the types and operations in the "User-Defined Types and Operations for Containers" table, and optionally the ones in the "Optional User-Defined Types and Operations for Containers".

To make a std::forward_list-like type, you need to define the types and operations in the "User-Defined Types and Operations for Containers" table, and optionally the ones in the "Optional User-Defined Types and Operations for Containers". You would also define the types and operations in the "User-Defined Types and Operations for Sequence Containers" table. You cannot define the types and operations in the "User-Defined Types and Operations for Reversible Containers" table, because your container is forward-only.

To make a std::vector-like type, you would provide the types and operations in all the tables below.

If you have a type that does not have all the operations in one of the tables, that's fine -- you can just implement the operations that your type can do, and whatever operations can be provided by sequence_container_interface in terms of the user-defined operations, will be provided. For example, the std::array-like container described above would have front() — which comes from the optional sequence container requirements — even if you did not write any user-defined insertion or erasure member functions into your container. If it has bidirectional iterators, the std::array-like container will have back() too.

The sequence_container_interface Tables

After each requirements table, there's a table indicating how sequence_container_interface maps the user-defined operations to the operations it provides. These mapping tables can be handy if you have a container that meets only some of the requirements of one of the requirements tables.

In the tables, X is a user-defined type derived from sequence_container_interface containing objects of type T; a and b are objects of type X; i and j are objects of type (possibly const) X::iterator; u is an identifier; r is a non-const value of type X; rv_c is a non-const rvalue of type X; i and j are forward iterators that refer to elements implicitly convertible to T; [i, j) is a range; il is an object of type std::initializer_list<T>; n is a value of type X::size_type, p is a valid constant iterator to a; q is a valid dereferenceable constant iterator to a; [q1, q2) is a valid range of constant iterators to a; t is an lvalue or a const rvalue of T; and rv denotes a non-const rvalue of T. Args is a template parameter pack; args denotes a function parameter pack with the pattern Args &&.

Container

All containers must meet the requirements of this table:

Table 39.3. User-Defined Types and Operations for Containers

Expression

Return Type

Semantics

Assertion/note/pre-/post-condition

X::value_type

T

Compile time only.

X::reference

T &

Compile time only.

X::const_reference

T const &

Compile time only.

X::iterator

An iterator whose value_type is T.

Must meet the forward iterator requirements, and must be convertible to X::const_iterator. Compile time only.

X::const_iterator

A constant iterator whose value_type is T.

Must meet the forward iterator requirements. Compile time only.

X::difference_type

A signed integer type.

Identical to the diference type of X::iterator and X::const_iterator. Compile time only.

X::size_type

An unsigned integer type.

Compile time only.

X u;

Ensures: u.empty()

X u(a);
X u = a;

Ensures: u == a

X u(rv);
X u = rv;

Ensures: u is equal to the value rv_c had before this operation.

a = rv

X &

All existing elements of a are either move assigned to or destroyed.

Ensures: u is equal to the value rv_c had before this operation.

a.~X()

Destroys every element of a; any memory obtained is deallocated.

a.begin()

X::iterator

This is the non-const overload; the const overload is not needed.

a.end()

X::iterator

This is the non-const overload; the const overload is not needed.

a.swap(b)

Convertible to bool.

Exchanges the contents of a and b.

r = a

X &

Ensures: r == a.

a.max_size()

X::size_type

std::distance(l.begin(), l.end()) for the largest possible container l.


[Note] Note

The requirements above are taken from the standard. Even though the standard requires things to be a certain way, you can often define types that work in any context in which a container is supposed to work, even though it varies from the requirements above. In particular, you may want to have non-reference and non-pointer types for X::reference and X::pointer, respectively — and that certainly will not break sequence_container_interface.

If you provide the types and operations above, sequence_container_interface will provide the rest of the container requirements, using this mapping:

Table 39.4. User-Defined Operations to sequence_container_interface Operations

User-Defined

sequence_container_interface-Provided

Note

a.begin()
a.end()

a.empty()
a.size()
a.begin()
a.end()
a.cbegin()
a.cend()

The user-defined begin() and end() are non-const, and the sequence_container_interface-provided ones are const. sequence_container_interface can only provide size() if X::const_iterator is a random access iterator; otherwise, it must be user-defined.

a == b

a != b

Though a == b is provided by sequence_container_interface, any user-defined replacement will be used to provide a != b.

a.swap(b)

swap(a, b)


Reversible Container

Containers that are reverse-iterable must meet the requirements of this table (in addition to the container requirements):

Table 39.5. User-Defined Types and Operations for Reversible Containers

Expression

Return Type

Semantics

Assertion/note/pre-/post-condition

X::reverse_iterator

boost::stl_interfaces::reverse_iterator<X::iterator>

Compile time only.

X::const_reverse_iterator

boost::stl_interfaces::reverse_iterator<X::const_iterator>

Compile time only.


If you provide the types and operations above, sequence_container_interface will provide the rest of the reversible container requirements, using this mapping:

Table 39.6. User-Defined Operations to sequence_container_interface Operations

User-Defined

sequence_container_interface-Provided

Note

a.begin()
a.end()

a.rbegin()
a.rend()
a.crbegin()
a.crend()

The user-defined begin() and end() are non-const, and sequence_container_interface provides both const and non-const overloads of rbegin() and rend(). sequence_container_interface can only provide these operations if X::iterator and X::const_iterator are bidirectional iterators.


Optional Container Operations

Containers that are comparable with <, >, <=, and >= get those operations automatically, so long as T is less-than comparable. In this case, there are no required user-defined operations, so that table is not needed.

sequence_container_interface will provide the optional container requirements using this mapping:

Table 39.7. User-Defined Operations to sequence_container_interface Operations

User-Defined

sequence_container_interface-Provided

Note

a < b

a <= b
a > b
a >= b

Though a < b is provided by sequence_container_interface, any user-defined replacement will be used to provide the other operations listed here.


Sequence Container

Sequence containers meet the requirements of this table (in addition to the container requirements):

Table 39.8. User-Defined Types and Operations for Sequence Containers

Expression

Return Type

Semantics

Assertion/note/pre-/post-condition

X u(n, t);

Constructs a sequence of n copies of t.

Ensures: distance(u.begin(), u.end()) == n

X u(i, j);

Constructs a sequence equal to [i, j).

Ensures: distance(u.begin(), u.end()) == distance(i, j)

X u(il);

X u(il.begin(), il.end());

a.emplace(p, args)

X::iterator

Inserts an object of type T constructed with std::forward<Args>(args)... before p.

args may directly or indirectly refer to a value in a.

a.insert(p, i, j)

X::iterator

Inserts copies of the elements in [i, j) before p.

a.erase(q1, q2)

X::iterator

Erases the elements in the range [q1, q2).


[Important] Important

In the notes for a.emplace(p, args), it says: "args may directly or indirectly refer to a value in a". Don't forget to handle that case in your implementation. Otherwise, a.emplace(a.begin(), a.back()) may do the wrong thing.

If you provide the types and operations above, sequence_container_interface will provide the rest of the sequence container requirements, using this mapping:

Table 39.9. User-Defined Operations to sequence_container_interface Operations

User-Defined

sequence_container_interface-Provided

Note

X(il)

a = il

a.emplace(p, args)

a.insert(p, t)
a.insert(p, rv)

a.insert(p, i, j)

a.insert(p, n, t)
a.insert(p, il)

a.erase(q1, q2)

a.erase(q)
a.clear()

a.erase(q1, q2)
a.insert(p, i, j)

a.assign(i, j)
a.assign(n, t)
a.assign(il)

a.erase(q1, q2) and a.insert(p, i, j) must both be user-defined for sequence_container_interface to provide these operations.


Optional Sequence Container Operations

Sequence containers with front(), back(), or any of the other operations in this table must define these operations (in addition to the container requirements):

Table 39.10. User-Defined Types and Operations for Sequence Containers

Expression

Return Type

Semantics

Assertion/note/pre-/post-condition

a.emplace_front(args)

X::reference

Prepends an object of type T constructed with std::forward<Args>(args)....

a.emplace_back(args)

X::reference

Appends an object of type T constructed with std::forward<Args>(args)....


If you provide the types and operations above, sequence_container_interface will provide the rest of the optional sequence container requirements, using this mapping:

Table 39.11. User-Defined Operations to sequence_container_interface Operations

User-Defined

sequence_container_interface-Provided

Note

a.begin()

a.front()
a[n]
a.at(n)

These operations are provided in const and non-const overloads. sequence_container_interface can only provide a[n] and a.at(n) if X::iterator and X::const_iterator are random access iterators.

a.end()

a.back()

back() is provided in const and non-const overloads. sequence_container_interface can only provide a.back() if X::iterator and X::const_iterator are bidirectional iterators.

a.emplace_front(args)

a.push_front(t)
a.push_front(rv)

a.emplace_back(args)

a.push_back(t)
a.push_back(rv)

a.emplace_front(args)
a.erase(q1, q2)

a.pop_front(t)

a.emplace_front(args) and a.erase(q1, q2) must both be user-defined for sequence_container_interface to provide this operation.

a.emplace_back(args)
a.erase(q1, q2)

a.pop_back(t)

a.emplace_front(args) and a.erase(q1, q2) must both be user-defined for sequence_container_interface to provide this operation.


[Note] Note

emplace_front() and emplace_back() are not needed for some of the sequence_container_interface-provided operations above (e.g. pop_front() and pop_back(), respectively). However, they are each used as the user-defined operation that indicates that the container being defined is front- or back-mutation-friendly.

General Requirements on All User-Defined Operations

There are other requirements listed in the standard that do not appear in any of the requirements tables; user-defined operations must conform to those as well:

Example: static_vector

Let's look at an example. Boost.Container contains a template called boost::container::static_vector, which is a fixed-capacity vector that does not allocate from the heap. We have a similar template in this example, static_vector. It is implemented by deriving from sequence_container_interface, which provides much of the API specified in the STL, based on a subset of the API that the user must provide.

static_vector meets all the sequence container requirements (including many of the optional ones) and reversible container requirements in the standard. It does not meet the allocator-aware container requirements, since it does not allocate. In short, it has the same full API as std::vector, without all the allocatory bits.

// The sections of member functions below are commented as they are in the
// standard for std::vector.  Each section has two numbers: the number of
// member functions in that section, and the number that are missing, because
// they are provided by sequence_container_interface.  The purely
// allocator-specific members are neither present nor part of the counts.
//
// We're passing boost::stl_interfaces::contiguous here, so that
// sequence_container_interface knows that it should provide data().
template<typename T, std::size_t N>
struct static_vector : sequence_container_interface<
                           static_vector<T, N>,
                           boost::stl_interfaces::element_layout::contiguous>
{
    // These are the types required for reversible containers.  These must be
    // user-defined.
    using value_type = T;
    using pointer = T *;
    using const_pointer = T const *;
    using reference = value_type &;
    using const_reference = value_type const &;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using iterator = T *;
    using const_iterator = T const *;
    using reverse_iterator = boost::stl_interfaces::reverse_iterator<iterator>;
    using const_reverse_iterator =
        boost::stl_interfaces::reverse_iterator<const_iterator>;

    // construct/copy/destroy (9 members, skipped 2)
    //
    // Constructors and special member functions all must be user-provided.
    // Were they provided by sequence_container_interface, everything would
    // break, due to the language rules related to them.  However, assignment
    // from std::initializer_list can come from sequence_container_interface.
    static_vector() noexcept : size_(0) {}
    explicit static_vector(size_type n) : size_(0) { resize(n); }
    explicit static_vector(size_type n, T const & x) : size_(0)
    {
        // Note that you must write "this->" before all the member functions
        // provided by sequence_container_interface, which is slightly annoying.
        this->assign(n, x);
    }
    template<
        typename InputIterator,
        typename Enable = std::enable_if_t<std::is_convertible<
            typename std::iterator_traits<InputIterator>::iterator_category,
            std::input_iterator_tag>::value>>
    static_vector(InputIterator first, InputIterator last) : size_(0)
    {
        this->assign(first, last);
    }
    static_vector(std::initializer_list<T> il) :
        static_vector(il.begin(), il.end())
    {}
    static_vector(static_vector const & other) : size_(0)
    {
        this->assign(other.begin(), other.end());
    }
    static_vector(static_vector && other) noexcept(
        noexcept(std::declval<static_vector>().emplace_back(
            std::move(*other.begin())))) :
        size_(0)
    {
        for (auto & element : other) {
            emplace_back(std::move(element));
        }
        other.clear();
    }
    static_vector & operator=(static_vector const & other)
    {
        this->clear();
        this->assign(other.begin(), other.end());
        return *this;
    }
    static_vector & operator=(static_vector && other) noexcept(noexcept(
        std::declval<static_vector>().emplace_back(std::move(*other.begin()))))
    {
        this->clear();
        for (auto & element : other) {
            emplace_back(std::move(element));
        }
        other.clear();
        return *this;
    }
    ~static_vector() { this->clear(); }

    // iterators (2 members, skipped 10)
    //
    // This section is the first big win.  Instead of having to write 12
    // overloads line begin, cbegin, rbegin, crbegin, etc., we can just write
    // 2.
    iterator begin() noexcept { return reinterpret_cast<T *>(buf_); }
    iterator end() noexcept
    {
        return reinterpret_cast<T *>(buf_ + size_ * sizeof(T));
    }

    // capacity (6 members, skipped 2)
    //
    // Most of these are not even part of the general requirements, because
    // some are specific to std::vector and related types.  However, we do get
    // empty and size from sequence_container_interface.
    size_type max_size() const noexcept { return N; }
    size_type capacity() const noexcept { return N; }
    void resize(size_type sz) noexcept
    {
        resize_impl(sz, [] { return T(); });
    }
    void resize(size_type sz, T const & x) noexcept
    {
        resize_impl(sz, [&]() -> T const & { return x; });
    }
    void reserve(size_type n) noexcept { assert(n < capacity()); }
    void shrink_to_fit() noexcept {}

    // element access (skipped 8)
    // data access (skipped 2)
    //
    // Another big win.  sequence_container_interface provides all of the
    // overloads of operator[], at, front, back, and data.

    // modifiers (5 members, skipped 9)
    //
    // In this section we again get most of the API from
    // sequence_container_interface.

    // emplace_back does not look very necessary -- just look at its trivial
    // implementation -- but we can't provide it from
    // sequence_container_interface, because it is an optional sequence
    // container interface.  We would not want emplace_front to suddenly
    // appear on our std::vector-like type, and there may be some other type
    // for which emplace_back is a bad idea.
    //
    // However, by providing emplace_back here, we signal to the
    // sequence_container_interface template that our container is
    // back-mutation-friendly, and this allows it to provide all the overloads
    // of push_back and pop_back.
    template<typename... Args>
    reference emplace_back(Args &&... args)
    {
        return *emplace(end(), std::forward<Args>(args)...);
    }
    template<typename... Args>
    iterator emplace(const_iterator pos, Args &&... args)
    {
        auto position = const_cast<T *>(pos);
        bool const insert_before_end = position < end();
        if (insert_before_end) {
            auto last = end();
            emplace_back(std::move(this->back()));
            std::move_backward(position, last - 1, last);
        }
        new (position) T(std::forward<Args>(args)...);
        if (!insert_before_end)
            ++size_;
        return position;
    }
    // Note: The iterator category here was upgraded to ForwardIterator
    // (instead of vector's InputIterator), to ensure linear time complexity.
    template<
        typename ForwardIterator,
        typename Enable = std::enable_if_t<std::is_convertible<
            typename std::iterator_traits<ForwardIterator>::iterator_category,
            std::forward_iterator_tag>::value>>
    iterator
    insert(const_iterator pos, ForwardIterator first, ForwardIterator last)
    {
        auto position = const_cast<T *>(pos);
        auto const insertions = std::distance(first, last);
        assert(this->size() + insertions < capacity());
        uninitialized_generate(end(), end() + insertions, [] { return T(); });
        std::move_backward(position, end(), end() + insertions);
        std::copy(first, last, position);
        size_ += insertions;
        return position;
    }
    iterator erase(const_iterator f, const_iterator l)
    {
        auto first = const_cast<T *>(f);
        auto last = const_cast<T *>(l);
        auto end_ = this->end();
        auto it = std::move(last, end_, first);
        for (; it != end_; ++it) {
            it->~T();
        }
        size_ -= last - first;
        return first;
    }
    void swap(static_vector & other)
    {
        size_type short_size, long_size;
        std::tie(short_size, long_size) =
            std::minmax(this->size(), other.size());
        for (auto i = size_type(0); i < short_size; ++i) {
            using std::swap;
            swap((*this)[i], other[i]);
        }

        static_vector * longer = this;
        static_vector * shorter = this;
        if (this->size() < other.size())
            longer = &other;
        else
            shorter = &other;

        for (auto it = longer->begin() + short_size, last = longer->end();
             it != last;
             ++it) {
            shorter->emplace_back(std::move(*it));
        }

        longer->resize(short_size);
        shorter->size_ = long_size;
    }

    // Since we're getting so many overloads from
    // sequence_container_interface, and since many of those overloads are
    // implemented in terms of a user-defined function of the same name, we
    // need to add quite a few using declarations here.
    using base_type = sequence_container_interface<
        static_vector<T, N>,
        boost::stl_interfaces::element_layout::contiguous>;
    using base_type::begin;
    using base_type::end;
    using base_type::insert;
    using base_type::erase;

    // comparisons (skipped 6)

private:
    template<typename F>
    static void uninitialized_generate(iterator f, iterator l, F func)
    {
        for (; f != l; ++f) {
            new (static_cast<void *>(std::addressof(*f))) T(func());
        }
    }
    template<typename F>
    void resize_impl(size_type sz, F func) noexcept
    {
        assert(sz < capacity());
        if (sz < this->size())
            erase(begin() + sz, end());
        if (this->size() < sz)
            uninitialized_generate(end(), begin() + sz, func);
        size_ = sz;
    }

    alignas(T) unsigned char buf_[N * sizeof(T)];
    size_type size_;
};

That's quite a bit of code. However, by using sequence_container_interface, we were able to write only 22 functions, and let sequence_container_interface provide the other 39. 9 of the 22 function that we did have to write were constructors and special member functions, and those always have to be written in the derived class; sequence_container_interface never could have helped with those.

[Note] Note

sequence_container_interface does not support all the sets of container requirements in the standard. In particular, it does not support the allocator-aware requirements, and it does not support the associative or unordered associative container requirements.


PrevUpHomeNext