blob: 3b1701e2fbb9e6d86e9d25bdaf404ede4661a284 [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 Hinnantd4cf2152011-12-11 20:31:33 +0000328template <class _Tp, class _Hash, bool = is_empty<_Hash>::value
329#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 Hinnantbc8d3f92010-05-11 19:42:16 +0000348 size_t operator()(const _Tp& __x) const
349 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000350 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000351 size_t operator()(const typename _Tp::first_type& __x) const
352 {return static_cast<const _Hash&>(*this)(__x);}
353};
354
355template <class _Tp, class _Hash>
356class __unordered_map_hasher<_Tp, _Hash, false>
357{
358 _Hash __hash_;
359public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000361 __unordered_map_hasher()
362 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
363 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000365 __unordered_map_hasher(const _Hash& __h)
366 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
367 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000368 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000369 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000370 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000371 size_t operator()(const _Tp& __x) const
372 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000373 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000374 size_t operator()(const typename _Tp::first_type& __x) const
375 {return __hash_(__x);}
376};
377
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000378template <class _Tp, class _Pred, bool = is_empty<_Pred>::value
379#if __has_feature(is_final)
380 && !__is_final(_Pred)
381#endif
382 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000383class __unordered_map_equal
384 : private _Pred
385{
386public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000387 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000388 __unordered_map_equal()
389 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
390 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000391 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000392 __unordered_map_equal(const _Pred& __p)
393 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
394 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000395 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000396 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000397 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000398 bool operator()(const _Tp& __x, const _Tp& __y) const
399 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000400 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000401 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
402 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000403 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000404 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
405 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000406 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant324bb032010-08-22 00:02:43 +0000407 bool operator()(const typename _Tp::first_type& __x,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000408 const typename _Tp::first_type& __y) const
409 {return static_cast<const _Pred&>(*this)(__x, __y);}
410};
411
412template <class _Tp, class _Pred>
413class __unordered_map_equal<_Tp, _Pred, false>
414{
415 _Pred __pred_;
416public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000418 __unordered_map_equal()
419 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
420 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000421 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000422 __unordered_map_equal(const _Pred& __p)
423 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
424 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000426 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000428 bool operator()(const _Tp& __x, const _Tp& __y) const
429 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000430 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000431 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
432 {return __pred_(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000433 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000434 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
435 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000436 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000437 bool operator()(const typename _Tp::first_type& __x,
438 const typename _Tp::first_type& __y) const
439 {return __pred_(__x, __y);}
440};
441
442template <class _Alloc>
443class __hash_map_node_destructor
444{
445 typedef _Alloc allocator_type;
446 typedef allocator_traits<allocator_type> __alloc_traits;
447 typedef typename __alloc_traits::value_type::value_type value_type;
448public:
449 typedef typename __alloc_traits::pointer pointer;
450private:
451 typedef typename value_type::first_type first_type;
452 typedef typename value_type::second_type second_type;
453
454 allocator_type& __na_;
455
456 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
457
458public:
459 bool __first_constructed;
460 bool __second_constructed;
461
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000462 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000463 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000464 : __na_(__na),
465 __first_constructed(false),
466 __second_constructed(false)
467 {}
468
Howard Hinnant73d21a42010-09-04 23:28:19 +0000469#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000470 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000471 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000472 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000473 : __na_(__x.__na_),
474 __first_constructed(__x.__value_constructed),
475 __second_constructed(__x.__value_constructed)
476 {
477 __x.__value_constructed = false;
478 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000479#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000480 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000481 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
482 : __na_(__x.__na_),
483 __first_constructed(__x.__value_constructed),
484 __second_constructed(__x.__value_constructed)
485 {
486 const_cast<bool&>(__x.__value_constructed) = false;
487 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000488#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000490 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000491 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000492 {
493 if (__second_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000494 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000495 if (__first_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000496 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000497 if (__p)
498 __alloc_traits::deallocate(__na_, __p, 1);
499 }
500};
501
502template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000503class _LIBCPP_VISIBLE __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000504{
505 _HashIterator __i_;
506
507 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
508 typedef const typename _HashIterator::value_type::first_type key_type;
509 typedef typename _HashIterator::value_type::second_type mapped_type;
510public:
511 typedef forward_iterator_tag iterator_category;
512 typedef pair<key_type, mapped_type> value_type;
513 typedef typename _HashIterator::difference_type difference_type;
514 typedef value_type& reference;
515 typedef typename __pointer_traits::template
516#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
517 rebind<value_type>
518#else
519 rebind<value_type>::other
520#endif
521 pointer;
522
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000524 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000526 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000527 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000528
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000530 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000531 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000532 pointer operator->() const {return (pointer)__i_.operator->();}
533
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000535 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000536 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000537 __hash_map_iterator operator++(int)
538 {
539 __hash_map_iterator __t(*this);
540 ++(*this);
541 return __t;
542 }
543
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000544 friend _LIBCPP_INLINE_VISIBILITY
545 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000546 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000547 friend _LIBCPP_INLINE_VISIBILITY
548 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000549 {return __x.__i_ != __y.__i_;}
550
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000551 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
552 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
553 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
554 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
555 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000556};
557
558template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000559class _LIBCPP_VISIBLE __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000560{
561 _HashIterator __i_;
562
563 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
564 typedef const typename _HashIterator::value_type::first_type key_type;
565 typedef typename _HashIterator::value_type::second_type mapped_type;
566public:
567 typedef forward_iterator_tag iterator_category;
568 typedef pair<key_type, mapped_type> value_type;
569 typedef typename _HashIterator::difference_type difference_type;
570 typedef const value_type& reference;
571 typedef typename __pointer_traits::template
572#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000573 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000574#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000575 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000576#endif
577 pointer;
578
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000579 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000580 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000581
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000583 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000585 __hash_map_const_iterator(
586 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000587 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000588 : __i_(__i.__i_) {}
589
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000590 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000591 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000592 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000593 pointer operator->() const {return (pointer)__i_.operator->();}
594
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000595 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000596 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000598 __hash_map_const_iterator operator++(int)
599 {
600 __hash_map_const_iterator __t(*this);
601 ++(*this);
602 return __t;
603 }
604
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000605 friend _LIBCPP_INLINE_VISIBILITY
606 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000607 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000608 friend _LIBCPP_INLINE_VISIBILITY
609 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000610 {return __x.__i_ != __y.__i_;}
611
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000612 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
613 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
614 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
615 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000616};
617
618template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
619 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000620class _LIBCPP_VISIBLE unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000621{
622public:
623 // types
624 typedef _Key key_type;
625 typedef _Tp mapped_type;
626 typedef _Hash hasher;
627 typedef _Pred key_equal;
628 typedef _Alloc allocator_type;
629 typedef pair<const key_type, mapped_type> value_type;
630 typedef value_type& reference;
631 typedef const value_type& const_reference;
632
633private:
634 typedef pair<key_type, mapped_type> __value_type;
635 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
636 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
637 typedef typename allocator_traits<allocator_type>::template
638#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
639 rebind_alloc<__value_type>
640#else
641 rebind_alloc<__value_type>::other
642#endif
643 __allocator_type;
644
645 typedef __hash_table<__value_type, __hasher,
646 __key_equal, __allocator_type> __table;
647
648 __table __table_;
649
650 typedef typename __table::__node_pointer __node_pointer;
651 typedef typename __table::__node_const_pointer __node_const_pointer;
652 typedef typename __table::__node_traits __node_traits;
653 typedef typename __table::__node_allocator __node_allocator;
654 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +0000655 typedef __hash_map_node_destructor<__node_allocator> _Dp;
656 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000657 typedef allocator_traits<allocator_type> __alloc_traits;
658public:
659 typedef typename __alloc_traits::pointer pointer;
660 typedef typename __alloc_traits::const_pointer const_pointer;
661 typedef typename __alloc_traits::size_type size_type;
662 typedef typename __alloc_traits::difference_type difference_type;
663
664 typedef __hash_map_iterator<typename __table::iterator> iterator;
665 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
666 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
667 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
668
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000669 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000670 unordered_map()
671 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
672 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000673 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
674 const key_equal& __eql = key_equal());
675 unordered_map(size_type __n, const hasher& __hf,
676 const key_equal& __eql,
677 const allocator_type& __a);
678 template <class _InputIterator>
679 unordered_map(_InputIterator __first, _InputIterator __last);
680 template <class _InputIterator>
681 unordered_map(_InputIterator __first, _InputIterator __last,
682 size_type __n, const hasher& __hf = hasher(),
683 const key_equal& __eql = key_equal());
684 template <class _InputIterator>
685 unordered_map(_InputIterator __first, _InputIterator __last,
686 size_type __n, const hasher& __hf,
687 const key_equal& __eql,
688 const allocator_type& __a);
689 explicit unordered_map(const allocator_type& __a);
690 unordered_map(const unordered_map& __u);
691 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000692#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000693 unordered_map(unordered_map&& __u)
694 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000695 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000696#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000697#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000698 unordered_map(initializer_list<value_type> __il);
699 unordered_map(initializer_list<value_type> __il, size_type __n,
700 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
701 unordered_map(initializer_list<value_type> __il, size_type __n,
702 const hasher& __hf, const key_equal& __eql,
703 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000704#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000705 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000706 _LIBCPP_INLINE_VISIBILITY
707 unordered_map& operator=(const unordered_map& __u)
708 {
709 __table_ = __u.__table_;
710 return *this;
711 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000712#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000713 unordered_map& operator=(unordered_map&& __u)
714 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000715#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000716#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000717 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000718#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000719
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000721 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000722 {return allocator_type(__table_.__node_alloc());}
723
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000724 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000725 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000726 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000727 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000728 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000729 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000730
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000732 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000733 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000734 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000735 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000736 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000737 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000738 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000739 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000740 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000741 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000742 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000743
Howard Hinnant73d21a42010-09-04 23:28:19 +0000744#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000745 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000746 pair<iterator, bool> emplace()
747 {return __table_.__emplace_unique();}
748
749 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000750 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000751 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000752 pair<iterator, bool> emplace(_A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000753 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000754
Howard Hinnant73d21a42010-09-04 23:28:19 +0000755#ifndef _LIBCPP_HAS_NO_VARIADICS
756
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000757 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000758 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000759 pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args);
760
Howard Hinnant73d21a42010-09-04 23:28:19 +0000761#endif // _LIBCPP_HAS_NO_VARIADICS
762
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000763 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000764 iterator emplace_hint(const_iterator)
765 {return __table_.__emplace_unique().first;}
766
767 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000768 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000769 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000770 iterator emplace_hint(const_iterator, _A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000771 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0)).first;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000772
Howard Hinnant73d21a42010-09-04 23:28:19 +0000773#ifndef _LIBCPP_HAS_NO_VARIADICS
774
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000775 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000776 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000777 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000778 iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000779 {return emplace(_VSTD::forward<_A0>(__a0),
780 _VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000781#endif // _LIBCPP_HAS_NO_VARIADICS
782#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000784 pair<iterator, bool> insert(const value_type& __x)
785 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000786#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000787 template <class _Pp,
788 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000790 pair<iterator, bool> insert(_Pp&& __x)
791 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000792#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000794 iterator insert(const_iterator, const value_type& __x)
795 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000796#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000797 template <class _Pp,
798 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000799 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000800 iterator insert(const_iterator, _Pp&& __x)
801 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000802#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000803 template <class _InputIterator>
804 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000805#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000807 void insert(initializer_list<value_type> __il)
808 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000809#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000810
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000811 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000812 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000813 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000814 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000815 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000816 iterator erase(const_iterator __first, const_iterator __last)
817 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000819 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000820
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000822 void swap(unordered_map& __u)
823 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
824 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000825
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000827 hasher hash_function() const
828 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000829 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000830 key_equal key_eq() const
831 {return __table_.key_eq().key_eq();}
832
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000833 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000834 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000836 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000838 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000839 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000840 pair<iterator, iterator> equal_range(const key_type& __k)
841 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000842 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000843 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
844 {return __table_.__equal_range_unique(__k);}
845
846 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000847#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000848 mapped_type& operator[](key_type&& __k);
849#endif
850
851 mapped_type& at(const key_type& __k);
852 const mapped_type& at(const key_type& __k) const;
853
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000855 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000857 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000858
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000860 size_type bucket_size(size_type __n) const
861 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000863 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
864
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000865 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000866 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000867 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000868 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000869 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000870 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000871 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000872 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000874 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000875 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000876 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
877
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000878 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000879 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000880 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000881 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000883 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000885 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000887 void reserve(size_type __n) {__table_.reserve(__n);}
888
889private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000890#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
891#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000892 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000893 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000894 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000895#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000896 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000897 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000898 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000899#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000900 __node_holder __construct_node(const key_type& __k);
901#endif
902};
903
904template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
905unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
906 size_type __n, const hasher& __hf, const key_equal& __eql)
907 : __table_(__hf, __eql)
908{
909 __table_.rehash(__n);
910}
911
912template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
913unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
914 size_type __n, const hasher& __hf, const key_equal& __eql,
915 const allocator_type& __a)
916 : __table_(__hf, __eql, __a)
917{
918 __table_.rehash(__n);
919}
920
921template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000922inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000923unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
924 const allocator_type& __a)
925 : __table_(__a)
926{
927}
928
929template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
930template <class _InputIterator>
931unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
932 _InputIterator __first, _InputIterator __last)
933{
934 insert(__first, __last);
935}
936
937template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
938template <class _InputIterator>
939unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
940 _InputIterator __first, _InputIterator __last, size_type __n,
941 const hasher& __hf, const key_equal& __eql)
942 : __table_(__hf, __eql)
943{
944 __table_.rehash(__n);
945 insert(__first, __last);
946}
947
948template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
949template <class _InputIterator>
950unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
951 _InputIterator __first, _InputIterator __last, size_type __n,
952 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
953 : __table_(__hf, __eql, __a)
954{
955 __table_.rehash(__n);
956 insert(__first, __last);
957}
958
959template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
960unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
961 const unordered_map& __u)
962 : __table_(__u.__table_)
963{
964 __table_.rehash(__u.bucket_count());
965 insert(__u.begin(), __u.end());
966}
967
968template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
969unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
970 const unordered_map& __u, const allocator_type& __a)
971 : __table_(__u.__table_, __a)
972{
973 __table_.rehash(__u.bucket_count());
974 insert(__u.begin(), __u.end());
975}
976
Howard Hinnant73d21a42010-09-04 23:28:19 +0000977#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000978
979template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000980inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000981unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
982 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000983 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000984 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000985{
986}
987
988template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
989unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
990 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000991 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000992{
993 if (__a != __u.get_allocator())
994 {
995 iterator __i = __u.begin();
996 while (__u.size() != 0)
997 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +0000998 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000999 );
1000 }
1001}
1002
Howard Hinnant73d21a42010-09-04 23:28:19 +00001003#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001004
Howard Hinnante3e32912011-08-12 21:56:02 +00001005#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1006
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001007template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1008unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1009 initializer_list<value_type> __il)
1010{
1011 insert(__il.begin(), __il.end());
1012}
1013
1014template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1015unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1016 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1017 const key_equal& __eql)
1018 : __table_(__hf, __eql)
1019{
1020 __table_.rehash(__n);
1021 insert(__il.begin(), __il.end());
1022}
1023
1024template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1025unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1026 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1027 const key_equal& __eql, const allocator_type& __a)
1028 : __table_(__hf, __eql, __a)
1029{
1030 __table_.rehash(__n);
1031 insert(__il.begin(), __il.end());
1032}
1033
Howard Hinnante3e32912011-08-12 21:56:02 +00001034#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1035
Howard Hinnant73d21a42010-09-04 23:28:19 +00001036#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001037
1038template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001039inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001040unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1041unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001042 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001043{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001044 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001045 return *this;
1046}
1047
Howard Hinnant73d21a42010-09-04 23:28:19 +00001048#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001049
Howard Hinnante3e32912011-08-12 21:56:02 +00001050#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1051
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001052template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001053inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001054unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1055unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1056 initializer_list<value_type> __il)
1057{
1058 __table_.__assign_unique(__il.begin(), __il.end());
1059 return *this;
1060}
1061
Howard Hinnante3e32912011-08-12 21:56:02 +00001062#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1063
Howard Hinnant73d21a42010-09-04 23:28:19 +00001064#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1065#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001066
1067template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1068template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001069 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001070 >
1071typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1072unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1073 _Args&&... __args)
1074{
1075 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001076 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001077 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1078 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001079 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001080 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second),
1081 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001082 __h.get_deleter().__second_constructed = true;
1083 return __h;
1084}
1085
Howard Hinnant73d21a42010-09-04 23:28:19 +00001086#endif // _LIBCPP_HAS_NO_VARIADICS
1087
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001088template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1089template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001090 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001091 >
1092typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1093unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1094{
1095 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001096 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001097 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1098 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001099 __h.get_deleter().__first_constructed = true;
1100 __h.get_deleter().__second_constructed = true;
1101 return __h;
1102}
1103
Howard Hinnant73d21a42010-09-04 23:28:19 +00001104#ifndef _LIBCPP_HAS_NO_VARIADICS
1105
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001106template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1107template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001108 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001109 >
1110pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1111unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1112{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001113 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1114 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001115 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1116 if (__r.second)
1117 __h.release();
1118 return __r;
1119}
1120
Howard Hinnant73d21a42010-09-04 23:28:19 +00001121#endif // _LIBCPP_HAS_NO_VARIADICS
1122#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001123
1124template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1125typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1126unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1127{
1128 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001129 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001130 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001131 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001132 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001133 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001134 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001135}
1136
Howard Hinnant73d21a42010-09-04 23:28:19 +00001137#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001138
1139template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1140template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001141inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001142void
1143unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1144 _InputIterator __last)
1145{
1146 for (; __first != __last; ++__first)
1147 __table_.__insert_unique(*__first);
1148}
1149
1150template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1151_Tp&
1152unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1153{
1154 iterator __i = find(__k);
1155 if (__i != end())
1156 return __i->second;
1157 __node_holder __h = __construct_node(__k);
1158 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1159 __h.release();
1160 return __r.first->second;
1161}
1162
Howard Hinnant73d21a42010-09-04 23:28:19 +00001163#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001164
1165template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1166_Tp&
1167unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1168{
1169 iterator __i = find(__k);
1170 if (__i != end())
1171 return __i->second;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001172 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001173 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1174 __h.release();
1175 return __r.first->second;
1176}
1177
Howard Hinnant73d21a42010-09-04 23:28:19 +00001178#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001179
1180template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1181_Tp&
1182unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1183{
1184 iterator __i = find(__k);
1185#ifndef _LIBCPP_NO_EXCEPTIONS
1186 if (__i == end())
1187 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001188#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001189 return __i->second;
1190}
1191
1192template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1193const _Tp&
1194unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1195{
1196 const_iterator __i = find(__k);
1197#ifndef _LIBCPP_NO_EXCEPTIONS
1198 if (__i == end())
1199 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001200#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001201 return __i->second;
1202}
1203
1204template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001205inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001206void
1207swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1208 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001209 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001210{
1211 __x.swap(__y);
1212}
1213
1214template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1215bool
1216operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1217 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1218{
1219 if (__x.size() != __y.size())
1220 return false;
1221 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1222 const_iterator;
1223 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1224 __i != __ex; ++__i)
1225 {
1226 const_iterator __j = __y.find(__i->first);
1227 if (__j == __ey || !(*__i == *__j))
1228 return false;
1229 }
1230 return true;
1231}
1232
1233template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001234inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001235bool
1236operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1237 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1238{
1239 return !(__x == __y);
1240}
1241
1242template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1243 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001244class _LIBCPP_VISIBLE unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001245{
1246public:
1247 // types
1248 typedef _Key key_type;
1249 typedef _Tp mapped_type;
1250 typedef _Hash hasher;
1251 typedef _Pred key_equal;
1252 typedef _Alloc allocator_type;
1253 typedef pair<const key_type, mapped_type> value_type;
1254 typedef value_type& reference;
1255 typedef const value_type& const_reference;
1256
1257private:
1258 typedef pair<key_type, mapped_type> __value_type;
1259 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
1260 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
1261 typedef typename allocator_traits<allocator_type>::template
1262#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1263 rebind_alloc<__value_type>
1264#else
1265 rebind_alloc<__value_type>::other
1266#endif
1267 __allocator_type;
1268
1269 typedef __hash_table<__value_type, __hasher,
1270 __key_equal, __allocator_type> __table;
1271
1272 __table __table_;
1273
1274 typedef typename __table::__node_traits __node_traits;
1275 typedef typename __table::__node_allocator __node_allocator;
1276 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001277 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1278 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001279 typedef allocator_traits<allocator_type> __alloc_traits;
1280public:
1281 typedef typename __alloc_traits::pointer pointer;
1282 typedef typename __alloc_traits::const_pointer const_pointer;
1283 typedef typename __alloc_traits::size_type size_type;
1284 typedef typename __alloc_traits::difference_type difference_type;
1285
1286 typedef __hash_map_iterator<typename __table::iterator> iterator;
1287 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1288 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1289 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1290
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001291 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001292 unordered_multimap()
1293 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1294 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001295 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1296 const key_equal& __eql = key_equal());
1297 unordered_multimap(size_type __n, const hasher& __hf,
1298 const key_equal& __eql,
1299 const allocator_type& __a);
1300 template <class _InputIterator>
1301 unordered_multimap(_InputIterator __first, _InputIterator __last);
1302 template <class _InputIterator>
1303 unordered_multimap(_InputIterator __first, _InputIterator __last,
1304 size_type __n, const hasher& __hf = hasher(),
1305 const key_equal& __eql = key_equal());
1306 template <class _InputIterator>
1307 unordered_multimap(_InputIterator __first, _InputIterator __last,
1308 size_type __n, const hasher& __hf,
1309 const key_equal& __eql,
1310 const allocator_type& __a);
1311 explicit unordered_multimap(const allocator_type& __a);
1312 unordered_multimap(const unordered_multimap& __u);
1313 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001314#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001315 unordered_multimap(unordered_multimap&& __u)
1316 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001317 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001318#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001319#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001320 unordered_multimap(initializer_list<value_type> __il);
1321 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1322 const hasher& __hf = hasher(),
1323 const key_equal& __eql = key_equal());
1324 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1325 const hasher& __hf, const key_equal& __eql,
1326 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001327#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001328 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001329 _LIBCPP_INLINE_VISIBILITY
1330 unordered_multimap& operator=(const unordered_multimap& __u)
1331 {
1332 __table_ = __u.__table_;
1333 return *this;
1334 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001335#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001336 unordered_multimap& operator=(unordered_multimap&& __u)
1337 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001338#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001339#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001340 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001341#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001342
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001343 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001344 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001345 {return allocator_type(__table_.__node_alloc());}
1346
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001347 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001348 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001349 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001350 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001351 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001352 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001353
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001355 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001356 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001357 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001358 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001359 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001361 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001362 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001363 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001365 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001366
Howard Hinnant73d21a42010-09-04 23:28:19 +00001367#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001368 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001369 iterator emplace()
1370 {return __table_.__emplace_multi();}
1371
1372 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001373 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001374 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001375 iterator emplace(_A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001376 {return __table_.__emplace_multi(_VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001377
Howard Hinnant73d21a42010-09-04 23:28:19 +00001378#ifndef _LIBCPP_HAS_NO_VARIADICS
1379
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001380 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001381 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001382 iterator emplace(_A0&& __a0, _Args&&... __args);
1383
Howard Hinnant73d21a42010-09-04 23:28:19 +00001384#endif // _LIBCPP_HAS_NO_VARIADICS
1385
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001386 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001387 iterator emplace_hint(const_iterator __p)
1388 {return __table_.__emplace_hint_multi(__p.__i_);}
1389
1390 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001391 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001393 iterator emplace_hint(const_iterator __p, _A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001394 {return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001395
Howard Hinnant73d21a42010-09-04 23:28:19 +00001396#ifndef _LIBCPP_HAS_NO_VARIADICS
1397
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001398 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001399 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001400 iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001401#endif // _LIBCPP_HAS_NO_VARIADICS
1402#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001403 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001404 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001405#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001406 template <class _Pp,
1407 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001409 iterator insert(_Pp&& __x)
1410 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001411#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001412 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001413 iterator insert(const_iterator __p, const value_type& __x)
1414 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001415#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001416 template <class _Pp,
1417 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001418 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001419 iterator insert(const_iterator __p, _Pp&& __x)
1420 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001421#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001422 template <class _InputIterator>
1423 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001424#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001426 void insert(initializer_list<value_type> __il)
1427 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001428#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001429
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001430 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001431 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001432 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001433 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001434 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001435 iterator erase(const_iterator __first, const_iterator __last)
1436 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001437 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001438 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001439
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001440 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001441 void swap(unordered_multimap& __u)
1442 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1443 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001444
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001446 hasher hash_function() const
1447 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001448 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001449 key_equal key_eq() const
1450 {return __table_.key_eq().key_eq();}
1451
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001452 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001453 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001454 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001455 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001456 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001457 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001458 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001459 pair<iterator, iterator> equal_range(const key_type& __k)
1460 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001462 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1463 {return __table_.__equal_range_multi(__k);}
1464
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001465 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001466 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001468 size_type max_bucket_count() const _NOEXCEPT
1469 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001470
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001472 size_type bucket_size(size_type __n) const
1473 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001474 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001475 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1476
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001477 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001478 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001479 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001480 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001481 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001482 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001483 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001484 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001485 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001486 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001487 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001488 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1489
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001490 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001491 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001492 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001493 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001494 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001495 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001496 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001497 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001498 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001499 void reserve(size_type __n) {__table_.reserve(__n);}
1500
1501private:
Howard Hinnant73d21a42010-09-04 23:28:19 +00001502#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001503 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001504 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001505 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
1506 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001507 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001508 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001509#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001510};
1511
1512template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1513unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1514 size_type __n, const hasher& __hf, const key_equal& __eql)
1515 : __table_(__hf, __eql)
1516{
1517 __table_.rehash(__n);
1518}
1519
1520template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1521unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1522 size_type __n, const hasher& __hf, const key_equal& __eql,
1523 const allocator_type& __a)
1524 : __table_(__hf, __eql, __a)
1525{
1526 __table_.rehash(__n);
1527}
1528
1529template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1530template <class _InputIterator>
1531unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1532 _InputIterator __first, _InputIterator __last)
1533{
1534 insert(__first, __last);
1535}
1536
1537template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1538template <class _InputIterator>
1539unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1540 _InputIterator __first, _InputIterator __last, size_type __n,
1541 const hasher& __hf, const key_equal& __eql)
1542 : __table_(__hf, __eql)
1543{
1544 __table_.rehash(__n);
1545 insert(__first, __last);
1546}
1547
1548template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1549template <class _InputIterator>
1550unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1551 _InputIterator __first, _InputIterator __last, size_type __n,
1552 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1553 : __table_(__hf, __eql, __a)
1554{
1555 __table_.rehash(__n);
1556 insert(__first, __last);
1557}
1558
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001559template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001560inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001561unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1562 const allocator_type& __a)
1563 : __table_(__a)
1564{
1565}
1566
1567template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1568unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1569 const unordered_multimap& __u)
1570 : __table_(__u.__table_)
1571{
1572 __table_.rehash(__u.bucket_count());
1573 insert(__u.begin(), __u.end());
1574}
1575
1576template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1577unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1578 const unordered_multimap& __u, const allocator_type& __a)
1579 : __table_(__u.__table_, __a)
1580{
1581 __table_.rehash(__u.bucket_count());
1582 insert(__u.begin(), __u.end());
1583}
1584
Howard Hinnant73d21a42010-09-04 23:28:19 +00001585#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001586
1587template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001588inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001589unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1590 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001591 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001592 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001593{
1594}
1595
1596template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1597unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1598 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001599 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001600{
1601 if (__a != __u.get_allocator())
1602 {
1603 iterator __i = __u.begin();
1604 while (__u.size() != 0)
1605{
1606 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001607 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001608 );
1609}
1610 }
1611}
1612
Howard Hinnant73d21a42010-09-04 23:28:19 +00001613#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001614
Howard Hinnante3e32912011-08-12 21:56:02 +00001615#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1616
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001617template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1618unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1619 initializer_list<value_type> __il)
1620{
1621 insert(__il.begin(), __il.end());
1622}
1623
1624template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1625unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1626 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1627 const key_equal& __eql)
1628 : __table_(__hf, __eql)
1629{
1630 __table_.rehash(__n);
1631 insert(__il.begin(), __il.end());
1632}
1633
1634template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1635unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1636 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1637 const key_equal& __eql, const allocator_type& __a)
1638 : __table_(__hf, __eql, __a)
1639{
1640 __table_.rehash(__n);
1641 insert(__il.begin(), __il.end());
1642}
1643
Howard Hinnante3e32912011-08-12 21:56:02 +00001644#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1645
Howard Hinnant73d21a42010-09-04 23:28:19 +00001646#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001647
1648template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001649inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001650unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1651unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001652 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001653{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001654 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001655 return *this;
1656}
1657
Howard Hinnant73d21a42010-09-04 23:28:19 +00001658#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001659
Howard Hinnante3e32912011-08-12 21:56:02 +00001660#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1661
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001662template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001663inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001664unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1665unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1666 initializer_list<value_type> __il)
1667{
1668 __table_.__assign_multi(__il.begin(), __il.end());
1669 return *this;
1670}
1671
Howard Hinnante3e32912011-08-12 21:56:02 +00001672#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1673
Howard Hinnant73d21a42010-09-04 23:28:19 +00001674#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1675#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001676
1677template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1678template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001679 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001680 >
1681typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1682unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1683 _A0&& __a0, _Args&&... __args)
1684{
1685 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001686 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001687 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1688 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001689 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001690 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second),
1691 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001692 __h.get_deleter().__second_constructed = true;
1693 return __h;
1694}
1695
Howard Hinnant73d21a42010-09-04 23:28:19 +00001696#endif // _LIBCPP_HAS_NO_VARIADICS
1697
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001698template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1699template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001700 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001701 >
1702typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1703unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1704{
1705 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001706 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001707 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1708 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001709 __h.get_deleter().__first_constructed = true;
1710 __h.get_deleter().__second_constructed = true;
1711 return __h;
1712}
1713
Howard Hinnant73d21a42010-09-04 23:28:19 +00001714#ifndef _LIBCPP_HAS_NO_VARIADICS
1715
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001716template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1717template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001718 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001719 >
1720typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1721unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1722{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001723 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1724 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001725 iterator __r = __table_.__node_insert_multi(__h.get());
1726 __h.release();
1727 return __r;
1728}
1729
1730template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1731template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001732 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001733 >
1734typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1735unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1736 const_iterator __p, _A0&& __a0, _Args&&... __args)
1737{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001738 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1739 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001740 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1741 __h.release();
1742 return __r;
1743}
1744
Howard Hinnant73d21a42010-09-04 23:28:19 +00001745#endif // _LIBCPP_HAS_NO_VARIADICS
1746#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001747
1748template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1749template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001750inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001751void
1752unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1753 _InputIterator __last)
1754{
1755 for (; __first != __last; ++__first)
1756 __table_.__insert_multi(*__first);
1757}
1758
1759template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001760inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001761void
1762swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1763 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001764 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001765{
1766 __x.swap(__y);
1767}
1768
1769template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1770bool
1771operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1772 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1773{
1774 if (__x.size() != __y.size())
1775 return false;
1776 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1777 const_iterator;
1778 typedef pair<const_iterator, const_iterator> _EqRng;
1779 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1780 {
1781 _EqRng __xeq = __x.equal_range(__i->first);
1782 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001783 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1784 _VSTD::distance(__yeq.first, __yeq.second) ||
1785 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001786 return false;
1787 __i = __xeq.second;
1788 }
1789 return true;
1790}
1791
1792template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001793inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001794bool
1795operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1796 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1797{
1798 return !(__x == __y);
1799}
1800
1801_LIBCPP_END_NAMESPACE_STD
1802
1803#endif // _LIBCPP_UNORDERED_MAP