Boost C++ Libraries

	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
	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:

X u(a);
X u = a;

X u(rv);
X u = rv;

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:

a.begin()
a.end()

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

Reversible Container

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

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

a.begin()
a.end()

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

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:

a <= b
a > b
a >= b

Sequence Container

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

	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:

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

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

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)

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):

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

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

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

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

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

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

	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 and the destructor 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
	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.