stl_interfaces/doc/tutorial.qbk

[/
 / 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)
 /]

[section Tutorial: `iterator_interface`]

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

[heading The `iterator_interface` Template]

Though a given iterator may have a large number of operations associated with
it, there are only a few basis operations that the iterator needs to define;
the full set of operations it supports can be defined in terms of that much
smaller basis.

It is possible to define any iterator `Iter` in terms of a subset of
user-defined operations.  By deriving `Iter` from _iter_iface_ using _CRTP_,
we can generate the full set of operations.  Here is the declaration of
_iter_iface_:

    template<
        typename Derived,
        typename IteratorConcept,
        typename ValueType,
        typename Reference = ValueType &,
        typename Pointer = ValueType *,
        typename DifferenceType = std::ptrdiff_t>
    struct iterator_interface;

Let's break that down.

`Derived` is the type that you're deriving _iter_iface_ from.

`IteratorConcept` defines the iterator category/concept.  This must be one of
the C++ standard iterator tag types, like `std::forward_iterator_tag`.  In
C++20 and later, `std::contiguous_iterator_tag` is a valid tag to use.

`ValueType` is used to define the iterator's `value_type` typedef.  Likewise,
`Reference` and `Pointer` are used to define the iterator's `reference` and
`pointer` typedefs, respectively.

[tip `Reference` does not need to be a reference type, and `Pointer` does not
need to be a pointer type.  This fact is very useful when making proxy
iterators. ]

`DifferenceType` is used to define the iterator's `difference_type`.  Don't be
a weirdo; just leave this as the default type, `std::ptrdiff_t`.

[heading Proxy Iterators]

Sometimes you need to create an iterator `I` such that `I::reference_type` is
not a (possibly `const`) reference to `I::value_type`.  For instance, let's
say you want to make a zip-iterator that produces pairs of values from two
separate underlying sequences.  For sequences `A` and `B`, with respective
`value_type`s `T` and `U`, one possible `reference_type` for a zip iterator
would be `std::pair<T &, U &>` (this is distinct from a reference to a pair,
such as `std::pair<T, U> &`).  Each such pair would contain a reference to one
element from `A` and a reference to the corresponding element from `B`.

As another example, if you wanted an iterator `I` that represents the infinite
sequence 0, 1, 2, ..., you'd be unable to form a reference to most or all of
those values; you'd instead produce a temporary for each value as it is
needed.  This implies that `I::value_type` does not involve references at all;
it may instead by `int` or `double`.

When defining a proxy iterator, you can use a template alias that provides
reasonable defaults for _iter_iface_'s parameters:

    template<
        typename Derived,
        typename IteratorConcept,
        typename ValueType,
        typename Reference = ValueType,
        typename DifferenceType = std::ptrdiff_t>
    using proxy_iterator_interface = iterator_interface<
        Derived,
        IteratorConcept,
        ValueType,
        Reference,
        proxy_arrow_result<Reference>,
        DifferenceType>;

[note As shown above, _proxy_iter_iface_ uses a template called
`proxy_arrow_result` as its pointer-type.  This template makes a copy of
whatever value is obtained by `operator*`, and then returns a pointer to the
copy in its `operator->`.  You may want to use something else if this is a
performance concern. ]


[heading User-Defined Iterator Operations]

Now, let's get back to the user-defined basis operations.

In the table below, `Iter` is a user-defined type derived from _iter_iface_;
`i` and `i2` are objects of type `Iter`; `reference` is the type passed as the
`Reference` template parameter to _iter_iface_; `pointer` is the type passed
as the `Pointer` template parameter to _iter_iface_; and `n` is a value of
type `difference_type`.

