blob: 4fdac160f92860f857c6c4892b0c9ca67322a6e1 [file] [log] [blame]
Howard Hinnant3e519522010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnant5b08a8a2010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnant3e519522010-05-11 19:42:16 +00005//
Howard Hinnant412dbeb2010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnant3e519522010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UNORDERED_MAP
12#define _LIBCPP_UNORDERED_MAP
13
14/*
15
16 unordered_map synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
24 class Alloc = allocator<pair<const Key, T>>>
25class unordered_map
26{
27public:
28 // types
29 typedef Key key_type;
30 typedef T mapped_type;
31 typedef Hash hasher;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef pair<const key_type, mapped_type> value_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
Howard Hinnant37141072011-06-04 18:54:24 +000047 unordered_map()
48 noexcept(
49 is_nothrow_default_constructible<hasher>::value &&
50 is_nothrow_default_constructible<key_equal>::value &&
51 is_nothrow_default_constructible<allocator_type>::value);
52 explicit unordered_map(size_type n, const hasher& hf = hasher(),
Howard Hinnant3e519522010-05-11 19:42:16 +000053 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 template <class InputIterator>
56 unordered_map(InputIterator f, InputIterator l,
57 size_type n = 0, const hasher& hf = hasher(),
58 const key_equal& eql = key_equal(),
59 const allocator_type& a = allocator_type());
60 explicit unordered_map(const allocator_type&);
61 unordered_map(const unordered_map&);
62 unordered_map(const unordered_map&, const Allocator&);
Howard Hinnant37141072011-06-04 18:54:24 +000063 unordered_map(unordered_map&&)
64 noexcept(
65 is_nothrow_move_constructible<hasher>::value &&
66 is_nothrow_move_constructible<key_equal>::value &&
67 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +000068 unordered_map(unordered_map&&, const Allocator&);
69 unordered_map(initializer_list<value_type>, size_type n = 0,
70 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
71 const allocator_type& a = allocator_type());
Marshall Clow3cd37e62013-09-12 03:00:31 +000072 unordered_map(size_type n, const allocator_type& a)
73 : unordered_map(n, hasher(), key_equal(), a) {} // C++14
74 unordered_map(size_type n, const hasher& hf, const allocator_type& a)
75 : unordered_map(n, hf, key_equal(), a) {} // C++14
76 template <class InputIterator>
77 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
78 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14
79 template <class InputIterator>
80 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
81 const allocator_type& a)
82 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14
83 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
84 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14
85 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
86 const allocator_type& a)
87 : unordered_map(il, n, hf, key_equal(), a) {} // C++14
Howard Hinnant3e519522010-05-11 19:42:16 +000088 ~unordered_map();
89 unordered_map& operator=(const unordered_map&);
Howard Hinnant37141072011-06-04 18:54:24 +000090 unordered_map& operator=(unordered_map&&)
91 noexcept(
92 allocator_type::propagate_on_container_move_assignment::value &&
93 is_nothrow_move_assignable<allocator_type>::value &&
94 is_nothrow_move_assignable<hasher>::value &&
95 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +000096 unordered_map& operator=(initializer_list<value_type>);
97
Howard Hinnant37141072011-06-04 18:54:24 +000098 allocator_type get_allocator() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +000099
Howard Hinnant37141072011-06-04 18:54:24 +0000100 bool empty() const noexcept;
101 size_type size() const noexcept;
102 size_type max_size() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000103
Howard Hinnant37141072011-06-04 18:54:24 +0000104 iterator begin() noexcept;
105 iterator end() noexcept;
106 const_iterator begin() const noexcept;
107 const_iterator end() const noexcept;
108 const_iterator cbegin() const noexcept;
109 const_iterator cend() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000110
111 template <class... Args>
112 pair<iterator, bool> emplace(Args&&... args);
113 template <class... Args>
114 iterator emplace_hint(const_iterator position, Args&&... args);
115 pair<iterator, bool> insert(const value_type& obj);
116 template <class P>
117 pair<iterator, bool> insert(P&& obj);
118 iterator insert(const_iterator hint, const value_type& obj);
119 template <class P>
120 iterator insert(const_iterator hint, P&& obj);
121 template <class InputIterator>
122 void insert(InputIterator first, InputIterator last);
123 void insert(initializer_list<value_type>);
124
Marshall Clowbc4c89a2015-07-07 05:45:35 +0000125 template <class... Args>
126 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
127 template <class... Args>
128 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
129 template <class... Args>
130 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
131 template <class... Args>
132 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
133 template <class M>
134 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
135 template <class M>
136 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
137 template <class M>
138 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
139 template <class M>
140 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
141
Howard Hinnant3e519522010-05-11 19:42:16 +0000142 iterator erase(const_iterator position);
Marshall Clowec392962015-05-10 13:35:00 +0000143 iterator erase(iterator position); // C++14
Howard Hinnant3e519522010-05-11 19:42:16 +0000144 size_type erase(const key_type& k);
145 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant37141072011-06-04 18:54:24 +0000146 void clear() noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000147
Howard Hinnant37141072011-06-04 18:54:24 +0000148 void swap(unordered_map&)
149 noexcept(
150 (!allocator_type::propagate_on_container_swap::value ||
151 __is_nothrow_swappable<allocator_type>::value) &&
152 __is_nothrow_swappable<hasher>::value &&
153 __is_nothrow_swappable<key_equal>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +0000154
155 hasher hash_function() const;
156 key_equal key_eq() const;
157
158 iterator find(const key_type& k);
159 const_iterator find(const key_type& k) const;
160 size_type count(const key_type& k) const;
161 pair<iterator, iterator> equal_range(const key_type& k);
162 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
163
164 mapped_type& operator[](const key_type& k);
165 mapped_type& operator[](key_type&& k);
166
167 mapped_type& at(const key_type& k);
168 const mapped_type& at(const key_type& k) const;
169
Howard Hinnant37141072011-06-04 18:54:24 +0000170 size_type bucket_count() const noexcept;
171 size_type max_bucket_count() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000172
173 size_type bucket_size(size_type n) const;
174 size_type bucket(const key_type& k) const;
175
176 local_iterator begin(size_type n);
177 local_iterator end(size_type n);
178 const_local_iterator begin(size_type n) const;
179 const_local_iterator end(size_type n) const;
180 const_local_iterator cbegin(size_type n) const;
181 const_local_iterator cend(size_type n) const;
182
Howard Hinnant37141072011-06-04 18:54:24 +0000183 float load_factor() const noexcept;
184 float max_load_factor() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000185 void max_load_factor(float z);
186 void rehash(size_type n);
187 void reserve(size_type n);
188};
189
190template <class Key, class T, class Hash, class Pred, class Alloc>
191 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant37141072011-06-04 18:54:24 +0000192 unordered_map<Key, T, Hash, Pred, Alloc>& y)
193 noexcept(noexcept(x.swap(y)));
Howard Hinnant3e519522010-05-11 19:42:16 +0000194
195template <class Key, class T, class Hash, class Pred, class Alloc>
196 bool
197 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
198 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
199
200template <class Key, class T, class Hash, class Pred, class Alloc>
201 bool
202 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
203 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
204
205template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
206 class Alloc = allocator<pair<const Key, T>>>
207class unordered_multimap
208{
209public:
210 // types
211 typedef Key key_type;
212 typedef T mapped_type;
213 typedef Hash hasher;
214 typedef Pred key_equal;
215 typedef Alloc allocator_type;
216 typedef pair<const key_type, mapped_type> value_type;
217 typedef value_type& reference;
218 typedef const value_type& const_reference;
219 typedef typename allocator_traits<allocator_type>::pointer pointer;
220 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
221 typedef typename allocator_traits<allocator_type>::size_type size_type;
222 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
223
224 typedef /unspecified/ iterator;
225 typedef /unspecified/ const_iterator;
226 typedef /unspecified/ local_iterator;
227 typedef /unspecified/ const_local_iterator;
228
Howard Hinnant37141072011-06-04 18:54:24 +0000229 unordered_multimap()
230 noexcept(
231 is_nothrow_default_constructible<hasher>::value &&
232 is_nothrow_default_constructible<key_equal>::value &&
233 is_nothrow_default_constructible<allocator_type>::value);
234 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
Howard Hinnant3e519522010-05-11 19:42:16 +0000235 const key_equal& eql = key_equal(),
236 const allocator_type& a = allocator_type());
237 template <class InputIterator>
238 unordered_multimap(InputIterator f, InputIterator l,
239 size_type n = 0, const hasher& hf = hasher(),
240 const key_equal& eql = key_equal(),
241 const allocator_type& a = allocator_type());
242 explicit unordered_multimap(const allocator_type&);
243 unordered_multimap(const unordered_multimap&);
244 unordered_multimap(const unordered_multimap&, const Allocator&);
Howard Hinnant37141072011-06-04 18:54:24 +0000245 unordered_multimap(unordered_multimap&&)
246 noexcept(
247 is_nothrow_move_constructible<hasher>::value &&
248 is_nothrow_move_constructible<key_equal>::value &&
249 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +0000250 unordered_multimap(unordered_multimap&&, const Allocator&);
251 unordered_multimap(initializer_list<value_type>, size_type n = 0,
252 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
253 const allocator_type& a = allocator_type());
Marshall Clow3cd37e62013-09-12 03:00:31 +0000254 unordered_multimap(size_type n, const allocator_type& a)
255 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14
256 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
257 : unordered_multimap(n, hf, key_equal(), a) {} // C++14
258 template <class InputIterator>
259 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
260 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14
261 template <class InputIterator>
262 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
263 const allocator_type& a)
264 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14
265 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
266 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14
267 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
268 const allocator_type& a)
269 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14
Howard Hinnant3e519522010-05-11 19:42:16 +0000270 ~unordered_multimap();
271 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant37141072011-06-04 18:54:24 +0000272 unordered_multimap& operator=(unordered_multimap&&)
273 noexcept(
274 allocator_type::propagate_on_container_move_assignment::value &&
275 is_nothrow_move_assignable<allocator_type>::value &&
276 is_nothrow_move_assignable<hasher>::value &&
277 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +0000278 unordered_multimap& operator=(initializer_list<value_type>);
279
Howard Hinnant37141072011-06-04 18:54:24 +0000280 allocator_type get_allocator() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000281
Howard Hinnant37141072011-06-04 18:54:24 +0000282 bool empty() const noexcept;
283 size_type size() const noexcept;
284 size_type max_size() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000285
Howard Hinnant37141072011-06-04 18:54:24 +0000286 iterator begin() noexcept;
287 iterator end() noexcept;
288 const_iterator begin() const noexcept;
289 const_iterator end() const noexcept;
290 const_iterator cbegin() const noexcept;
291 const_iterator cend() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000292
293 template <class... Args>
294 iterator emplace(Args&&... args);
295 template <class... Args>
296 iterator emplace_hint(const_iterator position, Args&&... args);
297 iterator insert(const value_type& obj);
298 template <class P>
299 iterator insert(P&& obj);
300 iterator insert(const_iterator hint, const value_type& obj);
301 template <class P>
302 iterator insert(const_iterator hint, P&& obj);
303 template <class InputIterator>
304 void insert(InputIterator first, InputIterator last);
305 void insert(initializer_list<value_type>);
306
307 iterator erase(const_iterator position);
Marshall Clowec392962015-05-10 13:35:00 +0000308 iterator erase(iterator position); // C++14
Howard Hinnant3e519522010-05-11 19:42:16 +0000309 size_type erase(const key_type& k);
310 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant37141072011-06-04 18:54:24 +0000311 void clear() noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000312
Howard Hinnant37141072011-06-04 18:54:24 +0000313 void swap(unordered_multimap&)
314 noexcept(
315 (!allocator_type::propagate_on_container_swap::value ||
316 __is_nothrow_swappable<allocator_type>::value) &&
317 __is_nothrow_swappable<hasher>::value &&
318 __is_nothrow_swappable<key_equal>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +0000319
320 hasher hash_function() const;
321 key_equal key_eq() const;
322
323 iterator find(const key_type& k);
324 const_iterator find(const key_type& k) const;
325 size_type count(const key_type& k) const;
326 pair<iterator, iterator> equal_range(const key_type& k);
327 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
328
Howard Hinnant37141072011-06-04 18:54:24 +0000329 size_type bucket_count() const noexcept;
330 size_type max_bucket_count() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000331
332 size_type bucket_size(size_type n) const;
333 size_type bucket(const key_type& k) const;
334
335 local_iterator begin(size_type n);
336 local_iterator end(size_type n);
337 const_local_iterator begin(size_type n) const;
338 const_local_iterator end(size_type n) const;
339 const_local_iterator cbegin(size_type n) const;
340 const_local_iterator cend(size_type n) const;
341
Howard Hinnant37141072011-06-04 18:54:24 +0000342 float load_factor() const noexcept;
343 float max_load_factor() const noexcept;
Howard Hinnant3e519522010-05-11 19:42:16 +0000344 void max_load_factor(float z);
345 void rehash(size_type n);
346 void reserve(size_type n);
347};
348
349template <class Key, class T, class Hash, class Pred, class Alloc>
350 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant37141072011-06-04 18:54:24 +0000351 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
352 noexcept(noexcept(x.swap(y)));
Howard Hinnant3e519522010-05-11 19:42:16 +0000353
354template <class Key, class T, class Hash, class Pred, class Alloc>
355 bool
356 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
357 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
358
359template <class Key, class T, class Hash, class Pred, class Alloc>
360 bool
361 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
362 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
363
364} // std
365
366*/
367
368#include <__config>
369#include <__hash_table>
370#include <functional>
371#include <stdexcept>
Eric Fiselier0f905672016-02-11 21:45:53 +0000372#include <tuple>
Howard Hinnant3e519522010-05-11 19:42:16 +0000373
Eric Fiselierc1bd9192014-08-10 23:53:08 +0000374#include <__debug>
375
Howard Hinnant073458b2011-10-17 20:05:10 +0000376#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnant3e519522010-05-11 19:42:16 +0000377#pragma GCC system_header
Howard Hinnant073458b2011-10-17 20:05:10 +0000378#endif
Howard Hinnant3e519522010-05-11 19:42:16 +0000379
380_LIBCPP_BEGIN_NAMESPACE_STD
381
Eric Fiselier04333f92017-01-13 22:42:53 +0000382template <class _Key, class _Cp, class _Hash, bool _IsEmpty>
Howard Hinnant3e519522010-05-11 19:42:16 +0000383class __unordered_map_hasher
384 : private _Hash
385{
386public:
Howard Hinnant789847d2010-09-23 18:58:28 +0000387 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000388 __unordered_map_hasher()
389 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
390 : _Hash() {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000391 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000392 __unordered_map_hasher(const _Hash& __h)
393 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
394 : _Hash(__h) {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000395 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000396 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000397 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000398 size_t operator()(const _Cp& __x) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000399 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000400 _LIBCPP_INLINE_VISIBILITY
401 size_t operator()(const _Key& __x) const
Howard Hinnant3e519522010-05-11 19:42:16 +0000402 {return static_cast<const _Hash&>(*this)(__x);}
Marshall Clowe3fbe142015-07-13 20:04:56 +0000403 void swap(__unordered_map_hasher&__y)
404 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
405 {
406 using _VSTD::swap;
Eric Fiselierb3f57422017-04-13 01:02:41 +0000407 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
Marshall Clowe3fbe142015-07-13 20:04:56 +0000408 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000409};
410
Howard Hinnantabb160e2013-07-05 18:06:00 +0000411template <class _Key, class _Cp, class _Hash>
412class __unordered_map_hasher<_Key, _Cp, _Hash, false>
Howard Hinnant3e519522010-05-11 19:42:16 +0000413{
414 _Hash __hash_;
415public:
Howard Hinnant789847d2010-09-23 18:58:28 +0000416 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000417 __unordered_map_hasher()
418 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
419 : __hash_() {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000420 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000421 __unordered_map_hasher(const _Hash& __h)
422 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
423 : __hash_(__h) {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000424 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000425 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000427 size_t operator()(const _Cp& __x) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000428 {return __hash_(__x.__cc.first);}
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000429 _LIBCPP_INLINE_VISIBILITY
430 size_t operator()(const _Key& __x) const
Howard Hinnant3e519522010-05-11 19:42:16 +0000431 {return __hash_(__x);}
Marshall Clowe3fbe142015-07-13 20:04:56 +0000432 void swap(__unordered_map_hasher&__y)
433 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
434 {
435 using _VSTD::swap;
436 swap(__hash_, __y.__hash_);
437 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000438};
439
Marshall Clowe3fbe142015-07-13 20:04:56 +0000440template <class _Key, class _Cp, class _Hash, bool __b>
441inline _LIBCPP_INLINE_VISIBILITY
442void
443swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,
444 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)
445 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
446{
447 __x.swap(__y);
448}
449
Eric Fiselier04333f92017-01-13 22:42:53 +0000450template <class _Key, class _Cp, class _Pred, bool _IsEmpty>
Howard Hinnant3e519522010-05-11 19:42:16 +0000451class __unordered_map_equal
452 : private _Pred
453{
454public:
Howard Hinnant789847d2010-09-23 18:58:28 +0000455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000456 __unordered_map_equal()
457 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
458 : _Pred() {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000460 __unordered_map_equal(const _Pred& __p)
461 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
462 : _Pred(__p) {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000464 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000465 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000466 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000467 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000468 _LIBCPP_INLINE_VISIBILITY
469 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000470 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000472 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000473 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
Marshall Clowe3fbe142015-07-13 20:04:56 +0000474 void swap(__unordered_map_equal&__y)
475 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
476 {
477 using _VSTD::swap;
Eric Fiselierb3f57422017-04-13 01:02:41 +0000478 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
Marshall Clowe3fbe142015-07-13 20:04:56 +0000479 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000480};
481
Howard Hinnantabb160e2013-07-05 18:06:00 +0000482template <class _Key, class _Cp, class _Pred>
483class __unordered_map_equal<_Key, _Cp, _Pred, false>
Howard Hinnant3e519522010-05-11 19:42:16 +0000484{
485 _Pred __pred_;
486public:
Howard Hinnant789847d2010-09-23 18:58:28 +0000487 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000488 __unordered_map_equal()
489 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
490 : __pred_() {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000491 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000492 __unordered_map_equal(const _Pred& __p)
493 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
494 : __pred_(__p) {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000495 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000496 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000497 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000498 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000499 {return __pred_(__x.__cc.first, __y.__cc.first);}
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000500 _LIBCPP_INLINE_VISIBILITY
501 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000502 {return __pred_(__x.__cc.first, __y);}
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000503 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta1a9e772011-12-12 17:26:24 +0000504 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnantabb160e2013-07-05 18:06:00 +0000505 {return __pred_(__x, __y.__cc.first);}
Marshall Clowe3fbe142015-07-13 20:04:56 +0000506 void swap(__unordered_map_equal&__y)
507 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
508 {
509 using _VSTD::swap;
510 swap(__pred_, __y.__pred_);
511 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000512};
513
Marshall Clowe3fbe142015-07-13 20:04:56 +0000514template <class _Key, class _Cp, class _Pred, bool __b>
515inline _LIBCPP_INLINE_VISIBILITY
516void
517swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,
518 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)
519 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
520{
521 __x.swap(__y);
522}
523
Howard Hinnant3e519522010-05-11 19:42:16 +0000524template <class _Alloc>
525class __hash_map_node_destructor
526{
527 typedef _Alloc allocator_type;
528 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000529
Howard Hinnant3e519522010-05-11 19:42:16 +0000530public:
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000531
532 typedef typename __alloc_traits::pointer pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000533private:
Howard Hinnant3e519522010-05-11 19:42:16 +0000534
535 allocator_type& __na_;
536
537 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
538
539public:
540 bool __first_constructed;
541 bool __second_constructed;
542
Howard Hinnant789847d2010-09-23 18:58:28 +0000543 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000544 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000545 : __na_(__na),
546 __first_constructed(false),
547 __second_constructed(false)
548 {}
549
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000550#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant789847d2010-09-23 18:58:28 +0000551 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000552 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant37141072011-06-04 18:54:24 +0000553 _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000554 : __na_(__x.__na_),
555 __first_constructed(__x.__value_constructed),
556 __second_constructed(__x.__value_constructed)
557 {
558 __x.__value_constructed = false;
559 }
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000560#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant789847d2010-09-23 18:58:28 +0000561 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000562 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
563 : __na_(__x.__na_),
564 __first_constructed(__x.__value_constructed),
565 __second_constructed(__x.__value_constructed)
566 {
567 const_cast<bool&>(__x.__value_constructed) = false;
568 }
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000569#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +0000570
Howard Hinnant789847d2010-09-23 18:58:28 +0000571 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000572 void operator()(pointer __p) _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000573 {
574 if (__second_constructed)
Howard Hinnant307f8142013-06-22 15:21:29 +0000575 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnant3e519522010-05-11 19:42:16 +0000576 if (__first_constructed)
Howard Hinnant307f8142013-06-22 15:21:29 +0000577 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnant3e519522010-05-11 19:42:16 +0000578 if (__p)
579 __alloc_traits::deallocate(__na_, __p, 1);
580 }
581};
582
Eric Fiselierfcd02212016-02-11 11:59:44 +0000583#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000584template <class _Key, class _Tp>
585union __hash_value_type
586{
587 typedef _Key key_type;
588 typedef _Tp mapped_type;
589 typedef pair<const key_type, mapped_type> value_type;
590 typedef pair<key_type, mapped_type> __nc_value_type;
591
592 value_type __cc;
593 __nc_value_type __nc;
594
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000595 _LIBCPP_INLINE_VISIBILITY
596 __hash_value_type& operator=(const __hash_value_type& __v)
597 {__nc = __v.__cc; return *this;}
598
599 _LIBCPP_INLINE_VISIBILITY
600 __hash_value_type& operator=(__hash_value_type&& __v)
Marshall Clow27647992015-05-06 12:11:22 +0000601 {__nc = _VSTD::move(__v.__nc); return *this;}
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000602
Eric Fiselierfcd02212016-02-11 11:59:44 +0000603 template <class _ValueTp,
604 class = typename enable_if<
605 __is_same_uncvref<_ValueTp, value_type>::value
606 >::type
607 >
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000608 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfcd02212016-02-11 11:59:44 +0000609 __hash_value_type& operator=(_ValueTp&& __v) {
610 __nc = _VSTD::forward<_ValueTp>(__v); return *this;
611 }
612
613private:
614 __hash_value_type(const __hash_value_type& __v) = delete;
615 __hash_value_type(__hash_value_type&& __v) = delete;
616 template <class ..._Args>
617 explicit __hash_value_type(_Args&& ...__args) = delete;
618
619 ~__hash_value_type() = delete;
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000620};
621
622#else
623
624template <class _Key, class _Tp>
625struct __hash_value_type
626{
627 typedef _Key key_type;
628 typedef _Tp mapped_type;
629 typedef pair<const key_type, mapped_type> value_type;
630
631 value_type __cc;
632
Eric Fiselierfcd02212016-02-11 11:59:44 +0000633private:
634 ~__hash_value_type();
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000635};
636
637#endif
638
Howard Hinnant3e519522010-05-11 19:42:16 +0000639template <class _HashIterator>
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000640class _LIBCPP_TEMPLATE_VIS __hash_map_iterator
Howard Hinnant3e519522010-05-11 19:42:16 +0000641{
642 _HashIterator __i_;
643
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000644 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
645
Howard Hinnant3e519522010-05-11 19:42:16 +0000646public:
647 typedef forward_iterator_tag iterator_category;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000648 typedef typename _NodeTypes::__map_value_type value_type;
649 typedef typename _NodeTypes::difference_type difference_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000650 typedef value_type& reference;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000651 typedef typename _NodeTypes::__map_value_type_pointer pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000652
Howard Hinnant789847d2010-09-23 18:58:28 +0000653 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000654 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnant3e519522010-05-11 19:42:16 +0000655
Howard Hinnant789847d2010-09-23 18:58:28 +0000656 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000657 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant3e519522010-05-11 19:42:16 +0000658
Howard Hinnant789847d2010-09-23 18:58:28 +0000659 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant307f8142013-06-22 15:21:29 +0000660 reference operator*() const {return __i_->__cc;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000661 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant307f8142013-06-22 15:21:29 +0000662 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnant3e519522010-05-11 19:42:16 +0000663
Howard Hinnant789847d2010-09-23 18:58:28 +0000664 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000665 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000666 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000667 __hash_map_iterator operator++(int)
668 {
669 __hash_map_iterator __t(*this);
670 ++(*this);
671 return __t;
672 }
673
Howard Hinnant789847d2010-09-23 18:58:28 +0000674 friend _LIBCPP_INLINE_VISIBILITY
675 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnant3e519522010-05-11 19:42:16 +0000676 {return __x.__i_ == __y.__i_;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000677 friend _LIBCPP_INLINE_VISIBILITY
678 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnant3e519522010-05-11 19:42:16 +0000679 {return __x.__i_ != __y.__i_;}
680
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000681 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
682 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
683 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
684 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
685 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000686};
687
688template <class _HashIterator>
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000689class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator
Howard Hinnant3e519522010-05-11 19:42:16 +0000690{
691 _HashIterator __i_;
692
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000693 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
694
Howard Hinnant3e519522010-05-11 19:42:16 +0000695public:
696 typedef forward_iterator_tag iterator_category;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000697 typedef typename _NodeTypes::__map_value_type value_type;
698 typedef typename _NodeTypes::difference_type difference_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000699 typedef const value_type& reference;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000700 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
Howard Hinnant3e519522010-05-11 19:42:16 +0000701
Howard Hinnant789847d2010-09-23 18:58:28 +0000702 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000703 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnant3e519522010-05-11 19:42:16 +0000704
Howard Hinnant789847d2010-09-23 18:58:28 +0000705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000706 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant789847d2010-09-23 18:58:28 +0000707 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000708 __hash_map_const_iterator(
709 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant37141072011-06-04 18:54:24 +0000710 _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000711 : __i_(__i.__i_) {}
712
Howard Hinnant789847d2010-09-23 18:58:28 +0000713 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant307f8142013-06-22 15:21:29 +0000714 reference operator*() const {return __i_->__cc;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000715 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant307f8142013-06-22 15:21:29 +0000716 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnant3e519522010-05-11 19:42:16 +0000717
Howard Hinnant789847d2010-09-23 18:58:28 +0000718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000719 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000721 __hash_map_const_iterator operator++(int)
722 {
723 __hash_map_const_iterator __t(*this);
724 ++(*this);
725 return __t;
726 }
727
Howard Hinnant789847d2010-09-23 18:58:28 +0000728 friend _LIBCPP_INLINE_VISIBILITY
729 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnant3e519522010-05-11 19:42:16 +0000730 {return __x.__i_ == __y.__i_;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000731 friend _LIBCPP_INLINE_VISIBILITY
732 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnant3e519522010-05-11 19:42:16 +0000733 {return __x.__i_ != __y.__i_;}
734
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000735 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
736 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
737 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
738 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
Howard Hinnant3e519522010-05-11 19:42:16 +0000739};
740
741template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
742 class _Alloc = allocator<pair<const _Key, _Tp> > >
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +0000743class _LIBCPP_TEMPLATE_VIS unordered_map
Howard Hinnant3e519522010-05-11 19:42:16 +0000744{
745public:
746 // types
747 typedef _Key key_type;
748 typedef _Tp mapped_type;
749 typedef _Hash hasher;
750 typedef _Pred key_equal;
751 typedef _Alloc allocator_type;
752 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant307f8142013-06-22 15:21:29 +0000753 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000754 typedef value_type& reference;
755 typedef const value_type& const_reference;
Howard Hinnantb24c8022013-07-23 22:01:58 +0000756 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
757 "Invalid allocator::value_type");
Howard Hinnant3e519522010-05-11 19:42:16 +0000758
759private:
Howard Hinnant9fd9f842013-09-30 19:08:22 +0000760 typedef __hash_value_type<key_type, mapped_type> __value_type;
Howard Hinnantabb160e2013-07-05 18:06:00 +0000761 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
762 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Marshall Clow1f508012015-04-07 05:21:38 +0000763 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
764 __value_type>::type __allocator_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000765
766 typedef __hash_table<__value_type, __hasher,
767 __key_equal, __allocator_type> __table;
768
769 __table __table_;
770
Eric Fiselierfcd02212016-02-11 11:59:44 +0000771 typedef typename __table::_NodeTypes _NodeTypes;
Howard Hinnant3e519522010-05-11 19:42:16 +0000772 typedef typename __table::__node_pointer __node_pointer;
773 typedef typename __table::__node_const_pointer __node_const_pointer;
774 typedef typename __table::__node_traits __node_traits;
775 typedef typename __table::__node_allocator __node_allocator;
776 typedef typename __table::__node __node;
Howard Hinnantc003db12011-11-29 18:15:50 +0000777 typedef __hash_map_node_destructor<__node_allocator> _Dp;
778 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnant3e519522010-05-11 19:42:16 +0000779 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiselierfcd02212016-02-11 11:59:44 +0000780
781 static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
782 static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
Howard Hinnant3e519522010-05-11 19:42:16 +0000783public:
784 typedef typename __alloc_traits::pointer pointer;
785 typedef typename __alloc_traits::const_pointer const_pointer;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +0000786 typedef typename __table::size_type size_type;
787 typedef typename __table::difference_type difference_type;
Howard Hinnant3e519522010-05-11 19:42:16 +0000788
789 typedef __hash_map_iterator<typename __table::iterator> iterator;
790 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
791 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
792 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
793
Howard Hinnant789847d2010-09-23 18:58:28 +0000794 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000795 unordered_map()
796 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnantb24c8022013-07-23 22:01:58 +0000797 {
798#if _LIBCPP_DEBUG_LEVEL >= 2
799 __get_db()->__insert_c(this);
800#endif
801 }
Howard Hinnant3e519522010-05-11 19:42:16 +0000802 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
803 const key_equal& __eql = key_equal());
804 unordered_map(size_type __n, const hasher& __hf,
805 const key_equal& __eql,
806 const allocator_type& __a);
807 template <class _InputIterator>
808 unordered_map(_InputIterator __first, _InputIterator __last);
809 template <class _InputIterator>
810 unordered_map(_InputIterator __first, _InputIterator __last,
811 size_type __n, const hasher& __hf = hasher(),
812 const key_equal& __eql = key_equal());
813 template <class _InputIterator>
814 unordered_map(_InputIterator __first, _InputIterator __last,
815 size_type __n, const hasher& __hf,
816 const key_equal& __eql,
817 const allocator_type& __a);
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000819 explicit unordered_map(const allocator_type& __a);
820 unordered_map(const unordered_map& __u);
821 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000822#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +0000823 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000824 unordered_map(unordered_map&& __u)
825 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +0000826 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000827#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant54976f22011-08-12 21:56:02 +0000828#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant3e519522010-05-11 19:42:16 +0000829 unordered_map(initializer_list<value_type> __il);
830 unordered_map(initializer_list<value_type> __il, size_type __n,
831 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
832 unordered_map(initializer_list<value_type> __il, size_type __n,
833 const hasher& __hf, const key_equal& __eql,
834 const allocator_type& __a);
Howard Hinnant54976f22011-08-12 21:56:02 +0000835#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Marshall Clow3cd37e62013-09-12 03:00:31 +0000836#if _LIBCPP_STD_VER > 11
837 _LIBCPP_INLINE_VISIBILITY
838 unordered_map(size_type __n, const allocator_type& __a)
839 : unordered_map(__n, hasher(), key_equal(), __a) {}
840 _LIBCPP_INLINE_VISIBILITY
841 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
842 : unordered_map(__n, __hf, key_equal(), __a) {}
843 template <class _InputIterator>
844 _LIBCPP_INLINE_VISIBILITY
845 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
846 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
847 template <class _InputIterator>
848 _LIBCPP_INLINE_VISIBILITY
849 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
850 const allocator_type& __a)
851 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
852 _LIBCPP_INLINE_VISIBILITY
853 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
854 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
855 _LIBCPP_INLINE_VISIBILITY
856 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
857 const allocator_type& __a)
858 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
859#endif
Howard Hinnant3e519522010-05-11 19:42:16 +0000860 // ~unordered_map() = default;
Howard Hinnant5a336872011-07-01 19:24:36 +0000861 _LIBCPP_INLINE_VISIBILITY
862 unordered_map& operator=(const unordered_map& __u)
863 {
Marshall Clow2ee83722016-07-18 13:19:00 +0000864#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant5a336872011-07-01 19:24:36 +0000865 __table_ = __u.__table_;
Howard Hinnant307f8142013-06-22 15:21:29 +0000866#else
Marshall Clow74cf6ff2014-02-08 04:03:14 +0000867 if (this != &__u) {
868 __table_.clear();
869 __table_.hash_function() = __u.__table_.hash_function();
870 __table_.key_eq() = __u.__table_.key_eq();
871 __table_.max_load_factor() = __u.__table_.max_load_factor();
872 __table_.__copy_assign_alloc(__u.__table_);
873 insert(__u.begin(), __u.end());
874 }
Howard Hinnant307f8142013-06-22 15:21:29 +0000875#endif
Howard Hinnant5a336872011-07-01 19:24:36 +0000876 return *this;
877 }
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000878#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +0000879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000880 unordered_map& operator=(unordered_map&& __u)
881 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +0000882#endif
Howard Hinnant54976f22011-08-12 21:56:02 +0000883#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +0000885 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnant54976f22011-08-12 21:56:02 +0000886#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant3e519522010-05-11 19:42:16 +0000887
Howard Hinnant789847d2010-09-23 18:58:28 +0000888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000889 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +0000890 {return allocator_type(__table_.__node_alloc());}
891
Howard Hinnant789847d2010-09-23 18:58:28 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000893 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnant789847d2010-09-23 18:58:28 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000895 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnant789847d2010-09-23 18:58:28 +0000896 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000897 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000898
Howard Hinnant789847d2010-09-23 18:58:28 +0000899 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000900 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnant789847d2010-09-23 18:58:28 +0000901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000902 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnant789847d2010-09-23 18:58:28 +0000903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000904 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnant789847d2010-09-23 18:58:28 +0000905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000906 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnant789847d2010-09-23 18:58:28 +0000907 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000908 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnant789847d2010-09-23 18:58:28 +0000909 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +0000910 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnant3e519522010-05-11 19:42:16 +0000911
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000912 _LIBCPP_INLINE_VISIBILITY
913 pair<iterator, bool> insert(const value_type& __x)
914 {return __table_.__insert_unique(__x);}
915
916 iterator insert(const_iterator __p, const value_type& __x) {
917#if _LIBCPP_DEBUG_LEVEL >= 2
918 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
919 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
920 " referring to this unordered_map");
Eric Fiselierfd838222016-12-23 23:37:52 +0000921#else
922 ((void)__p);
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000923#endif
924 return insert(__x).first;
925 }
926
927 template <class _InputIterator>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +0000928 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000929 void insert(_InputIterator __first, _InputIterator __last);
930
931#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
932 _LIBCPP_INLINE_VISIBILITY
933 void insert(initializer_list<value_type> __il)
934 {insert(__il.begin(), __il.end());}
935#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
936
Eric Fiselierfcd02212016-02-11 11:59:44 +0000937#ifndef _LIBCPP_CXX03_LANG
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000938 _LIBCPP_INLINE_VISIBILITY
939 pair<iterator, bool> insert(value_type&& __x)
940 {return __table_.__insert_unique(_VSTD::move(__x));}
941
942 iterator insert(const_iterator __p, value_type&& __x) {
943#if _LIBCPP_DEBUG_LEVEL >= 2
944 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
945 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
946 " referring to this unordered_map");
Eric Fiselierfd838222016-12-23 23:37:52 +0000947#else
948 ((void)__p);
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000949#endif
950 return __table_.__insert_unique(_VSTD::move(__x)).first;
951 }
952
953 template <class _Pp,
954 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
955 _LIBCPP_INLINE_VISIBILITY
956 pair<iterator, bool> insert(_Pp&& __x)
957 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
958
959 template <class _Pp,
960 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
961 _LIBCPP_INLINE_VISIBILITY
962 iterator insert(const_iterator __p, _Pp&& __x)
963 {
964#if _LIBCPP_DEBUG_LEVEL >= 2
965 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
966 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
967 " referring to this unordered_map");
Eric Fiselierfd838222016-12-23 23:37:52 +0000968#else
969 ((void)__p);
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000970#endif
971 return insert(_VSTD::forward<_Pp>(__x)).first;
972 }
973
Eric Fiselierfcd02212016-02-11 11:59:44 +0000974 template <class... _Args>
975 _LIBCPP_INLINE_VISIBILITY
976 pair<iterator, bool> emplace(_Args&&... __args) {
977 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
978 }
Howard Hinnant7609c9b2010-09-04 23:28:19 +0000979
Howard Hinnant8b805c92012-05-25 22:04:21 +0000980 template <class... _Args>
Eric Fiselierfcd02212016-02-11 11:59:44 +0000981 _LIBCPP_INLINE_VISIBILITY
982 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
Howard Hinnant4c80bfb2013-07-30 21:04:42 +0000983#if _LIBCPP_DEBUG_LEVEL >= 2
Eric Fiselierfcd02212016-02-11 11:59:44 +0000984 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
985 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
986 " referring to this unordered_map");
Eric Fiselierfd838222016-12-23 23:37:52 +0000987#else
988 ((void)__p);
Howard Hinnant4c80bfb2013-07-30 21:04:42 +0000989#endif
Eric Fiselierfcd02212016-02-11 11:59:44 +0000990 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
991 }
992
Eric Fiselier7a9f5002016-04-18 01:40:45 +0000993#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +0000994
Marshall Clowbc4c89a2015-07-07 05:45:35 +0000995#if _LIBCPP_STD_VER > 14
Marshall Clowbc4c89a2015-07-07 05:45:35 +0000996 template <class... _Args>
997 _LIBCPP_INLINE_VISIBILITY
998 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
999 {
Eric Fiselier87c41042016-04-18 06:51:33 +00001000 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1001 _VSTD::forward_as_tuple(__k),
1002 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001003 }
1004
1005 template <class... _Args>
1006 _LIBCPP_INLINE_VISIBILITY
1007 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1008 {
Eric Fiselier87c41042016-04-18 06:51:33 +00001009 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct,
1010 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1011 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001012 }
1013
1014 template <class... _Args>
1015 _LIBCPP_INLINE_VISIBILITY
1016 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1017 {
Eric Fiselier87c41042016-04-18 06:51:33 +00001018#if _LIBCPP_DEBUG_LEVEL >= 2
Oleg Ranevskyyeef9b352016-09-26 21:39:38 +00001019 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
Eric Fiselier87c41042016-04-18 06:51:33 +00001020 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1021 " referring to this unordered_map");
Eric Fiselierfd838222016-12-23 23:37:52 +00001022#else
1023 ((void)__h);
Eric Fiselier87c41042016-04-18 06:51:33 +00001024#endif
Eric Fiselierfd838222016-12-23 23:37:52 +00001025 return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first;
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001026 }
1027
1028 template <class... _Args>
1029 _LIBCPP_INLINE_VISIBILITY
1030 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1031 {
Eric Fiselier87c41042016-04-18 06:51:33 +00001032#if _LIBCPP_DEBUG_LEVEL >= 2
Oleg Ranevskyyeef9b352016-09-26 21:39:38 +00001033 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__h) == this,
Eric Fiselier87c41042016-04-18 06:51:33 +00001034 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not"
1035 " referring to this unordered_map");
Eric Fiselierfd838222016-12-23 23:37:52 +00001036#else
1037 ((void)__h);
Eric Fiselier87c41042016-04-18 06:51:33 +00001038#endif
1039 return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first;
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001040 }
1041
1042 template <class _Vp>
1043 _LIBCPP_INLINE_VISIBILITY
1044 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1045 {
Eric Fiselier87c41042016-04-18 06:51:33 +00001046 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1047 __k, _VSTD::forward<_Vp>(__v));
1048 if (!__res.second) {
1049 __res.first->second = _VSTD::forward<_Vp>(__v);
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001050 }
Eric Fiselier87c41042016-04-18 06:51:33 +00001051 return __res;
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001052 }
Eric Fiselier87c41042016-04-18 06:51:33 +00001053
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001054 template <class _Vp>
1055 _LIBCPP_INLINE_VISIBILITY
1056 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1057 {
Eric Fiselier87c41042016-04-18 06:51:33 +00001058 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k,
1059 _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1060 if (!__res.second) {
1061 __res.first->second = _VSTD::forward<_Vp>(__v);
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001062 }
Eric Fiselier87c41042016-04-18 06:51:33 +00001063 return __res;
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001064 }
1065
1066 template <class _Vp>
1067 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfd838222016-12-23 23:37:52 +00001068 iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v)
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001069 {
Eric Fiselierfd838222016-12-23 23:37:52 +00001070 // FIXME: Add debug mode checking for the iterator input
Eric Fiselier87c41042016-04-18 06:51:33 +00001071 return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first;
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001072 }
1073
1074 template <class _Vp>
1075 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierfd838222016-12-23 23:37:52 +00001076 iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v)
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001077 {
Eric Fiselierfd838222016-12-23 23:37:52 +00001078 // FIXME: Add debug mode checking for the iterator input
Eric Fiselier87c41042016-04-18 06:51:33 +00001079 return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first;
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001080 }
1081#endif
Marshall Clowbc4c89a2015-07-07 05:45:35 +00001082
Howard Hinnant789847d2010-09-23 18:58:28 +00001083 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001084 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001085 _LIBCPP_INLINE_VISIBILITY
Marshall Clowec392962015-05-10 13:35:00 +00001086 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1087 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001088 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001089 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001090 iterator erase(const_iterator __first, const_iterator __last)
1091 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001092 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001093 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnant3e519522010-05-11 19:42:16 +00001094
Howard Hinnant789847d2010-09-23 18:58:28 +00001095 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001096 void swap(unordered_map& __u)
1097 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
Eric Fiselier780b51d2016-12-28 05:53:01 +00001098 { __table_.swap(__u.__table_);}
Howard Hinnant3e519522010-05-11 19:42:16 +00001099
Howard Hinnant789847d2010-09-23 18:58:28 +00001100 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001101 hasher hash_function() const
1102 {return __table_.hash_function().hash_function();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001103 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001104 key_equal key_eq() const
1105 {return __table_.key_eq().key_eq();}
1106
Howard Hinnant789847d2010-09-23 18:58:28 +00001107 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001108 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001109 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001110 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001111 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001112 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001113 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001114 pair<iterator, iterator> equal_range(const key_type& __k)
1115 {return __table_.__equal_range_unique(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001116 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001117 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1118 {return __table_.__equal_range_unique(__k);}
1119
1120 mapped_type& operator[](const key_type& __k);
Eric Fiselier0f905672016-02-11 21:45:53 +00001121#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001122 mapped_type& operator[](key_type&& __k);
1123#endif
1124
1125 mapped_type& at(const key_type& __k);
1126 const mapped_type& at(const key_type& __k) const;
1127
Howard Hinnant789847d2010-09-23 18:58:28 +00001128 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001129 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001130 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001131 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnant3e519522010-05-11 19:42:16 +00001132
Howard Hinnant789847d2010-09-23 18:58:28 +00001133 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001134 size_type bucket_size(size_type __n) const
1135 {return __table_.bucket_size(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001136 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001137 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1138
Howard Hinnant789847d2010-09-23 18:58:28 +00001139 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001140 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001141 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001142 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001143 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001144 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001145 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001146 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001147 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001148 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001149 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001150 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1151
Howard Hinnant789847d2010-09-23 18:58:28 +00001152 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001153 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001154 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001155 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001156 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001157 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001158 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001159 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001160 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001161 void reserve(size_type __n) {__table_.reserve(__n);}
1162
Howard Hinnantb24c8022013-07-23 22:01:58 +00001163#if _LIBCPP_DEBUG_LEVEL >= 2
1164
1165 bool __dereferenceable(const const_iterator* __i) const
1166 {return __table_.__dereferenceable(&__i->__i_);}
1167 bool __decrementable(const const_iterator* __i) const
1168 {return __table_.__decrementable(&__i->__i_);}
1169 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1170 {return __table_.__addable(&__i->__i_, __n);}
1171 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1172 {return __table_.__addable(&__i->__i_, __n);}
1173
1174#endif // _LIBCPP_DEBUG_LEVEL >= 2
1175
Howard Hinnant3e519522010-05-11 19:42:16 +00001176private:
Eric Fiselier0f905672016-02-11 21:45:53 +00001177
1178#ifdef _LIBCPP_CXX03_LANG
Howard Hinnant4a95f9e2013-07-04 20:59:16 +00001179 __node_holder __construct_node_with_key(const key_type& __k);
Eric Fiselier0f905672016-02-11 21:45:53 +00001180#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001181};
1182
1183template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1184unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1185 size_type __n, const hasher& __hf, const key_equal& __eql)
1186 : __table_(__hf, __eql)
1187{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001188#if _LIBCPP_DEBUG_LEVEL >= 2
1189 __get_db()->__insert_c(this);
1190#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001191 __table_.rehash(__n);
1192}
1193
1194template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1195unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1196 size_type __n, const hasher& __hf, const key_equal& __eql,
1197 const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001198 : __table_(__hf, __eql, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001199{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001200#if _LIBCPP_DEBUG_LEVEL >= 2
1201 __get_db()->__insert_c(this);
1202#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001203 __table_.rehash(__n);
1204}
1205
1206template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001207inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001208unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1209 const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001210 : __table_(typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001211{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001212#if _LIBCPP_DEBUG_LEVEL >= 2
1213 __get_db()->__insert_c(this);
1214#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001215}
1216
1217template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1218template <class _InputIterator>
1219unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1220 _InputIterator __first, _InputIterator __last)
1221{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001222#if _LIBCPP_DEBUG_LEVEL >= 2
1223 __get_db()->__insert_c(this);
1224#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001225 insert(__first, __last);
1226}
1227
1228template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1229template <class _InputIterator>
1230unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1231 _InputIterator __first, _InputIterator __last, size_type __n,
1232 const hasher& __hf, const key_equal& __eql)
1233 : __table_(__hf, __eql)
1234{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001235#if _LIBCPP_DEBUG_LEVEL >= 2
1236 __get_db()->__insert_c(this);
1237#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001238 __table_.rehash(__n);
1239 insert(__first, __last);
1240}
1241
1242template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1243template <class _InputIterator>
1244unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1245 _InputIterator __first, _InputIterator __last, size_type __n,
1246 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001247 : __table_(__hf, __eql, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001248{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001249#if _LIBCPP_DEBUG_LEVEL >= 2
1250 __get_db()->__insert_c(this);
1251#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001252 __table_.rehash(__n);
1253 insert(__first, __last);
1254}
1255
1256template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1257unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1258 const unordered_map& __u)
1259 : __table_(__u.__table_)
1260{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001261#if _LIBCPP_DEBUG_LEVEL >= 2
1262 __get_db()->__insert_c(this);
1263#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001264 __table_.rehash(__u.bucket_count());
1265 insert(__u.begin(), __u.end());
1266}
1267
1268template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1269unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1270 const unordered_map& __u, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001271 : __table_(__u.__table_, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001272{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001273#if _LIBCPP_DEBUG_LEVEL >= 2
1274 __get_db()->__insert_c(this);
1275#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001276 __table_.rehash(__u.bucket_count());
1277 insert(__u.begin(), __u.end());
1278}
1279
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001280#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001281
1282template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001283inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001284unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1285 unordered_map&& __u)
Howard Hinnant37141072011-06-04 18:54:24 +00001286 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnantce48a112011-06-30 21:18:19 +00001287 : __table_(_VSTD::move(__u.__table_))
Howard Hinnant3e519522010-05-11 19:42:16 +00001288{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001289#if _LIBCPP_DEBUG_LEVEL >= 2
1290 __get_db()->__insert_c(this);
Howard Hinnant4c80bfb2013-07-30 21:04:42 +00001291 __get_db()->swap(this, &__u);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001292#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001293}
1294
1295template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1296unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1297 unordered_map&& __u, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001298 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001299{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001300#if _LIBCPP_DEBUG_LEVEL >= 2
1301 __get_db()->__insert_c(this);
1302#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001303 if (__a != __u.get_allocator())
1304 {
1305 iterator __i = __u.begin();
Eric Fiselierfcd02212016-02-11 11:59:44 +00001306 while (__u.size() != 0) {
1307 __table_.__emplace_unique(_VSTD::move(
1308 __u.__table_.remove((__i++).__i_)->__value_.__nc));
1309 }
Howard Hinnant3e519522010-05-11 19:42:16 +00001310 }
Howard Hinnant4c80bfb2013-07-30 21:04:42 +00001311#if _LIBCPP_DEBUG_LEVEL >= 2
1312 else
1313 __get_db()->swap(this, &__u);
1314#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001315}
1316
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001317#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001318
Howard Hinnant54976f22011-08-12 21:56:02 +00001319#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1320
Howard Hinnant3e519522010-05-11 19:42:16 +00001321template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1322unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1323 initializer_list<value_type> __il)
1324{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001325#if _LIBCPP_DEBUG_LEVEL >= 2
1326 __get_db()->__insert_c(this);
1327#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001328 insert(__il.begin(), __il.end());
1329}
1330
1331template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1332unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1333 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1334 const key_equal& __eql)
1335 : __table_(__hf, __eql)
1336{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001337#if _LIBCPP_DEBUG_LEVEL >= 2
1338 __get_db()->__insert_c(this);
1339#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001340 __table_.rehash(__n);
1341 insert(__il.begin(), __il.end());
1342}
1343
1344template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1345unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1346 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1347 const key_equal& __eql, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001348 : __table_(__hf, __eql, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001349{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001350#if _LIBCPP_DEBUG_LEVEL >= 2
1351 __get_db()->__insert_c(this);
1352#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001353 __table_.rehash(__n);
1354 insert(__il.begin(), __il.end());
1355}
1356
Howard Hinnant54976f22011-08-12 21:56:02 +00001357#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1358
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001359#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001360
1361template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001362inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001363unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1364unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant37141072011-06-04 18:54:24 +00001365 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +00001366{
Howard Hinnantce48a112011-06-30 21:18:19 +00001367 __table_ = _VSTD::move(__u.__table_);
Howard Hinnant3e519522010-05-11 19:42:16 +00001368 return *this;
1369}
1370
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001371#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001372
Howard Hinnant54976f22011-08-12 21:56:02 +00001373#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1374
Howard Hinnant3e519522010-05-11 19:42:16 +00001375template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001376inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001377unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1378unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1379 initializer_list<value_type> __il)
1380{
1381 __table_.__assign_unique(__il.begin(), __il.end());
1382 return *this;
1383}
1384
Howard Hinnant54976f22011-08-12 21:56:02 +00001385#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1386
Eric Fiselier0f905672016-02-11 21:45:53 +00001387#ifdef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001388template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1389typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant4a95f9e2013-07-04 20:59:16 +00001390unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
Howard Hinnant3e519522010-05-11 19:42:16 +00001391{
1392 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnantc003db12011-11-29 18:15:50 +00001393 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant307f8142013-06-22 15:21:29 +00001394 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnant3e519522010-05-11 19:42:16 +00001395 __h.get_deleter().__first_constructed = true;
Howard Hinnant307f8142013-06-22 15:21:29 +00001396 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant3e519522010-05-11 19:42:16 +00001397 __h.get_deleter().__second_constructed = true;
Dimitry Andric251c6292015-08-19 06:43:33 +00001398 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
Howard Hinnant3e519522010-05-11 19:42:16 +00001399}
Eric Fiselier0f905672016-02-11 21:45:53 +00001400#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001401
Howard Hinnant3e519522010-05-11 19:42:16 +00001402template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1403template <class _InputIterator>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001404inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001405void
1406unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1407 _InputIterator __last)
1408{
1409 for (; __first != __last; ++__first)
1410 __table_.__insert_unique(*__first);
1411}
1412
Eric Fiselier0f905672016-02-11 21:45:53 +00001413#ifdef _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001414template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1415_Tp&
1416unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1417{
1418 iterator __i = find(__k);
1419 if (__i != end())
1420 return __i->second;
Howard Hinnant4a95f9e2013-07-04 20:59:16 +00001421 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant3e519522010-05-11 19:42:16 +00001422 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1423 __h.release();
1424 return __r.first->second;
1425}
Eric Fiselier0f905672016-02-11 21:45:53 +00001426#else
Howard Hinnant3e519522010-05-11 19:42:16 +00001427
Eric Fiselier0f905672016-02-11 21:45:53 +00001428template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1429_Tp&
1430unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1431{
1432 return __table_.__emplace_unique_key_args(__k,
1433 std::piecewise_construct, std::forward_as_tuple(__k),
1434 std::forward_as_tuple()).first->__cc.second;
1435}
Howard Hinnant3e519522010-05-11 19:42:16 +00001436
1437template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1438_Tp&
1439unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1440{
Eric Fiselier0f905672016-02-11 21:45:53 +00001441 return __table_.__emplace_unique_key_args(__k,
1442 std::piecewise_construct, std::forward_as_tuple(std::move(__k)),
1443 std::forward_as_tuple()).first->__cc.second;
Howard Hinnant3e519522010-05-11 19:42:16 +00001444}
1445
Eric Fiselier0f905672016-02-11 21:45:53 +00001446#endif // !_LIBCPP_CXX03_MODE
Howard Hinnant3e519522010-05-11 19:42:16 +00001447
1448template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1449_Tp&
1450unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1451{
1452 iterator __i = find(__k);
1453#ifndef _LIBCPP_NO_EXCEPTIONS
1454 if (__i == end())
1455 throw out_of_range("unordered_map::at: key not found");
Howard Hinnantb3371f62010-08-22 00:02:43 +00001456#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant3e519522010-05-11 19:42:16 +00001457 return __i->second;
1458}
1459
1460template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1461const _Tp&
1462unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1463{
1464 const_iterator __i = find(__k);
1465#ifndef _LIBCPP_NO_EXCEPTIONS
1466 if (__i == end())
1467 throw out_of_range("unordered_map::at: key not found");
Howard Hinnantb3371f62010-08-22 00:02:43 +00001468#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant3e519522010-05-11 19:42:16 +00001469 return __i->second;
1470}
1471
1472template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant789847d2010-09-23 18:58:28 +00001473inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001474void
1475swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1476 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant37141072011-06-04 18:54:24 +00001477 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnant3e519522010-05-11 19:42:16 +00001478{
1479 __x.swap(__y);
1480}
1481
1482template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1483bool
1484operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1485 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1486{
1487 if (__x.size() != __y.size())
1488 return false;
1489 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1490 const_iterator;
1491 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1492 __i != __ex; ++__i)
1493 {
1494 const_iterator __j = __y.find(__i->first);
1495 if (__j == __ey || !(*__i == *__j))
1496 return false;
1497 }
1498 return true;
1499}
1500
1501template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant789847d2010-09-23 18:58:28 +00001502inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001503bool
1504operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1505 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1506{
1507 return !(__x == __y);
1508}
1509
1510template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1511 class _Alloc = allocator<pair<const _Key, _Tp> > >
Eric Fiseliere2f2d1e2017-01-04 23:56:00 +00001512class _LIBCPP_TEMPLATE_VIS unordered_multimap
Howard Hinnant3e519522010-05-11 19:42:16 +00001513{
1514public:
1515 // types
1516 typedef _Key key_type;
1517 typedef _Tp mapped_type;
1518 typedef _Hash hasher;
1519 typedef _Pred key_equal;
1520 typedef _Alloc allocator_type;
1521 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant307f8142013-06-22 15:21:29 +00001522 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnant3e519522010-05-11 19:42:16 +00001523 typedef value_type& reference;
1524 typedef const value_type& const_reference;
Howard Hinnantb24c8022013-07-23 22:01:58 +00001525 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1526 "Invalid allocator::value_type");
Howard Hinnant3e519522010-05-11 19:42:16 +00001527
1528private:
Howard Hinnant9fd9f842013-09-30 19:08:22 +00001529 typedef __hash_value_type<key_type, mapped_type> __value_type;
Howard Hinnantabb160e2013-07-05 18:06:00 +00001530 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1531 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Marshall Clow1f508012015-04-07 05:21:38 +00001532 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1533 __value_type>::type __allocator_type;
Howard Hinnant3e519522010-05-11 19:42:16 +00001534
1535 typedef __hash_table<__value_type, __hasher,
1536 __key_equal, __allocator_type> __table;
1537
1538 __table __table_;
1539
Eric Fiselierfcd02212016-02-11 11:59:44 +00001540 typedef typename __table::_NodeTypes _NodeTypes;
Howard Hinnant3e519522010-05-11 19:42:16 +00001541 typedef typename __table::__node_traits __node_traits;
1542 typedef typename __table::__node_allocator __node_allocator;
1543 typedef typename __table::__node __node;
Howard Hinnantc003db12011-11-29 18:15:50 +00001544 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1545 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnant3e519522010-05-11 19:42:16 +00001546 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +00001547 static_assert((is_same<typename __node_traits::size_type,
1548 typename __alloc_traits::size_type>::value),
1549 "Allocator uses different size_type for different types");
Howard Hinnant3e519522010-05-11 19:42:16 +00001550public:
1551 typedef typename __alloc_traits::pointer pointer;
1552 typedef typename __alloc_traits::const_pointer const_pointer;
Eric Fiselier75d0dcf2016-02-10 20:46:23 +00001553 typedef typename __table::size_type size_type;
1554 typedef typename __table::difference_type difference_type;
Howard Hinnant3e519522010-05-11 19:42:16 +00001555
1556 typedef __hash_map_iterator<typename __table::iterator> iterator;
1557 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1558 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1559 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1560
Howard Hinnant789847d2010-09-23 18:58:28 +00001561 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001562 unordered_multimap()
1563 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnantb24c8022013-07-23 22:01:58 +00001564 {
1565#if _LIBCPP_DEBUG_LEVEL >= 2
1566 __get_db()->__insert_c(this);
1567#endif
1568 }
Howard Hinnant3e519522010-05-11 19:42:16 +00001569 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1570 const key_equal& __eql = key_equal());
1571 unordered_multimap(size_type __n, const hasher& __hf,
1572 const key_equal& __eql,
1573 const allocator_type& __a);
1574 template <class _InputIterator>
1575 unordered_multimap(_InputIterator __first, _InputIterator __last);
1576 template <class _InputIterator>
1577 unordered_multimap(_InputIterator __first, _InputIterator __last,
1578 size_type __n, const hasher& __hf = hasher(),
1579 const key_equal& __eql = key_equal());
1580 template <class _InputIterator>
1581 unordered_multimap(_InputIterator __first, _InputIterator __last,
1582 size_type __n, const hasher& __hf,
1583 const key_equal& __eql,
1584 const allocator_type& __a);
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001585 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001586 explicit unordered_multimap(const allocator_type& __a);
1587 unordered_multimap(const unordered_multimap& __u);
1588 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001589#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001590 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001591 unordered_multimap(unordered_multimap&& __u)
1592 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +00001593 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001594#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant54976f22011-08-12 21:56:02 +00001595#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant3e519522010-05-11 19:42:16 +00001596 unordered_multimap(initializer_list<value_type> __il);
1597 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1598 const hasher& __hf = hasher(),
1599 const key_equal& __eql = key_equal());
1600 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1601 const hasher& __hf, const key_equal& __eql,
1602 const allocator_type& __a);
Howard Hinnant54976f22011-08-12 21:56:02 +00001603#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Marshall Clow3cd37e62013-09-12 03:00:31 +00001604#if _LIBCPP_STD_VER > 11
1605 _LIBCPP_INLINE_VISIBILITY
1606 unordered_multimap(size_type __n, const allocator_type& __a)
1607 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1608 _LIBCPP_INLINE_VISIBILITY
1609 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1610 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1611 template <class _InputIterator>
1612 _LIBCPP_INLINE_VISIBILITY
1613 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1614 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1615 template <class _InputIterator>
1616 _LIBCPP_INLINE_VISIBILITY
1617 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1618 const allocator_type& __a)
1619 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1620 _LIBCPP_INLINE_VISIBILITY
1621 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1622 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1623 _LIBCPP_INLINE_VISIBILITY
1624 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1625 const allocator_type& __a)
1626 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1627#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001628 // ~unordered_multimap() = default;
Howard Hinnant5a336872011-07-01 19:24:36 +00001629 _LIBCPP_INLINE_VISIBILITY
1630 unordered_multimap& operator=(const unordered_multimap& __u)
1631 {
Marshall Clow2ee83722016-07-18 13:19:00 +00001632#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant5a336872011-07-01 19:24:36 +00001633 __table_ = __u.__table_;
Howard Hinnant307f8142013-06-22 15:21:29 +00001634#else
Marshall Clow74cf6ff2014-02-08 04:03:14 +00001635 if (this != &__u) {
1636 __table_.clear();
1637 __table_.hash_function() = __u.__table_.hash_function();
1638 __table_.key_eq() = __u.__table_.key_eq();
1639 __table_.max_load_factor() = __u.__table_.max_load_factor();
1640 __table_.__copy_assign_alloc(__u.__table_);
1641 insert(__u.begin(), __u.end());
1642 }
Howard Hinnant307f8142013-06-22 15:21:29 +00001643#endif
Howard Hinnant5a336872011-07-01 19:24:36 +00001644 return *this;
1645 }
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001646#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001647 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001648 unordered_multimap& operator=(unordered_multimap&& __u)
1649 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnant3e519522010-05-11 19:42:16 +00001650#endif
Howard Hinnant54976f22011-08-12 21:56:02 +00001651#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001652 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001653 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnant54976f22011-08-12 21:56:02 +00001654#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant3e519522010-05-11 19:42:16 +00001655
Howard Hinnant789847d2010-09-23 18:58:28 +00001656 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001657 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnant3e519522010-05-11 19:42:16 +00001658 {return allocator_type(__table_.__node_alloc());}
1659
Howard Hinnant789847d2010-09-23 18:58:28 +00001660 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001661 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnant789847d2010-09-23 18:58:28 +00001662 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001663 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001664 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001665 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnant3e519522010-05-11 19:42:16 +00001666
Howard Hinnant789847d2010-09-23 18:58:28 +00001667 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001668 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001669 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001670 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001671 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001672 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001673 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001674 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001675 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001676 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001677 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001678 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnant3e519522010-05-11 19:42:16 +00001679
Eric Fiselier7a9f5002016-04-18 01:40:45 +00001680 _LIBCPP_INLINE_VISIBILITY
1681 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1682
1683 _LIBCPP_INLINE_VISIBILITY
1684 iterator insert(const_iterator __p, const value_type& __x)
1685 {return __table_.__insert_multi(__p.__i_, __x);}
1686
1687 template <class _InputIterator>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001688 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier7a9f5002016-04-18 01:40:45 +00001689 void insert(_InputIterator __first, _InputIterator __last);
1690
1691#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1692 _LIBCPP_INLINE_VISIBILITY
1693 void insert(initializer_list<value_type> __il)
1694 {insert(__il.begin(), __il.end());}
1695#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1696
Eric Fiselierfcd02212016-02-11 11:59:44 +00001697#ifndef _LIBCPP_CXX03_LANG
Eric Fiselier7a9f5002016-04-18 01:40:45 +00001698 _LIBCPP_INLINE_VISIBILITY
1699 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1700
1701 _LIBCPP_INLINE_VISIBILITY
1702 iterator insert(const_iterator __p, value_type&& __x)
1703 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));}
1704
1705 template <class _Pp,
1706 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1707 _LIBCPP_INLINE_VISIBILITY
1708 iterator insert(_Pp&& __x)
1709 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
1710
1711 template <class _Pp,
1712 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1713 _LIBCPP_INLINE_VISIBILITY
1714 iterator insert(const_iterator __p, _Pp&& __x)
1715 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
1716
Eric Fiselierfcd02212016-02-11 11:59:44 +00001717 template <class... _Args>
1718 iterator emplace(_Args&&... __args) {
1719 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1720 }
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001721
Howard Hinnant8b805c92012-05-25 22:04:21 +00001722 template <class... _Args>
Eric Fiselierfcd02212016-02-11 11:59:44 +00001723 iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1724 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1725 }
1726#endif // _LIBCPP_CXX03_LANG
Howard Hinnant3e519522010-05-11 19:42:16 +00001727
Howard Hinnant3e519522010-05-11 19:42:16 +00001728
Howard Hinnant789847d2010-09-23 18:58:28 +00001729 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001730 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001731 _LIBCPP_INLINE_VISIBILITY
Marshall Clowec392962015-05-10 13:35:00 +00001732 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1733 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001734 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001735 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001736 iterator erase(const_iterator __first, const_iterator __last)
1737 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001739 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnant3e519522010-05-11 19:42:16 +00001740
Howard Hinnant789847d2010-09-23 18:58:28 +00001741 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001742 void swap(unordered_multimap& __u)
1743 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1744 {__table_.swap(__u.__table_);}
Howard Hinnant3e519522010-05-11 19:42:16 +00001745
Howard Hinnant789847d2010-09-23 18:58:28 +00001746 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001747 hasher hash_function() const
1748 {return __table_.hash_function().hash_function();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001749 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001750 key_equal key_eq() const
1751 {return __table_.key_eq().key_eq();}
1752
Howard Hinnant789847d2010-09-23 18:58:28 +00001753 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001754 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001755 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001756 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001757 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001758 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001759 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001760 pair<iterator, iterator> equal_range(const key_type& __k)
1761 {return __table_.__equal_range_multi(__k);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001762 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001763 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1764 {return __table_.__equal_range_multi(__k);}
1765
Howard Hinnant789847d2010-09-23 18:58:28 +00001766 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001767 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001768 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001769 size_type max_bucket_count() const _NOEXCEPT
1770 {return __table_.max_bucket_count();}
Howard Hinnant3e519522010-05-11 19:42:16 +00001771
Howard Hinnant789847d2010-09-23 18:58:28 +00001772 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001773 size_type bucket_size(size_type __n) const
1774 {return __table_.bucket_size(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001776 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1777
Howard Hinnant789847d2010-09-23 18:58:28 +00001778 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001779 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001781 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001782 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001783 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001784 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001785 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001786 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001787 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001788 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001789 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1790
Howard Hinnant789847d2010-09-23 18:58:28 +00001791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001792 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant37141072011-06-04 18:54:24 +00001794 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnant789847d2010-09-23 18:58:28 +00001795 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001796 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001797 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001798 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnant789847d2010-09-23 18:58:28 +00001799 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00001800 void reserve(size_type __n) {__table_.reserve(__n);}
1801
Howard Hinnantb24c8022013-07-23 22:01:58 +00001802#if _LIBCPP_DEBUG_LEVEL >= 2
1803
1804 bool __dereferenceable(const const_iterator* __i) const
1805 {return __table_.__dereferenceable(&__i->__i_);}
1806 bool __decrementable(const const_iterator* __i) const
1807 {return __table_.__decrementable(&__i->__i_);}
1808 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1809 {return __table_.__addable(&__i->__i_, __n);}
1810 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1811 {return __table_.__addable(&__i->__i_, __n);}
1812
1813#endif // _LIBCPP_DEBUG_LEVEL >= 2
1814
Eric Fiselierfcd02212016-02-11 11:59:44 +00001815
Howard Hinnant3e519522010-05-11 19:42:16 +00001816};
1817
1818template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1819unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1820 size_type __n, const hasher& __hf, const key_equal& __eql)
1821 : __table_(__hf, __eql)
1822{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001823#if _LIBCPP_DEBUG_LEVEL >= 2
1824 __get_db()->__insert_c(this);
1825#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001826 __table_.rehash(__n);
1827}
1828
1829template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1830unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1831 size_type __n, const hasher& __hf, const key_equal& __eql,
1832 const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001833 : __table_(__hf, __eql, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001834{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001835#if _LIBCPP_DEBUG_LEVEL >= 2
1836 __get_db()->__insert_c(this);
1837#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001838 __table_.rehash(__n);
1839}
1840
1841template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1842template <class _InputIterator>
1843unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1844 _InputIterator __first, _InputIterator __last)
1845{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001846#if _LIBCPP_DEBUG_LEVEL >= 2
1847 __get_db()->__insert_c(this);
1848#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001849 insert(__first, __last);
1850}
1851
1852template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1853template <class _InputIterator>
1854unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1855 _InputIterator __first, _InputIterator __last, size_type __n,
1856 const hasher& __hf, const key_equal& __eql)
1857 : __table_(__hf, __eql)
1858{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001859#if _LIBCPP_DEBUG_LEVEL >= 2
1860 __get_db()->__insert_c(this);
1861#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001862 __table_.rehash(__n);
1863 insert(__first, __last);
1864}
1865
1866template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1867template <class _InputIterator>
1868unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1869 _InputIterator __first, _InputIterator __last, size_type __n,
1870 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001871 : __table_(__hf, __eql, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001872{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001873#if _LIBCPP_DEBUG_LEVEL >= 2
1874 __get_db()->__insert_c(this);
1875#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001876 __table_.rehash(__n);
1877 insert(__first, __last);
1878}
1879
Howard Hinnant3e519522010-05-11 19:42:16 +00001880template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001881inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001882unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1883 const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001884 : __table_(typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001885{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001886#if _LIBCPP_DEBUG_LEVEL >= 2
1887 __get_db()->__insert_c(this);
1888#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001889}
1890
1891template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1892unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1893 const unordered_multimap& __u)
1894 : __table_(__u.__table_)
1895{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001896#if _LIBCPP_DEBUG_LEVEL >= 2
1897 __get_db()->__insert_c(this);
1898#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001899 __table_.rehash(__u.bucket_count());
1900 insert(__u.begin(), __u.end());
1901}
1902
1903template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1904unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1905 const unordered_multimap& __u, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001906 : __table_(__u.__table_, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001907{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001908#if _LIBCPP_DEBUG_LEVEL >= 2
1909 __get_db()->__insert_c(this);
1910#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001911 __table_.rehash(__u.bucket_count());
1912 insert(__u.begin(), __u.end());
1913}
1914
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001915#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001916
1917template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001918inline
Howard Hinnant3e519522010-05-11 19:42:16 +00001919unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1920 unordered_multimap&& __u)
Howard Hinnant37141072011-06-04 18:54:24 +00001921 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnantce48a112011-06-30 21:18:19 +00001922 : __table_(_VSTD::move(__u.__table_))
Howard Hinnant3e519522010-05-11 19:42:16 +00001923{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001924#if _LIBCPP_DEBUG_LEVEL >= 2
1925 __get_db()->__insert_c(this);
Howard Hinnant4c80bfb2013-07-30 21:04:42 +00001926 __get_db()->swap(this, &__u);
Howard Hinnantb24c8022013-07-23 22:01:58 +00001927#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001928}
1929
1930template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1931unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1932 unordered_multimap&& __u, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001933 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001934{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001935#if _LIBCPP_DEBUG_LEVEL >= 2
1936 __get_db()->__insert_c(this);
1937#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001938 if (__a != __u.get_allocator())
1939 {
1940 iterator __i = __u.begin();
1941 while (__u.size() != 0)
Howard Hinnantb24c8022013-07-23 22:01:58 +00001942 {
Howard Hinnant3e519522010-05-11 19:42:16 +00001943 __table_.__insert_multi(
Eric Fiselierfcd02212016-02-11 11:59:44 +00001944 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc)
Howard Hinnant3e519522010-05-11 19:42:16 +00001945 );
Howard Hinnantb24c8022013-07-23 22:01:58 +00001946 }
Howard Hinnant3e519522010-05-11 19:42:16 +00001947 }
Howard Hinnant4c80bfb2013-07-30 21:04:42 +00001948#if _LIBCPP_DEBUG_LEVEL >= 2
1949 else
1950 __get_db()->swap(this, &__u);
1951#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001952}
1953
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001954#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001955
Howard Hinnant54976f22011-08-12 21:56:02 +00001956#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1957
Howard Hinnant3e519522010-05-11 19:42:16 +00001958template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1959unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1960 initializer_list<value_type> __il)
1961{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001962#if _LIBCPP_DEBUG_LEVEL >= 2
1963 __get_db()->__insert_c(this);
1964#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001965 insert(__il.begin(), __il.end());
1966}
1967
1968template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1969unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1970 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1971 const key_equal& __eql)
1972 : __table_(__hf, __eql)
1973{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001974#if _LIBCPP_DEBUG_LEVEL >= 2
1975 __get_db()->__insert_c(this);
1976#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001977 __table_.rehash(__n);
1978 insert(__il.begin(), __il.end());
1979}
1980
1981template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1982unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1983 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1984 const key_equal& __eql, const allocator_type& __a)
Marshall Clow2a10c962016-08-17 05:58:40 +00001985 : __table_(__hf, __eql, typename __table::allocator_type(__a))
Howard Hinnant3e519522010-05-11 19:42:16 +00001986{
Howard Hinnantb24c8022013-07-23 22:01:58 +00001987#if _LIBCPP_DEBUG_LEVEL >= 2
1988 __get_db()->__insert_c(this);
1989#endif
Howard Hinnant3e519522010-05-11 19:42:16 +00001990 __table_.rehash(__n);
1991 insert(__il.begin(), __il.end());
1992}
1993
Howard Hinnant54976f22011-08-12 21:56:02 +00001994#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1995
Howard Hinnant7609c9b2010-09-04 23:28:19 +00001996#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00001997
1998template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00001999inline
Howard Hinnant3e519522010-05-11 19:42:16 +00002000unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2001unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant37141072011-06-04 18:54:24 +00002002 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnant3e519522010-05-11 19:42:16 +00002003{
Howard Hinnantce48a112011-06-30 21:18:19 +00002004 __table_ = _VSTD::move(__u.__table_);
Howard Hinnant3e519522010-05-11 19:42:16 +00002005 return *this;
2006}
2007
Howard Hinnant7609c9b2010-09-04 23:28:19 +00002008#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant3e519522010-05-11 19:42:16 +00002009
Howard Hinnant54976f22011-08-12 21:56:02 +00002010#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2011
Howard Hinnant3e519522010-05-11 19:42:16 +00002012template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00002013inline
Howard Hinnant3e519522010-05-11 19:42:16 +00002014unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2015unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2016 initializer_list<value_type> __il)
2017{
2018 __table_.__assign_multi(__il.begin(), __il.end());
2019 return *this;
2020}
2021
Howard Hinnant54976f22011-08-12 21:56:02 +00002022#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2023
Howard Hinnant3e519522010-05-11 19:42:16 +00002024
Howard Hinnant3e519522010-05-11 19:42:16 +00002025
2026template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2027template <class _InputIterator>
Evgeniy Stepanovcd31b432016-04-22 01:04:55 +00002028inline
Howard Hinnant3e519522010-05-11 19:42:16 +00002029void
2030unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2031 _InputIterator __last)
2032{
2033 for (; __first != __last; ++__first)
2034 __table_.__insert_multi(*__first);
2035}
2036
2037template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant789847d2010-09-23 18:58:28 +00002038inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00002039void
2040swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2041 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant37141072011-06-04 18:54:24 +00002042 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnant3e519522010-05-11 19:42:16 +00002043{
2044 __x.swap(__y);
2045}
2046
2047template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2048bool
2049operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2050 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2051{
2052 if (__x.size() != __y.size())
2053 return false;
2054 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2055 const_iterator;
2056 typedef pair<const_iterator, const_iterator> _EqRng;
2057 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2058 {
2059 _EqRng __xeq = __x.equal_range(__i->first);
2060 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnantce48a112011-06-30 21:18:19 +00002061 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2062 _VSTD::distance(__yeq.first, __yeq.second) ||
2063 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnant3e519522010-05-11 19:42:16 +00002064 return false;
2065 __i = __xeq.second;
2066 }
2067 return true;
2068}
2069
2070template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant789847d2010-09-23 18:58:28 +00002071inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e519522010-05-11 19:42:16 +00002072bool
2073operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2074 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2075{
2076 return !(__x == __y);
2077}
2078
2079_LIBCPP_END_NAMESPACE_STD
2080
2081#endif // _LIBCPP_UNORDERED_MAP