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