[/
  Copyright 2016-2017 Joaquin M Lopez Munoz.
  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)
]

[def _AllocatorAwareContainer_ [@http://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer [* `AllocatorAwareContainer`]]]
[def _Callable_ [@http://en.cppreference.com/w/cpp/named_req/Callable [* `Callable`]]]
[def _Container_ [@http://en.cppreference.com/w/cpp/named_req/Container [* `Container`]]]
[def _CopyAssignable_ [@http://en.cppreference.com/w/cpp/named_req/CopyAssignable [* `CopyAssignable`]]]
[def _CopyInsertable_ [@http://en.cppreference.com/w/cpp/named_req/CopyInsertable [* `CopyInsertable`]]]
[def _DefaultConstructible_ [@http://en.cppreference.com/w/cpp/named_req/DefaultConstructible [* `DefaultConstructible`]]]
[def _InputIterator_ [@http://en.cppreference.com/w/cpp/named_req/InputIterator [* `InputIterator`]]]
[def _INVOKE_ [@http://en.cppreference.com/w/cpp/utility/functional/invoke ['[* `INVOKE`]]]]
[def _MoveAssignable_ [@http://en.cppreference.com/w/cpp/named_req/MoveAssignable [* `MoveAssignable`]]]
[def _MoveInsertable_ [@http://en.cppreference.com/w/cpp/named_req/MoveInsertable [* `MoveInsertable`]]]

[section Reference]

[section Polymorphism models]

[def _polymorphism_model_ [link poly_collection.reference.polymorphism_models polymorphism model]]

The key aspect of dynamic polymorphism is the ability for a value of type `T`
to internally use another value of a possibily different type `U` for the
implementation of a given interface. Base/derived polymorphism is the classic
model of dynamic polymorphism in C++, but not the only possible one.

Formally, a /polymorphism model/ is defined by

* A family *Interface* of permissible interface types and, for each
`I` \u2208 *Interface*, the family *Implementation*(`I`) of types satisfying
`I`.
* For a given interface type `I`, an operation *subobject*(`x`) that maps each
value of an implementation type to its internally used value `y` of a possibly
different implementation type
[footnote This is a metalinguistic definition not directly expressible in C++.
There are equivalent formulations that can indeed be realized in C++, but
they add little to the comprehension of the concepts.].

Static polymorphism is the trivial case where *subobject*(`x`) = `x` for all
`x`. Base/derived polymorphism is characterized by:

* *Interface* = { `Base` : `std::is_polymorphic_v<Base>` }.
* *Implementation*(`Base`) = { `Derived` : `std::is_base_of_v<Base,Derived>` }.
* *subobject*(`x`) = `static_cast<Derived&>(x)` with `typeid(x)==typeid(Derived)`.

[endsect]

[section Polymorphic containers]

[def _PolymorphicContainer_ [link poly_collection.reference.polymorphic_containers [* `PolymorphicContainer`]]]

A /polymorphic container/ is an object that stores objects of some type `T`
implementing a given interface `I` under an implicitly associated polymorphism
model. Polymorphic containers satisfy the requirements for _Container_ and
_AllocatorAwareContainer_ with the following modifications:

* Where it occurs, replace the requirement that `T` be _CopyInsertable_,
_CopyAssignable_, _MoveInsertable_,  _MoveAssignable_ or
_EqualityComparable_,  with the following semantic clause: may throw if
some subobject in the container is not
_CopyConstructible_ (respectively, _CopyAssignable_, _MoveConstructible_, 
_MoveAssignable_, _EqualityComparable_).
* Replace [container.requirements.general]/3 with:
`allocator_type` must have the property that for any type `U`
implementing `I` and the associated type `A` =
`std::allocator_traits<allocator_type>::rebind_alloc<U>`, `U` is
_CopyInsertable_ (respectively _MoveInsertable_) with respect to `A` if and
only if `U` is  _CopyConstructible_ (respectively _MoveConstructible_);
all subobjects of type `U` stored in these containers shall be constructed
using the `std::allocator_traits<A>::construct` function and
destroyed using the `std::allocator_traits<A>::destroy` function;
these functions (or their equivalents for a rebound allocator) are called
only for the types of the stored subobjects, not for
any other type (internal or public) used by the container.

[section Polymorphic collections]

[def _PolymorphicCollection_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections [* `PolymorphicCollection`]]]

/Polymorphic collections/ store their objects of type `value_type` in
/segments/ dedicated to each of the types of the contained subojects.
Only objects whose subobjects are of an /acceptable/ type are allowed,
where a type `U` is said to be acceptable if

* it implements the interface associated to the container,
* it is _MoveConstructible_,
* it is _MoveAssignable_ or
[@http://en.cppreference.com/w/cpp/types/is_move_constructible
`std::is_nothrow_move_constructible<U>::value`] is `true`.

Polymorphic collections conform
to the requirements of _PolymorphicContainer_ with the following
modfications and extra guarantees:

* The complexity of `empty()` and `size()` is linear on the number of
segments of the collection.
* `max_size()` is not provided.
* `a==b` evaluates to `true` iff for each non-empty segment of subojects
of type `U` in `a` there is a segment of `U` in `b` with the same size
and equal elements in the same order, and vice versa.
* No exceptions are thrown associated to some subobject type not being
_CopyAssignable_, _MoveConstructible_ or _MoveAssignable_.

A type `U` is said to be /registered/ into the collection if a
(possibly empty) segment for `U` has been created. Registered types
continue to stay so for the duration of the container except if it is
moved from, assigned to, or swapped.

Each segment has an associated capacity indicating the maximum size
that it can attain without reallocation. When the limit
is exceeded (or explicitly through `reserve`) new storage space is
allocated with greater capacity and elements are moved.

Collection traversal goes through the elements of the first segment,
then the second, etc. The order in which segments are visited is
unspecified but remains stable until a new segment is created.

Besides `iterator` and `const_iterator`, there are iterator types
`local_base_iterator` and `local_iterator<U>` (and their `const_`
counterparts) whose objects can be used to iterate over the segment
for `U` (in the same order followed by global traversal).
Local base iterators refer to `value_type`, whereas
(`const_`)`local_iterator<U>` refers to `U`. All local iterators model
_RandomAccessIterator_. Local base iterators may not be used
to iterate across segments, and comparing local base iterators
associated to different segments is undefined behavior. A (const)
local base iterator to a segment for `U` can be explicitly converted
to (`const_`)`local_iterator<U>` pointing to the same position,
and vice versa.

Insertion and erasure do not invalidate iterators (global or local)
except those from the insertion/erasure point to the end of the
affected segment, if its capacity is not exceeded, or all
iterators/references to the segment otherwise
[footnote The global `end()` iterator lies outside any segment, hence
it always remain valid.].

For the description of the remaining requirements of polymorphic collections,
we use the following notation:

* `C` is a polymorphic collection type,
* `c` is an object of type `C`, `cc` is a possibly `const` object of type `C`,
* `al` is a value of type `C::allocator_type`,
* `info` is a `const std::type_info&`,
* `U` is an acceptable type, `Us...` is a template parameter pack of
acceptable types, 
* `n` is a value of `size_type`,
* `x` is a value of a type `T` implementing the interface associated to the
collection,
* `args...` is a function parameter pack of types `Args&&...`,
* `it` is a possibly const global iterator of `c`,
* `it1` and `it2` are (same-typed) possibly const global iterators of a `C`
collection other than `c` such that \[`it1`, `it2`) is a valid range.
* `lbit` is a possibly const local base iterator of `c`,
* `lbit1` and `lbit2` are (same-typed) possibly const local base iterators of
a `C` collection other than `c` such that \[`lbit1`, `lbit2`) is a valid range.
* `lit` is a (`const_`)`local_iterator<U>` of `c`,
* `lit1` and `lit2` are (same-typed) (`const_`)`local_iterator<U>`s of
a `C` collection other than `c` such that \[`lit1`, `lit2`) is a valid range,
* `i1` and `i2` are iterators external to `c` referring to `T` such that
\[`i1`, `i2`) is a valid range,
* `j1` and `j2` are iterators external to `c` such that
\[`j1`, `j2`) is a valid range,
* `xit1` and `xit2` are (same-typed) possibly const iterators (global or
local) of `c` such that \[`xit1`, `xit2`) is a valid range.

[section Types]

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_base_iterator]
[def _local_base_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_base_iterator `local_base_iterator`]]

`C::local_base_iterator`

_RandomAccessIterator_ with same value type, difference type and pointer and
reference types as `C::iterator`, valid for accessing elements of a given
segment. Implicily convertible to `C::const_local_base_iterator`, explicitly
convertible to `C::local_iterator<U>` if the segment it points to is actually
that for `U`.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_base_iterator]
[def _const_local_base_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_base_iterator `const_local_base_iterator`]]

`C::const_local_base_iterator`

_RandomAccessIterator_ with same value type, difference type and pointer and
reference types as `C::const_iterator`, valid for accessing elements of a given
segment. Explicitly convertible to `C::const_local_iterator<U>` if the segment
it points to is actually that for `U`.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_iterator]
[def _local_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_iterator `local_iterator`]]

`C::local_iterator<U>`

_RandomAccessIterator_ with value type `U`, reference type `U&`, pointer type
`U*` and the same difference type as `C::iterator`, valid for accessing elements
of the segment for `U`. Implicily convertible to `C::const_local_iterator<U>`,
explicitly convertible to `C::local_base_iterator`.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_iterator]
[def _const_local_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_iterator `const_local_iterator`]]

`C::const_local_iterator<U>`

_RandomAccessIterator_ with value type `U`, reference type `const U&`, pointer
type `const U*` and the same difference type as `C::iterator`, valid for
accessing elements of the segment for `U`. Explicitly convertible to
`C::const_local_base_iterator`.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info]
[def _const_base_segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info `const_base_segment_info`]]

`C::const_base_segment_info`

_CopyConstructible_ and _CopyAssignable_ type with information about a given
segment of a collection. If `ci` is a possibly `const` object of type
`C::const_base_segment_info` associated to the segment of `c` for `U`, then

* `ci.begin()==c.cbegin(typeid(U))`
* `ci.cbegin()==c.cbegin(typeid(U))`
* `ci.begin<U>()==c.cbegin<U>()`
* `ci.cbegin<U>()==c.cbegin<U>()`
* `ci.end()==c.cend(typeid(U))`
* `ci.cend()==c.cend(typeid(U))`
* `ci.end<U>()==c.cend<U>()`
* `ci.cend<U>()==c.cend<U>()`
* `ci.type_info()==typeid(U)`

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info]
[def _base_segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info `base_segment_info`]]

`C::base_segment_info`

_CopyConstructible_ and _CopyAssignable_ type publicly derived from 
`C::const_base_segment_info` and exposing its public interface. Additionally,
if `i` is an object of type `C::base_segment_info` associated to the
segment of `c` for `U`, then

* `i.begin()==c.begin(typeid(U))`
* `i.begin<U>()==c.begin<U>()`
* `i.end()==c.end(typeid(U))`
* `i.end<U>()==c.end<U>()`

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_info]
[def _const_segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_info `const_segment_info`]]

`C::const_segment_info<U>`

_CopyConstructible_ and _CopyAssignable_ type with information about the segment
for `U`. If `ci` is a possibly `const` object of type `C::const_segment_info<U>`
associated to the collection `c`, then

* `ci.begin()==c.cbegin<U>()`
* `ci.cbegin()==c.cbegin<U>()`
* `ci.end()==c.cend<U>()`
* `ci.cend()==c.cend<U>()`

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_info]
[def _segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_info `segment_info`]]

`C::segment_info<U>`

_CopyConstructible_ and _CopyAssignable_ type publicly derived from 
`C::const_segment_info<U>` and exposing its public interface. Additionally,
if `i` is an object of type `C::segment_info<U>` associated to the collection
`c`, then

* `i.begin()==c.begin<U>()`
* `i.end()==c.end<U>()`

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info_iterator]
[def _base_segment_info_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info_iterator `base_segment_info_iterator`]]

`C::base_segment_info_iterator`

_InputIterator_ with value type and reference type `C::base_segment_info`.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info_iterator]
[def _const_base_segment_info_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info_iterator `const_base_segment_info_iterator`]]

