boost/intrusive/iunordered_set.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Olaf Krzikalla 2004-2006.\r
   4 // (C) Copyright Ion Gaztañaga  2006-2007\r
   5 //\r
   6 // Distributed under the Boost Software License, Version 1.0.\r
   7 //    (See accompanying file LICENSE_1_0.txt or copy at\r
   8 //          http://www.boost.org/LICENSE_1_0.txt)\r
   9 //\r
  10 // See http://www.boost.org/libs/intrusive for documentation.\r
  11 //\r
  12 /////////////////////////////////////////////////////////////////////////////\r
  13 #ifndef BOOST_INTRUSIVE_IHASHSET_HPP\r
  14 #define BOOST_INTRUSIVE_IHASHSET_HPP\r
  15 \r
  16 #include <boost/intrusive/detail/config_begin.hpp>\r
  17 #include <boost/intrusive/detail/ihashtable.hpp>\r
  18 #include <iterator>\r
  19 \r
  20 namespace boost {\r
  21 namespace intrusive {\r
  22 \r
  23 //! The class template iunordered_set is an intrusive container, that mimics most of \r
  24 //! the interface of std::tr1::unordered_set as described in the C++ TR1.\r
  25 //!\r
  26 //! iunordered_set is a pseudo-intrusive container: each object to be stored in the\r
  27 //! container must contain a proper hook, but the container also needs\r
  28 //! additional auxiliary memory to work: iunordered_set needs a pointer to an array\r
  29 //! of type `bucket_type` to be passed in the constructor. This bucket array must\r
  30 //! have at least the same lifetime as the container. This makes the use of\r
  31 //! iunordered_set more complicated than purely intrusive containers.\r
  32 //! `bucket_type` is default-constructible, copyable and assignable\r
  33 //!\r
  34 //! The template parameter ValueTraits is called "value traits". It stores\r
  35 //! information and operations about the type to be stored in the container.\r
  36 //!\r
  37 //! The template parameter Hash is a unary function object that take an argument\r
  38 //!   of type ValueTraits::value_type and returns a value of type std::size_t.\r
  39 //!\r
  40 //! The template parameter Equal is a binary predicate that takes two arguments of\r
  41 //!   type ValueTraits::value_type. Equal is an equivalence relation.\r
  42 //!\r
  43 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType\r
  44 //! will be embedded in the class, that will keep track of the number of stored objects.\r
  45 //! This will allow constant-time O(1) size() member, instead of default O(N) size.\r
  46 //!\r
  47 //! iunordered_set only provides forward iterators but it provides 4 iterator types:\r
  48 //! iterator and const_iterator to navigate through the whole container and\r
  49 //! local_iterator and const_local_iterator to navigate through the values\r
  50 //! stored in a single bucket. Local iterators are faster and smaller.\r
  51 //!\r
  52 //! It's not recommended to use non ConstantTimeSize iunordered_sets because several\r
  53 //! key functions, like "empty()", become non-constant time functions. Non\r
  54 //! ConstantTimeSize iunordered_sets are mainly provided to support auto-unlink hooks.\r
  55 //!\r
  56 //! iunordered_set, unlike std::unordered_set, does not make automatic rehashings nor\r
  57 //! offers functions related to a load factor. Rehashing can be explicitly requested\r
  58 //! and the user must provide a new bucket array that will be used from that moment.\r
  59 //!\r
  60 //! Since no automatic rehashing is done, iterators are never invalidated when\r
  61 //! inserting or erasing elements. Iterators are only invalidated when rehasing.\r
  62 template< class ValueTraits\r
  63         , class Hash             = boost::hash<typename ValueTraits::value_type>\r
  64         , class Equal            = std::equal_to<typename ValueTraits::value_type>\r
  65         , bool  ConstantTimeSize = true\r
  66         , class SizeType         = std::size_t\r
  67         >\r
  68 class iunordered_set\r
  69 {\r
  70    private:\r
  71    typedef detail::ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType> table_type;\r
  72 \r
  73    //! This class is\r
  74    //! non-copyable\r
  75    iunordered_set (const iunordered_set&);\r
  76 \r
  77    //! This class is\r
  78    //! non-assignable\r
  79    iunordered_set &operator =(const iunordered_set&);\r
  80 \r
  81    typedef table_type implementation_defined;\r
  82 \r
  83    public:\r
  84    typedef typename ValueTraits::value_type                             value_type;\r
  85    typedef typename ValueTraits::pointer                                pointer;\r
  86    typedef typename ValueTraits::const_pointer                          const_pointer;\r
  87    typedef value_type&                                                  reference;\r
  88    typedef const value_type&                                            const_reference;\r
  89    typedef SizeType                                                     size_type;\r
  90    typedef typename std::iterator_traits<pointer>::difference_type      difference_type;\r
  91    typedef value_type                                                   key_type;\r
  92    typedef Equal                                                        key_equal;\r
  93    typedef Hash                                                         hasher;\r
  94    typedef typename implementation_defined::bucket_type                 bucket_type;\r
  95    typedef typename boost::pointer_to_other<pointer, bucket_type>::type bucket_ptr;\r
  96    typedef typename implementation_defined::iterator                    iterator;\r
  97    typedef typename implementation_defined::const_iterator              const_iterator;\r
  98    typedef typename implementation_defined::insert_commit_data          insert_commit_data;\r
  99    typedef typename implementation_defined::local_iterator              local_iterator;\r
 100    typedef typename implementation_defined::const_local_iterator        const_local_iterator;\r
 101 \r
 102    private:\r
 103    table_type table_;\r
 104 \r
 105    public:\r
 106 \r
 107    //! <b>Requires</b>: buckets must not be being used by any other resource.\r
 108    //!\r
 109    //! <b>Effects</b>: Constructs an empty iunordered_set, storing a reference\r
 110    //!   to the bucket array and copies of the hasher and equal functors.\r
 111    //!   \r
 112    //! <b>Complexity</b>: Constant. \r
 113    //! \r
 114    //! <b>Throws</b>: If value_traits::node_traits::node\r
 115    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
 116    //!   or the copy constructor or invocation of Hash or Equal throws. \r
 117    //!\r
 118    //! <b>Notes</b>: buckets array must be destroyed only after\r
 119    //!   *this is destroyed. \r
 120    iunordered_set( bucket_ptr buckets\r
 121            , size_type buckets_len\r
 122            , const Hash & hasher = Hash()\r
 123            , const Equal &equal = Equal()) \r
 124       :  table_(buckets, buckets_len, hasher, equal)\r
 125    {}\r
 126 \r
 127    //! <b>Requires</b>: buckets must not be being used by any other resource\r
 128    //!   and Dereferencing iterator must yield an lvalue of type value_type.\r
 129    //! \r
 130    //! <b>Effects</b>: Constructs an empty iunordered_set and inserts elements from \r
 131    //!   [b, e).\r
 132    //!   \r
 133    //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)\r
 134    //!   (with a good hash function and with buckets_len >= N),worst case O(N2).\r
 135    //! \r
 136    //! <b>Throws</b>: If value_traits::node_traits::node\r
 137    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
 138    //!   or the copy constructor or invocation of Hash or Equal throws. \r
 139    //!\r
 140    //! <b>Notes</b>: buckets array must be destroyed only after\r
 141    //!   *this is destroyed. \r
 142    template<class Iterator>\r
 143    iunordered_set( bucket_ptr buckets\r
 144            , size_type buckets_len\r
 145            , Iterator b\r
 146            , Iterator e\r
 147            , const Hash & hasher = Hash()\r
 148            , const Equal &equal = Equal()) \r
 149       :  table_(buckets, buckets_len, hasher, equal)\r
 150    {  table_.insert_unique(b, e);  }\r
 151 \r
 152    //! <b>Effects</b>: Detaches all elements from this. The objects in the iunordered_set \r
 153    //!   are not deleted (i.e. no destructors are called).\r
 154    //! \r
 155    //! <b>Complexity</b>: Linear to the number of elements in the iunordered_set, if \r
 156    //!   it's a safe-mode or auto-unlink value. Otherwise constant.\r
 157    //! \r
 158    //! <b>Throws</b>: Nothing.\r
 159    ~iunordered_set() \r
 160    {}\r
 161 \r
 162    //! <b>Effects</b>: Returns an iterator pointing to the beginning of the iunordered_set.\r
 163    //! \r
 164    //! <b>Complexity</b>: Amortized constant time.\r
 165    //!   Worst case (empty iunordered_set): O(this->bucket_count())\r
 166    //! \r
 167    //! <b>Throws</b>: Nothing.\r
 168    iterator begin()\r
 169    { return table_.begin();  }\r
 170 \r
 171    //! <b>Effects</b>: Returns a const_iterator pointing to the beginning\r
 172    //!   of the iunordered_set.\r
 173    //!\r
 174    //! <b>Complexity</b>: Amortized constant time.\r
 175    //!   Worst case (empty iunordered_set): O(this->bucket_count())\r
 176    //! \r
 177    //! <b>Throws</b>: Nothing.\r
 178    const_iterator begin() const\r
 179    { return table_.begin();  }\r
 180 \r
 181    //! <b>Effects</b>: Returns an iterator pointing to the end of the iunordered_set.\r
 182    //! \r
 183    //! <b>Complexity</b>: Constant.\r
 184    //! \r
 185    //! <b>Throws</b>: Nothing.\r
 186    iterator end()\r
 187    { return table_.end();  }\r
 188 \r
 189    //! <b>Effects</b>: Returns a const_iterator pointing to the end of the iunordered_set.\r
 190    //! \r
 191    //! <b>Complexity</b>: Constant.\r
 192    //! \r
 193    //! <b>Throws</b>: Nothing.\r
 194    const_iterator end() const\r
 195    { return table_.end();  }\r
 196 \r
 197    //! <b>Effects</b>: Returns the hasher object used by the iunordered_set.\r
 198    //! \r
 199    //! <b>Complexity</b>: Constant.\r
 200    //! \r
 201    //! <b>Throws</b>: If hasher copy-constructor throws.\r
 202    hasher hash_function() const\r
 203    { return table_.hash_function(); }\r
 204 \r
 205    //! <b>Effects</b>: Returns the key_equal object used by the iunordered_set.\r
 206    //! \r
 207    //! <b>Complexity</b>: Constant.\r
 208    //! \r
 209    //! <b>Throws</b>: If key_equal copy-constructor throws.\r
 210    key_equal key_eq() const\r
 211    { return table_.key_eq(); }\r
 212 \r
 213    //! <b>Effects</b>: Returns true is the container is empty.\r
 214    //! \r
 215    //! <b>Complexity</b>: if ConstantTimeSize is false, average constant time\r
 216    //!   (worst case, with empty() == true): O(this->bucket_count()).\r
 217    //!   Otherwise constant.\r
 218    //! \r
 219    //! <b>Throws</b>: Nothing.\r
 220    bool empty() const\r
 221    { return table_.empty(); }\r
 222 \r
 223    //! <b>Effects</b>: Returns the number of elements stored in the iunordered_set.\r
 224    //! \r
 225    //! <b>Complexity</b>: Linear to elements contained in *this if\r
 226    //!   ConstantTimeSize is false. Constant-time otherwise.\r
 227    //! \r
 228    //! <b>Throws</b>: Nothing.\r
 229    size_type size() const\r
 230    { return table_.size(); }\r
 231 \r
 232    //! <b>Requires</b>: the hasher and the equality function unqualified swap\r
 233    //!   call should not throw.\r
 234    //! \r
 235    //! <b>Effects</b>: Swaps the contents of two iunordered_sets.\r
 236    //!   Swaps also the contained bucket array and equality and hasher functors.\r
 237    //! \r
 238    //! <b>Complexity</b>: Constant.\r
 239    //!\r
 240    //! <b>Throws</b>: If the swap() call for the comparison or hash functors\r
 241    //!   found using ADL throw. Basic guarantee.\r
 242    void swap(iunordered_set& other)\r
 243    { table_.swap(other.table_); }\r
 244 \r
 245    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 246    //!\r
 247    //! <b>Effects</b>: Erases all the elements from *this\r
 248    //!   calling Destroyer::operator()(pointer), clones all the \r
 249    //!   elements from src calling Cloner::operator()(const value_type &)\r
 250    //!   and inserts them on *this.\r
 251    //!\r
 252    //!   If cloner throws, all cloned elements are unlinked and destroyed\r
 253    //!   calling Destroyer::operator()(pointer).\r
 254    //!   \r
 255    //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
 256    //! \r
 257    //! <b>Throws</b>: If cloner throws. Basic guarantee.\r
 258    template <class Cloner, class Destroyer>\r
 259    void clone_from(const iunordered_set &src, Cloner cloner, Destroyer destroyer)\r
 260    {  table_.clone_from(src.table_, cloner, destroyer);  }\r
 261 \r
 262    //! <b>Requires</b>: value must be an lvalue\r
 263    //! \r
 264    //! <b>Effects</b>: Tries to inserts value into the iunordered_set.\r
 265    //!\r
 266    //! <b>Returns</b>: If the value\r
 267    //!   is not already present inserts it and returns a pair containing the\r
 268    //!   iterator to the new value and true. If the value is already present\r
 269    //!   returns a pair containing an iterator to the already present value\r
 270    //!   and false.\r
 271    //! \r
 272    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 273    //! \r
 274    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.\r
 275    //! \r
 276    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 277    //!   No copy-constructors are called.\r
 278    std::pair<iterator, bool> insert(value_type &value)\r
 279    {  return table_.insert_unique(value);  }\r
 280 \r
 281    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 282    //!   the same hash values as the stored hasher. The difference is that\r
 283    //!   "hasher" hashes the given key instead of the value_type.\r
 284    //!\r
 285    //!   "key_value_equal" must be a equality function that induces \r
 286    //!   the same equality as key_equal. The difference is that\r
 287    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 288    //! \r
 289    //! <b>Effects</b>: Checks if a value can be inserted in the iunordered_set, using\r
 290    //!   a user provided key instead of the value itself.\r
 291    //!\r
 292    //! <b>Returns</b>: If an equivalent value is already present\r
 293    //!   returns a pair containing an iterator to the already present value\r
 294    //!   and false. If the value can be inserted returns true in the returned\r
 295    //!   pair boolean and fills "commit_data" that is meant to be used with\r
 296    //!   the "insert_commit" function.\r
 297    //! \r
 298    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 299    //!\r
 300    //! <b>Throws</b>: If hasher or key_value_equal throw. Strong guarantee.\r
 301    //! \r
 302    //! <b>Notes</b>: This function is used to improve performance when constructing\r
 303    //!   a value_type is expensive: if an equivalent value is already present\r
 304    //!   the constructed object must be discarded. Many times, the part of the\r
 305    //!   node that is used to impose the hash or the equality is much cheaper to\r
 306    //!   construct than the value_type and this function offers the possibility to\r
 307    //!   use that the part to check if the insertion will be successful.\r
 308    //!\r
 309    //!   If the check is successful, the user can construct the value_type and use\r
 310    //!   "insert_commit" to insert the object in constant-time.\r
 311    //!\r
 312    //!   "commit_data" remains valid for a subsequent "insert_commit" only if no more\r
 313    //!   objects are inserted or erased from the iunordered_set.\r
 314    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 315    std::pair<iterator, bool> insert_check\r
 316       (const KeyType &key, KeyHasher hasher, KeyValueEqual key_value_equal, insert_commit_data &commit_data)\r
 317    {  return table_.insert_unique_check(key, hasher, key_value_equal, commit_data); }\r
 318 \r
 319    //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data\r
 320    //!   must have been obtained from a previous call to "insert_check".\r
 321    //!   No objects should have been inserted or erased from the iunordered_set between\r
 322    //!   the "insert_check" that filled "commit_data" and the call to "insert_commit".\r
 323    //! \r
 324    //! <b>Effects</b>: Inserts the value in the iunordered_set using the information obtained\r
 325    //!   from the "commit_data" that a previous "insert_check" filled.\r
 326    //!\r
 327    //! <b>Returns</b>: An iterator to the newly inserted object.\r
 328    //! \r
 329    //! <b>Complexity</b>: Constant time.\r
 330    //!\r
 331    //! <b>Throws</b>: Nothing.\r
 332    //! \r
 333    //! <b>Notes</b>: This function has only sense if a "insert_check" has been\r
 334    //!   previously executed to fill "commit_data". No value should be inserted or\r
 335    //!   erased between the "insert_check" and "insert_commit" calls.\r
 336    iterator insert_commit(value_type &value, const insert_commit_data &commit_data)\r
 337    {  return table_.insert_unique_commit(value, commit_data); }\r
 338 \r
 339    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue \r
 340    //!   of type value_type.\r
 341    //! \r
 342    //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).\r
 343    //! \r
 344    //! <b>Complexity</b>: Average case O(N), where N is std::distance(b, e).\r
 345    //!   Worst case O(N*this->size()).\r
 346    //! \r
 347    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.\r
 348    //! \r
 349    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
 350    //!   No copy-constructors are called.\r
 351    template<class Iterator>\r
 352    void insert(Iterator b, Iterator e)\r
 353    {  table_.insert_unique(b, e);  }\r
 354 \r
 355    //! <b>Effects</b>: Erases the element pointed to by i. \r
 356    //! \r
 357    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 358    //! \r
 359    //! <b>Throws</b>: Nothing.\r
 360    //! \r
 361    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 362    //!    to the erased element. No destructors are called.\r
 363    void erase(const_iterator i)\r
 364    {  table_.erase(i);  }\r
 365 \r
 366    //! <b>Effects</b>: Erases the range pointed to by b end e. \r
 367    //! \r
 368    //! <b>Complexity</b>: Average case O(std::distance(b, e)),\r
 369    //!   worst case O(this->size()).\r
 370    //! \r
 371    //! <b>Throws</b>: Nothing.\r
 372    //! \r
 373    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 374    //!    to the erased elements. No destructors are called.\r
 375    void erase(const_iterator b, const_iterator e)\r
 376    {  table_.erase(b, e);  }\r
 377 \r
 378    //! <b>Effects</b>: Erases all the elements with the given value.\r
 379    //! \r
 380    //! <b>Returns</b>: The number of erased elements.\r
 381    //! \r
 382    //! <b>Complexity</b>: Average case O(this->count(value)).\r
 383    //!   Worst case O(this->size()).\r
 384    //! \r
 385    //! <b>Throws</b>: If the internal hasher or the equality functor throws.  Basic guarantee.\r
 386    //! \r
 387    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 388    //!    to the erased elements. No destructors are called.\r
 389    size_type erase(const value_type &value)\r
 390    {  return table_.erase(value);  }\r
 391 \r
 392    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 393    //!   the same hash values as the stored hasher. The difference is that\r
 394    //!   "hasher" hashes the given key instead of the value_type.\r
 395    //!\r
 396    //!   "key_value_equal" must be a equality function that induces \r
 397    //!   the same equality as key_equal. The difference is that\r
 398    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 399    //!\r
 400    //! <b>Effects</b>: Erases all the elements that have the same hash and\r
 401    //!   compare equal with the given key.\r
 402    //! \r
 403    //! <b>Returns</b>: The number of erased elements.\r
 404    //! \r
 405    //! <b>Complexity</b>: Average case O(this->count(value)).\r
 406    //!   Worst case O(this->size()).\r
 407    //! \r
 408    //! <b>Throws</b>: If hasher or equal throw. Basic guarantee.\r
 409    //! \r
 410    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 411    //!    to the erased elements. No destructors are called.\r
 412    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 413    size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
 414    {  return table_.erase(key, hasher, equal);  }\r
 415 \r
 416    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 417    //!\r
 418    //! <b>Effects</b>: Erases the element pointed to by i. \r
 419    //!   Destroyer::operator()(pointer) is called for the removed element.\r
 420    //! \r
 421    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 422    //! \r
 423    //! <b>Throws</b>: Nothing.\r
 424    //! \r
 425    //! <b>Note</b>: Invalidates the iterators \r
 426    //!    to the erased elements.\r
 427    template<class Destroyer>\r
 428    iterator erase_and_destroy(const_iterator i, Destroyer destroyer)\r
 429    {  return table_.erase_and_destroy(i, destroyer);  }\r
 430 \r
 431    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 432    //!\r
 433    //! <b>Effects</b>: Erases the range pointed to by b end e.\r
 434    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 435    //! \r
 436    //! <b>Complexity</b>: Average case O(std::distance(b, e)),\r
 437    //!   worst case O(this->size()).\r
 438    //! \r
 439    //! <b>Throws</b>: Nothing.\r
 440    //! \r
 441    //! <b>Note</b>: Invalidates the iterators\r
 442    //!    to the erased elements.\r
 443    template<class Destroyer>\r
 444    iterator erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)\r
 445    {  return table_.erase_and_destroy(b, e, destroyer);  }\r
 446 \r
 447    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 448    //!\r
 449    //! <b>Effects</b>: Erases all the elements with the given value.\r
 450    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 451    //! \r
 452    //! <b>Returns</b>: The number of erased elements.\r
 453    //! \r
 454    //! <b>Complexity</b>: Average case O(this->count(value)).\r
 455    //!   Worst case O(this->size()).\r
 456    //! \r
 457    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.\r
 458    //! \r
 459    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 460    //!    to the erased elements. No destructors are called.\r
 461    template<class Destroyer>\r
 462    size_type erase_and_destroy(const value_type &value, Destroyer destroyer)\r
 463    {  return table_.erase_and_destroy(value, destroyer);  }\r
 464 \r
 465    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 466    //!\r
 467    //! <b>Effects</b>: Erases all the elements with the given key.\r
 468    //!   according to the comparison functor "equal".\r
 469    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 470    //!\r
 471    //! <b>Returns</b>: The number of erased elements.\r
 472    //! \r
 473    //! <b>Complexity</b>: Average case O(this->count(value)).\r
 474    //!   Worst case O(this->size()).\r
 475    //! \r
 476    //! <b>Throws</b>: If hasher or key_value_equal throw. Basic guarantee.\r
 477    //! \r
 478    //! <b>Note</b>: Invalidates the iterators\r
 479    //!    to the erased elements.\r
 480    template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>\r
 481    size_type erase_and_destroy(const KeyType& key, KeyHasher hasher, KeyValueEqual equal, Destroyer destroyer)\r
 482    {  return table_.erase_and_destroy(key, hasher, equal, destroyer);  }\r
 483 \r
 484    //! <b>Effects</b>: Erases all of the elements. \r
 485    //! \r
 486    //! <b>Complexity</b>: Linear to the number of elements on the container.\r
 487    //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
 488    //! \r
 489    //! <b>Throws</b>: Nothing.\r
 490    //! \r
 491    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 492    //!    to the erased elements. No destructors are called.\r
 493    void clear()\r
 494    {  return table_.clear();  }\r
 495 \r
 496    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
 497    //! \r
 498    //! <b>Effects</b>: Erases all of the elements. \r
 499    //! \r
 500    //! <b>Complexity</b>: Linear to the number of elements on the container.\r
 501    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
 502    //! \r
 503    //! <b>Throws</b>: Nothing.\r
 504    //! \r
 505    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
 506    //!    to the erased elements. No destructors are called.\r
 507    template<class Destroyer>\r
 508    void clear_and_destroy(Destroyer destroyer)\r
 509    {  return table_.clear_and_destroy(destroyer);  }\r
 510 \r
 511    //! <b>Effects</b>: Returns the number of contained elements with the given value\r
 512    //! \r
 513    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 514    //! \r
 515    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
 516    size_type count(const value_type &value) const\r
 517    {  return table_.find(value) != end();  }\r
 518 \r
 519    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 520    //!   the same hash values as the stored hasher. The difference is that\r
 521    //!   "hasher" hashes the given key instead of the value_type.\r
 522    //!\r
 523    //!   "key_value_equal" must be a equality function that induces \r
 524    //!   the same equality as key_equal. The difference is that\r
 525    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 526    //!\r
 527    //! <b>Effects</b>: Returns the number of contained elements with the given key\r
 528    //!\r
 529    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 530    //! \r
 531    //! <b>Throws</b>: If hasher or equal throw.\r
 532    template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>\r
 533    size_type count(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const\r
 534    {  return table_.find(key, hasher, equal) != end();  }\r
 535 \r
 536    //! <b>Effects</b>: Finds an iterator to the first element is equal to\r
 537    //!   "value" or end() if that element does not exist.\r
 538    //!\r
 539    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 540    //! \r
 541    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
 542    iterator find(const value_type &value)\r
 543    {  return table_.find(value);  }\r
 544 \r
 545    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 546    //!   the same hash values as the stored hasher. The difference is that\r
 547    //!   "hasher" hashes the given key instead of the value_type.\r
 548    //!\r
 549    //!   "key_value_equal" must be a equality function that induces \r
 550    //!   the same equality as key_equal. The difference is that\r
 551    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 552    //!\r
 553    //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
 554    //!   "key" according to the given hasher and equality functor or end() if\r
 555    //!   that element does not exist.\r
 556    //!\r
 557    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 558    //! \r
 559    //! <b>Throws</b>: If hasher or equal throw.\r
 560    //!\r
 561    //! <b>Note</b>: This function is used when constructing a value_type\r
 562    //!   is expensive and the value_type can be compared with a cheaper\r
 563    //!   key type. Usually this key is part of the value_type.\r
 564    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 565    iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
 566    {  return table_.find(key, hasher, equal);  }\r
 567 \r
 568    //! <b>Effects</b>: Finds a const_iterator to the first element whose key is \r
 569    //!   "key" or end() if that element does not exist.\r
 570    //! \r
 571    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 572    //! \r
 573    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
 574    const_iterator find(const value_type &value) const\r
 575    {  return table_.find(value);  }\r
 576 \r
 577    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 578    //!   the same hash values as the stored hasher. The difference is that\r
 579    //!   "hasher" hashes the given key instead of the value_type.\r
 580    //!\r
 581    //!   "key_value_equal" must be a equality function that induces \r
 582    //!   the same equality as key_equal. The difference is that\r
 583    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 584    //!\r
 585    //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
 586    //!   "key" according to the given hasher and equality functor or end() if\r
 587    //!   that element does not exist.\r
 588    //! \r
 589    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
 590    //! \r
 591    //! <b>Throws</b>: If hasher or equal throw.\r
 592    //!\r
 593    //! <b>Note</b>: This function is used when constructing a value_type\r
 594    //!   is expensive and the value_type can be compared with a cheaper\r
 595    //!   key type. Usually this key is part of the value_type.\r
 596    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 597    const_iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const\r
 598    {  return table_.find(key, equal);  }\r
 599 \r
 600    //! <b>Effects</b>: Returns a range containing all elements with values equivalent\r
 601    //!   to value. Returns std::make_pair(this->end(), this->end()) if no such \r
 602    //!   elements exist.\r
 603    //! \r
 604    //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).\r
 605    //! \r
 606    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
 607    std::pair<iterator,iterator> equal_range(const value_type &value)\r
 608    {  return table_.equal_range(value);  }\r
 609 \r
 610    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 611    //!   the same hash values as the stored hasher. The difference is that\r
 612    //!   "hasher" hashes the given key instead of the value_type.\r
 613    //!\r
 614    //!   "key_value_equal" must be a equality function that induces \r
 615    //!   the same equality as key_equal. The difference is that\r
 616    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 617    //!\r
 618    //! <b>Effects</b>: Returns a range containing all elements with equivalent\r
 619    //!   keys. Returns std::make_pair(this->end(), this->end()) if no such \r
 620    //!   elements exist.\r
 621    //! \r
 622    //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).\r
 623    //! \r
 624    //! <b>Throws</b>: If hasher or the equal throw.\r
 625    //!\r
 626    //! <b>Note</b>: This function is used when constructing a value_type\r
 627    //!   is expensive and the value_type can be compared with a cheaper\r
 628    //!   key type. Usually this key is part of the value_type.\r
 629    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 630    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
 631    {  return table_.equal_range(key, hasher, equal);  }\r
 632 \r
 633    //! <b>Effects</b>: Returns a range containing all elements with values equivalent\r
 634    //!   to value. Returns std::make_pair(this->end(), this->end()) if no such \r
 635    //!   elements exist.\r
 636    //! \r
 637    //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).\r
 638    //! \r
 639    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
 640    std::pair<const_iterator, const_iterator>\r
 641       equal_range(const value_type &value) const\r
 642    {  return table_.equal_range(value);  }\r
 643 \r
 644    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 645    //!   the same hash values as the stored hasher. The difference is that\r
 646    //!   "hasher" hashes the given key instead of the value_type.\r
 647    //!\r
 648    //!   "key_value_equal" must be a equality function that induces \r
 649    //!   the same equality as key_equal. The difference is that\r
 650    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
 651    //!\r
 652    //! <b>Effects</b>: Returns a range containing all elements with equivalent\r
 653    //!   keys. Returns std::make_pair(this->end(), this->end()) if no such \r
 654    //!   elements exist.\r
 655    //! \r
 656    //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).\r
 657    //! \r
 658    //! <b>Throws</b>: If the hasher or equal throw.\r
 659    //!\r
 660    //! <b>Note</b>: This function is used when constructing a value_type\r
 661    //!   is expensive and the value_type can be compared with a cheaper\r
 662    //!   key type. Usually this key is part of the value_type.\r
 663    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 664    std::pair<const_iterator, const_iterator>\r
 665       equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const\r
 666    {  return table_.equal_range(key, equal);  }\r
 667 \r
 668    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of\r
 669    //!   appropriate type. Otherwise the behavior is undefined.\r
 670    //! \r
 671    //! <b>Effects</b>: Returns: a valid iterator i belonging to the iunordered_set\r
 672    //!   that points to the value\r
 673    //! \r
 674    //! <b>Complexity</b>: Constant.\r
 675    //! \r
 676    //! <b>Throws</b>: If the internal hash function throws.\r
 677    iterator current(value_type &value)\r
 678    {  return table_.current(value);  }\r
 679 \r
 680    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of\r
 681    //!   appropriate type. Otherwise the behavior is undefined.\r
 682    //! \r
 683    //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the\r
 684    //!   iunordered_set that points to the value\r
 685    //! \r
 686    //! <b>Complexity</b>: Constant.\r
 687    //! \r
 688    //! <b>Throws</b>: If the internal hash function throws.\r
 689    const_iterator current(const value_type &value) const\r
 690    {  return table_.current(value);  }\r
 691 \r
 692    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of\r
 693    //!   appropriate type. Otherwise the behavior is undefined.\r
 694    //! \r
 695    //! <b>Effects</b>: Returns: a valid local_iterator i belonging to the iunordered_set\r
 696    //!   that points to the value\r
 697    //! \r
 698    //! <b>Complexity</b>: Constant.\r
 699    //! \r
 700    //! <b>Throws</b>: Nothing.\r
 701    static local_iterator current_local(value_type &value)\r
 702    {  return table_type::current_local(value);  }\r
 703 \r
 704    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_set of\r
 705    //!   appropriate type. Otherwise the behavior is undefined.\r
 706    //! \r
 707    //! <b>Effects</b>: Returns: a valid const_local_iterator i belonging to\r
 708    //!   the iunordered_set that points to the value\r
 709    //! \r
 710    //! <b>Complexity</b>: Constant.\r
 711    //! \r
 712    //! <b>Throws</b>: Nothing.\r
 713    static const_local_iterator current_local(const value_type &value)\r
 714    {  return table_type::current_local(value);  }\r
 715 \r
 716    //! <b>Effects</b>: Returns the number of buckets passed in the constructor\r
 717    //!   or the last rehash function.\r
 718    //! \r
 719    //! <b>Complexity</b>: Constant.\r
 720    //! \r
 721    //! <b>Throws</b>: Nothing.\r
 722    size_type bucket_count() const\r
 723    {  return table_.bucket_count();   }\r
 724 \r
 725    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
 726    //!\r
 727    //! <b>Effects</b>: Returns the number of elements in the nth bucket.\r
 728    //! \r
 729    //! <b>Complexity</b>: Constant.\r
 730    //! \r
 731    //! <b>Throws</b>: Nothing.\r
 732    size_type bucket_size(size_type n)\r
 733    {  return table_.bucket_size(n);   }\r
 734 \r
 735    //! <b>Effects</b>: Returns the index of the bucket in which elements\r
 736    //!   with keys equivalent to k would be found, if any such element existed.\r
 737    //! \r
 738    //! <b>Complexity</b>: Constant.\r
 739    //! \r
 740    //! <b>Throws</b>: If the hash functor throws.\r
 741    //!\r
 742    //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).\r
 743    size_type bucket(const key_type& k)\r
 744    {  return table_.bucket(k);   }\r
 745 \r
 746    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
 747    //!   the same hash values as the stored hasher. The difference is that\r
 748    //!   "hasher" hashes the given key instead of the value_type.\r
 749    //!\r
 750    //! <b>Effects</b>: Returns the index of the bucket in which elements\r
 751    //!   with keys equivalent to k would be found, if any such element existed.\r
 752    //! \r
 753    //! <b>Complexity</b>: Constant.\r
 754    //! \r
 755    //! <b>Throws</b>: If hasher throws.\r
 756    //!\r
 757    //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).\r
 758    template<class KeyType, class KeyHasher>\r
 759    size_type bucket(const KeyType& k,  KeyHasher hasher)\r
 760    {  return table_.bucket(k, hasher);   }\r
 761 \r
 762    //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor\r
 763    //!   or the last rehash function.\r
 764    //! \r
 765    //! <b>Complexity</b>: Constant.\r
 766    //! \r
 767    //! <b>Throws</b>: Nothing.\r
 768    bucket_ptr bucket_pointer() const\r
 769    {  return table_.bucket_pointer();   }\r
 770 \r
 771    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
 772    //!\r
 773    //! <b>Effects</b>: Returns a local_iterator pointing to the beginning\r
 774    //!   of the sequence stored in the bucket n.\r
 775    //! \r
 776    //! <b>Complexity</b>: Constant.\r
 777    //! \r
 778    //! <b>Throws</b>: Nothing.\r
 779    //! \r
 780    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
 781    //!   containing all of the elements in the nth bucket. \r
 782    local_iterator begin(size_type n)\r
 783    {  return table_.begin(n);   }\r
 784 \r
 785    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
 786    //!\r
 787    //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning\r
 788    //!   of the sequence stored in the bucket n.\r
 789    //! \r
 790    //! <b>Complexity</b>: Constant.\r
 791    //! \r
 792    //! <b>Throws</b>: Nothing.\r
 793    //! \r
 794    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
 795    //!   containing all of the elements in the nth bucket. \r
 796    const_local_iterator begin(size_type n) const\r
 797    {  return table_.begin(n);   }\r
 798 \r
 799    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
 800    //!\r
 801    //! <b>Effects</b>: Returns a local_iterator pointing to the end\r
 802    //!   of the sequence stored in the bucket n.\r
 803    //! \r
 804    //! <b>Complexity</b>: Constant.\r
 805    //! \r
 806    //! <b>Throws</b>: Nothing.\r
 807    //! \r
 808    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
 809    //!   containing all of the elements in the nth bucket. \r
 810    local_iterator end(size_type n)\r
 811    {  return table_.end(n);   }\r
 812 \r
 813    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
 814    //!\r
 815    //! <b>Effects</b>: Returns a const_local_iterator pointing to the end\r
 816    //!   of the sequence stored in the bucket n.\r
 817    //! \r
 818    //! <b>Complexity</b>: Constant.\r
 819    //! \r
 820    //! <b>Throws</b>: Nothing.\r
 821    //! \r
 822    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
 823    //!   containing all of the elements in the nth bucket. \r
 824    const_local_iterator end(size_type n) const\r
 825    {  return table_.end(n);   }\r
 826 \r
 827    //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array\r
 828    //!   or the same as the old bucket array. new_size is the length of the\r
 829    //!   the array pointed by new_buckets. If new_buckets == this->bucket_pointer()\r
 830    //!   n can be bigger or smaller than this->bucket_count().\r
 831    //!\r
 832    //! <b>Effects</b>: Updates the internal reference with the new bucket erases\r
 833    //!   the values from the old bucket and inserts then in the new one. \r
 834    //! \r
 835    //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.\r
 836    //! \r
 837    //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.\r
 838    void rehash(bucket_ptr new_buckets, size_type new_size)\r
 839    {  table_.rehash(new_buckets, new_size); }\r
 840 \r
 841    //! <b>Effects</b>: Returns the nearest new bucket count optimized for\r
 842    //!   the container that is bigger than n. This suggestion can be used\r
 843    //!   to create bucket arrays with a size that will usually improve\r
 844    //!   container's performance. If such value does not exist, the \r
 845    //!   higher possible value is returned.\r
 846    //! \r
 847    //! <b>Complexity</b>: Amortized constant time.\r
 848    //! \r
 849    //! <b>Throws</b>: Nothing.\r
 850    static size_type suggested_upper_bucket_count(size_type n)\r
 851    {  return table_type::suggested_upper_bucket_count(n);  }\r
 852 \r
 853    //! <b>Effects</b>: Returns the nearest new bucket count optimized for\r
 854    //!   the container that is smaller than n. This suggestion can be used\r
 855    //!   to create bucket arrays with a size that will usually improve\r
 856    //!   container's performance. If such value does not exist, the \r
 857    //!   lower possible value is returned.\r
 858    //! \r
 859    //! <b>Complexity</b>: Amortized constant time.\r
 860    //! \r
 861    //! <b>Throws</b>: Nothing.\r
 862    static size_type suggested_lower_bucket_count(size_type n)\r
 863    {  return table_type::suggested_lower_bucket_count(n);  }\r
 864 };\r
 865 \r
 866 //! The class template iunordered_multiset is an intrusive container, that mimics most of \r
 867 //! the interface of std::tr1::unordered_multiset as described in the C++ TR1.\r
 868 //!\r
 869 //! iunordered_multiset is a pseudo-intrusive container: each object to be stored in the\r
 870 //! container must contain a proper hook, but the container also needs\r
 871 //! additional auxiliary memory to work: iunordered_multiset needs a pointer to an array\r
 872 //! of type `bucket_type` to be passed in the constructor. This bucket array must\r
 873 //! have at least the same lifetime as the container. This makes the use of\r
 874 //! iunordered_multiset more complicated than purely intrusive containers.\r
 875 //! `bucket_type` is default-constructible, copyable and assignable\r
 876 //!\r
 877 //! The template parameter ValueTraits is called "value traits". It stores\r
 878 //! information and operations about the type to be stored in the container.\r
 879 //!\r
 880 //! The template parameter Hash is a unary function object that take an argument\r
 881 //!   of type ValueTraits::value_type and returns a value of type std::size_t.\r
 882 //!\r
 883 //! The template parameter Equal is a binary predicate that takes two arguments of\r
 884 //!   type ValueTraits::value_type. Equal is an equivalence relation.\r
 885 //!\r
 886 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType\r
 887 //! will be embedded in the class, that will keep track of the number of stored objects.\r
 888 //! This will allow constant-time O(1) size() member, instead of default O(N) size.\r
 889 //!\r
 890 //! iunordered_multiset only provides forward iterators but it provides 4 iterator types:\r
 891 //! iterator and const_iterator to navigate through the whole container and\r
 892 //! local_iterator and const_local_iterator to navigate through the values\r
 893 //! stored in a single bucket. Local iterators are faster and smaller.\r
 894 //!\r
 895 //! It's not recommended to use non ConstantTimeSize iunordered_multisets because several\r
 896 //! key functions, like "empty()", become non-constant time functions. Non\r
 897 //! ConstantTimeSize iunordered_multisets are mainly provided to support auto-unlink hooks.\r
 898 //!\r
 899 //! iunordered_multiset, unlike std::unordered_set, does not make automatic rehashings nor\r
 900 //! offers functions related to a load factor. Rehashing can be explicitly requested\r
 901 //! and the user must provide a new bucket array that will be used from that moment.\r
 902 //!\r
 903 //! Since no automatic rehashing is done, iterators are never invalidated when\r
 904 //! inserting or erasing elements. Iterators are only invalidated when rehasing.\r
 905 template< class ValueTraits\r
 906         , class Hash             = boost::hash<typename ValueTraits::value_type>\r
 907         , class Equal            = std::equal_to<typename ValueTraits::value_type>\r
 908         , bool  ConstantTimeSize = true\r
 909         , class SizeType         = std::size_t\r
 910         >\r
 911 class iunordered_multiset\r
 912 {\r
 913    private:\r
 914    typedef detail::ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType> table_type;\r
 915 \r
 916    //! This class is\r
 917    //! non-copyable\r
 918    iunordered_multiset (const iunordered_multiset&);\r
 919 \r
 920    //! This class is\r
 921    //! non-assignable\r
 922    iunordered_multiset &operator =(const iunordered_multiset&);\r
 923 \r
 924    typedef table_type implementation_defined;\r
 925 \r
 926    public:\r
 927    typedef typename ValueTraits::value_type                             value_type;\r
 928    typedef typename ValueTraits::pointer                                pointer;\r
 929    typedef typename ValueTraits::const_pointer                          const_pointer;\r
 930    typedef value_type&                                                  reference;\r
 931    typedef const value_type&                                            const_reference;\r
 932    typedef SizeType                                                     size_type;\r
 933    typedef typename std::iterator_traits<pointer>::difference_type      difference_type;\r
 934    typedef value_type                                                   key_type;\r
 935    typedef Equal                                                        key_equal;\r
 936    typedef Hash                                                         hasher;\r
 937    typedef typename implementation_defined::bucket_type                 bucket_type;\r
 938    typedef typename boost::pointer_to_other<pointer, bucket_type>::type bucket_ptr;\r
 939    typedef typename implementation_defined::iterator                    iterator;\r
 940    typedef typename implementation_defined::const_iterator              const_iterator;\r
 941    typedef typename implementation_defined::insert_commit_data          insert_commit_data;\r
 942    typedef typename implementation_defined::local_iterator              local_iterator;\r
 943    typedef typename implementation_defined::const_local_iterator        const_local_iterator;\r
 944 \r
 945    private:\r
 946    table_type table_;\r
 947 \r
 948    public:\r
 949 \r
 950    //! <b>Requires</b>: buckets must not be being used by any other resource.\r
 951    //!\r
 952    //! <b>Effects</b>: Constructs an empty iunordered_multiset, storing a reference\r
 953    //!   to the bucket array and copies of the hasher and equal functors.\r
 954    //!   \r
 955    //! <b>Complexity</b>: Constant. \r
 956    //! \r
 957    //! <b>Throws</b>: If value_traits::node_traits::node\r
 958    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
 959    //!   or the copy constructor or invocation of Hash or Equal throws. \r
 960    //!\r
 961    //! <b>Notes</b>: buckets array must be destroyed only after\r
 962    //!   *this is destroyed. \r
 963    iunordered_multiset  ( bucket_ptr buckets\r
 964                   , size_type buckets_len\r
 965                   , const Hash & hasher = Hash()\r
 966                   , const Equal &equal = Equal()) \r
 967       :  table_(buckets, buckets_len, hasher, equal)\r
 968    {}\r
 969 \r
 970    //! <b>Requires</b>: buckets must not be being used by any other resource\r
 971    //!   and Dereferencing iterator must yield an lvalue of type value_type.\r
 972    //! \r
 973    //! <b>Effects</b>: Constructs an empty iunordered_multiset and inserts elements from \r
 974    //!   [b, e).\r
 975    //!   \r
 976    //! <b>Complexity</b>: If N is std::distance(b, e): Average case is O(N)\r
 977    //!   (with a good hash function and with buckets_len >= N),worst case O(N2).\r
 978    //! \r
 979    //! <b>Throws</b>: If value_traits::node_traits::node\r
 980    //!   constructor throws (this does not happen with predefined Boost.Intrusive hooks)\r
 981    //!   or the copy constructor or invocation of Hash or Equal throws. \r
 982    //!\r
 983    //! <b>Notes</b>: buckets array must be destroyed only after\r
 984    //!   *this is destroyed.\r
 985    template<class Iterator>\r
 986    iunordered_multiset  ( bucket_ptr buckets\r
 987                   , size_type buckets_len\r
 988                   , Iterator b\r
 989                   , Iterator e\r
 990                   , const Hash & hasher = Hash()\r
 991                   , const Equal &equal = Equal()) \r
 992       :  table_(buckets, buckets_len, hasher, equal)\r
 993    {  table_.insert_equal(b, e);  }\r
 994 \r
 995    //! <b>Effects</b>: Detaches all elements from this. The objects in the iunordered_multiset \r
 996    //!   are not deleted (i.e. no destructors are called).\r
 997    //! \r
 998    //! <b>Complexity</b>: Linear to the number of elements in the iunordered_multiset, if \r
 999    //!   it's a safe-mode or auto-unlink value. Otherwise constant.\r
1000    //! \r
1001    //! <b>Throws</b>: Nothing.\r
1002    ~iunordered_multiset() \r
1003    {}\r
1004 \r
1005    //! <b>Effects</b>: Returns an iterator pointing to the beginning of the iunordered_multiset.\r
1006    //! \r
1007    //! <b>Complexity</b>: Amortized constant time.\r
1008    //!   Worst case (empty iunordered_multiset): O(this->bucket_count())\r
1009    //! \r
1010    //! <b>Throws</b>: Nothing.\r
1011    iterator begin()\r
1012    { return table_.begin();  }\r
1013 \r
1014    //! <b>Effects</b>: Returns a const_iterator pointing to the beginning\r
1015    //!   of the iunordered_multiset.\r
1016    //!\r
1017    //! <b>Complexity</b>: Amortized constant time.\r
1018    //!   Worst case (empty iunordered_multiset): O(this->bucket_count())\r
1019    //! \r
1020    //! <b>Throws</b>: Nothing.\r
1021    const_iterator begin() const\r
1022    { return table_.begin();  }\r
1023 \r
1024    //! <b>Effects</b>: Returns an iterator pointing to the end of the iunordered_multiset.\r
1025    //! \r
1026    //! <b>Complexity</b>: Constant.\r
1027    //! \r
1028    //! <b>Throws</b>: Nothing.\r
1029    iterator end()\r
1030    { return table_.end();  }\r
1031 \r
1032    //! <b>Effects</b>: Returns a const_iterator pointing to the end of the iunordered_multiset.\r
1033    //! \r
1034    //! <b>Complexity</b>: Constant.\r
1035    //! \r
1036    //! <b>Throws</b>: Nothing.\r
1037    const_iterator end() const\r
1038    { return table_.end();  }\r
1039 \r
1040    //! <b>Effects</b>: Returns the hasher object used by the iunordered_set.\r
1041    //! \r
1042    //! <b>Complexity</b>: Constant.\r
1043    //! \r
1044    //! <b>Throws</b>: If hasher copy-constructor throws.\r
1045    hasher hash_function() const\r
1046    { return table_.hash_function(); }\r
1047 \r
1048    //! <b>Effects</b>: Returns the key_equal object used by the iunordered_multiset.\r
1049    //! \r
1050    //! <b>Complexity</b>: Constant.\r
1051    //! \r
1052    //! <b>Throws</b>: If key_equal copy-constructor throws.\r
1053    key_equal key_eq() const\r
1054    { return table_.key_eq(); }\r
1055 \r
1056    //! <b>Effects</b>: Returns true is the container is empty.\r
1057    //! \r
1058    //! <b>Complexity</b>: if ConstantTimeSize is false, average constant time\r
1059    //!   (worst case, with empty() == true): O(this->bucket_count()).\r
1060    //!   Otherwise constant.\r
1061    //! \r
1062    //! <b>Throws</b>: Nothing.\r
1063    bool empty() const\r
1064    { return table_.empty(); }\r
1065 \r
1066    //! <b>Effects</b>: Returns the number of elements stored in the iunordered_multiset.\r
1067    //! \r
1068    //! <b>Complexity</b>: Linear to elements contained in *this if\r
1069    //!   ConstantTimeSize is false. Constant-time otherwise.\r
1070    //! \r
1071    //! <b>Throws</b>: Nothing.\r
1072    size_type size() const\r
1073    { return table_.size(); }\r
1074 \r
1075    //! <b>Requires</b>: the hasher and the equality function unqualified swap\r
1076    //!   call should not throw.\r
1077    //! \r
1078    //! <b>Effects</b>: Swaps the contents of two iunordered_multisets.\r
1079    //!   Swaps also the contained bucket array and equality and hasher functors.\r
1080    //!\r
1081    //! \r
1082    //! <b>Complexity</b>: Constant.\r
1083    //!\r
1084    //! <b>Throws</b>: If the swap() call for the comparison or hash functors\r
1085    //!   found using ADL throw. Basic guarantee.\r
1086    void swap(iunordered_multiset& other)\r
1087    { table_.swap(other.table_); }\r
1088 \r
1089    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1090    //!\r
1091    //! <b>Effects</b>: Erases all the elements from *this\r
1092    //!   calling Destroyer::operator()(pointer), clones all the \r
1093    //!   elements from src calling Cloner::operator()(const value_type &)\r
1094    //!   and inserts them on *this.\r
1095    //!\r
1096    //!   If cloner throws, all cloned elements are unlinked and destroyed\r
1097    //!   calling Destroyer::operator()(pointer).\r
1098    //!   \r
1099    //! <b>Complexity</b>: Linear to erased plus inserted elements.\r
1100    //! \r
1101    //! <b>Throws</b>: If cloner throws.\r
1102    template <class Cloner, class Destroyer>\r
1103    void clone_from(const iunordered_multiset &src, Cloner cloner, Destroyer destroyer)\r
1104    {  table_.clone_from(src.table_, cloner, destroyer);  }\r
1105 \r
1106    //! <b>Requires</b>: value must be an lvalue\r
1107    //! \r
1108    //! <b>Effects</b>: Inserts value into the iunordered_multiset.\r
1109    //!\r
1110    //! <b>Returns</b>: An iterator to the new inserted value.\r
1111    //! \r
1112    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1113    //! \r
1114    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.\r
1115    //! \r
1116    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
1117    //!   No copy-constructors are called.\r
1118    iterator insert(value_type &value)\r
1119    {  return table_.insert_equal(value);  }\r
1120 \r
1121    //! <b>Requires</b>: Dereferencing iterator must yield an lvalue \r
1122    //!   of type value_type.\r
1123    //! \r
1124    //! <b>Effects</b>: Equivalent to this->insert(t) for each element in [b, e).\r
1125    //! \r
1126    //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the \r
1127    //!   size of the range. However, it is linear in N if the range is already sorted \r
1128    //!   by value_comp().\r
1129    //! \r
1130    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.\r
1131    //! \r
1132    //! <b>Note</b>: Does not affect the validity of iterators and references.\r
1133    //!   No copy-constructors are called.\r
1134    template<class Iterator>\r
1135    void insert(Iterator b, Iterator e)\r
1136    {  table_.insert_equal(b, e);  }\r
1137 \r
1138    //! <b>Effects</b>: Erases the element pointed to by i. \r
1139    //! \r
1140    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1141    //! \r
1142    //! <b>Throws</b>: Nothing.\r
1143    //! \r
1144    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1145    //!    to the erased element. No destructors are called.\r
1146    void erase(const_iterator i)\r
1147    {  table_.erase(i);  }\r
1148 \r
1149    //! <b>Effects</b>: Erases the range pointed to by b end e. \r
1150    //! \r
1151    //! <b>Complexity</b>: Average case O(std::distance(b, e)),\r
1152    //!   worst case O(this->size()).\r
1153    //! \r
1154    //! <b>Throws</b>: Nothing.\r
1155    //! \r
1156    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1157    //!    to the erased elements. No destructors are called.\r
1158    void erase(const_iterator b, const_iterator e)\r
1159    {  table_.erase(b, e);  }\r
1160 \r
1161    //! <b>Effects</b>: Erases all the elements with the given value.\r
1162    //! \r
1163    //! <b>Returns</b>: The number of erased elements.\r
1164    //! \r
1165    //! <b>Complexity</b>: Average case O(this->count(value)).\r
1166    //!   Worst case O(this->size()).\r
1167    //! \r
1168    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.\r
1169    //! \r
1170    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1171    //!    to the erased elements. No destructors are called.\r
1172    size_type erase(const value_type &value)\r
1173    {  return table_.erase(value);  }\r
1174 \r
1175    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1176    //!   the same hash values as the stored hasher. The difference is that\r
1177    //!   "hasher" hashes the given key instead of the value_type.\r
1178    //!\r
1179    //!   "key_value_equal" must be a equality function that induces \r
1180    //!   the same equality as key_equal. The difference is that\r
1181    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
1182    //!\r
1183    //! <b>Effects</b>: Erases all the elements that have the same hash and\r
1184    //!   compare equal with the given key.\r
1185    //! \r
1186    //! <b>Returns</b>: The number of erased elements.\r
1187    //! \r
1188    //! <b>Complexity</b>: Average case O(this->count(value)).\r
1189    //!   Worst case O(this->size()).\r
1190    //! \r
1191    //! <b>Throws</b>: If the hasher or the equal functors throws. Basic guarantee.\r
1192    //! \r
1193    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1194    //!    to the erased elements. No destructors are called.\r
1195    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
1196    size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
1197    {  return table_.erase(key, hasher, equal);  }\r
1198 \r
1199    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1200    //!\r
1201    //! <b>Effects</b>: Erases the element pointed to by i. \r
1202    //!   Destroyer::operator()(pointer) is called for the removed element.\r
1203    //! \r
1204    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1205    //! \r
1206    //! <b>Throws</b>: Nothing.\r
1207    //! \r
1208    //! <b>Note</b>: Invalidates the iterators \r
1209    //!    to the erased elements.\r
1210    template<class Destroyer>\r
1211    void erase_and_destroy(const_iterator i, Destroyer destroyer)\r
1212    {  table_.erase_and_destroy(i, destroyer);  }\r
1213 \r
1214    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1215    //!\r
1216    //! <b>Effects</b>: Erases the range pointed to by b end e.\r
1217    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
1218    //! \r
1219    //! <b>Complexity</b>: Average case O(std::distance(b, e)),\r
1220    //!   worst case O(this->size()).\r
1221    //! \r
1222    //! <b>Throws</b>: Nothing.\r
1223    //! \r
1224    //! <b>Note</b>: Invalidates the iterators\r
1225    //!    to the erased elements.\r
1226    template<class Destroyer>\r
1227    void erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)\r
1228    {  table_.erase_and_destroy(b, e, destroyer);  }\r
1229 \r
1230    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1231    //!\r
1232    //! <b>Effects</b>: Erases all the elements with the given value.\r
1233    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
1234    //! \r
1235    //! <b>Returns</b>: The number of erased elements.\r
1236    //! \r
1237    //! <b>Complexity</b>: Average case O(this->count(value)).\r
1238    //!   Worst case O(this->size()).\r
1239    //! \r
1240    //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.\r
1241    //! \r
1242    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1243    //!    to the erased elements. No destructors are called.\r
1244    template<class Destroyer>\r
1245    size_type erase_and_destroy(const value_type &value, Destroyer destroyer)\r
1246    {  return table_.erase_and_destroy(value, destroyer);  }\r
1247 \r
1248    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1249    //!\r
1250    //! <b>Effects</b>: Erases all the elements with the given key.\r
1251    //!   according to the comparison functor "equal".\r
1252    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
1253    //!\r
1254    //! <b>Returns</b>: The number of erased elements.\r
1255    //! \r
1256    //! <b>Complexity</b>: Average case O(this->count(value)).\r
1257    //!   Worst case O(this->size()).\r
1258    //! \r
1259    //! <b>Throws</b>: If hasher or equal throw. Basic guarantee.\r
1260    //! \r
1261    //! <b>Note</b>: Invalidates the iterators\r
1262    //!    to the erased elements.\r
1263    template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>\r
1264    size_type erase_and_destroy(const KeyType& key, KeyHasher hasher, KeyValueEqual equal, Destroyer destroyer)\r
1265    {  return table_.erase_and_destroy(key, hasher, equal, destroyer);  }\r
1266 \r
1267    //! <b>Effects</b>: Erases all the elements of the container.\r
1268    //! \r
1269    //! <b>Complexity</b>: Linear to the number of elements on the container.\r
1270    //!   if it's a safe-mode or auto-unlink value_type. Constant time otherwise.\r
1271    //! \r
1272    //! <b>Throws</b>: Nothing.\r
1273    //! \r
1274    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1275    //!    to the erased elements. No destructors are called.\r
1276    void clear()\r
1277    {  return table_.clear();  }\r
1278 \r
1279    //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.\r
1280    //! \r
1281    //! <b>Effects</b>: Erases all the elements of the container.\r
1282    //! \r
1283    //! <b>Complexity</b>: Linear to the number of elements on the container.\r
1284    //!   Destroyer::operator()(pointer) is called for the removed elements.\r
1285    //! \r
1286    //! <b>Throws</b>: Nothing.\r
1287    //! \r
1288    //! <b>Note</b>: Invalidates the iterators (but not the references)\r
1289    //!    to the erased elements. No destructors are called.\r
1290    template<class Destroyer>\r
1291    void clear_and_destroy(Destroyer destroyer)\r
1292    {  return table_.clear_and_destroy(destroyer);  }\r
1293 \r
1294    //! <b>Effects</b>: Returns the number of contained elements with the given key\r
1295    //! \r
1296    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1297    //! \r
1298    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1299    size_type count(const value_type &value) const\r
1300    {  return table_.count(value);  }\r
1301 \r
1302    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1303    //!   the same hash values as the stored hasher. The difference is that\r
1304    //!   "hasher" hashes the given key instead of the value_type.\r
1305    //!\r
1306    //!   "key_value_equal" must be a equality function that induces \r
1307    //!   the same equality as key_equal. The difference is that\r
1308    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
1309    //!\r
1310    //! <b>Effects</b>: Returns the number of contained elements with the given key\r
1311    //!\r
1312    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1313    //! \r
1314    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1315    template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>\r
1316    size_type count(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const\r
1317    {  return table_.count(key, hasher, equal);  }\r
1318 \r
1319    //! <b>Effects</b>: Finds an iterator to the first element whose value is \r
1320    //!   "value" or end() if that element does not exist.\r
1321    //!\r
1322    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1323    //! \r
1324    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1325    iterator find(const value_type &value)\r
1326    {  return table_.find(value);  }\r
1327 \r
1328    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1329    //!   the same hash values as the stored hasher. The difference is that\r
1330    //!   "hasher" hashes the given key instead of the value_type.\r
1331    //!\r
1332    //!   "key_value_equal" must be a equality function that induces \r
1333    //!   the same equality as key_equal. The difference is that\r
1334    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
1335    //!\r
1336    //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
1337    //!   "key" according to the given hasher and equality functor or end() if\r
1338    //!   that element does not exist.\r
1339    //!\r
1340    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1341    //! \r
1342    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1343    //!\r
1344    //! <b>Note</b>: This function is used when constructing a value_type\r
1345    //!   is expensive and the value_type can be compared with a cheaper\r
1346    //!   key type. Usually this key is part of the value_type.\r
1347    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
1348    iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
1349    {  return table_.find(key, hasher, equal);  }\r
1350 \r
1351    //! <b>Effects</b>: Finds a const_iterator to the first element whose key is \r
1352    //!   "key" or end() if that element does not exist.\r
1353    //! \r
1354    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1355    //! \r
1356    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1357    const_iterator find(const value_type &value) const\r
1358    {  return table_.find(value);  }\r
1359 \r
1360    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1361    //!   the same hash values as the stored hasher. The difference is that\r
1362    //!   "hasher" hashes the given key instead of the value_type.\r
1363    //!\r
1364    //!   "key_value_equal" must be a equality function that induces \r
1365    //!   the same equality as key_equal. The difference is that\r
1366    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
1367    //!\r
1368    //! <b>Effects</b>: Finds an iterator to the first element whose key is \r
1369    //!   "key" according to the given hasher and equality functor or end() if\r
1370    //!   that element does not exist.\r
1371    //! \r
1372    //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).\r
1373    //! \r
1374    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1375    //!\r
1376    //! <b>Note</b>: This function is used when constructing a value_type\r
1377    //!   is expensive and the value_type can be compared with a cheaper\r
1378    //!   key type. Usually this key is part of the value_type.\r
1379    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
1380    const_iterator find(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const\r
1381    {  return table_.find(key, equal);  }\r
1382 \r
1383    //! <b>Effects</b>: Returns a range containing all elements with values equivalent\r
1384    //!   to value. Returns std::make_pair(this->end(), this->end()) if no such \r
1385    //!   elements exist.\r
1386    //! \r
1387    //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).\r
1388    //! \r
1389    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1390    std::pair<iterator,iterator> equal_range(const value_type &value)\r
1391    {  return table_.equal_range(value);  }\r
1392 \r
1393    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1394    //!   the same hash values as the stored hasher. The difference is that\r
1395    //!   "hasher" hashes the given key instead of the value_type.\r
1396    //!\r
1397    //!   "key_value_equal" must be a equality function that induces \r
1398    //!   the same equality as key_equal. The difference is that\r
1399    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
1400    //!\r
1401    //! <b>Effects</b>: Returns a range containing all elements with equivalent\r
1402    //!   keys. Returns std::make_pair(this->end(), this->end()) if no such \r
1403    //!   elements exist.\r
1404    //! \r
1405    //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).\r
1406    //! \r
1407    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1408    //!\r
1409    //! <b>Note</b>: This function is used when constructing a value_type\r
1410    //!   is expensive and the value_type can be compared with a cheaper\r
1411    //!   key type. Usually this key is part of the value_type.\r
1412    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
1413    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
1414    {  return table_.equal_range(key, hasher, equal);  }\r
1415 \r
1416    //! <b>Effects</b>: Returns a range containing all elements with values equivalent\r
1417    //!   to value. Returns std::make_pair(this->end(), this->end()) if no such \r
1418    //!   elements exist.\r
1419    //! \r
1420    //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).\r
1421    //! \r
1422    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1423    std::pair<const_iterator, const_iterator>\r
1424       equal_range(const value_type &value) const\r
1425    {  return table_.equal_range(value);  }\r
1426 \r
1427    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1428    //!   the same hash values as the stored hasher. The difference is that\r
1429    //!   "hasher" hashes the given key instead of the value_type.\r
1430    //!\r
1431    //!   "key_value_equal" must be a equality function that induces \r
1432    //!   the same equality as key_equal. The difference is that\r
1433    //!   "key_value_equal" compares an arbitrary key with the contained values.\r
1434    //!\r
1435    //! <b>Effects</b>: Returns a range containing all elements with equivalent\r
1436    //!   keys. Returns std::make_pair(this->end(), this->end()) if no such \r
1437    //!   elements exist.\r
1438    //! \r
1439    //! <b>Complexity</b>: Average case O(this->count(key, hasher, equal)). Worst case O(this->size()).\r
1440    //! \r
1441    //! <b>Throws</b>: If the internal hasher or the equality functor throws.\r
1442    //!\r
1443    //! <b>Note</b>: This function is used when constructing a value_type\r
1444    //!   is expensive and the value_type can be compared with a cheaper\r
1445    //!   key type. Usually this key is part of the value_type.\r
1446    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
1447    std::pair<const_iterator, const_iterator>\r
1448       equal_range(const KeyType& key, KeyHasher hasher, KeyValueEqual equal) const\r
1449    {  return table_.equal_range(key, equal);  }\r
1450 \r
1451    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of\r
1452    //!   appropriate type. Otherwise the behavior is undefined.\r
1453    //! \r
1454    //! <b>Effects</b>: Returns: a valid iterator i belonging to the iunordered_multiset\r
1455    //!   that points to the value\r
1456    //! \r
1457    //! <b>Complexity</b>: Constant.\r
1458    //! \r
1459    //! <b>Throws</b>: If the hash function throws.\r
1460    iterator current(value_type &value)\r
1461    {  return table_.current(value);  }\r
1462 \r
1463    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of\r
1464    //!   appropriate type. Otherwise the behavior is undefined.\r
1465    //! \r
1466    //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the\r
1467    //!   iunordered_multiset that points to the value\r
1468    //! \r
1469    //! <b>Complexity</b>: Constant.\r
1470    //! \r
1471    //! <b>Throws</b>: If the hash function throws.\r
1472    const_iterator current(const value_type &value) const\r
1473    {  return table_.current(value);  }\r
1474 \r
1475    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of\r
1476    //!   appropriate type. Otherwise the behavior is undefined.\r
1477    //! \r
1478    //! <b>Effects</b>: Returns: a valid local_iterator i belonging to the iunordered_multiset\r
1479    //!   that points to the value\r
1480    //! \r
1481    //! <b>Complexity</b>: Constant.\r
1482    //! \r
1483    //! <b>Throws</b>: Nothing.\r
1484    static local_iterator current_local(value_type &value)\r
1485    {  return table_type::current_local(value);  }\r
1486 \r
1487    //! <b>Requires</b>: value must be an lvalue and shall be in a iunordered_multiset of\r
1488    //!   appropriate type. Otherwise the behavior is undefined.\r
1489    //! \r
1490    //! <b>Effects</b>: Returns: a valid const_local_iterator i belonging to\r
1491    //!   the iunordered_multiset that points to the value\r
1492    //! \r
1493    //! <b>Complexity</b>: Constant.\r
1494    //! \r
1495    //! <b>Throws</b>: Nothing.\r
1496    static const_local_iterator current_local(const value_type &value)\r
1497    {  return table_type::current_local(value);  }\r
1498 \r
1499    //! <b>Effects</b>: Returns the number of buckets passed in the constructor\r
1500    //!   or the last rehash function.\r
1501    //! \r
1502    //! <b>Complexity</b>: Constant.\r
1503    //! \r
1504    //! <b>Throws</b>: Nothing.\r
1505    size_type bucket_count() const\r
1506    {  return table_.bucket_count();   }\r
1507 \r
1508    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
1509    //!\r
1510    //! <b>Effects</b>: Returns the number of elements in the nth bucket.\r
1511    //! \r
1512    //! <b>Complexity</b>: Constant.\r
1513    //! \r
1514    //! <b>Throws</b>: Nothing.\r
1515    size_type bucket_size(size_type n)\r
1516    {  return table_.bucket_size(n);   }\r
1517 \r
1518    //! <b>Effects</b>: Returns the index of the bucket in which elements\r
1519    //!   with keys equivalent to k would be found, if any such element existed.\r
1520    //! \r
1521    //! <b>Complexity</b>: Constant.\r
1522    //! \r
1523    //! <b>Throws</b>: If the hash functor throws.\r
1524    //!\r
1525    //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).\r
1526    size_type bucket(const key_type& k)\r
1527    {  return table_.bucket(k);   }\r
1528 \r
1529    //! <b>Requires</b>: "hasher" must be a hash function that induces \r
1530    //!   the same hash values as the stored hasher. The difference is that\r
1531    //!   "hasher" hashes the given key instead of the value_type.\r
1532    //!\r
1533    //! <b>Effects</b>: Returns the index of the bucket in which elements\r
1534    //!   with keys equivalent to k would be found, if any such element existed.\r
1535    //! \r
1536    //! <b>Complexity</b>: Constant.\r
1537    //! \r
1538    //! <b>Throws</b>: If the hash functor throws.\r
1539    //!\r
1540    //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).\r
1541    template<class KeyType, class KeyHasher>\r
1542    size_type bucket(const KeyType& k, const KeyHasher &hasher)\r
1543    {  return table_.bucket(k, hasher);   }\r
1544 \r
1545    //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor\r
1546    //!   or the last rehash function.\r
1547    //! \r
1548    //! <b>Complexity</b>: Constant.\r
1549    //! \r
1550    //! <b>Throws</b>: Nothing.\r
1551    bucket_ptr bucket_pointer() const\r
1552    {  return table_.bucket_pointer();   }\r
1553 \r
1554    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
1555    //!\r
1556    //! <b>Effects</b>: Returns a local_iterator pointing to the beginning\r
1557    //!   of the sequence stored in the bucket n.\r
1558    //! \r
1559    //! <b>Complexity</b>: Constant.\r
1560    //! \r
1561    //! <b>Throws</b>: Nothing.\r
1562    //! \r
1563    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
1564    //!   containing all of the elements in the nth bucket. \r
1565    local_iterator begin(size_type n)\r
1566    {  return table_.begin(n);   }\r
1567 \r
1568    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
1569    //!\r
1570    //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning\r
1571    //!   of the sequence stored in the bucket n.\r
1572    //! \r
1573    //! <b>Complexity</b>: Constant.\r
1574    //! \r
1575    //! <b>Throws</b>: Nothing.\r
1576    //! \r
1577    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
1578    //!   containing all of the elements in the nth bucket. \r
1579    const_local_iterator begin(size_type n) const\r
1580    {  return table_.begin(n);   }\r
1581 \r
1582    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
1583    //!\r
1584    //! <b>Effects</b>: Returns a local_iterator pointing to the end\r
1585    //!   of the sequence stored in the bucket n.\r
1586    //! \r
1587    //! <b>Complexity</b>: Constant.\r
1588    //! \r
1589    //! <b>Throws</b>: Nothing.\r
1590    //! \r
1591    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
1592    //!   containing all of the elements in the nth bucket. \r
1593    local_iterator end(size_type n)\r
1594    {  return table_.end(n);   }\r
1595 \r
1596    //! <b>Requires</b>: n is in the range [0, this->bucket_count()).\r
1597    //!\r
1598    //! <b>Effects</b>: Returns a const_local_iterator pointing to the end\r
1599    //!   of the sequence stored in the bucket n.\r
1600    //! \r
1601    //! <b>Complexity</b>: Constant.\r
1602    //! \r
1603    //! <b>Throws</b>: Nothing.\r
1604    //! \r
1605    //! <b>Note</b>:  [this->begin(n), this->end(n)) is a valid range\r
1606    //!   containing all of the elements in the nth bucket. \r
1607    const_local_iterator end(size_type n) const\r
1608    {  return table_.end(n);   }\r
1609 \r
1610    //! <b>Requires</b>: new_buckets must be a pointer to a new bucket array\r
1611    //!   or the same as the old bucket array. new_size is the length of the\r
1612    //!   the array pointed by new_buckets. If new_buckets == this->bucket_pointer()\r
1613    //!   n can be bigger or smaller than this->bucket_count().\r
1614    //!\r
1615    //! <b>Effects</b>: Updates the internal reference with the new bucket erases\r
1616    //!   the values from the old bucket and inserts then in the new one. \r
1617    //! \r
1618    //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.\r
1619    //! \r
1620    //! <b>Throws</b>: If the hasher functor throws.\r
1621    void rehash(bucket_ptr new_buckets, size_type new_size)\r
1622    {  table_.rehash(new_buckets, new_size); }\r
1623 \r
1624    //! <b>Effects</b>: Returns the nearest new bucket count optimized for\r
1625    //!   the container that is bigger than n. This suggestion can be used\r
1626    //!   to create bucket arrays with a size that will usually improve\r
1627    //!   container's performance. If such value does not exist, the \r
1628    //!   higher possible value is returned.\r
1629    //! \r
1630    //! <b>Complexity</b>: Amortized constant time.\r
1631    //! \r
1632    //! <b>Throws</b>: Nothing.\r
1633    static size_type suggested_upper_bucket_count(size_type n)\r
1634    {  return table_type::suggested_upper_bucket_count(n);  }\r
1635 \r
1636    //! <b>Effects</b>: Returns the nearest new bucket count optimized for\r
1637    //!   the container that is smaller than n. This suggestion can be used\r
1638    //!   to create bucket arrays with a size that will usually improve\r
1639    //!   container's performance. If such value does not exist, the \r
1640    //!   lower possible value is returned.\r
1641    //! \r
1642    //! <b>Complexity</b>: Amortized constant time.\r
1643    //! \r
1644    //! <b>Throws</b>: Nothing.\r
1645    static size_type suggested_lower_bucket_count(size_type n)\r
1646    {  return table_type::suggested_lower_bucket_count(n);  }\r
1647 };\r
1648 \r
1649 } //namespace intrusive \r
1650 } //namespace boost \r
1651 \r
1652 #include <boost/intrusive/detail/config_end.hpp>\r
1653 \r
1654 #endif //BOOST_INTRUSIVE_IHASHSET_HPP\r