blob: 0242cde8335c736129ac3a44097e000962315bab [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-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 Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Clow6dff6182013-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 Hinnantbc8d3f92010-05-11 19:42:16 +000088 ~unordered_map();
89 unordered_map& operator=(const unordered_map&);
Howard Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-05-11 19:42:16 +000096 unordered_map& operator=(initializer_list<value_type>);
97
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000098 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000099
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000100 bool empty() const noexcept;
101 size_type size() const noexcept;
102 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000103
Howard Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Clow0ce05a92015-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 Hinnantbc8d3f92010-05-11 19:42:16 +0000142 iterator erase(const_iterator position);
Marshall Clow488025c2015-05-10 13:35:00 +0000143 iterator erase(iterator position); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000144 size_type erase(const key_type& k);
145 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000146 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000147
Howard Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-06-04 18:54:24 +0000170 size_type bucket_count() const noexcept;
171 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-06-04 18:54:24 +0000183 float load_factor() const noexcept;
184 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-06-04 18:54:24 +0000192 unordered_map<Key, T, Hash, Pred, Alloc>& y)
193 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Clow6dff6182013-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 Hinnantbc8d3f92010-05-11 19:42:16 +0000270 ~unordered_multimap();
271 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-05-11 19:42:16 +0000278 unordered_multimap& operator=(initializer_list<value_type>);
279
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000280 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000281
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000282 bool empty() const noexcept;
283 size_type size() const noexcept;
284 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000285
Howard Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Clow488025c2015-05-10 13:35:00 +0000308 iterator erase(iterator position); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000309 size_type erase(const key_type& k);
310 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000311 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000312
Howard Hinnant5f2f14c2011-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 Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-06-04 18:54:24 +0000329 size_type bucket_count() const noexcept;
330 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-06-04 18:54:24 +0000342 float load_factor() const noexcept;
343 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-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 Hinnant5f2f14c2011-06-04 18:54:24 +0000351 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
352 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-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>
372
Eric Fiselierb9536102014-08-10 23:53:08 +0000373#include <__debug>
374
Howard Hinnant08e17472011-10-17 20:05:10 +0000375#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000376#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000377#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000378
379_LIBCPP_BEGIN_NAMESPACE_STD
380
Eric Fiselier3a0e4302015-06-13 07:08:02 +0000381template <class _Key, class _Cp, class _Hash,
382 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000383 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000384class __unordered_map_hasher
385 : private _Hash
386{
387public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000388 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000389 __unordered_map_hasher()
390 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
391 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000393 __unordered_map_hasher(const _Hash& __h)
394 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
395 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000397 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000398 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000399 size_t operator()(const _Cp& __x) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000400 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000401 _LIBCPP_INLINE_VISIBILITY
402 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000403 {return static_cast<const _Hash&>(*this)(__x);}
Marshall Clow7d914d12015-07-13 20:04:56 +0000404 void swap(__unordered_map_hasher&__y)
405 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
406 {
407 using _VSTD::swap;
408 swap(static_cast<const _Hash&>(*this), static_cast<const _Hash&>(__y));
409 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000410};
411
Howard Hinnant9b128e02013-07-05 18:06:00 +0000412template <class _Key, class _Cp, class _Hash>
413class __unordered_map_hasher<_Key, _Cp, _Hash, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000414{
415 _Hash __hash_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000416
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000417public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000418 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000419 __unordered_map_hasher()
420 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
421 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000422 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000423 __unordered_map_hasher(const _Hash& __h)
424 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
425 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000427 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000428 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000429 size_t operator()(const _Cp& __x) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000430 {return __hash_(__x.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000431 _LIBCPP_INLINE_VISIBILITY
432 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000433 {return __hash_(__x);}
Marshall Clow7d914d12015-07-13 20:04:56 +0000434 void swap(__unordered_map_hasher&__y)
435 _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value)
436 {
437 using _VSTD::swap;
438 swap(__hash_, __y.__hash_);
439 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000440};
441
Marshall Clow7d914d12015-07-13 20:04:56 +0000442template <class _Key, class _Cp, class _Hash, bool __b>
443inline _LIBCPP_INLINE_VISIBILITY
444void
445swap(__unordered_map_hasher<_Key, _Cp, _Hash, __b>& __x,
446 __unordered_map_hasher<_Key, _Cp, _Hash, __b>& __y)
447 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
448{
449 __x.swap(__y);
450}
451
Eric Fiselier3a0e4302015-06-13 07:08:02 +0000452template <class _Key, class _Cp, class _Pred,
453 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000454 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000455class __unordered_map_equal
456 : private _Pred
457{
458public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000460 __unordered_map_equal()
461 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
462 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000464 __unordered_map_equal(const _Pred& __p)
465 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
466 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000468 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000469 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000470 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000471 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000472 _LIBCPP_INLINE_VISIBILITY
473 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000474 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000475 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000476 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000477 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
Marshall Clow7d914d12015-07-13 20:04:56 +0000478 void swap(__unordered_map_equal&__y)
479 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
480 {
481 using _VSTD::swap;
482 swap(static_cast<const _Pred&>(*this), static_cast<const _Pred&>(__y));
483 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000484};
485
Howard Hinnant9b128e02013-07-05 18:06:00 +0000486template <class _Key, class _Cp, class _Pred>
487class __unordered_map_equal<_Key, _Cp, _Pred, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000488{
489 _Pred __pred_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000490
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000491public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000492 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000493 __unordered_map_equal()
494 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
495 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000496 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000497 __unordered_map_equal(const _Pred& __p)
498 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
499 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000500 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000501 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000502 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000503 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000504 {return __pred_(__x.__cc.first, __y.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000505 _LIBCPP_INLINE_VISIBILITY
506 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000507 {return __pred_(__x.__cc.first, __y);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000508 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000509 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000510 {return __pred_(__x, __y.__cc.first);}
Marshall Clow7d914d12015-07-13 20:04:56 +0000511 void swap(__unordered_map_equal&__y)
512 _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value)
513 {
514 using _VSTD::swap;
515 swap(__pred_, __y.__pred_);
516 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000517};
518
Marshall Clow7d914d12015-07-13 20:04:56 +0000519template <class _Key, class _Cp, class _Pred, bool __b>
520inline _LIBCPP_INLINE_VISIBILITY
521void
522swap(__unordered_map_equal<_Key, _Cp, _Pred, __b>& __x,
523 __unordered_map_equal<_Key, _Cp, _Pred, __b>& __y)
524 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
525{
526 __x.swap(__y);
527}
528
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000529template <class _Alloc>
530class __hash_map_node_destructor
531{
532 typedef _Alloc allocator_type;
533 typedef allocator_traits<allocator_type> __alloc_traits;
534 typedef typename __alloc_traits::value_type::value_type value_type;
535public:
536 typedef typename __alloc_traits::pointer pointer;
537private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000538 typedef typename value_type::value_type::first_type first_type;
539 typedef typename value_type::value_type::second_type second_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000540
541 allocator_type& __na_;
542
543 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
544
545public:
546 bool __first_constructed;
547 bool __second_constructed;
548
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000549 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000550 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000551 : __na_(__na),
552 __first_constructed(false),
553 __second_constructed(false)
554 {}
555
Howard Hinnant73d21a42010-09-04 23:28:19 +0000556#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000557 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000558 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000559 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000560 : __na_(__x.__na_),
561 __first_constructed(__x.__value_constructed),
562 __second_constructed(__x.__value_constructed)
563 {
564 __x.__value_constructed = false;
565 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000566#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
569 : __na_(__x.__na_),
570 __first_constructed(__x.__value_constructed),
571 __second_constructed(__x.__value_constructed)
572 {
573 const_cast<bool&>(__x.__value_constructed) = false;
574 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000575#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000576
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000578 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000579 {
580 if (__second_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000581 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000582 if (__first_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000583 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000584 if (__p)
585 __alloc_traits::deallocate(__na_, __p, 1);
586 }
587};
588
Howard Hinnantff7546e2013-09-30 19:08:22 +0000589#if __cplusplus >= 201103L
590
591template <class _Key, class _Tp>
592union __hash_value_type
593{
594 typedef _Key key_type;
595 typedef _Tp mapped_type;
596 typedef pair<const key_type, mapped_type> value_type;
597 typedef pair<key_type, mapped_type> __nc_value_type;
598
599 value_type __cc;
600 __nc_value_type __nc;
601
602 template <class ..._Args>
603 _LIBCPP_INLINE_VISIBILITY
604 __hash_value_type(_Args&& ...__args)
605 : __cc(std::forward<_Args>(__args)...) {}
606
607 _LIBCPP_INLINE_VISIBILITY
608 __hash_value_type(const __hash_value_type& __v)
609 : __cc(__v.__cc) {}
610
611 _LIBCPP_INLINE_VISIBILITY
612 __hash_value_type(__hash_value_type&& __v)
Marshall Clowcd137822015-05-06 12:11:22 +0000613 : __nc(_VSTD::move(__v.__nc)) {}
Howard Hinnantff7546e2013-09-30 19:08:22 +0000614
615 _LIBCPP_INLINE_VISIBILITY
616 __hash_value_type& operator=(const __hash_value_type& __v)
617 {__nc = __v.__cc; return *this;}
618
619 _LIBCPP_INLINE_VISIBILITY
620 __hash_value_type& operator=(__hash_value_type&& __v)
Marshall Clowcd137822015-05-06 12:11:22 +0000621 {__nc = _VSTD::move(__v.__nc); return *this;}
Howard Hinnantff7546e2013-09-30 19:08:22 +0000622
623 _LIBCPP_INLINE_VISIBILITY
624 ~__hash_value_type() {__cc.~value_type();}
625};
626
627#else
628
629template <class _Key, class _Tp>
630struct __hash_value_type
631{
632 typedef _Key key_type;
633 typedef _Tp mapped_type;
634 typedef pair<const key_type, mapped_type> value_type;
635
636 value_type __cc;
637
638 _LIBCPP_INLINE_VISIBILITY
639 __hash_value_type() {}
640
641 template <class _A0>
642 _LIBCPP_INLINE_VISIBILITY
643 __hash_value_type(const _A0& __a0)
644 : __cc(__a0) {}
645
646 template <class _A0, class _A1>
647 _LIBCPP_INLINE_VISIBILITY
648 __hash_value_type(const _A0& __a0, const _A1& __a1)
649 : __cc(__a0, __a1) {}
650};
651
652#endif
653
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000654template <class _HashIterator>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000655class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000656{
657 _HashIterator __i_;
658
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000659 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
660 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000661public:
662 typedef forward_iterator_tag iterator_category;
663 typedef pair<key_type, mapped_type> value_type;
664 typedef typename _HashIterator::difference_type difference_type;
665 typedef value_type& reference;
Eric Fiselier5cf84e02015-12-30 21:52:00 +0000666 typedef typename __rebind_pointer<typename _HashIterator::pointer, value_type>::type
667 pointer;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000668
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000669 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000670 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000671
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000672 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000673 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000674
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000675 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000676 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000677 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000678 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000679
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000680 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000681 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000682 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000683 __hash_map_iterator operator++(int)
684 {
685 __hash_map_iterator __t(*this);
686 ++(*this);
687 return __t;
688 }
689
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000690 friend _LIBCPP_INLINE_VISIBILITY
691 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000692 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000693 friend _LIBCPP_INLINE_VISIBILITY
694 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000695 {return __x.__i_ != __y.__i_;}
696
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000697 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
698 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
699 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
700 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
701 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000702};
703
704template <class _HashIterator>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000705class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000706{
707 _HashIterator __i_;
708
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000709 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
710 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000711public:
712 typedef forward_iterator_tag iterator_category;
713 typedef pair<key_type, mapped_type> value_type;
714 typedef typename _HashIterator::difference_type difference_type;
715 typedef const value_type& reference;
Eric Fiselier5cf84e02015-12-30 21:52:00 +0000716 typedef typename __rebind_pointer<typename _HashIterator::pointer, const value_type>::type
717 pointer;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000718
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000719 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000720 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000721
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000722 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000723 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000724 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000725 __hash_map_const_iterator(
726 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000727 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000728 : __i_(__i.__i_) {}
729
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000730 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000731 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000732 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000733 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000734
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000735 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000736 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000737 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000738 __hash_map_const_iterator operator++(int)
739 {
740 __hash_map_const_iterator __t(*this);
741 ++(*this);
742 return __t;
743 }
744
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000745 friend _LIBCPP_INLINE_VISIBILITY
746 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000747 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000748 friend _LIBCPP_INLINE_VISIBILITY
749 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000750 {return __x.__i_ != __y.__i_;}
751
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000752 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
753 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
754 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
755 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000756};
757
758template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
759 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000760class _LIBCPP_TYPE_VIS_ONLY unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000761{
762public:
763 // types
764 typedef _Key key_type;
765 typedef _Tp mapped_type;
766 typedef _Hash hasher;
767 typedef _Pred key_equal;
768 typedef _Alloc allocator_type;
769 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000770 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000771 typedef value_type& reference;
772 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +0000773 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
774 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000775
776private:
Howard Hinnantff7546e2013-09-30 19:08:22 +0000777 typedef __hash_value_type<key_type, mapped_type> __value_type;
Howard Hinnant9b128e02013-07-05 18:06:00 +0000778 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
779 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Marshall Clow66302c62015-04-07 05:21:38 +0000780 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
781 __value_type>::type __allocator_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000782
783 typedef __hash_table<__value_type, __hasher,
784 __key_equal, __allocator_type> __table;
785
786 __table __table_;
787
788 typedef typename __table::__node_pointer __node_pointer;
789 typedef typename __table::__node_const_pointer __node_const_pointer;
790 typedef typename __table::__node_traits __node_traits;
791 typedef typename __table::__node_allocator __node_allocator;
792 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +0000793 typedef __hash_map_node_destructor<__node_allocator> _Dp;
794 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000795 typedef allocator_traits<allocator_type> __alloc_traits;
796public:
797 typedef typename __alloc_traits::pointer pointer;
798 typedef typename __alloc_traits::const_pointer const_pointer;
799 typedef typename __alloc_traits::size_type size_type;
800 typedef typename __alloc_traits::difference_type difference_type;
801
802 typedef __hash_map_iterator<typename __table::iterator> iterator;
803 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
804 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
805 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
806
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000807 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000808 unordered_map()
809 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +0000810 {
811#if _LIBCPP_DEBUG_LEVEL >= 2
812 __get_db()->__insert_c(this);
813#endif
814 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000815 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
816 const key_equal& __eql = key_equal());
817 unordered_map(size_type __n, const hasher& __hf,
818 const key_equal& __eql,
819 const allocator_type& __a);
820 template <class _InputIterator>
821 unordered_map(_InputIterator __first, _InputIterator __last);
822 template <class _InputIterator>
823 unordered_map(_InputIterator __first, _InputIterator __last,
824 size_type __n, const hasher& __hf = hasher(),
825 const key_equal& __eql = key_equal());
826 template <class _InputIterator>
827 unordered_map(_InputIterator __first, _InputIterator __last,
828 size_type __n, const hasher& __hf,
829 const key_equal& __eql,
830 const allocator_type& __a);
831 explicit unordered_map(const allocator_type& __a);
832 unordered_map(const unordered_map& __u);
833 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000834#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000835 unordered_map(unordered_map&& __u)
836 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000837 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000838#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000839#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000840 unordered_map(initializer_list<value_type> __il);
841 unordered_map(initializer_list<value_type> __il, size_type __n,
842 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
843 unordered_map(initializer_list<value_type> __il, size_type __n,
844 const hasher& __hf, const key_equal& __eql,
845 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000846#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Marshall Clow6dff6182013-09-12 03:00:31 +0000847#if _LIBCPP_STD_VER > 11
848 _LIBCPP_INLINE_VISIBILITY
849 unordered_map(size_type __n, const allocator_type& __a)
850 : unordered_map(__n, hasher(), key_equal(), __a) {}
851 _LIBCPP_INLINE_VISIBILITY
852 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
853 : unordered_map(__n, __hf, key_equal(), __a) {}
854 template <class _InputIterator>
855 _LIBCPP_INLINE_VISIBILITY
856 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
857 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
858 template <class _InputIterator>
859 _LIBCPP_INLINE_VISIBILITY
860 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
861 const allocator_type& __a)
862 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
863 _LIBCPP_INLINE_VISIBILITY
864 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
865 : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
866 _LIBCPP_INLINE_VISIBILITY
867 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
868 const allocator_type& __a)
869 : unordered_map(__il, __n, __hf, key_equal(), __a) {}
870#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000871 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000872 _LIBCPP_INLINE_VISIBILITY
873 unordered_map& operator=(const unordered_map& __u)
874 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000875#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +0000876 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000877#else
Marshall Clowebfc50e2014-02-08 04:03:14 +0000878 if (this != &__u) {
879 __table_.clear();
880 __table_.hash_function() = __u.__table_.hash_function();
881 __table_.key_eq() = __u.__table_.key_eq();
882 __table_.max_load_factor() = __u.__table_.max_load_factor();
883 __table_.__copy_assign_alloc(__u.__table_);
884 insert(__u.begin(), __u.end());
885 }
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000886#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +0000887 return *this;
888 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000889#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000890 unordered_map& operator=(unordered_map&& __u)
891 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000892#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000893#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000894 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000895#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000896
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000898 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000899 {return allocator_type(__table_.__node_alloc());}
900
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000902 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000904 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000906 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000907
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000908 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000909 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000910 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000911 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000912 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000913 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000914 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000915 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000916 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000917 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000918 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000919 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000920
Howard Hinnant73d21a42010-09-04 23:28:19 +0000921#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +0000922#ifndef _LIBCPP_HAS_NO_VARIADICS
923
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000924 template <class... _Args>
Duncan P. N. Exon Smith9f745c82016-01-22 22:48:02 +0000925 pair<iterator, bool> emplace(_Args&&... __args)
926 {return __emplace_dispatch(std::forward<_Args>(__args)...);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000927
Duncan P. N. Exon Smith9f745c82016-01-22 22:48:02 +0000928private:
929 template <class _Arg>
930 pair<iterator, bool> __emplace_dispatch(_Arg&& __arg)
931 {
932 typedef is_constructible<value_type, _Arg> __constructible;
933 return __emplace_insert_if_constructible(std::forward<_Arg>(__arg),
934 __constructible());
935 }
936 template <class _Arg1, class... _Args>
937 pair<iterator, bool> __emplace_dispatch(_Arg1&& __arg1, _Args&&... __args)
938 {return __emplace_impl(std::forward<_Arg1>(__arg1), std::forward<_Args>(__args)...);}
939
940 template <class _Arg>
941 pair<iterator, bool> __emplace_insert_if_constructible(_Arg&& __arg, false_type)
942 {return __emplace_impl(std::forward<_Arg>(__arg));}
943 template <class _Arg>
944 pair<iterator, bool> __emplace_insert_if_constructible(_Arg&& __arg, true_type)
945 {return insert(std::forward<_Arg>(__arg));}
946
947 template <class... _Args>
948 pair<iterator, bool> __emplace_impl(_Args&&... __args);
949
950public:
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000951 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000952 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000953#if _LIBCPP_DEBUG_LEVEL >= 2
954 iterator emplace_hint(const_iterator __p, _Args&&... __args)
955 {
956 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
957 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
958 " referring to this unordered_map");
Duncan P. N. Exon Smith9f745c82016-01-22 22:48:02 +0000959 return emplace(_VSTD::forward<_Args>(__args)...).first;
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000960 }
961#else
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000962 iterator emplace_hint(const_iterator, _Args&&... __args)
963 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000964#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000965#endif // _LIBCPP_HAS_NO_VARIADICS
966#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000967 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000968 pair<iterator, bool> insert(const value_type& __x)
969 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000970#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000971 template <class _Pp,
972 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000973 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000974 pair<iterator, bool> insert(_Pp&& __x)
975 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000976#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000977 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000978#if _LIBCPP_DEBUG_LEVEL >= 2
979 iterator insert(const_iterator __p, const value_type& __x)
980 {
981 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
982 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
983 " referring to this unordered_map");
984 return insert(__x).first;
985 }
986#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000987 iterator insert(const_iterator, const value_type& __x)
988 {return insert(__x).first;}
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000989#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000990#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000991 template <class _Pp,
992 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000993 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000994#if _LIBCPP_DEBUG_LEVEL >= 2
995 iterator insert(const_iterator __p, _Pp&& __x)
996 {
997 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
998 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
999 " referring to this unordered_map");
1000 return insert(_VSTD::forward<_Pp>(__x)).first;
1001 }
1002#else
Howard Hinnant99968442011-11-29 18:15:50 +00001003 iterator insert(const_iterator, _Pp&& __x)
1004 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001005#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +00001006#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001007 template <class _InputIterator>
1008 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001009#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001010 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001011 void insert(initializer_list<value_type> __il)
1012 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001013#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001014
Marshall Clow0ce05a92015-07-07 05:45:35 +00001015#if _LIBCPP_STD_VER > 14
1016#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1017#ifndef _LIBCPP_HAS_NO_VARIADICS
1018 template <class... _Args>
1019 _LIBCPP_INLINE_VISIBILITY
1020 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1021 {
1022 iterator __p = __table_.find(__k);
1023 if ( __p != end())
1024 return _VSTD::make_pair(__p, false);
1025 else
1026 return _VSTD::make_pair(
1027 emplace_hint(__p,
1028 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1029 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1030 true);
1031 }
1032
1033 template <class... _Args>
1034 _LIBCPP_INLINE_VISIBILITY
1035 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1036 {
1037 iterator __p = __table_.find(__k);
1038 if ( __p != end())
1039 return _VSTD::make_pair(__p, false);
1040 else
1041 return _VSTD::make_pair(
1042 emplace_hint(__p,
1043 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1044 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1045 true);
1046 }
1047
1048 template <class... _Args>
1049 _LIBCPP_INLINE_VISIBILITY
1050 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1051 {
1052 iterator __p = __table_.find(__k);
1053 if ( __p != end())
1054 return __p;
1055 else
1056 return emplace_hint(__h,
1057 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1058 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1059 }
1060
1061 template <class... _Args>
1062 _LIBCPP_INLINE_VISIBILITY
1063 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1064 {
1065 iterator __p = __table_.find(__k);
1066 if ( __p != end())
1067 return __p;
1068 else
1069 return emplace_hint(__h,
1070 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1071 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1072 }
1073
1074 template <class _Vp>
1075 _LIBCPP_INLINE_VISIBILITY
1076 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1077 {
1078 iterator __p = __table_.find(__k);
1079 if ( __p != end())
1080 {
1081 __p->second = _VSTD::move(__v);
1082 return _VSTD::make_pair(__p, false);
1083 }
1084 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1085 }
1086
1087 template <class _Vp>
1088 _LIBCPP_INLINE_VISIBILITY
1089 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1090 {
1091 iterator __p = __table_.find(__k);
1092 if ( __p != end())
1093 {
1094 __p->second = _VSTD::move(__v);
1095 return _VSTD::make_pair(__p, false);
1096 }
1097 return _VSTD::make_pair(emplace_hint(__p, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v)), true);
1098 }
1099
1100 template <class _Vp>
1101 _LIBCPP_INLINE_VISIBILITY
1102 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1103 {
1104 iterator __p = __table_.find(__k);
1105 if ( __p != end())
1106 {
1107 __p->second = _VSTD::move(__v);
1108 return __p;
1109 }
1110 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1111 }
1112
1113 template <class _Vp>
1114 _LIBCPP_INLINE_VISIBILITY
1115 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1116 {
1117 iterator __p = __table_.find(__k);
1118 if ( __p != end())
1119 {
1120 __p->second = _VSTD::move(__v);
1121 return __p;
1122 }
1123 return emplace_hint(__h, _VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v));
1124 }
1125#endif
1126#endif
1127#endif
1128
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001129 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001130 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001131 _LIBCPP_INLINE_VISIBILITY
Marshall Clow488025c2015-05-10 13:35:00 +00001132 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1133 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001134 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001135 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001136 iterator erase(const_iterator __first, const_iterator __last)
1137 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001138 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001139 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001140
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001141 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001142 void swap(unordered_map& __u)
1143 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1144 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001145
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001146 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001147 hasher hash_function() const
1148 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001149 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001150 key_equal key_eq() const
1151 {return __table_.key_eq().key_eq();}
1152
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001153 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001154 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001155 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001156 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001157 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001158 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001159 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001160 pair<iterator, iterator> equal_range(const key_type& __k)
1161 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001162 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001163 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1164 {return __table_.__equal_range_unique(__k);}
1165
1166 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001167#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001168 mapped_type& operator[](key_type&& __k);
1169#endif
1170
1171 mapped_type& at(const key_type& __k);
1172 const mapped_type& at(const key_type& __k) const;
1173
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001174 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001175 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001176 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001177 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001178
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001179 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001180 size_type bucket_size(size_type __n) const
1181 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001182 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001183 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1184
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001185 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001186 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001187 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001188 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001189 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001190 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001191 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001192 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001193 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001194 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001195 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001196 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1197
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001198 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001199 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001200 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001201 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001202 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001203 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001204 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001205 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001206 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001207 void reserve(size_type __n) {__table_.reserve(__n);}
1208
Howard Hinnant39213642013-07-23 22:01:58 +00001209#if _LIBCPP_DEBUG_LEVEL >= 2
1210
1211 bool __dereferenceable(const const_iterator* __i) const
1212 {return __table_.__dereferenceable(&__i->__i_);}
1213 bool __decrementable(const const_iterator* __i) const
1214 {return __table_.__decrementable(&__i->__i_);}
1215 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1216 {return __table_.__addable(&__i->__i_, __n);}
1217 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1218 {return __table_.__addable(&__i->__i_, __n);}
1219
1220#endif // _LIBCPP_DEBUG_LEVEL >= 2
1221
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001222private:
Howard Hinnant73d21a42010-09-04 23:28:19 +00001223#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001224 __node_holder __construct_node();
1225 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001226 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001227 __construct_node(_A0&& __a0);
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001228 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001229#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001230 template <class _A0, class _A1, class ..._Args>
1231 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001232#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001233#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1234 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001235};
1236
1237template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1238unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1239 size_type __n, const hasher& __hf, const key_equal& __eql)
1240 : __table_(__hf, __eql)
1241{
Howard Hinnant39213642013-07-23 22:01:58 +00001242#if _LIBCPP_DEBUG_LEVEL >= 2
1243 __get_db()->__insert_c(this);
1244#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001245 __table_.rehash(__n);
1246}
1247
1248template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1249unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1250 size_type __n, const hasher& __hf, const key_equal& __eql,
1251 const allocator_type& __a)
1252 : __table_(__hf, __eql, __a)
1253{
Howard Hinnant39213642013-07-23 22:01:58 +00001254#if _LIBCPP_DEBUG_LEVEL >= 2
1255 __get_db()->__insert_c(this);
1256#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001257 __table_.rehash(__n);
1258}
1259
1260template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001261inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001262unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1263 const allocator_type& __a)
1264 : __table_(__a)
1265{
Howard Hinnant39213642013-07-23 22:01:58 +00001266#if _LIBCPP_DEBUG_LEVEL >= 2
1267 __get_db()->__insert_c(this);
1268#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001269}
1270
1271template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1272template <class _InputIterator>
1273unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1274 _InputIterator __first, _InputIterator __last)
1275{
Howard Hinnant39213642013-07-23 22:01:58 +00001276#if _LIBCPP_DEBUG_LEVEL >= 2
1277 __get_db()->__insert_c(this);
1278#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001279 insert(__first, __last);
1280}
1281
1282template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1283template <class _InputIterator>
1284unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1285 _InputIterator __first, _InputIterator __last, size_type __n,
1286 const hasher& __hf, const key_equal& __eql)
1287 : __table_(__hf, __eql)
1288{
Howard Hinnant39213642013-07-23 22:01:58 +00001289#if _LIBCPP_DEBUG_LEVEL >= 2
1290 __get_db()->__insert_c(this);
1291#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001292 __table_.rehash(__n);
1293 insert(__first, __last);
1294}
1295
1296template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1297template <class _InputIterator>
1298unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1299 _InputIterator __first, _InputIterator __last, size_type __n,
1300 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1301 : __table_(__hf, __eql, __a)
1302{
Howard Hinnant39213642013-07-23 22:01:58 +00001303#if _LIBCPP_DEBUG_LEVEL >= 2
1304 __get_db()->__insert_c(this);
1305#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001306 __table_.rehash(__n);
1307 insert(__first, __last);
1308}
1309
1310template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1311unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1312 const unordered_map& __u)
1313 : __table_(__u.__table_)
1314{
Howard Hinnant39213642013-07-23 22:01:58 +00001315#if _LIBCPP_DEBUG_LEVEL >= 2
1316 __get_db()->__insert_c(this);
1317#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001318 __table_.rehash(__u.bucket_count());
1319 insert(__u.begin(), __u.end());
1320}
1321
1322template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1323unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1324 const unordered_map& __u, const allocator_type& __a)
1325 : __table_(__u.__table_, __a)
1326{
Howard Hinnant39213642013-07-23 22:01:58 +00001327#if _LIBCPP_DEBUG_LEVEL >= 2
1328 __get_db()->__insert_c(this);
1329#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001330 __table_.rehash(__u.bucket_count());
1331 insert(__u.begin(), __u.end());
1332}
1333
Howard Hinnant73d21a42010-09-04 23:28:19 +00001334#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001335
1336template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001337inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001338unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1339 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001340 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001341 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001342{
Howard Hinnant39213642013-07-23 22:01:58 +00001343#if _LIBCPP_DEBUG_LEVEL >= 2
1344 __get_db()->__insert_c(this);
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001345 __get_db()->swap(this, &__u);
Howard Hinnant39213642013-07-23 22:01:58 +00001346#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001347}
1348
1349template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1350unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1351 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001352 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001353{
Howard Hinnant39213642013-07-23 22:01:58 +00001354#if _LIBCPP_DEBUG_LEVEL >= 2
1355 __get_db()->__insert_c(this);
1356#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001357 if (__a != __u.get_allocator())
1358 {
1359 iterator __i = __u.begin();
1360 while (__u.size() != 0)
1361 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001362 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001363 );
1364 }
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001365#if _LIBCPP_DEBUG_LEVEL >= 2
1366 else
1367 __get_db()->swap(this, &__u);
1368#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001369}
1370
Howard Hinnant73d21a42010-09-04 23:28:19 +00001371#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001372
Howard Hinnante3e32912011-08-12 21:56:02 +00001373#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1374
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001375template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1376unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1377 initializer_list<value_type> __il)
1378{
Howard Hinnant39213642013-07-23 22:01:58 +00001379#if _LIBCPP_DEBUG_LEVEL >= 2
1380 __get_db()->__insert_c(this);
1381#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001382 insert(__il.begin(), __il.end());
1383}
1384
1385template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1386unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1387 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1388 const key_equal& __eql)
1389 : __table_(__hf, __eql)
1390{
Howard Hinnant39213642013-07-23 22:01:58 +00001391#if _LIBCPP_DEBUG_LEVEL >= 2
1392 __get_db()->__insert_c(this);
1393#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001394 __table_.rehash(__n);
1395 insert(__il.begin(), __il.end());
1396}
1397
1398template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1399unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1400 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1401 const key_equal& __eql, const allocator_type& __a)
1402 : __table_(__hf, __eql, __a)
1403{
Howard Hinnant39213642013-07-23 22:01:58 +00001404#if _LIBCPP_DEBUG_LEVEL >= 2
1405 __get_db()->__insert_c(this);
1406#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001407 __table_.rehash(__n);
1408 insert(__il.begin(), __il.end());
1409}
1410
Howard Hinnante3e32912011-08-12 21:56:02 +00001411#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1412
Howard Hinnant73d21a42010-09-04 23:28:19 +00001413#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001414
1415template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001416inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001417unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1418unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001419 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001420{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001421 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001422 return *this;
1423}
1424
Howard Hinnant73d21a42010-09-04 23:28:19 +00001425#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001426
Howard Hinnante3e32912011-08-12 21:56:02 +00001427#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1428
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001429template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001430inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001431unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1432unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1433 initializer_list<value_type> __il)
1434{
1435 __table_.__assign_unique(__il.begin(), __il.end());
1436 return *this;
1437}
1438
Howard Hinnante3e32912011-08-12 21:56:02 +00001439#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1440
Howard Hinnant73d21a42010-09-04 23:28:19 +00001441#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001442
1443template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001444typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001445unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001446{
1447 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001448 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001449 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001450 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001451 __h.get_deleter().__second_constructed = true;
1452 return __h;
1453}
1454
1455template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001456template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001457typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001458unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1459{
1460 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001461 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001462 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1463 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001464 __h.get_deleter().__first_constructed = true;
1465 __h.get_deleter().__second_constructed = true;
1466 return __h;
1467}
1468
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001469template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001470typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1471unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001472{
1473 __node_allocator& __na = __table_.__node_alloc();
1474 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001475 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001476 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001477 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001478 __h.get_deleter().__second_constructed = true;
Howard Hinnant9a894d92013-08-22 18:29:50 +00001479 return __h;
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001480}
1481
Howard Hinnant73d21a42010-09-04 23:28:19 +00001482#ifndef _LIBCPP_HAS_NO_VARIADICS
1483
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001484template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001485template <class _A0, class _A1, class ..._Args>
1486typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1487unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1488 _A1&& __a1,
1489 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001490{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001491 __node_allocator& __na = __table_.__node_alloc();
1492 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1493 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1494 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1495 _VSTD::forward<_Args>(__args)...);
1496 __h.get_deleter().__first_constructed = true;
1497 __h.get_deleter().__second_constructed = true;
1498 return __h;
1499}
1500
1501template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1502template <class... _Args>
1503pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
Duncan P. N. Exon Smith9f745c82016-01-22 22:48:02 +00001504unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__emplace_impl(_Args&&... __args)
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001505{
1506 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001507 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1508 if (__r.second)
1509 __h.release();
1510 return __r;
1511}
1512
Howard Hinnant73d21a42010-09-04 23:28:19 +00001513#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001514#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001515
1516template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1517typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001518unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001519{
1520 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001521 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001522 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001523 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001524 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001525 __h.get_deleter().__second_constructed = true;
Dimitry Andric89663502015-08-19 06:43:33 +00001526 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001527}
1528
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001529template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1530template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001531inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001532void
1533unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1534 _InputIterator __last)
1535{
1536 for (; __first != __last; ++__first)
1537 __table_.__insert_unique(*__first);
1538}
1539
1540template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1541_Tp&
1542unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1543{
1544 iterator __i = find(__k);
1545 if (__i != end())
1546 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001547 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001548 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1549 __h.release();
1550 return __r.first->second;
1551}
1552
Howard Hinnant73d21a42010-09-04 23:28:19 +00001553#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001554
1555template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1556_Tp&
1557unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1558{
1559 iterator __i = find(__k);
1560 if (__i != end())
1561 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001562 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001563 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1564 __h.release();
1565 return __r.first->second;
1566}
1567
Howard Hinnant73d21a42010-09-04 23:28:19 +00001568#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001569
1570template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1571_Tp&
1572unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1573{
1574 iterator __i = find(__k);
1575#ifndef _LIBCPP_NO_EXCEPTIONS
1576 if (__i == end())
1577 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001578#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001579 return __i->second;
1580}
1581
1582template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1583const _Tp&
1584unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1585{
1586 const_iterator __i = find(__k);
1587#ifndef _LIBCPP_NO_EXCEPTIONS
1588 if (__i == end())
1589 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001590#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001591 return __i->second;
1592}
1593
1594template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001595inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001596void
1597swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1598 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001599 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001600{
1601 __x.swap(__y);
1602}
1603
1604template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1605bool
1606operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1607 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1608{
1609 if (__x.size() != __y.size())
1610 return false;
1611 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1612 const_iterator;
1613 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1614 __i != __ex; ++__i)
1615 {
1616 const_iterator __j = __y.find(__i->first);
1617 if (__j == __ey || !(*__i == *__j))
1618 return false;
1619 }
1620 return true;
1621}
1622
1623template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001624inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001625bool
1626operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1627 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1628{
1629 return !(__x == __y);
1630}
1631
1632template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1633 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant0f678bd2013-08-12 18:38:34 +00001634class _LIBCPP_TYPE_VIS_ONLY unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001635{
1636public:
1637 // types
1638 typedef _Key key_type;
1639 typedef _Tp mapped_type;
1640 typedef _Hash hasher;
1641 typedef _Pred key_equal;
1642 typedef _Alloc allocator_type;
1643 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001644 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001645 typedef value_type& reference;
1646 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +00001647 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1648 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001649
1650private:
Howard Hinnantff7546e2013-09-30 19:08:22 +00001651 typedef __hash_value_type<key_type, mapped_type> __value_type;
Howard Hinnant9b128e02013-07-05 18:06:00 +00001652 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1653 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Marshall Clow66302c62015-04-07 05:21:38 +00001654 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1655 __value_type>::type __allocator_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001656
1657 typedef __hash_table<__value_type, __hasher,
1658 __key_equal, __allocator_type> __table;
1659
1660 __table __table_;
1661
1662 typedef typename __table::__node_traits __node_traits;
1663 typedef typename __table::__node_allocator __node_allocator;
1664 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001665 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1666 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001667 typedef allocator_traits<allocator_type> __alloc_traits;
1668public:
1669 typedef typename __alloc_traits::pointer pointer;
1670 typedef typename __alloc_traits::const_pointer const_pointer;
1671 typedef typename __alloc_traits::size_type size_type;
1672 typedef typename __alloc_traits::difference_type difference_type;
1673
1674 typedef __hash_map_iterator<typename __table::iterator> iterator;
1675 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1676 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1677 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1678
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001679 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001680 unordered_multimap()
1681 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +00001682 {
1683#if _LIBCPP_DEBUG_LEVEL >= 2
1684 __get_db()->__insert_c(this);
1685#endif
1686 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001687 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1688 const key_equal& __eql = key_equal());
1689 unordered_multimap(size_type __n, const hasher& __hf,
1690 const key_equal& __eql,
1691 const allocator_type& __a);
1692 template <class _InputIterator>
1693 unordered_multimap(_InputIterator __first, _InputIterator __last);
1694 template <class _InputIterator>
1695 unordered_multimap(_InputIterator __first, _InputIterator __last,
1696 size_type __n, const hasher& __hf = hasher(),
1697 const key_equal& __eql = key_equal());
1698 template <class _InputIterator>
1699 unordered_multimap(_InputIterator __first, _InputIterator __last,
1700 size_type __n, const hasher& __hf,
1701 const key_equal& __eql,
1702 const allocator_type& __a);
1703 explicit unordered_multimap(const allocator_type& __a);
1704 unordered_multimap(const unordered_multimap& __u);
1705 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001706#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001707 unordered_multimap(unordered_multimap&& __u)
1708 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001709 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001710#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001711#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001712 unordered_multimap(initializer_list<value_type> __il);
1713 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1714 const hasher& __hf = hasher(),
1715 const key_equal& __eql = key_equal());
1716 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1717 const hasher& __hf, const key_equal& __eql,
1718 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001719#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Marshall Clow6dff6182013-09-12 03:00:31 +00001720#if _LIBCPP_STD_VER > 11
1721 _LIBCPP_INLINE_VISIBILITY
1722 unordered_multimap(size_type __n, const allocator_type& __a)
1723 : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1724 _LIBCPP_INLINE_VISIBILITY
1725 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
1726 : unordered_multimap(__n, __hf, key_equal(), __a) {}
1727 template <class _InputIterator>
1728 _LIBCPP_INLINE_VISIBILITY
1729 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
1730 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
1731 template <class _InputIterator>
1732 _LIBCPP_INLINE_VISIBILITY
1733 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf,
1734 const allocator_type& __a)
1735 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
1736 _LIBCPP_INLINE_VISIBILITY
1737 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1738 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
1739 _LIBCPP_INLINE_VISIBILITY
1740 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1741 const allocator_type& __a)
1742 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
1743#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001744 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001745 _LIBCPP_INLINE_VISIBILITY
1746 unordered_multimap& operator=(const unordered_multimap& __u)
1747 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001748#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +00001749 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001750#else
Marshall Clowebfc50e2014-02-08 04:03:14 +00001751 if (this != &__u) {
1752 __table_.clear();
1753 __table_.hash_function() = __u.__table_.hash_function();
1754 __table_.key_eq() = __u.__table_.key_eq();
1755 __table_.max_load_factor() = __u.__table_.max_load_factor();
1756 __table_.__copy_assign_alloc(__u.__table_);
1757 insert(__u.begin(), __u.end());
1758 }
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001759#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +00001760 return *this;
1761 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001762#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001763 unordered_multimap& operator=(unordered_multimap&& __u)
1764 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001765#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001766#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001767 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001768#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001769
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001771 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001772 {return allocator_type(__table_.__node_alloc());}
1773
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001774 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001775 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001776 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001777 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001778 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001779 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001780
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001781 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001782 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001784 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001786 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001788 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001790 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001792 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001793
Howard Hinnant73d21a42010-09-04 23:28:19 +00001794#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +00001795#ifndef _LIBCPP_HAS_NO_VARIADICS
1796
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001797 template <class... _Args>
1798 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001799
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001800 template <class... _Args>
1801 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001802#endif // _LIBCPP_HAS_NO_VARIADICS
1803#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001804 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001805 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001806#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001807 template <class _Pp,
1808 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001809 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001810 iterator insert(_Pp&& __x)
1811 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001812#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001813 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001814 iterator insert(const_iterator __p, const value_type& __x)
1815 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001816#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001817 template <class _Pp,
1818 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001820 iterator insert(const_iterator __p, _Pp&& __x)
1821 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001822#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001823 template <class _InputIterator>
1824 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001825#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001827 void insert(initializer_list<value_type> __il)
1828 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001829#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001830
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001831 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001832 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001833 _LIBCPP_INLINE_VISIBILITY
Marshall Clow488025c2015-05-10 13:35:00 +00001834 iterator erase(iterator __p) {return __table_.erase(__p.__i_);}
1835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001836 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001838 iterator erase(const_iterator __first, const_iterator __last)
1839 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001841 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001842
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001843 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001844 void swap(unordered_multimap& __u)
1845 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1846 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001847
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001849 hasher hash_function() const
1850 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001851 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001852 key_equal key_eq() const
1853 {return __table_.key_eq().key_eq();}
1854
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001855 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001856 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001857 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001858 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001860 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001862 pair<iterator, iterator> equal_range(const key_type& __k)
1863 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001864 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001865 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1866 {return __table_.__equal_range_multi(__k);}
1867
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001869 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001870 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001871 size_type max_bucket_count() const _NOEXCEPT
1872 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001873
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001874 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001875 size_type bucket_size(size_type __n) const
1876 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001877 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001878 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1879
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001880 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001881 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001883 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001885 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001887 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001889 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001890 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001891 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1892
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001893 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001894 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001895 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001896 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001898 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001899 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001900 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001902 void reserve(size_type __n) {__table_.reserve(__n);}
1903
Howard Hinnant39213642013-07-23 22:01:58 +00001904#if _LIBCPP_DEBUG_LEVEL >= 2
1905
1906 bool __dereferenceable(const const_iterator* __i) const
1907 {return __table_.__dereferenceable(&__i->__i_);}
1908 bool __decrementable(const const_iterator* __i) const
1909 {return __table_.__decrementable(&__i->__i_);}
1910 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1911 {return __table_.__addable(&__i->__i_, __n);}
1912 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1913 {return __table_.__addable(&__i->__i_, __n);}
1914
1915#endif // _LIBCPP_DEBUG_LEVEL >= 2
1916
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001917private:
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001918#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1919 __node_holder __construct_node();
1920 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001921 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001922 __construct_node(_A0&& __a0);
1923#ifndef _LIBCPP_HAS_NO_VARIADICS
1924 template <class _A0, class _A1, class ..._Args>
1925 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1926#endif // _LIBCPP_HAS_NO_VARIADICS
1927#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-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 size_type __n, const hasher& __hf, const key_equal& __eql)
1933 : __table_(__hf, __eql)
1934{
Howard Hinnant39213642013-07-23 22:01:58 +00001935#if _LIBCPP_DEBUG_LEVEL >= 2
1936 __get_db()->__insert_c(this);
1937#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001938 __table_.rehash(__n);
1939}
1940
1941template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1942unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1943 size_type __n, const hasher& __hf, const key_equal& __eql,
1944 const allocator_type& __a)
1945 : __table_(__hf, __eql, __a)
1946{
Howard Hinnant39213642013-07-23 22:01:58 +00001947#if _LIBCPP_DEBUG_LEVEL >= 2
1948 __get_db()->__insert_c(this);
1949#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001950 __table_.rehash(__n);
1951}
1952
1953template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1954template <class _InputIterator>
1955unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1956 _InputIterator __first, _InputIterator __last)
1957{
Howard Hinnant39213642013-07-23 22:01:58 +00001958#if _LIBCPP_DEBUG_LEVEL >= 2
1959 __get_db()->__insert_c(this);
1960#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001961 insert(__first, __last);
1962}
1963
1964template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1965template <class _InputIterator>
1966unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1967 _InputIterator __first, _InputIterator __last, size_type __n,
1968 const hasher& __hf, const key_equal& __eql)
1969 : __table_(__hf, __eql)
1970{
Howard Hinnant39213642013-07-23 22:01:58 +00001971#if _LIBCPP_DEBUG_LEVEL >= 2
1972 __get_db()->__insert_c(this);
1973#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001974 __table_.rehash(__n);
1975 insert(__first, __last);
1976}
1977
1978template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1979template <class _InputIterator>
1980unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1981 _InputIterator __first, _InputIterator __last, size_type __n,
1982 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1983 : __table_(__hf, __eql, __a)
1984{
Howard Hinnant39213642013-07-23 22:01:58 +00001985#if _LIBCPP_DEBUG_LEVEL >= 2
1986 __get_db()->__insert_c(this);
1987#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001988 __table_.rehash(__n);
1989 insert(__first, __last);
1990}
1991
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001992template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001993inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001994unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1995 const allocator_type& __a)
1996 : __table_(__a)
1997{
Howard Hinnant39213642013-07-23 22:01:58 +00001998#if _LIBCPP_DEBUG_LEVEL >= 2
1999 __get_db()->__insert_c(this);
2000#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002001}
2002
2003template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2004unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2005 const unordered_multimap& __u)
2006 : __table_(__u.__table_)
2007{
Howard Hinnant39213642013-07-23 22:01:58 +00002008#if _LIBCPP_DEBUG_LEVEL >= 2
2009 __get_db()->__insert_c(this);
2010#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002011 __table_.rehash(__u.bucket_count());
2012 insert(__u.begin(), __u.end());
2013}
2014
2015template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2016unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2017 const unordered_multimap& __u, const allocator_type& __a)
2018 : __table_(__u.__table_, __a)
2019{
Howard Hinnant39213642013-07-23 22:01:58 +00002020#if _LIBCPP_DEBUG_LEVEL >= 2
2021 __get_db()->__insert_c(this);
2022#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002023 __table_.rehash(__u.bucket_count());
2024 insert(__u.begin(), __u.end());
2025}
2026
Howard Hinnant73d21a42010-09-04 23:28:19 +00002027#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002028
2029template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002030inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002031unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2032 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00002033 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00002034 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002035{
Howard Hinnant39213642013-07-23 22:01:58 +00002036#if _LIBCPP_DEBUG_LEVEL >= 2
2037 __get_db()->__insert_c(this);
Howard Hinnantf890d9b2013-07-30 21:04:42 +00002038 __get_db()->swap(this, &__u);
Howard Hinnant39213642013-07-23 22:01:58 +00002039#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002040}
2041
2042template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2043unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2044 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00002045 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002046{
Howard Hinnant39213642013-07-23 22:01:58 +00002047#if _LIBCPP_DEBUG_LEVEL >= 2
2048 __get_db()->__insert_c(this);
2049#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002050 if (__a != __u.get_allocator())
2051 {
2052 iterator __i = __u.begin();
2053 while (__u.size() != 0)
Howard Hinnant39213642013-07-23 22:01:58 +00002054 {
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002055 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00002056 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002057 );
Howard Hinnant39213642013-07-23 22:01:58 +00002058 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002059 }
Howard Hinnantf890d9b2013-07-30 21:04:42 +00002060#if _LIBCPP_DEBUG_LEVEL >= 2
2061 else
2062 __get_db()->swap(this, &__u);
2063#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002064}
2065
Howard Hinnant73d21a42010-09-04 23:28:19 +00002066#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002067
Howard Hinnante3e32912011-08-12 21:56:02 +00002068#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2069
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002070template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2071unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2072 initializer_list<value_type> __il)
2073{
Howard Hinnant39213642013-07-23 22:01:58 +00002074#if _LIBCPP_DEBUG_LEVEL >= 2
2075 __get_db()->__insert_c(this);
2076#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002077 insert(__il.begin(), __il.end());
2078}
2079
2080template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2081unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2082 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2083 const key_equal& __eql)
2084 : __table_(__hf, __eql)
2085{
Howard Hinnant39213642013-07-23 22:01:58 +00002086#if _LIBCPP_DEBUG_LEVEL >= 2
2087 __get_db()->__insert_c(this);
2088#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002089 __table_.rehash(__n);
2090 insert(__il.begin(), __il.end());
2091}
2092
2093template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2094unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2095 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
2096 const key_equal& __eql, const allocator_type& __a)
2097 : __table_(__hf, __eql, __a)
2098{
Howard Hinnant39213642013-07-23 22:01:58 +00002099#if _LIBCPP_DEBUG_LEVEL >= 2
2100 __get_db()->__insert_c(this);
2101#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002102 __table_.rehash(__n);
2103 insert(__il.begin(), __il.end());
2104}
2105
Howard Hinnante3e32912011-08-12 21:56:02 +00002106#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2107
Howard Hinnant73d21a42010-09-04 23:28:19 +00002108#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002109
2110template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002111inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002112unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2113unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00002114 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002115{
Howard Hinnant0949eed2011-06-30 21:18:19 +00002116 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002117 return *this;
2118}
2119
Howard Hinnant73d21a42010-09-04 23:28:19 +00002120#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002121
Howard Hinnante3e32912011-08-12 21:56:02 +00002122#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2123
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002124template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002125inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002126unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2127unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
2128 initializer_list<value_type> __il)
2129{
2130 __table_.__assign_multi(__il.begin(), __il.end());
2131 return *this;
2132}
2133
Howard Hinnante3e32912011-08-12 21:56:02 +00002134#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2135
Howard Hinnant73d21a42010-09-04 23:28:19 +00002136#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002137
2138template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002139typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002140unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002141{
2142 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00002143 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002144 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002145 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002146 __h.get_deleter().__second_constructed = true;
2147 return __h;
2148}
2149
2150template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002151template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00002152typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002153unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
2154{
2155 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00002156 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00002157 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
2158 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002159 __h.get_deleter().__first_constructed = true;
2160 __h.get_deleter().__second_constructed = true;
2161 return __h;
2162}
2163
Howard Hinnant73d21a42010-09-04 23:28:19 +00002164#ifndef _LIBCPP_HAS_NO_VARIADICS
2165
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002166template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002167template <class _A0, class _A1, class ..._Args>
2168typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
2169unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
2170 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002171{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002172 __node_allocator& __na = __table_.__node_alloc();
2173 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2174 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
2175 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
2176 _VSTD::forward<_Args>(__args)...);
2177 __h.get_deleter().__first_constructed = true;
2178 __h.get_deleter().__second_constructed = true;
2179 return __h;
2180}
2181
2182template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2183template <class... _Args>
2184typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2185unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
2186{
2187 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002188 iterator __r = __table_.__node_insert_multi(__h.get());
2189 __h.release();
2190 return __r;
2191}
2192
2193template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002194template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002195typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
2196unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002197 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002198{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00002199 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002200 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
2201 __h.release();
2202 return __r;
2203}
2204
Howard Hinnant73d21a42010-09-04 23:28:19 +00002205#endif // _LIBCPP_HAS_NO_VARIADICS
2206#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002207
2208template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2209template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002210inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002211void
2212unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
2213 _InputIterator __last)
2214{
2215 for (; __first != __last; ++__first)
2216 __table_.__insert_multi(*__first);
2217}
2218
2219template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002220inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002221void
2222swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2223 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00002224 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002225{
2226 __x.swap(__y);
2227}
2228
2229template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2230bool
2231operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2232 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2233{
2234 if (__x.size() != __y.size())
2235 return false;
2236 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
2237 const_iterator;
2238 typedef pair<const_iterator, const_iterator> _EqRng;
2239 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
2240 {
2241 _EqRng __xeq = __x.equal_range(__i->first);
2242 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00002243 if (_VSTD::distance(__xeq.first, __xeq.second) !=
2244 _VSTD::distance(__yeq.first, __yeq.second) ||
2245 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002246 return false;
2247 __i = __xeq.second;
2248 }
2249 return true;
2250}
2251
2252template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002253inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002254bool
2255operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2256 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2257{
2258 return !(__x == __y);
2259}
2260
2261_LIBCPP_END_NAMESPACE_STD
2262
2263#endif // _LIBCPP_UNORDERED_MAP