blob: b53af146292b0158eb4b776322e64808f894331b [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 Hinnant0f678bd2013-08-12 18:38:34 +0000497class _LIBCPP_TYPE_VIS_ONLY __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 Hinnant0f678bd2013-08-12 18:38:34 +0000545 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
546 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
547 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
548 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
549 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000550};
551
552template <class _HashIterator>
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000553class _LIBCPP_TYPE_VIS_ONLY __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 Hinnant0f678bd2013-08-12 18:38:34 +0000606 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
607 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
608 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
609 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __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 Hinnant0f678bd2013-08-12 18:38:34 +0000614class _LIBCPP_TYPE_VIS_ONLY 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 Hinnantf890d9b2013-07-30 21:04:42 +0000804#if _LIBCPP_DEBUG_LEVEL >= 2
805 iterator emplace_hint(const_iterator __p, _Args&&... __args)
806 {
807 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
808 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not"
809 " referring to this unordered_map");
810 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
811 }
812#else
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000813 iterator emplace_hint(const_iterator, _Args&&... __args)
814 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000815#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000816#endif // _LIBCPP_HAS_NO_VARIADICS
817#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 pair<iterator, bool> insert(const value_type& __x)
820 {return __table_.__insert_unique(__x);}
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 pair<iterator, bool> insert(_Pp&& __x)
826 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000827#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000828 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000829#if _LIBCPP_DEBUG_LEVEL >= 2
830 iterator insert(const_iterator __p, const value_type& __x)
831 {
832 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
833 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not"
834 " referring to this unordered_map");
835 return insert(__x).first;
836 }
837#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000838 iterator insert(const_iterator, const value_type& __x)
839 {return insert(__x).first;}
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000840#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000841#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000842 template <class _Pp,
843 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000844 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000845#if _LIBCPP_DEBUG_LEVEL >= 2
846 iterator insert(const_iterator __p, _Pp&& __x)
847 {
848 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
849 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not"
850 " referring to this unordered_map");
851 return insert(_VSTD::forward<_Pp>(__x)).first;
852 }
853#else
Howard Hinnant99968442011-11-29 18:15:50 +0000854 iterator insert(const_iterator, _Pp&& __x)
855 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnantf890d9b2013-07-30 21:04:42 +0000856#endif
Howard Hinnant73d21a42010-09-04 23:28:19 +0000857#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000858 template <class _InputIterator>
859 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000860#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862 void insert(initializer_list<value_type> __il)
863 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000864#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000865
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000866 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000867 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000869 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000870 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000871 iterator erase(const_iterator __first, const_iterator __last)
872 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000874 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000875
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000876 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000877 void swap(unordered_map& __u)
878 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
879 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000880
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000881 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000882 hasher hash_function() const
883 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000885 key_equal key_eq() const
886 {return __table_.key_eq().key_eq();}
887
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000889 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000890 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000891 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000893 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000895 pair<iterator, iterator> equal_range(const key_type& __k)
896 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000898 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
899 {return __table_.__equal_range_unique(__k);}
900
901 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000902#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000903 mapped_type& operator[](key_type&& __k);
904#endif
905
906 mapped_type& at(const key_type& __k);
907 const mapped_type& at(const key_type& __k) const;
908
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000909 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000910 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000911 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000912 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000913
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000914 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000915 size_type bucket_size(size_type __n) const
916 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000917 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000918 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
919
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000920 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000921 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000922 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000923 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000924 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000925 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000926 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000927 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000928 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000929 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000930 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000931 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
932
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000933 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000934 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000935 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000936 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000937 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000938 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000939 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000940 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000941 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000942 void reserve(size_type __n) {__table_.reserve(__n);}
943
Howard Hinnant39213642013-07-23 22:01:58 +0000944#if _LIBCPP_DEBUG_LEVEL >= 2
945
946 bool __dereferenceable(const const_iterator* __i) const
947 {return __table_.__dereferenceable(&__i->__i_);}
948 bool __decrementable(const const_iterator* __i) const
949 {return __table_.__decrementable(&__i->__i_);}
950 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
951 {return __table_.__addable(&__i->__i_, __n);}
952 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
953 {return __table_.__addable(&__i->__i_, __n);}
954
955#endif // _LIBCPP_DEBUG_LEVEL >= 2
956
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000957private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000958#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000959 __node_holder __construct_node();
960 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000961 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000962 __construct_node(_A0&& __a0);
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000963 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000964#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000965 template <class _A0, class _A1, class ..._Args>
966 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000967#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000968#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
969 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000970};
971
972template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
973unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
974 size_type __n, const hasher& __hf, const key_equal& __eql)
975 : __table_(__hf, __eql)
976{
Howard Hinnant39213642013-07-23 22:01:58 +0000977#if _LIBCPP_DEBUG_LEVEL >= 2
978 __get_db()->__insert_c(this);
979#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000980 __table_.rehash(__n);
981}
982
983template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
984unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
985 size_type __n, const hasher& __hf, const key_equal& __eql,
986 const allocator_type& __a)
987 : __table_(__hf, __eql, __a)
988{
Howard Hinnant39213642013-07-23 22:01:58 +0000989#if _LIBCPP_DEBUG_LEVEL >= 2
990 __get_db()->__insert_c(this);
991#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000992 __table_.rehash(__n);
993}
994
995template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000996inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000997unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
998 const allocator_type& __a)
999 : __table_(__a)
1000{
Howard Hinnant39213642013-07-23 22:01:58 +00001001#if _LIBCPP_DEBUG_LEVEL >= 2
1002 __get_db()->__insert_c(this);
1003#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001004}
1005
1006template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1007template <class _InputIterator>
1008unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1009 _InputIterator __first, _InputIterator __last)
1010{
Howard Hinnant39213642013-07-23 22:01:58 +00001011#if _LIBCPP_DEBUG_LEVEL >= 2
1012 __get_db()->__insert_c(this);
1013#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001014 insert(__first, __last);
1015}
1016
1017template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1018template <class _InputIterator>
1019unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1020 _InputIterator __first, _InputIterator __last, size_type __n,
1021 const hasher& __hf, const key_equal& __eql)
1022 : __table_(__hf, __eql)
1023{
Howard Hinnant39213642013-07-23 22:01:58 +00001024#if _LIBCPP_DEBUG_LEVEL >= 2
1025 __get_db()->__insert_c(this);
1026#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001027 __table_.rehash(__n);
1028 insert(__first, __last);
1029}
1030
1031template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1032template <class _InputIterator>
1033unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1034 _InputIterator __first, _InputIterator __last, size_type __n,
1035 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1036 : __table_(__hf, __eql, __a)
1037{
Howard Hinnant39213642013-07-23 22:01:58 +00001038#if _LIBCPP_DEBUG_LEVEL >= 2
1039 __get_db()->__insert_c(this);
1040#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001041 __table_.rehash(__n);
1042 insert(__first, __last);
1043}
1044
1045template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1046unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1047 const unordered_map& __u)
1048 : __table_(__u.__table_)
1049{
Howard Hinnant39213642013-07-23 22:01:58 +00001050#if _LIBCPP_DEBUG_LEVEL >= 2
1051 __get_db()->__insert_c(this);
1052#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001053 __table_.rehash(__u.bucket_count());
1054 insert(__u.begin(), __u.end());
1055}
1056
1057template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1058unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1059 const unordered_map& __u, const allocator_type& __a)
1060 : __table_(__u.__table_, __a)
1061{
Howard Hinnant39213642013-07-23 22:01:58 +00001062#if _LIBCPP_DEBUG_LEVEL >= 2
1063 __get_db()->__insert_c(this);
1064#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001065 __table_.rehash(__u.bucket_count());
1066 insert(__u.begin(), __u.end());
1067}
1068
Howard Hinnant73d21a42010-09-04 23:28:19 +00001069#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001070
1071template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001072inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001073unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1074 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001075 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001076 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001077{
Howard Hinnant39213642013-07-23 22:01:58 +00001078#if _LIBCPP_DEBUG_LEVEL >= 2
1079 __get_db()->__insert_c(this);
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001080 __get_db()->swap(this, &__u);
Howard Hinnant39213642013-07-23 22:01:58 +00001081#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001082}
1083
1084template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1085unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1086 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001087 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001088{
Howard Hinnant39213642013-07-23 22:01:58 +00001089#if _LIBCPP_DEBUG_LEVEL >= 2
1090 __get_db()->__insert_c(this);
1091#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001092 if (__a != __u.get_allocator())
1093 {
1094 iterator __i = __u.begin();
1095 while (__u.size() != 0)
1096 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001097 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001098 );
1099 }
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001100#if _LIBCPP_DEBUG_LEVEL >= 2
1101 else
1102 __get_db()->swap(this, &__u);
1103#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001104}
1105
Howard Hinnant73d21a42010-09-04 23:28:19 +00001106#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001107
Howard Hinnante3e32912011-08-12 21:56:02 +00001108#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1109
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001110template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1111unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1112 initializer_list<value_type> __il)
1113{
Howard Hinnant39213642013-07-23 22:01:58 +00001114#if _LIBCPP_DEBUG_LEVEL >= 2
1115 __get_db()->__insert_c(this);
1116#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001117 insert(__il.begin(), __il.end());
1118}
1119
1120template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1121unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1122 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1123 const key_equal& __eql)
1124 : __table_(__hf, __eql)
1125{
Howard Hinnant39213642013-07-23 22:01:58 +00001126#if _LIBCPP_DEBUG_LEVEL >= 2
1127 __get_db()->__insert_c(this);
1128#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001129 __table_.rehash(__n);
1130 insert(__il.begin(), __il.end());
1131}
1132
1133template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1134unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1135 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1136 const key_equal& __eql, const allocator_type& __a)
1137 : __table_(__hf, __eql, __a)
1138{
Howard Hinnant39213642013-07-23 22:01:58 +00001139#if _LIBCPP_DEBUG_LEVEL >= 2
1140 __get_db()->__insert_c(this);
1141#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001142 __table_.rehash(__n);
1143 insert(__il.begin(), __il.end());
1144}
1145
Howard Hinnante3e32912011-08-12 21:56:02 +00001146#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1147
Howard Hinnant73d21a42010-09-04 23:28:19 +00001148#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001149
1150template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001151inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001152unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1153unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001154 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001155{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001156 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001157 return *this;
1158}
1159
Howard Hinnant73d21a42010-09-04 23:28:19 +00001160#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001161
Howard Hinnante3e32912011-08-12 21:56:02 +00001162#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1163
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001164template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001165inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001166unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1167unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1168 initializer_list<value_type> __il)
1169{
1170 __table_.__assign_unique(__il.begin(), __il.end());
1171 return *this;
1172}
1173
Howard Hinnante3e32912011-08-12 21:56:02 +00001174#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1175
Howard Hinnant73d21a42010-09-04 23:28:19 +00001176#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001177
1178template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001179typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001180unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001181{
1182 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001183 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001184 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001185 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001186 __h.get_deleter().__second_constructed = true;
1187 return __h;
1188}
1189
1190template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001191template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001192typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001193unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1194{
1195 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001196 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001197 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1198 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001199 __h.get_deleter().__first_constructed = true;
1200 __h.get_deleter().__second_constructed = true;
1201 return __h;
1202}
1203
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001204template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001205typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1206unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001207{
1208 __node_allocator& __na = __table_.__node_alloc();
1209 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001210 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001211 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001212 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001213 __h.get_deleter().__second_constructed = true;
Howard Hinnant9a894d92013-08-22 18:29:50 +00001214 return __h;
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001215}
1216
Howard Hinnant73d21a42010-09-04 23:28:19 +00001217#ifndef _LIBCPP_HAS_NO_VARIADICS
1218
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001219template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001220template <class _A0, class _A1, class ..._Args>
1221typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1222unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1223 _A1&& __a1,
1224 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001225{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001226 __node_allocator& __na = __table_.__node_alloc();
1227 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1228 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1229 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1230 _VSTD::forward<_Args>(__args)...);
1231 __h.get_deleter().__first_constructed = true;
1232 __h.get_deleter().__second_constructed = true;
1233 return __h;
1234}
1235
1236template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1237template <class... _Args>
1238pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1239unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1240{
1241 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001242 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1243 if (__r.second)
1244 __h.release();
1245 return __r;
1246}
1247
Howard Hinnant73d21a42010-09-04 23:28:19 +00001248#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001249#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001250
1251template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1252typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001253unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001254{
1255 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001256 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001257 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001258 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001259 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001260 __h.get_deleter().__second_constructed = true;
Howard Hinnant9a894d92013-08-22 18:29:50 +00001261 return _VSTD::move(__h); // explicitly moved for C++03
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001262}
1263
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001264template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1265template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001266inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001267void
1268unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1269 _InputIterator __last)
1270{
1271 for (; __first != __last; ++__first)
1272 __table_.__insert_unique(*__first);
1273}
1274
1275template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1276_Tp&
1277unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1278{
1279 iterator __i = find(__k);
1280 if (__i != end())
1281 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001282 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001283 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1284 __h.release();
1285 return __r.first->second;
1286}
1287
Howard Hinnant73d21a42010-09-04 23:28:19 +00001288#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001289
1290template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1291_Tp&
1292unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1293{
1294 iterator __i = find(__k);
1295 if (__i != end())
1296 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001297 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001298 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1299 __h.release();
1300 return __r.first->second;
1301}
1302
Howard Hinnant73d21a42010-09-04 23:28:19 +00001303#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001304
1305template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1306_Tp&
1307unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1308{
1309 iterator __i = find(__k);
1310#ifndef _LIBCPP_NO_EXCEPTIONS
1311 if (__i == end())
1312 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001313#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001314 return __i->second;
1315}
1316
1317template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1318const _Tp&
1319unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1320{
1321 const_iterator __i = find(__k);
1322#ifndef _LIBCPP_NO_EXCEPTIONS
1323 if (__i == end())
1324 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001325#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001326 return __i->second;
1327}
1328
1329template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001330inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001331void
1332swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1333 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001334 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001335{
1336 __x.swap(__y);
1337}
1338
1339template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1340bool
1341operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1342 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1343{
1344 if (__x.size() != __y.size())
1345 return false;
1346 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1347 const_iterator;
1348 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1349 __i != __ex; ++__i)
1350 {
1351 const_iterator __j = __y.find(__i->first);
1352 if (__j == __ey || !(*__i == *__j))
1353 return false;
1354 }
1355 return true;
1356}
1357
1358template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001359inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001360bool
1361operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1362 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1363{
1364 return !(__x == __y);
1365}
1366
1367template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1368 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant0f678bd2013-08-12 18:38:34 +00001369class _LIBCPP_TYPE_VIS_ONLY unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001370{
1371public:
1372 // types
1373 typedef _Key key_type;
1374 typedef _Tp mapped_type;
1375 typedef _Hash hasher;
1376 typedef _Pred key_equal;
1377 typedef _Alloc allocator_type;
1378 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001379 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001380 typedef value_type& reference;
1381 typedef const value_type& const_reference;
Howard Hinnant39213642013-07-23 22:01:58 +00001382 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
1383 "Invalid allocator::value_type");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001384
1385private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001386#if __cplusplus >= 201103L
1387 union __value_type
1388 {
1389 typedef typename unordered_multimap::value_type value_type;
1390 typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1391 value_type __cc;
1392 __nc_value_type __nc;
1393
1394 template <class ..._Args>
1395 __value_type(_Args&& ...__args)
1396 : __cc(std::forward<_Args>(__args)...) {}
1397
1398 __value_type(const __value_type& __v)
1399 : __cc(std::move(__v.__cc)) {}
1400
1401 __value_type(__value_type&& __v)
1402 : __nc(std::move(__v.__nc)) {}
1403
1404 __value_type& operator=(const __value_type& __v)
1405 {__nc = __v.__cc; return *this;}
1406
1407 __value_type& operator=(__value_type&& __v)
1408 {__nc = std::move(__v.__nc); return *this;}
1409
1410 ~__value_type() {__cc.~value_type();}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001411 };
1412#else
1413 struct __value_type
1414 {
1415 typedef typename unordered_multimap::value_type value_type;
1416 value_type __cc;
1417
1418 __value_type() {}
1419
1420 template <class _A0>
1421 __value_type(const _A0& __a0)
1422 : __cc(__a0) {}
1423
1424 template <class _A0, class _A1>
1425 __value_type(const _A0& __a0, const _A1& __a1)
1426 : __cc(__a0, __a1) {}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001427 };
1428#endif
Howard Hinnant9b128e02013-07-05 18:06:00 +00001429 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1430 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001431 typedef typename allocator_traits<allocator_type>::template
1432#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1433 rebind_alloc<__value_type>
1434#else
1435 rebind_alloc<__value_type>::other
1436#endif
1437 __allocator_type;
1438
1439 typedef __hash_table<__value_type, __hasher,
1440 __key_equal, __allocator_type> __table;
1441
1442 __table __table_;
1443
1444 typedef typename __table::__node_traits __node_traits;
1445 typedef typename __table::__node_allocator __node_allocator;
1446 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001447 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1448 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001449 typedef allocator_traits<allocator_type> __alloc_traits;
1450public:
1451 typedef typename __alloc_traits::pointer pointer;
1452 typedef typename __alloc_traits::const_pointer const_pointer;
1453 typedef typename __alloc_traits::size_type size_type;
1454 typedef typename __alloc_traits::difference_type difference_type;
1455
1456 typedef __hash_map_iterator<typename __table::iterator> iterator;
1457 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1458 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1459 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1460
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001462 unordered_multimap()
1463 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
Howard Hinnant39213642013-07-23 22:01:58 +00001464 {
1465#if _LIBCPP_DEBUG_LEVEL >= 2
1466 __get_db()->__insert_c(this);
1467#endif
1468 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001469 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1470 const key_equal& __eql = key_equal());
1471 unordered_multimap(size_type __n, const hasher& __hf,
1472 const key_equal& __eql,
1473 const allocator_type& __a);
1474 template <class _InputIterator>
1475 unordered_multimap(_InputIterator __first, _InputIterator __last);
1476 template <class _InputIterator>
1477 unordered_multimap(_InputIterator __first, _InputIterator __last,
1478 size_type __n, const hasher& __hf = hasher(),
1479 const key_equal& __eql = key_equal());
1480 template <class _InputIterator>
1481 unordered_multimap(_InputIterator __first, _InputIterator __last,
1482 size_type __n, const hasher& __hf,
1483 const key_equal& __eql,
1484 const allocator_type& __a);
1485 explicit unordered_multimap(const allocator_type& __a);
1486 unordered_multimap(const unordered_multimap& __u);
1487 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001488#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001489 unordered_multimap(unordered_multimap&& __u)
1490 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001491 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001492#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001493#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001494 unordered_multimap(initializer_list<value_type> __il);
1495 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1496 const hasher& __hf = hasher(),
1497 const key_equal& __eql = key_equal());
1498 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1499 const hasher& __hf, const key_equal& __eql,
1500 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001501#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001502 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001503 _LIBCPP_INLINE_VISIBILITY
1504 unordered_multimap& operator=(const unordered_multimap& __u)
1505 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001506#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +00001507 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001508#else
1509 __table_.clear();
1510 __table_.hash_function() = __u.__table_.hash_function();
1511 __table_.key_eq() = __u.__table_.key_eq();
1512 __table_.max_load_factor() = __u.__table_.max_load_factor();
1513 __table_.__copy_assign_alloc(__u.__table_);
1514 insert(__u.begin(), __u.end());
1515#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +00001516 return *this;
1517 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001518#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001519 unordered_multimap& operator=(unordered_multimap&& __u)
1520 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001521#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001522#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001523 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001524#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001525
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001526 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001527 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001528 {return allocator_type(__table_.__node_alloc());}
1529
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001531 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001532 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001533 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001535 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001536
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001537 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001538 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001539 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001540 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001541 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001542 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001543 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001544 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001545 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001546 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001547 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001548 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001549
Howard Hinnant73d21a42010-09-04 23:28:19 +00001550#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +00001551#ifndef _LIBCPP_HAS_NO_VARIADICS
1552
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001553 template <class... _Args>
1554 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001555
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001556 template <class... _Args>
1557 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001558#endif // _LIBCPP_HAS_NO_VARIADICS
1559#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001560 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001561 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001562#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001563 template <class _Pp,
1564 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001565 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001566 iterator insert(_Pp&& __x)
1567 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001568#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001569 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001570 iterator insert(const_iterator __p, const value_type& __x)
1571 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001572#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001573 template <class _Pp,
1574 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001576 iterator insert(const_iterator __p, _Pp&& __x)
1577 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001578#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001579 template <class _InputIterator>
1580 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001581#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001583 void insert(initializer_list<value_type> __il)
1584 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001585#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001586
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001588 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001590 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001592 iterator erase(const_iterator __first, const_iterator __last)
1593 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001594 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001595 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001596
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001598 void swap(unordered_multimap& __u)
1599 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1600 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001601
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001602 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001603 hasher hash_function() const
1604 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001605 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001606 key_equal key_eq() const
1607 {return __table_.key_eq().key_eq();}
1608
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001609 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001610 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001611 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001612 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001613 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001614 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001615 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001616 pair<iterator, iterator> equal_range(const key_type& __k)
1617 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001618 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001619 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1620 {return __table_.__equal_range_multi(__k);}
1621
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001622 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001623 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001624 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001625 size_type max_bucket_count() const _NOEXCEPT
1626 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001627
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001628 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001629 size_type bucket_size(size_type __n) const
1630 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001631 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001632 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1633
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001634 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001635 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001636 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001637 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001638 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001639 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001640 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001641 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001642 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001643 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001644 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001645 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1646
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001647 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001648 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001649 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001650 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001651 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001652 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001653 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001654 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001655 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001656 void reserve(size_type __n) {__table_.reserve(__n);}
1657
Howard Hinnant39213642013-07-23 22:01:58 +00001658#if _LIBCPP_DEBUG_LEVEL >= 2
1659
1660 bool __dereferenceable(const const_iterator* __i) const
1661 {return __table_.__dereferenceable(&__i->__i_);}
1662 bool __decrementable(const const_iterator* __i) const
1663 {return __table_.__decrementable(&__i->__i_);}
1664 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1665 {return __table_.__addable(&__i->__i_, __n);}
1666 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1667 {return __table_.__addable(&__i->__i_, __n);}
1668
1669#endif // _LIBCPP_DEBUG_LEVEL >= 2
1670
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001671private:
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001672#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1673 __node_holder __construct_node();
1674 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001675 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001676 __construct_node(_A0&& __a0);
1677#ifndef _LIBCPP_HAS_NO_VARIADICS
1678 template <class _A0, class _A1, class ..._Args>
1679 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1680#endif // _LIBCPP_HAS_NO_VARIADICS
1681#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001682};
1683
1684template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1685unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1686 size_type __n, const hasher& __hf, const key_equal& __eql)
1687 : __table_(__hf, __eql)
1688{
Howard Hinnant39213642013-07-23 22:01:58 +00001689#if _LIBCPP_DEBUG_LEVEL >= 2
1690 __get_db()->__insert_c(this);
1691#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001692 __table_.rehash(__n);
1693}
1694
1695template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1696unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1697 size_type __n, const hasher& __hf, const key_equal& __eql,
1698 const allocator_type& __a)
1699 : __table_(__hf, __eql, __a)
1700{
Howard Hinnant39213642013-07-23 22:01:58 +00001701#if _LIBCPP_DEBUG_LEVEL >= 2
1702 __get_db()->__insert_c(this);
1703#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001704 __table_.rehash(__n);
1705}
1706
1707template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1708template <class _InputIterator>
1709unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1710 _InputIterator __first, _InputIterator __last)
1711{
Howard Hinnant39213642013-07-23 22:01:58 +00001712#if _LIBCPP_DEBUG_LEVEL >= 2
1713 __get_db()->__insert_c(this);
1714#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001715 insert(__first, __last);
1716}
1717
1718template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1719template <class _InputIterator>
1720unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1721 _InputIterator __first, _InputIterator __last, size_type __n,
1722 const hasher& __hf, const key_equal& __eql)
1723 : __table_(__hf, __eql)
1724{
Howard Hinnant39213642013-07-23 22:01:58 +00001725#if _LIBCPP_DEBUG_LEVEL >= 2
1726 __get_db()->__insert_c(this);
1727#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001728 __table_.rehash(__n);
1729 insert(__first, __last);
1730}
1731
1732template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1733template <class _InputIterator>
1734unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1735 _InputIterator __first, _InputIterator __last, size_type __n,
1736 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1737 : __table_(__hf, __eql, __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(__n);
1743 insert(__first, __last);
1744}
1745
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001746template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001747inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001748unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1749 const allocator_type& __a)
1750 : __table_(__a)
1751{
Howard Hinnant39213642013-07-23 22:01:58 +00001752#if _LIBCPP_DEBUG_LEVEL >= 2
1753 __get_db()->__insert_c(this);
1754#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001755}
1756
1757template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1758unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1759 const unordered_multimap& __u)
1760 : __table_(__u.__table_)
1761{
Howard Hinnant39213642013-07-23 22:01:58 +00001762#if _LIBCPP_DEBUG_LEVEL >= 2
1763 __get_db()->__insert_c(this);
1764#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001765 __table_.rehash(__u.bucket_count());
1766 insert(__u.begin(), __u.end());
1767}
1768
1769template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1770unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1771 const unordered_multimap& __u, const allocator_type& __a)
1772 : __table_(__u.__table_, __a)
1773{
Howard Hinnant39213642013-07-23 22:01:58 +00001774#if _LIBCPP_DEBUG_LEVEL >= 2
1775 __get_db()->__insert_c(this);
1776#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001777 __table_.rehash(__u.bucket_count());
1778 insert(__u.begin(), __u.end());
1779}
1780
Howard Hinnant73d21a42010-09-04 23:28:19 +00001781#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001782
1783template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001784inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001785unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1786 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001787 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001788 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001789{
Howard Hinnant39213642013-07-23 22:01:58 +00001790#if _LIBCPP_DEBUG_LEVEL >= 2
1791 __get_db()->__insert_c(this);
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001792 __get_db()->swap(this, &__u);
Howard Hinnant39213642013-07-23 22:01:58 +00001793#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001794}
1795
1796template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1797unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1798 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001799 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001800{
Howard Hinnant39213642013-07-23 22:01:58 +00001801#if _LIBCPP_DEBUG_LEVEL >= 2
1802 __get_db()->__insert_c(this);
1803#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001804 if (__a != __u.get_allocator())
1805 {
1806 iterator __i = __u.begin();
1807 while (__u.size() != 0)
Howard Hinnant39213642013-07-23 22:01:58 +00001808 {
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001809 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001810 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001811 );
Howard Hinnant39213642013-07-23 22:01:58 +00001812 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001813 }
Howard Hinnantf890d9b2013-07-30 21:04:42 +00001814#if _LIBCPP_DEBUG_LEVEL >= 2
1815 else
1816 __get_db()->swap(this, &__u);
1817#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001818}
1819
Howard Hinnant73d21a42010-09-04 23:28:19 +00001820#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001821
Howard Hinnante3e32912011-08-12 21:56:02 +00001822#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1823
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001824template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1825unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1826 initializer_list<value_type> __il)
1827{
Howard Hinnant39213642013-07-23 22:01:58 +00001828#if _LIBCPP_DEBUG_LEVEL >= 2
1829 __get_db()->__insert_c(this);
1830#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001831 insert(__il.begin(), __il.end());
1832}
1833
1834template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1835unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1836 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1837 const key_equal& __eql)
1838 : __table_(__hf, __eql)
1839{
Howard Hinnant39213642013-07-23 22:01:58 +00001840#if _LIBCPP_DEBUG_LEVEL >= 2
1841 __get_db()->__insert_c(this);
1842#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001843 __table_.rehash(__n);
1844 insert(__il.begin(), __il.end());
1845}
1846
1847template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1848unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1849 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1850 const key_equal& __eql, const allocator_type& __a)
1851 : __table_(__hf, __eql, __a)
1852{
Howard Hinnant39213642013-07-23 22:01:58 +00001853#if _LIBCPP_DEBUG_LEVEL >= 2
1854 __get_db()->__insert_c(this);
1855#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001856 __table_.rehash(__n);
1857 insert(__il.begin(), __il.end());
1858}
1859
Howard Hinnante3e32912011-08-12 21:56:02 +00001860#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1861
Howard Hinnant73d21a42010-09-04 23:28:19 +00001862#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001863
1864template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001865inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001866unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1867unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001868 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001869{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001870 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001871 return *this;
1872}
1873
Howard Hinnant73d21a42010-09-04 23:28:19 +00001874#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001875
Howard Hinnante3e32912011-08-12 21:56:02 +00001876#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1877
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001878template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001879inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001880unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1881unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1882 initializer_list<value_type> __il)
1883{
1884 __table_.__assign_multi(__il.begin(), __il.end());
1885 return *this;
1886}
1887
Howard Hinnante3e32912011-08-12 21:56:02 +00001888#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1889
Howard Hinnant73d21a42010-09-04 23:28:19 +00001890#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001891
1892template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001893typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001894unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001895{
1896 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001897 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001898 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001899 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001900 __h.get_deleter().__second_constructed = true;
1901 return __h;
1902}
1903
1904template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001905template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001906typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001907unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1908{
1909 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001910 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001911 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1912 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001913 __h.get_deleter().__first_constructed = true;
1914 __h.get_deleter().__second_constructed = true;
1915 return __h;
1916}
1917
Howard Hinnant73d21a42010-09-04 23:28:19 +00001918#ifndef _LIBCPP_HAS_NO_VARIADICS
1919
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001920template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001921template <class _A0, class _A1, class ..._Args>
1922typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1923unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1924 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001925{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001926 __node_allocator& __na = __table_.__node_alloc();
1927 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1928 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1929 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1930 _VSTD::forward<_Args>(__args)...);
1931 __h.get_deleter().__first_constructed = true;
1932 __h.get_deleter().__second_constructed = true;
1933 return __h;
1934}
1935
1936template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1937template <class... _Args>
1938typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1939unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1940{
1941 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001942 iterator __r = __table_.__node_insert_multi(__h.get());
1943 __h.release();
1944 return __r;
1945}
1946
1947template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001948template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001949typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1950unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001951 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001952{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001953 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001954 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1955 __h.release();
1956 return __r;
1957}
1958
Howard Hinnant73d21a42010-09-04 23:28:19 +00001959#endif // _LIBCPP_HAS_NO_VARIADICS
1960#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001961
1962template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1963template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001964inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001965void
1966unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1967 _InputIterator __last)
1968{
1969 for (; __first != __last; ++__first)
1970 __table_.__insert_multi(*__first);
1971}
1972
1973template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001974inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001975void
1976swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1977 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001978 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001979{
1980 __x.swap(__y);
1981}
1982
1983template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1984bool
1985operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1986 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1987{
1988 if (__x.size() != __y.size())
1989 return false;
1990 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1991 const_iterator;
1992 typedef pair<const_iterator, const_iterator> _EqRng;
1993 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1994 {
1995 _EqRng __xeq = __x.equal_range(__i->first);
1996 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001997 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1998 _VSTD::distance(__yeq.first, __yeq.second) ||
1999 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002000 return false;
2001 __i = __xeq.second;
2002 }
2003 return true;
2004}
2005
2006template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002007inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002008bool
2009operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2010 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2011{
2012 return !(__x == __y);
2013}
2014
2015_LIBCPP_END_NAMESPACE_STD
2016
2017#endif // _LIBCPP_UNORDERED_MAP