ceph/src/boost/libs/bimap/doc/reference/list_of.qbk

   1 [/license
   2
   3 Boost.Bimap
   4
   5 Copyright (c) 2006-2007 Matias Capeletto
   6
   7 Distributed under the Boost Software License, Version 1.0.
   8 (See accompanying file LICENSE_1_0.txt or copy at
   9 http://www.boost.org/LICENSE_1_0.txt)
  10
  11 ]
  12
  13 [/ QuickBook Document version 1.4 ]
  14
  15 [section list_of Reference]
  16
  17 [section Header "boost/bimap/list_of.hpp" synopsis]
  18
  19     namespace boost {
  20     namespace bimaps {
  21
  22
  23     template< class KeyType >
  24     struct list_of;
  25
  26     struct list_of_relation;
  27
  28
  29     } // namespace bimap
  30     } // namespace boost
  31
  32 [endsect]
  33
  34 [section list_of Views]
  35
  36 A list_of set view is a std::list signature compatible
  37 interface to the underlying heap of elements contained in a `bimap`.
  38
  39 If you look the bimap by a side, you will use a map view and if you looked
  40 it as a whole you will be using a set view.
  41
  42 Elements in a list_of view are by default sorted according to
  43 their order of insertion: this means that new elements inserted through a
  44 different view of the `bimap` are appended to the end of the
  45 list_of view. Additionally, the view allows for free reordering of elements
  46 in the same vein as `std::list` does. Validity of iterators and references to
  47 elements is preserved in all operations.
  48
  49 There are a number of differences with respect to `std::lists`:
  50
  51 * list_of views are not
  52 __SGI_ASSIGNABLE__ (like any other view.)
  53 * Unlike as in `std::list`, insertions into a list_of view may fail due to
  54 clashings with other views. This alters the semantics of the operations
  55 provided with respect to their analogues in `std::list`.
  56 * Elements in a list_of view are not mutable, and can only be changed
  57 by means of `replace` and `modify` member functions.
  58
  59 Having these restrictions into account, list_of views are models of
  60 __SGI_REVERSIBLE_CONTAINER__, __SGI_FRONT_INSERTION_SEQUENCE__ and
  61 __SGI_BACK_INSERTION_SEQUENCE__.
  62 We only provide descriptions of those types and operations that are either
  63 not present in the concepts modeled or do not exactly conform to the
  64 requirements for these types of containers.
  65
  66     namespace boost {
  67     namespace bimaps {
  68     namespace views {
  69
  70     template< ``['-implementation defined parameter list-]`` >
  71     class ``['-implementation defined view name-]``
  72     {
  73         public:
  74
  75         // types
  76
  77         typedef ``['-unspecified-]`` value_type;
  78         typedef ``['-unspecified-]`` allocator_type;
  79         typedef ``['-unspecified-]`` reference;
  80         typedef ``['-unspecified-]`` const_reference;
  81         typedef ``['-unspecified-]`` iterator;
  82         typedef ``['-unspecified-]`` const_iterator;
  83         typedef ``['-unspecified-]`` size_type;
  84         typedef ``['-unspecified-]`` difference_type;
  85         typedef ``['-unspecified-]`` pointer;
  86         typedef ``['-unspecified-]`` const_pointer;
  87         typedef ``['-unspecified-]`` reverse_iterator;
  88         typedef ``['-unspecified-]`` const_reverse_iterator;
  89
  90         typedef ``['-unspecified-]`` info_type;
  91
  92         // construct/copy/destroy
  93
  94         this_type & operator=(const this_type & x);
  95
  96         template< class InputIterator >
  97         void ``[link reference_list_of_assign_iterator_iterator assign]``(InputIterator first, InputIterator last);
  98
  99         void ``[link reference_list_of_assign_size_value assign]``(size_type n, const value_type & value);
 100
 101         allocator_type get_allocator() const;
 102
 103         // iterators
 104
 105         iterator               begin();
 106         const_iterator         begin() const;
 107
 108         iterator               end();
 109         const_iterator         end() const;
 110
 111         reverse_iterator       rbegin();
 112         const_reverse_iterator rbegin() const;
 113
 114         reverse_iterator       rend();
 115         const_reverse_iterator rend() const;
 116
 117         // capacity
 118
 119         bool      empty() const;
 120
 121         size_type size() const;
 122
 123         size_type max_size() const;
 124
 125         void ``[link reference_list_of_resize_size_value resize]``(size_type n, const value_type & x = value_type());
 126
 127         // access
 128
 129         const_reference front() const;
 130         const_reference back() const;
 131
 132         // modifiers
 133
 134         std::pair<iterator,bool> ``[link reference_list_of_push_front_value push_front]``(const value_type & x);
 135         void                     pop_front();
 136
 137         std::pair<iterator,bool> ``[link reference_list_of_push_back_value push_back]``(const value_type & x);
 138         void                     pop_back();
 139
 140         std::pair<iterator,bool> ``[link reference_list_of_insert_iterator_value insert]``(iterator position, const value_type & x);
 141
 142         void ``[link reference_list_of_insert_iterator_size_value insert]``(iterator position, size_type n, const value_type & x);
 143
 144         template< class InputIterator >
 145         void ``[link reference_list_of_insert_iterator_iterator_iterator insert]``(iterator position, InputIterator first, InputIterator last);
 146
 147         iterator ``[link reference_list_of_erase_iterator erase]``(iterator position);
 148         iterator ``[link reference_list_of_erase_iterator_iterator erase]``(iterator first, iterator last);
 149
 150         bool ``[link reference_list_of_replace_iterator_value replace]``(iterator position, const value_type & x);
 151
 152         // Only in map views
 153         // {
 154
 155           typedef ``['-unspecified-]`` key_type;
 156           typedef ``['-unspecified-]`` mapped_type;
 157           typedef ``['-unspecified-]`` mapped_type; // Equal to mapped_type
 158
 159           template< class CompatibleKey >
 160           bool ``[link reference_list_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x);
 161
 162           template< class CompatibleData >
 163           bool ``[link reference_list_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x);
 164
 165           template< class KeyModifier >
 166           bool ``[link reference_list_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod);
 167
 168           template< class DataModifier >
 169           bool ``[link reference_list_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod);
 170
 171         // }
 172
 173
 174         void clear();
 175
 176         // list operations
 177
 178         void ``[link reference_list_of_splice_iterator_this splice]``(iterator position, this_type & x);
 179         void ``[link reference_list_of_splice_iterator_this_iterator splice]``(iterator position, this_type & x, iterator i);
 180         void splice(
 181             iterator position, this_type & x, iterator first, iterator last);
 182
 183         void ``[link reference_list_of_remove_value remove]``(const value_type & value);
 184
 185         template< class Predicate >
 186         void ``[link reference_list_of_remove_if_predicate remove_if]``(Predicate pred);
 187
 188         void ``[link reference_list_of_unique unique]``();
 189
 190         template< class BinaryPredicate >
 191         void ``[link reference_list_of_unique_predicate unique]``(BinaryPredicate binary_pred);
 192
 193         void ``[link reference_list_of_merge_this merge]``(this_type & x);
 194
 195         template< class Compare >
 196         void ``[link reference_list_of_merge_this_compare merge]``(this_type & x,Compare comp);
 197
 198         void ``[link reference_list_of_sort sort]``();
 199
 200         template< class Compare >
 201         void ``[link reference_list_of_sort_compare sort]``(Compare comp);
 202
 203         void ``[link reference_list_of_reverse reverse]``();
 204
 205         // rearrange operations
 206
 207         void relocate(iterator position, iterator i);
 208         void relocate(iterator position, iterator first, iterator last);
 209
 210     }
 211
 212     // view comparison
 213
 214     bool operator==(const this_type & v1, const this_type & v2 );
 215     bool operator< (const this_type & v1, const this_type & v2 );
 216     bool operator!=(const this_type & v1, const this_type & v2 );
 217     bool operator> (const this_type & v1, const this_type & v2 );
 218     bool operator>=(const this_type & v1, const this_type & v2 );
 219     bool operator<=(const this_type & v1, const this_type & v2 );
 220
 221     } // namespace views
 222     } // namespace bimap
 223     } // namespace boost
 224
 225 In the case of a `bimap< list_of<Left>, ... >`
 226
 227 In the set view:
 228
 229     typedef signature-compatible with relation< Left, ... > key_type;
 230     typedef signature-compatible with relation< Left, ... > value_type;
 231
 232 In the left map view:
 233
 234     typedef  Left  key_type;
 235     typedef  ...   mapped_type;
 236
 237     typedef signature-compatible with std::pair< Left, ... > value_type;
 238
 239 In the right map view:
 240
 241     typedef  ...  key_type;
 242     typedef  Left mapped_type;
 243
 244     typedef signature-compatible with std::pair< ... , Left > value_type;
 245
 246
 247 [#list_of_complexity_signature]
 248
 249 [section Complexity signature]
 250
 251 Here and in the descriptions of operations of `list_of` views, we adopt the
 252 scheme outlined in the
 253 [link complexity_signature_explanation complexity signature section].
 254 The complexity signature of a `list_of` view is:
 255
 256 * copying: `c(n) = n * log(n)`,
 257 * insertion: `i(n) = 1` (constant),
 258 * hinted insertion: `h(n) = 1` (constant),
 259 * deletion: `d(n) = 1` (constant),
 260 * replacement: `r(n) = 1` (constant),
 261 * modifying: `m(n) = 1` (constant).
 262
 263 [endsect]
 264
 265 [section Instantiation types]
 266
 267 `list_of` views are instantiated internally to `bimap` and specified
 268 by means of the collection type specifiers and the bimap itself.
 269 Instantiations are dependent on the following types:
 270
 271 * `Value` from `list_of`,
 272 * `Allocator` from `bimap`,
 273
 274 [endsect]
 275
 276 [section Constructors, copy and assignment]
 277
 278 As explained in the view concepts section, views do not have public
 279 constructors or destructors. Assignment, on the other hand, is provided.
 280
 281     this_type & operator=(const this_type & x);
 282
 283 * [*Effects: ] `a = b;`
 284 where a and b are the `bimap` objects to which `*this` and `x` belong,
 285 respectively.
 286 * [*Returns: ] `*this`.
 287
 288
 289 [#reference_list_of_assign_iterator_iterator]
 290
 291     template< class InputIterator >
 292     void assign(InputIterator first, InputIterator last);
 293
 294 * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements of type
 295 `value_type` or a type convertible to `value_type`. first and last are not
 296 iterators into any views of the `bimap` to which this view belongs.
 297 `last` is reachable from `first`.
 298 * [*Effects: ] `clear(); insert(end(),first,last);`
 299
 300
 301 [#reference_list_of_assign_size_value]
 302
 303     void assign(size_type n, const value_type & value);
 304
 305 * [*Effects: ] `clear(); for(size_type i = 0; i < n ; ++n) push_back(v);`
 306
 307
 308 [endsect]
 309
 310 [section Capacity operations]
 311
 312 [#reference_list_of_resize_size_value]
 313
 314     void resize(size_type n,const value_type& x=value_type());
 315
 316 * [*Effects: ]
 317 `if( n > size() ) insert(end(), n - size(), x);`
 318 `else if( n < size() ) {`
 319 `    iterator it = begin();`
 320 `    std::advance(it, n);`
 321 `    erase(it, end());`
 322 `}`
 323 * [*Note:] If an expansion is requested, the size of the view is not
 324 guaranteed to be n after this operation (other views may ban insertions.)
 325
 326 [endsect]
 327
 328 [section Modifiers]
 329
 330 [#reference_list_of_push_front_value]
 331
 332     std::pair<iterator,bool> push_front(const value_type& x);
 333
 334 * [*Effects:] Inserts `x` at the beginning of the sequence if no other views
 335 of the `bimap` bans the insertion.
 336 * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only
 337 if insertion took place. On successful insertion, `p.first` points to the element
 338 inserted; otherwise, `p.first` points to an element that caused the insertion to be
 339 banned. Note that more than one element can be causing insertion not to be allowed.
 340 * [link list_of_complexity_signature [*Complexity:]] O(I(n)).
 341 * [*Exception safety:] Strong.
 342
 343
 344 [#reference_list_of_push_back_value]
 345
 346     std::pair<iterator,bool> push_back(const value_type & x);
 347
 348 * [*Effects:] Inserts `x` at the end of the sequence if no other views of the
 349 `bimap` bans the insertion.
 350 * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if
 351 insertion took place. On successful insertion, `p.first` points to the element
 352 inserted; otherwise, `p.first` points to an element that caused the insertion
 353 to be banned. Note that more than one element can be causing insertion not
 354 to be allowed.
 355 * [link list_of_complexity_signature [*Complexity:]] O(I(n)).
 356 * [*Exception safety:] Strong.
 357
 358
 359 [#reference_list_of_insert_iterator_value]
 360
 361     std::pair<iterator,bool> insert(iterator position, const value_type & x);
 362
 363 * [*Requires: ] `position` is a valid `iterator` of the view.
 364 * [*Effects:] Inserts `x` before position if insertion is allowed by all other
 365 views of the `bimap`.
 366 * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if
 367 insertion took place. On successful insertion, `p.first` points to the element
 368 inserted; otherwise, `p.first` points to an element that caused the insertion
 369 to be banned. Note that more than one element can be causing insertion not
 370 to be allowed.
 371 * [link list_of_complexity_signature
 372 [*Complexity:]] O(I(n)).
 373 * [*Exception safety:] Strong.
 374
 375
 376 [#reference_list_of_insert_iterator_size_value]
 377
 378     void insert(iterator position, size_type n, const value_type & x);
 379
 380 * [*Requires: ] `position` is a valid `iterator` of the view.
 381 * [*Effects: ] `for(size_type i = 0; i < n; ++i) insert(position, x);`
 382
 383
 384 [#reference_list_of_insert_iterator_iterator_iterator]
 385
 386     template< class InputIterator>
 387     void insert(iterator position,InputIterator first,InputIterator last);
 388
 389 * [*Requires: ] `position` is a valid `iterator` of the view. `InputIterator` is
 390 a model of __SGI_INPUT_ITERATOR__ over elements of type `value_type`.
 391 `first` and `last` are not iterators into any view of the
 392 `bimap` to which this view belongs. `last` is reachable from `first`.
 393 * [*Effects: ] `while(first != last) insert(position, *first++);`
 394 * [link list_of_complexity_signature
 395 [*Complexity:]] O(m*I(n+m)), where m is the number of elements in `[first,last)`.
 396 * [*Exception safety:] Basic.
 397
 398
 399 [#reference_list_of_erase_iterator]
 400
 401     iterator erase(iterator position);
 402
 403 * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view.
 404 * [*Effects:] Deletes the element pointed to by `position`.
 405 * [*Returns:] An iterator pointing to the element immediately following the
 406 one that was deleted, or `end()` if no such element exists.
 407 * [link list_of_complexity_signature
 408 [*Complexity:]] O(D(n)).
 409 * [*Exception safety:] nothrow.
 410
 411
 412 [#reference_list_of_erase_iterator_iterator]
 413
 414     iterator erase(iterator first, iterator last);
 415
 416 * [*Requires: ] `[first,last)` is a valid range of the view.
 417 * [*Effects:] Deletes the elements in `[first,last)`.
 418 * [*Returns: ] `last`.
 419 * [link list_of_complexity_signature
 420 [*Complexity:]] O(m*D(n)), where m is the number of elements in `[first,last)`.
 421 * [*Exception safety:] nothrow.
 422
 423
 424 [#reference_list_of_replace_iterator_value]
 425
 426     bool replace(iterator position,const value_type& x);
 427
 428 * [*Requires: ] `position` is a valid dereferenceable iterator of the view.
 429 * [*Effects:] Assigns the value `x` to the element pointed to by `position` into
 430 the `bimap` to which the view belongs if replacing is allowed by
 431 all other views of the `bimap`.
 432 * [*Postconditions:] Validity of `position` is preserved in all cases.
 433 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 434 * [link list_of_complexity_signature
 435 [*Complexity:]] O(R(n)).
 436 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 437 operation the `bimap` to which the view belongs remains in its
 438 original state.
 439
 440
 441 [#reference_list_of_replace_key_iterator_key]
 442
 443     template< class CompatibleKey >
 444     bool replace_key(iterator position, const CompatibleKey & x);
 445
 446 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 447 `CompatibleKey` can be assigned to `key_type`.
 448 * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed
 449 to by `position` into the `bimap` to which the set view belongs if replacing is allowed by
 450 all other views of the `bimap`.
 451 * [*Postconditions:] Validity of position is preserved in all cases.
 452 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 453 * [link list_of_complexity_signature
 454 [*Complexity:]] O(R(n)).
 455 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 456 operation, the `bimap` to which the set view belongs remains in
 457 its original state.
 458
 459
 460 [#reference_list_of_replace_data_iterator_data]
 461
 462     template< class CompatibleData >
 463     bool replace_data(iterator position, const CompatibleData & x);
 464
 465 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 466 `CompatibleKey` can be assigned to `mapped_type`.
 467 * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed
 468 to by `position` into the `bimap` to which the set view belongs if replacing is allowed by
 469 all other views of the `bimap`.
 470 * [*Postconditions:] Validity of position is preserved in all cases.
 471 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 472 * [link list_of_complexity_signature
 473 [*Complexity:]] O(R(n)).
 474 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 475 operation, the `bimap` to which the set view belongs remains in
 476 its original state.
 477
 478
 479 [#reference_list_of_modify_key_iterator_modifier]
 480
 481     template< class KeyModifier >
 482     bool modify_key(iterator position, KeyModifier mod);
 483
 484 * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
 485 type: `key_type&`; `position` is a valid dereferenceable iterator of the view.
 486 * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and
 487 rearranges `*position` into all the views of the `bimap`.
 488 If the rearrangement fails, the element is erased.
 489 It is successful if the rearrangement is allowed by all other views of the `bimap`.
 490 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 491 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 492 * [link list_of_complexity_signature
 493 [*Complexity:]] O(M(n)).
 494 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 495 operation (except possibly mod), then the element pointed to by position is erased.
 496 * [*Note:] Only provided for map views.
 497
 498
 499 [#reference_list_of_modify_data_iterator_modifier]
 500
 501     template< class DataModifier >
 502     bool modify_data(iterator position, DataModifier mod);
 503
 504 * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
 505 type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view.
 506 * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and
 507 rearranges `*position` into all the views of the `bimap`.
 508 If the rearrangement fails, the element is erased.
 509 It is successful if the rearrangement is allowed by all other views of the `bimap`.
 510 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 511 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 512 * [link list_of_complexity_signature
 513 [*Complexity:]] O(M(n)).
 514 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 515 operation (except possibly mod), then the element pointed to by position is erased.
 516 * [*Note:] Only provided for map views.
 517
 518 [/
 519 [#reference_list_of_modify_iterator_modifier]
 520
 521     template< class Modifier >
 522     bool modify(iterator position,Modifier mod);
 523
 524 * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of
 525 type: `first_type&` and `second_type&` for ['Map View] and `left_type&` and `right_type&`
 526 for ['Set View]. `position` is a valid dereferenceable iterator of the view.
 527 * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View] or calls `mod(e.left,e.right)`
 528 for ['Set View] where `e` is the element pointed to by `position` and
 529 rearranges `*position` into all the views of the `bimap`.
 530 Rearrangement on `list_of` views does not change the position of the element
 531 with respect to the view; rearrangement on other views may or might not suceed.
 532 If the rearrangement fails, the element is erased.
 533 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 534 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 535 * [link list_of_complexity_signature
 536 [*Complexity:]] O(M(n)).
 537 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 538 operation (except possibly `mod`), then the element pointed to by position is erased.
 539 ]
 540
 541 [endsect]
 542
 543 [section List operations]
 544
 545 `list_of` views provide the full set of list operations found in `std::list`;
 546 the semantics of these member functions, however, differ from that of `std::list`
 547 in some cases as insertions might not succeed due to banning by other views.
 548 Similarly, the complexity of the operations may depend on the other views
 549 belonging to the same `bimap`.
 550
 551
 552 [#reference_list_of_splice_iterator_this]
 553
 554     void splice(iterator position, this_type & x);
 555
 556 * [*Requires: ] `position` is a valid iterator of the view. `&x!=this`.
 557 * [*Effects:] Inserts the contents of `x` before position, in the same order as
 558 they were in `x`. Those elements successfully inserted are erased from `x`.
 559 * [link list_of_complexity_signature
 560 [*Complexity:]] O(`x.size()`*I(n+`x.size()`) + `x.size()`*D(`x.size()`)).
 561 * [*Exception safety:] Basic.
 562
 563
 564 [#reference_list_of_splice_iterator_this_iterator]
 565
 566     void splice(iterator position, this_type & x,iterator i);
 567
 568 * [*Requires: ] `position` is a valid iterator of the view. `i` is a valid
 569 dereferenceable iterator `x`.
 570 * [*Effects:] Inserts the element pointed to by `i` before position: if insertion
 571 is successful, the element is erased from `x`. In the special case `&x==this`,
 572 no copy or deletion is performed, and the operation is always successful. If
 573 `position==i`, no operation is performed.
 574 * [*Postconditions:] If `&x==this`, no iterator or reference is invalidated.
 575 * [link list_of_complexity_signature
 576 [*Complexity:]] If `&x==this`, constant; otherwise O(I(n) + D(n)).
 577 * [*Exception safety:] If `&x==this`, nothrow; otherwise, strong.
 578
 579
 580 [#reference_list_of_splice_iterator_this_iterator_iterator]
 581
 582     void splice(iterator position, this_type & x, iterator first, iterator last);
 583
 584 * [*Requires: ] `position` is a valid iterator of the view. `first` and `last` are
 585 valid iterators of `x`. last is reachable from `first`. position is not in the
 586 range `[first,last)`.
 587 * [*Effects:] For each element in the range `[first,last)`, insertion is tried
 588 before position; if the operation is successful, the element is erased from x.
 589 In the special case `&x==this`, no copy or deletion is performed, and insertions
 590 are always successful.
 591 * [*Postconditions:] If `&x==this`, no iterator or reference is invalidated.
 592 * [link list_of_complexity_signature
 593 [*Complexity:]] If `&x==this`, constant; otherwise O(m*I(n+m) + m*D(x.size()))
 594 where m is the number of elements in `[first,last)`.
 595 * [*Exception safety:] If `&x==this`, nothrow; otherwise, basic.
 596
 597
 598 [#reference_list_of_remove_value]
 599
 600     void remove(const value_type & value);
 601
 602 * [*Effects:] Erases all elements of the view which compare equal to `value`.
 603 * [link list_of_complexity_signature
 604 [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
 605 * [*Exception safety:] Basic.
 606
 607
 608 [#reference_list_of_remove_if_predicate]
 609
 610     template< class Predicate >
 611     void remove_if(Predicate pred);
 612
 613 * [*Effects:] Erases all elements `x` of the view for which `pred(x)` holds.
 614 * [link list_of_complexity_signature
 615 [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
 616 * [*Exception safety:] Basic.
 617
 618
 619 [#reference_list_of_unique]
 620
 621     void unique();
 622
 623 * [*Effects:] Eliminates all but the first element from every consecutive
 624 group of equal elements referred to by the iterator `i` in the range
 625 `[first+1,last)` for which `*i==*(i-1)`.
 626 * [link list_of_complexity_signature
 627 [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
 628 * [*Exception safety:] Basic.
 629
 630
 631 [#reference_list_of_unique_predicate]
 632
 633     template< class BinaryPredicate >
 634     void unique(BinaryPredicate binary_pred);
 635
 636 * [*Effects:] Eliminates all but the first element from every consecutive
 637 group of elements referred to by the iterator i in the range \[first+1,last)
 638 for which `binary_pred(*i,*(i-1))` holds.
 639 * [link list_of_complexity_signature
 640 [*Complexity:]] O(n + m*D(n)), where m is the number of elements erased.
 641 * [*Exception safety:] Basic.
 642
 643
 644 [#reference_list_of_merge_this]
 645
 646     void merge(this_type & x);
 647
 648 * [*Requires: ] `std::less<value_type>` is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`.
 649 Both the view and `x` are sorted according to `std::less<value_type>`.
 650 * [*Effects:] Attempts to insert every element of `x` into the corresponding
 651 position of the view (according to the order). Elements successfully inserted
 652 are erased from `x`. The resulting sequence is stable, i.e. equivalent elements
 653 of either container preserve their relative position. In the special case
 654 `&x==this`, no operation is performed.
 655 * [*Postconditions:] Elements in the view and remaining elements in `x` are sorted.
 656 Validity of iterators to the view and of non-erased elements of `x` references
 657 is preserved.
 658 * [link list_of_complexity_signature
 659 [*Complexity:]] If `&x==this`, constant; otherwise
 660 O(n + `x.size()`*I(n+`x.size()`) + `x.size()`*D(`x.size()`)).
 661 * [*Exception safety:] If `&x==this`, nothrow; otherwise, basic.
 662
 663
 664 [#reference_list_of_merge_this_compare]
 665
 666     template< class Compare >
 667     void merge(this_type & x, Compare comp);
 668
 669 * [*Requires:] Compare is a __SGI_STRICT_WEAK_ORDERING__ over `value_type`. Both the view
 670 and `x` are sorted according to `comp`.
 671 * [*Effects:] Attempts to insert every element of `x` into the corresponding position
 672 of the view (according to `comp`). Elements successfully inserted are erased from `x`.
 673 The resulting sequence is stable, i.e. equivalent elements of either container preserve
 674 their relative position. In the special case `&x==this`, no operation is performed.
 675 * [*Postconditions:] Elements in the view and remaining elements in `x` are sorted
 676 according to `comp`. Validity of iterators to the view and of non-erased elements
 677 of `x` references is preserved.
 678 * [link list_of_complexity_signature
 679 [*Complexity:]] If `&x==this`, constant;
 680 otherwise O(n + `x.size()`*I(n+`x.size()`) + `x.size()`*D(`x.size()`)).
 681 * [*Exception safety:] If `&x==this`, nothrow; otherwise, basic.
 682
 683
 684 [#reference_list_of_sort]
 685
 686     void sort();
 687
 688 * [*Requires: ] `std::less<value_type>` is a __SGI_STRICT_WEAK_ORDERING__ over value_type.
 689 * [*Effects:] Sorts the view according to `std::less<value_type>`. The sorting is stable,
 690 i.e. equivalent elements preserve their relative position.
 691 * [*Postconditions:] Validity of iterators and references is preserved.
 692 * [*Complexity:] O(n*log(n)).
 693 * [*Exception safety:] nothrow if `std::less<value_type>` does not throw; otherwise, basic.
 694
 695
 696 [#reference_list_of_sort_compare]
 697
 698     template< typename Compare >
 699     void sort(Compare comp);
 700
 701 * [*Requires:] Compare is a __SGI_STRICT_WEAK_ORDERING__ over value_type.
 702 * [*Effects:] Sorts the view according to comp. The sorting is stable, i.e. equivalent
 703 elements preserve their relative position.
 704 * [*Postconditions:] Validity of iterators and references is preserved.
 705 * [*Complexity:] O(n*log(n)).
 706 * [*Exception safety:] nothrow if comp does not throw; otherwise, basic.
 707
 708
 709 [#reference_list_of_reverse]
 710
 711     void reverse();
 712
 713 * [*Effects:] Reverses the order of the elements in the view.
 714 * [*Postconditions:] Validity of iterators and references is preserved.
 715 * [*Complexity:] O(n).
 716 * [*Exception safety:] nothrow.
 717
 718
 719 [endsect]
 720
 721 [section Rearrange operations]
 722
 723 These operations, without counterpart in `std::list` (although splice provides
 724 partially overlapping functionality), perform individual and global repositioning
 725 of elements inside the index.
 726
 727
 728 [#reference_list_of_relocate_iterator_iterator]
 729
 730     void relocate(iterator position, iterator i);
 731
 732 * [*Requires: ] `position` is a valid iterator of the view. `i` is a valid
 733 dereferenceable iterator of the view.
 734 * [*Effects:] Inserts the element pointed to by `i` before `position`.
 735 If `position==i`, no operation is performed.
 736 * [*Postconditions:] No iterator or reference is invalidated.
 737 * [*Complexity:] Constant.
 738 * [*Exception safety:] nothrow.
 739
 740
 741 [#reference_list_of_relocate_iterator_iterator_iterator]
 742
 743     void relocate(iterator position, iterator first, iterator last);
 744
 745 * [*Requires: ] `position` is a valid iterator of the view. `first` and `last` are
 746 valid iterators of the view. `last` is reachable from `first`. `position` is not
 747 in the range `[first,last)`.
 748 * [*Effects:] The range of elements `[first,last)` is repositioned just before
 749 `position`.
 750 * [*Postconditions:] No iterator or reference is invalidated.
 751 * [*Complexity:] Constant.
 752 * [*Exception safety:] nothrow.
 753
 754
 755 [endsect]
 756
 757 [section Serialization]
 758
 759 Views cannot be serialized on their own, but only as part of the
 760 `bimap` into which they are embedded. In describing the additional
 761 preconditions and guarantees associated to `list_of` views with respect to
 762 serialization of their embedding containers, we use the concepts defined in the
 763 `bimap` serialization section.
 764
 765 [blurb [*Operation:] saving of a `bimap` b to an output archive
 766 (XML archive) ar.]
 767
 768 * [*Requires:] No additional requirements to those imposed by the container.
 769
 770
 771 [blurb [*Operation:] loading of a `bimap` b' from an input archive
 772 (XML archive) ar.]
 773
 774 * [*Requires:] No additional requirements to those imposed by the container.
 775 [*Postconditions:] On successful loading, each of the elements of
 776 `[begin(), end())`
 777 is a restored copy of the corresponding element in
 778 `[m.get<i>().begin(), m.get<i>().end())`,
 779 where `i` is the position of the `list_of` view in the container.
 780
 781
 782 [blurb [*Operation:] saving of an `iterator` or `const_iterator` it to an output
 783 archive (XML archive) ar.]
 784
 785 * [*Requires: ] `it` is a valid iterator of the view. The associated
 786 `bimap` has been previously saved.
 787
 788
 789 [blurb [*Operation:] loading of an `iterator` or `const_iterator it`' from an input
 790 archive (XML archive) ar.]
 791
 792 * [*Postconditions:] On successful loading, if it was dereferenceable then `*it`' is the
 793 restored copy of `*it`, otherwise `it`'` == end()`.
 794 * [*Note:] It is allowed that `it` be a `const_iterator` and the restored `it`' an iterator,
 795 or viceversa.
 796
 797
 798 [endsect]
 799 [endsect]
 800
 801
 802 [endsect]