blob: 55db2f5f584c1aae764a218141025aded632e2ae [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());
72 ~unordered_map();
73 unordered_map& operator=(const unordered_map&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000074 unordered_map& operator=(unordered_map&&)
75 noexcept(
76 allocator_type::propagate_on_container_move_assignment::value &&
77 is_nothrow_move_assignable<allocator_type>::value &&
78 is_nothrow_move_assignable<hasher>::value &&
79 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000080 unordered_map& operator=(initializer_list<value_type>);
81
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000082 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000083
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000084 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000087
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000088 iterator begin() noexcept;
89 iterator end() noexcept;
90 const_iterator begin() const noexcept;
91 const_iterator end() const noexcept;
92 const_iterator cbegin() const noexcept;
93 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000094
95 template <class... Args>
96 pair<iterator, bool> emplace(Args&&... args);
97 template <class... Args>
98 iterator emplace_hint(const_iterator position, Args&&... args);
99 pair<iterator, bool> insert(const value_type& obj);
100 template <class P>
101 pair<iterator, bool> insert(P&& obj);
102 iterator insert(const_iterator hint, const value_type& obj);
103 template <class P>
104 iterator insert(const_iterator hint, P&& obj);
105 template <class InputIterator>
106 void insert(InputIterator first, InputIterator last);
107 void insert(initializer_list<value_type>);
108
109 iterator erase(const_iterator position);
110 size_type erase(const key_type& k);
111 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000112 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000113
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000114 void swap(unordered_map&)
115 noexcept(
116 (!allocator_type::propagate_on_container_swap::value ||
117 __is_nothrow_swappable<allocator_type>::value) &&
118 __is_nothrow_swappable<hasher>::value &&
119 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
121 hasher hash_function() const;
122 key_equal key_eq() const;
123
124 iterator find(const key_type& k);
125 const_iterator find(const key_type& k) const;
126 size_type count(const key_type& k) const;
127 pair<iterator, iterator> equal_range(const key_type& k);
128 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
129
130 mapped_type& operator[](const key_type& k);
131 mapped_type& operator[](key_type&& k);
132
133 mapped_type& at(const key_type& k);
134 const mapped_type& at(const key_type& k) const;
135
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
141
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
148
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
154};
155
156template <class Key, class T, class Hash, class Pred, class Alloc>
157 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000160
161template <class Key, class T, class Hash, class Pred, class Alloc>
162 bool
163 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
164 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
165
166template <class Key, class T, class Hash, class Pred, class Alloc>
167 bool
168 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
169 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
170
171template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
172 class Alloc = allocator<pair<const Key, T>>>
173class unordered_multimap
174{
175public:
176 // types
177 typedef Key key_type;
178 typedef T mapped_type;
179 typedef Hash hasher;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef pair<const key_type, mapped_type> value_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
194
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000195 unordered_multimap()
196 noexcept(
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multimap(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multimap(const allocator_type&);
209 unordered_multimap(const unordered_multimap&);
210 unordered_multimap(const unordered_multimap&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000211 unordered_multimap(unordered_multimap&&)
212 noexcept(
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216 unordered_multimap(unordered_multimap&&, const Allocator&);
217 unordered_multimap(initializer_list<value_type>, size_type n = 0,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
220 ~unordered_multimap();
221 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000222 unordered_multimap& operator=(unordered_multimap&&)
223 noexcept(
224 allocator_type::propagate_on_container_move_assignment::value &&
225 is_nothrow_move_assignable<allocator_type>::value &&
226 is_nothrow_move_assignable<hasher>::value &&
227 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000228 unordered_multimap& operator=(initializer_list<value_type>);
229
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000230 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000231
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000236 iterator begin() noexcept;
237 iterator end() noexcept;
238 const_iterator begin() const noexcept;
239 const_iterator end() const noexcept;
240 const_iterator cbegin() const noexcept;
241 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000242
243 template <class... Args>
244 iterator emplace(Args&&... args);
245 template <class... Args>
246 iterator emplace_hint(const_iterator position, Args&&... args);
247 iterator insert(const value_type& obj);
248 template <class P>
249 iterator insert(P&& obj);
250 iterator insert(const_iterator hint, const value_type& obj);
251 template <class P>
252 iterator insert(const_iterator hint, P&& obj);
253 template <class InputIterator>
254 void insert(InputIterator first, InputIterator last);
255 void insert(initializer_list<value_type>);
256
257 iterator erase(const_iterator position);
258 size_type erase(const key_type& k);
259 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000260 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000261
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000262 void swap(unordered_multimap&)
263 noexcept(
264 (!allocator_type::propagate_on_container_swap::value ||
265 __is_nothrow_swappable<allocator_type>::value) &&
266 __is_nothrow_swappable<hasher>::value &&
267 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000268
269 hasher hash_function() const;
270 key_equal key_eq() const;
271
272 iterator find(const key_type& k);
273 const_iterator find(const key_type& k) const;
274 size_type count(const key_type& k) const;
275 pair<iterator, iterator> equal_range(const key_type& k);
276 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
277
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000280
281 size_type bucket_size(size_type n) const;
282 size_type bucket(const key_type& k) const;
283
284 local_iterator begin(size_type n);
285 local_iterator end(size_type n);
286 const_local_iterator begin(size_type n) const;
287 const_local_iterator end(size_type n) const;
288 const_local_iterator cbegin(size_type n) const;
289 const_local_iterator cend(size_type n) const;
290
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000293 void max_load_factor(float z);
294 void rehash(size_type n);
295 void reserve(size_type n);
296};
297
298template <class Key, class T, class Hash, class Pred, class Alloc>
299 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302
303template <class Key, class T, class Hash, class Pred, class Alloc>
304 bool
305 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
306 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
307
308template <class Key, class T, class Hash, class Pred, class Alloc>
309 bool
310 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
311 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
312
313} // std
314
315*/
316
317#include <__config>
318#include <__hash_table>
319#include <functional>
320#include <stdexcept>
321
Howard Hinnant08e17472011-10-17 20:05:10 +0000322#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000323#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000324#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000325
326_LIBCPP_BEGIN_NAMESPACE_STD
327
Howard Hinnant9b128e02013-07-05 18:06:00 +0000328template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000329#if __has_feature(is_final)
330 && !__is_final(_Hash)
331#endif
332 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000333class __unordered_map_hasher
334 : private _Hash
335{
336public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000337 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000338 __unordered_map_hasher()
339 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
340 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000342 __unordered_map_hasher(const _Hash& __h)
343 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
344 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000345 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000346 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000347 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000348 size_t operator()(const _Cp& __x) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000349 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000350 _LIBCPP_INLINE_VISIBILITY
351 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000352 {return static_cast<const _Hash&>(*this)(__x);}
353};
354
Howard Hinnant9b128e02013-07-05 18:06:00 +0000355template <class _Key, class _Cp, class _Hash>
356class __unordered_map_hasher<_Key, _Cp, _Hash, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000357{
358 _Hash __hash_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000359
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000360public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000361 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000362 __unordered_map_hasher()
363 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
364 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000365 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000366 __unordered_map_hasher(const _Hash& __h)
367 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
368 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000369 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000370 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000371 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000372 size_t operator()(const _Cp& __x) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000373 {return __hash_(__x.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000374 _LIBCPP_INLINE_VISIBILITY
375 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000376 {return __hash_(__x);}
377};
378
Howard Hinnant9b128e02013-07-05 18:06:00 +0000379template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000380#if __has_feature(is_final)
381 && !__is_final(_Pred)
382#endif
383 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000384class __unordered_map_equal
385 : private _Pred
386{
387public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000388 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000389 __unordered_map_equal()
390 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
391 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000393 __unordered_map_equal(const _Pred& __p)
394 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
395 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000397 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000398 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000399 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000400 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000401 _LIBCPP_INLINE_VISIBILITY
402 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000403 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000405 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000406 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000407};
408
Howard Hinnant9b128e02013-07-05 18:06:00 +0000409template <class _Key, class _Cp, class _Pred>
410class __unordered_map_equal<_Key, _Cp, _Pred, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000411{
412 _Pred __pred_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000413
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000414public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000416 __unordered_map_equal()
417 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
418 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000420 __unordered_map_equal(const _Pred& __p)
421 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
422 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000424 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000426 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000427 {return __pred_(__x.__cc.first, __y.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000428 _LIBCPP_INLINE_VISIBILITY
429 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000430 {return __pred_(__x.__cc.first, __y);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000431 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000432 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000433 {return __pred_(__x, __y.__cc.first);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000434};
435
436template <class _Alloc>
437class __hash_map_node_destructor
438{
439 typedef _Alloc allocator_type;
440 typedef allocator_traits<allocator_type> __alloc_traits;
441 typedef typename __alloc_traits::value_type::value_type value_type;
442public:
443 typedef typename __alloc_traits::pointer pointer;
444private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000445 typedef typename value_type::value_type::first_type first_type;
446 typedef typename value_type::value_type::second_type second_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000447
448 allocator_type& __na_;
449
450 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
451
452public:
453 bool __first_constructed;
454 bool __second_constructed;
455
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000456 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000457 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000458 : __na_(__na),
459 __first_constructed(false),
460 __second_constructed(false)
461 {}
462
Howard Hinnant73d21a42010-09-04 23:28:19 +0000463#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000464 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000465 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000466 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000467 : __na_(__x.__na_),
468 __first_constructed(__x.__value_constructed),
469 __second_constructed(__x.__value_constructed)
470 {
471 __x.__value_constructed = false;
472 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000473#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000474 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000475 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
476 : __na_(__x.__na_),
477 __first_constructed(__x.__value_constructed),
478 __second_constructed(__x.__value_constructed)
479 {
480 const_cast<bool&>(__x.__value_constructed) = false;
481 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000482#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000483
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000484 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000485 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000486 {
487 if (__second_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000488 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489 if (__first_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000490 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000491 if (__p)
492 __alloc_traits::deallocate(__na_, __p, 1);
493 }
494};
495
496template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000497class _LIBCPP_TYPE_VIS __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000498{
499 _HashIterator __i_;
500
501 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000502 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
503 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000504public:
505 typedef forward_iterator_tag iterator_category;
506 typedef pair<key_type, mapped_type> value_type;
507 typedef typename _HashIterator::difference_type difference_type;
508 typedef value_type& reference;
509 typedef typename __pointer_traits::template
510#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
511 rebind<value_type>
512#else
513 rebind<value_type>::other
514#endif
515 pointer;
516
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000517 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000518 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000519
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000520 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000521 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000522
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000524 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000526 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000528 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000529 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000531 __hash_map_iterator operator++(int)
532 {
533 __hash_map_iterator __t(*this);
534 ++(*this);
535 return __t;
536 }
537
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000538 friend _LIBCPP_INLINE_VISIBILITY
539 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000540 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000541 friend _LIBCPP_INLINE_VISIBILITY
542 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000543 {return __x.__i_ != __y.__i_;}
544
Howard Hinnant83eade62013-03-06 23:30:19 +0000545 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
546 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
547 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
548 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
549 template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000550};
551
552template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000553class _LIBCPP_TYPE_VIS __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000554{
555 _HashIterator __i_;
556
557 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000558 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
559 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000560public:
561 typedef forward_iterator_tag iterator_category;
562 typedef pair<key_type, mapped_type> value_type;
563 typedef typename _HashIterator::difference_type difference_type;
564 typedef const value_type& reference;
565 typedef typename __pointer_traits::template
566#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000567 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000569 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000570#endif
571 pointer;
572
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000574 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000575
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000577 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000579 __hash_map_const_iterator(
580 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000581 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000582 : __i_(__i.__i_) {}
583
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000585 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000586 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000587 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000588
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000590 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000592 __hash_map_const_iterator operator++(int)
593 {
594 __hash_map_const_iterator __t(*this);
595 ++(*this);
596 return __t;
597 }
598
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000599 friend _LIBCPP_INLINE_VISIBILITY
600 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000601 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000602 friend _LIBCPP_INLINE_VISIBILITY
603 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000604 {return __x.__i_ != __y.__i_;}
605
Howard Hinnant83eade62013-03-06 23:30:19 +0000606 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
607 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
608 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
609 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000610};
611
612template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
613 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +0000614class _LIBCPP_TYPE_VIS unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000615{
616public:
617 // types
618 typedef _Key key_type;
619 typedef _Tp mapped_type;
620 typedef _Hash hasher;
621 typedef _Pred key_equal;
622 typedef _Alloc allocator_type;
623 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000624 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000625 typedef value_type& reference;
626 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +0000627 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
628 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000629
630private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000631#if __cplusplus >= 201103L
632 union __value_type
633 {
634 typedef typename unordered_map::value_type value_type;
635 typedef typename unordered_map::__nc_value_type __nc_value_type;
636 value_type __cc;
637 __nc_value_type __nc;
638
639 template <class ..._Args>
640 __value_type(_Args&& ...__args)
641 : __cc(std::forward<_Args>(__args)...) {}
642
643 __value_type(const __value_type& __v)
644 : __cc(std::move(__v.__cc)) {}
645
646 __value_type(__value_type&& __v)
647 : __nc(std::move(__v.__nc)) {}
648
649 __value_type& operator=(const __value_type& __v)
650 {__nc = __v.__cc; return *this;}
651
652 __value_type& operator=(__value_type&& __v)
653 {__nc = std::move(__v.__nc); return *this;}
654
655 ~__value_type() {__cc.~value_type();}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000656 };
657#else
658 struct __value_type
659 {
660 typedef typename unordered_map::value_type value_type;
661 value_type __cc;
662
663 __value_type() {}
664
665 template <class _A0>
666 __value_type(const _A0& __a0)
667 : __cc(__a0) {}
668
669 template <class _A0, class _A1>
670 __value_type(const _A0& __a0, const _A1& __a1)
671 : __cc(__a0, __a1) {}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000672 };
673#endif
Howard Hinnant9b128e02013-07-05 18:06:00 +0000674 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
675 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000676 typedef typename allocator_traits<allocator_type>::template
677#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
678 rebind_alloc<__value_type>
679#else
680 rebind_alloc<__value_type>::other
681#endif
682 __allocator_type;
683
684 typedef __hash_table<__value_type, __hasher,
685 __key_equal, __allocator_type> __table;
686
687 __table __table_;
688
689 typedef typename __table::__node_pointer __node_pointer;
690 typedef typename __table::__node_const_pointer __node_const_pointer;
691 typedef typename __table::__node_traits __node_traits;
692 typedef typename __table::__node_allocator __node_allocator;
693 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +0000694 typedef __hash_map_node_destructor<__node_allocator> _Dp;
695 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000696 typedef allocator_traits<allocator_type> __alloc_traits;
697public:
698 typedef typename __alloc_traits::pointer pointer;
699 typedef typename __alloc_traits::const_pointer const_pointer;
700 typedef typename __alloc_traits::size_type size_type;
701 typedef typename __alloc_traits::difference_type difference_type;
702
703 typedef __hash_map_iterator<typename __table::iterator> iterator;
704 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
705 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
706 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
707
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000708 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000709 unordered_map()
710 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +0000711 {
712#if _LIBCPP_DEBUG_LEVEL >= 2
713 __get_db()->__insert_c(this);
714#endif
715 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000716 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
717 const key_equal& __eql = key_equal());
718 unordered_map(size_type __n, const hasher& __hf,
719 const key_equal& __eql,
720 const allocator_type& __a);
721 template <class _InputIterator>
722 unordered_map(_InputIterator __first, _InputIterator __last);
723 template <class _InputIterator>
724 unordered_map(_InputIterator __first, _InputIterator __last,
725 size_type __n, const hasher& __hf = hasher(),
726 const key_equal& __eql = key_equal());
727 template <class _InputIterator>
728 unordered_map(_InputIterator __first, _InputIterator __last,
729 size_type __n, const hasher& __hf,
730 const key_equal& __eql,
731 const allocator_type& __a);
732 explicit unordered_map(const allocator_type& __a);
733 unordered_map(const unordered_map& __u);
734 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000735#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000736 unordered_map(unordered_map&& __u)
737 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000738 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000739#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000740#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000741 unordered_map(initializer_list<value_type> __il);
742 unordered_map(initializer_list<value_type> __il, size_type __n,
743 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
744 unordered_map(initializer_list<value_type> __il, size_type __n,
745 const hasher& __hf, const key_equal& __eql,
746 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000747#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000748 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000749 _LIBCPP_INLINE_VISIBILITY
750 unordered_map& operator=(const unordered_map& __u)
751 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000752#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +0000753 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000754#else
755 __table_.clear();
756 __table_.hash_function() = __u.__table_.hash_function();
757 __table_.key_eq() = __u.__table_.key_eq();
758 __table_.max_load_factor() = __u.__table_.max_load_factor();
759 __table_.__copy_assign_alloc(__u.__table_);
760 insert(__u.begin(), __u.end());
761#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +0000762 return *this;
763 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000764#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000765 unordered_map& operator=(unordered_map&& __u)
766 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000767#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000768#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000769 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000770#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000771
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000772 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000773 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000774 {return allocator_type(__table_.__node_alloc());}
775
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000776 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000777 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000778 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000779 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000781 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000782
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000784 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000786 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000788 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000790 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000792 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000794 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000795
Howard Hinnant73d21a42010-09-04 23:28:19 +0000796#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +0000797#ifndef _LIBCPP_HAS_NO_VARIADICS
798
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000799 template <class... _Args>
800 pair<iterator, bool> emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000801
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000802 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000804 iterator emplace_hint(const_iterator, _Args&&... __args)
805 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000806#endif // _LIBCPP_HAS_NO_VARIADICS
807#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000808 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000809 pair<iterator, bool> insert(const value_type& __x)
810 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000811#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000812 template <class _Pp,
813 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000814 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000815 pair<iterator, bool> insert(_Pp&& __x)
816 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000817#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000819 iterator insert(const_iterator, const value_type& __x)
820 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000821#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000822 template <class _Pp,
823 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000824 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000825 iterator insert(const_iterator, _Pp&& __x)
826 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000827#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000828 template <class _InputIterator>
829 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000830#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000831 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000832 void insert(initializer_list<value_type> __il)
833 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000834#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000835
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000836 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000837 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000839 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000841 iterator erase(const_iterator __first, const_iterator __last)
842 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000843 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000844 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000845
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000846 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000847 void swap(unordered_map& __u)
848 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
849 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000850
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000851 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000852 hasher hash_function() const
853 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000855 key_equal key_eq() const
856 {return __table_.key_eq().key_eq();}
857
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000858 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000859 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000860 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000861 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000863 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000864 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000865 pair<iterator, iterator> equal_range(const key_type& __k)
866 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000867 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000868 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
869 {return __table_.__equal_range_unique(__k);}
870
871 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000872#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000873 mapped_type& operator[](key_type&& __k);
874#endif
875
876 mapped_type& at(const key_type& __k);
877 const mapped_type& at(const key_type& __k) const;
878
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000880 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000881 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000882 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000883
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000885 size_type bucket_size(size_type __n) const
886 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000887 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000888 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
889
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000890 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000891 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000893 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000895 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000896 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000897 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000898 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000899 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000900 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000901 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
902
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000904 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000906 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000907 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000908 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000909 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000910 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000911 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000912 void reserve(size_type __n) {__table_.reserve(__n);}
913
Howard Hinnant39213642013-07-23 22:01:58 +0000914#if _LIBCPP_DEBUG_LEVEL >= 2
915
916 bool __dereferenceable(const const_iterator* __i) const
917 {return __table_.__dereferenceable(&__i->__i_);}
918 bool __decrementable(const const_iterator* __i) const
919 {return __table_.__decrementable(&__i->__i_);}
920 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
921 {return __table_.__addable(&__i->__i_, __n);}
922 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
923 {return __table_.__addable(&__i->__i_, __n);}
924
925#endif // _LIBCPP_DEBUG_LEVEL >= 2
926
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000927private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000928#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000929 __node_holder __construct_node();
930 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000931 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000932 __construct_node(_A0&& __a0);
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000933 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000934#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000935 template <class _A0, class _A1, class ..._Args>
936 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000937#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000938#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
939 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000940};
941
942template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
943unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
944 size_type __n, const hasher& __hf, const key_equal& __eql)
945 : __table_(__hf, __eql)
946{
Howard Hinnant39213642013-07-23 22:01:58 +0000947#if _LIBCPP_DEBUG_LEVEL >= 2
948 __get_db()->__insert_c(this);
949#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000950 __table_.rehash(__n);
951}
952
953template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
954unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
955 size_type __n, const hasher& __hf, const key_equal& __eql,
956 const allocator_type& __a)
957 : __table_(__hf, __eql, __a)
958{
Howard Hinnant39213642013-07-23 22:01:58 +0000959#if _LIBCPP_DEBUG_LEVEL >= 2
960 __get_db()->__insert_c(this);
961#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000962 __table_.rehash(__n);
963}
964
965template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000966inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000967unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
968 const allocator_type& __a)
969 : __table_(__a)
970{
Howard Hinnant39213642013-07-23 22:01:58 +0000971#if _LIBCPP_DEBUG_LEVEL >= 2
972 __get_db()->__insert_c(this);
973#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000974}
975
976template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
977template <class _InputIterator>
978unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
979 _InputIterator __first, _InputIterator __last)
980{
Howard Hinnant39213642013-07-23 22:01:58 +0000981#if _LIBCPP_DEBUG_LEVEL >= 2
982 __get_db()->__insert_c(this);
983#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000984 insert(__first, __last);
985}
986
987template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
988template <class _InputIterator>
989unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
990 _InputIterator __first, _InputIterator __last, size_type __n,
991 const hasher& __hf, const key_equal& __eql)
992 : __table_(__hf, __eql)
993{
Howard Hinnant39213642013-07-23 22:01:58 +0000994#if _LIBCPP_DEBUG_LEVEL >= 2
995 __get_db()->__insert_c(this);
996#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000997 __table_.rehash(__n);
998 insert(__first, __last);
999}
1000
1001template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1002template <class _InputIterator>
1003unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1004 _InputIterator __first, _InputIterator __last, size_type __n,
1005 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1006 : __table_(__hf, __eql, __a)
1007{
Howard Hinnant39213642013-07-23 22:01:58 +00001008#if _LIBCPP_DEBUG_LEVEL >= 2
1009 __get_db()->__insert_c(this);
1010#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001011 __table_.rehash(__n);
1012 insert(__first, __last);
1013}
1014
1015template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1016unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1017 const unordered_map& __u)
1018 : __table_(__u.__table_)
1019{
Howard Hinnant39213642013-07-23 22:01:58 +00001020#if _LIBCPP_DEBUG_LEVEL >= 2
1021 __get_db()->__insert_c(this);
1022#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001023 __table_.rehash(__u.bucket_count());
1024 insert(__u.begin(), __u.end());
1025}
1026
1027template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1028unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1029 const unordered_map& __u, const allocator_type& __a)
1030 : __table_(__u.__table_, __a)
1031{
Howard Hinnant39213642013-07-23 22:01:58 +00001032#if _LIBCPP_DEBUG_LEVEL >= 2
1033 __get_db()->__insert_c(this);
1034#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001035 __table_.rehash(__u.bucket_count());
1036 insert(__u.begin(), __u.end());
1037}
1038
Howard Hinnant73d21a42010-09-04 23:28:19 +00001039#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001040
1041template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001042inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001043unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1044 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001045 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001046 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001047{
Howard Hinnant39213642013-07-23 22:01:58 +00001048#if _LIBCPP_DEBUG_LEVEL >= 2
1049 __get_db()->__insert_c(this);
1050#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001051}
1052
1053template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1054unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1055 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001056 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001057{
Howard Hinnant39213642013-07-23 22:01:58 +00001058#if _LIBCPP_DEBUG_LEVEL >= 2
1059 __get_db()->__insert_c(this);
1060#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001061 if (__a != __u.get_allocator())
1062 {
1063 iterator __i = __u.begin();
1064 while (__u.size() != 0)
1065 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001066 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001067 );
1068 }
1069}
1070
Howard Hinnant73d21a42010-09-04 23:28:19 +00001071#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001072
Howard Hinnante3e32912011-08-12 21:56:02 +00001073#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1074
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001075template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1076unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1077 initializer_list<value_type> __il)
1078{
Howard Hinnant39213642013-07-23 22:01:58 +00001079#if _LIBCPP_DEBUG_LEVEL >= 2
1080 __get_db()->__insert_c(this);
1081#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001082 insert(__il.begin(), __il.end());
1083}
1084
1085template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1086unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1087 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1088 const key_equal& __eql)
1089 : __table_(__hf, __eql)
1090{
Howard Hinnant39213642013-07-23 22:01:58 +00001091#if _LIBCPP_DEBUG_LEVEL >= 2
1092 __get_db()->__insert_c(this);
1093#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001094 __table_.rehash(__n);
1095 insert(__il.begin(), __il.end());
1096}
1097
1098template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1099unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1100 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1101 const key_equal& __eql, const allocator_type& __a)
1102 : __table_(__hf, __eql, __a)
1103{
Howard Hinnant39213642013-07-23 22:01:58 +00001104#if _LIBCPP_DEBUG_LEVEL >= 2
1105 __get_db()->__insert_c(this);
1106#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001107 __table_.rehash(__n);
1108 insert(__il.begin(), __il.end());
1109}
1110
Howard Hinnante3e32912011-08-12 21:56:02 +00001111#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1112
Howard Hinnant73d21a42010-09-04 23:28:19 +00001113#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001114
1115template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001116inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001117unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1118unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001119 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001120{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001121 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001122 return *this;
1123}
1124
Howard Hinnant73d21a42010-09-04 23:28:19 +00001125#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001126
Howard Hinnante3e32912011-08-12 21:56:02 +00001127#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1128
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001129template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001130inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001131unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1132unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1133 initializer_list<value_type> __il)
1134{
1135 __table_.__assign_unique(__il.begin(), __il.end());
1136 return *this;
1137}
1138
Howard Hinnante3e32912011-08-12 21:56:02 +00001139#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1140
Howard Hinnant73d21a42010-09-04 23:28:19 +00001141#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001142
1143template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001144typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001145unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001146{
1147 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001148 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001149 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001150 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001151 __h.get_deleter().__second_constructed = true;
1152 return __h;
1153}
1154
1155template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001156template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001157typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001158unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1159{
1160 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001161 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001162 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1163 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001164 __h.get_deleter().__first_constructed = true;
1165 __h.get_deleter().__second_constructed = true;
1166 return __h;
1167}
1168
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001169template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001170typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1171unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001172{
1173 __node_allocator& __na = __table_.__node_alloc();
1174 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001175 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001176 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001177 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001178 __h.get_deleter().__second_constructed = true;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001179 return _VSTD::move(__h);
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001180}
1181
Howard Hinnant73d21a42010-09-04 23:28:19 +00001182#ifndef _LIBCPP_HAS_NO_VARIADICS
1183
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001184template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001185template <class _A0, class _A1, class ..._Args>
1186typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1187unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1188 _A1&& __a1,
1189 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001190{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001191 __node_allocator& __na = __table_.__node_alloc();
1192 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1193 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1194 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1195 _VSTD::forward<_Args>(__args)...);
1196 __h.get_deleter().__first_constructed = true;
1197 __h.get_deleter().__second_constructed = true;
1198 return __h;
1199}
1200
1201template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1202template <class... _Args>
1203pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1204unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1205{
1206 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001207 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1208 if (__r.second)
1209 __h.release();
1210 return __r;
1211}
1212
Howard Hinnant73d21a42010-09-04 23:28:19 +00001213#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001214#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001215
1216template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1217typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001218unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001219{
1220 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001221 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001222 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001223 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001224 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001225 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001226 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001227}
1228
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001229template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1230template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001231inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001232void
1233unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1234 _InputIterator __last)
1235{
1236 for (; __first != __last; ++__first)
1237 __table_.__insert_unique(*__first);
1238}
1239
1240template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1241_Tp&
1242unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1243{
1244 iterator __i = find(__k);
1245 if (__i != end())
1246 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001247 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001248 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1249 __h.release();
1250 return __r.first->second;
1251}
1252
Howard Hinnant73d21a42010-09-04 23:28:19 +00001253#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001254
1255template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1256_Tp&
1257unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1258{
1259 iterator __i = find(__k);
1260 if (__i != end())
1261 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001262 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001263 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1264 __h.release();
1265 return __r.first->second;
1266}
1267
Howard Hinnant73d21a42010-09-04 23:28:19 +00001268#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001269
1270template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1271_Tp&
1272unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1273{
1274 iterator __i = find(__k);
1275#ifndef _LIBCPP_NO_EXCEPTIONS
1276 if (__i == end())
1277 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001278#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001279 return __i->second;
1280}
1281
1282template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1283const _Tp&
1284unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1285{
1286 const_iterator __i = find(__k);
1287#ifndef _LIBCPP_NO_EXCEPTIONS
1288 if (__i == end())
1289 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001290#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001291 return __i->second;
1292}
1293
1294template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001295inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001296void
1297swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1298 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001299 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001300{
1301 __x.swap(__y);
1302}
1303
1304template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1305bool
1306operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1307 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1308{
1309 if (__x.size() != __y.size())
1310 return false;
1311 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1312 const_iterator;
1313 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1314 __i != __ex; ++__i)
1315 {
1316 const_iterator __j = __y.find(__i->first);
1317 if (__j == __ey || !(*__i == *__j))
1318 return false;
1319 }
1320 return true;
1321}
1322
1323template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001324inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001325bool
1326operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1327 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1328{
1329 return !(__x == __y);
1330}
1331
1332template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1333 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +00001334class _LIBCPP_TYPE_VIS unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001335{
1336public:
1337 // types
1338 typedef _Key key_type;
1339 typedef _Tp mapped_type;
1340 typedef _Hash hasher;
1341 typedef _Pred key_equal;
1342 typedef _Alloc allocator_type;
1343 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001344 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001345 typedef value_type& reference;
1346 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +00001347 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1348 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001349
1350private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001351#if __cplusplus >= 201103L
1352 union __value_type
1353 {
1354 typedef typename unordered_multimap::value_type value_type;
1355 typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1356 value_type __cc;
1357 __nc_value_type __nc;
1358
1359 template <class ..._Args>
1360 __value_type(_Args&& ...__args)
1361 : __cc(std::forward<_Args>(__args)...) {}
1362
1363 __value_type(const __value_type& __v)
1364 : __cc(std::move(__v.__cc)) {}
1365
1366 __value_type(__value_type&& __v)
1367 : __nc(std::move(__v.__nc)) {}
1368
1369 __value_type& operator=(const __value_type& __v)
1370 {__nc = __v.__cc; return *this;}
1371
1372 __value_type& operator=(__value_type&& __v)
1373 {__nc = std::move(__v.__nc); return *this;}
1374
1375 ~__value_type() {__cc.~value_type();}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001376 };
1377#else
1378 struct __value_type
1379 {
1380 typedef typename unordered_multimap::value_type value_type;
1381 value_type __cc;
1382
1383 __value_type() {}
1384
1385 template <class _A0>
1386 __value_type(const _A0& __a0)
1387 : __cc(__a0) {}
1388
1389 template <class _A0, class _A1>
1390 __value_type(const _A0& __a0, const _A1& __a1)
1391 : __cc(__a0, __a1) {}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001392 };
1393#endif
Howard Hinnant9b128e02013-07-05 18:06:00 +00001394 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1395 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001396 typedef typename allocator_traits<allocator_type>::template
1397#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1398 rebind_alloc<__value_type>
1399#else
1400 rebind_alloc<__value_type>::other
1401#endif
1402 __allocator_type;
1403
1404 typedef __hash_table<__value_type, __hasher,
1405 __key_equal, __allocator_type> __table;
1406
1407 __table __table_;
1408
1409 typedef typename __table::__node_traits __node_traits;
1410 typedef typename __table::__node_allocator __node_allocator;
1411 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001412 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1413 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001414 typedef allocator_traits<allocator_type> __alloc_traits;
1415public:
1416 typedef typename __alloc_traits::pointer pointer;
1417 typedef typename __alloc_traits::const_pointer const_pointer;
1418 typedef typename __alloc_traits::size_type size_type;
1419 typedef typename __alloc_traits::difference_type difference_type;
1420
1421 typedef __hash_map_iterator<typename __table::iterator> iterator;
1422 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1423 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1424 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1425
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001427 unordered_multimap()
1428 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +00001429 {
1430#if _LIBCPP_DEBUG_LEVEL >= 2
1431 __get_db()->__insert_c(this);
1432#endif
1433 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001434 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1435 const key_equal& __eql = key_equal());
1436 unordered_multimap(size_type __n, const hasher& __hf,
1437 const key_equal& __eql,
1438 const allocator_type& __a);
1439 template <class _InputIterator>
1440 unordered_multimap(_InputIterator __first, _InputIterator __last);
1441 template <class _InputIterator>
1442 unordered_multimap(_InputIterator __first, _InputIterator __last,
1443 size_type __n, const hasher& __hf = hasher(),
1444 const key_equal& __eql = key_equal());
1445 template <class _InputIterator>
1446 unordered_multimap(_InputIterator __first, _InputIterator __last,
1447 size_type __n, const hasher& __hf,
1448 const key_equal& __eql,
1449 const allocator_type& __a);
1450 explicit unordered_multimap(const allocator_type& __a);
1451 unordered_multimap(const unordered_multimap& __u);
1452 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001453#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001454 unordered_multimap(unordered_multimap&& __u)
1455 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001456 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001457#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001458#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001459 unordered_multimap(initializer_list<value_type> __il);
1460 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1461 const hasher& __hf = hasher(),
1462 const key_equal& __eql = key_equal());
1463 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1464 const hasher& __hf, const key_equal& __eql,
1465 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001466#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001467 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001468 _LIBCPP_INLINE_VISIBILITY
1469 unordered_multimap& operator=(const unordered_multimap& __u)
1470 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001471#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +00001472 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001473#else
1474 __table_.clear();
1475 __table_.hash_function() = __u.__table_.hash_function();
1476 __table_.key_eq() = __u.__table_.key_eq();
1477 __table_.max_load_factor() = __u.__table_.max_load_factor();
1478 __table_.__copy_assign_alloc(__u.__table_);
1479 insert(__u.begin(), __u.end());
1480#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +00001481 return *this;
1482 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001483#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001484 unordered_multimap& operator=(unordered_multimap&& __u)
1485 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001486#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001487#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001488 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001489#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001490
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001491 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001492 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001493 {return allocator_type(__table_.__node_alloc());}
1494
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001495 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001496 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001497 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001498 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001499 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001500 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001501
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001502 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001503 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001504 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001505 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001507 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001508 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001509 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001510 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001511 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001512 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001513 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001514
Howard Hinnant73d21a42010-09-04 23:28:19 +00001515#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +00001516#ifndef _LIBCPP_HAS_NO_VARIADICS
1517
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001518 template <class... _Args>
1519 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001520
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001521 template <class... _Args>
1522 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001523#endif // _LIBCPP_HAS_NO_VARIADICS
1524#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001526 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001527#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001528 template <class _Pp,
1529 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001531 iterator insert(_Pp&& __x)
1532 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001533#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001535 iterator insert(const_iterator __p, const value_type& __x)
1536 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001537#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001538 template <class _Pp,
1539 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001540 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001541 iterator insert(const_iterator __p, _Pp&& __x)
1542 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001543#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001544 template <class _InputIterator>
1545 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001546#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001547 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001548 void insert(initializer_list<value_type> __il)
1549 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001550#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001551
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001552 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001553 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001555 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001556 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001557 iterator erase(const_iterator __first, const_iterator __last)
1558 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001559 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001560 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001561
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001562 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001563 void swap(unordered_multimap& __u)
1564 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1565 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001566
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001568 hasher hash_function() const
1569 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001571 key_equal key_eq() const
1572 {return __table_.key_eq().key_eq();}
1573
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001575 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001577 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001579 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001581 pair<iterator, iterator> equal_range(const key_type& __k)
1582 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001583 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001584 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1585 {return __table_.__equal_range_multi(__k);}
1586
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001588 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001590 size_type max_bucket_count() const _NOEXCEPT
1591 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001592
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001594 size_type bucket_size(size_type __n) const
1595 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001596 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001597 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1598
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001599 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001600 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001601 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001602 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001603 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001604 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001605 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001606 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001607 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001608 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001609 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001610 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1611
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001612 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001613 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001614 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001615 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001616 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001617 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001618 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001619 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001620 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001621 void reserve(size_type __n) {__table_.reserve(__n);}
1622
Howard Hinnant39213642013-07-23 22:01:58 +00001623#if _LIBCPP_DEBUG_LEVEL >= 2
1624
1625 bool __dereferenceable(const const_iterator* __i) const
1626 {return __table_.__dereferenceable(&__i->__i_);}
1627 bool __decrementable(const const_iterator* __i) const
1628 {return __table_.__decrementable(&__i->__i_);}
1629 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1630 {return __table_.__addable(&__i->__i_, __n);}
1631 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1632 {return __table_.__addable(&__i->__i_, __n);}
1633
1634#endif // _LIBCPP_DEBUG_LEVEL >= 2
1635
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001636private:
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001637#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1638 __node_holder __construct_node();
1639 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001640 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001641 __construct_node(_A0&& __a0);
1642#ifndef _LIBCPP_HAS_NO_VARIADICS
1643 template <class _A0, class _A1, class ..._Args>
1644 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1645#endif // _LIBCPP_HAS_NO_VARIADICS
1646#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001647};
1648
1649template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1650unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1651 size_type __n, const hasher& __hf, const key_equal& __eql)
1652 : __table_(__hf, __eql)
1653{
Howard Hinnant39213642013-07-23 22:01:58 +00001654#if _LIBCPP_DEBUG_LEVEL >= 2
1655 __get_db()->__insert_c(this);
1656#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001657 __table_.rehash(__n);
1658}
1659
1660template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1661unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1662 size_type __n, const hasher& __hf, const key_equal& __eql,
1663 const allocator_type& __a)
1664 : __table_(__hf, __eql, __a)
1665{
Howard Hinnant39213642013-07-23 22:01:58 +00001666#if _LIBCPP_DEBUG_LEVEL >= 2
1667 __get_db()->__insert_c(this);
1668#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001669 __table_.rehash(__n);
1670}
1671
1672template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1673template <class _InputIterator>
1674unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1675 _InputIterator __first, _InputIterator __last)
1676{
Howard Hinnant39213642013-07-23 22:01:58 +00001677#if _LIBCPP_DEBUG_LEVEL >= 2
1678 __get_db()->__insert_c(this);
1679#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001680 insert(__first, __last);
1681}
1682
1683template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1684template <class _InputIterator>
1685unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1686 _InputIterator __first, _InputIterator __last, size_type __n,
1687 const hasher& __hf, const key_equal& __eql)
1688 : __table_(__hf, __eql)
1689{
Howard Hinnant39213642013-07-23 22:01:58 +00001690#if _LIBCPP_DEBUG_LEVEL >= 2
1691 __get_db()->__insert_c(this);
1692#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001693 __table_.rehash(__n);
1694 insert(__first, __last);
1695}
1696
1697template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1698template <class _InputIterator>
1699unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1700 _InputIterator __first, _InputIterator __last, size_type __n,
1701 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1702 : __table_(__hf, __eql, __a)
1703{
Howard Hinnant39213642013-07-23 22:01:58 +00001704#if _LIBCPP_DEBUG_LEVEL >= 2
1705 __get_db()->__insert_c(this);
1706#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001707 __table_.rehash(__n);
1708 insert(__first, __last);
1709}
1710
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001711template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001712inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001713unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1714 const allocator_type& __a)
1715 : __table_(__a)
1716{
Howard Hinnant39213642013-07-23 22:01:58 +00001717#if _LIBCPP_DEBUG_LEVEL >= 2
1718 __get_db()->__insert_c(this);
1719#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001720}
1721
1722template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1723unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1724 const unordered_multimap& __u)
1725 : __table_(__u.__table_)
1726{
Howard Hinnant39213642013-07-23 22:01:58 +00001727#if _LIBCPP_DEBUG_LEVEL >= 2
1728 __get_db()->__insert_c(this);
1729#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001730 __table_.rehash(__u.bucket_count());
1731 insert(__u.begin(), __u.end());
1732}
1733
1734template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1735unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1736 const unordered_multimap& __u, const allocator_type& __a)
1737 : __table_(__u.__table_, __a)
1738{
Howard Hinnant39213642013-07-23 22:01:58 +00001739#if _LIBCPP_DEBUG_LEVEL >= 2
1740 __get_db()->__insert_c(this);
1741#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001742 __table_.rehash(__u.bucket_count());
1743 insert(__u.begin(), __u.end());
1744}
1745
Howard Hinnant73d21a42010-09-04 23:28:19 +00001746#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001747
1748template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001749inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001750unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1751 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001752 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001753 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001754{
Howard Hinnant39213642013-07-23 22:01:58 +00001755#if _LIBCPP_DEBUG_LEVEL >= 2
1756 __get_db()->__insert_c(this);
1757#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001758}
1759
1760template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1761unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1762 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001763 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001764{
Howard Hinnant39213642013-07-23 22:01:58 +00001765#if _LIBCPP_DEBUG_LEVEL >= 2
1766 __get_db()->__insert_c(this);
1767#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001768 if (__a != __u.get_allocator())
1769 {
1770 iterator __i = __u.begin();
1771 while (__u.size() != 0)
Howard Hinnant39213642013-07-23 22:01:58 +00001772 {
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001773 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001774 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001775 );
Howard Hinnant39213642013-07-23 22:01:58 +00001776 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001777 }
1778}
1779
Howard Hinnant73d21a42010-09-04 23:28:19 +00001780#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001781
Howard Hinnante3e32912011-08-12 21:56:02 +00001782#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1783
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001784template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1785unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1786 initializer_list<value_type> __il)
1787{
Howard Hinnant39213642013-07-23 22:01:58 +00001788#if _LIBCPP_DEBUG_LEVEL >= 2
1789 __get_db()->__insert_c(this);
1790#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001791 insert(__il.begin(), __il.end());
1792}
1793
1794template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1795unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1796 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1797 const key_equal& __eql)
1798 : __table_(__hf, __eql)
1799{
Howard Hinnant39213642013-07-23 22:01:58 +00001800#if _LIBCPP_DEBUG_LEVEL >= 2
1801 __get_db()->__insert_c(this);
1802#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001803 __table_.rehash(__n);
1804 insert(__il.begin(), __il.end());
1805}
1806
1807template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1808unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1809 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1810 const key_equal& __eql, const allocator_type& __a)
1811 : __table_(__hf, __eql, __a)
1812{
Howard Hinnant39213642013-07-23 22:01:58 +00001813#if _LIBCPP_DEBUG_LEVEL >= 2
1814 __get_db()->__insert_c(this);
1815#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001816 __table_.rehash(__n);
1817 insert(__il.begin(), __il.end());
1818}
1819
Howard Hinnante3e32912011-08-12 21:56:02 +00001820#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1821
Howard Hinnant73d21a42010-09-04 23:28:19 +00001822#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001823
1824template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001825inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001826unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1827unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001828 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001829{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001830 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001831 return *this;
1832}
1833
Howard Hinnant73d21a42010-09-04 23:28:19 +00001834#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001835
Howard Hinnante3e32912011-08-12 21:56:02 +00001836#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1837
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001838template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001839inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001840unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1841unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1842 initializer_list<value_type> __il)
1843{
1844 __table_.__assign_multi(__il.begin(), __il.end());
1845 return *this;
1846}
1847
Howard Hinnante3e32912011-08-12 21:56:02 +00001848#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1849
Howard Hinnant73d21a42010-09-04 23:28:19 +00001850#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001851
1852template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001853typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001854unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001855{
1856 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001857 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001858 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001859 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001860 __h.get_deleter().__second_constructed = true;
1861 return __h;
1862}
1863
1864template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001865template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001866typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001867unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1868{
1869 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001870 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001871 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1872 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001873 __h.get_deleter().__first_constructed = true;
1874 __h.get_deleter().__second_constructed = true;
1875 return __h;
1876}
1877
Howard Hinnant73d21a42010-09-04 23:28:19 +00001878#ifndef _LIBCPP_HAS_NO_VARIADICS
1879
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001880template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001881template <class _A0, class _A1, class ..._Args>
1882typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1883unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1884 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001885{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001886 __node_allocator& __na = __table_.__node_alloc();
1887 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1888 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1889 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1890 _VSTD::forward<_Args>(__args)...);
1891 __h.get_deleter().__first_constructed = true;
1892 __h.get_deleter().__second_constructed = true;
1893 return __h;
1894}
1895
1896template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1897template <class... _Args>
1898typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1899unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1900{
1901 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001902 iterator __r = __table_.__node_insert_multi(__h.get());
1903 __h.release();
1904 return __r;
1905}
1906
1907template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001908template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001909typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1910unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001911 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001912{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001913 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001914 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1915 __h.release();
1916 return __r;
1917}
1918
Howard Hinnant73d21a42010-09-04 23:28:19 +00001919#endif // _LIBCPP_HAS_NO_VARIADICS
1920#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001921
1922template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1923template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001924inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001925void
1926unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1927 _InputIterator __last)
1928{
1929 for (; __first != __last; ++__first)
1930 __table_.__insert_multi(*__first);
1931}
1932
1933template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001934inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001935void
1936swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1937 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001938 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001939{
1940 __x.swap(__y);
1941}
1942
1943template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1944bool
1945operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1946 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1947{
1948 if (__x.size() != __y.size())
1949 return false;
1950 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1951 const_iterator;
1952 typedef pair<const_iterator, const_iterator> _EqRng;
1953 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1954 {
1955 _EqRng __xeq = __x.equal_range(__i->first);
1956 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001957 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1958 _VSTD::distance(__yeq.first, __yeq.second) ||
1959 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001960 return false;
1961 __i = __xeq.second;
1962 }
1963 return true;
1964}
1965
1966template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001967inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001968bool
1969operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1970 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1971{
1972 return !(__x == __y);
1973}
1974
1975_LIBCPP_END_NAMESPACE_STD
1976
1977#endif // _LIBCPP_UNORDERED_MAP