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