`C::const_base_segment_info_iterator`

_InputIterator_ with value type and reference type `C::const_base_segment_info`.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_traversal_info]
[def _const_segment_traversal_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_traversal_info `const_segment_traversal_info`]]

`C::const_segment_traversal_info`

_CopyConstructible_ and _CopyAssignable_ type with `const` member
functions `begin`/`cbegin` and `end`/`cend` returning
`C::const_base_segment_info_iterator` objects that span over a range
of `C::const_base_segment_info` objects.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_traversal_info]
[def _segment_traversal_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_traversal_info `segment_traversal_info`]]

`C::segment_traversal_info`

_CopyConstructible_ and _CopyAssignable_ type publicly derived
from with `C::const_segment_traversal_info` and exposing its
public interface. Additionally, provides non-const member
functions `begin` and `end` returning
`C::base_segment_info_iterator` objects that span over an equivalent range
of `C::base_segment_info` objects.

[endsect]

[section Construct/copy/destroy]

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.construct_copy_destroy.range_construction]

`C(j1,j2)`[br]
`C d(j1,j2)`

[*Requires:] `C::allocator_type` is _DefaultConstructible_. \[`j1`, `j2`) can be
inserted into `C`.[br]
[*Effects:] Copy constructs the internal allocator from `C::allocator_type()`.
Internally calls `this->insert(j1,j2)` on construction.

