ceph/src/boost/libs/bimap/doc/reference/unordered_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 unordered_set_of Reference]
  16
  17 [section Header "boost/bimap/unordered_set_of.hpp" synopsis]
  18
  19     namespace boost {
  20     namespace bimaps {
  21
  22
  23     template
  24     <
  25         class KeyType,
  26         class HashFunctor   = hash< KeyType >,
  27         class EqualKey      = std::equal_to< KeyType >
  28     >
  29     struct unordered_set_of;
  30
  31
  32     template
  33     <
  34         class HashFunctor   = hash< _relation >,
  35         class EqualKey      = std::equal_to< _relation >
  36     >
  37     struct unordered_set_of_relation;
  38
  39
  40     } // namespace bimap
  41     } // namespace boost
  42
  43
  44 [endsect]
  45
  46 [section Header "boost/bimap/unordered_multiset_of.hpp" synopsis]
  47
  48     namespace boost {
  49     namespace bimaps {
  50
  51
  52     template
  53     <
  54         class KeyType,
  55         class HashFunctor   = hash< KeyType >,
  56         class EqualKey      = std::equal_to< KeyType >
  57     >
  58     struct unordered_multiset_of;
  59
  60
  61     template
  62     <
  63         class HashFunctor   = hash< _relation >,
  64         class EqualKey      = std::equal_to< _relation >
  65     >
  66     struct unordered_multiset_of_relation;
  67
  68
  69     } // namespace bimap
  70     } // namespace boost
  71
  72
  73 [endsect]
  74
  75 [section Collection type specifiers unordered_set_of and unordered_multiset_of]
  76
  77 These collection types specifiers allow for set views without and
  78 with allowance of duplicate elements, respectively. The syntax of
  79 `set_of` and `multiset_of` coincide, thus we describe them
  80 in a grouped manner.
  81
  82 [endsect]
  83
  84 [section unordered_\[multi\]set_of Views]
  85
  86 An unordered_\[multi\]set_of set view is a tr1::unordered\[multi\]set signature compatible
  87 interface to the underlying heap of elements contained in a `bimap`.
  88
  89 The interface and semantics of `unordered_[multi]set_of` views are
  90 modeled according to the proposal for unordered associative containers given
  91 in the __CPP_STANDARD_LIBRARY_TECHNICAL_REPORT__, also known as TR1.
  92 An `unordered_[multi]set_of` view is particularized according to a given
  93 `Hash` function object which returns hash values for the keys and a
  94 binary predicate `Pred` acting as an equivalence relation on values of Key.
  95
  96 There are two variants: unordered_set_of, which do not allow duplicate elements
  97 (with respect to its associated comparison predicate) and unordered_multiset_of,
  98 which accept those duplicates. The interface of these two variants is the same
  99 to a great extent, so they are documented together with their differences
 100 explicitly noted when they exist.
 101
 102 If you look the bimap by a side, you will use a map view and if you looked
 103 it as a whole you will be using a set view.
 104
 105 Except where noted, `unordered_[multi]set_of` views (both unique and non-unique) are models
 106 of [^Unordered Associative Container].
 107 Validity of iterators and references to elements is preserved in all cases.
 108 Occasionally, the exception safety guarantees provided are actually stronger
 109 than required by the extension draft. We only provide descriptions of those
 110 types and operations that are either not present in the concepts modeled or
 111 do not exactly conform to the requirements for unordered associative containers.
 112
 113
 114     namespace boost {
 115     namespace bimap {
 116     namespace views {
 117
 118     template< ``['-implementation defined parameter list-]`` >
 119     class ``['-implementation defined view name-]``
 120     {
 121         public:
 122
 123         // types
 124
 125         typedef ``['-unspecified-]`` key_type;
 126         typedef ``['-unspecified-]`` value_type;
 127         typedef ``['-unspecified-]`` key_compare;
 128         typedef ``['-unspecified-]`` value_compare;
 129         typedef ``['-unspecified-]`` hasher;
 130         typedef ``['-unspecified-]`` key_equal;
 131         typedef ``['-unspecified-]`` allocator_type;
 132         typedef ``['-unspecified-]`` reference;
 133         typedef ``['-unspecified-]`` const_reference;
 134         typedef ``['-unspecified-]`` iterator;
 135         typedef ``['-unspecified-]`` const_iterator;
 136         typedef ``['-unspecified-]`` size_type;
 137         typedef ``['-unspecified-]`` difference_type;
 138         typedef ``['-unspecified-]`` pointer;
 139         typedef ``['-unspecified-]`` const_pointer;
 140         typedef ``['-unspecified-]`` local_iterator;
 141         typedef ``['-unspecified-]`` const_local_iterator;
 142
 143         typedef ``['-unspecified-]`` info_type;
 144
 145         // construct/destroy/copy:
 146
 147         this_type & operator=(const this_type & x);
 148
 149         allocator_type get_allocator() const;
 150
 151         // size and capacity
 152
 153         bool      empty() const;
 154         size_type size() const;
 155         size_type max_size() const;
 156
 157         // iterators
 158
 159         iterator       begin();
 160         const_iterator begin() const;
 161         iterator       end();
 162         const_iterator end() const;
 163
 164         // modifiers
 165
 166         std::pair< iterator, bool > ``[link reference_unordered_set_of_insert_value insert]``(const value_type & x);
 167
 168         iterator ``[link reference_unordered_set_of_insert_iterator_value insert]``(iterator position, const value_type & x);
 169
 170         template< class InputIterator >
 171         void ``[link reference_unordered_set_of_insert_iterator_iterator insert]``(InputIterator first, InputIterator last);
 172
 173         iterator ``[link reference_unordered_set_of_erase_iterator erase]``(iterator position);
 174
 175         template< class CompatibleKey >
 176         size_type ``[link reference_unordered_set_of_erase_key erase]``(const CompatibleKey & x);
 177
 178         iterator ``[link reference_unordered_set_of_erase_iterator_iterator erase]``(iterator first, iterator last);
 179
 180         bool ``[link reference_unordered_set_of_replace_iterator_value replace]``(iterator position, const value_type & x);
 181
 182         // Only in map views
 183         // {
 184
 185           typedef ``['-unspecified-]`` mapped_type;
 186           typedef ``['-unspecified-]`` data_type; // Equal to mapped_type
 187
 188           template< class CompatibleKey >
 189           bool ``[link reference_unordered_set_of_replace_key_iterator_key replace_key]``(iterator position, const CompatibleKey & x);
 190
 191           template< class CompatibleData >
 192           bool ``[link reference_unordered_set_of_replace_data_iterator_data replace_data]``(iterator position, const CompatibleData & x);
 193
 194           template< class KeyModifier >
 195           bool ``[link reference_unordered_set_of_modify_key_iterator_modifier modify_key]``(iterator position, KeyModifier mod);
 196
 197           template< class DataModifier >
 198           bool ``[link reference_unordered_set_of_modify_data_iterator_modifier modify_data]``(iterator position, DataModifier mod);
 199
 200         // }
 201
 202
 203         void clear();
 204
 205         // observers
 206
 207         key_from_value key_extractor() const;
 208         hasher         hash_function() const;
 209         key_equal      key_eq() const;
 210
 211         // lookup
 212
 213         template< class CompatibleKey >
 214         iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x);
 215
 216         template< class CompatibleKey >
 217         const_iterator ``[link reference_unordered_set_of_find_key find]``(const CompatibleKey & x) const;
 218
 219         template< class CompatibleKey >
 220         size_type ``[link reference_unordered_set_of_count_key count]``(const CompatibleKey & x) const;
 221
 222         template< class CompatibleKey >
 223         std::pair<iterator,iterator>
 224             ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x);
 225
 226         template< class CompatibleKey >
 227         std::pair<const_iterator,const_iterator>
 228             ``[link reference_unordered_set_of_equal_range_key equal_range]``(const CompatibleKey & x) const;
 229
 230         // bucket interface
 231
 232         size_type bucket_count() const;
 233         size_type max_bucket_count() const;
 234         size_type bucket_size(size_type n) const;
 235         size_type bucket(const key_type & k) const;
 236
 237         local_iterator       begin(size_type n);
 238         const_local_iterator begin(size_type n) const;
 239         local_iterator       end(size_type n);
 240         const_local_iterator end(size_type n) const;
 241
 242         // hash policy
 243
 244         float load_factor() const;
 245         float max_load_factor() const;
 246         void  max_load_factor(float z);
 247         void  ``[link reference_unordered_set_of_rehash_size rehash]``(size_type n);
 248
 249         // Only in maps views
 250         // {
 251
 252         typedef ``['-unspecified-]`` mapped_type;
 253
 254           // Only in for `unordered_set_of` collection type
 255           // {
 256
 257           template<class CompatibleKey>
 258           const mapped_type & ``[link reference_unordered_set_of_at_key_const at]``(const CompatibleKey & k) const;
 259
 260             // Only if the other collection type is mutable
 261             // {
 262
 263             template<class CompatibleKey>
 264             mapped_type & ``[link reference_unordered_set_of_operator_bracket_key operator\[\]]``(const CompatibleKey & k);
 265
 266             template<class CompatibleKey>
 267             mapped_type & ``[link reference_unordered_set_of_at_key at]``(const CompatibleKey & k);
 268
 269             // }
 270
 271             // Only if info_hook is used
 272             // {
 273
 274             template< class CompatibleKey >
 275             info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k);
 276
 277             template< class CompatibleKey >
 278             const info_type & ``[link reference_unordered_set_of_info_at_key info_at]``(const CompatibleKey & k) const;
 279
 280           // }
 281
 282         // }
 283
 284     };
 285
 286     } // namespace views
 287     } // namespace bimap
 288     } // namespace boost
 289
 290
 291
 292 In the case of a `bimap< unordered_{multi}set_of<Left>, ... >`
 293
 294 In the set view:
 295
 296     typedef signature-compatible with relation<       Left, ... > key_type;
 297     typedef signature-compatible with relation< const Left, ... > value_type;
 298
 299 In the left map view:
 300
 301     typedef  Left  key_type;
 302     typedef  ...   mapped_type;
 303
 304     typedef signature-compatible with std::pair< const Left, ... > value_type;
 305
 306 In the right map view:
 307
 308     typedef  ...  key_type;
 309     typedef  Left mapped_type;
 310
 311     typedef signature-compatible with std::pair< ... ,const Left > value_type;
 312
 313
 314
 315 [#unordered_set_of_complexity_signature]
 316
 317 [section Complexity signature]
 318
 319 Here and in the descriptions of operations of `unordered_[multi]set_of` views,
 320 we adopt the scheme outlined in the
 321 [link complexity_signature_explanation complexity signature section].
 322 The complexity signature of `unordered_[multi]set_of` view is:
 323
 324 * copying: `c(n) = n * log(n)`,
 325 * insertion: average case `i(n) = 1` (constant), worst case `i(n) = n`,
 326 * hinted insertion: average case `h(n) = 1` (constant), worst case `h(n) = n`,
 327 * deletion: average case `d(n) = 1` (constant), worst case `d(n) = n`,
 328 * replacement:
 329     * if the new element key is equivalent to the original, `r(n) = 1` (constant),
 330     * otherwise, average case `r(n) = 1` (constant), worst case `r(n) = n`,
 331 * modifying: average case `m(n) = 1` (constant), worst case `m(n) = n`.
 332
 333 [endsect]
 334
 335
 336 [section Instantiation types]
 337
 338 `unordered_[multi]set_of` views are instantiated internally to `bimap`
 339 specified by means of the collection type specifiers and the `bimap` itself.
 340 Instantiations are dependent on the following types:
 341
 342 * `Value` from `bimap`,
 343 * `Allocator` from `bimap`,
 344 * `Hash` from the collection type specifier,
 345 * `Pred` from the collection type specifier.
 346
 347 `Hash` is a __SGI_UNARY_FUNCTION__ taking a single argument of type
 348 `key_type` and returning a value of type `std::size_t` in the range
 349 `[0, std::numeric_limits<std::size_t>::max())`.
 350 Pred is a __SGI_BINARY_PREDICATE__ inducing an equivalence relation on elements of
 351 `key_type`. It is required that the `Hash` object return the same value for
 352 keys equivalent under `Pred`.
 353
 354 [endsect]
 355
 356 [section Nested types]
 357
 358     iterator
 359     const_iterator
 360     local_iterator
 361     const_local_iterator
 362
 363 [:  These types are models of __SGI_FORWARD_ITERATOR__.
 364 ]
 365
 366
 367 [endsect]
 368
 369 [section Constructors, copy and assignment]
 370
 371 As explained in the concepts section,
 372 views do not have public constructors or destructors. Assignment, on the other
 373 hand, is provided.
 374 Upon construction, `max_load_factor()` is 1.0.
 375
 376     this_type & operator=(const this_type & x);
 377
 378 * [*Effects: ] `a = b`;
 379 where a and b are the `bimap` objects to which `*this`
 380 and x belong, respectively.
 381 * [*Returns: ] `*this.`
 382
 383
 384
 385 [endsect]
 386
 387 [section Modifiers]
 388
 389 [#reference_unordered_set_of_insert_value]
 390
 391     std::pair<iterator,bool> insert(const value_type & x);
 392
 393 * [*Effects:] Inserts `x` into the `bimap` to which the view belongs if
 394     * the view is non-unique OR no other element with equivalent key exists,
 395     * AND insertion is allowed by all other views of the `bimap`.
 396 * [*Returns:] The return value is a pair `p`. `p.second` is `true` if and only if
 397 insertion took place. On successful insertion, `p.first` points to the element
 398 inserted; otherwise, `p.first` points to an element that caused the insertion to
 399 be banned. Note that more than one element can be causing insertion not to be
 400 allowed.
 401 * [link unordered_set_of_complexity_signature
 402 [*Complexity:]] O(I(n)).
 403 * [*Exception safety:] Strong.
 404
 405 [#reference_unordered_set_of_insert_iterator_value]
 406
 407     iterator insert(iterator position, const value_type & x);
 408
 409 * [*Requires: ] `position` is a valid iterator of the view.
 410 * [*Effects: ] `position` is used as a hint to improve the efficiency of the operation.
 411 Inserts `x` into the `bimap` to which the view belongs if
 412     * the view is non-unique OR no other element with equivalent key exists,
 413     * AND insertion is allowed by all other views of the `bimap`.
 414 * [*Returns:] On successful insertion, an iterator to the newly inserted element.
 415 Otherwise, an iterator to an element that caused the insertion to be banned.
 416 Note that more than one element can be causing insertion not to be allowed.
 417 * [link unordered_set_of_complexity_signature [*Complexity:]] O(H(n)).
 418 * [*Exception safety:] Strong.
 419
 420 [#reference_unordered_set_of_insert_iterator_iterator]
 421
 422     template< class InputIterator>
 423     void insert(InputIterator first, InputIterator last);
 424
 425 * [*Requires: ] `InputIterator` is a model of __SGI_INPUT_ITERATOR__ over elements of type
 426 `value_type`. `first` and `last` are not iterators into any views of the
 427 `bimap` to which this view belongs. `last` is reachable from first.
 428 * [*Effects: ]
 429 `iterator hint = end();`
 430 `while(first != last) hint = insert(hint, *first++);`
 431 * [link unordered_set_of_complexity_signature
 432 [*Complexity:]] O(m*H(n+m)), where m is the number of elements in `[first, last)`.
 433 * [*Exception safety:] Basic.
 434
 435 [#reference_unordered_set_of_erase_iterator]
 436
 437     iterator erase(iterator position);
 438
 439 * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view.
 440 * [*Effects:] Deletes the element pointed to by `position`.
 441 * [*Returns:] An `iterator` pointing to the element immediately following the one
 442 that was deleted, or `end()` if no such element exists.
 443 * [link unordered_set_of_complexity_signature
 444 [*Complexity:]] O(D(n)).
 445 * [*Exception safety:] nothrow.
 446
 447
 448 [#reference_unordered_set_of_erase_key]
 449
 450     template< class CompatibleKey >
 451     size_type erase(const CompatibleKey & x);
 452
 453 * [*Effects:] Deletes the elements with key equivalent to `x`.
 454 * [*Returns:] Number of elements deleted.
 455 * [link unordered_set_of_complexity_signature
 456 [*Complexity:]] Average case, O(1 + m*D(n)), worst case O(n + m*D(n)),
 457 where m is the number of elements deleted.
 458 * [*Exception safety:] Basic.
 459
 460
 461 [#reference_unordered_set_of_erase_iterator_iterator]
 462
 463     iterator erase(iterator first, iterator last);
 464
 465 * [*Requires: ] `[first,last)` is a valid range of the view.
 466 * [*Effects:] Deletes the elements in `[first,last)`.
 467 * [*Returns: ] `last`.
 468 * [link unordered_set_of_complexity_signature
 469 [*Complexity:]] O(m*D(n)), where m is the number of elements in `[first,last)`.
 470 * [*Exception safety:] nothrow.
 471
 472
 473 [#reference_unordered_set_of_replace_iterator_value]
 474
 475     bool replace(iterator position, const value_type & x);
 476
 477 * [*Requires: ] `position` is a valid dereferenceable `iterator` of the view.
 478 * [*Effects:] Assigns the value `x` to the element pointed to by `position` into
 479 the `bimap` to which the view belongs if, for the value `x`
 480     * the view is non-unique OR no other element with equivalent key exists
 481 (except possibly `*position`),
 482     * AND replacing is allowed by all other views of the `bimap`.
 483 * [*Postconditions:] Validity of position is preserved in all cases.
 484 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 485 * [link unordered_set_of_complexity_signature
 486 [*Complexity:]] O(R(n)).
 487 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 488 operation the `bimap` to which the view belongs remains in its original state.
 489
 490
 491 [#reference_unordered_set_of_replace_key_iterator_key]
 492
 493     template< class CompatibleKey >
 494     bool replace_key(iterator position, const CompatibleKey & x);
 495
 496 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 497 `CompatibleKey` can be assigned to `key_type`.
 498 * [*Effects:] Assigns the value `x` to `e.first`, where `e` is the element pointed
 499 to by `position` into the `bimap` to which the set view belongs if,
 500     * the map view is non-unique OR no other element with equivalent key exists
 501 (except possibly `*position`),
 502     * AND replacing is allowed by all other views of the `bimap`.
 503 * [*Postconditions:] Validity of position is preserved in all cases.
 504 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 505 * [link unordered_set_of_complexity_signature
 506 [*Complexity:]] O(R(n)).
 507 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 508 operation, the `bimap` to which the set view belongs remains in
 509 its original state.
 510
 511
 512 [#reference_unordered_set_of_replace_data_iterator_data]
 513
 514     template< class CompatibleData >
 515     bool replace_data(iterator position, const CompatibleData & x);
 516
 517 * [*Requires: ] `position` is a valid dereferenceable iterator of the set view.
 518 `CompatibleKey` can be assigned to `mapped_type`.
 519 * [*Effects:] Assigns the value `x` to `e.second`, where `e` is the element pointed
 520 to by `position` into the `bimap` to which the set view belongs if,
 521     * the map view is non-unique OR no other element with equivalent key exists
 522 (except possibly `*position`),
 523     * AND replacing is allowed by all other views of the `bimap`.
 524 * [*Postconditions:] Validity of position is preserved in all cases.
 525 * [*Returns: ] `true` if the replacement took place, `false` otherwise.
 526 * [link unordered_set_of_complexity_signature
 527 [*Complexity:]] O(R(n)).
 528 * [*Exception safety:] Strong. If an exception is thrown by some user-provided
 529 operation, the `bimap` to which the set view belongs remains in
 530 its original state.
 531
 532
 533 [#reference_unordered_set_of_modify_key_iterator_modifier]
 534
 535     template< class KeyModifier >
 536     bool modify_key(iterator position, KeyModifier mod);
 537
 538 * [*Requires: ] `KeyModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
 539 type: `key_type&`; `position` is a valid dereferenceable iterator of the view.
 540 * [*Effects:] Calls `mod(e.first)` where e is the element pointed to by position and
 541 rearranges `*position` into all the views of the `bimap`.
 542 If the rearrangement fails, the element is erased.
 543 Rearrangement is successful if
 544     * the map view is non-unique OR no other element with equivalent key exists,
 545     * AND rearrangement is allowed by all other views of the `bimap`.
 546 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 547 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 548 * [link unordered_set_of_complexity_signature
 549 [*Complexity:]] O(M(n)).
 550 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 551 operation (except possibly mod), then the element pointed to by position is erased.
 552 * [*Note:] Only provided for map views.
 553
 554
 555 [#reference_unordered_set_of_modify_data_iterator_modifier]
 556
 557     template< class DataModifier >
 558     bool modify_data(iterator position, DataModifier mod);
 559
 560 * [*Requires: ] `DataModifier` is a model of __SGI_UNARY_FUNCTION__ accepting arguments of
 561 type: `mapped_type&`; `position` is a valid dereferenceable iterator of the view.
 562 * [*Effects:] Calls `mod(e.second)` where e is the element pointed to by position and
 563 rearranges `*position` into all the views of the `bimap`.
 564 If the rearrangement fails, the element is erased.
 565 Rearrangement is successful if
 566     * the oppositte map view is non-unique OR no other element with equivalent key in that
 567 view exists,
 568     * AND rearrangement is allowed by all other views of the `bimap`.
 569 * [*Postconditions:] Validity of `position` is preserved if the operation succeeds.
 570 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 571 * [link unordered_set_of_complexity_signature
 572 [*Complexity:]] O(M(n)).
 573 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 574 operation (except possibly mod), then the element pointed to by position is erased.
 575 * [*Note:] Only provided for map views.
 576
 577 [/
 578 [#reference_unordered_set_of_modify_iterator_modifier]
 579
 580     template< class Modifier>
 581     bool modify(iterator position, Modifier mod);
 582
 583 * [*Requires: ] `Modifier` is a model of __SGI_BINARY_FUNCTION__ accepting arguments of
 584 type: `first_type&` and `second_type&` for ['Map View] or `left_type&` and `right_type&`
 585 for ['Set View]; `position` is a valid dereferenceable iterator of the view.
 586 * [*Effects:] Calls `mod(e.first,e.second)` for ['Map View:] or calls `mod(e.left,e.right)`
 587 for ['Set View] where `e` is the element pointed to by `position` and
 588 rearranges `*position` into all the views of the `bimap`.
 589 If the rearrangement fails, the element is erased.
 590 Rearrangement is successful if
 591     * the view is non-unique OR no other element with equivalent key exists,
 592     * AND rearrangement is allowed by all other views of the `bimap`.
 593 * [*Postconditions:] Validity of position is preserved if the operation succeeds.
 594 * [*Returns: ] `true` if the operation succeeded, `false` otherwise.
 595 * [link unordered_set_of_complexity_signature
 596 [*Complexity:]] O(M(n)).
 597 * [*Exception safety:] Basic. If an exception is thrown by some user-provided
 598 operation (except possibly `mod`), then the element pointed to by `position` is erased.
 599 /]
 600
 601 [endsect]
 602
 603 [section Lookup]
 604
 605 `unordered_[multi]set_of` views provide the full lookup functionality required by unordered
 606 associative containers, namely `find`, `count`, and `equal_range`. Additionally,
 607 these member functions are templatized to allow for non-standard arguments,
 608 so extending the types of search operations allowed. The kind of arguments
 609 permissible when invoking the lookup member functions is defined by the
 610 following concept.
 611
 612 [/
 613 Consider a pair `(Hash, Pred)` where `Hash` is a hash functor over values of type
 614 `Key` and `Pred` is a __SGI_BINARY_PREDICATE__ inducing an equivalence relation on `Key`,
 615 with the additional constraint that equivalent keys have the same hash value.
 616 A triplet of types `(CompatibleKey, CompatibleHash, CompatiblePred)` is said to
 617 be a ['compatible extension] of `(Hash, Pred)` if
 618
 619 * `CompatibleHash` is a hash functor on values of type `CompatibleKey`,
 620 * `CompatiblePred` is a __SGI_BINARY_PREDICATE__ over `(Key, CompatibleKey)`,
 621 * `CompatiblePred` is a __SGI_BINARY_PREDICATE__ over `(CompatibleKey, Key)`,
 622 * if `c_eq(ck,k1)` then `c_eq(k1,ck)`,
 623 * if `c_eq(ck,k1)` and `eq(k1,k2)` then `c_eq(ck,k2)`,
 624 * if `c_eq(ck,k1)` and `c_eq(ck,k2)` then `eq(k1,k2)`,
 625 * if `c_eq(ck,k1)` then `c_hash(ck)==hash(k1)`,
 626
 627 for every `c_hash` of type `CompatibleHash`, `c_eq` of type `CompatiblePred`, hash of
 628 type `Hash`, `eq` of type `Pred`, `ck` of type `CompatibleKey` and `k1`, `k2` of type `Key`.
 629 ]
 630
 631 A type `CompatibleKey` is said to be a ['compatible key] of `(Hash, Pred)`
 632 if `(CompatibleKey, Hash, Pred)` is a compatible extension of `(Hash, Pred)`. This
 633 implies that `Hash` and `Pred` accept arguments of type `CompatibleKey`, which usually
 634 means they have several overloads of their corresponding `operator()` member
 635 functions.
 636
 637 [/
 638 In the context of a compatible extension or a compatible key, the expression
 639 "equivalent key" takes on its obvious interpretation.
 640 ]
 641
 642 [#reference_unordered_set_of_find_key]
 643
 644     template< class CompatibleKey >
 645     iterator find(const CompatibleKey & x);
 646
 647     template< class CompatibleKey >
 648     const_iterator find(const CompatibleKey & x) const;
 649
 650 * [*Effects:] Returns a pointer to an element whose key is equivalent to `x`,
 651 or `end()` if such an element does not exist.
 652 * [*Complexity:] Average case O(1) (constant), worst case O(n).
 653
 654
 655 [#reference_unordered_set_of_count_key]
 656
 657     template< class CompatibleKey >
 658     size_type count(const CompatibleKey & x) const;
 659
 660 * [*Effects:] Returns the number of elements with key equivalent to `x`.
 661 * [*Complexity:] Average case O(count(x)), worst case O(n).
 662
 663
 664 [#reference_unordered_set_of_equal_range_key]
 665
 666     template< class CompatibleKey >
 667     std::pair<iterator,iterator>
 668         equal_range(const CompatibleKey & x);
 669
 670     template< class CompatibleKey >
 671     std::pair<const_iterator,const_iterator>
 672         equal_range(const CompatibleKey & x) const;
 673
 674 * [*Effects:] Returns a range containing all elements with keys equivalent
 675 to `x` (and only those).
 676 * [*Complexity:] Average case O(count(x)), worst case O(n).
 677
 678
 679
 680 [endsect]
 681
 682 [section at(), info_at() and operator\[\] - set_of only]
 683
 684
 685 [#reference_unordered_set_of_at_key_const]
 686
 687     template< class CompatibleKey >
 688     const mapped_type & at(const CompatibleKey & k) const;
 689
 690 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 691 * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or
 692 throws `std::out_of_range` if such key does not exist.
 693 * [*Complexity:] Average case O(1) (constant), worst case O(n).
 694 * [*Note:] Only provided when `unordered_set_of` is used.
 695
 696 The symmetry of bimap imposes some constraints on `operator[]` and the
 697 non constant version of at() that are not found in `std::maps`.
 698 Tey are only provided if the other collection type is mutable
 699 (`list_of`, `vector_of` and `unconstrained_set_of`).
 700
 701
 702 [#reference_unordered_set_of_operator_bracket_key]
 703
 704     template< class CompatibleKey >
 705     mapped_type & operator[](const CompatibleKey & k);
 706
 707 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 708 * [*Effects: ] `return insert(value_type(k,mapped_type()))->second;`
 709 * [*Complexity:] If the insertion is performed O(I(n)), else: Average case
 710 O(1) (constant), worst case O(n).
 711 * [*Note:] Only provided when `unordered_set_of` is used and the other collection
 712 type is mutable.
 713
 714
 715 [#reference_unordered_set_of_at_key]
 716
 717     template< class CompatibleKey >
 718     mapped_type & at(const CompatibleKey & k);
 719
 720 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 721 * [*Effects: ] Returns the `mapped_type` reference that is associated with `k`, or
 722 throws `std::out_of_range` if such key does not exist.
 723 * [*Complexity:] Average case O(1) (constant), worst case O(n).
 724 * [*Note:] Only provided when `unordered_set_of` is used and the other collection
 725 type is mutable.
 726
 727 [/
 728
 729 The symmetry of bimap imposes some constraints to the `operator[]` that are not
 730 found in `std::maps`.
 731 If other views are unique, `bimap::duplicate_value` is thrown whenever an assignment is
 732 attempted to a value that is already a key in this views.
 733 As for bimap::value_not_found, this exception is thrown while trying to access
 734 a non-existent key: this behavior differs from that of std::map, which automatically
 735 assigns a default value to non-existent keys referred to by `operator[]`.
 736
 737     const mapped_type & operator[](const typename key_type & k) const;
 738
 739 * [*Effects:] Returns the `mapped_type` reference that is associated with `k`, or
 740 throws `bimap::value_not_found` if such an element does not exist.
 741 * [*Complexity:] O(log(n)).
 742
 743
 744     ``['-unspecified mapped_type proxy-]`` operator[](const typename key_type & k);
 745
 746 * [*Effects:] Returns a proxy to a `mapped_type` associated with `k` and the
 747 bimap. The proxy behaves as a reference to the `mapped_type` object. If this
 748 proxy is read and `k` was not in the bimap, the bimap::value_not_found is
 749 thrown. If it is written then `bimap::duplicate_value` is thrown if the
 750 assignment is not allowed by one of the other views of the `bimap`.
 751 * [link unordered_set_of_complexity_signature
 752 [*Complexity:]] If the assignment operator of the proxy is not used, then
 753 the order is O(log(n)). If it is used, the order is O(I(n)) if `k` was not
 754 in the bimap and O(R(n)) if it existed in the bimap.
 755
 756 ]
 757
 758 [#reference_unordered_set_of_info_at_key]
 759
 760     template< class CompatibleKey >
 761     info_type & info_at(const CompatibleKey & k);
 762
 763     template< class CompatibleKey >
 764     const info_type & info_at(const CompatibleKey & k) const;
 765
 766 * [*Requires: ] `CompatibleKey` is a compatible key of `key_compare`.
 767 * [*Effects:] Returns the `info_type` reference that is associated with `k`, or
 768 throws `std::out_of_range` if such key does not exist.
 769 * [*Complexity:] Average case O(1) (constant), worst case O(n).
 770 * [*Note:] Only provided when `unordered_set_of` and `info_hook` are used
 771
 772
 773 [endsect]
 774
 775 [section Hash policy]
 776
 777
 778 [#reference_unordered_set_of_rehash_size]
 779
 780     void rehash(size_type n);
 781
 782 * [*Effects:] Increases if necessary the number of internal buckets so that
 783 `size()/bucket_count()` does not exceed the maximum load factor, and
 784 `bucket_count()>=n`.
 785 * [*Postconditions:] Validity of iterators and references to the elements
 786 contained is preserved.
 787 * [*Complexity:] Average case O(size()), worst case O(size(n)2).
 788 * [*Exception safety:] Strong.
 789
 790
 791 [endsect]
 792
 793 [section Serialization]
 794
 795 Views cannot be serialized on their own, but only as part of the
 796 `bimap` into which they are embedded. In describing the
 797 additional preconditions and guarantees associated to `unordered_[multi]set_of` views
 798 with respect to serialization of their embedding containers, we use
 799 the concepts defined in the `bimap` serialization section.
 800
 801 [blurb [*Operation:] saving of a `bimap` b to an output archive
 802 (XML archive) ar.]
 803
 804 * [*Requires:] No additional requirements to those imposed by the container.
 805
 806
 807 [blurb [*Operation:] loading of a `bimap` b' from an input
 808 archive (XML archive) ar.]
 809
 810 * [*Requires:] Additionally to the general requirements, `key_eq()` must
 811 be serialization-compatible with `m.get<i>().key_eq()`, where i is the
 812 position of the `unordered_[multi]set_of` view in the container.
 813 * [*Postconditions:] On successful loading, the range `[begin(), end())`
 814 contains restored copies of every element in
 815 `[m.get<i>().begin(), m.get<i>().end())`, though not necessarily in
 816 the same order.
 817
 818
 819 [blurb  [*Operation:] saving of an `iterator` or `const_iterator` `it` to an output
 820 archive (XML archive) ar.]
 821
 822 * [*Requires: ] `it` is a valid `iterator` of the view. The associated
 823 `bimap` has been previously saved.
 824
 825
 826 [blurb [*Operation:] loading of an iterator or `const_iterator it`' from an
 827 input archive (XML archive) ar.]
 828
 829 * [*Postconditions:] On successful loading, if `it` was dereferenceable then
 830 `*it`' is the restored copy of `*it`, otherwise `it`'` == end()`.
 831 * [*Note:] It is allowed that `it` be a `const_iterator` and the restored
 832 `it`' an `iterator`, or viceversa.
 833
 834
 835 [blurb [*Operation:] saving of a local_iterator or const_local_iterator it
 836 to an output archive (XML archive) ar.]
 837
 838 * [*Requires: ] `it` is a valid local iterator of the view. The associated
 839 `bimap` has been previously saved.
 840
 841
 842 [blurb [*Operation:] loading of a `local_iterator` or `const_local_iterator`
 843 `it`' from an input archive (XML archive) ar.]
 844
 845 * [*Postconditions:] On successful loading, if `it` was dereferenceable then
 846 `*it`' is the restored copy of `*it`; if `it` was `m.get<i>().end(n)` for some n,
 847 then `it`'` == m`'`.get<i>().end(n)` (where `b` is the original `bimap`,
 848 `b`' its restored copy and `i` is the ordinal of the index.)
 849 * [*Note:] It is allowed that `it` be a `const_local_iterator` and the restored
 850 `it`' a `local_iterator`, or viceversa.
 851
 852
 853 [endsect]
 854 [endsect]
 855
 856 [endsect]