blob: cb30fc87d698d2f56fd0a03f7375f747408492c4 [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
322#pragma GCC system_header
323
324_LIBCPP_BEGIN_NAMESPACE_STD
325
326template <class _Tp, class _Hash, bool = is_empty<_Hash>::value>
327class __unordered_map_hasher
328 : private _Hash
329{
330public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000331 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000332 __unordered_map_hasher()
333 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
334 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000336 __unordered_map_hasher(const _Hash& __h)
337 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
338 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000340 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000342 size_t operator()(const _Tp& __x) const
343 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000344 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000345 size_t operator()(const typename _Tp::first_type& __x) const
346 {return static_cast<const _Hash&>(*this)(__x);}
347};
348
349template <class _Tp, class _Hash>
350class __unordered_map_hasher<_Tp, _Hash, false>
351{
352 _Hash __hash_;
353public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000355 __unordered_map_hasher()
356 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
357 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000358 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000359 __unordered_map_hasher(const _Hash& __h)
360 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
361 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000362 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000363 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000365 size_t operator()(const _Tp& __x) const
366 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000367 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000368 size_t operator()(const typename _Tp::first_type& __x) const
369 {return __hash_(__x);}
370};
371
372template <class _Tp, class _Pred, bool = is_empty<_Pred>::value>
373class __unordered_map_equal
374 : private _Pred
375{
376public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000377 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000378 __unordered_map_equal()
379 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
380 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000381 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000382 __unordered_map_equal(const _Pred& __p)
383 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
384 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000385 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000386 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000387 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000388 bool operator()(const _Tp& __x, const _Tp& __y) const
389 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000390 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000391 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
392 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000393 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000394 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
395 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant324bb032010-08-22 00:02:43 +0000397 bool operator()(const typename _Tp::first_type& __x,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000398 const typename _Tp::first_type& __y) const
399 {return static_cast<const _Pred&>(*this)(__x, __y);}
400};
401
402template <class _Tp, class _Pred>
403class __unordered_map_equal<_Tp, _Pred, false>
404{
405 _Pred __pred_;
406public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000407 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000408 __unordered_map_equal()
409 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
410 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000411 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000412 __unordered_map_equal(const _Pred& __p)
413 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
414 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000416 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000418 bool operator()(const _Tp& __x, const _Tp& __y) const
419 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000420 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000421 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
422 {return __pred_(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000424 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
425 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000427 bool operator()(const typename _Tp::first_type& __x,
428 const typename _Tp::first_type& __y) const
429 {return __pred_(__x, __y);}
430};
431
432template <class _Alloc>
433class __hash_map_node_destructor
434{
435 typedef _Alloc allocator_type;
436 typedef allocator_traits<allocator_type> __alloc_traits;
437 typedef typename __alloc_traits::value_type::value_type value_type;
438public:
439 typedef typename __alloc_traits::pointer pointer;
440private:
441 typedef typename value_type::first_type first_type;
442 typedef typename value_type::second_type second_type;
443
444 allocator_type& __na_;
445
446 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
447
448public:
449 bool __first_constructed;
450 bool __second_constructed;
451
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000452 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000453 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000454 : __na_(__na),
455 __first_constructed(false),
456 __second_constructed(false)
457 {}
458
Howard Hinnant73d21a42010-09-04 23:28:19 +0000459#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000461 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000462 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000463 : __na_(__x.__na_),
464 __first_constructed(__x.__value_constructed),
465 __second_constructed(__x.__value_constructed)
466 {
467 __x.__value_constructed = false;
468 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000469#else // _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(const __hash_node_destructor<allocator_type>& __x)
472 : __na_(__x.__na_),
473 __first_constructed(__x.__value_constructed),
474 __second_constructed(__x.__value_constructed)
475 {
476 const_cast<bool&>(__x.__value_constructed) = false;
477 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000478#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000479
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000480 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000481 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000482 {
483 if (__second_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000484 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000485 if (__first_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000486 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000487 if (__p)
488 __alloc_traits::deallocate(__na_, __p, 1);
489 }
490};
491
492template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000493class _LIBCPP_VISIBLE __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000494{
495 _HashIterator __i_;
496
497 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
498 typedef const typename _HashIterator::value_type::first_type key_type;
499 typedef typename _HashIterator::value_type::second_type mapped_type;
500public:
501 typedef forward_iterator_tag iterator_category;
502 typedef pair<key_type, mapped_type> value_type;
503 typedef typename _HashIterator::difference_type difference_type;
504 typedef value_type& reference;
505 typedef typename __pointer_traits::template
506#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
507 rebind<value_type>
508#else
509 rebind<value_type>::other
510#endif
511 pointer;
512
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000513 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000514 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000515
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000516 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000517 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000518
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000520 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000522 pointer operator->() const {return (pointer)__i_.operator->();}
523
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000526 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527 __hash_map_iterator operator++(int)
528 {
529 __hash_map_iterator __t(*this);
530 ++(*this);
531 return __t;
532 }
533
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000534 friend _LIBCPP_INLINE_VISIBILITY
535 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000536 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000537 friend _LIBCPP_INLINE_VISIBILITY
538 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000539 {return __x.__i_ != __y.__i_;}
540
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000541 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
542 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
543 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
544 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
545 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000546};
547
548template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000549class _LIBCPP_VISIBLE __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000550{
551 _HashIterator __i_;
552
553 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
554 typedef const typename _HashIterator::value_type::first_type key_type;
555 typedef typename _HashIterator::value_type::second_type mapped_type;
556public:
557 typedef forward_iterator_tag iterator_category;
558 typedef pair<key_type, mapped_type> value_type;
559 typedef typename _HashIterator::difference_type difference_type;
560 typedef const value_type& reference;
561 typedef typename __pointer_traits::template
562#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000563 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000564#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000565 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000566#endif
567 pointer;
568
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000569 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000570 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000571
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000573 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000575 __hash_map_const_iterator(
576 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000577 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000578 : __i_(__i.__i_) {}
579
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000581 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 pointer operator->() const {return (pointer)__i_.operator->();}
584
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000585 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000586 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000588 __hash_map_const_iterator operator++(int)
589 {
590 __hash_map_const_iterator __t(*this);
591 ++(*this);
592 return __t;
593 }
594
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000595 friend _LIBCPP_INLINE_VISIBILITY
596 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000597 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000598 friend _LIBCPP_INLINE_VISIBILITY
599 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000600 {return __x.__i_ != __y.__i_;}
601
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000602 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
603 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
604 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
605 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000606};
607
608template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
609 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000610class _LIBCPP_VISIBLE unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000611{
612public:
613 // types
614 typedef _Key key_type;
615 typedef _Tp mapped_type;
616 typedef _Hash hasher;
617 typedef _Pred key_equal;
618 typedef _Alloc allocator_type;
619 typedef pair<const key_type, mapped_type> value_type;
620 typedef value_type& reference;
621 typedef const value_type& const_reference;
622
623private:
624 typedef pair<key_type, mapped_type> __value_type;
625 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
626 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
627 typedef typename allocator_traits<allocator_type>::template
628#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
629 rebind_alloc<__value_type>
630#else
631 rebind_alloc<__value_type>::other
632#endif
633 __allocator_type;
634
635 typedef __hash_table<__value_type, __hasher,
636 __key_equal, __allocator_type> __table;
637
638 __table __table_;
639
640 typedef typename __table::__node_pointer __node_pointer;
641 typedef typename __table::__node_const_pointer __node_const_pointer;
642 typedef typename __table::__node_traits __node_traits;
643 typedef typename __table::__node_allocator __node_allocator;
644 typedef typename __table::__node __node;
645 typedef __hash_map_node_destructor<__node_allocator> _D;
646 typedef unique_ptr<__node, _D> __node_holder;
647 typedef allocator_traits<allocator_type> __alloc_traits;
648public:
649 typedef typename __alloc_traits::pointer pointer;
650 typedef typename __alloc_traits::const_pointer const_pointer;
651 typedef typename __alloc_traits::size_type size_type;
652 typedef typename __alloc_traits::difference_type difference_type;
653
654 typedef __hash_map_iterator<typename __table::iterator> iterator;
655 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
656 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
657 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
658
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000659 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000660 unordered_map()
661 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
662 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000663 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
664 const key_equal& __eql = key_equal());
665 unordered_map(size_type __n, const hasher& __hf,
666 const key_equal& __eql,
667 const allocator_type& __a);
668 template <class _InputIterator>
669 unordered_map(_InputIterator __first, _InputIterator __last);
670 template <class _InputIterator>
671 unordered_map(_InputIterator __first, _InputIterator __last,
672 size_type __n, const hasher& __hf = hasher(),
673 const key_equal& __eql = key_equal());
674 template <class _InputIterator>
675 unordered_map(_InputIterator __first, _InputIterator __last,
676 size_type __n, const hasher& __hf,
677 const key_equal& __eql,
678 const allocator_type& __a);
679 explicit unordered_map(const allocator_type& __a);
680 unordered_map(const unordered_map& __u);
681 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000682#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000683 unordered_map(unordered_map&& __u)
684 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000685 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000686#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000687#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000688 unordered_map(initializer_list<value_type> __il);
689 unordered_map(initializer_list<value_type> __il, size_type __n,
690 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
691 unordered_map(initializer_list<value_type> __il, size_type __n,
692 const hasher& __hf, const key_equal& __eql,
693 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000694#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000695 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000696 _LIBCPP_INLINE_VISIBILITY
697 unordered_map& operator=(const unordered_map& __u)
698 {
699 __table_ = __u.__table_;
700 return *this;
701 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000702#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000703 unordered_map& operator=(unordered_map&& __u)
704 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000705#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000706#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000707 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000708#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000709
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000710 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000711 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000712 {return allocator_type(__table_.__node_alloc());}
713
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000714 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000715 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000716 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000717 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000719 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000720
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000721 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000722 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000723 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000724 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000726 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000727 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000728 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000729 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000730 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000732 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000733
Howard Hinnant73d21a42010-09-04 23:28:19 +0000734#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000735 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000736 pair<iterator, bool> emplace()
737 {return __table_.__emplace_unique();}
738
739 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000740 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000741 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000742 pair<iterator, bool> emplace(_A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000743 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000744
Howard Hinnant73d21a42010-09-04 23:28:19 +0000745#ifndef _LIBCPP_HAS_NO_VARIADICS
746
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000747 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000748 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000749 pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args);
750
Howard Hinnant73d21a42010-09-04 23:28:19 +0000751#endif // _LIBCPP_HAS_NO_VARIADICS
752
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000753 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000754 iterator emplace_hint(const_iterator)
755 {return __table_.__emplace_unique().first;}
756
757 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000758 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000759 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000760 iterator emplace_hint(const_iterator, _A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000761 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0)).first;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000762
Howard Hinnant73d21a42010-09-04 23:28:19 +0000763#ifndef _LIBCPP_HAS_NO_VARIADICS
764
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000765 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000766 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000767 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000768 iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000769 {return emplace(_VSTD::forward<_A0>(__a0),
770 _VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000771#endif // _LIBCPP_HAS_NO_VARIADICS
772#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000773 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000774 pair<iterator, bool> insert(const value_type& __x)
775 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000776#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000777 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000778 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000779 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000780 pair<iterator, bool> insert(_P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000781 {return __table_.__insert_unique(_VSTD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000782#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 iterator insert(const_iterator, const value_type& __x)
785 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000786#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000787 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000788 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000790 iterator insert(const_iterator, _P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000791 {return insert(_VSTD::forward<_P>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000792#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000793 template <class _InputIterator>
794 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000795#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000796 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000797 void insert(initializer_list<value_type> __il)
798 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000799#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000800
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000801 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000802 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000804 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000806 iterator erase(const_iterator __first, const_iterator __last)
807 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000808 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000809 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000810
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000811 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000812 void swap(unordered_map& __u)
813 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
814 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000815
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000817 hasher hash_function() const
818 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000820 key_equal key_eq() const
821 {return __table_.key_eq().key_eq();}
822
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000823 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000824 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000825 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000826 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000827 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000828 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000829 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000830 pair<iterator, iterator> equal_range(const key_type& __k)
831 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000832 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000833 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
834 {return __table_.__equal_range_unique(__k);}
835
836 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000837#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000838 mapped_type& operator[](key_type&& __k);
839#endif
840
841 mapped_type& at(const key_type& __k);
842 const mapped_type& at(const key_type& __k) const;
843
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000844 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000845 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000846 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000847 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000848
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000849 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000850 size_type bucket_size(size_type __n) const
851 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000852 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000853 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
854
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000855 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000856 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000857 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000858 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000860 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000864 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000865 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000866 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
867
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000869 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000870 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000871 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000872 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000873 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000874 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000875 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000876 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000877 void reserve(size_type __n) {__table_.reserve(__n);}
878
879private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000880#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
881#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000882 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000883 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000884 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000885#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000886 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000887 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000888 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000889#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000890 __node_holder __construct_node(const key_type& __k);
891#endif
892};
893
894template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
895unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
896 size_type __n, const hasher& __hf, const key_equal& __eql)
897 : __table_(__hf, __eql)
898{
899 __table_.rehash(__n);
900}
901
902template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
903unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
904 size_type __n, const hasher& __hf, const key_equal& __eql,
905 const allocator_type& __a)
906 : __table_(__hf, __eql, __a)
907{
908 __table_.rehash(__n);
909}
910
911template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000912inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000913unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
914 const allocator_type& __a)
915 : __table_(__a)
916{
917}
918
919template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
920template <class _InputIterator>
921unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
922 _InputIterator __first, _InputIterator __last)
923{
924 insert(__first, __last);
925}
926
927template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
928template <class _InputIterator>
929unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
930 _InputIterator __first, _InputIterator __last, size_type __n,
931 const hasher& __hf, const key_equal& __eql)
932 : __table_(__hf, __eql)
933{
934 __table_.rehash(__n);
935 insert(__first, __last);
936}
937
938template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
939template <class _InputIterator>
940unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
941 _InputIterator __first, _InputIterator __last, size_type __n,
942 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
943 : __table_(__hf, __eql, __a)
944{
945 __table_.rehash(__n);
946 insert(__first, __last);
947}
948
949template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
950unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
951 const unordered_map& __u)
952 : __table_(__u.__table_)
953{
954 __table_.rehash(__u.bucket_count());
955 insert(__u.begin(), __u.end());
956}
957
958template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
959unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
960 const unordered_map& __u, const allocator_type& __a)
961 : __table_(__u.__table_, __a)
962{
963 __table_.rehash(__u.bucket_count());
964 insert(__u.begin(), __u.end());
965}
966
Howard Hinnant73d21a42010-09-04 23:28:19 +0000967#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000968
969template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000970inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000971unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
972 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000973 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000974 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000975{
976}
977
978template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
979unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
980 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000981 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000982{
983 if (__a != __u.get_allocator())
984 {
985 iterator __i = __u.begin();
986 while (__u.size() != 0)
987 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +0000988 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000989 );
990 }
991}
992
Howard Hinnant73d21a42010-09-04 23:28:19 +0000993#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000994
Howard Hinnante3e32912011-08-12 21:56:02 +0000995#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
996
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000997template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
998unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
999 initializer_list<value_type> __il)
1000{
1001 insert(__il.begin(), __il.end());
1002}
1003
1004template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1005unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1006 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1007 const key_equal& __eql)
1008 : __table_(__hf, __eql)
1009{
1010 __table_.rehash(__n);
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, const allocator_type& __a)
1018 : __table_(__hf, __eql, __a)
1019{
1020 __table_.rehash(__n);
1021 insert(__il.begin(), __il.end());
1022}
1023
Howard Hinnante3e32912011-08-12 21:56:02 +00001024#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1025
Howard Hinnant73d21a42010-09-04 23:28:19 +00001026#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001027
1028template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001029inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001030unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1031unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001032 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001033{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001034 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001035 return *this;
1036}
1037
Howard Hinnant73d21a42010-09-04 23:28:19 +00001038#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001039
Howard Hinnante3e32912011-08-12 21:56:02 +00001040#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1041
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001042template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001043inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001044unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1045unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1046 initializer_list<value_type> __il)
1047{
1048 __table_.__assign_unique(__il.begin(), __il.end());
1049 return *this;
1050}
1051
Howard Hinnante3e32912011-08-12 21:56:02 +00001052#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1053
Howard Hinnant73d21a42010-09-04 23:28:19 +00001054#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1055#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001056
1057template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1058template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001059 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001060 >
1061typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1062unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1063 _Args&&... __args)
1064{
1065 __node_allocator& __na = __table_.__node_alloc();
1066 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001067 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1068 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001069 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001070 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second),
1071 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001072 __h.get_deleter().__second_constructed = true;
1073 return __h;
1074}
1075
Howard Hinnant73d21a42010-09-04 23:28:19 +00001076#endif // _LIBCPP_HAS_NO_VARIADICS
1077
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001078template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1079template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001080 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001081 >
1082typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1083unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1084{
1085 __node_allocator& __na = __table_.__node_alloc();
1086 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001087 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1088 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001089 __h.get_deleter().__first_constructed = true;
1090 __h.get_deleter().__second_constructed = true;
1091 return __h;
1092}
1093
Howard Hinnant73d21a42010-09-04 23:28:19 +00001094#ifndef _LIBCPP_HAS_NO_VARIADICS
1095
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001096template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1097template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001098 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001099 >
1100pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1101unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1102{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001103 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1104 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001105 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1106 if (__r.second)
1107 __h.release();
1108 return __r;
1109}
1110
Howard Hinnant73d21a42010-09-04 23:28:19 +00001111#endif // _LIBCPP_HAS_NO_VARIADICS
1112#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001113
1114template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1115typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1116unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1117{
1118 __node_allocator& __na = __table_.__node_alloc();
1119 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001120 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001121 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001122 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001123 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001124 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001125}
1126
Howard Hinnant73d21a42010-09-04 23:28:19 +00001127#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001128
1129template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1130template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001131inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001132void
1133unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1134 _InputIterator __last)
1135{
1136 for (; __first != __last; ++__first)
1137 __table_.__insert_unique(*__first);
1138}
1139
1140template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1141_Tp&
1142unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1143{
1144 iterator __i = find(__k);
1145 if (__i != end())
1146 return __i->second;
1147 __node_holder __h = __construct_node(__k);
1148 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1149 __h.release();
1150 return __r.first->second;
1151}
1152
Howard Hinnant73d21a42010-09-04 23:28:19 +00001153#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001154
1155template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1156_Tp&
1157unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1158{
1159 iterator __i = find(__k);
1160 if (__i != end())
1161 return __i->second;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001162 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001163 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1164 __h.release();
1165 return __r.first->second;
1166}
1167
Howard Hinnant73d21a42010-09-04 23:28:19 +00001168#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001169
1170template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1171_Tp&
1172unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1173{
1174 iterator __i = find(__k);
1175#ifndef _LIBCPP_NO_EXCEPTIONS
1176 if (__i == end())
1177 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001178#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001179 return __i->second;
1180}
1181
1182template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1183const _Tp&
1184unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1185{
1186 const_iterator __i = find(__k);
1187#ifndef _LIBCPP_NO_EXCEPTIONS
1188 if (__i == end())
1189 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001190#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001191 return __i->second;
1192}
1193
1194template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001195inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001196void
1197swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1198 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001199 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001200{
1201 __x.swap(__y);
1202}
1203
1204template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1205bool
1206operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1207 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1208{
1209 if (__x.size() != __y.size())
1210 return false;
1211 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1212 const_iterator;
1213 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1214 __i != __ex; ++__i)
1215 {
1216 const_iterator __j = __y.find(__i->first);
1217 if (__j == __ey || !(*__i == *__j))
1218 return false;
1219 }
1220 return true;
1221}
1222
1223template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001224inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001225bool
1226operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1227 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1228{
1229 return !(__x == __y);
1230}
1231
1232template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1233 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001234class _LIBCPP_VISIBLE unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001235{
1236public:
1237 // types
1238 typedef _Key key_type;
1239 typedef _Tp mapped_type;
1240 typedef _Hash hasher;
1241 typedef _Pred key_equal;
1242 typedef _Alloc allocator_type;
1243 typedef pair<const key_type, mapped_type> value_type;
1244 typedef value_type& reference;
1245 typedef const value_type& const_reference;
1246
1247private:
1248 typedef pair<key_type, mapped_type> __value_type;
1249 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
1250 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
1251 typedef typename allocator_traits<allocator_type>::template
1252#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1253 rebind_alloc<__value_type>
1254#else
1255 rebind_alloc<__value_type>::other
1256#endif
1257 __allocator_type;
1258
1259 typedef __hash_table<__value_type, __hasher,
1260 __key_equal, __allocator_type> __table;
1261
1262 __table __table_;
1263
1264 typedef typename __table::__node_traits __node_traits;
1265 typedef typename __table::__node_allocator __node_allocator;
1266 typedef typename __table::__node __node;
1267 typedef __hash_map_node_destructor<__node_allocator> _D;
1268 typedef unique_ptr<__node, _D> __node_holder;
1269 typedef allocator_traits<allocator_type> __alloc_traits;
1270public:
1271 typedef typename __alloc_traits::pointer pointer;
1272 typedef typename __alloc_traits::const_pointer const_pointer;
1273 typedef typename __alloc_traits::size_type size_type;
1274 typedef typename __alloc_traits::difference_type difference_type;
1275
1276 typedef __hash_map_iterator<typename __table::iterator> iterator;
1277 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1278 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1279 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1280
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001281 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001282 unordered_multimap()
1283 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1284 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001285 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1286 const key_equal& __eql = key_equal());
1287 unordered_multimap(size_type __n, const hasher& __hf,
1288 const key_equal& __eql,
1289 const allocator_type& __a);
1290 template <class _InputIterator>
1291 unordered_multimap(_InputIterator __first, _InputIterator __last);
1292 template <class _InputIterator>
1293 unordered_multimap(_InputIterator __first, _InputIterator __last,
1294 size_type __n, const hasher& __hf = hasher(),
1295 const key_equal& __eql = key_equal());
1296 template <class _InputIterator>
1297 unordered_multimap(_InputIterator __first, _InputIterator __last,
1298 size_type __n, const hasher& __hf,
1299 const key_equal& __eql,
1300 const allocator_type& __a);
1301 explicit unordered_multimap(const allocator_type& __a);
1302 unordered_multimap(const unordered_multimap& __u);
1303 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001304#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001305 unordered_multimap(unordered_multimap&& __u)
1306 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001307 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001308#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001309#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001310 unordered_multimap(initializer_list<value_type> __il);
1311 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1312 const hasher& __hf = hasher(),
1313 const key_equal& __eql = key_equal());
1314 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1315 const hasher& __hf, const key_equal& __eql,
1316 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001317#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001318 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001319 _LIBCPP_INLINE_VISIBILITY
1320 unordered_multimap& operator=(const unordered_multimap& __u)
1321 {
1322 __table_ = __u.__table_;
1323 return *this;
1324 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001325#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001326 unordered_multimap& operator=(unordered_multimap&& __u)
1327 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001328#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001329#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001330 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001331#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001332
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001333 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001334 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001335 {return allocator_type(__table_.__node_alloc());}
1336
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001337 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001338 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001340 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001342 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001343
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001344 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001345 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001346 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001347 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001349 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001350 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001351 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001353 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001355 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001356
Howard Hinnant73d21a42010-09-04 23:28:19 +00001357#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001358 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001359 iterator emplace()
1360 {return __table_.__emplace_multi();}
1361
1362 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001363 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001365 iterator emplace(_A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001366 {return __table_.__emplace_multi(_VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001367
Howard Hinnant73d21a42010-09-04 23:28:19 +00001368#ifndef _LIBCPP_HAS_NO_VARIADICS
1369
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001370 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001371 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001372 iterator emplace(_A0&& __a0, _Args&&... __args);
1373
Howard Hinnant73d21a42010-09-04 23:28:19 +00001374#endif // _LIBCPP_HAS_NO_VARIADICS
1375
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001376 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001377 iterator emplace_hint(const_iterator __p)
1378 {return __table_.__emplace_hint_multi(__p.__i_);}
1379
1380 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001381 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001382 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001383 iterator emplace_hint(const_iterator __p, _A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001384 {return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001385
Howard Hinnant73d21a42010-09-04 23:28:19 +00001386#ifndef _LIBCPP_HAS_NO_VARIADICS
1387
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001388 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001389 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001390 iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001391#endif // _LIBCPP_HAS_NO_VARIADICS
1392#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001393 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001394 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001395#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001396 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001397 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001398 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001399 iterator insert(_P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001400 {return __table_.__insert_multi(_VSTD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001401#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001402 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001403 iterator insert(const_iterator __p, const value_type& __x)
1404 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001405#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001406 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001407 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001409 iterator insert(const_iterator __p, _P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001410 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001411#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001412 template <class _InputIterator>
1413 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001414#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001416 void insert(initializer_list<value_type> __il)
1417 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001418#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001419
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001420 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001421 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001422 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001423 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001424 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001425 iterator erase(const_iterator __first, const_iterator __last)
1426 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001428 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001429
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001430 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001431 void swap(unordered_multimap& __u)
1432 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1433 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001434
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001435 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001436 hasher hash_function() const
1437 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001438 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001439 key_equal key_eq() const
1440 {return __table_.key_eq().key_eq();}
1441
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001442 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001443 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001444 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001445 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001446 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001447 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001448 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001449 pair<iterator, iterator> equal_range(const key_type& __k)
1450 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001451 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001452 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1453 {return __table_.__equal_range_multi(__k);}
1454
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001456 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001458 size_type max_bucket_count() const _NOEXCEPT
1459 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001460
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001462 size_type bucket_size(size_type __n) const
1463 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001464 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001465 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1466
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001468 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001469 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001470 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001472 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001473 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001474 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001475 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001476 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001477 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001478 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1479
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001480 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001481 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001482 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001483 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001484 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001485 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001486 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001487 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001489 void reserve(size_type __n) {__table_.reserve(__n);}
1490
1491private:
Howard Hinnant73d21a42010-09-04 23:28:19 +00001492#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001493 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001494 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001495 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
1496 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001497 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001498 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001499#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001500};
1501
1502template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1503unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1504 size_type __n, const hasher& __hf, const key_equal& __eql)
1505 : __table_(__hf, __eql)
1506{
1507 __table_.rehash(__n);
1508}
1509
1510template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1511unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1512 size_type __n, const hasher& __hf, const key_equal& __eql,
1513 const allocator_type& __a)
1514 : __table_(__hf, __eql, __a)
1515{
1516 __table_.rehash(__n);
1517}
1518
1519template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1520template <class _InputIterator>
1521unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1522 _InputIterator __first, _InputIterator __last)
1523{
1524 insert(__first, __last);
1525}
1526
1527template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1528template <class _InputIterator>
1529unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1530 _InputIterator __first, _InputIterator __last, size_type __n,
1531 const hasher& __hf, const key_equal& __eql)
1532 : __table_(__hf, __eql)
1533{
1534 __table_.rehash(__n);
1535 insert(__first, __last);
1536}
1537
1538template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1539template <class _InputIterator>
1540unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1541 _InputIterator __first, _InputIterator __last, size_type __n,
1542 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1543 : __table_(__hf, __eql, __a)
1544{
1545 __table_.rehash(__n);
1546 insert(__first, __last);
1547}
1548
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001549template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001550inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001551unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1552 const allocator_type& __a)
1553 : __table_(__a)
1554{
1555}
1556
1557template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1558unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1559 const unordered_multimap& __u)
1560 : __table_(__u.__table_)
1561{
1562 __table_.rehash(__u.bucket_count());
1563 insert(__u.begin(), __u.end());
1564}
1565
1566template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1567unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1568 const unordered_multimap& __u, const allocator_type& __a)
1569 : __table_(__u.__table_, __a)
1570{
1571 __table_.rehash(__u.bucket_count());
1572 insert(__u.begin(), __u.end());
1573}
1574
Howard Hinnant73d21a42010-09-04 23:28:19 +00001575#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001576
1577template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001578inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001579unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1580 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001581 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001582 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001583{
1584}
1585
1586template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1587unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1588 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001589 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001590{
1591 if (__a != __u.get_allocator())
1592 {
1593 iterator __i = __u.begin();
1594 while (__u.size() != 0)
1595{
1596 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001597 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001598 );
1599}
1600 }
1601}
1602
Howard Hinnant73d21a42010-09-04 23:28:19 +00001603#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001604
Howard Hinnante3e32912011-08-12 21:56:02 +00001605#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1606
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001607template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1608unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1609 initializer_list<value_type> __il)
1610{
1611 insert(__il.begin(), __il.end());
1612}
1613
1614template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1615unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1616 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1617 const key_equal& __eql)
1618 : __table_(__hf, __eql)
1619{
1620 __table_.rehash(__n);
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, const allocator_type& __a)
1628 : __table_(__hf, __eql, __a)
1629{
1630 __table_.rehash(__n);
1631 insert(__il.begin(), __il.end());
1632}
1633
Howard Hinnante3e32912011-08-12 21:56:02 +00001634#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1635
Howard Hinnant73d21a42010-09-04 23:28:19 +00001636#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001637
1638template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001639inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001640unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1641unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001642 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001643{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001644 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001645 return *this;
1646}
1647
Howard Hinnant73d21a42010-09-04 23:28:19 +00001648#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001649
Howard Hinnante3e32912011-08-12 21:56:02 +00001650#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1651
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001652template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001653inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001654unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1655unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1656 initializer_list<value_type> __il)
1657{
1658 __table_.__assign_multi(__il.begin(), __il.end());
1659 return *this;
1660}
1661
Howard Hinnante3e32912011-08-12 21:56:02 +00001662#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1663
Howard Hinnant73d21a42010-09-04 23:28:19 +00001664#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1665#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001666
1667template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1668template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001669 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001670 >
1671typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1672unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1673 _A0&& __a0, _Args&&... __args)
1674{
1675 __node_allocator& __na = __table_.__node_alloc();
1676 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001677 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1678 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001679 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001680 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second),
1681 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001682 __h.get_deleter().__second_constructed = true;
1683 return __h;
1684}
1685
Howard Hinnant73d21a42010-09-04 23:28:19 +00001686#endif // _LIBCPP_HAS_NO_VARIADICS
1687
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001688template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1689template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001690 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001691 >
1692typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1693unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1694{
1695 __node_allocator& __na = __table_.__node_alloc();
1696 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001697 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1698 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001699 __h.get_deleter().__first_constructed = true;
1700 __h.get_deleter().__second_constructed = true;
1701 return __h;
1702}
1703
Howard Hinnant73d21a42010-09-04 23:28:19 +00001704#ifndef _LIBCPP_HAS_NO_VARIADICS
1705
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001706template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1707template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001708 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001709 >
1710typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1711unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1712{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001713 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1714 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001715 iterator __r = __table_.__node_insert_multi(__h.get());
1716 __h.release();
1717 return __r;
1718}
1719
1720template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1721template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001722 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001723 >
1724typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1725unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1726 const_iterator __p, _A0&& __a0, _Args&&... __args)
1727{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001728 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1729 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001730 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1731 __h.release();
1732 return __r;
1733}
1734
Howard Hinnant73d21a42010-09-04 23:28:19 +00001735#endif // _LIBCPP_HAS_NO_VARIADICS
1736#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001737
1738template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1739template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001740inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001741void
1742unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1743 _InputIterator __last)
1744{
1745 for (; __first != __last; ++__first)
1746 __table_.__insert_multi(*__first);
1747}
1748
1749template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001750inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001751void
1752swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1753 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001754 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001755{
1756 __x.swap(__y);
1757}
1758
1759template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1760bool
1761operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1762 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1763{
1764 if (__x.size() != __y.size())
1765 return false;
1766 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1767 const_iterator;
1768 typedef pair<const_iterator, const_iterator> _EqRng;
1769 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1770 {
1771 _EqRng __xeq = __x.equal_range(__i->first);
1772 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001773 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1774 _VSTD::distance(__yeq.first, __yeq.second) ||
1775 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001776 return false;
1777 __i = __xeq.second;
1778 }
1779 return true;
1780}
1781
1782template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001783inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001784bool
1785operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1786 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1787{
1788 return !(__x == __y);
1789}
1790
1791_LIBCPP_END_NAMESPACE_STD
1792
1793#endif // _LIBCPP_UNORDERED_MAP