`C(j1,j2,al)`[br]
`C d(j1,j2,al)`

[*Requires:] \[`j1`, `j2`) can be inserted into `C`.[br]
[*Effects:] Copy constructs the internal allocator from `al`.
Internally calls `this->insert(j1,j2)` on construction.

[endsect]

[section Type registration]

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.register_types]
[def _register_types_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.register_types `register_types`]]

`c.register_types<Us...>()`

[*Effects:] Registers (if needed) each of the indicated types in the
collection.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.is_registered]
[def _is_registered_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.is_registered `is_registered`]]

`cc.is_registered(info)`[br]
`cc.is_registered<U>()`

[*Returns:] `true` iff the indicated type is registered in the collection.

[endsect]

[section Iterators]

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.begin]
[def _begin_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.begin `begin`]]
[def _cbegin_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.begin `cbegin`]]

(1) `c.begin(info)`[br]
(2) `c.begin<U>()`[br]
(3) `const_cast<const C&>(c).begin(info)`[br]
(4) `cc.cbegin(info)`[br]
(5) `const_cast<const C&>(c).begin<U>()`[br]
(6) `cc.cbegin<U>()`

[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) or
`const_local_base_iterator` (3,4) or `const_local_iterator<U>` (5,6) to the
beginning of the segment for the indicated type.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.end]
[def _end_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.end `end`]]
[def _cend_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.end `cend`]]

(1) `c.end(info)`[br]
(2) `c.end<U>()`[br]
(3) `const_cast<const C&>(c).end(info)`[br]
(4) `cc.cend(info)`[br]
(5) `const_cast<const C&>(c).end<U>()`[br]
(6) `cc.cend<U>()`

[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) or
`const_local_base_iterator` (3,4) or `const_local_iterator<U>` (5,6) to the
end of the segment for the indicated type.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment]
[def _segment_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment `segment`]]

(1) `c.segment(info)`[br]
(2) `c.segment<U>()`[br]
(3) `const_cast<const C&>(c).segment(info)`[br]
(4) `const_cast<const C&>(c).segment<U>()`[br]

[*Returns:] A `base_segment_info` (1) or `segment_info<U>` (2) or
`const_base_segment_info` (3) or `const_segment_info<U>` (4) object
referring to the segment for the indicated type.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment_traversal]
[def _segment_traversal_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment_traversal `segment_traversal`]]

(1) `c.segment_traversal()`[br]
(2) `const_cast<const C&>(c).segment_traversal()`

[*Returns:] A `segment_traversal_info` (1) or `const_segment_traversal_info`
(2) object spanning over a range of segment descriptors for the collection.
The order in which segments are visited matches that of
\[`c.begin()`, `c.end()`).

[endsect]

[section Capacity]

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.empty]
[def _empty_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.empty `empty`]]

`cc.empty(info)`[br]
`cc.empty<U>()`

[*Returns:] `true` iff the segment for the indicated type exists and
is empty.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.size]
[def _size_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.size `size`]]

`cc.size(info)`[br]
`cc.size<U>()`

[*Returns:] The size of the segment for the indicated type.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.max_size]
[def _max_size_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.max_size `max_size`]]

`cc.max_size(info)`[br]
`cc.max_size<U>()`

[*Returns:] The maximum size attainable by the segment for
the indicated type.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.capacity]
[def _capacity_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.capacity `capacity`]]

`cc.capacity(info)`[br]
`cc.capacity<U>()`[br]

[*Returns:] The maximum size that the segment for the indicated type can
attain without requiring reallocation.[br]
[*Throws:] If the indicated type is not registered.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.reserve]
[def _reserve_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.reserve `reserve`]]

`c.reserve(n)`

[*Effects:] Calls `reserve` with `n` for each of the segments of the
collection.

(1) `c.reserve(info,n)`[br]
(2) `c.reserve<U>(n)`

