...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Note | |
---|---|
All the member functions provided by |
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.
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):
[tab:container.req]
[tab:container.rev.req]
[tab:container.opt]
[tab:container.alloc.req]
[tab:container.seq.req]
[tab:container.seq.opt]
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.
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.
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 &&
.
All containers must meet the requirements of this table:
Table 37.3. User-Defined Types and Operations for Containers
Expression |
Return Type |
Semantics |
Assertion/note/pre-/post-condition |
---|---|---|---|
|
|
Compile time only. |
|
|
|
Compile time only. |
|
|
|
Compile time only. |
|
|
An iterator whose |
Must meet the forward iterator requirements, and must be convertible
to |
|
|
A constant iterator whose |
Must meet the forward iterator requirements. Compile time only. |
|
|
A signed integer type. |
Identical to the diference type of |
|
|
An unsigned integer type. |
Compile time only. |
|
|
Ensures: |
||
X u(a); X u = a;
|
Ensures: |
||
X u(rv); X u = rv;
|
Ensures: |
||
|
|
All existing elements of |
Ensures: |
|
Destroys every element of |
||
|
|
This is the non- |
|
|
|
This is the non- |
|
|
Convertible to |
Exchanges the contents of |
|
|
|
Ensures: |
|
|
|
|
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 |
If you provide the types and operations above, sequence_container_interface
will provide the rest of the container requirements, using this mapping:
Table 37.4. User-Defined Operations to sequence_container_interface Operations
User-Defined |
|
Note |
---|---|---|
a.begin() a.end()
|
a.empty() a.size() a.begin() a.end() a.cbegin() a.cend()
|
The user-defined |
|
|
Though |
|
|
Containers that are reverse-iterable must meet the requirements of this table (in addition to the container requirements):
Table 37.5. User-Defined Types and Operations for Reversible Containers
Expression |
Return Type |
Semantics |
Assertion/note/pre-/post-condition |
---|---|---|---|
|
|
Compile time only. |
|
|
|
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 37.6. User-Defined Operations to sequence_container_interface Operations
User-Defined |
|
Note |
---|---|---|
a.begin() a.end()
|
a.rbegin() a.rend() a.crbegin() a.crend()
|
The user-defined |
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 37.7. User-Defined Operations to sequence_container_interface Operations
User-Defined |
|
Note |
---|---|---|
|
a <= b a > b a >= b
|
Though |
Sequence containers meet the requirements of this table (in addition to the container requirements):
Table 37.8. User-Defined Types and Operations for Sequence Containers
Expression |
Return Type |
Semantics |
Assertion/note/pre-/post-condition |
---|---|---|---|
|
Constructs a sequence of |
Ensures: |
|
|
Constructs a sequence equal to |
Ensures: |
|
|
|
||
|
|
Inserts an object of type T constructed with |
|
|
|
Inserts copies of the elements in |
|
|
|
Erases the elements in the range |
Important | |
---|---|
In the notes for |
If you provide the types and operations above, sequence_container_interface
will provide the rest of the sequence container requirements, using this mapping:
Table 37.9. User-Defined Operations to sequence_container_interface Operations
User-Defined |
|
Note |
---|---|---|
|
|
|
|
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)
|
|
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 37.10. User-Defined Types and Operations for Sequence Containers
Expression |
Return Type |
Semantics |
Assertion/note/pre-/post-condition |
---|---|---|---|
|
|
Prepends an object of type |
|
|
|
Appends an object of type |
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 37.11. User-Defined Operations to sequence_container_interface Operations
User-Defined |
|
Note |
---|---|---|
|
a.front() a[n] a.at(n)
|
These operations are provided in |
|
|
|
|
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 | |
---|---|
|
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:
insert()
or emplace()
call while inserting a single element,
that function has no effect.
erase()
function throws an exception.
a.emplace(p,
args)
points to the new element constructed from args
into a
.
a.insert(p,
i,
j)
points to the copy of the first element inserted into a
,
or p
if i
== j
.
a.erase(q1,
q2)
points to the element pointed to by q2
prior to any elements being erased. If no such element exists, a.end()
is returned.
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 | |
---|---|
|