blob: 78e630757b47ae49cb22d319958a081149c0b854 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UNORDERED_MAP
12#define _LIBCPP_UNORDERED_MAP
13
14/*
15
16 unordered_map synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
24 class Alloc = allocator<pair<const Key, T>>>
25class unordered_map
26{
27public:
28 // types
29 typedef Key key_type;
30 typedef T mapped_type;
31 typedef Hash hasher;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef pair<const key_type, mapped_type> value_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000047 unordered_map()
48 noexcept(
49 is_nothrow_default_constructible<hasher>::value &&
50 is_nothrow_default_constructible<key_equal>::value &&
51 is_nothrow_default_constructible<allocator_type>::value);
52 explicit unordered_map(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000053 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 template <class InputIterator>
56 unordered_map(InputIterator f, InputIterator l,
57 size_type n = 0, const hasher& hf = hasher(),
58 const key_equal& eql = key_equal(),
59 const allocator_type& a = allocator_type());
60 explicit unordered_map(const allocator_type&);
61 unordered_map(const unordered_map&);
62 unordered_map(const unordered_map&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000063 unordered_map(unordered_map&&)
64 noexcept(
65 is_nothrow_move_constructible<hasher>::value &&
66 is_nothrow_move_constructible<key_equal>::value &&
67 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000068 unordered_map(unordered_map&&, const Allocator&);
69 unordered_map(initializer_list<value_type>, size_type n = 0,
70 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
71 const allocator_type& a = allocator_type());
72 ~unordered_map();
73 unordered_map& operator=(const unordered_map&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000074 unordered_map& operator=(unordered_map&&)
75 noexcept(
76 allocator_type::propagate_on_container_move_assignment::value &&
77 is_nothrow_move_assignable<allocator_type>::value &&
78 is_nothrow_move_assignable<hasher>::value &&
79 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000080 unordered_map& operator=(initializer_list<value_type>);
81
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000082 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000083
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000084 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000087
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000088 iterator begin() noexcept;
89 iterator end() noexcept;
90 const_iterator begin() const noexcept;
91 const_iterator end() const noexcept;
92 const_iterator cbegin() const noexcept;
93 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000094
95 template <class... Args>
96 pair<iterator, bool> emplace(Args&&... args);
97 template <class... Args>
98 iterator emplace_hint(const_iterator position, Args&&... args);
99 pair<iterator, bool> insert(const value_type& obj);
100 template <class P>
101 pair<iterator, bool> insert(P&& obj);
102 iterator insert(const_iterator hint, const value_type& obj);
103 template <class P>
104 iterator insert(const_iterator hint, P&& obj);
105 template <class InputIterator>
106 void insert(InputIterator first, InputIterator last);
107 void insert(initializer_list<value_type>);
108
109 iterator erase(const_iterator position);
110 size_type erase(const key_type& k);
111 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000112 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000113
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000114 void swap(unordered_map&)
115 noexcept(
116 (!allocator_type::propagate_on_container_swap::value ||
117 __is_nothrow_swappable<allocator_type>::value) &&
118 __is_nothrow_swappable<hasher>::value &&
119 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
121 hasher hash_function() const;
122 key_equal key_eq() const;
123
124 iterator find(const key_type& k);
125 const_iterator find(const key_type& k) const;
126 size_type count(const key_type& k) const;
127 pair<iterator, iterator> equal_range(const key_type& k);
128 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
129
130 mapped_type& operator[](const key_type& k);
131 mapped_type& operator[](key_type&& k);
132
133 mapped_type& at(const key_type& k);
134 const mapped_type& at(const key_type& k) const;
135
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
141
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
148
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
154};
155
156template <class Key, class T, class Hash, class Pred, class Alloc>
157 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000160
161template <class Key, class T, class Hash, class Pred, class Alloc>
162 bool
163 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
164 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
165
166template <class Key, class T, class Hash, class Pred, class Alloc>
167 bool
168 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
169 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
170
171template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
172 class Alloc = allocator<pair<const Key, T>>>
173class unordered_multimap
174{
175public:
176 // types
177 typedef Key key_type;
178 typedef T mapped_type;
179 typedef Hash hasher;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef pair<const key_type, mapped_type> value_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
194
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000195 unordered_multimap()
196 noexcept(
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multimap(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multimap(const allocator_type&);
209 unordered_multimap(const unordered_multimap&);
210 unordered_multimap(const unordered_multimap&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000211 unordered_multimap(unordered_multimap&&)
212 noexcept(
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216 unordered_multimap(unordered_multimap&&, const Allocator&);
217 unordered_multimap(initializer_list<value_type>, size_type n = 0,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
220 ~unordered_multimap();
221 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000222 unordered_multimap& operator=(unordered_multimap&&)
223 noexcept(
224 allocator_type::propagate_on_container_move_assignment::value &&
225 is_nothrow_move_assignable<allocator_type>::value &&
226 is_nothrow_move_assignable<hasher>::value &&
227 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000228 unordered_multimap& operator=(initializer_list<value_type>);
229
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000230 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000231
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000236 iterator begin() noexcept;
237 iterator end() noexcept;
238 const_iterator begin() const noexcept;
239 const_iterator end() const noexcept;
240 const_iterator cbegin() const noexcept;
241 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000242
243 template <class... Args>
244 iterator emplace(Args&&... args);
245 template <class... Args>
246 iterator emplace_hint(const_iterator position, Args&&... args);
247 iterator insert(const value_type& obj);
248 template <class P>
249 iterator insert(P&& obj);
250 iterator insert(const_iterator hint, const value_type& obj);
251 template <class P>
252 iterator insert(const_iterator hint, P&& obj);
253 template <class InputIterator>
254 void insert(InputIterator first, InputIterator last);
255 void insert(initializer_list<value_type>);
256
257 iterator erase(const_iterator position);
258 size_type erase(const key_type& k);
259 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000260 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000261
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000262 void swap(unordered_multimap&)
263 noexcept(
264 (!allocator_type::propagate_on_container_swap::value ||
265 __is_nothrow_swappable<allocator_type>::value) &&
266 __is_nothrow_swappable<hasher>::value &&
267 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000268
269 hasher hash_function() const;
270 key_equal key_eq() const;
271
272 iterator find(const key_type& k);
273 const_iterator find(const key_type& k) const;
274 size_type count(const key_type& k) const;
275 pair<iterator, iterator> equal_range(const key_type& k);
276 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
277
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000280
281 size_type bucket_size(size_type n) const;
282 size_type bucket(const key_type& k) const;
283
284 local_iterator begin(size_type n);
285 local_iterator end(size_type n);
286 const_local_iterator begin(size_type n) const;
287 const_local_iterator end(size_type n) const;
288 const_local_iterator cbegin(size_type n) const;
289 const_local_iterator cend(size_type n) const;
290
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000293 void max_load_factor(float z);
294 void rehash(size_type n);
295 void reserve(size_type n);
296};
297
298template <class Key, class T, class Hash, class Pred, class Alloc>
299 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302
303template <class Key, class T, class Hash, class Pred, class Alloc>
304 bool
305 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
306 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
307
308template <class Key, class T, class Hash, class Pred, class Alloc>
309 bool
310 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
311 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
312
313} // std
314
315*/
316
317#include <__config>
318#include <__hash_table>
319#include <functional>
320#include <stdexcept>
321
Howard Hinnant08e17472011-10-17 20:05:10 +0000322#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000323#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000324#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000325
326_LIBCPP_BEGIN_NAMESPACE_STD
327
Howard Hinnant9b128e02013-07-05 18:06:00 +0000328template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000329#if __has_feature(is_final)
330 && !__is_final(_Hash)
331#endif
332 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000333class __unordered_map_hasher
334 : private _Hash
335{
336public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000337 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000338 __unordered_map_hasher()
339 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
340 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000342 __unordered_map_hasher(const _Hash& __h)
343 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
344 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000345 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000346 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000347 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000348 size_t operator()(const _Cp& __x) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000349 {return static_cast<const _Hash&>(*this)(__x.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000350 _LIBCPP_INLINE_VISIBILITY
351 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000352 {return static_cast<const _Hash&>(*this)(__x);}
353};
354
Howard Hinnant9b128e02013-07-05 18:06:00 +0000355template <class _Key, class _Cp, class _Hash>
356class __unordered_map_hasher<_Key, _Cp, _Hash, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000357{
358 _Hash __hash_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000359
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000360public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000361 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000362 __unordered_map_hasher()
363 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
364 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000365 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000366 __unordered_map_hasher(const _Hash& __h)
367 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
368 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000369 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000370 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000371 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000372 size_t operator()(const _Cp& __x) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000373 {return __hash_(__x.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000374 _LIBCPP_INLINE_VISIBILITY
375 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000376 {return __hash_(__x);}
377};
378
Howard Hinnant9b128e02013-07-05 18:06:00 +0000379template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value
Howard Hinnantd4cf2152011-12-11 20:31:33 +0000380#if __has_feature(is_final)
381 && !__is_final(_Pred)
382#endif
383 >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000384class __unordered_map_equal
385 : private _Pred
386{
387public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000388 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000389 __unordered_map_equal()
390 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
391 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000393 __unordered_map_equal(const _Pred& __p)
394 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
395 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000397 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000398 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000399 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000400 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000401 _LIBCPP_INLINE_VISIBILITY
402 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000403 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000405 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000406 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000407};
408
Howard Hinnant9b128e02013-07-05 18:06:00 +0000409template <class _Key, class _Cp, class _Pred>
410class __unordered_map_equal<_Key, _Cp, _Pred, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000411{
412 _Pred __pred_;
Howard Hinnantf8880d02011-12-12 17:26:24 +0000413
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000414public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000416 __unordered_map_equal()
417 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
418 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000420 __unordered_map_equal(const _Pred& __p)
421 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
422 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000424 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000426 bool operator()(const _Cp& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000427 {return __pred_(__x.__cc.first, __y.__cc.first);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000428 _LIBCPP_INLINE_VISIBILITY
429 bool operator()(const _Cp& __x, const _Key& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000430 {return __pred_(__x.__cc.first, __y);}
Howard Hinnantf8880d02011-12-12 17:26:24 +0000431 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24 +0000432 bool operator()(const _Key& __x, const _Cp& __y) const
Howard Hinnant9b128e02013-07-05 18:06:00 +0000433 {return __pred_(__x, __y.__cc.first);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000434};
435
436template <class _Alloc>
437class __hash_map_node_destructor
438{
439 typedef _Alloc allocator_type;
440 typedef allocator_traits<allocator_type> __alloc_traits;
441 typedef typename __alloc_traits::value_type::value_type value_type;
442public:
443 typedef typename __alloc_traits::pointer pointer;
444private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000445 typedef typename value_type::value_type::first_type first_type;
446 typedef typename value_type::value_type::second_type second_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000447
448 allocator_type& __na_;
449
450 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
451
452public:
453 bool __first_constructed;
454 bool __second_constructed;
455
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000456 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000457 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000458 : __na_(__na),
459 __first_constructed(false),
460 __second_constructed(false)
461 {}
462
Howard Hinnant73d21a42010-09-04 23:28:19 +0000463#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000464 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000465 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000466 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000467 : __na_(__x.__na_),
468 __first_constructed(__x.__value_constructed),
469 __second_constructed(__x.__value_constructed)
470 {
471 __x.__value_constructed = false;
472 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000473#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000474 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000475 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
476 : __na_(__x.__na_),
477 __first_constructed(__x.__value_constructed),
478 __second_constructed(__x.__value_constructed)
479 {
480 const_cast<bool&>(__x.__value_constructed) = false;
481 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000482#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000483
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000484 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000485 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000486 {
487 if (__second_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000488 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489 if (__first_constructed)
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000490 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000491 if (__p)
492 __alloc_traits::deallocate(__na_, __p, 1);
493 }
494};
495
496template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000497class _LIBCPP_TYPE_VIS __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000498{
499 _HashIterator __i_;
500
501 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000502 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
503 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000504public:
505 typedef forward_iterator_tag iterator_category;
506 typedef pair<key_type, mapped_type> value_type;
507 typedef typename _HashIterator::difference_type difference_type;
508 typedef value_type& reference;
509 typedef typename __pointer_traits::template
510#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
511 rebind<value_type>
512#else
513 rebind<value_type>::other
514#endif
515 pointer;
516
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000517 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000518 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000519
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000520 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000521 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000522
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000524 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000526 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000528 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000529 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000531 __hash_map_iterator operator++(int)
532 {
533 __hash_map_iterator __t(*this);
534 ++(*this);
535 return __t;
536 }
537
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000538 friend _LIBCPP_INLINE_VISIBILITY
539 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000540 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000541 friend _LIBCPP_INLINE_VISIBILITY
542 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000543 {return __x.__i_ != __y.__i_;}
544
Howard Hinnant83eade62013-03-06 23:30:19 +0000545 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
546 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
547 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
548 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
549 template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000550};
551
552template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19 +0000553class _LIBCPP_TYPE_VIS __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000554{
555 _HashIterator __i_;
556
557 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000558 typedef const typename _HashIterator::value_type::value_type::first_type key_type;
559 typedef typename _HashIterator::value_type::value_type::second_type mapped_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000560public:
561 typedef forward_iterator_tag iterator_category;
562 typedef pair<key_type, mapped_type> value_type;
563 typedef typename _HashIterator::difference_type difference_type;
564 typedef const value_type& reference;
565 typedef typename __pointer_traits::template
566#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000567 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000569 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000570#endif
571 pointer;
572
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000574 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000575
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000577 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000579 __hash_map_const_iterator(
580 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000581 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000582 : __i_(__i.__i_) {}
583
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000585 reference operator*() const {return __i_->__cc;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000586 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000587 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000588
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000590 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000592 __hash_map_const_iterator operator++(int)
593 {
594 __hash_map_const_iterator __t(*this);
595 ++(*this);
596 return __t;
597 }
598
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000599 friend _LIBCPP_INLINE_VISIBILITY
600 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000601 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000602 friend _LIBCPP_INLINE_VISIBILITY
603 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000604 {return __x.__i_ != __y.__i_;}
605
Howard Hinnant83eade62013-03-06 23:30:19 +0000606 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
607 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
608 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
609 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000610};
611
612template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
613 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +0000614class _LIBCPP_TYPE_VIS unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000615{
616public:
617 // types
618 typedef _Key key_type;
619 typedef _Tp mapped_type;
620 typedef _Hash hasher;
621 typedef _Pred key_equal;
622 typedef _Alloc allocator_type;
623 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000624 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000625 typedef value_type& reference;
626 typedef const value_type& const_reference;
627
628private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000629#if __cplusplus >= 201103L
630 union __value_type
631 {
632 typedef typename unordered_map::value_type value_type;
633 typedef typename unordered_map::__nc_value_type __nc_value_type;
634 value_type __cc;
635 __nc_value_type __nc;
636
637 template <class ..._Args>
638 __value_type(_Args&& ...__args)
639 : __cc(std::forward<_Args>(__args)...) {}
640
641 __value_type(const __value_type& __v)
642 : __cc(std::move(__v.__cc)) {}
643
644 __value_type(__value_type&& __v)
645 : __nc(std::move(__v.__nc)) {}
646
647 __value_type& operator=(const __value_type& __v)
648 {__nc = __v.__cc; return *this;}
649
650 __value_type& operator=(__value_type&& __v)
651 {__nc = std::move(__v.__nc); return *this;}
652
653 ~__value_type() {__cc.~value_type();}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000654 };
655#else
656 struct __value_type
657 {
658 typedef typename unordered_map::value_type value_type;
659 value_type __cc;
660
661 __value_type() {}
662
663 template <class _A0>
664 __value_type(const _A0& __a0)
665 : __cc(__a0) {}
666
667 template <class _A0, class _A1>
668 __value_type(const _A0& __a0, const _A1& __a1)
669 : __cc(__a0, __a1) {}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000670 };
671#endif
Howard Hinnant9b128e02013-07-05 18:06:00 +0000672 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
673 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000674 typedef typename allocator_traits<allocator_type>::template
675#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
676 rebind_alloc<__value_type>
677#else
678 rebind_alloc<__value_type>::other
679#endif
680 __allocator_type;
681
682 typedef __hash_table<__value_type, __hasher,
683 __key_equal, __allocator_type> __table;
684
685 __table __table_;
686
687 typedef typename __table::__node_pointer __node_pointer;
688 typedef typename __table::__node_const_pointer __node_const_pointer;
689 typedef typename __table::__node_traits __node_traits;
690 typedef typename __table::__node_allocator __node_allocator;
691 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +0000692 typedef __hash_map_node_destructor<__node_allocator> _Dp;
693 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000694 typedef allocator_traits<allocator_type> __alloc_traits;
695public:
696 typedef typename __alloc_traits::pointer pointer;
697 typedef typename __alloc_traits::const_pointer const_pointer;
698 typedef typename __alloc_traits::size_type size_type;
699 typedef typename __alloc_traits::difference_type difference_type;
700
701 typedef __hash_map_iterator<typename __table::iterator> iterator;
702 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
703 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
704 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
705
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000706 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000707 unordered_map()
708 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
709 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000710 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
711 const key_equal& __eql = key_equal());
712 unordered_map(size_type __n, const hasher& __hf,
713 const key_equal& __eql,
714 const allocator_type& __a);
715 template <class _InputIterator>
716 unordered_map(_InputIterator __first, _InputIterator __last);
717 template <class _InputIterator>
718 unordered_map(_InputIterator __first, _InputIterator __last,
719 size_type __n, const hasher& __hf = hasher(),
720 const key_equal& __eql = key_equal());
721 template <class _InputIterator>
722 unordered_map(_InputIterator __first, _InputIterator __last,
723 size_type __n, const hasher& __hf,
724 const key_equal& __eql,
725 const allocator_type& __a);
726 explicit unordered_map(const allocator_type& __a);
727 unordered_map(const unordered_map& __u);
728 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000729#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000730 unordered_map(unordered_map&& __u)
731 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000732 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000733#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000734#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000735 unordered_map(initializer_list<value_type> __il);
736 unordered_map(initializer_list<value_type> __il, size_type __n,
737 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
738 unordered_map(initializer_list<value_type> __il, size_type __n,
739 const hasher& __hf, const key_equal& __eql,
740 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000741#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000742 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000743 _LIBCPP_INLINE_VISIBILITY
744 unordered_map& operator=(const unordered_map& __u)
745 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000746#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +0000747 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +0000748#else
749 __table_.clear();
750 __table_.hash_function() = __u.__table_.hash_function();
751 __table_.key_eq() = __u.__table_.key_eq();
752 __table_.max_load_factor() = __u.__table_.max_load_factor();
753 __table_.__copy_assign_alloc(__u.__table_);
754 insert(__u.begin(), __u.end());
755#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +0000756 return *this;
757 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000758#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000759 unordered_map& operator=(unordered_map&& __u)
760 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000761#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000762#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000763 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000764#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000765
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000766 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000767 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000768 {return allocator_type(__table_.__node_alloc());}
769
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000771 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000772 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000773 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000774 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000775 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000776
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000777 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000778 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000779 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000780 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000781 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000782 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000784 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000786 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000788 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000789
Howard Hinnant73d21a42010-09-04 23:28:19 +0000790#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +0000791#ifndef _LIBCPP_HAS_NO_VARIADICS
792
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000793 template <class... _Args>
794 pair<iterator, bool> emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000795
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000796 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000797 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000798 iterator emplace_hint(const_iterator, _Args&&... __args)
799 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000800#endif // _LIBCPP_HAS_NO_VARIADICS
801#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000802 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000803 pair<iterator, bool> insert(const value_type& __x)
804 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000805#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000806 template <class _Pp,
807 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000808 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000809 pair<iterator, bool> insert(_Pp&& __x)
810 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000811#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000812 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000813 iterator insert(const_iterator, const value_type& __x)
814 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000815#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +0000816 template <class _Pp,
817 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +0000819 iterator insert(const_iterator, _Pp&& __x)
820 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000821#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000822 template <class _InputIterator>
823 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000824#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000825 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000826 void insert(initializer_list<value_type> __il)
827 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000828#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000829
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000830 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000831 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000832 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000833 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000834 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000835 iterator erase(const_iterator __first, const_iterator __last)
836 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000838 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000839
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000841 void swap(unordered_map& __u)
842 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
843 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000844
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000845 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000846 hasher hash_function() const
847 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000849 key_equal key_eq() const
850 {return __table_.key_eq().key_eq();}
851
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000852 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000853 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000855 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000857 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000858 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000859 pair<iterator, iterator> equal_range(const key_type& __k)
860 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
863 {return __table_.__equal_range_unique(__k);}
864
865 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000866#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000867 mapped_type& operator[](key_type&& __k);
868#endif
869
870 mapped_type& at(const key_type& __k);
871 const mapped_type& at(const key_type& __k) const;
872
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000874 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000875 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000876 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000877
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000878 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000879 size_type bucket_size(size_type __n) const
880 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000881 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000882 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
883
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000885 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000887 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000889 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000890 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000891 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000893 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000895 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
896
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000898 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000899 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000900 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000902 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000904 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000906 void reserve(size_type __n) {__table_.reserve(__n);}
907
908private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000909#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000910 __node_holder __construct_node();
911 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000912 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000913 __construct_node(_A0&& __a0);
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000914 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000915#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21 +0000916 template <class _A0, class _A1, class ..._Args>
917 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000918#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +0000919#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
920 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000921};
922
923template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
924unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
925 size_type __n, const hasher& __hf, const key_equal& __eql)
926 : __table_(__hf, __eql)
927{
928 __table_.rehash(__n);
929}
930
931template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
932unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
933 size_type __n, const hasher& __hf, const key_equal& __eql,
934 const allocator_type& __a)
935 : __table_(__hf, __eql, __a)
936{
937 __table_.rehash(__n);
938}
939
940template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000941inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000942unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
943 const allocator_type& __a)
944 : __table_(__a)
945{
946}
947
948template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
949template <class _InputIterator>
950unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
951 _InputIterator __first, _InputIterator __last)
952{
953 insert(__first, __last);
954}
955
956template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
957template <class _InputIterator>
958unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
959 _InputIterator __first, _InputIterator __last, size_type __n,
960 const hasher& __hf, const key_equal& __eql)
961 : __table_(__hf, __eql)
962{
963 __table_.rehash(__n);
964 insert(__first, __last);
965}
966
967template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
968template <class _InputIterator>
969unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
970 _InputIterator __first, _InputIterator __last, size_type __n,
971 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
972 : __table_(__hf, __eql, __a)
973{
974 __table_.rehash(__n);
975 insert(__first, __last);
976}
977
978template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
979unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
980 const unordered_map& __u)
981 : __table_(__u.__table_)
982{
983 __table_.rehash(__u.bucket_count());
984 insert(__u.begin(), __u.end());
985}
986
987template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
988unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
989 const unordered_map& __u, const allocator_type& __a)
990 : __table_(__u.__table_, __a)
991{
992 __table_.rehash(__u.bucket_count());
993 insert(__u.begin(), __u.end());
994}
995
Howard Hinnant73d21a42010-09-04 23:28:19 +0000996#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000997
998template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000999inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001000unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1001 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001002 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001003 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001004{
1005}
1006
1007template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1008unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1009 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001010 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001011{
1012 if (__a != __u.get_allocator())
1013 {
1014 iterator __i = __u.begin();
1015 while (__u.size() != 0)
1016 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001017 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001018 );
1019 }
1020}
1021
Howard Hinnant73d21a42010-09-04 23:28:19 +00001022#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001023
Howard Hinnante3e32912011-08-12 21:56:02 +00001024#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1025
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001026template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1027unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1028 initializer_list<value_type> __il)
1029{
1030 insert(__il.begin(), __il.end());
1031}
1032
1033template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1034unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1035 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1036 const key_equal& __eql)
1037 : __table_(__hf, __eql)
1038{
1039 __table_.rehash(__n);
1040 insert(__il.begin(), __il.end());
1041}
1042
1043template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1044unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1045 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1046 const key_equal& __eql, const allocator_type& __a)
1047 : __table_(__hf, __eql, __a)
1048{
1049 __table_.rehash(__n);
1050 insert(__il.begin(), __il.end());
1051}
1052
Howard Hinnante3e32912011-08-12 21:56:02 +00001053#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1054
Howard Hinnant73d21a42010-09-04 23:28:19 +00001055#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001056
1057template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001058inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001059unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1060unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001061 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001062{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001063 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001064 return *this;
1065}
1066
Howard Hinnant73d21a42010-09-04 23:28:19 +00001067#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001068
Howard Hinnante3e32912011-08-12 21:56:02 +00001069#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1070
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001071template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001072inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001073unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1074unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1075 initializer_list<value_type> __il)
1076{
1077 __table_.__assign_unique(__il.begin(), __il.end());
1078 return *this;
1079}
1080
Howard Hinnante3e32912011-08-12 21:56:02 +00001081#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1082
Howard Hinnant73d21a42010-09-04 23:28:19 +00001083#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001084
1085template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001086typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001087unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001088{
1089 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001090 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001091 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001092 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001093 __h.get_deleter().__second_constructed = true;
1094 return __h;
1095}
1096
1097template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001098template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001099typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001100unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1101{
1102 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001103 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001104 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1105 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001106 __h.get_deleter().__first_constructed = true;
1107 __h.get_deleter().__second_constructed = true;
1108 return __h;
1109}
1110
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001111template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001112typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1113unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k)
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001114{
1115 __node_allocator& __na = __table_.__node_alloc();
1116 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001117 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001118 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001119 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001120 __h.get_deleter().__second_constructed = true;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001121 return _VSTD::move(__h);
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001122}
1123
Howard Hinnant73d21a42010-09-04 23:28:19 +00001124#ifndef _LIBCPP_HAS_NO_VARIADICS
1125
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001126template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001127template <class _A0, class _A1, class ..._Args>
1128typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1129unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1130 _A1&& __a1,
1131 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001132{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001133 __node_allocator& __na = __table_.__node_alloc();
1134 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1135 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1136 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1137 _VSTD::forward<_Args>(__args)...);
1138 __h.get_deleter().__first_constructed = true;
1139 __h.get_deleter().__second_constructed = true;
1140 return __h;
1141}
1142
1143template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1144template <class... _Args>
1145pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1146unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1147{
1148 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001149 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1150 if (__r.second)
1151 __h.release();
1152 return __r;
1153}
1154
Howard Hinnant73d21a42010-09-04 23:28:19 +00001155#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001156#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001157
1158template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1159typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001160unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001161{
1162 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001163 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001164 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001165 __h.get_deleter().__first_constructed = true;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001166 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001167 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001168 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001169}
1170
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001171template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1172template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001173inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001174void
1175unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1176 _InputIterator __last)
1177{
1178 for (; __first != __last; ++__first)
1179 __table_.__insert_unique(*__first);
1180}
1181
1182template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1183_Tp&
1184unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1185{
1186 iterator __i = find(__k);
1187 if (__i != end())
1188 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001189 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001190 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1191 __h.release();
1192 return __r.first->second;
1193}
1194
Howard Hinnant73d21a42010-09-04 23:28:19 +00001195#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001196
1197template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1198_Tp&
1199unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1200{
1201 iterator __i = find(__k);
1202 if (__i != end())
1203 return __i->second;
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001204 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001205 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1206 __h.release();
1207 return __r.first->second;
1208}
1209
Howard Hinnant73d21a42010-09-04 23:28:19 +00001210#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001211
1212template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1213_Tp&
1214unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1215{
1216 iterator __i = find(__k);
1217#ifndef _LIBCPP_NO_EXCEPTIONS
1218 if (__i == end())
1219 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001220#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001221 return __i->second;
1222}
1223
1224template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1225const _Tp&
1226unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1227{
1228 const_iterator __i = find(__k);
1229#ifndef _LIBCPP_NO_EXCEPTIONS
1230 if (__i == end())
1231 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001232#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001233 return __i->second;
1234}
1235
1236template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001237inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001238void
1239swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1240 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001241 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001242{
1243 __x.swap(__y);
1244}
1245
1246template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1247bool
1248operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1249 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1250{
1251 if (__x.size() != __y.size())
1252 return false;
1253 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1254 const_iterator;
1255 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1256 __i != __ex; ++__i)
1257 {
1258 const_iterator __j = __y.find(__i->first);
1259 if (__j == __ey || !(*__i == *__j))
1260 return false;
1261 }
1262 return true;
1263}
1264
1265template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001266inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001267bool
1268operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1269 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1270{
1271 return !(__x == __y);
1272}
1273
1274template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1275 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19 +00001276class _LIBCPP_TYPE_VIS unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001277{
1278public:
1279 // types
1280 typedef _Key key_type;
1281 typedef _Tp mapped_type;
1282 typedef _Hash hasher;
1283 typedef _Pred key_equal;
1284 typedef _Alloc allocator_type;
1285 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001286 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001287 typedef value_type& reference;
1288 typedef const value_type& const_reference;
1289
1290private:
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001291#if __cplusplus >= 201103L
1292 union __value_type
1293 {
1294 typedef typename unordered_multimap::value_type value_type;
1295 typedef typename unordered_multimap::__nc_value_type __nc_value_type;
1296 value_type __cc;
1297 __nc_value_type __nc;
1298
1299 template <class ..._Args>
1300 __value_type(_Args&& ...__args)
1301 : __cc(std::forward<_Args>(__args)...) {}
1302
1303 __value_type(const __value_type& __v)
1304 : __cc(std::move(__v.__cc)) {}
1305
1306 __value_type(__value_type&& __v)
1307 : __nc(std::move(__v.__nc)) {}
1308
1309 __value_type& operator=(const __value_type& __v)
1310 {__nc = __v.__cc; return *this;}
1311
1312 __value_type& operator=(__value_type&& __v)
1313 {__nc = std::move(__v.__nc); return *this;}
1314
1315 ~__value_type() {__cc.~value_type();}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001316 };
1317#else
1318 struct __value_type
1319 {
1320 typedef typename unordered_multimap::value_type value_type;
1321 value_type __cc;
1322
1323 __value_type() {}
1324
1325 template <class _A0>
1326 __value_type(const _A0& __a0)
1327 : __cc(__a0) {}
1328
1329 template <class _A0, class _A1>
1330 __value_type(const _A0& __a0, const _A1& __a1)
1331 : __cc(__a0, __a1) {}
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001332 };
1333#endif
Howard Hinnant9b128e02013-07-05 18:06:00 +00001334 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher;
1335 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001336 typedef typename allocator_traits<allocator_type>::template
1337#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1338 rebind_alloc<__value_type>
1339#else
1340 rebind_alloc<__value_type>::other
1341#endif
1342 __allocator_type;
1343
1344 typedef __hash_table<__value_type, __hasher,
1345 __key_equal, __allocator_type> __table;
1346
1347 __table __table_;
1348
1349 typedef typename __table::__node_traits __node_traits;
1350 typedef typename __table::__node_allocator __node_allocator;
1351 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50 +00001352 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1353 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001354 typedef allocator_traits<allocator_type> __alloc_traits;
1355public:
1356 typedef typename __alloc_traits::pointer pointer;
1357 typedef typename __alloc_traits::const_pointer const_pointer;
1358 typedef typename __alloc_traits::size_type size_type;
1359 typedef typename __alloc_traits::difference_type difference_type;
1360
1361 typedef __hash_map_iterator<typename __table::iterator> iterator;
1362 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1363 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1364 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1365
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001366 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001367 unordered_multimap()
1368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1369 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001370 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1371 const key_equal& __eql = key_equal());
1372 unordered_multimap(size_type __n, const hasher& __hf,
1373 const key_equal& __eql,
1374 const allocator_type& __a);
1375 template <class _InputIterator>
1376 unordered_multimap(_InputIterator __first, _InputIterator __last);
1377 template <class _InputIterator>
1378 unordered_multimap(_InputIterator __first, _InputIterator __last,
1379 size_type __n, const hasher& __hf = hasher(),
1380 const key_equal& __eql = key_equal());
1381 template <class _InputIterator>
1382 unordered_multimap(_InputIterator __first, _InputIterator __last,
1383 size_type __n, const hasher& __hf,
1384 const key_equal& __eql,
1385 const allocator_type& __a);
1386 explicit unordered_multimap(const allocator_type& __a);
1387 unordered_multimap(const unordered_multimap& __u);
1388 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001389#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001390 unordered_multimap(unordered_multimap&& __u)
1391 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001392 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001393#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001394#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001395 unordered_multimap(initializer_list<value_type> __il);
1396 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1397 const hasher& __hf = hasher(),
1398 const key_equal& __eql = key_equal());
1399 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1400 const hasher& __hf, const key_equal& __eql,
1401 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001402#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001403 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001404 _LIBCPP_INLINE_VISIBILITY
1405 unordered_multimap& operator=(const unordered_multimap& __u)
1406 {
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001407#if __cplusplus >= 201103L
Howard Hinnant61aa6012011-07-01 19:24:36 +00001408 __table_ = __u.__table_;
Howard Hinnant7a6b7ce2013-06-22 15:21:29 +00001409#else
1410 __table_.clear();
1411 __table_.hash_function() = __u.__table_.hash_function();
1412 __table_.key_eq() = __u.__table_.key_eq();
1413 __table_.max_load_factor() = __u.__table_.max_load_factor();
1414 __table_.__copy_assign_alloc(__u.__table_);
1415 insert(__u.begin(), __u.end());
1416#endif
Howard Hinnant61aa6012011-07-01 19:24:36 +00001417 return *this;
1418 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001419#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001420 unordered_multimap& operator=(unordered_multimap&& __u)
1421 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001422#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001423#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001424 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001425#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001426
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001428 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001429 {return allocator_type(__table_.__node_alloc());}
1430
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001431 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001432 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001433 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001434 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001435 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001436 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001437
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001438 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001439 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001440 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001441 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001442 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001443 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001444 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001445 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001446 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001447 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001448 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001449 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001450
Howard Hinnant73d21a42010-09-04 23:28:19 +00001451#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19 +00001452#ifndef _LIBCPP_HAS_NO_VARIADICS
1453
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001454 template <class... _Args>
1455 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001456
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001457 template <class... _Args>
1458 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001459#endif // _LIBCPP_HAS_NO_VARIADICS
1460#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001462 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001463#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001464 template <class _Pp,
1465 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001467 iterator insert(_Pp&& __x)
1468 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001469#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001470 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001471 iterator insert(const_iterator __p, const value_type& __x)
1472 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001473#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50 +00001474 template <class _Pp,
1475 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001476 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50 +00001477 iterator insert(const_iterator __p, _Pp&& __x)
1478 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001479#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001480 template <class _InputIterator>
1481 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001482#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001483 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001484 void insert(initializer_list<value_type> __il)
1485 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001486#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001487
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001489 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001490 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001491 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001492 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001493 iterator erase(const_iterator __first, const_iterator __last)
1494 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001495 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001496 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001497
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001498 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001499 void swap(unordered_multimap& __u)
1500 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1501 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001502
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001503 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001504 hasher hash_function() const
1505 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001507 key_equal key_eq() const
1508 {return __table_.key_eq().key_eq();}
1509
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001510 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001511 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001512 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001513 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001515 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001516 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001517 pair<iterator, iterator> equal_range(const key_type& __k)
1518 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001520 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1521 {return __table_.__equal_range_multi(__k);}
1522
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001524 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001526 size_type max_bucket_count() const _NOEXCEPT
1527 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001528
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001530 size_type bucket_size(size_type __n) const
1531 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001532 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001533 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1534
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001535 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001536 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001537 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001538 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001539 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001540 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001541 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001542 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001543 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001544 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001545 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001546 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1547
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001548 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001549 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001550 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001551 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001552 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001553 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001555 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001556 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001557 void reserve(size_type __n) {__table_.reserve(__n);}
1558
1559private:
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001560#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1561 __node_holder __construct_node();
1562 template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001563 __node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001564 __construct_node(_A0&& __a0);
1565#ifndef _LIBCPP_HAS_NO_VARIADICS
1566 template <class _A0, class _A1, class ..._Args>
1567 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1568#endif // _LIBCPP_HAS_NO_VARIADICS
1569#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001570};
1571
1572template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1573unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1574 size_type __n, const hasher& __hf, const key_equal& __eql)
1575 : __table_(__hf, __eql)
1576{
1577 __table_.rehash(__n);
1578}
1579
1580template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1581unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1582 size_type __n, const hasher& __hf, const key_equal& __eql,
1583 const allocator_type& __a)
1584 : __table_(__hf, __eql, __a)
1585{
1586 __table_.rehash(__n);
1587}
1588
1589template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1590template <class _InputIterator>
1591unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1592 _InputIterator __first, _InputIterator __last)
1593{
1594 insert(__first, __last);
1595}
1596
1597template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1598template <class _InputIterator>
1599unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1600 _InputIterator __first, _InputIterator __last, size_type __n,
1601 const hasher& __hf, const key_equal& __eql)
1602 : __table_(__hf, __eql)
1603{
1604 __table_.rehash(__n);
1605 insert(__first, __last);
1606}
1607
1608template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1609template <class _InputIterator>
1610unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1611 _InputIterator __first, _InputIterator __last, size_type __n,
1612 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1613 : __table_(__hf, __eql, __a)
1614{
1615 __table_.rehash(__n);
1616 insert(__first, __last);
1617}
1618
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001619template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001620inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001621unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1622 const allocator_type& __a)
1623 : __table_(__a)
1624{
1625}
1626
1627template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1628unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1629 const unordered_multimap& __u)
1630 : __table_(__u.__table_)
1631{
1632 __table_.rehash(__u.bucket_count());
1633 insert(__u.begin(), __u.end());
1634}
1635
1636template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1637unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638 const unordered_multimap& __u, const allocator_type& __a)
1639 : __table_(__u.__table_, __a)
1640{
1641 __table_.rehash(__u.bucket_count());
1642 insert(__u.begin(), __u.end());
1643}
1644
Howard Hinnant73d21a42010-09-04 23:28:19 +00001645#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001646
1647template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001648inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001649unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1650 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001651 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001652 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001653{
1654}
1655
1656template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1657unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1658 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001659 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001660{
1661 if (__a != __u.get_allocator())
1662 {
1663 iterator __i = __u.begin();
1664 while (__u.size() != 0)
1665{
1666 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001667 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001668 );
1669}
1670 }
1671}
1672
Howard Hinnant73d21a42010-09-04 23:28:19 +00001673#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001674
Howard Hinnante3e32912011-08-12 21:56:02 +00001675#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1676
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001677template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1678unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1679 initializer_list<value_type> __il)
1680{
1681 insert(__il.begin(), __il.end());
1682}
1683
1684template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1685unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1686 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1687 const key_equal& __eql)
1688 : __table_(__hf, __eql)
1689{
1690 __table_.rehash(__n);
1691 insert(__il.begin(), __il.end());
1692}
1693
1694template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1695unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1696 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1697 const key_equal& __eql, const allocator_type& __a)
1698 : __table_(__hf, __eql, __a)
1699{
1700 __table_.rehash(__n);
1701 insert(__il.begin(), __il.end());
1702}
1703
Howard Hinnante3e32912011-08-12 21:56:02 +00001704#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1705
Howard Hinnant73d21a42010-09-04 23:28:19 +00001706#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001707
1708template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001709inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001710unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1711unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001712 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001713{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001714 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001715 return *this;
1716}
1717
Howard Hinnant73d21a42010-09-04 23:28:19 +00001718#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001719
Howard Hinnante3e32912011-08-12 21:56:02 +00001720#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1721
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001722template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001723inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001724unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1725unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1726 initializer_list<value_type> __il)
1727{
1728 __table_.__assign_multi(__il.begin(), __il.end());
1729 return *this;
1730}
1731
Howard Hinnante3e32912011-08-12 21:56:02 +00001732#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1733
Howard Hinnant73d21a42010-09-04 23:28:19 +00001734#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001735
1736template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001737typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001738unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001739{
1740 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001741 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001742 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001743 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001744 __h.get_deleter().__second_constructed = true;
1745 return __h;
1746}
1747
1748template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001749template <class _A0>
Howard Hinnantb66e1c32013-07-04 20:59:16 +00001750typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001751unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1752{
1753 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:50 +00001754 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001755 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1756 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001757 __h.get_deleter().__first_constructed = true;
1758 __h.get_deleter().__second_constructed = true;
1759 return __h;
1760}
1761
Howard Hinnant73d21a42010-09-04 23:28:19 +00001762#ifndef _LIBCPP_HAS_NO_VARIADICS
1763
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001764template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001765template <class _A0, class _A1, class ..._Args>
1766typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1767unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1768 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001769{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001770 __node_allocator& __na = __table_.__node_alloc();
1771 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1772 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1773 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1774 _VSTD::forward<_Args>(__args)...);
1775 __h.get_deleter().__first_constructed = true;
1776 __h.get_deleter().__second_constructed = true;
1777 return __h;
1778}
1779
1780template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1781template <class... _Args>
1782typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1783unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1784{
1785 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001786 iterator __r = __table_.__node_insert_multi(__h.get());
1787 __h.release();
1788 return __r;
1789}
1790
1791template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001792template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001793typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1794unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001795 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001796{
Howard Hinnant635ce1d2012-05-25 22:04:21 +00001797 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001798 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1799 __h.release();
1800 return __r;
1801}
1802
Howard Hinnant73d21a42010-09-04 23:28:19 +00001803#endif // _LIBCPP_HAS_NO_VARIADICS
1804#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001805
1806template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1807template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001808inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001809void
1810unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1811 _InputIterator __last)
1812{
1813 for (; __first != __last; ++__first)
1814 __table_.__insert_multi(*__first);
1815}
1816
1817template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001818inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001819void
1820swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1821 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001822 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001823{
1824 __x.swap(__y);
1825}
1826
1827template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1828bool
1829operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1830 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1831{
1832 if (__x.size() != __y.size())
1833 return false;
1834 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1835 const_iterator;
1836 typedef pair<const_iterator, const_iterator> _EqRng;
1837 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1838 {
1839 _EqRng __xeq = __x.equal_range(__i->first);
1840 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001841 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1842 _VSTD::distance(__yeq.first, __yeq.second) ||
1843 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001844 return false;
1845 __i = __xeq.second;
1846 }
1847 return true;
1848}
1849
1850template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001851inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001852bool
1853operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1854 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1855{
1856 return !(__x == __y);
1857}
1858
1859_LIBCPP_END_NAMESPACE_STD
1860
1861#endif // _LIBCPP_UNORDERED_MAP