[*Effects:] Throws if the type indicated by `info` is not registered (1)
or registers `U` if needed (2). If `n` is greater than the current
capacity of the segment for the indicated type, new storage space is allocated
with a capacity of at least `n` and elements are moved there.[br]
[*Complexity:] Linear in the size of the segment if reallocation happens,
constant otherwise.[br]
[*Throws:] `std::length_error` if `n` is greater than the return value of
`max_size` for the segment.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.shrink_to_fit]
[def _shrink_to_fit_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.shrink_to_fit `shrink_to_fit`]]

`c.shrink_to_fit()`

[*Effects:] Calls `shrink_to_fit` for each of the segments of the
collection.

`c.shrink_to_fit(info)`[br]
`c.shrink_to_fit<U>()`

[*Effects:] Non-binding request to reduce memory usage while preserving the
sequence of elements of the segment for the indicated type. May invalidate
all iterators and references to the segment.[br]
[*Throws:] If the indicated type is not registered.

[endsect]

[section Modifiers]

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace]
[def _emplace_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace `emplace`]]
[def _emplace_hint_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace `emplace_hint`]]

(1) `c.emplace<U>(args...)`[br]
(2) `c.emplace_hint<U>(it,args...)`

[*Requires:] `U` is constructible from `std::forward<Args>(args)...`.[br]
[*Effects:] Registers `U` (if needed) and inserts a new element with
a subobject constructed from `std::forward<Args>(args)...`: (1) at the end of
the segment for `U`; (2) just before the
position indicated by `it`, if it points to the segment for `U`, or at the
end of the segment for `U` otherwise.[br]
[*Returns:] An `iterator` to the newly inserted element.[br]
[*Complexity:] Amortized constant time plus linear in the distance from the
insertion position to the end of the segment.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace_pos]
[def _emplace_pos_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace_pos `emplace_pos`]]

(1) `c.emplace_pos<U>(lbit,args...)`[br]
(2) `c.emplace_pos(lit,args...)`

[*Requires:] `U` is constructible from `std::forward<Args>(args)...`.
(1) `lbit` points to the segment for `U`.[br]
[*Effects:] Inserts a new element with
a subobject constructed from `std::forward<Args>(args)...` just before the
position indicated.[br]
[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) to the
newly inserted element.[br]
[*Complexity:] Amortized constant time plus linear in the distance from
the insertion position to the end of the segment.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert]
[def _insert_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert `insert`]]
[def _insert_hint_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert `insert`]]

(1) `c.insert(x)`[br]
(2) `c.insert(it,x)`

[*Effects:] Let `Q` be the type of the subobject of `x`. If
`Q` = `T` and `T` is acceptable, registers `T` if needed.
If `Q` = `T` and `T` is not acceptable, throws.
If `Q` \u2260 `T` and `Q` is not registered, throws.
If `x` is not a non-const rvalue expression and `Q` is not _CopyConstructible_, throws.
Inserts an element with a subobject move constructed or copy constructed
from the subobject of `x`: (1) at the end of the corresponding segment;
(2) just before the position indicated by `it`, if it points to the
corresponding segment, or at the end of the segment otherwise.[br]
[*Returns:] An `iterator` to the newly inserted element.[br]
[*Complexity:] Amortized constant time plus linear in the distance
from the insertion position to the end of the segment.

(1) `c.insert(lbit,x)`[br]
(2) `c.insert(lit,x)`

[*Requires:] The type of the subobject of `x` corresponds to the indicated
segment.[br]
[*Effects:] Inserts an element with a subobject move constructed or copy
constructed from the subobject of `x` just before the
position indicated.[br]
[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) to the
newly inserted element.[br]
[*Complexity:] Amortized constant time plus linear in the distance
from the insertion position to the end of the segment.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_range]
[def _insert_range_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_range `insert`]]

`c.insert(i1,i2)`

[*Effects:] Equivalent to `while(i1!=i2)c.insert(*i1++)`.

`c.insert(it1,it2)`[br]
`c.insert(lbit1,lbit2)`[br]
`c.insert(lit1,lit2)`

[*Effects:] For each of the elements of the range in succession, registers the
type of its subobject if needed and inserts it into the collection
[footnote Note that, unlike `c.insert(i1,i2)`, these versions do not throw
due to type registration problems.].

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_hint_range]
[def _insert_hint_range_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_hint_range `insert`]]

`c.insert(it,i1,i2)`

[*Effects:] If `it==c.end()`, equivalent to `while(i1!=i2)c.insert(it,*i1++)`,
otherwise inserts each of the elements in \[`i1`, `i2`) in succession with a hint
pointing to `*it`
[footnote That is, the hint remains stable even if `it` may become invalid due
to reallocations.].

`c.insert(it,it1,it2)`[br]
`c.insert(it,lbit1,lbit2)`[br]
`c.insert(it,lit1,lit2)`

[*Effects:] If `it==c.end()`, equivalent to the corresponding hint-less version,
otherwise for each of the elements in \[`i1`, `i2`) in succession registers the
type of its subobject if needed and inserts it into the collection with a hint
pointing to `*it`
[footnote The two previous notes apply here.].

`c.insert(lbit,i1,i2)`

[*Requires:] The subojects of elements in  \[`i1`, `i2`) are all of the type
corresponding to the indicated segment.[br]
[*Effects:] Inserts a range of elements with subobjects copy constructed from
those in \[`i1`, `i2`) just before `lbit`.[br]
[*Returns:] A `local_base_iterator` to the beginning of the inserted range.

`c.insert(lit,j1,j2)`

[*Requires:] For each value `x` in \[`j1`, `j2`) either (a) `x` is of a type
implementing the interface associated to the collection and the subobject of
`x` is of type `U` or (b) `U` is constructible from `x`.[br]
[*Effects:] Inserts a range of elements with subobjects copy
constructed (a) or constructed (b) from the values in \[`j1`, `j2`)
just before `lit`.[br]
[*Returns:] A `local_iterator<U>` to the beginning of the inserted range.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.erase]
[def _erase_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.erase `erase`]]

`c.erase(xit1)`[br]
`c.erase(xit1,xit2)`

