1[/license 2 3Boost.Bimap 4 5Copyright (c) 2006-2007 Matias Capeletto 6 7Distributed under the Boost Software License, Version 1.0. 8(See accompanying file LICENSE_1_0.txt or copy at 9http://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 75These collection type specifiers allow for insertion of sets disallowing or 76allowing 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 84A \[multi\]set_of set view is a std::\[multi\]set signature-compatible 85interface to the underlying heap of elements contained in a `bimap`. 86 87There are two variants: set_of, which does not allow duplicate elements 88(with respect to its associated comparison predicate) and multiset_of, 89which does accept those duplicates. The interface of these two variants 90is largely the same, so they are documented together with their 91differences explicitly noted where they exist. 92 93If you look the bimap from a side, you will use a map view, and if you 94look 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 337In the case of a `bimap< {multi}set_of<Left>, ... >` 338 339In the set view: 340 341 typedef signature-compatible with relation< Left, ... > key_type; 342 typedef signature-compatible with relation< const Left, ... > value_type; 343 344In 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 351In 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 363Here and in the descriptions of operations of this view, we adopt the 364scheme outlined in the [link complexity_signature_explanation complexity signature section]. 365The 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 370insertion, `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 381Set views are instantiated internally to a `bimap`. 382Instantiations 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 394Set views do not have public constructors or destructors. 395Assignment, on the other hand, is provided. 396 397 this_type & operator=(const this_type & x); 398 399* [*Effects: ] `a = b;` 400where a and b are the `bimap` objects to which `*this` and x 401belong, 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 418took place. On successful insertion, `p.first` points to the element inserted; 419otherwise, `p.first` points to an element that caused the insertion to be banned. 420Note 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 435element. Otherwise, an iterator to an element that caused the insertion to be 436banned. 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 448type `value_type` or a type convertible to value_type. `first` and `last` are not 449iterators into any view of the `bimap` to which this index 450belongs. `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 467the 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 495in `[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 505the `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 514operation, the `bimap` to which the set view belongs remains in 515its 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 526to 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 535operation, the `bimap` to which the set view belongs remains in 536its 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 547to 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 556operation, the `bimap` to which the set view belongs remains in 557its 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 566type: `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 568rearranges `*position` into all the views of the `bimap`. 569If the rearrangement fails, the element is erased. 570Rearrangement 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 578operation (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 588type: `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 590rearranges `*position` into all the views of the `bimap`. 591If the rearrangement fails, the element is erased. 592Rearrangement is successful if 593 * the oppositte map view is non-unique OR no other element with equivalent key in that 594view 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 601operation (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 612type: `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)` 615for ['Set View] where e is the element pointed to by position and rearranges `*position` 616into all the views of the `bimap`. 617If the rearrangement fails, the element is erased. 618Rearrangement 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 626operation (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__, 636namely `find`, `count`, `lower_bound`, `upper_bound` and `equal_range`. 637Additionally, these member functions are templatized to allow for non-standard 638arguments, so extending the types of search operations allowed. 639 640[/ 641The kinds of arguments permissible when invoking the lookup member functions 642are defined by the following concept. 643 644Consider a __SGI_STRICT_WEAK_ORDERING__ `Compare` over values of type `Key`. A pair of 645types `(CompatibleKey, CompatibleCompare)` is said to be a ['compatible extension] 646of 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 654for every `c_comp` of type `CompatibleCompare`, `comp` of type `Compare`, `ck` of type 655`CompatibleKey` and `k1`, `k2` of type `Key`. 656] 657A type `CompatibleKey` is said to be a ['compatible key] of `Compare` 658if `(CompatibleKey, Compare)` is a compatible extension of `Compare`. This implies 659that `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[/ 663In 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 692equivalent 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 726less 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 740than `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 764The member function range is not defined for sorted associative 765containers, but `[multi]set_of` map views provide it as a convenient utility. 766A range or interval is defined by two conditions for the lower and upper 767bounds, which are modelled after the following concepts. 768 769Consider a __SGI_STRICT_WEAK_ORDERING__ `Compare` over values of type Key. 770A 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 775for every `lower` of type `LowerBounder`, `comp` of type `Compare`, and `k1`, `k2` 776of type `Key`. 777Similarly, 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 782for every `upper` of type `UpperBounder`, `comp` of type `Compare`, and `k1`, `k2` 783of 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 794the beginning and one past the end of the subsequence of elements satisfying 795lower and upper simultaneously. If no such elements exist, the iterators both 796point to the first element satisfying lower, or else are equal to `end()` if this 797latter 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 801all 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 815throws `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 819The symmetry of bimap imposes some constraints on `operator[]` and the 820non constant version of at() that are not found in `std::maps`. 821They 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 833type 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 842throws `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 845type is mutable. 846 847[/ 848The symmetry of bimap imposes some constraints on `operator[]` that are 849not found in `std::maps`. If other views are unique, 850`bimap::duplicate_value` is thrown whenever an assignment is attempted to 851a value that is already a key in these views. As for 852`bimap::value_not_found`, this exception is thrown while trying to access 853a non-existent key: this behaviour differs from that of `std::map`, which 854automatically assigns a default value to non-existent keys referred to 855by `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 860throws `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 867bimap. The proxy behaves as a reference to the `mapped_type` object. If this 868proxy is read and `k` was not in the bimap, the bimap::value_not_found is 869thrown. If it is written then `bimap::duplicate_value` is thrown if the 870assignment 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 873the order is O(log(n)). If it is used, the order is O(I(n)) if `k` was not 874in 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 888throws `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 897Views cannot be serialized on their own, but only as part of the `bimap` 898into which they are embedded. In describing the additional preconditions and guarantees 899associated to `[multi]set_of` views with respect to serialization of their embedding containers, 900we 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 910serialization-compatible with `m.get<i>().value_comp()`, where i is the position 911of the ordered view in the container. 912* [*Postconditions:] On successful loading, each of the elements of `[begin(), end())` 913is 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` 921has been previously saved. 922 923 924[blurb [*Operation:] loading of an `iterator` or `const_iterator` `it`' from an input archive ( 925XML archive) ar.] 926 927* [*Postconditions:] On successful loading, if it was dereferenceable then `*it`' is the 928restored copy of `*it`, otherwise `it`'` == end()`. 929* [*Note:] It is allowed that it be a `const_iterator` and the restored `it`' an iterator, 930or viceversa. 931 932 933[endsect] 934[endsect] 935 936[endsect]