blob: 772c44b6f4b7543884434f4bc19df669bced4ef8 [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<typename remove_const<_Key>::type, _Tp> _Pp;
337 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000338public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000340 __unordered_map_hasher()
341 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
342 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000343 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000344 __unordered_map_hasher(const _Hash& __h)
345 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
346 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000347 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000348 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000349 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000350 size_t operator()(const _Pp& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000351 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000353 size_t operator()(const _Cp& __x) const
354 {return static_cast<const _Hash&>(*this)(__x.first);}
355 _LIBCPP_INLINE_VISIBILITY
356 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000357 {return static_cast<const _Hash&>(*this)(__x);}
358};
359
Howard Hinnantf8880d02011-12-12 17:26:24 +0000360template <class _Key, class _Tp, class _Hash>
361class __unordered_map_hasher<_Key, _Tp, _Hash, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000362{
363 _Hash __hash_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000364
365 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
366 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000367public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000368 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000369 __unordered_map_hasher()
370 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
371 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000372 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000373 __unordered_map_hasher(const _Hash& __h)
374 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
375 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000376 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000377 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000378 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000379 size_t operator()(const _Pp& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000380 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000381 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000382 size_t operator()(const _Cp& __x) const
383 {return __hash_(__x.first);}
384 _LIBCPP_INLINE_VISIBILITY
385 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000386 {return __hash_(__x);}
387};
388
Howard Hinnantf8880d02011-12-12 17:26:24 +0000389template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000390#if __has_feature(is_final)
391 && !__is_final(_Pred)
392#endif
393 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000394class __unordered_map_equal
395 : private _Pred
396{
Howard Hinnantf8880d02011-12-12 17:26:24 +0000397 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
398 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000399public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000400 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000401 __unordered_map_equal()
402 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
403 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000405 __unordered_map_equal(const _Pred& __p)
406 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
407 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000409 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000410 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000411 bool operator()(const _Pp& __x, const _Pp& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000412 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000414 bool operator()(const _Pp& __x, const _Cp& __y) const
415 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000416 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000417 bool operator()(const _Pp& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000418 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000420 bool operator()(const _Cp& __x, const _Pp& __y) const
421 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
422 _LIBCPP_INLINE_VISIBILITY
423 bool operator()(const _Cp& __x, const _Cp& __y) const
424 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
425 _LIBCPP_INLINE_VISIBILITY
426 bool operator()(const _Cp& __x, const _Key& __y) const
427 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
428 _LIBCPP_INLINE_VISIBILITY
429 bool operator()(const _Key& __x, const _Pp& __y) const
430 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
431 _LIBCPP_INLINE_VISIBILITY
432 bool operator()(const _Key& __x, const _Cp& __y) const
433 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
434 _LIBCPP_INLINE_VISIBILITY
435 bool operator()(const _Key& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000436 {return static_cast<const _Pred&>(*this)(__x, __y);}
437};
438
Howard Hinnantf8880d02011-12-12 17:26:24 +0000439template <class _Key, class _Tp, class _Pred>
440class __unordered_map_equal<_Key, _Tp, _Pred, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000441{
442 _Pred __pred_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000443
444 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
445 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000446public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000447 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000448 __unordered_map_equal()
449 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
450 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000451 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000452 __unordered_map_equal(const _Pred& __p)
453 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
454 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000456 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000458 bool operator()(const _Pp& __x, const _Pp& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000459 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000461 bool operator()(const _Pp& __x, const _Cp& __y) const
462 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000464 bool operator()(const _Pp& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000465 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000467 bool operator()(const _Cp& __x, const _Pp& __y) const
468 {return __pred_(__x.first, __y.first);}
469 _LIBCPP_INLINE_VISIBILITY
470 bool operator()(const _Cp& __x, const _Cp& __y) const
471 {return __pred_(__x.first, __y.first);}
472 _LIBCPP_INLINE_VISIBILITY
473 bool operator()(const _Cp& __x, const _Key& __y) const
474 {return __pred_(__x.first, __y);}
475 _LIBCPP_INLINE_VISIBILITY
476 bool operator()(const _Key& __x, const _Pp& __y) const
477 {return __pred_(__x, __y.first);}
478 _LIBCPP_INLINE_VISIBILITY
479 bool operator()(const _Key& __x, const _Cp& __y) const
480 {return __pred_(__x, __y.first);}
481 _LIBCPP_INLINE_VISIBILITY
482 bool operator()(const _Key& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000483 {return __pred_(__x, __y);}
484};
485
486template <class _Alloc>
487class __hash_map_node_destructor
488{
489 typedef _Alloc allocator_type;
490 typedef allocator_traits<allocator_type> __alloc_traits;
491 typedef typename __alloc_traits::value_type::value_type value_type;
492public:
493 typedef typename __alloc_traits::pointer pointer;
494private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000495 typedef typename value_type::value_type::first_type first_type;
496 typedef typename value_type::value_type::second_type second_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000497
498 allocator_type& __na_;
499
500 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
501
502public:
503 bool __first_constructed;
504 bool __second_constructed;
505
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000507 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000508 : __na_(__na),
509 __first_constructed(false),
510 __second_constructed(false)
511 {}
512
Howard Hinnant73d21a42010-09-04 23:28:19 +0000513#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000515 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000516 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000517 : __na_(__x.__na_),
518 __first_constructed(__x.__value_constructed),
519 __second_constructed(__x.__value_constructed)
520 {
521 __x.__value_constructed = false;
522 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000523#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
526 : __na_(__x.__na_),
527 __first_constructed(__x.__value_constructed),
528 __second_constructed(__x.__value_constructed)
529 {
530 const_cast<bool&>(__x.__value_constructed) = false;
531 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000532#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000533
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000535 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000536 {
537 if (__second_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000538 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000539 if (__first_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000540 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000541 if (__p)
542 __alloc_traits::deallocate(__na_, __p, 1);
543 }
544};
545
546template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000547class _LIBCPP_TYPE_VIS __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000548{
549 _HashIterator __i_;
550
551 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000552 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
553 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000554public:
555 typedef forward_iterator_tag iterator_category;
556 typedef pair<key_type, mapped_type> value_type;
557 typedef typename _HashIterator::difference_type difference_type;
558 typedef value_type& reference;
559 typedef typename __pointer_traits::template
560#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
561 rebind<value_type>
562#else
563 rebind<value_type>::other
564#endif
565 pointer;
566
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000568 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000569
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000571 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000572
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000574 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000576 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000577
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000579 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000581 __hash_map_iterator operator++(int)
582 {
583 __hash_map_iterator __t(*this);
584 ++(*this);
585 return __t;
586 }
587
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000588 friend _LIBCPP_INLINE_VISIBILITY
589 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000590 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000591 friend _LIBCPP_INLINE_VISIBILITY
592 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000593 {return __x.__i_ != __y.__i_;}
594
Howard Hinnant83eade62013-03-06 23:30:19 +0000595 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
596 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
597 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
598 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
599 template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000600};
601
602template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000603class _LIBCPP_TYPE_VIS __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000604{
605 _HashIterator __i_;
606
607 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000608 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
609 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000610public:
611 typedef forward_iterator_tag iterator_category;
612 typedef pair<key_type, mapped_type> value_type;
613 typedef typename _HashIterator::difference_type difference_type;
614 typedef const value_type& reference;
615 typedef typename __pointer_traits::template
616#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000617 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000618#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000619 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000620#endif
621 pointer;
622
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000623 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000624 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000625
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000626 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000627 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000628 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000629 __hash_map_const_iterator(
630 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000631 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000632 : __i_(__i.__i_) {}
633
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000634 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000635 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000636 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000637 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000638
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000639 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000640 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000641 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000642 __hash_map_const_iterator operator++(int)
643 {
644 __hash_map_const_iterator __t(*this);
645 ++(*this);
646 return __t;
647 }
648
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000649 friend _LIBCPP_INLINE_VISIBILITY
650 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000651 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000652 friend _LIBCPP_INLINE_VISIBILITY
653 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000654 {return __x.__i_ != __y.__i_;}
655
Howard Hinnant83eade62013-03-06 23:30:19 +0000656 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
657 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
658 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
659 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000660};
661
662template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
663 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +0000664class _LIBCPP_TYPE_VIS unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000665{
666public:
667 // types
668 typedef _Key key_type;
669 typedef _Tp mapped_type;
670 typedef _Hash hasher;
671 typedef _Pred key_equal;
672 typedef _Alloc allocator_type;
673 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000674 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000675 typedef value_type& reference;
676 typedef const value_type& const_reference;
677
678private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000679#if __cplusplus >= 201103L
680 union __value_type
681 {
682 typedef typename unordered_map::value_type value_type;
683 typedef typename unordered_map::__nc_value_type __nc_value_type;
684 value_type __cc;
685 __nc_value_type __nc;
686
687 template <class ..._Args>
688 __value_type(_Args&& ...__args)
689 : __cc(std::forward<_Args>(__args)...) {}
690
691 __value_type(const __value_type& __v)
692 : __cc(std::move(__v.__cc)) {}
693
694 __value_type(__value_type&& __v)
695 : __nc(std::move(__v.__nc)) {}
696
697 __value_type& operator=(const __value_type& __v)
698 {__nc = __v.__cc; return *this;}
699
700 __value_type& operator=(__value_type&& __v)
701 {__nc = std::move(__v.__nc); return *this;}
702
703 ~__value_type() {__cc.~value_type();}
704
705 operator const value_type& () const {return __cc;}
706 };
707#else
708 struct __value_type
709 {
710 typedef typename unordered_map::value_type value_type;
711 value_type __cc;
712
713 __value_type() {}
714
715 template <class _A0>
716 __value_type(const _A0& __a0)
717 : __cc(__a0) {}
718
719 template <class _A0, class _A1>
720 __value_type(const _A0& __a0, const _A1& __a1)
721 : __cc(__a0, __a1) {}
722
723 operator const value_type& () const {return __cc;}
724 };
725#endif
Howard Hinnantf8880d02011-12-12 17:26:24 +0000726 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
727 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000728 typedef typename allocator_traits<allocator_type>::template
729#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
730 rebind_alloc<__value_type>
731#else
732 rebind_alloc<__value_type>::other
733#endif
734 __allocator_type;
735
736 typedef __hash_table<__value_type, __hasher,
737 __key_equal, __allocator_type> __table;
738
739 __table __table_;
740
741 typedef typename __table::__node_pointer __node_pointer;
742 typedef typename __table::__node_const_pointer __node_const_pointer;
743 typedef typename __table::__node_traits __node_traits;
744 typedef typename __table::__node_allocator __node_allocator;
745 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +0000746 typedef __hash_map_node_destructor<__node_allocator> _Dp;
747 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000748 typedef allocator_traits<allocator_type> __alloc_traits;
749public:
750 typedef typename __alloc_traits::pointer pointer;
751 typedef typename __alloc_traits::const_pointer const_pointer;
752 typedef typename __alloc_traits::size_type size_type;
753 typedef typename __alloc_traits::difference_type difference_type;
754
755 typedef __hash_map_iterator<typename __table::iterator> iterator;
756 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
757 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
758 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
759
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000760 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000761 unordered_map()
762 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
763 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000764 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
765 const key_equal& __eql = key_equal());
766 unordered_map(size_type __n, const hasher& __hf,
767 const key_equal& __eql,
768 const allocator_type& __a);
769 template <class _InputIterator>
770 unordered_map(_InputIterator __first, _InputIterator __last);
771 template <class _InputIterator>
772 unordered_map(_InputIterator __first, _InputIterator __last,
773 size_type __n, const hasher& __hf = hasher(),
774 const key_equal& __eql = key_equal());
775 template <class _InputIterator>
776 unordered_map(_InputIterator __first, _InputIterator __last,
777 size_type __n, const hasher& __hf,
778 const key_equal& __eql,
779 const allocator_type& __a);
780 explicit unordered_map(const allocator_type& __a);
781 unordered_map(const unordered_map& __u);
782 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000783#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000784 unordered_map(unordered_map&& __u)
785 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000786 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000787#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000788#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000789 unordered_map(initializer_list<value_type> __il);
790 unordered_map(initializer_list<value_type> __il, size_type __n,
791 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
792 unordered_map(initializer_list<value_type> __il, size_type __n,
793 const hasher& __hf, const key_equal& __eql,
794 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000795#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000796 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000797 _LIBCPP_INLINE_VISIBILITY
798 unordered_map& operator=(const unordered_map& __u)
799 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000800#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +0000801 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000802#else
803 __table_.clear();
804 __table_.hash_function() = __u.__table_.hash_function();
805 __table_.key_eq() = __u.__table_.key_eq();
806 __table_.max_load_factor() = __u.__table_.max_load_factor();
807 __table_.__copy_assign_alloc(__u.__table_);
808 insert(__u.begin(), __u.end());
809#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +0000810 return *this;
811 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000812#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000813 unordered_map& operator=(unordered_map&& __u)
814 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000815#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000816#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000817 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000818#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000819
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000820 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000821 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000822 {return allocator_type(__table_.__node_alloc());}
823
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000824 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000825 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000827 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000828 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000829 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000830
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000831 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000832 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000833 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000834 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000836 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000838 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000839 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000840 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000841 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000842 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000843
Howard Hinnant73d21a42010-09-04 23:28:19 +0000844#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +0000845#ifndef _LIBCPP_HAS_NO_VARIADICS
846
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000847 template <class... _Args>
848 pair<iterator, bool> emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000849
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000850 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000851 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000852 iterator emplace_hint(const_iterator, _Args&&... __args)
853 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000854#endif // _LIBCPP_HAS_NO_VARIADICS
855#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000857 pair<iterator, bool> insert(const value_type& __x)
858 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000859#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000860 template <class _Pp,
861 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000863 pair<iterator, bool> insert(_Pp&& __x)
864 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000865#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000866 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000867 iterator insert(const_iterator, const value_type& __x)
868 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000869#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000870 template <class _Pp,
871 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000872 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000873 iterator insert(const_iterator, _Pp&& __x)
874 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000875#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000876 template <class _InputIterator>
877 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000878#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000880 void insert(initializer_list<value_type> __il)
881 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000882#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000883
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000885 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000887 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000889 iterator erase(const_iterator __first, const_iterator __last)
890 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000891 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000892 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000893
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000895 void swap(unordered_map& __u)
896 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
897 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000898
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000899 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000900 hasher hash_function() const
901 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000902 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000903 key_equal key_eq() const
904 {return __table_.key_eq().key_eq();}
905
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000906 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000907 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000908 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000909 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000910 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000911 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000912 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000913 pair<iterator, iterator> equal_range(const key_type& __k)
914 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000915 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000916 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
917 {return __table_.__equal_range_unique(__k);}
918
919 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000920#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000921 mapped_type& operator[](key_type&& __k);
922#endif
923
924 mapped_type& at(const key_type& __k);
925 const mapped_type& at(const key_type& __k) const;
926
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000927 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000928 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000929 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000930 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000931
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000932 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000933 size_type bucket_size(size_type __n) const
934 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000935 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000936 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
937
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000938 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000939 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000940 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000941 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000942 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000943 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000944 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000945 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000946 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000947 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000948 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000949 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
950
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000951 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000952 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000953 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000954 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000955 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000956 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000957 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000958 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000959 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000960 void reserve(size_type __n) {__table_.reserve(__n);}
961
962private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000963#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000964 __node_holder __construct_node();
965 template <class _A0>
966 typename enable_if
967 <
968 is_constructible<value_type, _A0>::value,
969 __node_holder
970 >::type
971 __construct_node(_A0&& __a0);
972 template <class _A0>
973 typename enable_if
974 <
975 is_constructible<key_type, _A0>::value,
976 __node_holder
977 >::type
978 __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000979#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000980 template <class _A0, class _A1, class ..._Args>
981 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000982#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant73d21a42010-09-04 23:28:19 +0000983#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000984 __node_holder __construct_node(const key_type& __k);
985#endif
986};
987
988template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
989unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
990 size_type __n, const hasher& __hf, const key_equal& __eql)
991 : __table_(__hf, __eql)
992{
993 __table_.rehash(__n);
994}
995
996template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
997unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
998 size_type __n, const hasher& __hf, const key_equal& __eql,
999 const allocator_type& __a)
1000 : __table_(__hf, __eql, __a)
1001{
1002 __table_.rehash(__n);
1003}
1004
1005template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001006inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001007unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1008 const allocator_type& __a)
1009 : __table_(__a)
1010{
1011}
1012
1013template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1014template <class _InputIterator>
1015unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1016 _InputIterator __first, _InputIterator __last)
1017{
1018 insert(__first, __last);
1019}
1020
1021template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1022template <class _InputIterator>
1023unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1024 _InputIterator __first, _InputIterator __last, size_type __n,
1025 const hasher& __hf, const key_equal& __eql)
1026 : __table_(__hf, __eql)
1027{
1028 __table_.rehash(__n);
1029 insert(__first, __last);
1030}
1031
1032template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1033template <class _InputIterator>
1034unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1035 _InputIterator __first, _InputIterator __last, size_type __n,
1036 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1037 : __table_(__hf, __eql, __a)
1038{
1039 __table_.rehash(__n);
1040 insert(__first, __last);
1041}
1042
1043template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1044unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1045 const unordered_map& __u)
1046 : __table_(__u.__table_)
1047{
1048 __table_.rehash(__u.bucket_count());
1049 insert(__u.begin(), __u.end());
1050}
1051
1052template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1053unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1054 const unordered_map& __u, const allocator_type& __a)
1055 : __table_(__u.__table_, __a)
1056{
1057 __table_.rehash(__u.bucket_count());
1058 insert(__u.begin(), __u.end());
1059}
1060
Howard Hinnant73d21a42010-09-04 23:28:19 +00001061#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001062
1063template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001064inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001065unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1066 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001067 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001068 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001069{
1070}
1071
1072template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1073unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1074 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001075 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001076{
1077 if (__a != __u.get_allocator())
1078 {
1079 iterator __i = __u.begin();
1080 while (__u.size() != 0)
1081 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001082 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001083 );
1084 }
1085}
1086
Howard Hinnant73d21a42010-09-04 23:28:19 +00001087#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001088
Howard Hinnante3e32912011-08-12 21:56:02 +00001089#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1090
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001091template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1092unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1093 initializer_list<value_type> __il)
1094{
1095 insert(__il.begin(), __il.end());
1096}
1097
1098template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1099unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1100 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1101 const key_equal& __eql)
1102 : __table_(__hf, __eql)
1103{
1104 __table_.rehash(__n);
1105 insert(__il.begin(), __il.end());
1106}
1107
1108template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1109unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1110 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1111 const key_equal& __eql, const allocator_type& __a)
1112 : __table_(__hf, __eql, __a)
1113{
1114 __table_.rehash(__n);
1115 insert(__il.begin(), __il.end());
1116}
1117
Howard Hinnante3e32912011-08-12 21:56:02 +00001118#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1119
Howard Hinnant73d21a42010-09-04 23:28:19 +00001120#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001121
1122template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001123inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001124unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1125unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001126 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001127{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001128 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001129 return *this;
1130}
1131
Howard Hinnant73d21a42010-09-04 23:28:19 +00001132#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001133
Howard Hinnante3e32912011-08-12 21:56:02 +00001134#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1135
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001136template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001137inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001138unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1139unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1140 initializer_list<value_type> __il)
1141{
1142 __table_.__assign_unique(__il.begin(), __il.end());
1143 return *this;
1144}
1145
Howard Hinnante3e32912011-08-12 21:56:02 +00001146#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1147
Howard Hinnant73d21a42010-09-04 23:28:19 +00001148#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001149
1150template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001151typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001152unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001153{
1154 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001155 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001156 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001157 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001158 __h.get_deleter().__second_constructed = true;
1159 return __h;
1160}
1161
1162template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001163template <class _A0>
1164typename enable_if
1165<
1166 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1167 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1168>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001169unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1170{
1171 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001172 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001173 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1174 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001175 __h.get_deleter().__first_constructed = true;
1176 __h.get_deleter().__second_constructed = true;
1177 return __h;
1178}
1179
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001180template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1181template <class _A0>
1182typename enable_if
1183<
1184 is_constructible<_Key, _A0>::value,
1185 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1186>::type
1187unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1188{
1189 __node_allocator& __na = __table_.__node_alloc();
1190 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001191 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first),
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001192 _VSTD::forward<_A0>(__a0));
1193 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001194 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001195 __h.get_deleter().__second_constructed = true;
1196 return __h;
1197}
1198
Howard Hinnant73d21a42010-09-04 23:28:19 +00001199#ifndef _LIBCPP_HAS_NO_VARIADICS
1200
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001201template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001202template <class _A0, class _A1, class ..._Args>
1203typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1204unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1205 _A1&& __a1,
1206 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001207{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001208 __node_allocator& __na = __table_.__node_alloc();
1209 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1210 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1211 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1212 _VSTD::forward<_Args>(__args)...);
1213 __h.get_deleter().__first_constructed = true;
1214 __h.get_deleter().__second_constructed = true;
1215 return __h;
1216}
1217
1218template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1219template <class... _Args>
1220pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1221unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1222{
1223 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001224 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1225 if (__r.second)
1226 __h.release();
1227 return __r;
1228}
1229
Howard Hinnant73d21a42010-09-04 23:28:19 +00001230#endif // _LIBCPP_HAS_NO_VARIADICS
1231#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001232
1233template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1234typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1235unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1236{
1237 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001238 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001239 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001240 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001241 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001242 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001243 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001244}
1245
Howard Hinnant73d21a42010-09-04 23:28:19 +00001246#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001247
1248template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1249template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001250inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001251void
1252unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1253 _InputIterator __last)
1254{
1255 for (; __first != __last; ++__first)
1256 __table_.__insert_unique(*__first);
1257}
1258
1259template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1260_Tp&
1261unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1262{
1263 iterator __i = find(__k);
1264 if (__i != end())
1265 return __i->second;
1266 __node_holder __h = __construct_node(__k);
1267 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1268 __h.release();
1269 return __r.first->second;
1270}
1271
Howard Hinnant73d21a42010-09-04 23:28:19 +00001272#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001273
1274template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1275_Tp&
1276unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1277{
1278 iterator __i = find(__k);
1279 if (__i != end())
1280 return __i->second;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001281 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001282 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1283 __h.release();
1284 return __r.first->second;
1285}
1286
Howard Hinnant73d21a42010-09-04 23:28:19 +00001287#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001288
1289template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1290_Tp&
1291unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1292{
1293 iterator __i = find(__k);
1294#ifndef _LIBCPP_NO_EXCEPTIONS
1295 if (__i == end())
1296 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001297#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001298 return __i->second;
1299}
1300
1301template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1302const _Tp&
1303unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1304{
1305 const_iterator __i = find(__k);
1306#ifndef _LIBCPP_NO_EXCEPTIONS
1307 if (__i == end())
1308 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001309#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001310 return __i->second;
1311}
1312
1313template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001314inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001315void
1316swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1317 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001318 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001319{
1320 __x.swap(__y);
1321}
1322
1323template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1324bool
1325operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1326 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1327{
1328 if (__x.size() != __y.size())
1329 return false;
1330 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1331 const_iterator;
1332 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1333 __i != __ex; ++__i)
1334 {
1335 const_iterator __j = __y.find(__i->first);
1336 if (__j == __ey || !(*__i == *__j))
1337 return false;
1338 }
1339 return true;
1340}
1341
1342template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001343inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001344bool
1345operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1346 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1347{
1348 return !(__x == __y);
1349}
1350
1351template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1352 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +00001353class _LIBCPP_TYPE_VIS unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001354{
1355public:
1356 // types
1357 typedef _Key key_type;
1358 typedef _Tp mapped_type;
1359 typedef _Hash hasher;
1360 typedef _Pred key_equal;
1361 typedef _Alloc allocator_type;
1362 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001363 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001364 typedef value_type& reference;
1365 typedef const value_type& const_reference;
1366
1367private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001368#if __cplusplus >= 201103L
1369 union __value_type
1370 {
1371 typedef typename unordered_multimap::value_type value_type;
1372 typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1373 value_type __cc;
1374 __nc_value_type __nc;
1375
1376 template <class ..._Args>
1377 __value_type(_Args&& ...__args)
1378 : __cc(std::forward<_Args>(__args)...) {}
1379
1380 __value_type(const __value_type& __v)
1381 : __cc(std::move(__v.__cc)) {}
1382
1383 __value_type(__value_type&& __v)
1384 : __nc(std::move(__v.__nc)) {}
1385
1386 __value_type& operator=(const __value_type& __v)
1387 {__nc = __v.__cc; return *this;}
1388
1389 __value_type& operator=(__value_type&& __v)
1390 {__nc = std::move(__v.__nc); return *this;}
1391
1392 ~__value_type() {__cc.~value_type();}
1393
1394 operator const value_type& () const {return __cc;}
1395 };
1396#else
1397 struct __value_type
1398 {
1399 typedef typename unordered_multimap::value_type value_type;
1400 value_type __cc;
1401
1402 __value_type() {}
1403
1404 template <class _A0>
1405 __value_type(const _A0& __a0)
1406 : __cc(__a0) {}
1407
1408 template <class _A0, class _A1>
1409 __value_type(const _A0& __a0, const _A1& __a1)
1410 : __cc(__a0, __a1) {}
1411
1412 operator const value_type& () const {return __cc;}
1413 };
1414#endif
Howard Hinnantf8880d02011-12-12 17:26:24 +00001415 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
1416 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001417 typedef typename allocator_traits<allocator_type>::template
1418#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1419 rebind_alloc<__value_type>
1420#else
1421 rebind_alloc<__value_type>::other
1422#endif
1423 __allocator_type;
1424
1425 typedef __hash_table<__value_type, __hasher,
1426 __key_equal, __allocator_type> __table;
1427
1428 __table __table_;
1429
1430 typedef typename __table::__node_traits __node_traits;
1431 typedef typename __table::__node_allocator __node_allocator;
1432 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001433 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1434 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001435 typedef allocator_traits<allocator_type> __alloc_traits;
1436public:
1437 typedef typename __alloc_traits::pointer pointer;
1438 typedef typename __alloc_traits::const_pointer const_pointer;
1439 typedef typename __alloc_traits::size_type size_type;
1440 typedef typename __alloc_traits::difference_type difference_type;
1441
1442 typedef __hash_map_iterator<typename __table::iterator> iterator;
1443 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1444 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1445 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1446
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001447 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001448 unordered_multimap()
1449 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1450 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001451 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1452 const key_equal& __eql = key_equal());
1453 unordered_multimap(size_type __n, const hasher& __hf,
1454 const key_equal& __eql,
1455 const allocator_type& __a);
1456 template <class _InputIterator>
1457 unordered_multimap(_InputIterator __first, _InputIterator __last);
1458 template <class _InputIterator>
1459 unordered_multimap(_InputIterator __first, _InputIterator __last,
1460 size_type __n, const hasher& __hf = hasher(),
1461 const key_equal& __eql = key_equal());
1462 template <class _InputIterator>
1463 unordered_multimap(_InputIterator __first, _InputIterator __last,
1464 size_type __n, const hasher& __hf,
1465 const key_equal& __eql,
1466 const allocator_type& __a);
1467 explicit unordered_multimap(const allocator_type& __a);
1468 unordered_multimap(const unordered_multimap& __u);
1469 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001470#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001471 unordered_multimap(unordered_multimap&& __u)
1472 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001473 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001474#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001475#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001476 unordered_multimap(initializer_list<value_type> __il);
1477 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1478 const hasher& __hf = hasher(),
1479 const key_equal& __eql = key_equal());
1480 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1481 const hasher& __hf, const key_equal& __eql,
1482 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001483#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001484 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001485 _LIBCPP_INLINE_VISIBILITY
1486 unordered_multimap& operator=(const unordered_multimap& __u)
1487 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001488#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +00001489 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001490#else
1491 __table_.clear();
1492 __table_.hash_function() = __u.__table_.hash_function();
1493 __table_.key_eq() = __u.__table_.key_eq();
1494 __table_.max_load_factor() = __u.__table_.max_load_factor();
1495 __table_.__copy_assign_alloc(__u.__table_);
1496 insert(__u.begin(), __u.end());
1497#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +00001498 return *this;
1499 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001500#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001501 unordered_multimap& operator=(unordered_multimap&& __u)
1502 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001503#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001504#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001505 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001506#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001507
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001508 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001509 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001510 {return allocator_type(__table_.__node_alloc());}
1511
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001512 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001513 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001515 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001516 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001517 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001518
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001520 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001522 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001524 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001526 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001528 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001530 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001531
Howard Hinnant73d21a42010-09-04 23:28:19 +00001532#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +00001533#ifndef _LIBCPP_HAS_NO_VARIADICS
1534
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001535 template <class... _Args>
1536 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001537
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001538 template <class... _Args>
1539 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001540#endif // _LIBCPP_HAS_NO_VARIADICS
1541#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001542 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001543 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001544#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001545 template <class _Pp,
1546 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001547 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001548 iterator insert(_Pp&& __x)
1549 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001550#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001551 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001552 iterator insert(const_iterator __p, const value_type& __x)
1553 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001554#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001555 template <class _Pp,
1556 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001557 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001558 iterator insert(const_iterator __p, _Pp&& __x)
1559 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001560#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001561 template <class _InputIterator>
1562 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001563#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001564 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001565 void insert(initializer_list<value_type> __il)
1566 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001567#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001568
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001569 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001570 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001571 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001572 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001574 iterator erase(const_iterator __first, const_iterator __last)
1575 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001577 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001578
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001579 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001580 void swap(unordered_multimap& __u)
1581 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1582 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001583
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001585 hasher hash_function() const
1586 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001588 key_equal key_eq() const
1589 {return __table_.key_eq().key_eq();}
1590
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001592 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001594 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001595 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001596 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001598 pair<iterator, iterator> equal_range(const key_type& __k)
1599 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001600 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001601 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1602 {return __table_.__equal_range_multi(__k);}
1603
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001604 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001605 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001606 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001607 size_type max_bucket_count() const _NOEXCEPT
1608 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001609
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001610 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001611 size_type bucket_size(size_type __n) const
1612 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001613 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001614 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1615
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001616 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001617 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001618 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001619 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001620 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001621 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001622 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001623 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001624 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001625 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001626 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001627 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1628
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001629 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001630 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001631 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001632 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001633 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001634 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001635 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001636 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001637 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001638 void reserve(size_type __n) {__table_.reserve(__n);}
1639
1640private:
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001641#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1642 __node_holder __construct_node();
1643 template <class _A0>
1644 typename enable_if
1645 <
1646 is_constructible<value_type, _A0>::value,
1647 __node_holder
1648 >::type
1649 __construct_node(_A0&& __a0);
1650 template <class _A0>
1651 typename enable_if
1652 <
1653 is_constructible<key_type, _A0>::value,
1654 __node_holder
1655 >::type
1656 __construct_node(_A0&& __a0);
1657#ifndef _LIBCPP_HAS_NO_VARIADICS
1658 template <class _A0, class _A1, class ..._Args>
1659 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1660#endif // _LIBCPP_HAS_NO_VARIADICS
1661#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001662};
1663
1664template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1666 size_type __n, const hasher& __hf, const key_equal& __eql)
1667 : __table_(__hf, __eql)
1668{
1669 __table_.rehash(__n);
1670}
1671
1672template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1673unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1674 size_type __n, const hasher& __hf, const key_equal& __eql,
1675 const allocator_type& __a)
1676 : __table_(__hf, __eql, __a)
1677{
1678 __table_.rehash(__n);
1679}
1680
1681template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1682template <class _InputIterator>
1683unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1684 _InputIterator __first, _InputIterator __last)
1685{
1686 insert(__first, __last);
1687}
1688
1689template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1690template <class _InputIterator>
1691unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1692 _InputIterator __first, _InputIterator __last, size_type __n,
1693 const hasher& __hf, const key_equal& __eql)
1694 : __table_(__hf, __eql)
1695{
1696 __table_.rehash(__n);
1697 insert(__first, __last);
1698}
1699
1700template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1701template <class _InputIterator>
1702unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1703 _InputIterator __first, _InputIterator __last, size_type __n,
1704 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1705 : __table_(__hf, __eql, __a)
1706{
1707 __table_.rehash(__n);
1708 insert(__first, __last);
1709}
1710
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001711template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001712inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001713unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1714 const allocator_type& __a)
1715 : __table_(__a)
1716{
1717}
1718
1719template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1720unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1721 const unordered_multimap& __u)
1722 : __table_(__u.__table_)
1723{
1724 __table_.rehash(__u.bucket_count());
1725 insert(__u.begin(), __u.end());
1726}
1727
1728template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1729unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1730 const unordered_multimap& __u, const allocator_type& __a)
1731 : __table_(__u.__table_, __a)
1732{
1733 __table_.rehash(__u.bucket_count());
1734 insert(__u.begin(), __u.end());
1735}
1736
Howard Hinnant73d21a42010-09-04 23:28:19 +00001737#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001738
1739template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001740inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001741unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1742 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001743 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001744 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001745{
1746}
1747
1748template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1749unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1750 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001751 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001752{
1753 if (__a != __u.get_allocator())
1754 {
1755 iterator __i = __u.begin();
1756 while (__u.size() != 0)
1757{
1758 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001759 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001760 );
1761}
1762 }
1763}
1764
Howard Hinnant73d21a42010-09-04 23:28:19 +00001765#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001766
Howard Hinnante3e32912011-08-12 21:56:02 +00001767#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1768
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001769template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1770unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1771 initializer_list<value_type> __il)
1772{
1773 insert(__il.begin(), __il.end());
1774}
1775
1776template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1777unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1778 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1779 const key_equal& __eql)
1780 : __table_(__hf, __eql)
1781{
1782 __table_.rehash(__n);
1783 insert(__il.begin(), __il.end());
1784}
1785
1786template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1787unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1788 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1789 const key_equal& __eql, const allocator_type& __a)
1790 : __table_(__hf, __eql, __a)
1791{
1792 __table_.rehash(__n);
1793 insert(__il.begin(), __il.end());
1794}
1795
Howard Hinnante3e32912011-08-12 21:56:02 +00001796#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1797
Howard Hinnant73d21a42010-09-04 23:28:19 +00001798#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001799
1800template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001801inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001802unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1803unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001804 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001805{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001806 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001807 return *this;
1808}
1809
Howard Hinnant73d21a42010-09-04 23:28:19 +00001810#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001811
Howard Hinnante3e32912011-08-12 21:56:02 +00001812#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1813
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001814template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001815inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001816unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1817unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1818 initializer_list<value_type> __il)
1819{
1820 __table_.__assign_multi(__il.begin(), __il.end());
1821 return *this;
1822}
1823
Howard Hinnante3e32912011-08-12 21:56:02 +00001824#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1825
Howard Hinnant73d21a42010-09-04 23:28:19 +00001826#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001827
1828template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001829typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001830unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001831{
1832 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001833 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001834 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001835 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001836 __h.get_deleter().__second_constructed = true;
1837 return __h;
1838}
1839
1840template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001841template <class _A0>
1842typename enable_if
1843<
1844 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1845 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1846>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001847unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1848{
1849 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001850 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001851 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1852 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001853 __h.get_deleter().__first_constructed = true;
1854 __h.get_deleter().__second_constructed = true;
1855 return __h;
1856}
1857
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001858template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1859template <class _A0>
1860typename enable_if
1861<
1862 is_constructible<_Key, _A0>::value,
1863 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1864>::type
1865unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1866{
1867 __node_allocator& __na = __table_.__node_alloc();
1868 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001869 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first),
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001870 _VSTD::forward<_A0>(__a0));
1871 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001872 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001873 __h.get_deleter().__second_constructed = true;
1874 return __h;
1875}
1876
Howard Hinnant73d21a42010-09-04 23:28:19 +00001877#ifndef _LIBCPP_HAS_NO_VARIADICS
1878
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001879template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001880template <class _A0, class _A1, class ..._Args>
1881typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1882unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1883 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001884{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001885 __node_allocator& __na = __table_.__node_alloc();
1886 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1887 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1888 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1889 _VSTD::forward<_Args>(__args)...);
1890 __h.get_deleter().__first_constructed = true;
1891 __h.get_deleter().__second_constructed = true;
1892 return __h;
1893}
1894
1895template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1896template <class... _Args>
1897typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1898unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1899{
1900 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001901 iterator __r = __table_.__node_insert_multi(__h.get());
1902 __h.release();
1903 return __r;
1904}
1905
1906template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001907template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001908typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1909unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001910 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001911{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001912 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001913 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1914 __h.release();
1915 return __r;
1916}
1917
Howard Hinnant73d21a42010-09-04 23:28:19 +00001918#endif // _LIBCPP_HAS_NO_VARIADICS
1919#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001920
1921template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1922template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001923inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001924void
1925unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1926 _InputIterator __last)
1927{
1928 for (; __first != __last; ++__first)
1929 __table_.__insert_multi(*__first);
1930}
1931
1932template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001933inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001934void
1935swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1936 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001937 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001938{
1939 __x.swap(__y);
1940}
1941
1942template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1943bool
1944operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1945 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1946{
1947 if (__x.size() != __y.size())
1948 return false;
1949 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1950 const_iterator;
1951 typedef pair<const_iterator, const_iterator> _EqRng;
1952 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1953 {
1954 _EqRng __xeq = __x.equal_range(__i->first);
1955 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001956 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1957 _VSTD::distance(__yeq.first, __yeq.second) ||
1958 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001959 return false;
1960 __i = __xeq.second;
1961 }
1962 return true;
1963}
1964
1965template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001966inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001967bool
1968operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1969 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1970{
1971 return !(__x == __y);
1972}
1973
1974_LIBCPP_END_NAMESPACE_STD
1975
1976#endif // _LIBCPP_UNORDERED_MAP