[*Effects:] Erases the indicated element(s).[br]
[*Returns:] A non-const iterator of the same category as `xit` pointing
to the position just after the erased element(s).[br]
[*Complexity:] Linear on the number of elements erased plus the distance
from the last one to the end of its segment.

[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.clear]
[def _clear_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.clear `clear`]]

`c.clear()`

[*Effects:] Erases all the elements of the container.[br]
[*Complexity:] Linear.

`c.clear(info)`[br]
`c.clear<U>()`

[*Effects:] Erases all the elements of the segment for the indicated type.[br]
[*Complexity:] Linear in the size of the segment.[br]
[*Throws:] If the indicated type is not registered.

[endsect]

[endsect]

[endsect]

[import poly_collection_synopsis.qbk] [/ template poly_collection_synopsis]

[section Header `"boost/poly_collection/exception.hpp"` synopsis]

All the collections in Boost.PolyCollection use the following exceptions
(and only these) to signal various run-time problems with contained types:

  namespace boost{

  namespace poly_collection{

  struct ``[link poly_collection.reference.header_boost_poly_collection_exc.class_unregistered_type unregistered_type]``;
  struct ``[link poly_collection.reference.header_boost_poly_collection_exc.class_not_copy_constructible not_copy_constructible]``;
  struct ``[link poly_collection.reference.header_boost_poly_collection_exc.class_not_equality_comparable not_equality_comparable]``;

  } /* namespace poly_collection */

  } /* namespace boost */

[section Class `unregistered_type`]

  struct unregistered_type:std::logic_error
  {
    unregistered_type(const std::type_info& info);

    const std::type_info* pinfo;
  };

`unregistered_type` is thrown when an operation is requested on a type which
does not yet have an associated segment.

`unregistered_type(const std::type_info& info);`

[*Effects:] Constructs an `unregistered_type` object with the specified type
information.

[endsect]

[section Class `not_copy_constructible`]

  struct not_copy_constructible:std::logic_error
  {
    not_copy_constructible(const std::type_info& info);

    const std::type_info* pinfo;
  };

`not_copy_constructible` is thrown when a copy operation is tried that
involves a non-_CopyConstructible_ type.

`not_copy_constructible(const std::type_info& info);`

[*Effects:] Constructs a `not_copy_constructible` object with the specified
type information.

[endsect]

[section Class `not_equality_comparable`]

  struct not_equality_comparable:std::logic_error
  {
    not_equality_comparable(const std::type_info& info);

    const std::type_info* pinfo;
  };

`not_equality_comparable` is thrown when comparing two collections
for (in)equality involves a non-_EqualityComparable_ type.

`not_equality_comparable(const std::type_info& info);`

[*Effects:] Constructs a `not_equality_comparable` object with the specified
type information.

[endsect]

[endsect]

[section Header `"boost/poly_collection/base_collection_fwd.hpp"` synopsis]

[def _base_collection_ [link poly_collection.reference.header_boost_poly_collection_ba0.class_template_base_collection `base_collection`]]

  #include <memory>

  namespace boost{

  namespace poly_collection{

  template<typename Base,typename Allocator=std::allocator<Base>>
  class _base_collection_;

  template<typename Base,typename Allocator>
  bool operator==(
    const base_collection<Base,Allocator>& x,
    const base_collection<Base,Allocator>& y);

  template<typename Base,typename Allocator>
  bool operator!=(
    const base_collection<Base,Allocator>& x,
    const base_collection<Base,Allocator>& y);

  template<typename Base,typename Allocator>
  void swap(
    base_collection<Base,Allocator>& x,base_collection<Base,Allocator>& y);

  } /* namespace poly_collection */

  using poly_collection::base_collection;

  } /* namespace boost */

Forward declares the class template _base_collection_
and specifies its default template arguments. Forward declares associated free
functions and brings `boost::poly_collection::base_collection` to the `boost`
namespace.

[endsect]

[section Header `"boost/poly_collection/base_collection.hpp"` synopsis]

  #include <boost/poly_collection/base_collection_fwd.hpp>

  namespace boost{

  namespace poly_collection{

  template<typename Base,typename Allocator>
  class _base_collection_;

  template<typename Base,typename Allocator>
  bool operator==(
    const base_collection<Base,Allocator>& x,
    const base_collection<Base,Allocator>& y);

  template<typename Base,typename Allocator>
  bool operator!=(
    const base_collection<Base,Allocator>& x,
    const base_collection<Base,Allocator>& y);

  template<typename Base,typename Allocator>
  void swap(
    base_collection<Base,Allocator>& x,base_collection<Base,Allocator>& y);

  } /* namespace poly_collection */

  } /* namespace boost */

[section Class template `base_collection`]

`base_collection<Base,Allocator>` is a _PolymorphicCollection_ associated to
the classic base/derived _polymorphism_model_:

* *Interface* = { `Base` : `std::is_polymorphic_v<Base>` }.
* *Implementation*(`Base`) = { `Derived` : `std::is_base_of_v<Base,Derived>` }.
* *subobject*(`x`) = `static_cast<Derived&>(x)` with `typeid(x)==typeid(Derived)`.

[poly_collection_synopsis `base_collection`..`template<typename Base,typename Allocator>`..`Base`]

[endsect]

[endsect]

[section Header `"boost/poly_collection/function_collection_fwd.hpp"` synopsis]

[def _function_collection_ [link poly_collection.reference.header_boost_poly_collection_fu0.class_template_function_collecti `function_collection`]]
[def _function_collection_value_type_ [link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti `function_collection_value_type`]]

  #include <memory>

  namespace boost{

  namespace poly_collection{

  template<typename Signature>
  using _function_collection_value_type_=``/implementation-defined/``;

  template<
    typename Signature,
    typename Allocator=std::allocator<function_collection_value_type<Signature>>
  >
  class _function_collection_;

  template<typename Signature,typename Allocator>
  bool operator==(
    const function_collection<Signature,Allocator>& x,
    const function_collection<Signature,Allocator>& y);

  template<typename Signature,typename Allocator>
  bool operator!=(
    const function_collection<Signature,Allocator>& x,
    const function_collection<Signature,Allocator>& y);

  template<typename Signature,typename Allocator>
  void swap(
    function_collection<Signature,Allocator>& x,
    function_collection<Signature,Allocator>& y);

  } /* namespace poly_collection */

  using poly_collection::function_collection;

  } /* namespace boost */

