[/ / 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` (this is distinct from a reference to a pair, such as `std::pair &`). 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, 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 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 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`; `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` ] [ ] [ Compile time only. ] ] [ [ `X​::​const_reverse_iterator` ] [ `boost::stl_interfaces::reverse_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)...` 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)...`. ] [ ] ] [ [ `a.emplace_back(args)` ] [ `X::reference` ] [ Appends an object of type `T` constructed with `std::forward(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]