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

   1 // TR1 unordered_set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2010-2013 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 tr1/unordered_set.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{tr1/unordered_set}
  28  */
  29
  30 namespace std _GLIBCXX_VISIBILITY(default)
  31 {
  32 namespace tr1
  33 {
  34 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  35
  36   // NB: When we get typedef templates these class definitions
  37   // will be unnecessary.
  38   template<class _Value,
  39            class _Hash = hash<_Value>,
  40            class _Pred = std::equal_to<_Value>,
  41            class _Alloc = std::allocator<_Value>,
  42            bool __cache_hash_code = false>
  43     class __unordered_set
  44     : public _Hashtable<_Value, _Value, _Alloc,
  45                         std::_Identity<_Value>, _Pred,
  46                         _Hash, __detail::_Mod_range_hashing,
  47                         __detail::_Default_ranged_hash,
  48                         __detail::_Prime_rehash_policy,
  49                         __cache_hash_code, true, true>
  50     {
  51       typedef _Hashtable<_Value, _Value, _Alloc,
  52                          std::_Identity<_Value>, _Pred,
  53                          _Hash, __detail::_Mod_range_hashing,
  54                          __detail::_Default_ranged_hash,
  55                          __detail::_Prime_rehash_policy,
  56                          __cache_hash_code, true, true>
  57         _Base;
  58
  59     public:
  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>(), __a)
  73       { }
  74
  75       template<typename _InputIterator>
  76         __unordered_set(_InputIterator __f, _InputIterator __l,
  77                         size_type __n = 10,
  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>(), __a)
  84         { }
  85     };
  86
  87   template<class _Value,
  88            class _Hash = hash<_Value>,
  89            class _Pred = std::equal_to<_Value>,
  90            class _Alloc = std::allocator<_Value>,
  91            bool __cache_hash_code = false>
  92     class __unordered_multiset
  93     : public _Hashtable<_Value, _Value, _Alloc,
  94                         std::_Identity<_Value>, _Pred,
  95                         _Hash, __detail::_Mod_range_hashing,
  96                         __detail::_Default_ranged_hash,
  97                         __detail::_Prime_rehash_policy,
  98                         __cache_hash_code, true, false>
  99     {
 100       typedef _Hashtable<_Value, _Value, _Alloc,
 101                          std::_Identity<_Value>, _Pred,
 102                          _Hash, __detail::_Mod_range_hashing,
 103                          __detail::_Default_ranged_hash,
 104                          __detail::_Prime_rehash_policy,
 105                          __cache_hash_code, true, false>
 106         _Base;
 107
 108     public:
 109       typedef typename _Base::size_type       size_type;
 110       typedef typename _Base::hasher          hasher;
 111       typedef typename _Base::key_equal       key_equal;
 112       typedef typename _Base::allocator_type  allocator_type;
 113
 114       explicit
 115       __unordered_multiset(size_type __n = 10,
 116                            const hasher& __hf = hasher(),
 117                            const key_equal& __eql = key_equal(),
 118                            const allocator_type& __a = allocator_type())
 119       : _Base(__n, __hf, __detail::_Mod_range_hashing(),
 120               __detail::_Default_ranged_hash(), __eql,
 121               std::_Identity<_Value>(), __a)
 122       { }
 123
 124
 125       template<typename _InputIterator>
 126         __unordered_multiset(_InputIterator __f, _InputIterator __l,
 127                              typename _Base::size_type __n = 0,
 128                              const hasher& __hf = hasher(),
 129                              const key_equal& __eql = key_equal(),
 130                              const allocator_type& __a = allocator_type())
 131         : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
 132                 __detail::_Default_ranged_hash(), __eql,
 133                 std::_Identity<_Value>(), __a)
 134         { }
 135     };
 136
 137   template<class _Value, class _Hash, class _Pred, class _Alloc,
 138            bool __cache_hash_code>
 139     inline void
 140     swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
 141          __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
 142     { __x.swap(__y); }
 143
 144   template<class _Value, class _Hash, class _Pred, class _Alloc,
 145            bool __cache_hash_code>
 146     inline void
 147     swap(__unordered_multiset<_Value, _Hash, _Pred,
 148          _Alloc, __cache_hash_code>& __x,
 149          __unordered_multiset<_Value, _Hash, _Pred,
 150          _Alloc, __cache_hash_code>& __y)
 151     { __x.swap(__y); }
 152
 153
 154   /**
 155    *  @brief A standard container composed of unique keys (containing
 156    *  at most one of each key value) in which the elements' keys are
 157    *  the elements themselves.
 158    *
 159    *  @ingroup unordered_associative_containers
 160    *
 161    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 162    *  <a href="tables.html#xx">unordered associative container</a>
 163    *
 164    *  @param  Value  Type of key objects.
 165    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 166    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 167    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 168    */
 169   template<class _Value,
 170            class _Hash = hash<_Value>,
 171            class _Pred = std::equal_to<_Value>,
 172            class _Alloc = std::allocator<_Value> >
 173     class unordered_set
 174     : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
 175     {
 176       typedef __unordered_set<_Value, _Hash, _Pred, _Alloc>  _Base;
 177
 178     public:
 179       typedef typename _Base::value_type      value_type;
 180       typedef typename _Base::size_type       size_type;
 181       typedef typename _Base::hasher          hasher;
 182       typedef typename _Base::key_equal       key_equal;
 183       typedef typename _Base::allocator_type  allocator_type;
 184
 185       explicit
 186       unordered_set(size_type __n = 10,
 187                     const hasher& __hf = hasher(),
 188                     const key_equal& __eql = key_equal(),
 189                     const allocator_type& __a = allocator_type())
 190       : _Base(__n, __hf, __eql, __a)
 191       { }
 192
 193       template<typename _InputIterator>
 194         unordered_set(_InputIterator __f, _InputIterator __l,
 195                       size_type __n = 10,
 196                       const hasher& __hf = hasher(),
 197                       const key_equal& __eql = key_equal(),
 198                       const allocator_type& __a = allocator_type())
 199         : _Base(__f, __l, __n, __hf, __eql, __a)
 200         { }
 201     };
 202
 203   /**
 204    *  @brief A standard container composed of equivalent keys
 205    *  (possibly containing multiple of each key value) in which the
 206    *  elements' keys are the elements themselves.
 207    *
 208    *  @ingroup unordered_associative_containers
 209    *
 210    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
 211    *  <a href="tables.html#xx">unordered associative container</a>
 212    *
 213    *  @param  Value  Type of key objects.
 214    *  @param  Hash  Hashing function object type, defaults to hash<Value>.
 215    *  @param  Pred  Predicate function object type, defaults to equal_to<Value>.
 216    *  @param  Alloc  Allocator type, defaults to allocator<Key>.
 217    */
 218   template<class _Value,
 219            class _Hash = hash<_Value>,
 220            class _Pred = std::equal_to<_Value>,
 221            class _Alloc = std::allocator<_Value> >
 222     class unordered_multiset
 223     : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 224     {
 225       typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc>  _Base;
 226
 227     public:
 228       typedef typename _Base::value_type      value_type;
 229       typedef typename _Base::size_type       size_type;
 230       typedef typename _Base::hasher          hasher;
 231       typedef typename _Base::key_equal       key_equal;
 232       typedef typename _Base::allocator_type  allocator_type;
 233
 234       explicit
 235       unordered_multiset(size_type __n = 10,
 236                          const hasher& __hf = hasher(),
 237                          const key_equal& __eql = key_equal(),
 238                          const allocator_type& __a = allocator_type())
 239       : _Base(__n, __hf, __eql, __a)
 240       { }
 241
 242
 243       template<typename _InputIterator>
 244         unordered_multiset(_InputIterator __f, _InputIterator __l,
 245                            typename _Base::size_type __n = 0,
 246                            const hasher& __hf = hasher(),
 247                            const key_equal& __eql = key_equal(),
 248                            const allocator_type& __a = allocator_type())
 249         : _Base(__f, __l, __n, __hf, __eql, __a)
 250         { }
 251     };
 252
 253   template<class _Value, class _Hash, class _Pred, class _Alloc>
 254     inline void
 255     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 256          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 257     { __x.swap(__y); }
 258
 259   template<class _Value, class _Hash, class _Pred, class _Alloc>
 260     inline void
 261     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 262          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 263     { __x.swap(__y); }
 264
 265 _GLIBCXX_END_NAMESPACE_VERSION
 266 }
 267 }