l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/bits/unordered_set.h

   1 // unordered_set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2010, 2011 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 namespace std _GLIBCXX_VISIBILITY(default)
  34 {
  35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  36
  37   // NB: When we get typedef templates these class definitions
  38   // will be unnecessary.
  39   template<class _Value,
  40            class _Hash = hash<_Value>,
  41            class _Pred = std::equal_to<_Value>,
  42            class _Alloc = std::allocator<_Value>,
  43            bool __cache_hash_code = false>
  44     class __unordered_set
  45     : public _Hashtable<_Value, _Value, _Alloc,
  46                         std::_Identity<_Value>, _Pred,
  47                         _Hash, __detail::_Mod_range_hashing,
  48                         __detail::_Default_ranged_hash,
  49                         __detail::_Prime_rehash_policy,
  50                         __cache_hash_code, true, true>
  51     {
  52       typedef _Hashtable<_Value, _Value, _Alloc,
  53                          std::_Identity<_Value>, _Pred,
  54                          _Hash, __detail::_Mod_range_hashing,
  55                          __detail::_Default_ranged_hash,
  56                          __detail::_Prime_rehash_policy,
  57                          __cache_hash_code, true, true>
  58         _Base;
  59
  60     public:
  61       typedef typename _Base::value_type      value_type;
  62       typedef typename _Base::size_type       size_type;
  63       typedef typename _Base::hasher          hasher;
  64       typedef typename _Base::key_equal       key_equal;
  65       typedef typename _Base::allocator_type  allocator_type;
  66
  67       explicit
  68       __unordered_set(size_type __n = 10,
  69                       const hasher& __hf = hasher(),
  70                       const key_equal& __eql = key_equal(),
  71                       const allocator_type& __a = allocator_type())
  72       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
  73               __detail::_Default_ranged_hash(), __eql,
  74               std::_Identity<value_type>(), __a)
  75       { }
  76
  77       template<typename _InputIterator>
  78         __unordered_set(_InputIterator __f, _InputIterator __l,
  79                         size_type __n = 0,
  80                         const hasher& __hf = hasher(),
  81                         const key_equal& __eql = key_equal(),
  82                         const allocator_type& __a = allocator_type())
  83         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
  84                 __detail::_Default_ranged_hash(), __eql,
  85                 std::_Identity<value_type>(), __a)
  86         { }
  87
  88       __unordered_set(initializer_list<value_type> __l,
  89                       size_type __n = 0,
  90                       const hasher& __hf = hasher(),
  91                       const key_equal& __eql = key_equal(),
  92                       const allocator_type& __a = allocator_type())
  93       : _Base(__l.begin(), __l.end(), __n, __hf,
  94               __detail::_Mod_range_hashing(),
  95               __detail::_Default_ranged_hash(), __eql,
  96               std::_Identity<value_type>(), __a)
  97       { }
  98
  99       __unordered_set&
 100       operator=(initializer_list<value_type> __l)
 101       {
 102         this->clear();
 103         this->insert(__l.begin(), __l.end());
 104         return *this;
 105       }
 106     };
 107
 108   template<class _Value,
 109            class _Hash = hash<_Value>,
 110            class _Pred = std::equal_to<_Value>,
 111            class _Alloc = std::allocator<_Value>,
 112            bool __cache_hash_code = false>
 113     class __unordered_multiset
 114     : public _Hashtable<_Value, _Value, _Alloc,
 115                         std::_Identity<_Value>, _Pred,
 116                         _Hash, __detail::_Mod_range_hashing,
 117                         __detail::_Default_ranged_hash,
 118                         __detail::_Prime_rehash_policy,
 119                         __cache_hash_code, true, false>
 120     {
 121       typedef _Hashtable<_Value, _Value, _Alloc,
 122                          std::_Identity<_Value>, _Pred,
 123                          _Hash, __detail::_Mod_range_hashing,
 124                          __detail::_Default_ranged_hash,
 125                          __detail::_Prime_rehash_policy,
 126                          __cache_hash_code, true, false>
 127         _Base;
 128
 129     public:
 130       typedef typename _Base::value_type      value_type;
 131       typedef typename _Base::size_type       size_type;
 132       typedef typename _Base::hasher          hasher;
 133       typedef typename _Base::key_equal       key_equal;
 134       typedef typename _Base::allocator_type  allocator_type;
 135
 136       explicit
 137       __unordered_multiset(size_type __n = 10,
 138                            const hasher& __hf = hasher(),
 139                            const key_equal& __eql = key_equal(),
 140                            const allocator_type& __a = allocator_type())
 141       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
 142               __detail::_Default_ranged_hash(), __eql,
 143               std::_Identity<value_type>(), __a)
 144       { }
 145
 146
 147       template<typename _InputIterator>
 148         __unordered_multiset(_InputIterator __f, _InputIterator __l,
 149                              size_type __n = 0,
 150                              const hasher& __hf = hasher(),
 151                              const key_equal& __eql = key_equal(),
 152                              const allocator_type& __a = allocator_type())
 153         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
 154                 __detail::_Default_ranged_hash(), __eql,
 155                 std::_Identity<value_type>(), __a)
 156         { }
 157
 158       __unordered_multiset(initializer_list<value_type> __l,
 159                            size_type __n = 0,
 160                            const hasher& __hf = hasher(),
 161                            const key_equal& __eql = key_equal(),
 162                            const allocator_type& __a = allocator_type())
 163       : _Base(__l.begin(), __l.end(), __n, __hf,
 164               __detail::_Mod_range_hashing(),
 165               __detail::_Default_ranged_hash(), __eql,
 166               std::_Identity<value_type>(), __a)
 167       { }
 168
 169       __unordered_multiset&
 170       operator=(initializer_list<value_type> __l)
 171       {
 172         this->clear();
 173         this->insert(__l.begin(), __l.end());
 174         return *this;
 175       }
 176     };
 177
 178   template<class _Value, class _Hash, class _Pred, class _Alloc,
 179            bool __cache_hash_code>
 180     inline void
 181     swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
 182          __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
 183     { __x.swap(__y); }
 184
 185   template<class _Value, class _Hash, class _Pred, class _Alloc,
 186            bool __cache_hash_code>
 187     inline void
 188     swap(__unordered_multiset<_Value, _Hash, _Pred,
 189          _Alloc, __cache_hash_code>& __x,
 190          __unordered_multiset<_Value, _Hash, _Pred,
 191          _Alloc, __cache_hash_code>& __y)
 192     { __x.swap(__y); }
 193
 194   template<class _Value, class _Hash, class _Pred, class _Alloc,
 195            bool __cache_hash_code>
 196     inline bool
 197     operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 198                __cache_hash_code>& __x,
 199                const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 200                __cache_hash_code>& __y)
 201     { return __x._M_equal(__y); }
 202
 203   template<class _Value, class _Hash, class _Pred, class _Alloc,
 204            bool __cache_hash_code>
 205     inline bool
 206     operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 207                __cache_hash_code>& __x,
 208                const __unordered_set<_Value, _Hash, _Pred, _Alloc,
 209                __cache_hash_code>& __y)
 210     { return !(__x == __y); }
 211
 212   template<class _Value, class _Hash, class _Pred, class _Alloc,
 213            bool __cache_hash_code>
 214     inline bool
 215     operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 216                __cache_hash_code>& __x,
 217                const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 218                __cache_hash_code>& __y)
 219     { return __x._M_equal(__y); }
 220
 221   template<class _Value, class _Hash, class _Pred, class _Alloc,
 222            bool __cache_hash_code>
 223     inline bool
 224     operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 225                __cache_hash_code>& __x,
 226                const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
 227                __cache_hash_code>& __y)
 228     { return !(__x == __y); }
 229
 230   /**
 231    *  @brief A standard container composed of unique keys (containing
 232    *  at most one of each key value) in which the elements' keys are
 233    *  the elements themselves.
 234    *
 235    *  @ingroup unordered_associative_containers
 236    *
 237    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 238    *  <a href="tables.html#xx">unordered associative container</a>
 239    *
 240    *  @param  Value  Type of key objects.
 241    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 242    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 243    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 244    */
 245   template<class _Value,
 246            class _Hash = hash<_Value>,
 247            class _Pred = std::equal_to<_Value>,
 248            class _Alloc = std::allocator<_Value> >
 249     class unordered_set
 250     : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
 251     {
 252       typedef __unordered_set<_Value, _Hash, _Pred, _Alloc>  _Base;
 253
 254     public:
 255       typedef typename _Base::value_type      value_type;
 256       typedef typename _Base::size_type       size_type;
 257       typedef typename _Base::hasher          hasher;
 258       typedef typename _Base::key_equal       key_equal;
 259       typedef typename _Base::allocator_type  allocator_type;
 260
 261       explicit
 262       unordered_set(size_type __n = 10,
 263                     const hasher& __hf = hasher(),
 264                     const key_equal& __eql = key_equal(),
 265                     const allocator_type& __a = allocator_type())
 266       : _Base(__n, __hf, __eql, __a)
 267       { }
 268
 269       template<typename _InputIterator>
 270         unordered_set(_InputIterator __f, _InputIterator __l,
 271                       size_type __n = 0,
 272                       const hasher& __hf = hasher(),
 273                       const key_equal& __eql = key_equal(),
 274                       const allocator_type& __a = allocator_type())
 275         : _Base(__f, __l, __n, __hf, __eql, __a)
 276         { }
 277
 278       unordered_set(initializer_list<value_type> __l,
 279                     size_type __n = 0,
 280                     const hasher& __hf = hasher(),
 281                     const key_equal& __eql = key_equal(),
 282                     const allocator_type& __a = allocator_type())
 283       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
 284       { }
 285
 286       unordered_set&
 287       operator=(initializer_list<value_type> __l)
 288       {
 289         this->clear();
 290         this->insert(__l.begin(), __l.end());
 291         return *this;
 292       }
 293     };
 294
 295   /**
 296    *  @brief A standard container composed of equivalent keys
 297    *  (possibly containing multiple of each key value) in which the
 298    *  elements' keys are the elements themselves.
 299    *
 300    *  @ingroup unordered_associative_containers
 301    *
 302    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 303    *  <a href="tables.html#xx">unordered associative container</a>
 304    *
 305    *  @param  Value  Type of key objects.
 306    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 307    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 308    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 309    */
 310   template<class _Value,
 311            class _Hash = hash<_Value>,
 312            class _Pred = std::equal_to<_Value>,
 313            class _Alloc = std::allocator<_Value> >
 314     class unordered_multiset
 315     : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 316     {
 317       typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc>  _Base;
 318
 319     public:
 320       typedef typename _Base::value_type      value_type;
 321       typedef typename _Base::size_type       size_type;
 322       typedef typename _Base::hasher          hasher;
 323       typedef typename _Base::key_equal       key_equal;
 324       typedef typename _Base::allocator_type  allocator_type;
 325
 326       explicit
 327       unordered_multiset(size_type __n = 10,
 328                          const hasher& __hf = hasher(),
 329                          const key_equal& __eql = key_equal(),
 330                          const allocator_type& __a = allocator_type())
 331       : _Base(__n, __hf, __eql, __a)
 332       { }
 333
 334
 335       template<typename _InputIterator>
 336         unordered_multiset(_InputIterator __f, _InputIterator __l,
 337                            size_type __n = 0,
 338                            const hasher& __hf = hasher(),
 339                            const key_equal& __eql = key_equal(),
 340                            const allocator_type& __a = allocator_type())
 341         : _Base(__f, __l, __n, __hf, __eql, __a)
 342         { }
 343
 344       unordered_multiset(initializer_list<value_type> __l,
 345                          size_type __n = 0,
 346                          const hasher& __hf = hasher(),
 347                          const key_equal& __eql = key_equal(),
 348                          const allocator_type& __a = allocator_type())
 349       : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
 350       { }
 351
 352       unordered_multiset&
 353       operator=(initializer_list<value_type> __l)
 354       {
 355         this->clear();
 356         this->insert(__l.begin(), __l.end());
 357         return *this;
 358       }
 359     };
 360
 361   template<class _Value, class _Hash, class _Pred, class _Alloc>
 362     inline void
 363     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 364          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 365     { __x.swap(__y); }
 366
 367   template<class _Value, class _Hash, class _Pred, class _Alloc>
 368     inline void
 369     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 370          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 371     { __x.swap(__y); }
 372
 373   template<class _Value, class _Hash, class _Pred, class _Alloc>
 374     inline bool
 375     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 376                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 377     { return __x._M_equal(__y); }
 378
 379   template<class _Value, class _Hash, class _Pred, class _Alloc>
 380     inline bool
 381     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 382                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 383     { return !(__x == __y); }
 384
 385   template<class _Value, class _Hash, class _Pred, class _Alloc>
 386     inline bool
 387     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 388                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 389     { return __x._M_equal(__y); }
 390
 391   template<class _Value, class _Hash, class _Pred, class _Alloc>
 392     inline bool
 393     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 394                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 395     { return !(__x == __y); }
 396
 397 _GLIBCXX_END_NAMESPACE_CONTAINER
 398 } // namespace std
 399
 400 #endif /* _UNORDERED_SET_H */
 401