libstdc++-v3/include/bits/unordered_set.h

   1 // unordered_set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2010 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file bits/unordered_set.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{unordered_set}
  28  */
  29
  30 #ifndef _UNORDERED_SET_H
  31 #define _UNORDERED_SET_H
  32
  33 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  34
  35   // XXX When we get typedef templates these class definitions
  36   // will be unnecessary.
  37   template<class _Value,
  38            class _Hash = hash<_Value>,
  39            class _Pred = std::equal_to<_Value>,
  40            class _Alloc = std::allocator<_Value>,
  41            bool __cache_hash_code = false>
  42     class __unordered_set
  43     : public _Hashtable<_Value, _Value, _Alloc,
  44                         std::_Identity<_Value>, _Pred,
  45                         _Hash, __detail::_Mod_range_hashing,
  46                         __detail::_Default_ranged_hash,
  47                         __detail::_Prime_rehash_policy,
  48                         __cache_hash_code, true, true>
  49     {
  50       typedef _Hashtable<_Value, _Value, _Alloc,
  51                          std::_Identity<_Value>, _Pred,
  52                          _Hash, __detail::_Mod_range_hashing,
  53                          __detail::_Default_ranged_hash,
  54                          __detail::_Prime_rehash_policy,
  55                          __cache_hash_code, true, true>
  56         _Base;
  57
  58     public:
  59       typedef typename _Base::value_type      value_type;
  60       typedef typename _Base::size_type       size_type;
  61       typedef typename _Base::hasher          hasher;
  62       typedef typename _Base::key_equal       key_equal;
  63       typedef typename _Base::allocator_type  allocator_type;
  64
  65       explicit
  66       __unordered_set(size_type __n = 10,
  67                       const hasher& __hf = hasher(),
  68                       const key_equal& __eql = key_equal(),
  69                       const allocator_type& __a = allocator_type())
  70       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
  71               __detail::_Default_ranged_hash(), __eql,
  72               std::_Identity<value_type>(), __a)
  73       { }
  74
  75       template<typename _InputIterator>
  76         __unordered_set(_InputIterator __f, _InputIterator __l,
  77                         size_type __n = 0,
  78                         const hasher& __hf = hasher(),
  79                         const key_equal& __eql = key_equal(),
  80                         const allocator_type& __a = allocator_type())
  81         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
  82                 __detail::_Default_ranged_hash(), __eql,
  83                 std::_Identity<value_type>(), __a)
  84         { }
  85
  86       __unordered_set(initializer_list<value_type> __l,
  87                       size_type __n = 0,
  88                       const hasher& __hf = hasher(),
  89                       const key_equal& __eql = key_equal(),
  90                       const allocator_type& __a = allocator_type())
  91       : _Base(__l.begin(), __l.end(), __n, __hf,
  92               __detail::_Mod_range_hashing(),
  93               __detail::_Default_ranged_hash(), __eql,
  94               std::_Identity<value_type>(), __a)
  95       { }
  96
  97       __unordered_set&
  98       operator=(initializer_list<value_type> __l)
  99       {
 100         this->clear();
 101         this->insert(__l.begin(), __l.end());
 102         return *this;
 103       }
 104     };
 105
 106   template<class _Value,
 107            class _Hash = hash<_Value>,
 108            class _Pred = std::equal_to<_Value>,
 109            class _Alloc = std::allocator<_Value>,
 110            bool __cache_hash_code = false>
 111     class __unordered_multiset
 112     : public _Hashtable<_Value, _Value, _Alloc,
 113                         std::_Identity<_Value>, _Pred,
 114                         _Hash, __detail::_Mod_range_hashing,
 115                         __detail::_Default_ranged_hash,
 116                         __detail::_Prime_rehash_policy,
 117                         __cache_hash_code, true, false>
 118     {
 119       typedef _Hashtable<_Value, _Value, _Alloc,
 120                          std::_Identity<_Value>, _Pred,
 121                          _Hash, __detail::_Mod_range_hashing,
 122                          __detail::_Default_ranged_hash,
 123                          __detail::_Prime_rehash_policy,
 124                          __cache_hash_code, true, false>
 125         _Base;
 126
 127     public:
 128       typedef typename _Base::value_type      value_type;
 129       typedef typename _Base::size_type       size_type;
 130       typedef typename _Base::hasher          hasher;
 131       typedef typename _Base::key_equal       key_equal;
 132       typedef typename _Base::allocator_type  allocator_type;
 133
 134       explicit
 135       __unordered_multiset(size_type __n = 10,
 136                            const hasher& __hf = hasher(),
 137                            const key_equal& __eql = key_equal(),
 138                            const allocator_type& __a = allocator_type())
 139       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
 140               __detail::_Default_ranged_hash(), __eql,
 141               std::_Identity<value_type>(), __a)
 142       { }
 143
 144
 145       template<typename _InputIterator>
 146         __unordered_multiset(_InputIterator __f, _InputIterator __l,
 147                              size_type __n = 0,
 148                              const hasher& __hf = hasher(),
 149                              const key_equal& __eql = key_equal(),
 150                              const allocator_type& __a = allocator_type())
 151         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
 152                 __detail::_Default_ranged_hash(), __eql,
 153                 std::_Identity<value_type>(), __a)
 154         { }
 155
 156       __unordered_multiset(initializer_list<value_type> __l,
 157                            size_type __n = 0,
 158                            const hasher& __hf = hasher(),
 159                            const key_equal& __eql = key_equal(),
 160                            const allocator_type& __a = allocator_type())
 161       : _Base(__l.begin(), __l.end(), __n, __hf,
 162               __detail::_Mod_range_hashing(),
 163               __detail::_Default_ranged_hash(), __eql,
 164               std::_Identity<value_type>(), __a)
 165       { }
 166
 167       __unordered_multiset&
 168       operator=(initializer_list<value_type> __l)
 169       {
 170         this->clear();
 171         this->insert(__l.begin(), __l.end());
 172         return *this;
 173       }
 174     };
 175
 176   template<class _Value, class _Hash, class _Pred, class _Alloc,
 177            bool __cache_hash_code>
 178     inline void
 179     swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
 180          __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
 181     { __x.swap(__y); }
 182
 183   template<class _Value, class _Hash, class _Pred, class _Alloc,
 184            bool __cache_hash_code>
 185     inline void
 186     swap(__unordered_multiset<_Value, _Hash, _Pred,
 187          _Alloc, __cache_hash_code>& __x,
 188          __unordered_multiset<_Value, _Hash, _Pred,
 189          _Alloc, __cache_hash_code>& __y)
 190     { __x.swap(__y); }
 191
 192   template<class _Value, class _Hash, class _Pred, class _Alloc,
 193            bool __cache_hash_code>
 194     inline bool
 195     operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 196                __cache_hash_code>& __x,
 197                const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 198                __cache_hash_code>& __y)
 199     { return __x._M_equal(__y); }
 200
 201   template<class _Value, class _Hash, class _Pred, class _Alloc,
 202            bool __cache_hash_code>
 203     inline bool
 204     operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 205                __cache_hash_code>& __x,
 206                const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 207                __cache_hash_code>& __y)
 208     { return !(__x == __y); }
 209
 210   template<class _Value, class _Hash, class _Pred, class _Alloc,
 211            bool __cache_hash_code>
 212     inline bool
 213     operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 214                __cache_hash_code>& __x,
 215                const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 216                __cache_hash_code>& __y)
 217     { return __x._M_equal(__y); }
 218
 219   template<class _Value, class _Hash, class _Pred, class _Alloc,
 220            bool __cache_hash_code>
 221     inline bool
 222     operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 223                __cache_hash_code>& __x,
 224                const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 225                __cache_hash_code>& __y)
 226     { return !(__x == __y); }
 227
 228   /**
 229    *  @brief A standard container composed of unique keys (containing
 230    *  at most one of each key value) in which the elements' keys are
 231    *  the elements themselves.
 232    *
 233    *  @ingroup unordered_associative_containers
 234    *
 235    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 236    *  <a href="tables.html#xx">unordered associative container</a>
 237    *
 238    *  @param  Value  Type of key objects.
 239    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 240    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 241    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 242    */
 243   template<class _Value,
 244            class _Hash = hash<_Value>,
 245            class _Pred = std::equal_to<_Value>,
 246            class _Alloc = std::allocator<_Value> >
 247     class unordered_set
 248     : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
 249     {
 250       typedef __unordered_set<_Value, _Hash, _Pred, _Alloc>  _Base;
 251
 252     public:
 253       typedef typename _Base::value_type      value_type;
 254       typedef typename _Base::size_type       size_type;
 255       typedef typename _Base::hasher          hasher;
 256       typedef typename _Base::key_equal       key_equal;
 257       typedef typename _Base::allocator_type  allocator_type;
 258
 259       explicit
 260       unordered_set(size_type __n = 10,
 261                     const hasher& __hf = hasher(),
 262                     const key_equal& __eql = key_equal(),
 263                     const allocator_type& __a = allocator_type())
 264       : _Base(__n, __hf, __eql, __a)
 265       { }
 266
 267       template<typename _InputIterator>
 268         unordered_set(_InputIterator __f, _InputIterator __l,
 269                       size_type __n = 0,
 270                       const hasher& __hf = hasher(),
 271                       const key_equal& __eql = key_equal(),
 272                       const allocator_type& __a = allocator_type())
 273         : _Base(__f, __l, __n, __hf, __eql, __a)
 274         { }
 275
 276       unordered_set(initializer_list<value_type> __l,
 277                     size_type __n = 0,
 278                     const hasher& __hf = hasher(),
 279                     const key_equal& __eql = key_equal(),
 280                     const allocator_type& __a = allocator_type())
 281       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
 282       { }
 283
 284       unordered_set&
 285       operator=(initializer_list<value_type> __l)
 286       {
 287         this->clear();
 288         this->insert(__l.begin(), __l.end());
 289         return *this;
 290       }
 291     };
 292
 293   /**
 294    *  @brief A standard container composed of equivalent keys
 295    *  (possibly containing multiple of each key value) in which the
 296    *  elements' keys are the elements themselves.
 297    *
 298    *  @ingroup unordered_associative_containers
 299    *
 300    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 301    *  <a href="tables.html#xx">unordered associative container</a>
 302    *
 303    *  @param  Value  Type of key objects.
 304    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 305    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 306    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 307    */
 308   template<class _Value,
 309            class _Hash = hash<_Value>,
 310            class _Pred = std::equal_to<_Value>,
 311            class _Alloc = std::allocator<_Value> >
 312     class unordered_multiset
 313     : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 314     {
 315       typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc>  _Base;
 316
 317     public:
 318       typedef typename _Base::value_type      value_type;
 319       typedef typename _Base::size_type       size_type;
 320       typedef typename _Base::hasher          hasher;
 321       typedef typename _Base::key_equal       key_equal;
 322       typedef typename _Base::allocator_type  allocator_type;
 323
 324       explicit
 325       unordered_multiset(size_type __n = 10,
 326                          const hasher& __hf = hasher(),
 327                          const key_equal& __eql = key_equal(),
 328                          const allocator_type& __a = allocator_type())
 329       : _Base(__n, __hf, __eql, __a)
 330       { }
 331
 332
 333       template<typename _InputIterator>
 334         unordered_multiset(_InputIterator __f, _InputIterator __l,
 335                            size_type __n = 0,
 336                            const hasher& __hf = hasher(),
 337                            const key_equal& __eql = key_equal(),
 338                            const allocator_type& __a = allocator_type())
 339         : _Base(__f, __l, __n, __hf, __eql, __a)
 340         { }
 341
 342       unordered_multiset(initializer_list<value_type> __l,
 343                          size_type __n = 0,
 344                          const hasher& __hf = hasher(),
 345                          const key_equal& __eql = key_equal(),
 346                          const allocator_type& __a = allocator_type())
 347       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
 348       { }
 349
 350       unordered_multiset&
 351       operator=(initializer_list<value_type> __l)
 352       {
 353         this->clear();
 354         this->insert(__l.begin(), __l.end());
 355         return *this;
 356       }
 357     };
 358
 359   template<class _Value, class _Hash, class _Pred, class _Alloc>
 360     inline void
 361     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 362          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 363     { __x.swap(__y); }
 364
 365   template<class _Value, class _Hash, class _Pred, class _Alloc>
 366     inline void
 367     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 368          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 369     { __x.swap(__y); }
 370
 371   template<class _Value, class _Hash, class _Pred, class _Alloc>
 372     inline bool
 373     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 374                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 375     { return __x._M_equal(__y); }
 376
 377   template<class _Value, class _Hash, class _Pred, class _Alloc>
 378     inline bool
 379     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 380                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 381     { return !(__x == __y); }
 382
 383   template<class _Value, class _Hash, class _Pred, class _Alloc>
 384     inline bool
 385     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 386                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 387     { return __x._M_equal(__y); }
 388
 389   template<class _Value, class _Hash, class _Pred, class _Alloc>
 390     inline bool
 391     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 392                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 393     { return !(__x == __y); }
 394
 395 _GLIBCXX_END_NESTED_NAMESPACE
 396
 397 #endif /* _UNORDERED_SET_H */
 398