[table User-Defined Operations
    [[Expression]   [Return Type]   [Semantics]   [Assertion/note/pre-/post-condition]]
    [
        [ `*i` ]
        [ Convertible to `reference`. ]
        [ Dereferences `i` and returns the result. ]
        [ ['Expects:] i is dereferenceable. ]
    ]
    [
        [ `i == i2` ]
        [ Contextually convertible to `bool`. ]
        [ Returns true if and only if `i` and `i2` refer to the same value. ]
        [ ['Expects:] `(i, i2)` is in the domain of `==`. ]
    ]
    [
        [ `i2 - i` ]
        [ Convertible to `difference_type`. ]
        [ Returns `n`. ]
        [ ['Expects:] there exists a value `n` of type `difference_type` such that `i + n == i2`.
        `i2 == i + (i2 - i)`. ]
    ]
    [
        [ `++i` ]
        [ `Iter &` ]
        [ Increments `i`. ]
        [ ]
    ]
    [
        [ `--i` ]
        [ `Iter &` ]
        [ Decrements `i`. ]
        [ ]
    ]
    [
        [ `i += n` ]
        [ `Iter &` ]
        [
``difference_type m = n;
if (m >= 0)
  while (m--) ++i;
else
  while (m++) --i;`` ]
        [ ]
    ]
]

[tip The table above leaves a lot of implementation freedom.  In
`operator+=()`, you could take `n` as a value or as a reference; `operator-()`
can return a `difference_type` or just something convertible to one; etc.  In
particular, your operations can be `constexpr` or `noexcept` as you see fit.]

Not all the iterator concepts require all the operations above.  Here are the
operations used with each iterator concept:

[table Operations Required for Each Concept
    [[Concept]   [Operations]]
    [
        [ `input_iterator` ]
        [ ``*i
i == i2
++i`` ]
    ]
    [
        [ `output_iterator` ]
        [ ``*i
++i`` ]
    ]
    [
        [ `forward_iterator` ]
        [ ``*i
i == i2
++i`` ]
    ]
    [
        [ `bidirectional_iterator` ]
        [ ``*i
i == i2
++i
--i`` ]
    ]
    [
        [ `random_access_iterator`/`continguous_iterator` ]
        [ ``*i
i - i2
i += n`` ]
    ]
]

[note For `random_access_iterator`s, the operation `i - i2` is used to provide
all the relational operators, including `operator==()` and `operator!=()`.  If
you are defining an iterator over a discontiguous sequence
(e.g. `std::deque`), this implementation of `operator==()` may not be optimal.
In this case, provide your own `operator==()`.  `operator!=()` will be
provided if `operator==` is available. ]

[heading An Important Note About `operator++()` and `operator--()`]

There's a wrinkle in this way of doing things.  When you define `operator++()`
in your iterator type `Derived`, _iter_iface_ defines post-increment,
`operator++(int)`.  But since `Derived` has an `operator++` and so does its
base class _iter_iface_, the one in `Derived` *hides* the one in _iter_iface_.

So, you need to add a using declaration that makes the `operator++` from the
base class visible in the derived class.  For instance, in the `node_iterator`
example there are these lines:

[node_iterator_using_declaration]

[important All of the above applies to `operator--`.  So, for bidirectional
iterators, you need to add a line like `using base_type::operator--;` as
well. ]

[note These using declarations are not necessary for a random access iterator,
because `Derived` does not have an `operator++()` in that case. ]

[heading Putting it All Together]

Ok, let's actually define a simple iterator.  Let's say you need to interact
with some legacy code that has a hand-written linked list:

[node_defn]

We can't change this code to use `std::list`, but it would be nice to be able
to reuse all of the standard algorithms with this type.  Defining an iterator
will get us there.

[node_iterator_class_head]

We are deriving `node_iterator` from _iter_iface_, and because we're using
_CRTP_, we first have to pass `node_iterator` for the `Derived` template
parameter, so that _iter_iface_ knows what derived type to cast to in order to
get at the user-defined operations.  Then, we pass `std::forward_iterator_tag`
for `IteratorConcept`, since that's appropriate for a singly-linked list.
Finally, we pass `T` to let _iter_iface_ know what the `value_type` is for our
iterator.

We leave the rest of the template parameters at their defaults: `T &` for
`Reference`, `T *` for `Pointer`, and `std::ptrdiff_t` for `DifferenceType`.
This is what you will do for almost all iterators.  The most common exceptions
to this are usually some kind of proxy iterator.  Another exception is when
for better code generation you want to return builtin values instead of
references for constant iterators.  To see an example of the latter, see the
`repeated_chars_iterator` in the introduction; it's `Reference` template
parameter is `char` for this reason.

[node_iterator_ctors]

Next, we define two constructors: a default constructor, and one that takes a
`node` pointer.  A default constructor is required by the `forward_iterator`
concept, but _iter_iface_ cannot supply this, since constructors are not
visible in derived types without user intervention.

[important A default constructor is required for every iterator concept.]

[node_iterator_user_ops]

Next, we define the user-defined operations that _iter_iface_ requires to do
its work.  As you might expect, the three required operations are very
straightforward.

[note Here, I implement `operator==()` as a hidden friend function.  it would
have worked just as well if I had instead implemented it as a member function,
like this:

``constexpr bool operator==(node_iterator rhs) const noexcept
{
    return it_ == rhs.it_;
}``

Either of these forms works, since _iter_iface_ is concept-based _emdash_ the
appropriate expressions need to be well-formed for the _iter_iface_ tempalte
to do its work. ]

Finally, we need a using declaration to make
`iterator_interface::operator++(int)` visible:

[node_iterator_using_declaration]

Here's how we might use the forward iterator we just defined:

[node_iterator_usage]

[heading What About Adapting an Existing Iterator?]

So glad you asked.  If you want to make something like a filtering iterator,
or say a UTF-8 to UTF-32 transcoding iterator, you are starting with an
existing iterator and adapting it.  There's a way to avoid having to write all
of the user-defined basis functions, as long as there's a base iterator that
already has the right operations with the right semantics.

For example, consider an iterator that contains a pointer to an array of
`int`, and predicate of type `Pred`.  It filters out integers that do not meet
the predicate.  Since we are using an existing iterator (the pointer to
`int`), we already have all the operations we need for a bidirectional
iterator (and more), except that `operator++` on an `int *` does not skip over
elements as we'd like.  Here's the code:

[filtered_int_iterator_defn]

So, all we had to do was let _iter_iface_ know that there was an underlying
iterator it could use _emdash_ by implementing `base_reference()` _emdash_ and
the operations that we did not define got defined for us by _iter_iface_.

Here is the iterator in action:

[filtered_int_iterator_usage]

[heading Checking Your Work]

_IFaces_ is able to check that some of the code that you write is compatible
with the concept for the iterator you're writing.  It cannot check everything.
For instance, _IFaces_ does not know if your derived type includes a default
constructor, which is required by all the iterators.  In particular,
_iter_iface_ cannot `static_assert` on the wellformedness of `Derived()`,
since `Derived` is an incomplete type within the body of _iter_iface_
_emdash_ _iter_iface_ is the base class for `Derived`, not the other way
round.

Since you can easily `static_assert` that a type models a given concept, a
good practice is to put such a `static_assert` after you define your iterator
type.

For instance, after `node_iterator` you'll find this code:

[node_iterator_concept_check]

Consider this good code hygiene.  Without this simple check, you'll probably
eventually find yourself looking at an error message with a very long template
instantiation stack.

There's also a macro that can help you check that `std::iterator_traits` is
well-formed and provides the correct types.  See _traits_m_.

[endsect]

[section Tutorial: `view_interface`]

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

[heading The `view_interface` Template]

C++20 contains a _CRTP_ template, `std::ranges::view_interface`, which takes a
range or view, and adds all the operations that view types have, using only
the range's/view's `begin()` and `end()`.  This is a C++14-compatible version
of that template.

As with _iter_iface_, _view_iface_ makes it possible to write very few
operations _emdash_ only `begin()` and `end()` are actually used by
_view_iface_ _emdash_ and get all the other operations that go with view
types.  The operations added depend on what kinds of iterator and/or sentinel
types your derived view type defines.

Here is the declaration of _view_iface_:

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

_view_iface_ only requires 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.

[note Proxy iterators are inherently discontiguous.]

In this example, we're implementing something very similar to
`std::ranges::drop_while_view`.  First, we need helper view types `subrange`
and `all_view`, and a function that takes a range and returns a view of the
entire range, `all()`:

[all_view]

Note that `subrange` is derived from _view_iface_, so it will have all the
view-like operations that are appropriate to its `Iterator` and `Sentinel`
types.

With the helpers available, we can define `drop_while_view`:

[drop_while_view_template]

Now, let's look at code using these types, including operations defined by
_view_iface_ that we did not have to write:

[drop_while_view_usage]

If you want more details on _view_iface_, you can find it wherever you usually
find reference documentation on the standard library.  We won't cover it here
for that reason.  See [@http://eel.is/c++draft/view.interface [view.interface]
on eel.is] or [@https://cppreference.com] for details.

[endsect]

[section Tutorial: `sequence_container_interface`]

[note All the member functions provided by _cont_iface_ are in your
container's base class _emdash_ _cont_iface_ _emdash_ 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 _cont_iface_-provided
member function, feel free to replace it.]

[heading 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.
_cont_iface_ 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_iface_, _cont_iface_ 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.

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

* Container requirements `[tab:container.req]`
* Reversible container requirements `[tab:container.rev.req]`
* Optional container operations `[tab:container.opt]`
* Allocator-aware container requirements `[tab:container.alloc.req]`
* Sequence container requirements `[tab:container.seq.req]`
* Optional sequence container operations `[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 _cont_iface_, except the allocator-aware container requirements.
The container and sequence container requirements are required for any
sequence container.  _cont_iface_ 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 _IFaces_ use the 2017 version of the
C++ Standard.  See your favorite online resource for the contents of these
tables.  Many people like [@http://eel.is/c++draft eel.is], which is really
easy to navigate.]

Note that _cont_iface_ 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 _emdash_ it's just that
_cont_iface_ does not.

[heading How `sequence_container_interface` Works]

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

Below, there are tables that show what user-defined types and operations are
required for _cont_iface_ 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 _cont_iface_ 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 _cont_iface_ in terms of the
user-defined operations, will be provided.  For example, the `std::array`-like
container described above would have `front()` _emdash_ which comes from the
optional sequence container requirements _emdash_ 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.

[heading The `sequence_container_interface` Tables]

After each requirements table, there's a table indicating how _cont_iface_
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 _cont_iface_ 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 &&`.

[heading Container]

All containers must meet the requirements of this table:

[table 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 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 _emdash_ and that certainly will not break _cont_iface_. ]

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

[table User-Defined Operations to sequence_container_interface Operations
    [[User-Defined]   [_cont_iface_-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 _cont_iface_-provided ones are `const`.  _cont_iface_ 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 _cont_iface_, any user-defined replacement will be used to provide `a != b`. ]
    ]
    [
        [ `a.swap(b)` ]
        [ `swap(a, b)` ]
        [ ]
    ]
]

[heading Reversible Container]

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

[table 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, _cont_iface_ will provide the
rest of the reversible container requirements, using this mapping:

[table User-Defined Operations to sequence_container_interface Operations
    [[User-Defined]   [_cont_iface_-Provided]   [Note]]
    [
        [ ``a.begin()
a.end()`` ]
        [ ``a.rbegin()
a.rend()
a.crbegin()
a.crend()`` ]
        [ The user-defined `begin()` and `end()` are non-`const`, and _cont_iface_ provides both `const` and non-`const` overloads of `rbegin()` and `rend()`.  _cont_iface_ can only provide these operations if `X::iterator` and `X::const_iterator` are bidirectional iterators. ]
    ]
]

[heading 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.

_cont_iface_ will provide the optional container requirements using this
mapping:

[table User-Defined Operations to sequence_container_interface Operations
    [[User-Defined]   [_cont_iface_-Provided]   [Note]]
    [
        [ `a < b` ]
        [ ``a <= b
a > b
a >= b`` ]
        [ Though `a < b` is provided by _cont_iface_, any user-defined replacement will be used to provide the other operations listed here. ]
    ]
]

[heading Sequence Container]

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

[table 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 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, _cont_iface_ will provide the
rest of the sequence container requirements, using this mapping:

[table User-Defined Operations to sequence_container_interface Operations
    [[User-Defined]   [_cont_iface_-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 _cont_iface_ to provide these operations. ]
    ]
]

[heading 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 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, _cont_iface_ will provide the
rest of the optional sequence container requirements, using this mapping:

[table User-Defined Operations to sequence_container_interface Operations
    [[User-Defined]   [_cont_iface_-Provided]   [Note]]
    [
        [ `a.begin()` ]
        [ ``a.front()
a[n]
a.at(n)
`` ]
        [ These operations are provided in `const` and non-`const` overloads.  _cont_iface_ 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.  _cont_iface_ 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 _cont_iface_ 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 _cont_iface_ to provide this operation. ]
    ]
]

[note `emplace_front()` and `emplace_back()` are not needed for some of the
_cont_iface_-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. ]

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

* If an exception is thrown by an `insert()` or `emplace()` call while
  inserting a single element, that function has no effect.
* No `erase()` function throws an exception.
* No copy constructor or assignment operator of a returned iterator throws an
  exception.
* The iterator returned from `a.emplace(p, args)` points to the new element
  constructed from `args` into `a`.
* The iterator returned from `a.insert(p, i, j)` points to the copy of the
  first element inserted into `a`, or `p` if `i == j`.
* The iterator returned by `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.

[heading Example: `static_vector`]

Let's look at an example.  _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 _cont_iface_, 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.

[static_vector_defn]

That's quite a bit of code.  However, by using _cont_iface_, we were able to
write only 22 functions, and let _cont_iface_ 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;
_cont_iface_ never could have helped with those.

[note _cont_iface_ 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.]

[endsect]

[section Tutorial: `reverse_iterator`]

There is a `std::reverse_iterator` template that has been around since C++98.
In C++20 it is compatible with proxy iterators, and is `constexpr`- and
`noexcept`-friendly.  If you are using C++20 or later, just use
`std::reverse_iterator`.  For code built against earlier versions of C++, you
can use _rev_iter_.

There's nothing much to document about it; it works just like
`std::reverse_iterator`.

[endsect]