blob: 235b2eabb6035b5c29837ffdb8e166f34dd1318b [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:161// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:014// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:165//
Howard Hinnantb64f8b02010-11-16 22:09:026// 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:168//
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:2447 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:1653 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:2463 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:1668 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:2474 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:1680 unordered_map& operator=(initializer_list<value_type>);
81
Howard Hinnant5f2f14c2011-06-04 18:54:2482 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:1683
Howard Hinnant5f2f14c2011-06-04 18:54:2484 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:1687
Howard Hinnant5f2f14c2011-06-04 18:54:2488 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:1694
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:24112 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16113
Howard Hinnant5f2f14c2011-06-04 18:54:24114 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:16120
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:24136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16138
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:24149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16151 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:24158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16160
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:24195 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:16201 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:24211 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:16216 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:24222 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:16228 unordered_multimap& operator=(initializer_list<value_type>);
229
Howard Hinnant5f2f14c2011-06-04 18:54:24230 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16231
Howard Hinnant5f2f14c2011-06-04 18:54:24232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16235
Howard Hinnant5f2f14c2011-06-04 18:54:24236 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:16242
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:24260 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16261
Howard Hinnant5f2f14c2011-06-04 18:54:24262 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:16268
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:24278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16280
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:24291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16293 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:24300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16302
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:10322#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16323#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10324#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16325
326_LIBCPP_BEGIN_NAMESPACE_STD
327
Howard Hinnantf8880d02011-12-12 17:26:24328template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value
Howard Hinnantd4cf2152011-12-11 20:31:33329#if __has_feature(is_final)
330 && !__is_final(_Hash)
331#endif
332 >
Howard Hinnantbc8d3f92010-05-11 19:42:16333class __unordered_map_hasher
334 : private _Hash
335{
Howard Hinnantf8880d02011-12-12 17:26:24336 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
337 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16338public:
Howard Hinnantee6ccd02010-09-23 18:58:28339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24340 __unordered_map_hasher()
341 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
342 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28343 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24344 __unordered_map_hasher(const _Hash& __h)
345 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
346 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28347 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24348 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28349 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24350 size_t operator()(const _Pp& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16351 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24353 size_t operator()(const _Cp& __x) const
354 {return static_cast<const _Hash&>(*this)(__x.first);}
355 _LIBCPP_INLINE_VISIBILITY
356 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16357 {return static_cast<const _Hash&>(*this)(__x);}
358};
359
Howard Hinnantf8880d02011-12-12 17:26:24360template <class _Key, class _Tp, class _Hash>
361class __unordered_map_hasher<_Key, _Tp, _Hash, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16362{
363 _Hash __hash_;
Howard Hinnantf8880d02011-12-12 17:26:24364
365 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
366 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16367public:
Howard Hinnantee6ccd02010-09-23 18:58:28368 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24369 __unordered_map_hasher()
370 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
371 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28372 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24373 __unordered_map_hasher(const _Hash& __h)
374 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
375 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28376 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24377 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28378 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24379 size_t operator()(const _Pp& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16380 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28381 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24382 size_t operator()(const _Cp& __x) const
383 {return __hash_(__x.first);}
384 _LIBCPP_INLINE_VISIBILITY
385 size_t operator()(const _Key& __x) const
Howard Hinnantbc8d3f92010-05-11 19:42:16386 {return __hash_(__x);}
387};
388
Howard Hinnantf8880d02011-12-12 17:26:24389template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value
Howard Hinnantd4cf2152011-12-11 20:31:33390#if __has_feature(is_final)
391 && !__is_final(_Pred)
392#endif
393 >
Howard Hinnantbc8d3f92010-05-11 19:42:16394class __unordered_map_equal
395 : private _Pred
396{
Howard Hinnantf8880d02011-12-12 17:26:24397 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
398 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16399public:
Howard Hinnantee6ccd02010-09-23 18:58:28400 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24401 __unordered_map_equal()
402 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
403 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24405 __unordered_map_equal(const _Pred& __p)
406 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
407 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24409 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28410 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24411 bool operator()(const _Pp& __x, const _Pp& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16412 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24414 bool operator()(const _Pp& __x, const _Cp& __y) const
415 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28416 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24417 bool operator()(const _Pp& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16418 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24420 bool operator()(const _Cp& __x, const _Pp& __y) const
421 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
422 _LIBCPP_INLINE_VISIBILITY
423 bool operator()(const _Cp& __x, const _Cp& __y) const
424 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
425 _LIBCPP_INLINE_VISIBILITY
426 bool operator()(const _Cp& __x, const _Key& __y) const
427 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
428 _LIBCPP_INLINE_VISIBILITY
429 bool operator()(const _Key& __x, const _Pp& __y) const
430 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
431 _LIBCPP_INLINE_VISIBILITY
432 bool operator()(const _Key& __x, const _Cp& __y) const
433 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
434 _LIBCPP_INLINE_VISIBILITY
435 bool operator()(const _Key& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16436 {return static_cast<const _Pred&>(*this)(__x, __y);}
437};
438
Howard Hinnantf8880d02011-12-12 17:26:24439template <class _Key, class _Tp, class _Pred>
440class __unordered_map_equal<_Key, _Tp, _Pred, false>
Howard Hinnantbc8d3f92010-05-11 19:42:16441{
442 _Pred __pred_;
Howard Hinnantf8880d02011-12-12 17:26:24443
444 typedef pair<typename remove_const<_Key>::type, _Tp> _Pp;
445 typedef pair<const _Key, _Tp> _Cp;
Howard Hinnantbc8d3f92010-05-11 19:42:16446public:
Howard Hinnantee6ccd02010-09-23 18:58:28447 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24448 __unordered_map_equal()
449 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
450 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28451 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24452 __unordered_map_equal(const _Pred& __p)
453 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
454 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24456 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24458 bool operator()(const _Pp& __x, const _Pp& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16459 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24461 bool operator()(const _Pp& __x, const _Cp& __y) const
462 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24464 bool operator()(const _Pp& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16465 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf8880d02011-12-12 17:26:24467 bool operator()(const _Cp& __x, const _Pp& __y) const
468 {return __pred_(__x.first, __y.first);}
469 _LIBCPP_INLINE_VISIBILITY
470 bool operator()(const _Cp& __x, const _Cp& __y) const
471 {return __pred_(__x.first, __y.first);}
472 _LIBCPP_INLINE_VISIBILITY
473 bool operator()(const _Cp& __x, const _Key& __y) const
474 {return __pred_(__x.first, __y);}
475 _LIBCPP_INLINE_VISIBILITY
476 bool operator()(const _Key& __x, const _Pp& __y) const
477 {return __pred_(__x, __y.first);}
478 _LIBCPP_INLINE_VISIBILITY
479 bool operator()(const _Key& __x, const _Cp& __y) const
480 {return __pred_(__x, __y.first);}
481 _LIBCPP_INLINE_VISIBILITY
482 bool operator()(const _Key& __x, const _Key& __y) const
Howard Hinnantbc8d3f92010-05-11 19:42:16483 {return __pred_(__x, __y);}
484};
485
486template <class _Alloc>
487class __hash_map_node_destructor
488{
489 typedef _Alloc allocator_type;
490 typedef allocator_traits<allocator_type> __alloc_traits;
491 typedef typename __alloc_traits::value_type::value_type value_type;
492public:
493 typedef typename __alloc_traits::pointer pointer;
494private:
495 typedef typename value_type::first_type first_type;
496 typedef typename value_type::second_type second_type;
497
498 allocator_type& __na_;
499
500 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
501
502public:
503 bool __first_constructed;
504 bool __second_constructed;
505
Howard Hinnantee6ccd02010-09-23 18:58:28506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24507 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16508 : __na_(__na),
509 __first_constructed(false),
510 __second_constructed(false)
511 {}
512
Howard Hinnant73d21a42010-09-04 23:28:19513#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16515 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24516 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16517 : __na_(__x.__na_),
518 __first_constructed(__x.__value_constructed),
519 __second_constructed(__x.__value_constructed)
520 {
521 __x.__value_constructed = false;
522 }
Howard Hinnant73d21a42010-09-04 23:28:19523#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16525 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
526 : __na_(__x.__na_),
527 __first_constructed(__x.__value_constructed),
528 __second_constructed(__x.__value_constructed)
529 {
530 const_cast<bool&>(__x.__value_constructed) = false;
531 }
Howard Hinnant73d21a42010-09-04 23:28:19532#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16533
Howard Hinnantee6ccd02010-09-23 18:58:28534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24535 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16536 {
537 if (__second_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19538 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16539 if (__first_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19540 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16541 if (__p)
542 __alloc_traits::deallocate(__na_, __p, 1);
543 }
544};
545
546template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19547class _LIBCPP_TYPE_VIS __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16548{
549 _HashIterator __i_;
550
551 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
552 typedef const typename _HashIterator::value_type::first_type key_type;
553 typedef typename _HashIterator::value_type::second_type mapped_type;
554public:
555 typedef forward_iterator_tag iterator_category;
556 typedef pair<key_type, mapped_type> value_type;
557 typedef typename _HashIterator::difference_type difference_type;
558 typedef value_type& reference;
559 typedef typename __pointer_traits::template
560#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
561 rebind<value_type>
562#else
563 rebind<value_type>::other
564#endif
565 pointer;
566
Howard Hinnantee6ccd02010-09-23 18:58:28567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24568 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16569
Howard Hinnantee6ccd02010-09-23 18:58:28570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24571 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16572
Howard Hinnantee6ccd02010-09-23 18:58:28573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16574 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16576 pointer operator->() const {return (pointer)__i_.operator->();}
577
Howard Hinnantee6ccd02010-09-23 18:58:28578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16579 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16581 __hash_map_iterator operator++(int)
582 {
583 __hash_map_iterator __t(*this);
584 ++(*this);
585 return __t;
586 }
587
Howard Hinnantee6ccd02010-09-23 18:58:28588 friend _LIBCPP_INLINE_VISIBILITY
589 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16590 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28591 friend _LIBCPP_INLINE_VISIBILITY
592 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16593 {return __x.__i_ != __y.__i_;}
594
Howard Hinnant83eade62013-03-06 23:30:19595 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
596 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
597 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
598 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
599 template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16600};
601
602template <class _HashIterator>
Howard Hinnant83eade62013-03-06 23:30:19603class _LIBCPP_TYPE_VIS __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16604{
605 _HashIterator __i_;
606
607 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
608 typedef const typename _HashIterator::value_type::first_type key_type;
609 typedef typename _HashIterator::value_type::second_type mapped_type;
610public:
611 typedef forward_iterator_tag iterator_category;
612 typedef pair<key_type, mapped_type> value_type;
613 typedef typename _HashIterator::difference_type difference_type;
614 typedef const value_type& reference;
615 typedef typename __pointer_traits::template
616#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35617 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16618#else
Howard Hinnant099084d2011-07-23 16:14:35619 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16620#endif
621 pointer;
622
Howard Hinnantee6ccd02010-09-23 18:58:28623 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24624 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16625
Howard Hinnantee6ccd02010-09-23 18:58:28626 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24627 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28628 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16629 __hash_map_const_iterator(
630 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24631 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16632 : __i_(__i.__i_) {}
633
Howard Hinnantee6ccd02010-09-23 18:58:28634 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16635 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28636 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16637 pointer operator->() const {return (pointer)__i_.operator->();}
638
Howard Hinnantee6ccd02010-09-23 18:58:28639 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16640 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28641 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16642 __hash_map_const_iterator operator++(int)
643 {
644 __hash_map_const_iterator __t(*this);
645 ++(*this);
646 return __t;
647 }
648
Howard Hinnantee6ccd02010-09-23 18:58:28649 friend _LIBCPP_INLINE_VISIBILITY
650 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16651 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28652 friend _LIBCPP_INLINE_VISIBILITY
653 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16654 {return __x.__i_ != __y.__i_;}
655
Howard Hinnant83eade62013-03-06 23:30:19656 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map;
657 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap;
658 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator;
659 template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16660};
661
662template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
663 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:19664class _LIBCPP_TYPE_VIS unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16665{
666public:
667 // types
668 typedef _Key key_type;
669 typedef _Tp mapped_type;
670 typedef _Hash hasher;
671 typedef _Pred key_equal;
672 typedef _Alloc allocator_type;
673 typedef pair<const key_type, mapped_type> value_type;
674 typedef value_type& reference;
675 typedef const value_type& const_reference;
676
677private:
678 typedef pair<key_type, mapped_type> __value_type;
Howard Hinnantf8880d02011-12-12 17:26:24679 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
680 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:16681 typedef typename allocator_traits<allocator_type>::template
682#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
683 rebind_alloc<__value_type>
684#else
685 rebind_alloc<__value_type>::other
686#endif
687 __allocator_type;
688
689 typedef __hash_table<__value_type, __hasher,
690 __key_equal, __allocator_type> __table;
691
692 __table __table_;
693
694 typedef typename __table::__node_pointer __node_pointer;
695 typedef typename __table::__node_const_pointer __node_const_pointer;
696 typedef typename __table::__node_traits __node_traits;
697 typedef typename __table::__node_allocator __node_allocator;
698 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:50699 typedef __hash_map_node_destructor<__node_allocator> _Dp;
700 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:16701 typedef allocator_traits<allocator_type> __alloc_traits;
702public:
703 typedef typename __alloc_traits::pointer pointer;
704 typedef typename __alloc_traits::const_pointer const_pointer;
705 typedef typename __alloc_traits::size_type size_type;
706 typedef typename __alloc_traits::difference_type difference_type;
707
708 typedef __hash_map_iterator<typename __table::iterator> iterator;
709 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
710 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
711 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
712
Howard Hinnantee6ccd02010-09-23 18:58:28713 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24714 unordered_map()
715 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
716 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16717 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
718 const key_equal& __eql = key_equal());
719 unordered_map(size_type __n, const hasher& __hf,
720 const key_equal& __eql,
721 const allocator_type& __a);
722 template <class _InputIterator>
723 unordered_map(_InputIterator __first, _InputIterator __last);
724 template <class _InputIterator>
725 unordered_map(_InputIterator __first, _InputIterator __last,
726 size_type __n, const hasher& __hf = hasher(),
727 const key_equal& __eql = key_equal());
728 template <class _InputIterator>
729 unordered_map(_InputIterator __first, _InputIterator __last,
730 size_type __n, const hasher& __hf,
731 const key_equal& __eql,
732 const allocator_type& __a);
733 explicit unordered_map(const allocator_type& __a);
734 unordered_map(const unordered_map& __u);
735 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19736#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24737 unordered_map(unordered_map&& __u)
738 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16739 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19740#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02741#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16742 unordered_map(initializer_list<value_type> __il);
743 unordered_map(initializer_list<value_type> __il, size_type __n,
744 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
745 unordered_map(initializer_list<value_type> __il, size_type __n,
746 const hasher& __hf, const key_equal& __eql,
747 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02748#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16749 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36750 _LIBCPP_INLINE_VISIBILITY
751 unordered_map& operator=(const unordered_map& __u)
752 {
753 __table_ = __u.__table_;
754 return *this;
755 }
Howard Hinnant73d21a42010-09-04 23:28:19756#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24757 unordered_map& operator=(unordered_map&& __u)
758 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16759#endif
Howard Hinnante3e32912011-08-12 21:56:02760#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16761 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02762#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16763
Howard Hinnantee6ccd02010-09-23 18:58:28764 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24765 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16766 {return allocator_type(__table_.__node_alloc());}
767
Howard Hinnantee6ccd02010-09-23 18:58:28768 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24769 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24771 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28772 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24773 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16774
Howard Hinnantee6ccd02010-09-23 18:58:28775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24776 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28777 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24778 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28779 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24780 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28781 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24782 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24784 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24786 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16787
Howard Hinnant73d21a42010-09-04 23:28:19788#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:19789#ifndef _LIBCPP_HAS_NO_VARIADICS
790
Howard Hinnant635ce1d2012-05-25 22:04:21791 template <class... _Args>
792 pair<iterator, bool> emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:16793
Howard Hinnant635ce1d2012-05-25 22:04:21794 template <class... _Args>
Howard Hinnantee6ccd02010-09-23 18:58:28795 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant635ce1d2012-05-25 22:04:21796 iterator emplace_hint(const_iterator, _Args&&... __args)
797 {return emplace(_VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19798#endif // _LIBCPP_HAS_NO_VARIADICS
799#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28800 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16801 pair<iterator, bool> insert(const value_type& __x)
802 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19803#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50804 template <class _Pp,
805 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50807 pair<iterator, bool> insert(_Pp&& __x)
808 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19809#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28810 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16811 iterator insert(const_iterator, const value_type& __x)
812 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19813#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:50814 template <class _Pp,
815 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:50817 iterator insert(const_iterator, _Pp&& __x)
818 {return insert(_VSTD::forward<_Pp>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19819#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16820 template <class _InputIterator>
821 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02822#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28823 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16824 void insert(initializer_list<value_type> __il)
825 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02826#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16827
Howard Hinnantee6ccd02010-09-23 18:58:28828 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16829 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28830 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16831 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28832 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16833 iterator erase(const_iterator __first, const_iterator __last)
834 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24836 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16837
Howard Hinnantee6ccd02010-09-23 18:58:28838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24839 void swap(unordered_map& __u)
840 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
841 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16842
Howard Hinnantee6ccd02010-09-23 18:58:28843 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16844 hasher hash_function() const
845 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28846 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16847 key_equal key_eq() const
848 {return __table_.key_eq().key_eq();}
849
Howard Hinnantee6ccd02010-09-23 18:58:28850 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16851 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28852 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16853 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16855 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16857 pair<iterator, iterator> equal_range(const key_type& __k)
858 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16860 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
861 {return __table_.__equal_range_unique(__k);}
862
863 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19864#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16865 mapped_type& operator[](key_type&& __k);
866#endif
867
868 mapped_type& at(const key_type& __k);
869 const mapped_type& at(const key_type& __k) const;
870
Howard Hinnantee6ccd02010-09-23 18:58:28871 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24872 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24874 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16875
Howard Hinnantee6ccd02010-09-23 18:58:28876 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16877 size_type bucket_size(size_type __n) const
878 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16880 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
881
Howard Hinnantee6ccd02010-09-23 18:58:28882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16883 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16885 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16887 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16889 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28890 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16891 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16893 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
894
Howard Hinnantee6ccd02010-09-23 18:58:28895 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24896 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24898 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28899 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16900 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16902 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16904 void reserve(size_type __n) {__table_.reserve(__n);}
905
906private:
Howard Hinnant73d21a42010-09-04 23:28:19907#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant635ce1d2012-05-25 22:04:21908 __node_holder __construct_node();
909 template <class _A0>
910 typename enable_if
911 <
912 is_constructible<value_type, _A0>::value,
913 __node_holder
914 >::type
915 __construct_node(_A0&& __a0);
916 template <class _A0>
917 typename enable_if
918 <
919 is_constructible<key_type, _A0>::value,
920 __node_holder
921 >::type
922 __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19923#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant635ce1d2012-05-25 22:04:21924 template <class _A0, class _A1, class ..._Args>
925 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant73d21a42010-09-04 23:28:19926#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant73d21a42010-09-04 23:28:19927#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16928 __node_holder __construct_node(const key_type& __k);
929#endif
930};
931
932template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
933unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
934 size_type __n, const hasher& __hf, const key_equal& __eql)
935 : __table_(__hf, __eql)
936{
937 __table_.rehash(__n);
938}
939
940template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
941unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
942 size_type __n, const hasher& __hf, const key_equal& __eql,
943 const allocator_type& __a)
944 : __table_(__hf, __eql, __a)
945{
946 __table_.rehash(__n);
947}
948
949template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28950inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16951unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
952 const allocator_type& __a)
953 : __table_(__a)
954{
955}
956
957template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
958template <class _InputIterator>
959unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
960 _InputIterator __first, _InputIterator __last)
961{
962 insert(__first, __last);
963}
964
965template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
966template <class _InputIterator>
967unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
968 _InputIterator __first, _InputIterator __last, size_type __n,
969 const hasher& __hf, const key_equal& __eql)
970 : __table_(__hf, __eql)
971{
972 __table_.rehash(__n);
973 insert(__first, __last);
974}
975
976template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
977template <class _InputIterator>
978unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
979 _InputIterator __first, _InputIterator __last, size_type __n,
980 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
981 : __table_(__hf, __eql, __a)
982{
983 __table_.rehash(__n);
984 insert(__first, __last);
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)
990 : __table_(__u.__table_)
991{
992 __table_.rehash(__u.bucket_count());
993 insert(__u.begin(), __u.end());
994}
995
996template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
997unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
998 const unordered_map& __u, const allocator_type& __a)
999 : __table_(__u.__table_, __a)
1000{
1001 __table_.rehash(__u.bucket_count());
1002 insert(__u.begin(), __u.end());
1003}
1004
Howard Hinnant73d21a42010-09-04 23:28:191005#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161006
1007template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281008inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161009unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1010 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:241011 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:191012 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:161013{
1014}
1015
1016template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1017unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1018 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:191019 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:161020{
1021 if (__a != __u.get_allocator())
1022 {
1023 iterator __i = __u.begin();
1024 while (__u.size() != 0)
1025 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:191026 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:161027 );
1028 }
1029}
1030
Howard Hinnant73d21a42010-09-04 23:28:191031#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161032
Howard Hinnante3e32912011-08-12 21:56:021033#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1034
Howard Hinnantbc8d3f92010-05-11 19:42:161035template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1036unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1037 initializer_list<value_type> __il)
1038{
1039 insert(__il.begin(), __il.end());
1040}
1041
1042template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1043unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1044 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1045 const key_equal& __eql)
1046 : __table_(__hf, __eql)
1047{
1048 __table_.rehash(__n);
1049 insert(__il.begin(), __il.end());
1050}
1051
1052template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1053unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1054 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1055 const key_equal& __eql, const allocator_type& __a)
1056 : __table_(__hf, __eql, __a)
1057{
1058 __table_.rehash(__n);
1059 insert(__il.begin(), __il.end());
1060}
1061
Howard Hinnante3e32912011-08-12 21:56:021062#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1063
Howard Hinnant73d21a42010-09-04 23:28:191064#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161065
1066template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281067inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161068unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1069unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:241070 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:161071{
Howard Hinnant0949eed2011-06-30 21:18:191072 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:161073 return *this;
1074}
1075
Howard Hinnant73d21a42010-09-04 23:28:191076#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161077
Howard Hinnante3e32912011-08-12 21:56:021078#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1079
Howard Hinnantbc8d3f92010-05-11 19:42:161080template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281081inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161082unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1083unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1084 initializer_list<value_type> __il)
1085{
1086 __table_.__assign_unique(__il.begin(), __il.end());
1087 return *this;
1088}
1089
Howard Hinnante3e32912011-08-12 21:56:021090#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1091
Howard Hinnant73d21a42010-09-04 23:28:191092#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161093
1094template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:161095typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:211096unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:161097{
1098 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:501099 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:211100 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:161101 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:161102 __h.get_deleter().__second_constructed = true;
1103 return __h;
1104}
1105
Howard Hinnantbc8d3f92010-05-11 19:42:161106template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:211107template <class _A0>
1108typename enable_if
1109<
1110 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1111 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1112>::type
Howard Hinnantbc8d3f92010-05-11 19:42:161113unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1114{
1115 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:501116 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:191117 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1118 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:161119 __h.get_deleter().__first_constructed = true;
1120 __h.get_deleter().__second_constructed = true;
1121 return __h;
1122}
1123
Howard Hinnant635ce1d2012-05-25 22:04:211124template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1125template <class _A0>
1126typename enable_if
1127<
1128 is_constructible<_Key, _A0>::value,
1129 typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1130>::type
1131unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1132{
1133 __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_.first),
1136 _VSTD::forward<_A0>(__a0));
1137 __h.get_deleter().__first_constructed = true;
1138 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1139 __h.get_deleter().__second_constructed = true;
1140 return __h;
1141}
1142
Howard Hinnant73d21a42010-09-04 23:28:191143#ifndef _LIBCPP_HAS_NO_VARIADICS
1144
Howard Hinnantbc8d3f92010-05-11 19:42:161145template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:211146template <class _A0, class _A1, class ..._Args>
1147typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1148unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1149 _A1&& __a1,
1150 _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:161151{
Howard Hinnant635ce1d2012-05-25 22:04:211152 __node_allocator& __na = __table_.__node_alloc();
1153 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1154 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1155 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1156 _VSTD::forward<_Args>(__args)...);
1157 __h.get_deleter().__first_constructed = true;
1158 __h.get_deleter().__second_constructed = true;
1159 return __h;
1160}
1161
1162template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1163template <class... _Args>
1164pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1165unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1166{
1167 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:161168 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1169 if (__r.second)
1170 __h.release();
1171 return __r;
1172}
1173
Howard Hinnant73d21a42010-09-04 23:28:191174#endif // _LIBCPP_HAS_NO_VARIADICS
1175#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161176
1177template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1178typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1179unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1180{
1181 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:501182 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:191183 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:161184 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:191185 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:161186 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:191187 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:161188}
1189
Howard Hinnant73d21a42010-09-04 23:28:191190#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161191
1192template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1193template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:281194inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161195void
1196unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1197 _InputIterator __last)
1198{
1199 for (; __first != __last; ++__first)
1200 __table_.__insert_unique(*__first);
1201}
1202
1203template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1204_Tp&
1205unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1206{
1207 iterator __i = find(__k);
1208 if (__i != end())
1209 return __i->second;
1210 __node_holder __h = __construct_node(__k);
1211 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1212 __h.release();
1213 return __r.first->second;
1214}
1215
Howard Hinnant73d21a42010-09-04 23:28:191216#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161217
1218template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1219_Tp&
1220unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1221{
1222 iterator __i = find(__k);
1223 if (__i != end())
1224 return __i->second;
Howard Hinnant0949eed2011-06-30 21:18:191225 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:161226 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1227 __h.release();
1228 return __r.first->second;
1229}
1230
Howard Hinnant73d21a42010-09-04 23:28:191231#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161232
1233template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1234_Tp&
1235unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1236{
1237 iterator __i = find(__k);
1238#ifndef _LIBCPP_NO_EXCEPTIONS
1239 if (__i == end())
1240 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:431241#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:161242 return __i->second;
1243}
1244
1245template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1246const _Tp&
1247unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1248{
1249 const_iterator __i = find(__k);
1250#ifndef _LIBCPP_NO_EXCEPTIONS
1251 if (__i == end())
1252 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:431253#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:161254 return __i->second;
1255}
1256
1257template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281258inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161259void
1260swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1261 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:241262 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:161263{
1264 __x.swap(__y);
1265}
1266
1267template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1268bool
1269operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1270 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1271{
1272 if (__x.size() != __y.size())
1273 return false;
1274 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1275 const_iterator;
1276 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1277 __i != __ex; ++__i)
1278 {
1279 const_iterator __j = __y.find(__i->first);
1280 if (__j == __ey || !(*__i == *__j))
1281 return false;
1282 }
1283 return true;
1284}
1285
1286template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281287inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161288bool
1289operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1290 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1291{
1292 return !(__x == __y);
1293}
1294
1295template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1296 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnant83eade62013-03-06 23:30:191297class _LIBCPP_TYPE_VIS unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:161298{
1299public:
1300 // types
1301 typedef _Key key_type;
1302 typedef _Tp mapped_type;
1303 typedef _Hash hasher;
1304 typedef _Pred key_equal;
1305 typedef _Alloc allocator_type;
1306 typedef pair<const key_type, mapped_type> value_type;
1307 typedef value_type& reference;
1308 typedef const value_type& const_reference;
1309
1310private:
1311 typedef pair<key_type, mapped_type> __value_type;
Howard Hinnantf8880d02011-12-12 17:26:241312 typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher;
1313 typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal;
Howard Hinnantbc8d3f92010-05-11 19:42:161314 typedef typename allocator_traits<allocator_type>::template
1315#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1316 rebind_alloc<__value_type>
1317#else
1318 rebind_alloc<__value_type>::other
1319#endif
1320 __allocator_type;
1321
1322 typedef __hash_table<__value_type, __hasher,
1323 __key_equal, __allocator_type> __table;
1324
1325 __table __table_;
1326
1327 typedef typename __table::__node_traits __node_traits;
1328 typedef typename __table::__node_allocator __node_allocator;
1329 typedef typename __table::__node __node;
Howard Hinnant99968442011-11-29 18:15:501330 typedef __hash_map_node_destructor<__node_allocator> _Dp;
1331 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantbc8d3f92010-05-11 19:42:161332 typedef allocator_traits<allocator_type> __alloc_traits;
1333public:
1334 typedef typename __alloc_traits::pointer pointer;
1335 typedef typename __alloc_traits::const_pointer const_pointer;
1336 typedef typename __alloc_traits::size_type size_type;
1337 typedef typename __alloc_traits::difference_type difference_type;
1338
1339 typedef __hash_map_iterator<typename __table::iterator> iterator;
1340 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1341 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1342 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1343
Howard Hinnantee6ccd02010-09-23 18:58:281344 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241345 unordered_multimap()
1346 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1347 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:161348 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1349 const key_equal& __eql = key_equal());
1350 unordered_multimap(size_type __n, const hasher& __hf,
1351 const key_equal& __eql,
1352 const allocator_type& __a);
1353 template <class _InputIterator>
1354 unordered_multimap(_InputIterator __first, _InputIterator __last);
1355 template <class _InputIterator>
1356 unordered_multimap(_InputIterator __first, _InputIterator __last,
1357 size_type __n, const hasher& __hf = hasher(),
1358 const key_equal& __eql = key_equal());
1359 template <class _InputIterator>
1360 unordered_multimap(_InputIterator __first, _InputIterator __last,
1361 size_type __n, const hasher& __hf,
1362 const key_equal& __eql,
1363 const allocator_type& __a);
1364 explicit unordered_multimap(const allocator_type& __a);
1365 unordered_multimap(const unordered_multimap& __u);
1366 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:191367#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:241368 unordered_multimap(unordered_multimap&& __u)
1369 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:161370 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:191371#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:021372#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:161373 unordered_multimap(initializer_list<value_type> __il);
1374 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1375 const hasher& __hf = hasher(),
1376 const key_equal& __eql = key_equal());
1377 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1378 const hasher& __hf, const key_equal& __eql,
1379 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:021380#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:161381 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:361382 _LIBCPP_INLINE_VISIBILITY
1383 unordered_multimap& operator=(const unordered_multimap& __u)
1384 {
1385 __table_ = __u.__table_;
1386 return *this;
1387 }
Howard Hinnant73d21a42010-09-04 23:28:191388#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:241389 unordered_multimap& operator=(unordered_multimap&& __u)
1390 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:161391#endif
Howard Hinnante3e32912011-08-12 21:56:021392#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:161393 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:021394#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:161395
Howard Hinnantee6ccd02010-09-23 18:58:281396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241397 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:161398 {return allocator_type(__table_.__node_alloc());}
1399
Howard Hinnantee6ccd02010-09-23 18:58:281400 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241401 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:281402 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241403 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:281404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241405 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:161406
Howard Hinnantee6ccd02010-09-23 18:58:281407 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241408 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:281409 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241410 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:281411 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241412 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:281413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241414 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:281415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241416 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:281417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241418 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:161419
Howard Hinnant73d21a42010-09-04 23:28:191420#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant73d21a42010-09-04 23:28:191421#ifndef _LIBCPP_HAS_NO_VARIADICS
1422
Howard Hinnant635ce1d2012-05-25 22:04:211423 template <class... _Args>
1424 iterator emplace(_Args&&... __args);
Howard Hinnantbc8d3f92010-05-11 19:42:161425
Howard Hinnant635ce1d2012-05-25 22:04:211426 template <class... _Args>
1427 iterator emplace_hint(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:191428#endif // _LIBCPP_HAS_NO_VARIADICS
1429#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:281430 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161431 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:191432#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:501433 template <class _Pp,
1434 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:281435 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:501436 iterator insert(_Pp&& __x)
1437 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:191438#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:281439 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161440 iterator insert(const_iterator __p, const value_type& __x)
1441 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:191442#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant99968442011-11-29 18:15:501443 template <class _Pp,
1444 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:281445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant99968442011-11-29 18:15:501446 iterator insert(const_iterator __p, _Pp&& __x)
1447 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:191448#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161449 template <class _InputIterator>
1450 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:021451#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:281452 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161453 void insert(initializer_list<value_type> __il)
1454 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:021455#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:161456
Howard Hinnantee6ccd02010-09-23 18:58:281457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161458 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:281459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161460 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:281461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161462 iterator erase(const_iterator __first, const_iterator __last)
1463 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:281464 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241465 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:161466
Howard Hinnantee6ccd02010-09-23 18:58:281467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241468 void swap(unordered_multimap& __u)
1469 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1470 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:161471
Howard Hinnantee6ccd02010-09-23 18:58:281472 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161473 hasher hash_function() const
1474 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:281475 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161476 key_equal key_eq() const
1477 {return __table_.key_eq().key_eq();}
1478
Howard Hinnantee6ccd02010-09-23 18:58:281479 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161480 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:281481 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161482 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:281483 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161484 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:281485 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161486 pair<iterator, iterator> equal_range(const key_type& __k)
1487 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:281488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161489 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1490 {return __table_.__equal_range_multi(__k);}
1491
Howard Hinnantee6ccd02010-09-23 18:58:281492 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241493 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:281494 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241495 size_type max_bucket_count() const _NOEXCEPT
1496 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:161497
Howard Hinnantee6ccd02010-09-23 18:58:281498 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161499 size_type bucket_size(size_type __n) const
1500 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281501 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161502 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1503
Howard Hinnantee6ccd02010-09-23 18:58:281504 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161505 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161507 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281508 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161509 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281510 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161511 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281512 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161513 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161515 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1516
Howard Hinnantee6ccd02010-09-23 18:58:281517 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241518 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:281519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:241520 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:281521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161522 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:281523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161524 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:281525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161526 void reserve(size_type __n) {__table_.reserve(__n);}
1527
1528private:
Howard Hinnant635ce1d2012-05-25 22:04:211529#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1530 __node_holder __construct_node();
1531 template <class _A0>
1532 typename enable_if
1533 <
1534 is_constructible<value_type, _A0>::value,
1535 __node_holder
1536 >::type
1537 __construct_node(_A0&& __a0);
1538 template <class _A0>
1539 typename enable_if
1540 <
1541 is_constructible<key_type, _A0>::value,
1542 __node_holder
1543 >::type
1544 __construct_node(_A0&& __a0);
1545#ifndef _LIBCPP_HAS_NO_VARIADICS
1546 template <class _A0, class _A1, class ..._Args>
1547 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1548#endif // _LIBCPP_HAS_NO_VARIADICS
1549#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161550};
1551
1552template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1553unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1554 size_type __n, const hasher& __hf, const key_equal& __eql)
1555 : __table_(__hf, __eql)
1556{
1557 __table_.rehash(__n);
1558}
1559
1560template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1561unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1562 size_type __n, const hasher& __hf, const key_equal& __eql,
1563 const allocator_type& __a)
1564 : __table_(__hf, __eql, __a)
1565{
1566 __table_.rehash(__n);
1567}
1568
1569template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1570template <class _InputIterator>
1571unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1572 _InputIterator __first, _InputIterator __last)
1573{
1574 insert(__first, __last);
1575}
1576
1577template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1578template <class _InputIterator>
1579unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1580 _InputIterator __first, _InputIterator __last, size_type __n,
1581 const hasher& __hf, const key_equal& __eql)
1582 : __table_(__hf, __eql)
1583{
1584 __table_.rehash(__n);
1585 insert(__first, __last);
1586}
1587
1588template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1589template <class _InputIterator>
1590unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1591 _InputIterator __first, _InputIterator __last, size_type __n,
1592 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1593 : __table_(__hf, __eql, __a)
1594{
1595 __table_.rehash(__n);
1596 insert(__first, __last);
1597}
1598
Howard Hinnantbc8d3f92010-05-11 19:42:161599template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281600inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161601unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1602 const allocator_type& __a)
1603 : __table_(__a)
1604{
1605}
1606
1607template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1608unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1609 const unordered_multimap& __u)
1610 : __table_(__u.__table_)
1611{
1612 __table_.rehash(__u.bucket_count());
1613 insert(__u.begin(), __u.end());
1614}
1615
1616template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1617unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1618 const unordered_multimap& __u, const allocator_type& __a)
1619 : __table_(__u.__table_, __a)
1620{
1621 __table_.rehash(__u.bucket_count());
1622 insert(__u.begin(), __u.end());
1623}
1624
Howard Hinnant73d21a42010-09-04 23:28:191625#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161626
1627template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281628inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161629unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1630 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:241631 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:191632 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:161633{
1634}
1635
1636template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1637unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1638 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:191639 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:161640{
1641 if (__a != __u.get_allocator())
1642 {
1643 iterator __i = __u.begin();
1644 while (__u.size() != 0)
1645{
1646 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:191647 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:161648 );
1649}
1650 }
1651}
1652
Howard Hinnant73d21a42010-09-04 23:28:191653#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161654
Howard Hinnante3e32912011-08-12 21:56:021655#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1656
Howard Hinnantbc8d3f92010-05-11 19:42:161657template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1658unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1659 initializer_list<value_type> __il)
1660{
1661 insert(__il.begin(), __il.end());
1662}
1663
1664template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1665unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1666 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1667 const key_equal& __eql)
1668 : __table_(__hf, __eql)
1669{
1670 __table_.rehash(__n);
1671 insert(__il.begin(), __il.end());
1672}
1673
1674template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1675unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1676 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1677 const key_equal& __eql, const allocator_type& __a)
1678 : __table_(__hf, __eql, __a)
1679{
1680 __table_.rehash(__n);
1681 insert(__il.begin(), __il.end());
1682}
1683
Howard Hinnante3e32912011-08-12 21:56:021684#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1685
Howard Hinnant73d21a42010-09-04 23:28:191686#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161687
1688template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281689inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161690unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1691unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:241692 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:161693{
Howard Hinnant0949eed2011-06-30 21:18:191694 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:161695 return *this;
1696}
1697
Howard Hinnant73d21a42010-09-04 23:28:191698#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161699
Howard Hinnante3e32912011-08-12 21:56:021700#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1701
Howard Hinnantbc8d3f92010-05-11 19:42:161702template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281703inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161704unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1705unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1706 initializer_list<value_type> __il)
1707{
1708 __table_.__assign_multi(__il.begin(), __il.end());
1709 return *this;
1710}
1711
Howard Hinnante3e32912011-08-12 21:56:021712#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1713
Howard Hinnant73d21a42010-09-04 23:28:191714#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161715
1716template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantbc8d3f92010-05-11 19:42:161717typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
Howard Hinnant635ce1d2012-05-25 22:04:211718unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node()
Howard Hinnantbc8d3f92010-05-11 19:42:161719{
1720 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:501721 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant635ce1d2012-05-25 22:04:211722 __node_traits::construct(__na, _VSTD::addressof(__h->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:161723 __h.get_deleter().__first_constructed = true;
Howard Hinnantbc8d3f92010-05-11 19:42:161724 __h.get_deleter().__second_constructed = true;
1725 return __h;
1726}
1727
Howard Hinnantbc8d3f92010-05-11 19:42:161728template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:211729template <class _A0>
1730typename enable_if
1731<
1732 is_constructible<pair<const _Key, _Tp>, _A0>::value,
1733 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1734>::type
Howard Hinnantbc8d3f92010-05-11 19:42:161735unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1736{
1737 __node_allocator& __na = __table_.__node_alloc();
Howard Hinnant99968442011-11-29 18:15:501738 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant0949eed2011-06-30 21:18:191739 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1740 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:161741 __h.get_deleter().__first_constructed = true;
1742 __h.get_deleter().__second_constructed = true;
1743 return __h;
1744}
1745
Howard Hinnant635ce1d2012-05-25 22:04:211746template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1747template <class _A0>
1748typename enable_if
1749<
1750 is_constructible<_Key, _A0>::value,
1751 typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1752>::type
1753unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1754{
1755 __node_allocator& __na = __table_.__node_alloc();
1756 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1757 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1758 _VSTD::forward<_A0>(__a0));
1759 __h.get_deleter().__first_constructed = true;
1760 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
1761 __h.get_deleter().__second_constructed = true;
1762 return __h;
1763}
1764
Howard Hinnant73d21a42010-09-04 23:28:191765#ifndef _LIBCPP_HAS_NO_VARIADICS
1766
Howard Hinnantbc8d3f92010-05-11 19:42:161767template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:211768template <class _A0, class _A1, class ..._Args>
1769typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1770unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1771 _A0&& __a0, _A1&& __a1, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:161772{
Howard Hinnant635ce1d2012-05-25 22:04:211773 __node_allocator& __na = __table_.__node_alloc();
1774 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1775 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1776 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1777 _VSTD::forward<_Args>(__args)...);
1778 __h.get_deleter().__first_constructed = true;
1779 __h.get_deleter().__second_constructed = true;
1780 return __h;
1781}
1782
1783template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1784template <class... _Args>
1785typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1786unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args)
1787{
1788 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:161789 iterator __r = __table_.__node_insert_multi(__h.get());
1790 __h.release();
1791 return __r;
1792}
1793
1794template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnant635ce1d2012-05-25 22:04:211795template <class... _Args>
Howard Hinnantbc8d3f92010-05-11 19:42:161796typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1797unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
Howard Hinnant635ce1d2012-05-25 22:04:211798 const_iterator __p, _Args&&... __args)
Howard Hinnantbc8d3f92010-05-11 19:42:161799{
Howard Hinnant635ce1d2012-05-25 22:04:211800 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:161801 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1802 __h.release();
1803 return __r;
1804}
1805
Howard Hinnant73d21a42010-09-04 23:28:191806#endif // _LIBCPP_HAS_NO_VARIADICS
1807#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:161808
1809template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1810template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:281811inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161812void
1813unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1814 _InputIterator __last)
1815{
1816 for (; __first != __last; ++__first)
1817 __table_.__insert_multi(*__first);
1818}
1819
1820template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281821inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161822void
1823swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1824 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:241825 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:161826{
1827 __x.swap(__y);
1828}
1829
1830template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1831bool
1832operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1833 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1834{
1835 if (__x.size() != __y.size())
1836 return false;
1837 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1838 const_iterator;
1839 typedef pair<const_iterator, const_iterator> _EqRng;
1840 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1841 {
1842 _EqRng __xeq = __x.equal_range(__i->first);
1843 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:191844 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1845 _VSTD::distance(__yeq.first, __yeq.second) ||
1846 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:161847 return false;
1848 __i = __xeq.second;
1849 }
1850 return true;
1851}
1852
1853template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:281854inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:161855bool
1856operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1857 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1858{
1859 return !(__x == __y);
1860}
1861
1862_LIBCPP_END_NAMESPACE_STD
1863
1864#endif // _LIBCPP_UNORDERED_MAP