Defines the alias template _function_collection_value_type_ (the actual type
it refers to, though, is merely forward declared).
Forward declares the class template _function_collection_
and specifies its default template arguments. Forward declares associated free
functions and brings `boost::poly_collection::function_collection` to the
`boost` namespace.

[endsect]

[section Header `"boost/poly_collection/function_collection.hpp"` synopsis]

  #include <boost/poly_collection/function_collection_fwd.hpp>

  namespace boost{

  namespace poly_collection{

  // defines the type ``_function_collection_value_type_`` refers to

  template<typename Signature,typename Allocator>
  class _function_collection_;

  template<typename Signature,typename Allocator>
  bool operator==(
    const function_collection<Signature,Allocator>& x,
    const function_collection<Signature,Allocator>& y);

  template<typename Signature,typename Allocator>
  bool operator!=(
    const function_collection<Signature,Allocator>& x,
    const function_collection<Signature,Allocator>& y);

  template<typename Signature,typename Allocator>
  void swap(
    function_collection<Signature,Allocator>& x,
    function_collection<Signature,Allocator>& y);

  } /* namespace poly_collection */

  } /* namespace boost */

[section Alias template `function_collection_value_type`]

`function_collection_value_type<Signature>` is the `value_type` of
`boost::function_collection<Signature,Allocator>`, where `Signature` must be a type
of the form `R(Args...)`. `function_collection_value_type<Signature>` wraps a
reference to an object modeling _Callable_ for the given `Signature`. The
interface provided partially replicates that of _std::function_ and adds some
extra facilities.

In what follows, the name [' `function_collection_value_type_impl`]
is used just for explanatory purposes in place of the actual
class template name, which is implementation defined.

  template<typename Signature>
  using function_collection_value_type=
    ``/function_collection_value_type_impl/``<Signature>;

  template<typename Signature>
  class ``/function_collection_value_type_impl/``;

  template<typename R,typename... Args>
  class ``/function_collection_value_type_impl/``<R(Args...)>
  {
  public:
    explicit ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_bool operator bool]``()const noexcept;

    R ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_call operator()]``(Args... args)const;

    const std::type_info& ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target_type target_type]``()const noexcept;
    template<typename T> T* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target target]``()noexcept;
    template<typename T> const T* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target target]``()const noexcept;

    operator ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_std_function std::function<R(Args...)>]``()const noexcept;

    void*       ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.data data]``()noexcept;
    const void* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.data data]``()const noexcept;
  };

[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_bool]

`explicit operator bool()const noexcept;`

[*Returns:] `true`.

[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_call]

`R operator()(Args... args)const;`

[*Effects:] `_INVOKE_(f,std::forward<Args>(args)...,R)`, where f is the wrapped
callable object.[br]
[*Returns:] Nothing if `R` is `void`, otherwise the return value of
`_INVOKE_(f,std::forward<Args>(args)...,R)`.

[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target_type]

`const std::type_info& target_type()const noexcept;`

[*Returns:] `typeid(T)` where `T` is the type of the wrapped callable object.

[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target]

`template<typename T> T* target()noexcept;`[br]
`template<typename T> const T* target()const noexcept;`

[*Returns:] If `target_type()==typeid(T)` a pointer to the wrapped callable
object, otherwise `nullptr`.

[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_std_function]

`operator std::function<R(Args...)>()const noexcept;`

[*Returns:] A `std::function<R(Args...)>` object holding a reference to the
wrapped callable object.

[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.data]

`void* data()noexcept;`[br]
`const void* data()const noexcept;`

[*Returns:] The address of the wrapped callable object.

[endsect]

[section Class template `function_collection`]

`function_collection<Signature,Allocator>` is a _PolymorphicCollection_ associated to
a dynamic _polymorphism_model_ based on call signature compatibility:

[itemized_list
  [*Interface* = { `Signature` : `Signature` = `R(Args...)` }.]
  [*Implementation*(`Signature`) = { `Callable` : `std::is_invocable_r_v<R,Callable,Args...>` }.]
  [*subobject*(`x`) =[br]
    `x.target<T>()` with `typeid(T)==x.target_type()`, if `x` is an instantiation of _function_collection_value_type_,[br]
    `x`, otherwise.
  ]
]

[poly_collection_synopsis `function_collection`..`template<typename Signature,typename Allocator>`..`_function_collection_value_type_<Signature>`]

[endsect]

[endsect]

[section Header `"boost/poly_collection/any_collection_fwd.hpp"` synopsis]

[def _any_collection_ [link poly_collection.reference.header_boost_poly_collection_an0.class_template_any_collection `any_collection`]]
[def _any_collection_value_type_ [link poly_collection.reference.header_boost_poly_collection_an0.alias_template_any_collection_va `any_collection_value_type`]]

  #include <memory>

  namespace boost{

  namespace poly_collection{

  template<typename Concept>
  using _any_collection_value_type_=``/implementation-defined/``;

  template<
    typename Concept,
    typename Allocator=std::allocator<any_collection_value_type<Concept>>
  >
  class _any_collection_;

  template<typename Concept,typename Allocator>
  bool operator==(
    const any_collection<Concept,Allocator>& x,
    const any_collection<Concept,Allocator>& y);

  template<typename Concept,typename Allocator>
  bool operator!=(
    const any_collection<Concept,Allocator>& x,
    const any_collection<Concept,Allocator>& y);

  template<typename Concept,typename Allocator>
  void swap(
    any_collection<Concept,Allocator>& x,any_collection<Concept,Allocator>& y);

  } /* namespace poly_collection */

  using poly_collection::any_collection;

  } /* namespace boost */

