blob: cc30d7634245fdabc13a5461473cca546450c56f [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UNORDERED_MAP
12#define _LIBCPP_UNORDERED_MAP
13
14/*
15
16 unordered_map synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
24 class Alloc = allocator<pair<const Key, T>>>
25class unordered_map
26{
27public:
28 // types
29 typedef Key key_type;
30 typedef T mapped_type;
31 typedef Hash hasher;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef pair<const key_type, mapped_type> value_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000047 unordered_map()
48 noexcept(
49 is_nothrow_default_constructible<hasher>::value &&
50 is_nothrow_default_constructible<key_equal>::value &&
51 is_nothrow_default_constructible<allocator_type>::value);
52 explicit unordered_map(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000053 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 template <class InputIterator>
56 unordered_map(InputIterator f, InputIterator l,
57 size_type n = 0, const hasher& hf = hasher(),
58 const key_equal& eql = key_equal(),
59 const allocator_type& a = allocator_type());
60 explicit unordered_map(const allocator_type&);
61 unordered_map(const unordered_map&);
62 unordered_map(const unordered_map&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000063 unordered_map(unordered_map&&)
64 noexcept(
65 is_nothrow_move_constructible<hasher>::value &&
66 is_nothrow_move_constructible<key_equal>::value &&
67 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000068 unordered_map(unordered_map&&, const Allocator&);
69 unordered_map(initializer_list<value_type>, size_type n = 0,
70 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
71 const allocator_type& a = allocator_type());
72 ~unordered_map();
73 unordered_map& operator=(const unordered_map&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000074 unordered_map& operator=(unordered_map&&)
75 noexcept(
76 allocator_type::propagate_on_container_move_assignment::value &&
77 is_nothrow_move_assignable<allocator_type>::value &&
78 is_nothrow_move_assignable<hasher>::value &&
79 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000080 unordered_map& operator=(initializer_list<value_type>);
81
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000082 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000083
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000084 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000087
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000088 iterator begin() noexcept;
89 iterator end() noexcept;
90 const_iterator begin() const noexcept;
91 const_iterator end() const noexcept;
92 const_iterator cbegin() const noexcept;
93 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000094
95 template <class... Args>
96 pair<iterator, bool> emplace(Args&&... args);
97 template <class... Args>
98 iterator emplace_hint(const_iterator position, Args&&... args);
99 pair<iterator, bool> insert(const value_type& obj);
100 template <class P>
101 pair<iterator, bool> insert(P&& obj);
102 iterator insert(const_iterator hint, const value_type& obj);
103 template <class P>
104 iterator insert(const_iterator hint, P&& obj);
105 template <class InputIterator>
106 void insert(InputIterator first, InputIterator last);
107 void insert(initializer_list<value_type>);
108
109 iterator erase(const_iterator position);
110 size_type erase(const key_type& k);
111 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000112 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000113
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000114 void swap(unordered_map&)
115 noexcept(
116 (!allocator_type::propagate_on_container_swap::value ||
117 __is_nothrow_swappable<allocator_type>::value) &&
118 __is_nothrow_swappable<hasher>::value &&
119 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
121 hasher hash_function() const;
122 key_equal key_eq() const;
123
124 iterator find(const key_type& k);
125 const_iterator find(const key_type& k) const;
126 size_type count(const key_type& k) const;
127 pair<iterator, iterator> equal_range(const key_type& k);
128 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
129
130 mapped_type& operator[](const key_type& k);
131 mapped_type& operator[](key_type&& k);
132
133 mapped_type& at(const key_type& k);
134 const mapped_type& at(const key_type& k) const;
135
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
141
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
148
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
154};
155
156template <class Key, class T, class Hash, class Pred, class Alloc>
157 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000160
161template <class Key, class T, class Hash, class Pred, class Alloc>
162 bool
163 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
164 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
165
166template <class Key, class T, class Hash, class Pred, class Alloc>
167 bool
168 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
169 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
170
171template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
172 class Alloc = allocator<pair<const Key, T>>>
173class unordered_multimap
174{
175public:
176 // types
177 typedef Key key_type;
178 typedef T mapped_type;
179 typedef Hash hasher;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef pair<const key_type, mapped_type> value_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
194
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000195 unordered_multimap()
196 noexcept(
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multimap(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multimap(const allocator_type&);
209 unordered_multimap(const unordered_multimap&);
210 unordered_multimap(const unordered_multimap&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000211 unordered_multimap(unordered_multimap&&)
212 noexcept(
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216 unordered_multimap(unordered_multimap&&, const Allocator&);
217 unordered_multimap(initializer_list<value_type>, size_type n = 0,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
220 ~unordered_multimap();
221 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000222 unordered_multimap& operator=(unordered_multimap&&)
223 noexcept(
224 allocator_type::propagate_on_container_move_assignment::value &&
225 is_nothrow_move_assignable<allocator_type>::value &&
226 is_nothrow_move_assignable<hasher>::value &&
227 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000228 unordered_multimap& operator=(initializer_list<value_type>);
229
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000230 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000231
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000236 iterator begin() noexcept;
237 iterator end() noexcept;
238 const_iterator begin() const noexcept;
239 const_iterator end() const noexcept;
240 const_iterator cbegin() const noexcept;
241 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000242
243 template <class... Args>
244 iterator emplace(Args&&... args);
245 template <class... Args>
246 iterator emplace_hint(const_iterator position, Args&&... args);
247 iterator insert(const value_type& obj);
248 template <class P>
249 iterator insert(P&& obj);
250 iterator insert(const_iterator hint, const value_type& obj);
251 template <class P>
252 iterator insert(const_iterator hint, P&& obj);
253 template <class InputIterator>
254 void insert(InputIterator first, InputIterator last);
255 void insert(initializer_list<value_type>);
256
257 iterator erase(const_iterator position);
258 size_type erase(const key_type& k);
259 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000260 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000261
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000262 void swap(unordered_multimap&)
263 noexcept(
264 (!allocator_type::propagate_on_container_swap::value ||
265 __is_nothrow_swappable<allocator_type>::value) &&
266 __is_nothrow_swappable<hasher>::value &&
267 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000268
269 hasher hash_function() const;
270 key_equal key_eq() const;
271
272 iterator find(const key_type& k);
273 const_iterator find(const key_type& k) const;
274 size_type count(const key_type& k) const;
275 pair<iterator, iterator> equal_range(const key_type& k);
276 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
277
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000280
281 size_type bucket_size(size_type n) const;
282 size_type bucket(const key_type& k) const;
283
284 local_iterator begin(size_type n);
285 local_iterator end(size_type n);
286 const_local_iterator begin(size_type n) const;
287 const_local_iterator end(size_type n) const;
288 const_local_iterator cbegin(size_type n) const;
289 const_local_iterator cend(size_type n) const;
290
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000293 void max_load_factor(float z);
294 void rehash(size_type n);
295 void reserve(size_type n);
296};
297
298template <class Key, class T, class Hash, class Pred, class Alloc>
299 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302
303template <class Key, class T, class Hash, class Pred, class Alloc>
304 bool
305 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
306 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
307
308template <class Key, class T, class Hash, class Pred, class Alloc>
309 bool
310 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
311 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
312
313} // std
314
315*/
316
317#include <__config>
318#include <__hash_table>
319#include <functional>
320#include <stdexcept>
321
Howard Hinnant08e17472011-10-17 20:05:10 +0000322#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000323#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000324#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000325
326_LIBCPP_BEGIN_NAMESPACE_STD
327
Howard Hinnantf8880d02011-12-12 17:26:24 +0000328template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000329#if __has_feature(is_final)
330 && !__is_final(_Hash)
331#endif
332 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000333class __unordered_map_hasher
334 : private _Hash
335{
Howard Hinnantf8880d02011-12-12 17:26:24 +0000336 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000337public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000338 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000339 __unordered_map_hasher()
340 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
341 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000342 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000343 __unordered_map_hasher(const _Hash& __h)
344 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
345 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000346 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000347 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000349 size_t operator()(const _Cp& __x) const
350 {return static_cast<const _Hash&>(*this)(__x.first);}
351 _LIBCPP_INLINE_VISIBILITY
352 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000353 {return static_cast<const _Hash&>(*this)(__x);}
354};
355
Howard Hinnantf8880d02011-12-12 17:26:24 +0000356template <class _Key, class _Tp, class _Hash>
357class __unordered_map_hasher<_Key, _Tp, _Hash, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000358{
359 _Hash __hash_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000360
Howard Hinnantf8880d02011-12-12 17:26:24 +0000361 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000362public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000363 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000364 __unordered_map_hasher()
365 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
366 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000367 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000368 __unordered_map_hasher(const _Hash& __h)
369 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
370 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000371 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000372 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000373 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000374 size_t operator()(const _Cp& __x) const
375 {return __hash_(__x.first);}
376 _LIBCPP_INLINE_VISIBILITY
377 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000378 {return __hash_(__x);}
379};
380
Howard Hinnantf8880d02011-12-12 17:26:24 +0000381template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000382#if __has_feature(is_final)
383 && !__is_final(_Pred)
384#endif
385 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000386class __unordered_map_equal
387 : private _Pred
388{
Howard Hinnantf8880d02011-12-12 17:26:24 +0000389 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000390public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000391 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000392 __unordered_map_equal()
393 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
394 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000395 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000396 __unordered_map_equal(const _Pred& __p)
397 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
398 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000399 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000400 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000401 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000402 bool operator()(const _Cp& __x, const _Cp& __y) const
403 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
404 _LIBCPP_INLINE_VISIBILITY
405 bool operator()(const _Cp& __x, const _Key& __y) const
406 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
407 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000408 bool operator()(const _Key& __x, const _Cp& __y) const
409 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000410};
411
Howard Hinnantf8880d02011-12-12 17:26:24 +0000412template <class _Key, class _Tp, class _Pred>
413class __unordered_map_equal<_Key, _Tp, _Pred, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000414{
415 _Pred __pred_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000416
Howard Hinnantf8880d02011-12-12 17:26:24 +0000417 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000418public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000420 __unordered_map_equal()
421 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
422 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000424 __unordered_map_equal(const _Pred& __p)
425 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
426 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000428 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000429 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000430 bool operator()(const _Cp& __x, const _Cp& __y) const
431 {return __pred_(__x.first, __y.first);}
432 _LIBCPP_INLINE_VISIBILITY
433 bool operator()(const _Cp& __x, const _Key& __y) const
434 {return __pred_(__x.first, __y);}
435 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000436 bool operator()(const _Key& __x, const _Cp& __y) const
437 {return __pred_(__x, __y.first);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000438};
439
440template <class _Alloc>
441class __hash_map_node_destructor
442{
443 typedef _Alloc allocator_type;
444 typedef allocator_traits<allocator_type> __alloc_traits;
445 typedef typename __alloc_traits::value_type::value_type value_type;
446public:
447 typedef typename __alloc_traits::pointer pointer;
448private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000449 typedef typename value_type::value_type::first_type first_type;
450 typedef typename value_type::value_type::second_type second_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000451
452 allocator_type& __na_;
453
454 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
455
456public:
457 bool __first_constructed;
458 bool __second_constructed;
459
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000461 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000462 : __na_(__na),
463 __first_constructed(false),
464 __second_constructed(false)
465 {}
466
Howard Hinnant73d21a42010-09-04 23:28:19 +0000467#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000468 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000469 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000470 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000471 : __na_(__x.__na_),
472 __first_constructed(__x.__value_constructed),
473 __second_constructed(__x.__value_constructed)
474 {
475 __x.__value_constructed = false;
476 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000477#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000478 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000479 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
480 : __na_(__x.__na_),
481 __first_constructed(__x.__value_constructed),
482 __second_constructed(__x.__value_constructed)
483 {
484 const_cast<bool&>(__x.__value_constructed) = false;
485 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000486#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000487
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000489 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000490 {
491 if (__second_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000492 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000493 if (__first_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000494 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000495 if (__p)
496 __alloc_traits::deallocate(__na_, __p, 1);
497 }
498};
499
500template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000501class _LIBCPP_TYPE_VIS __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000502{
503 _HashIterator __i_;
504
505 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000506 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
507 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000508public:
509 typedef forward_iterator_tag iterator_category;
510 typedef pair<key_type, mapped_type> value_type;
511 typedef typename _HashIterator::difference_type difference_type;
512 typedef value_type& reference;
513 typedef typename __pointer_traits::template
514#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
515 rebind<value_type>
516#else
517 rebind<value_type>::other
518#endif
519 pointer;
520
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000522 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000523
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000525 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000526
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000528 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000530 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000531
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000532 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000533 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000535 __hash_map_iterator operator++(int)
536 {
537 __hash_map_iterator __t(*this);
538 ++(*this);
539 return __t;
540 }
541
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000542 friend _LIBCPP_INLINE_VISIBILITY
543 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000544 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000545 friend _LIBCPP_INLINE_VISIBILITY
546 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000547 {return __x.__i_ != __y.__i_;}
548
Howard Hinnant83eade62013-03-06 23:30:19 +0000549 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
550 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
551 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
552 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
553 template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000554};
555
556template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000557class _LIBCPP_TYPE_VIS __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000558{
559 _HashIterator __i_;
560
561 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000562 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
563 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000564public:
565 typedef forward_iterator_tag iterator_category;
566 typedef pair<key_type, mapped_type> value_type;
567 typedef typename _HashIterator::difference_type difference_type;
568 typedef const value_type& reference;
569 typedef typename __pointer_traits::template
570#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000571 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000572#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000573 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000574#endif
575 pointer;
576
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000578 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000579
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000581 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 __hash_map_const_iterator(
584 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000585 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000586 : __i_(__i.__i_) {}
587
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000588 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000589 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000590 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000591 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000592
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000594 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000595 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000596 __hash_map_const_iterator operator++(int)
597 {
598 __hash_map_const_iterator __t(*this);
599 ++(*this);
600 return __t;
601 }
602
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000603 friend _LIBCPP_INLINE_VISIBILITY
604 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000605 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000606 friend _LIBCPP_INLINE_VISIBILITY
607 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000608 {return __x.__i_ != __y.__i_;}
609
Howard Hinnant83eade62013-03-06 23:30:19 +0000610 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
611 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
612 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
613 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000614};
615
616template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
617 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +0000618class _LIBCPP_TYPE_VIS unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000619{
620public:
621 // types
622 typedef _Key key_type;
623 typedef _Tp mapped_type;
624 typedef _Hash hasher;
625 typedef _Pred key_equal;
626 typedef _Alloc allocator_type;
627 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000628 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000629 typedef value_type& reference;
630 typedef const value_type& const_reference;
631
632private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000633#if __cplusplus >= 201103L
634 union __value_type
635 {
636 typedef typename unordered_map::value_type value_type;
637 typedef typename unordered_map::__nc_value_type __nc_value_type;
638 value_type __cc;
639 __nc_value_type __nc;
640
641 template <class ..._Args>
642 __value_type(_Args&& ...__args)
643 : __cc(std::forward<_Args>(__args)...) {}
644
645 __value_type(const __value_type& __v)
646 : __cc(std::move(__v.__cc)) {}
647
648 __value_type(__value_type&& __v)
649 : __nc(std::move(__v.__nc)) {}
650
651 __value_type& operator=(const __value_type& __v)
652 {__nc = __v.__cc; return *this;}
653
654 __value_type& operator=(__value_type&& __v)
655 {__nc = std::move(__v.__nc); return *this;}
656
657 ~__value_type() {__cc.~value_type();}
658
659 operator const value_type& () const {return __cc;}
660 };
661#else
662 struct __value_type
663 {
664 typedef typename unordered_map::value_type value_type;
665 value_type __cc;
666
667 __value_type() {}
668
669 template <class _A0>
670 __value_type(const _A0& __a0)
671 : __cc(__a0) {}
672
673 template <class _A0, class _A1>
674 __value_type(const _A0& __a0, const _A1& __a1)
675 : __cc(__a0, __a1) {}
676
677 operator const value_type& () const {return __cc;}
678 };
679#endif
Howard Hinnantf8880d02011-12-12 17:26:24 +0000680 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
681 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000682 typedef typename allocator_traits<allocator_type>::template
683#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
684 rebind_alloc<__value_type>
685#else
686 rebind_alloc<__value_type>::other
687#endif
688 __allocator_type;
689
690 typedef __hash_table<__value_type, __hasher,
691 __key_equal, __allocator_type> __table;
692
693 __table __table_;
694
695 typedef typename __table::__node_pointer __node_pointer;
696 typedef typename __table::__node_const_pointer __node_const_pointer;
697 typedef typename __table::__node_traits __node_traits;
698 typedef typename __table::__node_allocator __node_allocator;
699 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +0000700 typedef __hash_map_node_destructor<__node_allocator> _Dp;
701 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000702 typedef allocator_traits<allocator_type> __alloc_traits;
703public:
704 typedef typename __alloc_traits::pointer pointer;
705 typedef typename __alloc_traits::const_pointer const_pointer;
706 typedef typename __alloc_traits::size_type size_type;
707 typedef typename __alloc_traits::difference_type difference_type;
708
709 typedef __hash_map_iterator<typename __table::iterator> iterator;
710 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
711 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
712 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
713
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000714 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000715 unordered_map()
716 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
717 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000718 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
719 const key_equal& __eql = key_equal());
720 unordered_map(size_type __n, const hasher& __hf,
721 const key_equal& __eql,
722 const allocator_type& __a);
723 template <class _InputIterator>
724 unordered_map(_InputIterator __first, _InputIterator __last);
725 template <class _InputIterator>
726 unordered_map(_InputIterator __first, _InputIterator __last,
727 size_type __n, const hasher& __hf = hasher(),
728 const key_equal& __eql = key_equal());
729 template <class _InputIterator>
730 unordered_map(_InputIterator __first, _InputIterator __last,
731 size_type __n, const hasher& __hf,
732 const key_equal& __eql,
733 const allocator_type& __a);
734 explicit unordered_map(const allocator_type& __a);
735 unordered_map(const unordered_map& __u);
736 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000737#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000738 unordered_map(unordered_map&& __u)
739 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000740 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000741#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000742#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000743 unordered_map(initializer_list<value_type> __il);
744 unordered_map(initializer_list<value_type> __il, size_type __n,
745 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
746 unordered_map(initializer_list<value_type> __il, size_type __n,
747 const hasher& __hf, const key_equal& __eql,
748 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000749#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000750 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000751 _LIBCPP_INLINE_VISIBILITY
752 unordered_map& operator=(const unordered_map& __u)
753 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000754#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +0000755 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000756#else
757 __table_.clear();
758 __table_.hash_function() = __u.__table_.hash_function();
759 __table_.key_eq() = __u.__table_.key_eq();
760 __table_.max_load_factor() = __u.__table_.max_load_factor();
761 __table_.__copy_assign_alloc(__u.__table_);
762 insert(__u.begin(), __u.end());
763#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +0000764 return *this;
765 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000766#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000767 unordered_map& operator=(unordered_map&& __u)
768 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000769#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000770#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000771 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000772#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000773
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000774 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000775 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000776 {return allocator_type(__table_.__node_alloc());}
777
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000778 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000779 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000781 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000782 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000783 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000784
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000786 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000788 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000790 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000792 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000794 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000795 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000796 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000797
Howard Hinnant73d21a42010-09-04 23:28:19 +0000798#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +0000799#ifndef _LIBCPP_HAS_NO_VARIADICS
800
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000801 template <class... _Args>
802 pair<iterator, bool> emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000803
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000804 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000806 iterator emplace_hint(const_iterator, _Args&&... __args)
807 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000808#endif // _LIBCPP_HAS_NO_VARIADICS
809#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000810 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000811 pair<iterator, bool> insert(const value_type& __x)
812 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000813#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000814 template <class _Pp,
815 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000817 pair<iterator, bool> insert(_Pp&& __x)
818 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000819#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000820 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000821 iterator insert(const_iterator, const value_type& __x)
822 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000823#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000824 template <class _Pp,
825 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000827 iterator insert(const_iterator, _Pp&& __x)
828 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000829#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000830 template <class _InputIterator>
831 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000832#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000833 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000834 void insert(initializer_list<value_type> __il)
835 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000836#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000837
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000839 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000841 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000842 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000843 iterator erase(const_iterator __first, const_iterator __last)
844 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000845 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000846 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000847
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000849 void swap(unordered_map& __u)
850 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
851 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000852
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000853 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000854 hasher hash_function() const
855 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000857 key_equal key_eq() const
858 {return __table_.key_eq().key_eq();}
859
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000860 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000861 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000863 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000864 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000865 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000866 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000867 pair<iterator, iterator> equal_range(const key_type& __k)
868 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000869 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000870 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
871 {return __table_.__equal_range_unique(__k);}
872
873 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000874#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000875 mapped_type& operator[](key_type&& __k);
876#endif
877
878 mapped_type& at(const key_type& __k);
879 const mapped_type& at(const key_type& __k) const;
880
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000881 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000882 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000883 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000884 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000885
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000887 size_type bucket_size(size_type __n) const
888 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000889 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000890 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
891
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000893 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000895 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000896 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000897 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000898 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000899 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000900 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000901 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000902 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000903 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
904
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000906 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000907 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000908 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000909 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000910 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000911 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000912 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000913 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000914 void reserve(size_type __n) {__table_.reserve(__n);}
915
916private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000917#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000918 __node_holder __construct_node();
919 template <class _A0>
920 typename enable_if
921 <
922 is_constructible<value_type, _A0>::value,
923 __node_holder
924 >::type
925 __construct_node(_A0&& __a0);
926 template <class _A0>
927 typename enable_if
928 <
929 is_constructible<key_type, _A0>::value,
930 __node_holder
931 >::type
932 __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000933#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000934 template <class _A0, class _A1, class ..._Args>
935 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000936#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant73d21a42010-09-04 23:28:19 +0000937#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000938 __node_holder __construct_node(const key_type& __k);
939#endif
940};
941
942template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
943unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
944 size_type __n, const hasher& __hf, const key_equal& __eql)
945 : __table_(__hf, __eql)
946{
947 __table_.rehash(__n);
948}
949
950template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
951unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
952 size_type __n, const hasher& __hf, const key_equal& __eql,
953 const allocator_type& __a)
954 : __table_(__hf, __eql, __a)
955{
956 __table_.rehash(__n);
957}
958
959template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000960inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000961unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
962 const allocator_type& __a)
963 : __table_(__a)
964{
965}
966
967template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
968template <class _InputIterator>
969unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
970 _InputIterator __first, _InputIterator __last)
971{
972 insert(__first, __last);
973}
974
975template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
976template <class _InputIterator>
977unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
978 _InputIterator __first, _InputIterator __last, size_type __n,
979 const hasher& __hf, const key_equal& __eql)
980 : __table_(__hf, __eql)
981{
982 __table_.rehash(__n);
983 insert(__first, __last);
984}
985
986template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
987template <class _InputIterator>
988unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
989 _InputIterator __first, _InputIterator __last, size_type __n,
990 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
991 : __table_(__hf, __eql, __a)
992{
993 __table_.rehash(__n);
994 insert(__first, __last);
995}
996
997template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
998unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
999 const unordered_map& __u)
1000 : __table_(__u.__table_)
1001{
1002 __table_.rehash(__u.bucket_count());
1003 insert(__u.begin(), __u.end());
1004}
1005
1006template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1007unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1008 const unordered_map& __u, const allocator_type& __a)
1009 : __table_(__u.__table_, __a)
1010{
1011 __table_.rehash(__u.bucket_count());
1012 insert(__u.begin(), __u.end());
1013}
1014
Howard Hinnant73d21a42010-09-04 23:28:19 +00001015#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001016
1017template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001018inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001019unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1020 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001021 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001022 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001023{
1024}
1025
1026template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1027unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1028 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001029 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001030{
1031 if (__a != __u.get_allocator())
1032 {
1033 iterator __i = __u.begin();
1034 while (__u.size() != 0)
1035 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001036 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001037 );
1038 }
1039}
1040
Howard Hinnant73d21a42010-09-04 23:28:19 +00001041#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001042
Howard Hinnante3e32912011-08-12 21:56:02 +00001043#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1044
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001045template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1046unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1047 initializer_list<value_type> __il)
1048{
1049 insert(__il.begin(), __il.end());
1050}
1051
1052template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1053unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1054 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1055 const key_equal& __eql)
1056 : __table_(__hf, __eql)
1057{
1058 __table_.rehash(__n);
1059 insert(__il.begin(), __il.end());
1060}
1061
1062template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1063unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1064 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1065 const key_equal& __eql, const allocator_type& __a)
1066 : __table_(__hf, __eql, __a)
1067{
1068 __table_.rehash(__n);
1069 insert(__il.begin(), __il.end());
1070}
1071
Howard Hinnante3e32912011-08-12 21:56:02 +00001072#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1073
Howard Hinnant73d21a42010-09-04 23:28:19 +00001074#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001075
1076template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001077inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001078unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1079unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001080 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001081{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001082 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001083 return *this;
1084}
1085
Howard Hinnant73d21a42010-09-04 23:28:19 +00001086#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001087
Howard Hinnante3e32912011-08-12 21:56:02 +00001088#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1089
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001090template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001091inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001092unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1093unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1094 initializer_list<value_type> __il)
1095{
1096 __table_.__assign_unique(__il.begin(), __il.end());
1097 return *this;
1098}
1099
Howard Hinnante3e32912011-08-12 21:56:02 +00001100#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1101
Howard Hinnant73d21a42010-09-04 23:28:19 +00001102#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001103
1104template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001105typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001106unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001107{
1108 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001109 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001110 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001111 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001112 __h.get_deleter().__second_constructed = true;
1113 return __h;
1114}
1115
1116template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001117template <class _A0>
1118typename enable_if
1119<
1120 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1121 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1122>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001123unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1124{
1125 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001126 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001127 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1128 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001129 __h.get_deleter().__first_constructed = true;
1130 __h.get_deleter().__second_constructed = true;
1131 return __h;
1132}
1133
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001134template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1135template <class _A0>
1136typename enable_if
1137<
1138 is_constructible<_Key, _A0>::value,
1139 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1140>::type
1141unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1142{
1143 __node_allocator& __na = __table_.__node_alloc();
1144 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001145 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first),
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001146 _VSTD::forward<_A0>(__a0));
1147 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001148 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001149 __h.get_deleter().__second_constructed = true;
1150 return __h;
1151}
1152
Howard Hinnant73d21a42010-09-04 23:28:19 +00001153#ifndef _LIBCPP_HAS_NO_VARIADICS
1154
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001155template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001156template <class _A0, class _A1, class ..._Args>
1157typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1158unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1159 _A1&& __a1,
1160 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001161{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001162 __node_allocator& __na = __table_.__node_alloc();
1163 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1164 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1165 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1166 _VSTD::forward<_Args>(__args)...);
1167 __h.get_deleter().__first_constructed = true;
1168 __h.get_deleter().__second_constructed = true;
1169 return __h;
1170}
1171
1172template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1173template <class... _Args>
1174pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1175unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1176{
1177 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001178 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1179 if (__r.second)
1180 __h.release();
1181 return __r;
1182}
1183
Howard Hinnant73d21a42010-09-04 23:28:19 +00001184#endif // _LIBCPP_HAS_NO_VARIADICS
1185#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001186
1187template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1188typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1189unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1190{
1191 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001192 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001193 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001194 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001195 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001196 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001197 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001198}
1199
Howard Hinnant73d21a42010-09-04 23:28:19 +00001200#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001201
1202template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1203template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001204inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001205void
1206unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1207 _InputIterator __last)
1208{
1209 for (; __first != __last; ++__first)
1210 __table_.__insert_unique(*__first);
1211}
1212
1213template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1214_Tp&
1215unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1216{
1217 iterator __i = find(__k);
1218 if (__i != end())
1219 return __i->second;
1220 __node_holder __h = __construct_node(__k);
1221 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1222 __h.release();
1223 return __r.first->second;
1224}
1225
Howard Hinnant73d21a42010-09-04 23:28:19 +00001226#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001227
1228template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1229_Tp&
1230unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1231{
1232 iterator __i = find(__k);
1233 if (__i != end())
1234 return __i->second;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001235 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001236 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1237 __h.release();
1238 return __r.first->second;
1239}
1240
Howard Hinnant73d21a42010-09-04 23:28:19 +00001241#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001242
1243template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1244_Tp&
1245unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1246{
1247 iterator __i = find(__k);
1248#ifndef _LIBCPP_NO_EXCEPTIONS
1249 if (__i == end())
1250 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001251#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001252 return __i->second;
1253}
1254
1255template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1256const _Tp&
1257unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1258{
1259 const_iterator __i = find(__k);
1260#ifndef _LIBCPP_NO_EXCEPTIONS
1261 if (__i == end())
1262 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001263#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001264 return __i->second;
1265}
1266
1267template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001268inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001269void
1270swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1271 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001272 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001273{
1274 __x.swap(__y);
1275}
1276
1277template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1278bool
1279operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1280 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1281{
1282 if (__x.size() != __y.size())
1283 return false;
1284 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1285 const_iterator;
1286 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1287 __i != __ex; ++__i)
1288 {
1289 const_iterator __j = __y.find(__i->first);
1290 if (__j == __ey || !(*__i == *__j))
1291 return false;
1292 }
1293 return true;
1294}
1295
1296template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001297inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001298bool
1299operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1300 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1301{
1302 return !(__x == __y);
1303}
1304
1305template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1306 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +00001307class _LIBCPP_TYPE_VIS unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001308{
1309public:
1310 // types
1311 typedef _Key key_type;
1312 typedef _Tp mapped_type;
1313 typedef _Hash hasher;
1314 typedef _Pred key_equal;
1315 typedef _Alloc allocator_type;
1316 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001317 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001318 typedef value_type& reference;
1319 typedef const value_type& const_reference;
1320
1321private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001322#if __cplusplus >= 201103L
1323 union __value_type
1324 {
1325 typedef typename unordered_multimap::value_type value_type;
1326 typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1327 value_type __cc;
1328 __nc_value_type __nc;
1329
1330 template <class ..._Args>
1331 __value_type(_Args&& ...__args)
1332 : __cc(std::forward<_Args>(__args)...) {}
1333
1334 __value_type(const __value_type& __v)
1335 : __cc(std::move(__v.__cc)) {}
1336
1337 __value_type(__value_type&& __v)
1338 : __nc(std::move(__v.__nc)) {}
1339
1340 __value_type& operator=(const __value_type& __v)
1341 {__nc = __v.__cc; return *this;}
1342
1343 __value_type& operator=(__value_type&& __v)
1344 {__nc = std::move(__v.__nc); return *this;}
1345
1346 ~__value_type() {__cc.~value_type();}
1347
1348 operator const value_type& () const {return __cc;}
1349 };
1350#else
1351 struct __value_type
1352 {
1353 typedef typename unordered_multimap::value_type value_type;
1354 value_type __cc;
1355
1356 __value_type() {}
1357
1358 template <class _A0>
1359 __value_type(const _A0& __a0)
1360 : __cc(__a0) {}
1361
1362 template <class _A0, class _A1>
1363 __value_type(const _A0& __a0, const _A1& __a1)
1364 : __cc(__a0, __a1) {}
1365
1366 operator const value_type& () const {return __cc;}
1367 };
1368#endif
Howard Hinnantf8880d02011-12-12 17:26:24 +00001369 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
1370 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001371 typedef typename allocator_traits<allocator_type>::template
1372#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1373 rebind_alloc<__value_type>
1374#else
1375 rebind_alloc<__value_type>::other
1376#endif
1377 __allocator_type;
1378
1379 typedef __hash_table<__value_type, __hasher,
1380 __key_equal, __allocator_type> __table;
1381
1382 __table __table_;
1383
1384 typedef typename __table::__node_traits __node_traits;
1385 typedef typename __table::__node_allocator __node_allocator;
1386 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001387 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1388 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001389 typedef allocator_traits<allocator_type> __alloc_traits;
1390public:
1391 typedef typename __alloc_traits::pointer pointer;
1392 typedef typename __alloc_traits::const_pointer const_pointer;
1393 typedef typename __alloc_traits::size_type size_type;
1394 typedef typename __alloc_traits::difference_type difference_type;
1395
1396 typedef __hash_map_iterator<typename __table::iterator> iterator;
1397 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1398 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1399 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1400
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001401 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001402 unordered_multimap()
1403 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1404 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001405 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1406 const key_equal& __eql = key_equal());
1407 unordered_multimap(size_type __n, const hasher& __hf,
1408 const key_equal& __eql,
1409 const allocator_type& __a);
1410 template <class _InputIterator>
1411 unordered_multimap(_InputIterator __first, _InputIterator __last);
1412 template <class _InputIterator>
1413 unordered_multimap(_InputIterator __first, _InputIterator __last,
1414 size_type __n, const hasher& __hf = hasher(),
1415 const key_equal& __eql = key_equal());
1416 template <class _InputIterator>
1417 unordered_multimap(_InputIterator __first, _InputIterator __last,
1418 size_type __n, const hasher& __hf,
1419 const key_equal& __eql,
1420 const allocator_type& __a);
1421 explicit unordered_multimap(const allocator_type& __a);
1422 unordered_multimap(const unordered_multimap& __u);
1423 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001424#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001425 unordered_multimap(unordered_multimap&& __u)
1426 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001427 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001428#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001429#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001430 unordered_multimap(initializer_list<value_type> __il);
1431 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1432 const hasher& __hf = hasher(),
1433 const key_equal& __eql = key_equal());
1434 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1435 const hasher& __hf, const key_equal& __eql,
1436 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001437#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001438 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001439 _LIBCPP_INLINE_VISIBILITY
1440 unordered_multimap& operator=(const unordered_multimap& __u)
1441 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001442#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +00001443 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001444#else
1445 __table_.clear();
1446 __table_.hash_function() = __u.__table_.hash_function();
1447 __table_.key_eq() = __u.__table_.key_eq();
1448 __table_.max_load_factor() = __u.__table_.max_load_factor();
1449 __table_.__copy_assign_alloc(__u.__table_);
1450 insert(__u.begin(), __u.end());
1451#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +00001452 return *this;
1453 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001454#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001455 unordered_multimap& operator=(unordered_multimap&& __u)
1456 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001457#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001458#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001459 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001460#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001461
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001462 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001463 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001464 {return allocator_type(__table_.__node_alloc());}
1465
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001467 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001468 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001469 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001470 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001471 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001472
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001473 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001474 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001475 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001476 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001477 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001478 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001479 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001480 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001481 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001482 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001483 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001484 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001485
Howard Hinnant73d21a42010-09-04 23:28:19 +00001486#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +00001487#ifndef _LIBCPP_HAS_NO_VARIADICS
1488
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001489 template <class... _Args>
1490 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001491
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001492 template <class... _Args>
1493 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001494#endif // _LIBCPP_HAS_NO_VARIADICS
1495#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001496 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001497 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001498#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001499 template <class _Pp,
1500 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001501 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001502 iterator insert(_Pp&& __x)
1503 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001504#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001505 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001506 iterator insert(const_iterator __p, const value_type& __x)
1507 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001508#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001509 template <class _Pp,
1510 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001511 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001512 iterator insert(const_iterator __p, _Pp&& __x)
1513 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001514#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001515 template <class _InputIterator>
1516 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001517#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001518 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001519 void insert(initializer_list<value_type> __il)
1520 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001521#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001522
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001524 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001526 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001528 iterator erase(const_iterator __first, const_iterator __last)
1529 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001531 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001532
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001534 void swap(unordered_multimap& __u)
1535 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1536 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001537
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001538 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001539 hasher hash_function() const
1540 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001541 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001542 key_equal key_eq() const
1543 {return __table_.key_eq().key_eq();}
1544
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001545 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001546 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001547 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001548 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001549 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001550 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001551 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001552 pair<iterator, iterator> equal_range(const key_type& __k)
1553 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001555 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1556 {return __table_.__equal_range_multi(__k);}
1557
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001558 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001559 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001560 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001561 size_type max_bucket_count() const _NOEXCEPT
1562 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001563
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001564 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001565 size_type bucket_size(size_type __n) const
1566 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001568 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1569
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001571 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001573 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001575 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001577 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001579 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001581 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1582
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001583 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001584 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001585 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001586 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001588 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001590 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001592 void reserve(size_type __n) {__table_.reserve(__n);}
1593
1594private:
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001595#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1596 __node_holder __construct_node();
1597 template <class _A0>
1598 typename enable_if
1599 <
1600 is_constructible<value_type, _A0>::value,
1601 __node_holder
1602 >::type
1603 __construct_node(_A0&& __a0);
1604 template <class _A0>
1605 typename enable_if
1606 <
1607 is_constructible<key_type, _A0>::value,
1608 __node_holder
1609 >::type
1610 __construct_node(_A0&& __a0);
1611#ifndef _LIBCPP_HAS_NO_VARIADICS
1612 template <class _A0, class _A1, class ..._Args>
1613 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1614#endif // _LIBCPP_HAS_NO_VARIADICS
1615#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001616};
1617
1618template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1619unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1620 size_type __n, const hasher& __hf, const key_equal& __eql)
1621 : __table_(__hf, __eql)
1622{
1623 __table_.rehash(__n);
1624}
1625
1626template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1627unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1628 size_type __n, const hasher& __hf, const key_equal& __eql,
1629 const allocator_type& __a)
1630 : __table_(__hf, __eql, __a)
1631{
1632 __table_.rehash(__n);
1633}
1634
1635template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1636template <class _InputIterator>
1637unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638 _InputIterator __first, _InputIterator __last)
1639{
1640 insert(__first, __last);
1641}
1642
1643template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1644template <class _InputIterator>
1645unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1646 _InputIterator __first, _InputIterator __last, size_type __n,
1647 const hasher& __hf, const key_equal& __eql)
1648 : __table_(__hf, __eql)
1649{
1650 __table_.rehash(__n);
1651 insert(__first, __last);
1652}
1653
1654template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1655template <class _InputIterator>
1656unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1657 _InputIterator __first, _InputIterator __last, size_type __n,
1658 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1659 : __table_(__hf, __eql, __a)
1660{
1661 __table_.rehash(__n);
1662 insert(__first, __last);
1663}
1664
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001665template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001666inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001667unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1668 const allocator_type& __a)
1669 : __table_(__a)
1670{
1671}
1672
1673template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1674unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1675 const unordered_multimap& __u)
1676 : __table_(__u.__table_)
1677{
1678 __table_.rehash(__u.bucket_count());
1679 insert(__u.begin(), __u.end());
1680}
1681
1682template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1683unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1684 const unordered_multimap& __u, const allocator_type& __a)
1685 : __table_(__u.__table_, __a)
1686{
1687 __table_.rehash(__u.bucket_count());
1688 insert(__u.begin(), __u.end());
1689}
1690
Howard Hinnant73d21a42010-09-04 23:28:19 +00001691#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001692
1693template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001694inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001695unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1696 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001697 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001698 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001699{
1700}
1701
1702template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1703unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1704 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001705 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001706{
1707 if (__a != __u.get_allocator())
1708 {
1709 iterator __i = __u.begin();
1710 while (__u.size() != 0)
1711{
1712 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001713 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001714 );
1715}
1716 }
1717}
1718
Howard Hinnant73d21a42010-09-04 23:28:19 +00001719#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001720
Howard Hinnante3e32912011-08-12 21:56:02 +00001721#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1722
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001723template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1724unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1725 initializer_list<value_type> __il)
1726{
1727 insert(__il.begin(), __il.end());
1728}
1729
1730template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1731unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1732 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1733 const key_equal& __eql)
1734 : __table_(__hf, __eql)
1735{
1736 __table_.rehash(__n);
1737 insert(__il.begin(), __il.end());
1738}
1739
1740template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1741unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1742 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1743 const key_equal& __eql, const allocator_type& __a)
1744 : __table_(__hf, __eql, __a)
1745{
1746 __table_.rehash(__n);
1747 insert(__il.begin(), __il.end());
1748}
1749
Howard Hinnante3e32912011-08-12 21:56:02 +00001750#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1751
Howard Hinnant73d21a42010-09-04 23:28:19 +00001752#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001753
1754template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001755inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001756unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1757unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001758 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001759{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001760 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001761 return *this;
1762}
1763
Howard Hinnant73d21a42010-09-04 23:28:19 +00001764#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001765
Howard Hinnante3e32912011-08-12 21:56:02 +00001766#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1767
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001768template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001769inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001770unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1771unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1772 initializer_list<value_type> __il)
1773{
1774 __table_.__assign_multi(__il.begin(), __il.end());
1775 return *this;
1776}
1777
Howard Hinnante3e32912011-08-12 21:56:02 +00001778#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1779
Howard Hinnant73d21a42010-09-04 23:28:19 +00001780#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001781
1782template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001783typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001784unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001785{
1786 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001787 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001788 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001789 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001790 __h.get_deleter().__second_constructed = true;
1791 return __h;
1792}
1793
1794template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001795template <class _A0>
1796typename enable_if
1797<
1798 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1799 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1800>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001801unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1802{
1803 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001804 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001805 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1806 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001807 __h.get_deleter().__first_constructed = true;
1808 __h.get_deleter().__second_constructed = true;
1809 return __h;
1810}
1811
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001812template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1813template <class _A0>
1814typename enable_if
1815<
1816 is_constructible<_Key, _A0>::value,
1817 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1818>::type
1819unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1820{
1821 __node_allocator& __na = __table_.__node_alloc();
1822 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001823 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first),
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001824 _VSTD::forward<_A0>(__a0));
1825 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001826 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001827 __h.get_deleter().__second_constructed = true;
1828 return __h;
1829}
1830
Howard Hinnant73d21a42010-09-04 23:28:19 +00001831#ifndef _LIBCPP_HAS_NO_VARIADICS
1832
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001833template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001834template <class _A0, class _A1, class ..._Args>
1835typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1836unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1837 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001838{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001839 __node_allocator& __na = __table_.__node_alloc();
1840 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1841 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1842 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1843 _VSTD::forward<_Args>(__args)...);
1844 __h.get_deleter().__first_constructed = true;
1845 __h.get_deleter().__second_constructed = true;
1846 return __h;
1847}
1848
1849template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1850template <class... _Args>
1851typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1852unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1853{
1854 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001855 iterator __r = __table_.__node_insert_multi(__h.get());
1856 __h.release();
1857 return __r;
1858}
1859
1860template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001861template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001862typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1863unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001864 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001865{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001866 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001867 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1868 __h.release();
1869 return __r;
1870}
1871
Howard Hinnant73d21a42010-09-04 23:28:19 +00001872#endif // _LIBCPP_HAS_NO_VARIADICS
1873#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001874
1875template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1876template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001877inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001878void
1879unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1880 _InputIterator __last)
1881{
1882 for (; __first != __last; ++__first)
1883 __table_.__insert_multi(*__first);
1884}
1885
1886template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001887inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001888void
1889swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1890 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001891 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001892{
1893 __x.swap(__y);
1894}
1895
1896template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1897bool
1898operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1899 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1900{
1901 if (__x.size() != __y.size())
1902 return false;
1903 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1904 const_iterator;
1905 typedef pair<const_iterator, const_iterator> _EqRng;
1906 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1907 {
1908 _EqRng __xeq = __x.equal_range(__i->first);
1909 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001910 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1911 _VSTD::distance(__yeq.first, __yeq.second) ||
1912 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001913 return false;
1914 __i = __xeq.second;
1915 }
1916 return true;
1917}
1918
1919template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001920inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001921bool
1922operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1923 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1924{
1925 return !(__x == __y);
1926}
1927
1928_LIBCPP_END_NAMESPACE_STD
1929
1930#endif // _LIBCPP_UNORDERED_MAP