1[/ 2 Copyright 2016-2017 Joaquin M Lopez Munoz. 3 Distributed under the Boost Software License, Version 1.0. 4 (See accompanying file LICENSE_1_0.txt or copy at 5 http://www.boost.org/LICENSE_1_0.txt) 6] 7 8[def _AllocatorAwareContainer_ [@http://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer [* `AllocatorAwareContainer`]]] 9[def _Callable_ [@http://en.cppreference.com/w/cpp/named_req/Callable [* `Callable`]]] 10[def _Container_ [@http://en.cppreference.com/w/cpp/named_req/Container [* `Container`]]] 11[def _CopyAssignable_ [@http://en.cppreference.com/w/cpp/named_req/CopyAssignable [* `CopyAssignable`]]] 12[def _CopyInsertable_ [@http://en.cppreference.com/w/cpp/named_req/CopyInsertable [* `CopyInsertable`]]] 13[def _DefaultConstructible_ [@http://en.cppreference.com/w/cpp/named_req/DefaultConstructible [* `DefaultConstructible`]]] 14[def _InputIterator_ [@http://en.cppreference.com/w/cpp/named_req/InputIterator [* `InputIterator`]]] 15[def _INVOKE_ [@http://en.cppreference.com/w/cpp/utility/functional/invoke ['[* `INVOKE`]]]] 16[def _MoveAssignable_ [@http://en.cppreference.com/w/cpp/named_req/MoveAssignable [* `MoveAssignable`]]] 17[def _MoveInsertable_ [@http://en.cppreference.com/w/cpp/named_req/MoveInsertable [* `MoveInsertable`]]] 18 19[section Reference] 20 21[section Polymorphism models] 22 23[def _polymorphism_model_ [link poly_collection.reference.polymorphism_models polymorphism model]] 24 25The key aspect of dynamic polymorphism is the ability for a value of type `T` 26to internally use another value of a possibily different type `U` for the 27implementation of a given interface. Base/derived polymorphism is the classic 28model of dynamic polymorphism in C++, but not the only possible one. 29 30Formally, a /polymorphism model/ is defined by 31 32* A family *Interface* of permissible interface types and, for each 33`I` \u2208 *Interface*, the family *Implementation*(`I`) of types satisfying 34`I`. 35* For a given interface type `I`, an operation *subobject*(`x`) that maps each 36value of an implementation type to its internally used value `y` of a possibly 37different implementation type 38[footnote This is a metalinguistic definition not directly expressible in C++. 39There are equivalent formulations that can indeed be realized in C++, but 40they add little to the comprehension of the concepts.]. 41 42Static polymorphism is the trivial case where *subobject*(`x`) = `x` for all 43`x`. Base/derived polymorphism is characterized by: 44 45* *Interface* = { `Base` : `std::is_polymorphic_v<Base>` }. 46* *Implementation*(`Base`) = { `Derived` : `std::is_base_of_v<Base,Derived>` }. 47* *subobject*(`x`) = `static_cast<Derived&>(x)` with `typeid(x)==typeid(Derived)`. 48 49[endsect] 50 51[section Polymorphic containers] 52 53[def _PolymorphicContainer_ [link poly_collection.reference.polymorphic_containers [* `PolymorphicContainer`]]] 54 55A /polymorphic container/ is an object that stores objects of some type `T` 56implementing a given interface `I` under an implicitly associated polymorphism 57model. Polymorphic containers satisfy the requirements for _Container_ and 58_AllocatorAwareContainer_ with the following modifications: 59 60* Where it occurs, replace the requirement that `T` be _CopyInsertable_, 61_CopyAssignable_, _MoveInsertable_, _MoveAssignable_ or 62_EqualityComparable_, with the following semantic clause: may throw if 63some subobject in the container is not 64_CopyConstructible_ (respectively, _CopyAssignable_, _MoveConstructible_, 65_MoveAssignable_, _EqualityComparable_). 66* Replace [container.requirements.general]/3 with: 67`allocator_type` must have the property that for any type `U` 68implementing `I` and the associated type `A` = 69`std::allocator_traits<allocator_type>::rebind_alloc<U>`, `U` is 70_CopyInsertable_ (respectively _MoveInsertable_) with respect to `A` if and 71only if `U` is _CopyConstructible_ (respectively _MoveConstructible_); 72all subobjects of type `U` stored in these containers shall be constructed 73using the `std::allocator_traits<A>::construct` function and 74destroyed using the `std::allocator_traits<A>::destroy` function; 75these functions (or their equivalents for a rebound allocator) are called 76only for the types of the stored subobjects, not for 77any other type (internal or public) used by the container. 78 79[section Polymorphic collections] 80 81[def _PolymorphicCollection_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections [* `PolymorphicCollection`]]] 82 83/Polymorphic collections/ store their objects of type `value_type` in 84/segments/ dedicated to each of the types of the contained subojects. 85Only objects whose subobjects are of an /acceptable/ type are allowed, 86where a type `U` is said to be acceptable if 87 88* it implements the interface associated to the container, 89* it is _MoveConstructible_, 90* it is _MoveAssignable_ or 91[@http://en.cppreference.com/w/cpp/types/is_move_constructible 92`std::is_nothrow_move_constructible<U>::value`] is `true`. 93 94Polymorphic collections conform 95to the requirements of _PolymorphicContainer_ with the following 96modfications and extra guarantees: 97 98* The complexity of `empty()` and `size()` is linear on the number of 99segments of the collection. 100* `max_size()` is not provided. 101* `a==b` evaluates to `true` iff for each non-empty segment of subojects 102of type `U` in `a` there is a segment of `U` in `b` with the same size 103and equal elements in the same order, and vice versa. 104* No exceptions are thrown associated to some subobject type not being 105_CopyAssignable_, _MoveConstructible_ or _MoveAssignable_. 106 107A type `U` is said to be /registered/ into the collection if a 108(possibly empty) segment for `U` has been created. Registered types 109continue to stay so for the duration of the container except if it is 110moved from, assigned to, or swapped. 111 112Each segment has an associated capacity indicating the maximum size 113that it can attain without reallocation. When the limit 114is exceeded (or explicitly through `reserve`) new storage space is 115allocated with greater capacity and elements are moved. 116 117Collection traversal goes through the elements of the first segment, 118then the second, etc. The order in which segments are visited is 119unspecified but remains stable until a new segment is created. 120 121Besides `iterator` and `const_iterator`, there are iterator types 122`local_base_iterator` and `local_iterator<U>` (and their `const_` 123counterparts) whose objects can be used to iterate over the segment 124for `U` (in the same order followed by global traversal). 125Local base iterators refer to `value_type`, whereas 126(`const_`)`local_iterator<U>` refers to `U`. All local iterators model 127_RandomAccessIterator_. Local base iterators may not be used 128to iterate across segments, and comparing local base iterators 129associated to different segments is undefined behavior. A (const) 130local base iterator to a segment for `U` can be explicitly converted 131to (`const_`)`local_iterator<U>` pointing to the same position, 132and vice versa. 133 134Insertion and erasure do not invalidate iterators (global or local) 135except those from the insertion/erasure point to the end of the 136affected segment, if its capacity is not exceeded, or all 137iterators/references to the segment otherwise 138[footnote The global `end()` iterator lies outside any segment, hence 139it always remain valid.]. 140 141For the description of the remaining requirements of polymorphic collections, 142we use the following notation: 143 144* `C` is a polymorphic collection type, 145* `c` is an object of type `C`, `cc` is a possibly `const` object of type `C`, 146* `al` is a value of type `C::allocator_type`, 147* `info` is a `const std::type_info&`, 148* `U` is an acceptable type, `Us...` is a template parameter pack of 149acceptable types, 150* `n` is a value of `size_type`, 151* `x` is a value of a type `T` implementing the interface associated to the 152collection, 153* `args...` is a function parameter pack of types `Args&&...`, 154* `it` is a possibly const global iterator of `c`, 155* `it1` and `it2` are (same-typed) possibly const global iterators of a `C` 156collection other than `c` such that \[`it1`, `it2`) is a valid range. 157* `lbit` is a possibly const local base iterator of `c`, 158* `lbit1` and `lbit2` are (same-typed) possibly const local base iterators of 159a `C` collection other than `c` such that \[`lbit1`, `lbit2`) is a valid range. 160* `lit` is a (`const_`)`local_iterator<U>` of `c`, 161* `lit1` and `lit2` are (same-typed) (`const_`)`local_iterator<U>`s of 162a `C` collection other than `c` such that \[`lit1`, `lit2`) is a valid range, 163* `i1` and `i2` are iterators external to `c` referring to `T` such that 164\[`i1`, `i2`) is a valid range, 165* `j1` and `j2` are iterators external to `c` such that 166\[`j1`, `j2`) is a valid range, 167* `xit1` and `xit2` are (same-typed) possibly const iterators (global or 168local) of `c` such that \[`xit1`, `xit2`) is a valid range. 169 170[section Types] 171 172[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_base_iterator] 173[def _local_base_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_base_iterator `local_base_iterator`]] 174 175`C::local_base_iterator` 176 177_RandomAccessIterator_ with same value type, difference type and pointer and 178reference types as `C::iterator`, valid for accessing elements of a given 179segment. Implicily convertible to `C::const_local_base_iterator`, explicitly 180convertible to `C::local_iterator<U>` if the segment it points to is actually 181that for `U`. 182 183[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_base_iterator] 184[def _const_local_base_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_base_iterator `const_local_base_iterator`]] 185 186`C::const_local_base_iterator` 187 188_RandomAccessIterator_ with same value type, difference type and pointer and 189reference types as `C::const_iterator`, valid for accessing elements of a given 190segment. Explicitly convertible to `C::const_local_iterator<U>` if the segment 191it points to is actually that for `U`. 192 193[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_iterator] 194[def _local_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.local_iterator `local_iterator`]] 195 196`C::local_iterator<U>` 197 198_RandomAccessIterator_ with value type `U`, reference type `U&`, pointer type 199`U*` and the same difference type as `C::iterator`, valid for accessing elements 200of the segment for `U`. Implicily convertible to `C::const_local_iterator<U>`, 201explicitly convertible to `C::local_base_iterator`. 202 203[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_iterator] 204[def _const_local_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_local_iterator `const_local_iterator`]] 205 206`C::const_local_iterator<U>` 207 208_RandomAccessIterator_ with value type `U`, reference type `const U&`, pointer 209type `const U*` and the same difference type as `C::iterator`, valid for 210accessing elements of the segment for `U`. Explicitly convertible to 211`C::const_local_base_iterator`. 212 213[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info] 214[def _const_base_segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info `const_base_segment_info`]] 215 216`C::const_base_segment_info` 217 218_CopyConstructible_ and _CopyAssignable_ type with information about a given 219segment of a collection. If `ci` is a possibly `const` object of type 220`C::const_base_segment_info` associated to the segment of `c` for `U`, then 221 222* `ci.begin()==c.cbegin(typeid(U))` 223* `ci.cbegin()==c.cbegin(typeid(U))` 224* `ci.begin<U>()==c.cbegin<U>()` 225* `ci.cbegin<U>()==c.cbegin<U>()` 226* `ci.end()==c.cend(typeid(U))` 227* `ci.cend()==c.cend(typeid(U))` 228* `ci.end<U>()==c.cend<U>()` 229* `ci.cend<U>()==c.cend<U>()` 230* `ci.type_info()==typeid(U)` 231 232[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info] 233[def _base_segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info `base_segment_info`]] 234 235`C::base_segment_info` 236 237_CopyConstructible_ and _CopyAssignable_ type publicly derived from 238`C::const_base_segment_info` and exposing its public interface. Additionally, 239if `i` is an object of type `C::base_segment_info` associated to the 240segment of `c` for `U`, then 241 242* `i.begin()==c.begin(typeid(U))` 243* `i.begin<U>()==c.begin<U>()` 244* `i.end()==c.end(typeid(U))` 245* `i.end<U>()==c.end<U>()` 246 247[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_info] 248[def _const_segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_info `const_segment_info`]] 249 250`C::const_segment_info<U>` 251 252_CopyConstructible_ and _CopyAssignable_ type with information about the segment 253for `U`. If `ci` is a possibly `const` object of type `C::const_segment_info<U>` 254associated to the collection `c`, then 255 256* `ci.begin()==c.cbegin<U>()` 257* `ci.cbegin()==c.cbegin<U>()` 258* `ci.end()==c.cend<U>()` 259* `ci.cend()==c.cend<U>()` 260 261[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_info] 262[def _segment_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_info `segment_info`]] 263 264`C::segment_info<U>` 265 266_CopyConstructible_ and _CopyAssignable_ type publicly derived from 267`C::const_segment_info<U>` and exposing its public interface. Additionally, 268if `i` is an object of type `C::segment_info<U>` associated to the collection 269`c`, then 270 271* `i.begin()==c.begin<U>()` 272* `i.end()==c.end<U>()` 273 274[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info_iterator] 275[def _base_segment_info_iterator_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.base_segment_info_iterator `base_segment_info_iterator`]] 276 277`C::base_segment_info_iterator` 278 279_InputIterator_ with value type and reference type `C::base_segment_info`. 280 281[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_base_segment_info_iterator] 282[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`]] 283 284`C::const_base_segment_info_iterator` 285 286_InputIterator_ with value type and reference type `C::const_base_segment_info`. 287 288[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_traversal_info] 289[def _const_segment_traversal_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.const_segment_traversal_info `const_segment_traversal_info`]] 290 291`C::const_segment_traversal_info` 292 293_CopyConstructible_ and _CopyAssignable_ type with `const` member 294functions `begin`/`cbegin` and `end`/`cend` returning 295`C::const_base_segment_info_iterator` objects that span over a range 296of `C::const_base_segment_info` objects. 297 298[#poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_traversal_info] 299[def _segment_traversal_info_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.types.segment_traversal_info `segment_traversal_info`]] 300 301`C::segment_traversal_info` 302 303_CopyConstructible_ and _CopyAssignable_ type publicly derived 304from with `C::const_segment_traversal_info` and exposing its 305public interface. Additionally, provides non-const member 306functions `begin` and `end` returning 307`C::base_segment_info_iterator` objects that span over an equivalent range 308of `C::base_segment_info` objects. 309 310[endsect] 311 312[section Construct/copy/destroy] 313 314[#poly_collection.reference.polymorphic_containers.polymorphic_collections.construct_copy_destroy.range_construction] 315 316`C(j1,j2)`[br] 317`C d(j1,j2)` 318 319[*Requires:] `C::allocator_type` is _DefaultConstructible_. \[`j1`, `j2`) can be 320inserted into `C`.[br] 321[*Effects:] Copy constructs the internal allocator from `C::allocator_type()`. 322Internally calls `this->insert(j1,j2)` on construction. 323 324`C(j1,j2,al)`[br] 325`C d(j1,j2,al)` 326 327[*Requires:] \[`j1`, `j2`) can be inserted into `C`.[br] 328[*Effects:] Copy constructs the internal allocator from `al`. 329Internally calls `this->insert(j1,j2)` on construction. 330 331[endsect] 332 333[section Type registration] 334 335[#poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.register_types] 336[def _register_types_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.register_types `register_types`]] 337 338`c.register_types<Us...>()` 339 340[*Effects:] Registers (if needed) each of the indicated types in the 341collection. 342 343[#poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.is_registered] 344[def _is_registered_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.type_registration.is_registered `is_registered`]] 345 346`cc.is_registered(info)`[br] 347`cc.is_registered<U>()` 348 349[*Returns:] `true` iff the indicated type is registered in the collection. 350 351[endsect] 352 353[section Iterators] 354 355[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.begin] 356[def _begin_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.begin `begin`]] 357[def _cbegin_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.begin `cbegin`]] 358 359(1) `c.begin(info)`[br] 360(2) `c.begin<U>()`[br] 361(3) `const_cast<const C&>(c).begin(info)`[br] 362(4) `cc.cbegin(info)`[br] 363(5) `const_cast<const C&>(c).begin<U>()`[br] 364(6) `cc.cbegin<U>()` 365 366[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) or 367`const_local_base_iterator` (3,4) or `const_local_iterator<U>` (5,6) to the 368beginning of the segment for the indicated type.[br] 369[*Throws:] If the indicated type is not registered. 370 371[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.end] 372[def _end_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.end `end`]] 373[def _cend_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.end `cend`]] 374 375(1) `c.end(info)`[br] 376(2) `c.end<U>()`[br] 377(3) `const_cast<const C&>(c).end(info)`[br] 378(4) `cc.cend(info)`[br] 379(5) `const_cast<const C&>(c).end<U>()`[br] 380(6) `cc.cend<U>()` 381 382[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) or 383`const_local_base_iterator` (3,4) or `const_local_iterator<U>` (5,6) to the 384end of the segment for the indicated type.[br] 385[*Throws:] If the indicated type is not registered. 386 387[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment] 388[def _segment_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment `segment`]] 389 390(1) `c.segment(info)`[br] 391(2) `c.segment<U>()`[br] 392(3) `const_cast<const C&>(c).segment(info)`[br] 393(4) `const_cast<const C&>(c).segment<U>()`[br] 394 395[*Returns:] A `base_segment_info` (1) or `segment_info<U>` (2) or 396`const_base_segment_info` (3) or `const_segment_info<U>` (4) object 397referring to the segment for the indicated type.[br] 398[*Throws:] If the indicated type is not registered. 399 400[#poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment_traversal] 401[def _segment_traversal_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.iterators.segment_traversal `segment_traversal`]] 402 403(1) `c.segment_traversal()`[br] 404(2) `const_cast<const C&>(c).segment_traversal()` 405 406[*Returns:] A `segment_traversal_info` (1) or `const_segment_traversal_info` 407(2) object spanning over a range of segment descriptors for the collection. 408The order in which segments are visited matches that of 409\[`c.begin()`, `c.end()`). 410 411[endsect] 412 413[section Capacity] 414 415[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.empty] 416[def _empty_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.empty `empty`]] 417 418`cc.empty(info)`[br] 419`cc.empty<U>()` 420 421[*Returns:] `true` iff the segment for the indicated type exists and 422is empty.[br] 423[*Throws:] If the indicated type is not registered. 424 425[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.size] 426[def _size_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.size `size`]] 427 428`cc.size(info)`[br] 429`cc.size<U>()` 430 431[*Returns:] The size of the segment for the indicated type.[br] 432[*Throws:] If the indicated type is not registered. 433 434[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.max_size] 435[def _max_size_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.max_size `max_size`]] 436 437`cc.max_size(info)`[br] 438`cc.max_size<U>()` 439 440[*Returns:] The maximum size attainable by the segment for 441the indicated type.[br] 442[*Throws:] If the indicated type is not registered. 443 444[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.capacity] 445[def _capacity_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.capacity `capacity`]] 446 447`cc.capacity(info)`[br] 448`cc.capacity<U>()`[br] 449 450[*Returns:] The maximum size that the segment for the indicated type can 451attain without requiring reallocation.[br] 452[*Throws:] If the indicated type is not registered. 453 454[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.reserve] 455[def _reserve_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.reserve `reserve`]] 456 457`c.reserve(n)` 458 459[*Effects:] Calls `reserve` with `n` for each of the segments of the 460collection. 461 462(1) `c.reserve(info,n)`[br] 463(2) `c.reserve<U>(n)` 464 465[*Effects:] Throws if the type indicated by `info` is not registered (1) 466or registers `U` if needed (2). If `n` is greater than the current 467capacity of the segment for the indicated type, new storage space is allocated 468with a capacity of at least `n` and elements are moved there.[br] 469[*Complexity:] Linear in the size of the segment if reallocation happens, 470constant otherwise.[br] 471[*Throws:] `std::length_error` if `n` is greater than the return value of 472`max_size` for the segment. 473 474[#poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.shrink_to_fit] 475[def _shrink_to_fit_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.capacity.shrink_to_fit `shrink_to_fit`]] 476 477`c.shrink_to_fit()` 478 479[*Effects:] Calls `shrink_to_fit` for each of the segments of the 480collection. 481 482`c.shrink_to_fit(info)`[br] 483`c.shrink_to_fit<U>()` 484 485[*Effects:] Non-binding request to reduce memory usage while preserving the 486sequence of elements of the segment for the indicated type. May invalidate 487all iterators and references to the segment.[br] 488[*Throws:] If the indicated type is not registered. 489 490[endsect] 491 492[section Modifiers] 493 494[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace] 495[def _emplace_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace `emplace`]] 496[def _emplace_hint_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace `emplace_hint`]] 497 498(1) `c.emplace<U>(args...)`[br] 499(2) `c.emplace_hint<U>(it,args...)` 500 501[*Requires:] `U` is constructible from `std::forward<Args>(args)...`.[br] 502[*Effects:] Registers `U` (if needed) and inserts a new element with 503a subobject constructed from `std::forward<Args>(args)...`: (1) at the end of 504the segment for `U`; (2) just before the 505position indicated by `it`, if it points to the segment for `U`, or at the 506end of the segment for `U` otherwise.[br] 507[*Returns:] An `iterator` to the newly inserted element.[br] 508[*Complexity:] Amortized constant time plus linear in the distance from the 509insertion position to the end of the segment. 510 511[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace_pos] 512[def _emplace_pos_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.emplace_pos `emplace_pos`]] 513 514(1) `c.emplace_pos<U>(lbit,args...)`[br] 515(2) `c.emplace_pos(lit,args...)` 516 517[*Requires:] `U` is constructible from `std::forward<Args>(args)...`. 518(1) `lbit` points to the segment for `U`.[br] 519[*Effects:] Inserts a new element with 520a subobject constructed from `std::forward<Args>(args)...` just before the 521position indicated.[br] 522[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) to the 523newly inserted element.[br] 524[*Complexity:] Amortized constant time plus linear in the distance from 525the insertion position to the end of the segment. 526 527[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert] 528[def _insert_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert `insert`]] 529[def _insert_hint_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert `insert`]] 530 531(1) `c.insert(x)`[br] 532(2) `c.insert(it,x)` 533 534[*Effects:] Let `Q` be the type of the subobject of `x`. If 535`Q` = `T` and `T` is acceptable, registers `T` if needed. 536If `Q` = `T` and `T` is not acceptable, throws. 537If `Q` \u2260 `T` and `Q` is not registered, throws. 538If `x` is not a non-const rvalue expression and `Q` is not _CopyConstructible_, throws. 539Inserts an element with a subobject move constructed or copy constructed 540from the subobject of `x`: (1) at the end of the corresponding segment; 541(2) just before the position indicated by `it`, if it points to the 542corresponding segment, or at the end of the segment otherwise.[br] 543[*Returns:] An `iterator` to the newly inserted element.[br] 544[*Complexity:] Amortized constant time plus linear in the distance 545from the insertion position to the end of the segment. 546 547(1) `c.insert(lbit,x)`[br] 548(2) `c.insert(lit,x)` 549 550[*Requires:] The type of the subobject of `x` corresponds to the indicated 551segment.[br] 552[*Effects:] Inserts an element with a subobject move constructed or copy 553constructed from the subobject of `x` just before the 554position indicated.[br] 555[*Returns:] A `local_base_iterator` (1) or `local_iterator<U>` (2) to the 556newly inserted element.[br] 557[*Complexity:] Amortized constant time plus linear in the distance 558from the insertion position to the end of the segment. 559 560[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_range] 561[def _insert_range_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_range `insert`]] 562 563`c.insert(i1,i2)` 564 565[*Effects:] Equivalent to `while(i1!=i2)c.insert(*i1++)`. 566 567`c.insert(it1,it2)`[br] 568`c.insert(lbit1,lbit2)`[br] 569`c.insert(lit1,lit2)` 570 571[*Effects:] For each of the elements of the range in succession, registers the 572type of its subobject if needed and inserts it into the collection 573[footnote Note that, unlike `c.insert(i1,i2)`, these versions do not throw 574due to type registration problems.]. 575 576[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_hint_range] 577[def _insert_hint_range_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.insert_hint_range `insert`]] 578 579`c.insert(it,i1,i2)` 580 581[*Effects:] If `it==c.end()`, equivalent to `while(i1!=i2)c.insert(it,*i1++)`, 582otherwise inserts each of the elements in \[`i1`, `i2`) in succession with a hint 583pointing to `*it` 584[footnote That is, the hint remains stable even if `it` may become invalid due 585to reallocations.]. 586 587`c.insert(it,it1,it2)`[br] 588`c.insert(it,lbit1,lbit2)`[br] 589`c.insert(it,lit1,lit2)` 590 591[*Effects:] If `it==c.end()`, equivalent to the corresponding hint-less version, 592otherwise for each of the elements in \[`i1`, `i2`) in succession registers the 593type of its subobject if needed and inserts it into the collection with a hint 594pointing to `*it` 595[footnote The two previous notes apply here.]. 596 597`c.insert(lbit,i1,i2)` 598 599[*Requires:] The subojects of elements in \[`i1`, `i2`) are all of the type 600corresponding to the indicated segment.[br] 601[*Effects:] Inserts a range of elements with subobjects copy constructed from 602those in \[`i1`, `i2`) just before `lbit`.[br] 603[*Returns:] A `local_base_iterator` to the beginning of the inserted range. 604 605`c.insert(lit,j1,j2)` 606 607[*Requires:] For each value `x` in \[`j1`, `j2`) either (a) `x` is of a type 608implementing the interface associated to the collection and the subobject of 609`x` is of type `U` or (b) `U` is constructible from `x`.[br] 610[*Effects:] Inserts a range of elements with subobjects copy 611constructed (a) or constructed (b) from the values in \[`j1`, `j2`) 612just before `lit`.[br] 613[*Returns:] A `local_iterator<U>` to the beginning of the inserted range. 614 615[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.erase] 616[def _erase_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.erase `erase`]] 617 618`c.erase(xit1)`[br] 619`c.erase(xit1,xit2)` 620 621[*Effects:] Erases the indicated element(s).[br] 622[*Returns:] A non-const iterator of the same category as `xit` pointing 623to the position just after the erased element(s).[br] 624[*Complexity:] Linear on the number of elements erased plus the distance 625from the last one to the end of its segment. 626 627[#poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.clear] 628[def _clear_ [link poly_collection.reference.polymorphic_containers.polymorphic_collections.modifiers.clear `clear`]] 629 630`c.clear()` 631 632[*Effects:] Erases all the elements of the container.[br] 633[*Complexity:] Linear. 634 635`c.clear(info)`[br] 636`c.clear<U>()` 637 638[*Effects:] Erases all the elements of the segment for the indicated type.[br] 639[*Complexity:] Linear in the size of the segment.[br] 640[*Throws:] If the indicated type is not registered. 641 642[endsect] 643 644[endsect] 645 646[endsect] 647 648[import poly_collection_synopsis.qbk] [/ template poly_collection_synopsis] 649 650[section Header `"boost/poly_collection/exception.hpp"` synopsis] 651 652All the collections in Boost.PolyCollection use the following exceptions 653(and only these) to signal various run-time problems with contained types: 654 655 namespace boost{ 656 657 namespace poly_collection{ 658 659 struct ``[link poly_collection.reference.header_boost_poly_collection_exc.class_unregistered_type unregistered_type]``; 660 struct ``[link poly_collection.reference.header_boost_poly_collection_exc.class_not_copy_constructible not_copy_constructible]``; 661 struct ``[link poly_collection.reference.header_boost_poly_collection_exc.class_not_equality_comparable not_equality_comparable]``; 662 663 } /* namespace poly_collection */ 664 665 } /* namespace boost */ 666 667[section Class `unregistered_type`] 668 669 struct unregistered_type:std::logic_error 670 { 671 unregistered_type(const std::type_info& info); 672 673 const std::type_info* pinfo; 674 }; 675 676`unregistered_type` is thrown when an operation is requested on a type which 677does not yet have an associated segment. 678 679`unregistered_type(const std::type_info& info);` 680 681[*Effects:] Constructs an `unregistered_type` object with the specified type 682information. 683 684[endsect] 685 686[section Class `not_copy_constructible`] 687 688 struct not_copy_constructible:std::logic_error 689 { 690 not_copy_constructible(const std::type_info& info); 691 692 const std::type_info* pinfo; 693 }; 694 695`not_copy_constructible` is thrown when a copy operation is tried that 696involves a non-_CopyConstructible_ type. 697 698`not_copy_constructible(const std::type_info& info);` 699 700[*Effects:] Constructs a `not_copy_constructible` object with the specified 701type information. 702 703[endsect] 704 705[section Class `not_equality_comparable`] 706 707 struct not_equality_comparable:std::logic_error 708 { 709 not_equality_comparable(const std::type_info& info); 710 711 const std::type_info* pinfo; 712 }; 713 714`not_equality_comparable` is thrown when comparing two collections 715for (in)equality involves a non-_EqualityComparable_ type. 716 717`not_equality_comparable(const std::type_info& info);` 718 719[*Effects:] Constructs a `not_equality_comparable` object with the specified 720type information. 721 722[endsect] 723 724[endsect] 725 726[section Header `"boost/poly_collection/base_collection_fwd.hpp"` synopsis] 727 728[def _base_collection_ [link poly_collection.reference.header_boost_poly_collection_ba0.class_template_base_collection `base_collection`]] 729 730 #include <memory> 731 732 namespace boost{ 733 734 namespace poly_collection{ 735 736 template<typename Base,typename Allocator=std::allocator<Base>> 737 class _base_collection_; 738 739 template<typename Base,typename Allocator> 740 bool operator==( 741 const base_collection<Base,Allocator>& x, 742 const base_collection<Base,Allocator>& y); 743 744 template<typename Base,typename Allocator> 745 bool operator!=( 746 const base_collection<Base,Allocator>& x, 747 const base_collection<Base,Allocator>& y); 748 749 template<typename Base,typename Allocator> 750 void swap( 751 base_collection<Base,Allocator>& x,base_collection<Base,Allocator>& y); 752 753 } /* namespace poly_collection */ 754 755 using poly_collection::base_collection; 756 757 } /* namespace boost */ 758 759Forward declares the class template _base_collection_ 760and specifies its default template arguments. Forward declares associated free 761functions and brings `boost::poly_collection::base_collection` to the `boost` 762namespace. 763 764[endsect] 765 766[section Header `"boost/poly_collection/base_collection.hpp"` synopsis] 767 768 #include <boost/poly_collection/base_collection_fwd.hpp> 769 770 namespace boost{ 771 772 namespace poly_collection{ 773 774 template<typename Base,typename Allocator> 775 class _base_collection_; 776 777 template<typename Base,typename Allocator> 778 bool operator==( 779 const base_collection<Base,Allocator>& x, 780 const base_collection<Base,Allocator>& y); 781 782 template<typename Base,typename Allocator> 783 bool operator!=( 784 const base_collection<Base,Allocator>& x, 785 const base_collection<Base,Allocator>& y); 786 787 template<typename Base,typename Allocator> 788 void swap( 789 base_collection<Base,Allocator>& x,base_collection<Base,Allocator>& y); 790 791 } /* namespace poly_collection */ 792 793 } /* namespace boost */ 794 795[section Class template `base_collection`] 796 797`base_collection<Base,Allocator>` is a _PolymorphicCollection_ associated to 798the classic base/derived _polymorphism_model_: 799 800* *Interface* = { `Base` : `std::is_polymorphic_v<Base>` }. 801* *Implementation*(`Base`) = { `Derived` : `std::is_base_of_v<Base,Derived>` }. 802* *subobject*(`x`) = `static_cast<Derived&>(x)` with `typeid(x)==typeid(Derived)`. 803 804[poly_collection_synopsis `base_collection`..`template<typename Base,typename Allocator>`..`Base`] 805 806[endsect] 807 808[endsect] 809 810[section Header `"boost/poly_collection/function_collection_fwd.hpp"` synopsis] 811 812[def _function_collection_ [link poly_collection.reference.header_boost_poly_collection_fu0.class_template_function_collecti `function_collection`]] 813[def _function_collection_value_type_ [link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti `function_collection_value_type`]] 814 815 #include <memory> 816 817 namespace boost{ 818 819 namespace poly_collection{ 820 821 template<typename Signature> 822 using _function_collection_value_type_=``/implementation-defined/``; 823 824 template< 825 typename Signature, 826 typename Allocator=std::allocator<function_collection_value_type<Signature>> 827 > 828 class _function_collection_; 829 830 template<typename Signature,typename Allocator> 831 bool operator==( 832 const function_collection<Signature,Allocator>& x, 833 const function_collection<Signature,Allocator>& y); 834 835 template<typename Signature,typename Allocator> 836 bool operator!=( 837 const function_collection<Signature,Allocator>& x, 838 const function_collection<Signature,Allocator>& y); 839 840 template<typename Signature,typename Allocator> 841 void swap( 842 function_collection<Signature,Allocator>& x, 843 function_collection<Signature,Allocator>& y); 844 845 } /* namespace poly_collection */ 846 847 using poly_collection::function_collection; 848 849 } /* namespace boost */ 850 851Defines the alias template _function_collection_value_type_ (the actual type 852it refers to, though, is merely forward declared). 853Forward declares the class template _function_collection_ 854and specifies its default template arguments. Forward declares associated free 855functions and brings `boost::poly_collection::function_collection` to the 856`boost` namespace. 857 858[endsect] 859 860[section Header `"boost/poly_collection/function_collection.hpp"` synopsis] 861 862 #include <boost/poly_collection/function_collection_fwd.hpp> 863 864 namespace boost{ 865 866 namespace poly_collection{ 867 868 // defines the type ``_function_collection_value_type_`` refers to 869 870 template<typename Signature,typename Allocator> 871 class _function_collection_; 872 873 template<typename Signature,typename Allocator> 874 bool operator==( 875 const function_collection<Signature,Allocator>& x, 876 const function_collection<Signature,Allocator>& y); 877 878 template<typename Signature,typename Allocator> 879 bool operator!=( 880 const function_collection<Signature,Allocator>& x, 881 const function_collection<Signature,Allocator>& y); 882 883 template<typename Signature,typename Allocator> 884 void swap( 885 function_collection<Signature,Allocator>& x, 886 function_collection<Signature,Allocator>& y); 887 888 } /* namespace poly_collection */ 889 890 } /* namespace boost */ 891 892[section Alias template `function_collection_value_type`] 893 894`function_collection_value_type<Signature>` is the `value_type` of 895`boost::function_collection<Signature,Allocator>`, where `Signature` must be a type 896of the form `R(Args...)`. `function_collection_value_type<Signature>` wraps a 897reference to an object modeling _Callable_ for the given `Signature`. The 898interface provided partially replicates that of _std::function_ and adds some 899extra facilities. 900 901In what follows, the name [' `function_collection_value_type_impl`] 902is used just for explanatory purposes in place of the actual 903class template name, which is implementation defined. 904 905 template<typename Signature> 906 using function_collection_value_type= 907 ``/function_collection_value_type_impl/``<Signature>; 908 909 template<typename Signature> 910 class ``/function_collection_value_type_impl/``; 911 912 template<typename R,typename... Args> 913 class ``/function_collection_value_type_impl/``<R(Args...)> 914 { 915 public: 916 explicit ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_bool operator bool]``()const noexcept; 917 918 R ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_call operator()]``(Args... args)const; 919 920 const std::type_info& ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target_type target_type]``()const noexcept; 921 template<typename T> T* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target target]``()noexcept; 922 template<typename T> const T* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target target]``()const noexcept; 923 924 operator ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_std_function std::function<R(Args...)>]``()const noexcept; 925 926 void* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.data data]``()noexcept; 927 const void* ``[link poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.data data]``()const noexcept; 928 }; 929 930[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_bool] 931 932`explicit operator bool()const noexcept;` 933 934[*Returns:] `true`. 935 936[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_call] 937 938`R operator()(Args... args)const;` 939 940[*Effects:] `_INVOKE_(f,std::forward<Args>(args)...,R)`, where f is the wrapped 941callable object.[br] 942[*Returns:] Nothing if `R` is `void`, otherwise the return value of 943`_INVOKE_(f,std::forward<Args>(args)...,R)`. 944 945[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target_type] 946 947`const std::type_info& target_type()const noexcept;` 948 949[*Returns:] `typeid(T)` where `T` is the type of the wrapped callable object. 950 951[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.target] 952 953`template<typename T> T* target()noexcept;`[br] 954`template<typename T> const T* target()const noexcept;` 955 956[*Returns:] If `target_type()==typeid(T)` a pointer to the wrapped callable 957object, otherwise `nullptr`. 958 959[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.operator_std_function] 960 961`operator std::function<R(Args...)>()const noexcept;` 962 963[*Returns:] A `std::function<R(Args...)>` object holding a reference to the 964wrapped callable object. 965 966[#poly_collection.reference.header_boost_poly_collection_fu0.alias_template_function_collecti.data] 967 968`void* data()noexcept;`[br] 969`const void* data()const noexcept;` 970 971[*Returns:] The address of the wrapped callable object. 972 973[endsect] 974 975[section Class template `function_collection`] 976 977`function_collection<Signature,Allocator>` is a _PolymorphicCollection_ associated to 978a dynamic _polymorphism_model_ based on call signature compatibility: 979 980[itemized_list 981 [*Interface* = { `Signature` : `Signature` = `R(Args...)` }.] 982 [*Implementation*(`Signature`) = { `Callable` : `std::is_invocable_r_v<R,Callable,Args...>` }.] 983 [*subobject*(`x`) =[br] 984 `x.target<T>()` with `typeid(T)==x.target_type()`, if `x` is an instantiation of _function_collection_value_type_,[br] 985 `x`, otherwise. 986 ] 987] 988 989[poly_collection_synopsis `function_collection`..`template<typename Signature,typename Allocator>`..`_function_collection_value_type_<Signature>`] 990 991[endsect] 992 993[endsect] 994 995[section Header `"boost/poly_collection/any_collection_fwd.hpp"` synopsis] 996 997[def _any_collection_ [link poly_collection.reference.header_boost_poly_collection_an0.class_template_any_collection `any_collection`]] 998[def _any_collection_value_type_ [link poly_collection.reference.header_boost_poly_collection_an0.alias_template_any_collection_va `any_collection_value_type`]] 999 1000 #include <memory> 1001 1002 namespace boost{ 1003 1004 namespace poly_collection{ 1005 1006 template<typename Concept> 1007 using _any_collection_value_type_=``/implementation-defined/``; 1008 1009 template< 1010 typename Concept, 1011 typename Allocator=std::allocator<any_collection_value_type<Concept>> 1012 > 1013 class _any_collection_; 1014 1015 template<typename Concept,typename Allocator> 1016 bool operator==( 1017 const any_collection<Concept,Allocator>& x, 1018 const any_collection<Concept,Allocator>& y); 1019 1020 template<typename Concept,typename Allocator> 1021 bool operator!=( 1022 const any_collection<Concept,Allocator>& x, 1023 const any_collection<Concept,Allocator>& y); 1024 1025 template<typename Concept,typename Allocator> 1026 void swap( 1027 any_collection<Concept,Allocator>& x,any_collection<Concept,Allocator>& y); 1028 1029 } /* namespace poly_collection */ 1030 1031 using poly_collection::any_collection; 1032 1033 } /* namespace boost */ 1034 1035Defines the alias template _any_collection_value_type_ (the actual type 1036it refers to, though, is merely forward declared). 1037Forward declares the class template _any_collection_ 1038and specifies its default template arguments. Forward declares associated free 1039functions and brings `boost::poly_collection::any_collection` to the 1040`boost` namespace. 1041 1042[endsect] 1043 1044[section Header `"boost/poly_collection/any_collection.hpp"` synopsis] 1045 1046 #include <boost/poly_collection/any_collection_fwd.hpp> 1047 1048 namespace boost{ 1049 1050 namespace poly_collection{ 1051 1052 // defines the type ``_any_collection_value_type_`` refers to 1053 1054 template<typename Concept,typename Allocator> 1055 class _any_collection_; 1056 1057 template<typename Concept,typename Allocator> 1058 bool operator==( 1059 const any_collection<Concept,Allocator>& x, 1060 const any_collection<Concept,Allocator>& y); 1061 1062 template<typename Concept,typename Allocator> 1063 bool operator!=( 1064 const any_collection<Concept,Allocator>& x, 1065 const any_collection<Concept,Allocator>& y); 1066 1067 template<typename Concept,typename Allocator> 1068 void swap( 1069 any_collection<Concept,Allocator>& x,any_collection<Concept,Allocator>& y); 1070 1071 } /* namespace poly_collection */ 1072 1073 } /* namespace boost */ 1074 1075[section Alias template `any_collection_value_type`] 1076 1077`any_collection_value_type<Concept>` is the `value_type` of 1078`boost::any_collection<Concept,Allocator>`, where `Concept` is defined according to 1079the [@boost:/doc/html/boost_typeerasure/conceptdef.html requisites] 1080of _Boost.TypeErasure_ using 1081[@boost:/doc/html/boost/type_erasure/_self.html `_self`] 1082as its [@boost:/doc/html/boost/type_erasure/placeholder.html placeholder]. 1083The alias template definition has the form 1084 1085 template<typename Concept> 1086 using any_collection_value_type= 1087 boost::type_erasure::``[@boost:/doc/html/boost/type_erasure/any.html any]``<Concept2,boost::type_erasure::_self&>; 1088 1089with `boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/is_subconcept.html `is_subconcept`]`<Concept,Concept2>::value==true`. 1090The exact definition of `Concept2` is implementation defined. 1091 1092[endsect] 1093 1094[section Class template `any_collection`] 1095 1096`any_collection<Concept,Allocator>` is a _PolymorphicCollection_ associated to 1097a dynamic _polymorphism_model_ based on _duck_typing_ as implemented by 1098_Boost.TypeErasure_: 1099 1100[itemized_list 1101 [*Interface* = { `Concept` : 1102 as [@boost:/doc/html/boost_typeerasure/conceptdef.html specified] by _Boost.TypeErasure_, 1103 using the [@boost:/doc/html/boost/type_erasure/_self.html `_self`] 1104 [@boost:/doc/html/boost/type_erasure/placeholder.html placeholder] }.] 1105 [*Implementation*(`Concept`) = { `Concrete` : `Concrete` satisfies `Concept` }.] 1106 [*subobject*(`x`) =[br] 1107 `boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/any_cast.html `any_cast`]`<T&>(x)` 1108 with `typeid(T)==boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/typeid_of.html `typeid_of`]`(x)`, 1109 if `x` is an instantiation of `boost::type_erasure::`[@boost:/doc/html/boost/type_erasure/any.html `any`] 1110 including [@boost:/doc/html/boost/type_erasure/typeid_.html `typeid_`]`<>`,[br] 1111 `x`, otherwise. 1112 ] 1113] 1114 1115[poly_collection_synopsis `any_collection`..`template<typename Concept,typename Allocator>`..`_any_collection_value_type_<Concept>`] 1116 1117[endsect] 1118 1119[endsect] 1120 1121[section Header `"boost/poly_collection/algorithm.hpp"` synopsis] 1122 1123 namespace boost{ 1124 1125 namespace poly_collection{ 1126 1127 ``['`// non-modifying sequence operations:`]`` 1128 1129 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1130 bool all_of( 1131 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1132 1133 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1134 bool any_of( 1135 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1136 1137 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1138 bool none_of( 1139 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1140 1141 template<typename... Ts,typename PolyCollectionIterator,typename Function> 1142 Function for_each( 1143 PolyCollectionIterator first,PolyCollectionIterator last,Function f); 1144 1145 template< 1146 typename... Ts,typename PolyCollectionIterator, 1147 typename Size,typename Function 1148 > 1149 Iterator for_each_n( 1150 PolyCollectionIterator first,Size n,Function f); 1151 1152 template<typename... Ts,typename PolyCollectionIterator,typename T> 1153 PolyCollectionIterator find( 1154 PolyCollectionIterator first,PolyCollectionIterator last,const T& x); 1155 1156 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1157 PolyCollectionIterator find_if( 1158 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1159 1160 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1161 PolyCollectionIterator find_if_not( 1162 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1163 1164 template< 1165 typename... Ts,typename PolyCollectionIterator,typename ForwardIterator 1166 > 1167 PolyCollectionIterator find_end( 1168 PolyCollectionIterator first1,PolyCollectionIterator last1, 1169 ForwardIterator first2,ForwardIterator last2); 1170 1171 template< 1172 typename... Ts,typename PolyCollectionIterator, 1173 typename ForwardIterator,typename BinaryPredicate 1174 > 1175 PolyCollectionIterator find_end( 1176 PolyCollectionIterator first1,PolyCollectionIterator last1, 1177 ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred); 1178 1179 template< 1180 typename... Ts,typename PolyCollectionIterator,typename ForwardIterator 1181 > 1182 PolyCollectionIterator find_first_of( 1183 PolyCollectionIterator first1,PolyCollectionIterator last1, 1184 ForwardIterator first2,ForwardIterator last2); 1185 1186 template< 1187 typename... Ts,typename PolyCollectionIterator, 1188 typename ForwardIterator,typename BinaryPredicate 1189 > 1190 PolyCollectionIterator find_first_of( 1191 PolyCollectionIterator first1,PolyCollectionIterator last1, 1192 ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred); 1193 1194 template<typename... Ts,typename PolyCollectionIterator> 1195 PolyCollectionIterator adjacent_find( 1196 PolyCollectionIterator first,PolyCollectionIterator last); 1197 1198 template< 1199 typename... Ts,typename PolyCollectionIterator,typename BinaryPredicate 1200 > 1201 PolyCollectionIterator adjacent_find( 1202 PolyCollectionIterator first,PolyCollectionIterator last, 1203 BinaryPredicate pred); 1204 1205 template<typename... Ts,typename PolyCollectionIterator,typename T> 1206 std::ptrdiff_t count( 1207 PolyCollectionIterator first,PolyCollectionIterator last,const T& x); 1208 1209 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1210 std::ptrdiff_t count_if( 1211 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1212 1213 template< 1214 typename... Ts,typename PolyCollectionIterator,typename InputIterator 1215 > 1216 std::pair<PolyCollectionIterator,InputIterator> mismatch( 1217 PolyCollectionIterator first1,PolyCollectionIterator last1, 1218 InputIterator first2); 1219 1220 template< 1221 typename... Ts,typename PolyCollectionIterator, 1222 typename InputIterator,typename BinaryPredicate 1223 > 1224 std::pair<PolyCollectionIterator,InputIterator> mismatch( 1225 PolyCollectionIterator first1,PolyCollectionIterator last1, 1226 InputIterator first2,BinaryPredicate pred); 1227 1228 template< 1229 typename... Ts,typename PolyCollectionIterator,typename InputIterator 1230 > 1231 std::pair<PolyCollectionIterator,InputIterator> mismatch( 1232 PolyCollectionIterator first1,PolyCollectionIterator last1, 1233 InputIterator first2,InputIterator last2); 1234 1235 template< 1236 typename... Ts,typename PolyCollectionIterator, 1237 typename InputIterator,typename BinaryPredicate 1238 > 1239 std::pair<PolyCollectionIterator,InputIterator> mismatch( 1240 PolyCollectionIterator first1,PolyCollectionIterator last1, 1241 InputIterator first2,InputIterator last2,BinaryPredicate pred); 1242 1243 template< 1244 typename... Ts,typename PolyCollectionIterator,typename InputIterator 1245 > 1246 bool equal( 1247 PolyCollectionIterator first1,PolyCollectionIterator last1, 1248 InputIterator first2); 1249 1250 template< 1251 typename... Ts,typename PolyCollectionIterator, 1252 typename InputIterator,typename BinaryPredicate 1253 > 1254 bool equal( 1255 PolyCollectionIterator first1,PolyCollectionIterator last1, 1256 InputIterator first2,BinaryPredicate pred); 1257 1258 template< 1259 typename... Ts,typename PolyCollectionIterator,typename InputIterator 1260 > 1261 bool equal( 1262 PolyCollectionIterator first1,PolyCollectionIterator last1, 1263 InputIterator first2,InputIterator last2); 1264 1265 template< 1266 typename... Ts,typename PolyCollectionIterator, 1267 typename InputIterator,typename BinaryPredicate 1268 > 1269 bool equal( 1270 PolyCollectionIterator first1,PolyCollectionIterator last1, 1271 InputIterator first2,InputIterator last2,BinaryPredicate pred); 1272 1273 template< 1274 typename... Ts,typename PolyCollectionIterator,typename ForwardIterator 1275 > 1276 bool is_permutation( 1277 PolyCollectionIterator first1,PolyCollectionIterator last1, 1278 ForwardIterator first2); 1279 1280 template< 1281 typename... Ts,typename PolyCollectionIterator, 1282 typename ForwardIterator,typename BinaryPredicate 1283 > 1284 bool is_permutation( 1285 PolyCollectionIterator first1,PolyCollectionIterator last1, 1286 ForwardIterator first2,BinaryPredicate pred); 1287 1288 template< 1289 typename... Ts,typename PolyCollectionIterator,typename ForwardIterator 1290 > 1291 bool is_permutation( 1292 PolyCollectionIterator first1,PolyCollectionIterator last1, 1293 ForwardIterator first2,ForwardIterator last2); 1294 1295 template< 1296 typename... Ts,typename PolyCollectionIterator, 1297 typename ForwardIterator,typename BinaryPredicate 1298 > 1299 bool is_permutation( 1300 PolyCollectionIterator first1,PolyCollectionIterator last1, 1301 ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred); 1302 1303 template< 1304 typename... Ts,typename PolyCollectionIterator,typename ForwardIterator 1305 > 1306 PolyCollectionIterator search( 1307 PolyCollectionIterator first1,PolyCollectionIterator last1, 1308 ForwardIterator first2,ForwardIterator last2); 1309 1310 template< 1311 typename... Ts,typename PolyCollectionIterator, 1312 typename ForwardIterator,typename BinaryPredicate 1313 > 1314 PolyCollectionIterator search( 1315 PolyCollectionIterator first1,PolyCollectionIterator last1, 1316 ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred); 1317 1318 template< 1319 typename... Ts,typename PolyCollectionIterator,typename Size,typename T 1320 > 1321 PolyCollectionIterator search_n( 1322 PolyCollectionIterator first1,PolyCollectionIterator last1, 1323 Size count,const T& x); 1324 1325 template< 1326 typename... Ts,typename PolyCollectionIterator, 1327 typename Size,typename T,typename BinaryPredicate 1328 > 1329 PolyCollectionIterator search_n( 1330 PolyCollectionIterator first1,PolyCollectionIterator last1, 1331 Size count,const T& x,BinaryPredicate pred); 1332 1333 ``['`// modifying sequence operations:`]`` 1334 1335 template< 1336 typename... Ts,typename PolyCollectionIterator,typename OutputIterator 1337 > 1338 OutputIterator copy( 1339 PolyCollectionIterator first,PolyCollectionIterator last, 1340 OutputIterator res); 1341 1342 template< 1343 typename... Ts,typename PolyCollectionIterator, 1344 typename Size,typename OutputIterator 1345 > 1346 OutputIterator copy_n( 1347 PolyCollectionIterator first,Size count,OutputIterator res); 1348 1349 template< 1350 typename... Ts,typename PolyCollectionIterator, 1351 typename OutputIterator,typename Predicate 1352 > 1353 OutputIterator copy_if( 1354 PolyCollectionIterator first,PolyCollectionIterator last, 1355 OutputIterator res,Predicate pred); 1356 1357 template< 1358 typename... Ts,typename PolyCollectionIterator,typename OutputIterator 1359 > 1360 OutputIterator move( 1361 PolyCollectionIterator first,PolyCollectionIterator last, 1362 OutputIterator res); 1363 1364 template< 1365 typename... Ts,typename PolyCollectionIterator, 1366 typename OutputIterator,typename UnaryOperation 1367 > 1368 OutputIterator transform( 1369 PolyCollectionIterator first,PolyCollectionIterator last, 1370 OutputIterator res,UnaryOperation op); 1371 1372 template< 1373 typename... Ts,typename PolyCollectionIterator, 1374 typename InputIterator,typename OutputIterator,typename BinaryOperation 1375 > 1376 OutputIterator transform( 1377 PolyCollectionIterator first1,PolyCollectionIterator last1, 1378 InputIterator first2,OutputIterator res,BinaryOperation op); 1379 1380 template< 1381 typename... Ts,typename PolyCollectionIterator, 1382 typename OutputIterator,typename T 1383 > 1384 OutputIterator replace_copy( 1385 PolyCollectionIterator first,PolyCollectionIterator last, 1386 OutputIterator res,const T& old_x,const T& new_x); 1387 1388 template< 1389 typename... Ts,typename PolyCollectionIterator, 1390 typename OutputIterator,typename Predicate,typename T 1391 > 1392 OutputIterator replace_copy_if( 1393 PolyCollectionIterator first,PolyCollectionIterator last, 1394 OutputIterator res,Predicate pred,const T& new_x); 1395 1396 template< 1397 typename... Ts,typename PolyCollectionIterator, 1398 typename OutputIterator,typename T 1399 > 1400 OutputIterator remove_copy( 1401 PolyCollectionIterator first,PolyCollectionIterator last, 1402 OutputIterator res,const T& x); 1403 1404 template< 1405 typename... Ts,typename PolyCollectionIterator, 1406 typename OutputIterator,typename Predicate 1407 > 1408 OutputIterator remove_copy_if( 1409 PolyCollectionIterator first,PolyCollectionIterator last, 1410 OutputIterator res,Predicate pred); 1411 1412 template< 1413 typename... Ts,typename PolyCollectionIterator,typename OutputIterator 1414 > 1415 OutputIterator unique_copy( 1416 PolyCollectionIterator first,PolyCollectionIterator last, 1417 OutputIterator res); 1418 1419 template< 1420 typename... Ts,typename PolyCollectionIterator, 1421 typename OutputIterator,typename BinaryPredicate 1422 > 1423 OutputIterator unique_copy( 1424 PolyCollectionIterator first,PolyCollectionIterator last, 1425 OutputIterator res,BinaryPredicate pred); 1426 1427 template< 1428 typename... Ts,typename PolyCollectionIterator,typename OutputIterator 1429 > 1430 OutputIterator rotate_copy( 1431 PolyCollectionIterator first,PolyCollectionIterator middle, 1432 PolyCollectionIterator last,OutputIterator res); 1433 1434 template< 1435 typename... Ts,typename PolyCollectionIterator,typename OutputIterator, 1436 typename Distance,typename UniformRandomBitGenerator 1437 > 1438 OutputIterator sample( 1439 PolyCollectionIterator first,PolyCollectionIterator last, 1440 OutputIterator res,Distance n,UniformRandomBitGenerator&& g); 1441 1442 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1443 bool is_partitioned( 1444 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1445 1446 template< 1447 typename... Ts,typename PolyCollectionIterator, 1448 typename OutputIterator1,typename OutputIterator2,typename Predicate 1449 > 1450 std::pair<OutputIterator1,OutputIterator2> partition_copy( 1451 PolyCollectionIterator first,PolyCollectionIterator last, 1452 OutputIterator1 rest,OutputIterator2 resf,Predicate pred); 1453 1454 template<typename... Ts,typename PolyCollectionIterator,typename Predicate> 1455 PolyCollectionIterator partition_point( 1456 PolyCollectionIterator first,PolyCollectionIterator last,Predicate pred); 1457 1458 } /* namespace poly_collection */ 1459 1460 } /* namespace boost */ 1461 1462The algorithms provided mimic the functionality of their homonyms in 1463[@http://en.cppreference.com/w/cpp/algorithm `<algorithm>`] but take advantage 1464of the segmented nature of Boost.PolyCollection (global) iterators to 1465deliver better performance. Additionally, concrete types can be passed to 1466these algorithms for /type restitution/. 1467 1468For the description of the algorithms we use the following notation: 1469 1470* [' `alg`] is the (unqualified) name of any of the algorithms in 1471`"boost/poly_collection/algorithm.hpp"` except `copy_n` and `rotate_copy`. 1472* `first`, `middle` and `last` are (same-typed) possibly const global iterators 1473of a collection of Boost.PolyCollection such that \[`first`, `middle`) and 1474\[`middle`, `last`) are valid ranges. 1475* `args...` is a function parameter pack of types `Args&&...`, 1476* `Ts...` is a template parameter pack of arbitrary types. 1477 1478(1) [' `alg`]`(first,last,args...)`[br] 1479(2) `for_each_n(first,args...)`[br] 1480(3) `copy_n(first,args...)`[br] 1481(4) `rotate_copy(first,middle,last,args...)` 1482 1483[*Requires:] The expression `expr` is well-formed, where `expr` is defined 1484as:[br] 1485(1) `std::`[' `alg`]`(first,last,args...)`,[br] 1486(2) `std::for_each_n(first,args...)`,[br] 1487(3) `std::copy_n(first,args...)`,[br] 1488(4) `std::rotate_copy(first,middle,last,args...)`.[br] 1489[*Effects:] Equivalent to `expr`.[br] 1490[*Returns:] `expr`.[br] 1491[*Complexity:] That of `expr`. 1492 1493(1) [' `alg`]`<Ts...>(first,last,args...)`[br] 1494(2) `for_each_n<Ts...>(first,args...)`[br] 1495(3) `copy_n<Ts...>(first,args...)`[br] 1496(4) `rotate_copy<Ts...>(first,middle,last,args...)` 1497 1498[*Requires:] The expression `expr` is well-formed, where `expr` is defined 1499as:[br] 1500(1) `std::`[' `alg`]`(rfirst,rlast,args...)`,[br] 1501(2) `std::for_each_n(rfirst,args...)`,[br] 1502(3) `std::copy_n(rfirst,args...)`,[br] 1503(4) `std::rotate_copy(rfirst,rmiddle,rlast,args...)`,[br] 1504and `rfirst`, `rmiddle` and `rlast` are iterator-like objects behaving like 1505their `first`, `middle` and `last` counterparts except that they 1506dereference to the corresponding subobject (`const`) `T&` if pointing to a 1507segment for `T` and `T` is in `Ts...` 1508[footnote Strictly speaking a proper _ForwardIterator_ cannot behave 1509like this as dereferencing must yield /exactly/ a (`const`) `value_type&` 1510value, which disallows this type of polymorphism.].[br] 1511[*Effects:] Equivalent to `expr`.[br] 1512[*Returns:] `expr`.[br] 1513[*Complexity:] That of `expr`. 1514 1515[endsect] 1516 1517[endsect]