Defines the alias template _any_collection_value_type_ (the actual type
it refers to, though, is merely forward declared).
Forward declares the class template _any_collection_
and specifies its default template arguments. Forward declares associated free
functions and brings `boost::poly_collection::any_collection` to the
`boost` namespace.

[endsect]

[section Header `"boost/poly_collection/any_collection.hpp"` synopsis]

  #include <boost/poly_collection/any_collection_fwd.hpp>

  namespace boost{

  namespace poly_collection{

  // defines the type ``_any_collection_value_type_`` refers to

  template<typename Concept,typename Allocator>
  class _any_collection_;

  template<typename Concept,typename Allocator>
  bool operator==(
    const any_collection<Concept,Allocator>& x,
    const any_collection<Concept,Allocator>& y);

  template<typename Concept,typename Allocator>
  bool operator!=(
    const any_collection<Concept,Allocator>& x,
    const any_collection<Concept,Allocator>& y);

  template<typename Concept,typename Allocator>
  void swap(
    any_collection<Concept,Allocator>& x,any_collection<Concept,Allocator>& y);

  } /* namespace poly_collection */

  } /* namespace boost */

[section Alias template `any_collection_value_type`]

`any_collection_value_type<Concept>` is the `value_type` of
`boost::any_collection<Concept,Allocator>`, where `Concept` is defined according to
the [@boost:/doc/html/boost_typeerasure/conceptdef.html requisites]
of _Boost.TypeErasure_ using
[@boost:/doc/html/boost/type_erasure/_self.html `_self`]
as its [@boost:/doc/html/boost/type_erasure/placeholder.html placeholder].
The alias template definition has the form

  template<typename Concept>
  using any_collection_value_type=
    boost::type_erasure::``[@boost:/doc/html/boost/type_erasure/any.html any]``<Concept2,boost::type_erasure::_self&>;

with `boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/is_subconcept.html `is_subconcept`]`<Concept,Concept2>::value==true`.
The exact definition of `Concept2` is implementation defined.

[endsect]

[section Class template `any_collection`]

`any_collection<Concept,Allocator>` is a _PolymorphicCollection_ associated to
a dynamic _polymorphism_model_ based on _duck_typing_ as implemented by
_Boost.TypeErasure_:

[itemized_list
  [*Interface* = { `Concept` :
    as [@boost:/doc/html/boost_typeerasure/conceptdef.html specified] by _Boost.TypeErasure_,
    using the [@boost:/doc/html/boost/type_erasure/_self.html `_self`]
    [@boost:/doc/html/boost/type_erasure/placeholder.html placeholder] }.]
  [*Implementation*(`Concept`) = { `Concrete` : `Concrete` satisfies `Concept` }.]
  [*subobject*(`x`) =[br]
    `boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/any_cast.html `any_cast`]`<T&>(x)`
    with `typeid(T)==boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/typeid_of.html `typeid_of`]`(x)`,
    if `x` is an instantiation of `boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/any.html `any`]
    including [@boost:/doc/html/boost/type_erasure/typeid_.html `typeid_`]`<>`,[br]
    `x`, otherwise.
  ]
]

[poly_collection_synopsis `any_collection`..`template<typename Concept,typename Allocator>`..`_any_collection_value_type_<Concept>`]

[endsect]

[endsect]

