ceph/src/boost/libs/bimap/doc/reference/set_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 set_of Reference]
  16
  17 [section Header "boost/bimap/set_of.hpp" synopsis]
  18
  19     namespace boost {
  20     namespace bimaps {
  21
  22
  23     template
  24     <
  25         class KeyType,
  26         class KeyCompare = std::less< KeyType >
  27     >
  28     struct set_of;
  29
  30
  31     template
  32     <
  33         class KeyCompare = std::less< _relation >
  34     >
  35     struct set_of_relation;
  36
  37
  38     } // namespace bimap
  39     } // namespace boost
  40
  41
  42 [endsect]
  43
  44 [section Header "boost/bimap/multiset_of.hpp" synopsis]
  45
  46
  47     namespace boost {
  48     namespace bimaps {
  49
  50
  51     template
  52     <
  53         class KeyType,
  54         class KeyCompare = std::less< KeyType >
  55     >
  56     struct multiset_of;
  57
  58
  59     template
  60     <
  61         class KeyCompare = std::less< _relation >
  62     >
  63     struct multiset_of_relation;
  64
  65
  66     } // namespace bimap
  67     } // namespace boost
  68
  69
  70 [endsect]
  71
  72
  73 [section Collection type specifiers set_of and multiset_of]
  74
  75 These collection type specifiers allow for insertion of sets disallowing or
  76 allowing duplicate elements, respectively. The syntaxes of `set_of` and
  77 `multiset_of` coincide, so they are described together.
  78
  79 [endsect]
  80
  81
  82 [section \[multi\]set_of Views]
  83
  84 A \[multi\]set_of set view is a std::\[multi\]set signature-compatible
  85 interface to the underlying heap of elements contained in a `bimap`.
  86
  87 There are two variants: set_of, which does not allow duplicate elements
  88 (with respect to its associated comparison predicate) and multiset_of,
  89 which does accept those duplicates. The interface of these two variants
  90 is largely the same, so they are documented together with their
  91 differences explicitly noted where they exist.
  92
  93 If you look the bimap from a side, you will use a map view, and if you
  94 look at it as a whole, you will be using a set view.
  95
  96
  97
  98     namespace boost {
  99     namespace bimaps {
 100     namespace views {
 101
 102     template< ``['-implementation defined parameter list-]`` >
 103     class ``['-implementation defined view name-]``
 104     {
 105         public:
 106
 107         typedef ``['-unspecified-]`` key_type;
 108                 typedef ``['-unspecified-]`` value_type;
 109         typedef ``['-unspecified-]`` key_compare;
 110         typedef ``['-unspecified-]`` value_compare;
 111         typedef ``['-unspecified-]`` allocator_type;
 112         typedef ``['-unspecified-]`` reference;
 113         typedef ``['-unspecified-]`` const_reference;
 114         typedef ``['-unspecified-]`` iterator;
 115         typedef ``['-unspecified-]`` const_iterator;
 116         typedef ``['-unspecified-]`` size_type;
 117         typedef ``['-unspecified-]`` difference_type;
 118         typedef ``['-unspecified-]`` pointer;
 119         typedef ``['-unspecified-]`` const_pointer;
 120         typedef ``['-unspecified-]`` reverse_iterator;
 121         typedef ``['-unspecified-]`` const_reverse_iterator;
 122
 123         typedef ``['-unspecified-]`` info_type;
 124
 125         this_type & operator=(const this_type & x);
 126
 127         allocator_type get_allocator() const;
 128
 129         // iterators
 130
 131         iterator               begin();
 132         const_iterator         begin() const;
 133
 134         iterator               end();
 135         const_iterator         end() const;
 136
 137         reverse_iterator       rbegin();
 138         const_reverse_iterator rbegin() const;
 139
 140         reverse_iterator       rend();
 141         const_reverse_iterator rend() const;
 142
 143         // capacity
 144
 145         bool      empty() const;
 146
 147         size_type size() const;
 148
 149         size_type max_size() const;
 150
 151         // modifiers
 152
 153         std::pair<iterator,bool> ``[link reference_set_of_insert_value insert]``(const value_type & x);
 154
 155         iterator ``[link reference_set_of_insert_iterator_value insert]``(iterator position, const value_type & x);
 156
 157         template< class InputIterator>
 158         void ``[link reference_set_of_insert_iterator_iterator insert]``(InputIterator first,  InputIterator last);
 159
 160         iterator ``[link reference_set_of_erase_iterator erase]``(iterator position);
 161
 162         template< class CompatibleKey >
 163         size_type ``[link reference_set_of_erase_key erase]``(const CompatibleKey & x);
 164
 165         iterator ``[link reference_set_of_erase_iterator_iterator erase]``(iterator first,  iterator last);
 166
 167         bool ``[link reference_set_of_replace_iterator_value replace]``(iterator position, const value_type& x);
 168
 169         // Only in map views
 170         // {
 171
 172           template< class CompatibleKey >
 173           bool ``[link reference_set_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x);
 174
 175           template< class CompatibleData >
 176           bool ``[link reference_set_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x);
 177
 178           template< class KeyModifier >
 179           bool ``[link reference_set_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod);
 180
 181           template< class DataModifier >
 182           bool ``[link reference_set_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod);
 183
 184         // }
 185
 186         void swap(this_type & x);
 187
 188         void clear();
 189
 190         // observers
 191
 192         key_compare    key_comp() const;
 193
 194         value_compare  value_comp() const;
 195
 196         // set operations
 197
 198         template< class CompatibleKey >
 199         iterator ``[link reference_set_of_find_key find]``(const CompatibleKey & x);
 200
 201         template< class CompatibleKey >
 202         const_iterator ``[link reference_set_of_find_key find]``(const CompatibleKey & x) const;
 203
 204
 205         template< class CompatibleKey >
 206         size_type ``[link reference_set_of_count_key count]``(const CompatibleKey & x) const;
 207
 208
 209         template< class CompatibleKey >
 210         iterator ``[link reference_set_of_lower_bound_key lower_bound]``(const CompatibleKey & x);
 211
 212         template< class CompatibleKey >
 213         const_iterator ``[link reference_set_of_lower_bound_key lower_bound]``(const CompatibleKey & x) const;
 214
 215
 216         template< class CompatibleKey >
 217         iterator ``[link reference_set_of_upper_bound_key upper_bound]``(const CompatibleKey & x);
 218
 219         template< class CompatibleKey >
 220         const_iterator ``[link reference_set_of_upper_bound_key upper_bound]``(const CompatibleKey & x) const;
 221
 222
 223         template< class CompatibleKey >
 224         std::pair<iterator,iterator>
 225             ``[link reference_set_of_equal_range_key equal_range]``(const CompatibleKey & x);
 226
 227         template< class CompatibleKey >
 228         std::pair<const_iterator,const_iterator>
 229             ``[link reference_set_of_equal_range_key equal_range]``(const CompatibleKey & x) const;
 230
 231         // Only in maps views
 232         // {
 233
 234         template< class LowerBounder, class UpperBounder>
 235         std::pair<iterator,iterator> ``[link reference_set_of_range_lower_upper range]``(
 236             LowerBounder lower, UpperBounder upper);
 237
 238         template< class LowerBounder, class UpperBounder>
 239         std::pair<const_iterator,const_iterator> ``[link reference_set_of_range_lower_upper range]``(
 240             LowerBounder lower, UpperBounder upper) const;
 241
 242         typedef ``['-unspecified-]`` mapped_type;
 243         typedef ``['-unspecified-]`` data_type; // Equal to mapped_type
 244
 245           // Only in for `set_of` collection type
 246           // {
 247
 248           template< class CompatibleKey >
 249           const mapped_type & ``[link reference_set_of_at_key_const at]``(const CompatibleKey & k) const;
 250
 251             // Only if the other collection type is mutable
 252             // {
 253
 254             template< class CompatibleKey >
 255             mapped_type & ``[link reference_set_of_operator_bracket_key operator\[\]]``(const CompatibleKey & k);
 256
 257             template< class CompatibleKey >
 258             mapped_type & ``[link reference_set_of_at_key at]``(const CompatibleKey & k);
 259
 260             // }
 261
 262             // Only if info_hook is used
 263             // {
 264
 265             template< class CompatibleKey >
 266             info_type & ``[link reference_set_of_info_at_key info_at]``(const CompatibleKey & k);
 267
 268             template< class CompatibleKey >
 269             const info_type & ``[link reference_set_of_info_at_key info_at]``(const CompatibleKey & k) const;
 270
 271             // }
 272
 273           // }
 274
 275         // }
 276     };
 277
 278     // view comparison
 279
 280     bool operator==(const this_type & v1, const this_type & v2 );
 281     bool operator< (const this_type & v1, const this_type & v2 );
 282     bool operator!=(const this_type & v1, const this_type & v2 );
 283     bool operator> (const this_type & v1, const this_type & v2 );
 284     bool operator>=(const this_type & v1, const this_type & v2 );
 285     bool operator<=(const this_type & v1, const this_type & v2 );
 286
 287     } // namespace views
 288     } // namespace bimap
 289     } // namespace boost
 290
 291
 292
 293 [/ Functions that may be implemented some day
 294
 295         template< class Modifier>
 296         bool ``[link reference_set_of_modify_iterator_modifier modify]``(iterator position, Modifier mod);
 297
 298         template< class CompatibleKey, class CompatibleCompare >
 299         iterator find(const CompatibleKey & x,
 300                       const CompatibleCompare & comp);
 301
 302         template< class CompatibleKey, class CompatibleCompare >
 303         const_iterator find(const CompatibleKey & x,
 304                             const CompatibleCompare & comp) const;
 305
 306         template< class CompatibleKey, class CompatibleCompare >
 307         size_type count(const CompatibleKey & x,
 308                         const CompatibleCompare & comp) const;
 309
 310         template< class CompatibleKey, class CompatibleCompare >
 311         iterator lower_bound(const CompatibleKey & x,
 312                              const CompatibleCompare & comp);
 313
 314         template< class CompatibleKey, class CompatibleCompare >
 315         const_iterator lower_bound(const CompatibleKey & x,
 316                                    const CompatibleCompare & comp) const;
 317
 318         template< class CompatibleKey, class CompatibleCompare >
 319         iterator upper_bound(const CompatibleKey & x,
 320                              const CompatibleCompare & comp);
 321
 322         template< class CompatibleKey, class CompatibleCompare >
 323         const_iterator upper_bound(const CompatibleKey & x,
 324                                    const CompatibleCompare & comp) const;
 325
 326         template< class CompatibleKey, class CompatibleCompare >
 327         std::pair<iterator,iterator> equal_range(
 328             const CompatibleKey & x, const CompatibleCompare & comp);
 329
 330         template< class CompatibleKey, class CompatibleCompare >
 331         std::pair<const_iterator,const_iterator> equal_range(
 332             const CompatibleKey & x, const CompatibleCompare & comp) const;
 333
 334 ]
 335
 336
 337 In the case of a `bimap< {multi}set_of<Left>, ... >`
 338
 339 In the set view:
 340
 341     typedef signature-compatible with relation<       Left, ... > key_type;
 342     typedef signature-compatible with relation< const Left, ... > value_type;
 343
 344 In the left map view:
 345
 346     typedef  Left  key_type;
 347     typedef  ...   mapped_type;
 348
 349     typedef signature-compatible with std::pair< const Left, ... > value_type;
 350
 351 In the right map view:
 352
 353     typedef  ...  key_type;
 354     typedef  Left mapped_type;
 355
 356     typedef signature-compatible with std::pair< ... ,const Left > value_type;
 357
 358
 359 [#set_of_complexity_signature]
 360
 361 [section Complexity signature]
 362
 363 Here and in the descriptions of operations of this view, we adopt the
 364 scheme outlined in the [link complexity_signature_explanation complexity signature section].
 365 The complexity signature of \[multi\]set_of view is:
 366
 367 * copying: `c(n) = n * log(n)`,
 368 * insertion: `i(n) = log(n)`,
 369 * hinted insertion: `h(n) = 1` (constant) if the hint element precedes the point of
 370 insertion, `h(n) = log(n)` otherwise,
 371 * deletion: `d(n) = 1` (amortized constant),
 372 * replacement: `r(n) = 1` (constant) if the element position does not change,
 373 `r(n) = log(n)` otherwise,
 374 * modifying: `m(n) = 1` (constant) if the element position does not change,
 375 `m(n) = log(n)` otherwise.
 376
 377 [endsect]
 378
 379 [section Instantiation types]
 380
 381 Set views are instantiated internally to a `bimap`.
 382 Instantiations are dependent on the following types:
 383
 384 * `Value` from the set specifier,
 385 * `Allocator` from `bimap`,
 386 * `Compare` from the set specifier.
 387
 388 `Compare` is a __SGI_STRICT_WEAK_ORDERING__ on elements of `Value`.
 389
 390 [endsect]
 391
 392 [section Constructors, copy and assignment]
 393
 394 Set views do not have public constructors or destructors.
 395 Assignment, on the other hand, is provided.
 396
 397     this_type & operator=(const this_type & x);
 398
 399 * [*Effects: ] `a = b;`
 400 where a and b are the `bimap` objects to which `*this` and x
 401 belong, respectively.
 402 * [*Returns: ] `*this`.
 403
 404
 405
 406 [endsect]
 407
 408 [section Modifiers]
 409
 410 [#reference_set_of_insert_value]
 411
 412     std::pair<iterator,bool> insert(const value_type & x);
 413
 414 * [*Effects:] Inserts `x` into the `bimap` to which the set view belongs if
 415     * the set view is non-unique OR no other element with equivalent key exists,
 416     * AND insertion is allowed by the other set specifications the `bimap`.
 417 * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if insertion
 418 took place. On successful insertion, `p.first` points to the element inserted;
 419 otherwise, `p.first` points to an element that caused the insertion to be banned.
 420 Note that more than one element can be causing insertion not to be allowed.
 421 * [link set_of_complexity_signature
 422 [*Complexity:]] O(I(n)).
 423 * [*Exception safety:] Strong.
 424
 425
 426 [#reference_set_of_insert_iterator_value]
 427
 428     iterator insert(iterator position, const value_type & x);
 429
 430 * [*Requires: ] `position` is a valid iterator of the view.
 431 * [*Effects: ] `position` is used as a hint to improve the efficiency of the operation. Inserts `x` into the `bimap` to which the view belongs if
 432     * the set view is non-unique OR no other element with equivalent key exists,
 433     * AND insertion is allowed by all other views of the `bimap`.
 434 * [*Returns:] On successful insertion, an iterator to the newly inserted
 435 element. Otherwise, an iterator to an element that caused the insertion to be
 436 banned. Note that more than one element can be causing insertion not to be allowed.
 437 * [link set_of_complexity_signature
 438 [*Complexity:]] O(H(n)).
 439 * [*Exception safety:] Strong.
 440
 441
 442 [#reference_set_of_insert_iterator_iterator]
 443
 444     template< class InputIterator >
 445     void insert(InputIterator first, InputIterator last);
 446
 447 * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements of
 448 type `value_type` or a type convertible to value_type. `first` and `last` are not
 449 iterators into any view of the `bimap` to which this index
 450 belongs. `last` is reachable from `first`.
 451 * [*Effects: ]
 452 `iterator hint = end()`;
 453 `while( first != last ) hint = insert( hint, *first++ );`
 454 * [link set_of_complexity_signature
 455 [*Complexity:]] O(m*H(n+m)), where m is the number of elements in
 456 `[first, last)`.
 457 * [*Exception safety:] Basic.
 458
 459
 460 [#reference_set_of_erase_iterator]
 461
 462     iterator erase(iterator position);
 463
 464 * [*Requires: ] `position` is a valid dereferenceable iterator if the set view.
 465 * [*Effects:] Deletes the element pointed to by `position`.
 466 * [*Returns:] An iterator pointing to the element immediately following
 467 the one that was deleted, or `end()` if no such element exists.
 468 * [link set_of_complexity_signature
 469 [*Complexity:]] O(D(n)).
 470 * [*Exception safety:] nothrow.
 471
 472
 473 [#reference_set_of_erase_key]
 474
 475     template< class CompatibleKey >
 476     size_type erase(const CompatibleKey & x);
 477
 478 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 479 * [*Effects:] Deletes the elements with key equivalent to `x`.
 480 * [*Returns:] Number of elements deleted.
 481 * [link set_of_complexity_signature
 482 [*Complexity:]] O(log(n) + m*D(n)), where m is the number of elements deleted.
 483 * [*Exception safety:] Basic.
 484
 485
 486 [#reference_set_of_erase_iterator_iterator]
 487
 488     iterator erase(iterator first, iterator last);
 489
 490 * [*Requires: ] `[first,last)` is a valid range of the view.
 491 * [*Effects:] Deletes the elements in `[first,last)`.
 492 * [*Returns:] last.
 493 * [link set_of_complexity_signature
 494 [*Complexity:]] O(log(n) + m*D(n)), where m is the number of elements
 495 in `[first,last)`.
 496 * [*Exception safety:] nothrow.
 497
 498
 499 [#reference_set_of_replace_iterator_value]
 500
 501     bool replace(iterator position, const value_type& x);
 502
 503 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 504 * [*Effects:] Assigns the value `x` to the element pointed to by `position` into
 505 the `bimap` to which the set view belongs if, for the value `x`
 506     * the set view is non-unique OR no other element with equivalent key exists
 507 (except possibly `*position`),
 508     * AND replacing is allowed by all other views of the `bimap`.
 509 * [*Postconditions:] Validity of position is preserved in all cases.
 510 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 511 * [link set_of_complexity_signature
 512 [*Complexity:]] O(R(n)).
 513 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 514 operation, the `bimap` to which the set view belongs remains in
 515 its original state.
 516
 517
 518 [#reference_set_of_replace_key_iterator_key]
 519
 520     template< class CompatibleKey >
 521     bool replace_key(iterator position, const CompatibleKey & x);
 522
 523 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 524 `CompatibleKey` can be assigned to `key_type`.
 525 * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed
 526 to by `position` into the `bimap` to which the set view belongs if,
 527     * the map view is non-unique OR no other element with equivalent key exists
 528 (except possibly `*position`),
 529     * AND replacing is allowed by all other views of the `bimap`.
 530 * [*Postconditions:] Validity of position is preserved in all cases.
 531 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 532 * [link set_of_complexity_signature
 533 [*Complexity:]] O(R(n)).
 534 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 535 operation, the `bimap` to which the set view belongs remains in
 536 its original state.
 537
 538
 539 [#reference_set_of_replace_data_iterator_data]
 540
 541     template< class CompatibleData >
 542     bool replace_data(iterator position, const CompatibleData & x);
 543
 544 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 545 `CompatibleKey` can be assigned to `mapped_type`.
 546 * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed
 547 to by `position` into the `bimap` to which the set view belongs if,
 548     * the map view is non-unique OR no other element with equivalent key exists
 549 (except possibly `*position`),
 550     * AND replacing is allowed by all other views of the `bimap`.
 551 * [*Postconditions:] Validity of position is preserved in all cases.
 552 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 553 * [link set_of_complexity_signature
 554 [*Complexity:]] O(R(n)).
 555 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 556 operation, the `bimap` to which the set view belongs remains in
 557 its original state.
 558
 559
 560 [#reference_set_of_modify_key_iterator_modifier]
 561
 562     template< class KeyModifier >
 563     bool modify_key(iterator position, KeyModifier mod);
 564
 565 * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
 566 type: `key_type&`; `position` is a valid dereferenceable iterator of the view.
 567 * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and
 568 rearranges `*position` into all the views of the `bimap`.
 569 If the rearrangement fails, the element is erased.
 570 Rearrangement is successful if
 571     * the map view is non-unique OR no other element with equivalent key exists,
 572     * AND rearrangement is allowed by all other views of the `bimap`.
 573 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 574 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 575 * [link set_of_complexity_signature
 576 [*Complexity:]] O(M(n)).
 577 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 578 operation (except possibly mod), then the element pointed to by position is erased.
 579 * [*Note:] Only provided for map views.
 580
 581
 582 [#reference_set_of_modify_data_iterator_modifier]
 583
 584     template< class DataModifier >
 585     bool modify_data(iterator position, DataModifier mod);
 586
 587 * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
 588 type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view.
 589 * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and
 590 rearranges `*position` into all the views of the `bimap`.
 591 If the rearrangement fails, the element is erased.
 592 Rearrangement is successful if
 593     * the oppositte map view is non-unique OR no other element with equivalent key in that
 594 view exists,
 595     * AND rearrangement is allowed by all other views of the `bimap`.
 596 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 597 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 598 * [link set_of_complexity_signature
 599 [*Complexity:]] O(M(n)).
 600 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 601 operation (except possibly mod), then the element pointed to by position is erased.
 602 * [*Note:] Only provided for map views.
 603
 604 [/
 605
 606 [#reference_set_of_modify_iterator_modifier]
 607
 608     template< class Modifier >
 609     bool modify(iterator position, Modifier mod);
 610
 611 * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of
 612 type: `first_type&` and `second_type&` for ['Map View] or `left_type&` and `right_type&`
 613 ['Set View]; `position` is a valid dereferenceable iterator of the view.
 614 * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View] or Calls `mod(e.left,e.right)`
 615 for ['Set View] where e is the element pointed to by position and rearranges `*position`
 616 into all the views of the `bimap`.
 617 If the rearrangement fails, the element is erased.
 618 Rearrangement is successful if
 619     * the view is non-unique OR no other element with equivalent key exists,
 620     * AND rearrangement is allowed by all other views of the `bimap`.
 621 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 622 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 623 * [link set_of_complexity_signature
 624 [*Complexity:]] O(M(n)).
 625 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 626 operation (except possibly mod), then the element pointed to by position is erased.
 627
 628 ]
 629
 630 [endsect]
 631
 632 [section Set operations]
 633
 634 `[multi]set_of` views provide the full lookup functionality required by
 635 __SGI_SORTED_ASSOCIATIVE_CONTAINER__ and __SGI_UNIQUE_ASSOCIATIVE_CONTAINER__,
 636 namely `find`, `count`, `lower_bound`, `upper_bound` and `equal_range`.
 637 Additionally, these member functions are templatized to allow for non-standard
 638 arguments, so extending the types of search operations allowed.
 639
 640 [/
 641 The kinds of arguments permissible when invoking the lookup member functions
 642 are defined by the following concept.
 643
 644 Consider a __SGI_STRICT_WEAK_ORDERING__ `Compare` over values of type `Key`. A pair of
 645 types `(CompatibleKey, CompatibleCompare)` is said to be a ['compatible extension]
 646 of Compare if
 647
 648 * `CompatibleCompare` is a __SGI_BINARY_PREDICATE__ over `(Key, CompatibleKey)`,
 649 * `CompatibleCompare` is a __SGI_BINARY_PREDICATE__ over `(CompatibleKey, Key)`,
 650 * if `c_comp(ck,k1)` then `!c_comp(k1,ck)`,
 651 * if `!c_comp(ck,k1)` and `!comp(k1,k2)` then `!c_comp(ck,k2)`,
 652 * if `!c_comp(k1,ck)` and `!comp(k2,k1)` then `!c_comp(k2,ck)`,
 653
 654 for every `c_comp` of type `CompatibleCompare`, `comp` of type `Compare`, `ck` of type
 655 `CompatibleKey` and `k1`, `k2` of type `Key`.
 656 ]
 657 A type `CompatibleKey` is said to be a ['compatible key] of `Compare`
 658 if `(CompatibleKey, Compare)` is a compatible extension of `Compare`. This implies
 659 that `Compare`, as well as being a strict weak ordering, accepts arguments of type
 660 `CompatibleKey`, which usually means it has several overloads of `operator()`.
 661
 662 [/
 663 In the context of a compatible extension or a compatible key, the expressions
 664 "equivalent", "less than" and "greater than" take on their obvious interpretations.
 665 ]
 666
 667 [#reference_set_of_find_key]
 668
 669     template< class CompatibleKey >
 670     iterator find(const CompatibleKey & x);
 671
 672     template< class CompatibleKey >
 673     const_iterator find(const CompatibleKey & x) const;
 674
 675 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 676 * [*Effects:] Returns a pointer to an element whose key is equivalent to `x`, or
 677 `end()` if such an element does not exist.
 678 * [*Complexity:] O(log(n)).
 679
 680 [/
 681     template< class CompatibleKey, class CompatibleCompare >
 682     iterator find(const CompatibleKey & x,
 683                   const CompatibleCompare & comp);
 684
 685     template< class CompatibleKey, class CompatibleCompare >
 686     const_iterator find(const CompatibleKey & x,
 687                         const CompatibleCompare & comp) const;
 688
 689 * [*Requires: ] `(CompatibleKey, CompatibleCompare)` is a compatible extension of
 690 `key_compare.`
 691 * [*Effects:] Returns a pointer to an element whose key is
 692 equivalent to `x`, or `end()` if such an element does not exist.
 693 * [*Complexity:] O(log(n)).
 694 ]
 695
 696 [#reference_set_of_count_key]
 697
 698     template< class CompatibleKey >
 699     size_type count(const key_type & x) const;
 700
 701 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 702 * [*Effects:] Returns the number of elements with key equivalent to `x`.
 703 * [*Complexity:] O(log(n) + count(x)).
 704
 705 [/
 706     template< class CompatibleKey, class CompatibleCompare >
 707     size_type count(const CompatibleKey & x,
 708                     const CompatibleCompare & comp) const;
 709
 710 * [*Requires: ] `(CompatibleKey, CompatibleCompare)` is a compatible extension of
 711 `key_compare.`
 712 * [*Effects:] Returns the number of elements with key equivalent to `x`.
 713 * [*Complexity:] O(log(n) + count(x)).
 714 ]
 715
 716 [#reference_set_of_lower_bound_key]
 717
 718     template< class CompatibleKey >
 719     iterator lower_bound(const key_type & x);
 720
 721     template< class CompatibleKey >
 722     const_iterator lower_bound(const key_type & x) const;
 723
 724 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 725 * [*Effects:] Returns an iterator pointing to the first element with key not
 726 less than `x`, or `end()` if such an element does not exist.
 727 * [*Complexity:] O(log(n)).
 728
 729
 730 [#reference_set_of_upper_bound_key]
 731
 732     template< class CompatibleKey >
 733     iterator upper_bound(const key_type & x);
 734
 735     template< class CompatibleKey >
 736     const_iterator upper_bound(const key_type & x) const;
 737
 738 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 739 * [*Effects:] Returns an iterator pointing to the first element with key greater
 740 than `x`, or `end()` if such an element does not exist.
 741 * [*Complexity:] O(log(n)).
 742
 743
 744 [#reference_set_of_equal_range_key]
 745
 746     template< class CompatibleKey >
 747     std::pair<iterator,iterator>
 748         equal_range(const key_type & x);
 749
 750     template< class CompatibleKey >
 751     std::pair<const_iterator,const_iterator>
 752         equal_range(const key_type & x) const;
 753
 754 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 755 * [*Effects:] Equivalent to `make_pair(lower_bound(x),upper_bound(x))`.
 756 * [*Complexity:] O(log(n)).
 757
 758
 759
 760 [endsect]
 761
 762 [section Range operations]
 763
 764 The member function range is not defined for sorted associative
 765 containers, but `[multi]set_of` map views provide it as a convenient utility.
 766 A range or interval is defined by two conditions for the lower and upper
 767 bounds, which are modelled after the following concepts.
 768
 769 Consider a __SGI_STRICT_WEAK_ORDERING__ `Compare` over values of type Key.
 770 A type `LowerBounder` is said to be a lower bounder of `Compare` if
 771
 772 * `LowerBounder` is a `Predicate` over `Key`,
 773 * if `lower(k1)` and `!comp(k2,k1)` then `lower(k2)`,
 774
 775 for every `lower` of type `LowerBounder`, `comp` of type `Compare`, and `k1`, `k2`
 776 of type `Key`.
 777 Similarly, an upper bounder is a type `UpperBounder` such that
 778
 779 * `UpperBounder` is a `Predicate` over `Key`,
 780 * if `upper(k1)` and `!comp(k1,k2)` then `upper(k2)`,
 781
 782 for every `upper` of type `UpperBounder`, `comp` of type `Compare`, and `k1`, `k2`
 783 of type `Key`.
 784
 785 [#reference_set_of_range_lower_upper]
 786
 787     template< class LowerBounder, class UpperBounder>
 788     std::pair<const_iterator,const_iterator> range(
 789         LowerBounder lower, UpperBounder upper) const;
 790
 791 * [*Requires: ] `LowerBounder` and `UpperBounder` are a lower and upper bounder of
 792 `key_compare`, respectively.
 793 * [*Effects:] Returns a pair of iterators pointing to
 794 the beginning and one past the end of the subsequence of elements satisfying
 795 lower and upper simultaneously. If no such elements exist, the iterators both
 796 point to the first element satisfying lower, or else are equal to `end()` if this
 797 latter element does not exist.
 798 * [*Complexity:] O(log(n)).
 799 * [*Variants:] In place of lower or upper (or both), the singular value
 800 `boost::bimap::unbounded` can be provided. This acts as a predicate which
 801 all values of type `key_type` satisfy.
 802 * [*Note:] Only provided for map views.
 803
 804 [endsect]
 805
 806 [section at(), info_at() and operator\[\] - set_of only]
 807
 808 [#reference_set_of_at_key_const]
 809
 810     template< class CompatibleKey >
 811     const mapped_type & at(const CompatibleKey & k) const;
 812
 813 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 814 * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or
 815 throws `std::out_of_range` if such key does not exist.
 816 * [*Complexity:] O(log(n)).
 817 * [*Note:] Only provided when `set_of` is used.
 818
 819 The symmetry of bimap imposes some constraints on `operator[]` and the
 820 non constant version of at() that are not found in `std::maps`.
 821 Tey are only provided if the other collection type is mutable
 822 (`list_of`, `vector_of` and `unconstrained_set_of`).
 823
 824 [#reference_set_of_operator_bracket_key]
 825
 826     template< class CompatibleKey >
 827     mapped_type & operator[](const CompatibleKey & k);
 828
 829 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 830 * [*Effects: ] `return insert(value_type(k,mapped_type()))->second;`
 831 * [*Complexity:] O(log(n)).
 832 * [*Note:] Only provided when `set_of` is used and the other collection
 833 type is mutable.
 834
 835 [#reference_set_of_at_key]
 836
 837     template< class CompatibleKey >
 838     mapped_type & at(const CompatibleKey & k);
 839
 840 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 841 * [*Effects: ] Returns the `mapped_type` reference that is associated with `k`, or
 842 throws `std::out_of_range` if such key does not exist.
 843 * [*Complexity:] O(log(n)).
 844 * [*Note:] Only provided when `set_of` is used and the other collection
 845 type is mutable.
 846
 847 [/
 848 The symmetry of bimap imposes some constraints on `operator[]` that are
 849 not found in `std::maps`. If other views are unique,
 850 `bimap::duplicate_value` is thrown whenever an assignment is attempted to
 851 a value that is already a key in these views. As for
 852 `bimap::value_not_found`, this exception is thrown while trying to access
 853 a non-existent key: this behaviour differs from that of `std::map`, which
 854 automatically assigns a default value to non-existent keys referred to
 855 by `operator[]`.
 856
 857     const mapped_type & operator[](const typename key_type & k) const;
 858
 859 * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or
 860 throws `bimap::value_not_found` if such an element does not exist.
 861 * [*Complexity:] O(log(n)).
 862
 863
 864     ``['-unspecified mapped_type proxy-]`` operator[](const typename key_type & k);
 865
 866 * [*Effects:] Returns a proxy to a `mapped_type` associated with `k` and the
 867 bimap. The proxy behaves as a reference to the `mapped_type` object. If this
 868 proxy is read and `k` was not in the bimap, the bimap::value_not_found is
 869 thrown. If it is written then `bimap::duplicate_value` is thrown if the
 870 assignment is not allowed by one of the other views of the `bimap`.
 871 * [link set_of_complexity_signature
 872 [*Complexity:]] If the assignment operator of the proxy is not used, then
 873 the order is O(log(n)). If it is used, the order is O(I(n)) if `k` was not
 874 in the bimap and O(R(n)) if it existed in the bimap.
 875 ]
 876
 877
 878 [#reference_set_of_info_at_key]
 879
 880     template< class CompatibleKey >
 881     info_type & info_at(const CompatibleKey & k);
 882
 883     template< class CompatibleKey >
 884     const info_type & info_at(const CompatibleKey & k) const;
 885
 886 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 887 * [*Effects:] Returns the `info_type` reference that is associated with `k`, or
 888 throws `std::out_of_range` if such key does not exist.
 889 * [*Complexity:] O(log(n)).
 890 * [*Note:] Only provided when `set_of` and `info_hook` are used
 891
 892
 893 [endsect]
 894
 895 [section Serialization]
 896
 897 Views cannot be serialized on their own, but only as part of the `bimap`
 898 into which they are embedded. In describing the additional preconditions and guarantees
 899 associated to `[multi]set_of` views with respect to serialization of their embedding containers,
 900 we use the concepts defined in the `bimap` serialization section.
 901
 902 [blurb  [*Operation:] saving of a `bimap` m to an output archive (XML archive) ar.]
 903
 904 * [*Requires:] No additional requirements to those imposed by the container.
 905
 906
 907 [blurb [*Operation:] loading of a `bimap` m' from an input archive (XML archive) ar.]
 908
 909 * [*Requires:] In addition to the general requirements, `value_comp()` must be
 910 serialization-compatible with `m.get<i>().value_comp()`, where i is the position
 911 of the ordered view in the container.
 912 * [*Postconditions:] On successful loading, each of the elements of `[begin(), end())`
 913 is a restored copy of the corresponding element in `[m.get<i>().begin(), m.get<i>().end())`.
 914
 915
 916
 917 [blurb [*Operation:] saving of an iterator or `const_iterator` it to an output archive
 918 (XML archive) ar.]
 919
 920 * [*Requires: ] `it` is a valid iterator of the view. The associated `bimap`
 921 has been previously saved.
 922
 923
 924 [blurb [*Operation:] loading of an `iterator` or `const_iterator` `it`' from an input archive (
 925 XML archive) ar.]
 926
 927 * [*Postconditions:] On successful loading, if it was dereferenceable then `*it`' is the
 928 restored copy of `*it`, otherwise `it`'` == end()`.
 929 * [*Note:] It is allowed that it be a `const_iterator` and the restored `it`' an iterator,
 930 or viceversa.
 931
 932
 933 [endsect]
 934 [endsect]
 935
 936 [endsect]