[section Header `"boost/poly_collection/algorithm.hpp"` synopsis]

  namespace boost{

  namespace poly_collection{

  ``['`// non-modifying sequence operations:`]``

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  bool all_of(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  bool any_of(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  bool none_of(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<typename... Ts,typename PolyCollectionIterator,typename Function>
  Function for_each(
    PolyCollectionIterator first,PolyCollectionIterator last,Function f);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename Size,typename Function
  >
  Iterator for_each_n(
    PolyCollectionIterator first,Size n,Function f);

  template<typename... Ts,typename PolyCollectionIterator,typename T>
  PolyCollectionIterator find(
    PolyCollectionIterator first,PolyCollectionIterator last,const T& x);

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  PolyCollectionIterator find_if(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  PolyCollectionIterator find_if_not(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename ForwardIterator
  >
  PolyCollectionIterator find_end(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename ForwardIterator,typename BinaryPredicate
  >
  PolyCollectionIterator find_end(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename ForwardIterator
  >
  PolyCollectionIterator find_first_of(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename ForwardIterator,typename BinaryPredicate
  >
  PolyCollectionIterator find_first_of(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred);

  template<typename... Ts,typename PolyCollectionIterator>
  PolyCollectionIterator adjacent_find(
    PolyCollectionIterator first,PolyCollectionIterator last);

  template<
    typename... Ts,typename PolyCollectionIterator,typename BinaryPredicate
  >
  PolyCollectionIterator adjacent_find(
    PolyCollectionIterator first,PolyCollectionIterator last,
    BinaryPredicate pred);

  template<typename... Ts,typename PolyCollectionIterator,typename T>
  std::ptrdiff_t count(
    PolyCollectionIterator first,PolyCollectionIterator last,const T& x);

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  std::ptrdiff_t count_if(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename InputIterator
  >
  std::pair<PolyCollectionIterator,InputIterator> mismatch(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename InputIterator,typename BinaryPredicate
  >
  std::pair<PolyCollectionIterator,InputIterator> mismatch(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename InputIterator
  >
  std::pair<PolyCollectionIterator,InputIterator> mismatch(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,InputIterator last2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename InputIterator,typename BinaryPredicate
  >
  std::pair<PolyCollectionIterator,InputIterator> mismatch(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,InputIterator last2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename InputIterator
  >
  bool equal(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename InputIterator,typename BinaryPredicate
  >
  bool equal(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename InputIterator
  >
  bool equal(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,InputIterator last2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename InputIterator,typename BinaryPredicate
  >
  bool equal(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,InputIterator last2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename ForwardIterator
  >
  bool is_permutation(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename ForwardIterator,typename BinaryPredicate
  >
  bool is_permutation(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename ForwardIterator
  >
  bool is_permutation(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename ForwardIterator,typename BinaryPredicate
  >
  bool is_permutation(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename ForwardIterator
  >
  PolyCollectionIterator search(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename ForwardIterator,typename BinaryPredicate
  >
  PolyCollectionIterator search(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename Size,typename T
  >
  PolyCollectionIterator search_n(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    Size count,const T& x);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename Size,typename T,typename BinaryPredicate
  >
  PolyCollectionIterator search_n(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    Size count,const T& x,BinaryPredicate pred);

  ``['`// modifying sequence operations:`]``

  template<
    typename... Ts,typename PolyCollectionIterator,typename OutputIterator
  >
  OutputIterator copy(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename Size,typename OutputIterator
  >
  OutputIterator copy_n(
    PolyCollectionIterator first,Size count,OutputIterator res);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename Predicate
  >
  OutputIterator copy_if(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,Predicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename OutputIterator
  >
  OutputIterator move(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename UnaryOperation
  >
  OutputIterator transform(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,UnaryOperation op);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename InputIterator,typename OutputIterator,typename BinaryOperation
  >
  OutputIterator transform(
    PolyCollectionIterator first1,PolyCollectionIterator last1,
    InputIterator first2,OutputIterator res,BinaryOperation op);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename T
  >
  OutputIterator replace_copy(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,const T& old_x,const T& new_x);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename Predicate,typename T
  >
  OutputIterator replace_copy_if(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,Predicate pred,const T& new_x);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename T
  >
  OutputIterator remove_copy(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,const T& x);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename Predicate
  >
  OutputIterator remove_copy_if(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,Predicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename OutputIterator
  >
  OutputIterator unique_copy(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator,typename BinaryPredicate
  >
  OutputIterator unique_copy(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,BinaryPredicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,typename OutputIterator
  >
  OutputIterator rotate_copy(
    PolyCollectionIterator first,PolyCollectionIterator middle,
    PolyCollectionIterator last,OutputIterator res);

  template<
    typename... Ts,typename PolyCollectionIterator,typename OutputIterator,
    typename Distance,typename UniformRandomBitGenerator
  >
  OutputIterator sample(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator res,Distance n,UniformRandomBitGenerator&& g);
  
  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  bool is_partitioned(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  template<
    typename... Ts,typename PolyCollectionIterator,
    typename OutputIterator1,typename OutputIterator2,typename Predicate
  >
  std::pair<OutputIterator1,OutputIterator2> partition_copy(
    PolyCollectionIterator first,PolyCollectionIterator last,
    OutputIterator1 rest,OutputIterator2 resf,Predicate pred);

  template<typename... Ts,typename PolyCollectionIterator,typename Predicate>
  PolyCollectionIterator partition_point(
    PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred);

  } /* namespace poly_collection */

  } /* namespace boost */

The algorithms provided mimic the functionality of their homonyms in
[@http://en.cppreference.com/w/cpp/algorithm `<algorithm>`] but take advantage
of the segmented nature of Boost.PolyCollection (global) iterators to
deliver better performance. Additionally, concrete types can be passed to
these algorithms for /type restitution/.

For the description of the algorithms we use the following notation:

* [' `alg`] is the (unqualified) name of any of the algorithms in
`"boost/poly_collection/algorithm.hpp"` except `copy_n` and `rotate_copy`.
* `first`, `middle` and `last` are (same-typed) possibly const global iterators
of a collection of Boost.PolyCollection such that \[`first`, `middle`) and
\[`middle`, `last`) are valid ranges.
* `args...` is a function parameter pack of types `Args&&...`,
* `Ts...` is a template parameter pack of arbitrary types. 

(1) [' `alg`]`(first,last,args...)`[br]
(2) `for_each_n(first,args...)`[br]
(3) `copy_n(first,args...)`[br]
(4) `rotate_copy(first,middle,last,args...)`

[*Requires:] The expression `expr` is well-formed, where `expr` is defined
as:[br]
(1) `std::`[' `alg`]`(first,last,args...)`,[br]
(2) `std::for_each_n(first,args...)`,[br]
(3) `std::copy_n(first,args...)`,[br]
(4) `std::rotate_copy(first,middle,last,args...)`.[br]
[*Effects:] Equivalent to `expr`.[br]
[*Returns:] `expr`.[br]
[*Complexity:] That of `expr`.

(1) [' `alg`]`<Ts...>(first,last,args...)`[br]
(2) `for_each_n<Ts...>(first,args...)`[br]
(3) `copy_n<Ts...>(first,args...)`[br]
(4) `rotate_copy<Ts...>(first,middle,last,args...)`

[*Requires:] The expression `expr` is well-formed, where `expr` is defined
as:[br]
(1) `std::`[' `alg`]`(rfirst,rlast,args...)`,[br]
(2) `std::for_each_n(rfirst,args...)`,[br]
(3) `std::copy_n(rfirst,args...)`,[br]
(4) `std::rotate_copy(rfirst,rmiddle,rlast,args...)`,[br]
and `rfirst`, `rmiddle` and `rlast` are iterator-like objects behaving like
their `first`, `middle` and `last` counterparts except that they
dereference to the corresponding subobject (`const`) `T&` if pointing to a
segment for `T` and `T` is in `Ts...`
[footnote Strictly speaking a proper _ForwardIterator_ cannot behave
like this as dereferencing must yield /exactly/ a (`const`) `value_type&`
value, which disallows this type of polymorphism.].[br]
[*Effects:] Equivalent to `expr`.[br]
[*Returns:] `expr`.[br]
[*Complexity:] That of `expr`.

[endsect]

[endsect]