blob: 2a22a56d61c2c7f433c8c59c710642e000e27239 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UNORDERED_MAP
12#define _LIBCPP_UNORDERED_MAP
13
14/*
15
16 unordered_map synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
24 class Alloc = allocator<pair<const Key, T>>>
25class unordered_map
26{
27public:
28 // types
29 typedef Key key_type;
30 typedef T mapped_type;
31 typedef Hash hasher;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef pair<const key_type, mapped_type> value_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000047 unordered_map()
48 noexcept(
49 is_nothrow_default_constructible<hasher>::value &&
50 is_nothrow_default_constructible<key_equal>::value &&
51 is_nothrow_default_constructible<allocator_type>::value);
52 explicit unordered_map(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000053 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 template <class InputIterator>
56 unordered_map(InputIterator f, InputIterator l,
57 size_type n = 0, const hasher& hf = hasher(),
58 const key_equal& eql = key_equal(),
59 const allocator_type& a = allocator_type());
60 explicit unordered_map(const allocator_type&);
61 unordered_map(const unordered_map&);
62 unordered_map(const unordered_map&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000063 unordered_map(unordered_map&&)
64 noexcept(
65 is_nothrow_move_constructible<hasher>::value &&
66 is_nothrow_move_constructible<key_equal>::value &&
67 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000068 unordered_map(unordered_map&&, const Allocator&);
69 unordered_map(initializer_list<value_type>, size_type n = 0,
70 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
71 const allocator_type& a = allocator_type());
72 ~unordered_map();
73 unordered_map& operator=(const unordered_map&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000074 unordered_map& operator=(unordered_map&&)
75 noexcept(
76 allocator_type::propagate_on_container_move_assignment::value &&
77 is_nothrow_move_assignable<allocator_type>::value &&
78 is_nothrow_move_assignable<hasher>::value &&
79 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000080 unordered_map& operator=(initializer_list<value_type>);
81
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000082 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000083
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000084 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000087
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000088 iterator begin() noexcept;
89 iterator end() noexcept;
90 const_iterator begin() const noexcept;
91 const_iterator end() const noexcept;
92 const_iterator cbegin() const noexcept;
93 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000094
95 template <class... Args>
96 pair<iterator, bool> emplace(Args&&... args);
97 template <class... Args>
98 iterator emplace_hint(const_iterator position, Args&&... args);
99 pair<iterator, bool> insert(const value_type& obj);
100 template <class P>
101 pair<iterator, bool> insert(P&& obj);
102 iterator insert(const_iterator hint, const value_type& obj);
103 template <class P>
104 iterator insert(const_iterator hint, P&& obj);
105 template <class InputIterator>
106 void insert(InputIterator first, InputIterator last);
107 void insert(initializer_list<value_type>);
108
109 iterator erase(const_iterator position);
110 size_type erase(const key_type& k);
111 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000112 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000113
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000114 void swap(unordered_map&)
115 noexcept(
116 (!allocator_type::propagate_on_container_swap::value ||
117 __is_nothrow_swappable<allocator_type>::value) &&
118 __is_nothrow_swappable<hasher>::value &&
119 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
121 hasher hash_function() const;
122 key_equal key_eq() const;
123
124 iterator find(const key_type& k);
125 const_iterator find(const key_type& k) const;
126 size_type count(const key_type& k) const;
127 pair<iterator, iterator> equal_range(const key_type& k);
128 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
129
130 mapped_type& operator[](const key_type& k);
131 mapped_type& operator[](key_type&& k);
132
133 mapped_type& at(const key_type& k);
134 const mapped_type& at(const key_type& k) const;
135
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
141
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
148
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
154};
155
156template <class Key, class T, class Hash, class Pred, class Alloc>
157 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000160
161template <class Key, class T, class Hash, class Pred, class Alloc>
162 bool
163 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
164 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
165
166template <class Key, class T, class Hash, class Pred, class Alloc>
167 bool
168 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
169 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
170
171template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
172 class Alloc = allocator<pair<const Key, T>>>
173class unordered_multimap
174{
175public:
176 // types
177 typedef Key key_type;
178 typedef T mapped_type;
179 typedef Hash hasher;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef pair<const key_type, mapped_type> value_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
194
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000195 unordered_multimap()
196 noexcept(
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multimap(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multimap(const allocator_type&);
209 unordered_multimap(const unordered_multimap&);
210 unordered_multimap(const unordered_multimap&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000211 unordered_multimap(unordered_multimap&&)
212 noexcept(
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216 unordered_multimap(unordered_multimap&&, const Allocator&);
217 unordered_multimap(initializer_list<value_type>, size_type n = 0,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
220 ~unordered_multimap();
221 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000222 unordered_multimap& operator=(unordered_multimap&&)
223 noexcept(
224 allocator_type::propagate_on_container_move_assignment::value &&
225 is_nothrow_move_assignable<allocator_type>::value &&
226 is_nothrow_move_assignable<hasher>::value &&
227 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000228 unordered_multimap& operator=(initializer_list<value_type>);
229
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000230 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000231
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000236 iterator begin() noexcept;
237 iterator end() noexcept;
238 const_iterator begin() const noexcept;
239 const_iterator end() const noexcept;
240 const_iterator cbegin() const noexcept;
241 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000242
243 template <class... Args>
244 iterator emplace(Args&&... args);
245 template <class... Args>
246 iterator emplace_hint(const_iterator position, Args&&... args);
247 iterator insert(const value_type& obj);
248 template <class P>
249 iterator insert(P&& obj);
250 iterator insert(const_iterator hint, const value_type& obj);
251 template <class P>
252 iterator insert(const_iterator hint, P&& obj);
253 template <class InputIterator>
254 void insert(InputIterator first, InputIterator last);
255 void insert(initializer_list<value_type>);
256
257 iterator erase(const_iterator position);
258 size_type erase(const key_type& k);
259 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000260 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000261
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000262 void swap(unordered_multimap&)
263 noexcept(
264 (!allocator_type::propagate_on_container_swap::value ||
265 __is_nothrow_swappable<allocator_type>::value) &&
266 __is_nothrow_swappable<hasher>::value &&
267 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000268
269 hasher hash_function() const;
270 key_equal key_eq() const;
271
272 iterator find(const key_type& k);
273 const_iterator find(const key_type& k) const;
274 size_type count(const key_type& k) const;
275 pair<iterator, iterator> equal_range(const key_type& k);
276 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
277
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000280
281 size_type bucket_size(size_type n) const;
282 size_type bucket(const key_type& k) const;
283
284 local_iterator begin(size_type n);
285 local_iterator end(size_type n);
286 const_local_iterator begin(size_type n) const;
287 const_local_iterator end(size_type n) const;
288 const_local_iterator cbegin(size_type n) const;
289 const_local_iterator cend(size_type n) const;
290
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000293 void max_load_factor(float z);
294 void rehash(size_type n);
295 void reserve(size_type n);
296};
297
298template <class Key, class T, class Hash, class Pred, class Alloc>
299 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302
303template <class Key, class T, class Hash, class Pred, class Alloc>
304 bool
305 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
306 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
307
308template <class Key, class T, class Hash, class Pred, class Alloc>
309 bool
310 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
311 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
312
313} // std
314
315*/
316
317#include <__config>
318#include <__hash_table>
319#include <functional>
320#include <stdexcept>
321
322#pragma GCC system_header
323
324_LIBCPP_BEGIN_NAMESPACE_STD
325
326template <class _Tp, class _Hash, bool = is_empty<_Hash>::value>
327class __unordered_map_hasher
328 : private _Hash
329{
330public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000331 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000332 __unordered_map_hasher()
333 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
334 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000336 __unordered_map_hasher(const _Hash& __h)
337 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
338 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000340 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000342 size_t operator()(const _Tp& __x) const
343 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000344 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000345 size_t operator()(const typename _Tp::first_type& __x) const
346 {return static_cast<const _Hash&>(*this)(__x);}
347};
348
349template <class _Tp, class _Hash>
350class __unordered_map_hasher<_Tp, _Hash, false>
351{
352 _Hash __hash_;
353public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000355 __unordered_map_hasher()
356 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
357 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000358 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000359 __unordered_map_hasher(const _Hash& __h)
360 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
361 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000362 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000363 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000365 size_t operator()(const _Tp& __x) const
366 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000367 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000368 size_t operator()(const typename _Tp::first_type& __x) const
369 {return __hash_(__x);}
370};
371
372template <class _Tp, class _Pred, bool = is_empty<_Pred>::value>
373class __unordered_map_equal
374 : private _Pred
375{
376public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000377 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000378 __unordered_map_equal()
379 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
380 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000381 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000382 __unordered_map_equal(const _Pred& __p)
383 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
384 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000385 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000386 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000387 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000388 bool operator()(const _Tp& __x, const _Tp& __y) const
389 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000390 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000391 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
392 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000393 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000394 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
395 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant324bb032010-08-22 00:02:43 +0000397 bool operator()(const typename _Tp::first_type& __x,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000398 const typename _Tp::first_type& __y) const
399 {return static_cast<const _Pred&>(*this)(__x, __y);}
400};
401
402template <class _Tp, class _Pred>
403class __unordered_map_equal<_Tp, _Pred, false>
404{
405 _Pred __pred_;
406public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000407 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000408 __unordered_map_equal()
409 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
410 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000411 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000412 __unordered_map_equal(const _Pred& __p)
413 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
414 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000416 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000418 bool operator()(const _Tp& __x, const _Tp& __y) const
419 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000420 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000421 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
422 {return __pred_(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000424 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
425 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000427 bool operator()(const typename _Tp::first_type& __x,
428 const typename _Tp::first_type& __y) const
429 {return __pred_(__x, __y);}
430};
431
432template <class _Alloc>
433class __hash_map_node_destructor
434{
435 typedef _Alloc allocator_type;
436 typedef allocator_traits<allocator_type> __alloc_traits;
437 typedef typename __alloc_traits::value_type::value_type value_type;
438public:
439 typedef typename __alloc_traits::pointer pointer;
440private:
441 typedef typename value_type::first_type first_type;
442 typedef typename value_type::second_type second_type;
443
444 allocator_type& __na_;
445
446 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
447
448public:
449 bool __first_constructed;
450 bool __second_constructed;
451
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000452 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000453 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000454 : __na_(__na),
455 __first_constructed(false),
456 __second_constructed(false)
457 {}
458
Howard Hinnant73d21a42010-09-04 23:28:19 +0000459#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000461 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000462 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000463 : __na_(__x.__na_),
464 __first_constructed(__x.__value_constructed),
465 __second_constructed(__x.__value_constructed)
466 {
467 __x.__value_constructed = false;
468 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000469#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000470 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000471 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
472 : __na_(__x.__na_),
473 __first_constructed(__x.__value_constructed),
474 __second_constructed(__x.__value_constructed)
475 {
476 const_cast<bool&>(__x.__value_constructed) = false;
477 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000478#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000479
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000480 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000481 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000482 {
483 if (__second_constructed)
Howard Hinnant2529d022011-02-02 17:36:20 +0000484 __alloc_traits::destroy(__na_, _STD::addressof(__p->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000485 if (__first_constructed)
Howard Hinnant2529d022011-02-02 17:36:20 +0000486 __alloc_traits::destroy(__na_, _STD::addressof(__p->__value_.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000487 if (__p)
488 __alloc_traits::deallocate(__na_, __p, 1);
489 }
490};
491
492template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000493class _LIBCPP_VISIBLE __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000494{
495 _HashIterator __i_;
496
497 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
498 typedef const typename _HashIterator::value_type::first_type key_type;
499 typedef typename _HashIterator::value_type::second_type mapped_type;
500public:
501 typedef forward_iterator_tag iterator_category;
502 typedef pair<key_type, mapped_type> value_type;
503 typedef typename _HashIterator::difference_type difference_type;
504 typedef value_type& reference;
505 typedef typename __pointer_traits::template
506#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
507 rebind<value_type>
508#else
509 rebind<value_type>::other
510#endif
511 pointer;
512
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000513 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000514 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000515
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000516 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000517 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000518
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000520 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000522 pointer operator->() const {return (pointer)__i_.operator->();}
523
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000526 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527 __hash_map_iterator operator++(int)
528 {
529 __hash_map_iterator __t(*this);
530 ++(*this);
531 return __t;
532 }
533
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000534 friend _LIBCPP_INLINE_VISIBILITY
535 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000536 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000537 friend _LIBCPP_INLINE_VISIBILITY
538 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000539 {return __x.__i_ != __y.__i_;}
540
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000541 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
542 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
543 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
544 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
545 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000546};
547
548template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000549class _LIBCPP_VISIBLE __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000550{
551 _HashIterator __i_;
552
553 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
554 typedef const typename _HashIterator::value_type::first_type key_type;
555 typedef typename _HashIterator::value_type::second_type mapped_type;
556public:
557 typedef forward_iterator_tag iterator_category;
558 typedef pair<key_type, mapped_type> value_type;
559 typedef typename _HashIterator::difference_type difference_type;
560 typedef const value_type& reference;
561 typedef typename __pointer_traits::template
562#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
563 rebind<value_type>
564#else
565 rebind<value_type>::other
566#endif
567 pointer;
568
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000569 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000570 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000571
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000573 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000575 __hash_map_const_iterator(
576 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000577 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000578 : __i_(__i.__i_) {}
579
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000581 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 pointer operator->() const {return (pointer)__i_.operator->();}
584
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000585 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000586 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000588 __hash_map_const_iterator operator++(int)
589 {
590 __hash_map_const_iterator __t(*this);
591 ++(*this);
592 return __t;
593 }
594
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000595 friend _LIBCPP_INLINE_VISIBILITY
596 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000597 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000598 friend _LIBCPP_INLINE_VISIBILITY
599 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000600 {return __x.__i_ != __y.__i_;}
601
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000602 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
603 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
604 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
605 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000606};
607
608template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
609 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000610class _LIBCPP_VISIBLE unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000611{
612public:
613 // types
614 typedef _Key key_type;
615 typedef _Tp mapped_type;
616 typedef _Hash hasher;
617 typedef _Pred key_equal;
618 typedef _Alloc allocator_type;
619 typedef pair<const key_type, mapped_type> value_type;
620 typedef value_type& reference;
621 typedef const value_type& const_reference;
622
623private:
624 typedef pair<key_type, mapped_type> __value_type;
625 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
626 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
627 typedef typename allocator_traits<allocator_type>::template
628#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
629 rebind_alloc<__value_type>
630#else
631 rebind_alloc<__value_type>::other
632#endif
633 __allocator_type;
634
635 typedef __hash_table<__value_type, __hasher,
636 __key_equal, __allocator_type> __table;
637
638 __table __table_;
639
640 typedef typename __table::__node_pointer __node_pointer;
641 typedef typename __table::__node_const_pointer __node_const_pointer;
642 typedef typename __table::__node_traits __node_traits;
643 typedef typename __table::__node_allocator __node_allocator;
644 typedef typename __table::__node __node;
645 typedef __hash_map_node_destructor<__node_allocator> _D;
646 typedef unique_ptr<__node, _D> __node_holder;
647 typedef allocator_traits<allocator_type> __alloc_traits;
648public:
649 typedef typename __alloc_traits::pointer pointer;
650 typedef typename __alloc_traits::const_pointer const_pointer;
651 typedef typename __alloc_traits::size_type size_type;
652 typedef typename __alloc_traits::difference_type difference_type;
653
654 typedef __hash_map_iterator<typename __table::iterator> iterator;
655 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
656 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
657 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
658
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000659 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000660 unordered_map()
661 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
662 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000663 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
664 const key_equal& __eql = key_equal());
665 unordered_map(size_type __n, const hasher& __hf,
666 const key_equal& __eql,
667 const allocator_type& __a);
668 template <class _InputIterator>
669 unordered_map(_InputIterator __first, _InputIterator __last);
670 template <class _InputIterator>
671 unordered_map(_InputIterator __first, _InputIterator __last,
672 size_type __n, const hasher& __hf = hasher(),
673 const key_equal& __eql = key_equal());
674 template <class _InputIterator>
675 unordered_map(_InputIterator __first, _InputIterator __last,
676 size_type __n, const hasher& __hf,
677 const key_equal& __eql,
678 const allocator_type& __a);
679 explicit unordered_map(const allocator_type& __a);
680 unordered_map(const unordered_map& __u);
681 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000682#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000683 unordered_map(unordered_map&& __u)
684 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000685 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000686#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000687 unordered_map(initializer_list<value_type> __il);
688 unordered_map(initializer_list<value_type> __il, size_type __n,
689 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
690 unordered_map(initializer_list<value_type> __il, size_type __n,
691 const hasher& __hf, const key_equal& __eql,
692 const allocator_type& __a);
693 // ~unordered_map() = default;
694 // unordered_map& operator=(const unordered_map& __u) = default;
Howard Hinnant73d21a42010-09-04 23:28:19 +0000695#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000696 unordered_map& operator=(unordered_map&& __u)
697 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000698#endif
699 unordered_map& operator=(initializer_list<value_type> __il);
700
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000701 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000702 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000703 {return allocator_type(__table_.__node_alloc());}
704
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000706 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000707 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000708 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000709 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000710 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000711
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000712 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000713 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000714 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000715 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000716 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000717 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000719 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000721 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000722 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000723 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000724
Howard Hinnant73d21a42010-09-04 23:28:19 +0000725#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000726 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000727 pair<iterator, bool> emplace()
728 {return __table_.__emplace_unique();}
729
730 template <class _A0,
731 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000732 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000733 pair<iterator, bool> emplace(_A0&& __a0)
734 {return __table_.__emplace_unique(_STD::forward<_A0>(__a0));}
735
Howard Hinnant73d21a42010-09-04 23:28:19 +0000736#ifndef _LIBCPP_HAS_NO_VARIADICS
737
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000738 template <class _A0, class... _Args,
739 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
740 pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args);
741
Howard Hinnant73d21a42010-09-04 23:28:19 +0000742#endif // _LIBCPP_HAS_NO_VARIADICS
743
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000744 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000745 iterator emplace_hint(const_iterator)
746 {return __table_.__emplace_unique().first;}
747
748 template <class _A0,
749 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000750 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000751 iterator emplace_hint(const_iterator, _A0&& __a0)
752 {return __table_.__emplace_unique(_STD::forward<_A0>(__a0)).first;}
753
Howard Hinnant73d21a42010-09-04 23:28:19 +0000754#ifndef _LIBCPP_HAS_NO_VARIADICS
755
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000756 template <class _A0, class... _Args,
757 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000758 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000759 iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args)
760 {return emplace(_STD::forward<_A0>(__a0),
761 _STD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000762#endif // _LIBCPP_HAS_NO_VARIADICS
763#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000764 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000765 pair<iterator, bool> insert(const value_type& __x)
766 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000767#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000768 template <class _P,
769 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000771 pair<iterator, bool> insert(_P&& __x)
772 {return __table_.__insert_unique(_STD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000773#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000774 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000775 iterator insert(const_iterator, const value_type& __x)
776 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000777#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000778 template <class _P,
779 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000781 iterator insert(const_iterator, _P&& __x)
782 {return insert(_STD::forward<_P>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000783#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000784 template <class _InputIterator>
785 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000786 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000787 void insert(initializer_list<value_type> __il)
788 {insert(__il.begin(), __il.end());}
789
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000790 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000791 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000792 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000793 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000794 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000795 iterator erase(const_iterator __first, const_iterator __last)
796 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000797 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000798 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000799
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000800 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000801 void swap(unordered_map& __u)
802 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
803 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000804
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000806 hasher hash_function() const
807 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000808 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000809 key_equal key_eq() const
810 {return __table_.key_eq().key_eq();}
811
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000812 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000813 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000814 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000815 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000817 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000819 pair<iterator, iterator> equal_range(const key_type& __k)
820 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000822 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
823 {return __table_.__equal_range_unique(__k);}
824
825 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000826#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000827 mapped_type& operator[](key_type&& __k);
828#endif
829
830 mapped_type& at(const key_type& __k);
831 const mapped_type& at(const key_type& __k) const;
832
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000833 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000834 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000836 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000837
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000839 size_type bucket_size(size_type __n) const
840 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000841 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000842 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
843
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000844 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000845 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000846 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000847 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000849 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000850 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000851 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000852 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000853 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000855 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
856
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000857 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000858 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000860 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000864 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000865 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000866 void reserve(size_type __n) {__table_.reserve(__n);}
867
868private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000869#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
870#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000871 template <class _A0, class... _Args,
872 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
873 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000874#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000875 template <class _A0,
876 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
877 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000878#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000879 __node_holder __construct_node(const key_type& __k);
880#endif
881};
882
883template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
884unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
885 size_type __n, const hasher& __hf, const key_equal& __eql)
886 : __table_(__hf, __eql)
887{
888 __table_.rehash(__n);
889}
890
891template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
892unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
893 size_type __n, const hasher& __hf, const key_equal& __eql,
894 const allocator_type& __a)
895 : __table_(__hf, __eql, __a)
896{
897 __table_.rehash(__n);
898}
899
900template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000901inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000902unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
903 const allocator_type& __a)
904 : __table_(__a)
905{
906}
907
908template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
909template <class _InputIterator>
910unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
911 _InputIterator __first, _InputIterator __last)
912{
913 insert(__first, __last);
914}
915
916template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
917template <class _InputIterator>
918unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
919 _InputIterator __first, _InputIterator __last, size_type __n,
920 const hasher& __hf, const key_equal& __eql)
921 : __table_(__hf, __eql)
922{
923 __table_.rehash(__n);
924 insert(__first, __last);
925}
926
927template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
928template <class _InputIterator>
929unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
930 _InputIterator __first, _InputIterator __last, size_type __n,
931 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
932 : __table_(__hf, __eql, __a)
933{
934 __table_.rehash(__n);
935 insert(__first, __last);
936}
937
938template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
939unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
940 const unordered_map& __u)
941 : __table_(__u.__table_)
942{
943 __table_.rehash(__u.bucket_count());
944 insert(__u.begin(), __u.end());
945}
946
947template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
948unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
949 const unordered_map& __u, const allocator_type& __a)
950 : __table_(__u.__table_, __a)
951{
952 __table_.rehash(__u.bucket_count());
953 insert(__u.begin(), __u.end());
954}
955
Howard Hinnant73d21a42010-09-04 23:28:19 +0000956#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000957
958template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000959inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000960unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
961 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000962 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000963 : __table_(_STD::move(__u.__table_))
964{
965}
966
967template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
968unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
969 unordered_map&& __u, const allocator_type& __a)
970 : __table_(_STD::move(__u.__table_), __a)
971{
972 if (__a != __u.get_allocator())
973 {
974 iterator __i = __u.begin();
975 while (__u.size() != 0)
976 __table_.__insert_unique(
977 _STD::move(__u.__table_.remove((__i++).__i_)->__value_)
978 );
979 }
980}
981
Howard Hinnant73d21a42010-09-04 23:28:19 +0000982#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000983
984template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
985unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
986 initializer_list<value_type> __il)
987{
988 insert(__il.begin(), __il.end());
989}
990
991template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
992unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
993 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
994 const key_equal& __eql)
995 : __table_(__hf, __eql)
996{
997 __table_.rehash(__n);
998 insert(__il.begin(), __il.end());
999}
1000
1001template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1002unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1003 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1004 const key_equal& __eql, const allocator_type& __a)
1005 : __table_(__hf, __eql, __a)
1006{
1007 __table_.rehash(__n);
1008 insert(__il.begin(), __il.end());
1009}
1010
Howard Hinnant73d21a42010-09-04 23:28:19 +00001011#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001012
1013template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001014inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001015unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1016unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001017 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001018{
1019 __table_ = _STD::move(__u.__table_);
1020 return *this;
1021}
1022
Howard Hinnant73d21a42010-09-04 23:28:19 +00001023#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001024
1025template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001026inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001027unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1028unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1029 initializer_list<value_type> __il)
1030{
1031 __table_.__assign_unique(__il.begin(), __il.end());
1032 return *this;
1033}
1034
Howard Hinnant73d21a42010-09-04 23:28:19 +00001035#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1036#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001037
1038template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1039template <class _A0, class... _Args,
1040 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1041 >
1042typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1043unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1044 _Args&&... __args)
1045{
1046 __node_allocator& __na = __table_.__node_alloc();
1047 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant2529d022011-02-02 17:36:20 +00001048 __node_traits::construct(__na, _STD::addressof(__h->__value_.first),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001049 _STD::forward<_A0>(__a0));
1050 __h.get_deleter().__first_constructed = true;
Howard Hinnant2529d022011-02-02 17:36:20 +00001051 __node_traits::construct(__na, _STD::addressof(__h->__value_.second),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001052 _STD::forward<_Args>(__args)...);
1053 __h.get_deleter().__second_constructed = true;
1054 return __h;
1055}
1056
Howard Hinnant73d21a42010-09-04 23:28:19 +00001057#endif // _LIBCPP_HAS_NO_VARIADICS
1058
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001059template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1060template <class _A0,
1061 class // = typename enable_if<is_convertible<_A0, value_type>::value>::type
1062 >
1063typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1064unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1065{
1066 __node_allocator& __na = __table_.__node_alloc();
1067 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant2529d022011-02-02 17:36:20 +00001068 __node_traits::construct(__na, _STD::addressof(__h->__value_),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001069 _STD::forward<_A0>(__a0));
1070 __h.get_deleter().__first_constructed = true;
1071 __h.get_deleter().__second_constructed = true;
1072 return __h;
1073}
1074
Howard Hinnant73d21a42010-09-04 23:28:19 +00001075#ifndef _LIBCPP_HAS_NO_VARIADICS
1076
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001077template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1078template <class _A0, class... _Args,
1079 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1080 >
1081pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1082unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1083{
1084 __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1085 _STD::forward<_Args>(__args)...);
1086 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1087 if (__r.second)
1088 __h.release();
1089 return __r;
1090}
1091
Howard Hinnant73d21a42010-09-04 23:28:19 +00001092#endif // _LIBCPP_HAS_NO_VARIADICS
1093#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001094
1095template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1096typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1097unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1098{
1099 __node_allocator& __na = __table_.__node_alloc();
1100 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant2529d022011-02-02 17:36:20 +00001101 __node_traits::construct(__na, _STD::addressof(__h->__value_.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001102 __h.get_deleter().__first_constructed = true;
Howard Hinnant2529d022011-02-02 17:36:20 +00001103 __node_traits::construct(__na, _STD::addressof(__h->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001104 __h.get_deleter().__second_constructed = true;
1105 return _STD::move(__h);
1106}
1107
Howard Hinnant73d21a42010-09-04 23:28:19 +00001108#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001109
1110template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1111template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001112inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001113void
1114unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1115 _InputIterator __last)
1116{
1117 for (; __first != __last; ++__first)
1118 __table_.__insert_unique(*__first);
1119}
1120
1121template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1122_Tp&
1123unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1124{
1125 iterator __i = find(__k);
1126 if (__i != end())
1127 return __i->second;
1128 __node_holder __h = __construct_node(__k);
1129 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1130 __h.release();
1131 return __r.first->second;
1132}
1133
Howard Hinnant73d21a42010-09-04 23:28:19 +00001134#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001135
1136template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1137_Tp&
1138unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1139{
1140 iterator __i = find(__k);
1141 if (__i != end())
1142 return __i->second;
1143 __node_holder __h = __construct_node(_STD::move(__k));
1144 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1145 __h.release();
1146 return __r.first->second;
1147}
1148
Howard Hinnant73d21a42010-09-04 23:28:19 +00001149#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001150
1151template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1152_Tp&
1153unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1154{
1155 iterator __i = find(__k);
1156#ifndef _LIBCPP_NO_EXCEPTIONS
1157 if (__i == end())
1158 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001159#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001160 return __i->second;
1161}
1162
1163template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1164const _Tp&
1165unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1166{
1167 const_iterator __i = find(__k);
1168#ifndef _LIBCPP_NO_EXCEPTIONS
1169 if (__i == end())
1170 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001171#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001172 return __i->second;
1173}
1174
1175template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001176inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001177void
1178swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1179 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001180 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001181{
1182 __x.swap(__y);
1183}
1184
1185template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1186bool
1187operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1188 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1189{
1190 if (__x.size() != __y.size())
1191 return false;
1192 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1193 const_iterator;
1194 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1195 __i != __ex; ++__i)
1196 {
1197 const_iterator __j = __y.find(__i->first);
1198 if (__j == __ey || !(*__i == *__j))
1199 return false;
1200 }
1201 return true;
1202}
1203
1204template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001205inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001206bool
1207operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1208 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1209{
1210 return !(__x == __y);
1211}
1212
1213template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1214 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001215class _LIBCPP_VISIBLE unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001216{
1217public:
1218 // types
1219 typedef _Key key_type;
1220 typedef _Tp mapped_type;
1221 typedef _Hash hasher;
1222 typedef _Pred key_equal;
1223 typedef _Alloc allocator_type;
1224 typedef pair<const key_type, mapped_type> value_type;
1225 typedef value_type& reference;
1226 typedef const value_type& const_reference;
1227
1228private:
1229 typedef pair<key_type, mapped_type> __value_type;
1230 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
1231 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
1232 typedef typename allocator_traits<allocator_type>::template
1233#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1234 rebind_alloc<__value_type>
1235#else
1236 rebind_alloc<__value_type>::other
1237#endif
1238 __allocator_type;
1239
1240 typedef __hash_table<__value_type, __hasher,
1241 __key_equal, __allocator_type> __table;
1242
1243 __table __table_;
1244
1245 typedef typename __table::__node_traits __node_traits;
1246 typedef typename __table::__node_allocator __node_allocator;
1247 typedef typename __table::__node __node;
1248 typedef __hash_map_node_destructor<__node_allocator> _D;
1249 typedef unique_ptr<__node, _D> __node_holder;
1250 typedef allocator_traits<allocator_type> __alloc_traits;
1251public:
1252 typedef typename __alloc_traits::pointer pointer;
1253 typedef typename __alloc_traits::const_pointer const_pointer;
1254 typedef typename __alloc_traits::size_type size_type;
1255 typedef typename __alloc_traits::difference_type difference_type;
1256
1257 typedef __hash_map_iterator<typename __table::iterator> iterator;
1258 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1259 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1260 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1261
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001262 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001263 unordered_multimap()
1264 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1265 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001266 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1267 const key_equal& __eql = key_equal());
1268 unordered_multimap(size_type __n, const hasher& __hf,
1269 const key_equal& __eql,
1270 const allocator_type& __a);
1271 template <class _InputIterator>
1272 unordered_multimap(_InputIterator __first, _InputIterator __last);
1273 template <class _InputIterator>
1274 unordered_multimap(_InputIterator __first, _InputIterator __last,
1275 size_type __n, const hasher& __hf = hasher(),
1276 const key_equal& __eql = key_equal());
1277 template <class _InputIterator>
1278 unordered_multimap(_InputIterator __first, _InputIterator __last,
1279 size_type __n, const hasher& __hf,
1280 const key_equal& __eql,
1281 const allocator_type& __a);
1282 explicit unordered_multimap(const allocator_type& __a);
1283 unordered_multimap(const unordered_multimap& __u);
1284 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001285#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001286 unordered_multimap(unordered_multimap&& __u)
1287 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001288 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001289#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001290 unordered_multimap(initializer_list<value_type> __il);
1291 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1292 const hasher& __hf = hasher(),
1293 const key_equal& __eql = key_equal());
1294 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1295 const hasher& __hf, const key_equal& __eql,
1296 const allocator_type& __a);
1297 // ~unordered_multimap() = default;
1298 // unordered_multimap& operator=(const unordered_multimap& __u) = default;
Howard Hinnant73d21a42010-09-04 23:28:19 +00001299#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001300 unordered_multimap& operator=(unordered_multimap&& __u)
1301 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001302#endif
1303 unordered_multimap& operator=(initializer_list<value_type> __il);
1304
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001305 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001306 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001307 {return allocator_type(__table_.__node_alloc());}
1308
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001309 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001310 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001311 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001312 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001313 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001314 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001315
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001316 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001317 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001318 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001319 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001320 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001321 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001322 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001323 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001324 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001325 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001326 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001327 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001328
Howard Hinnant73d21a42010-09-04 23:28:19 +00001329#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001330 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001331 iterator emplace()
1332 {return __table_.__emplace_multi();}
1333
1334 template <class _A0,
1335 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001336 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001337 iterator emplace(_A0&& __a0)
1338 {return __table_.__emplace_multi(_STD::forward<_A0>(__a0));}
1339
Howard Hinnant73d21a42010-09-04 23:28:19 +00001340#ifndef _LIBCPP_HAS_NO_VARIADICS
1341
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001342 template <class _A0, class... _Args,
1343 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1344 iterator emplace(_A0&& __a0, _Args&&... __args);
1345
Howard Hinnant73d21a42010-09-04 23:28:19 +00001346#endif // _LIBCPP_HAS_NO_VARIADICS
1347
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001349 iterator emplace_hint(const_iterator __p)
1350 {return __table_.__emplace_hint_multi(__p.__i_);}
1351
1352 template <class _A0,
1353 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001355 iterator emplace_hint(const_iterator __p, _A0&& __a0)
1356 {return __table_.__emplace_hint_multi(__p.__i_, _STD::forward<_A0>(__a0));}
1357
Howard Hinnant73d21a42010-09-04 23:28:19 +00001358#ifndef _LIBCPP_HAS_NO_VARIADICS
1359
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001360 template <class _A0, class... _Args,
1361 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1362 iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001363#endif // _LIBCPP_HAS_NO_VARIADICS
1364#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001365 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001366 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001367#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001368 template <class _P,
1369 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001370 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001371 iterator insert(_P&& __x)
1372 {return __table_.__insert_multi(_STD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001373#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001374 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001375 iterator insert(const_iterator __p, const value_type& __x)
1376 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001377#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001378 template <class _P,
1379 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001380 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001381 iterator insert(const_iterator __p, _P&& __x)
1382 {return __table_.__insert_multi(__p.__i_, _STD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001383#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001384 template <class _InputIterator>
1385 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001386 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001387 void insert(initializer_list<value_type> __il)
1388 {insert(__il.begin(), __il.end());}
1389
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001390 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001391 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001393 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001394 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001395 iterator erase(const_iterator __first, const_iterator __last)
1396 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001397 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001398 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001399
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001400 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001401 void swap(unordered_multimap& __u)
1402 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1403 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001404
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001405 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001406 hasher hash_function() const
1407 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001409 key_equal key_eq() const
1410 {return __table_.key_eq().key_eq();}
1411
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001412 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001413 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001414 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001415 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001416 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001417 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001418 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001419 pair<iterator, iterator> equal_range(const key_type& __k)
1420 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001421 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001422 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1423 {return __table_.__equal_range_multi(__k);}
1424
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001426 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001428 size_type max_bucket_count() const _NOEXCEPT
1429 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001430
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001431 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001432 size_type bucket_size(size_type __n) const
1433 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001434 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001435 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1436
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001437 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001438 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001439 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001440 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001441 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001442 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001443 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001444 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001446 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001447 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001448 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1449
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001450 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001451 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001452 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001453 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001454 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001455 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001456 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001457 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001458 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001459 void reserve(size_type __n) {__table_.reserve(__n);}
1460
1461private:
Howard Hinnant73d21a42010-09-04 23:28:19 +00001462#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001463 template <class _A0, class... _Args,
1464 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1465 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
1466 template <class _A0,
1467 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
1468 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001469#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001470};
1471
1472template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1473unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1474 size_type __n, const hasher& __hf, const key_equal& __eql)
1475 : __table_(__hf, __eql)
1476{
1477 __table_.rehash(__n);
1478}
1479
1480template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1481unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1482 size_type __n, const hasher& __hf, const key_equal& __eql,
1483 const allocator_type& __a)
1484 : __table_(__hf, __eql, __a)
1485{
1486 __table_.rehash(__n);
1487}
1488
1489template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1490template <class _InputIterator>
1491unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1492 _InputIterator __first, _InputIterator __last)
1493{
1494 insert(__first, __last);
1495}
1496
1497template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1498template <class _InputIterator>
1499unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1500 _InputIterator __first, _InputIterator __last, size_type __n,
1501 const hasher& __hf, const key_equal& __eql)
1502 : __table_(__hf, __eql)
1503{
1504 __table_.rehash(__n);
1505 insert(__first, __last);
1506}
1507
1508template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1509template <class _InputIterator>
1510unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1511 _InputIterator __first, _InputIterator __last, size_type __n,
1512 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1513 : __table_(__hf, __eql, __a)
1514{
1515 __table_.rehash(__n);
1516 insert(__first, __last);
1517}
1518
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001519template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001520inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001521unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1522 const allocator_type& __a)
1523 : __table_(__a)
1524{
1525}
1526
1527template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1528unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1529 const unordered_multimap& __u)
1530 : __table_(__u.__table_)
1531{
1532 __table_.rehash(__u.bucket_count());
1533 insert(__u.begin(), __u.end());
1534}
1535
1536template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1537unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1538 const unordered_multimap& __u, const allocator_type& __a)
1539 : __table_(__u.__table_, __a)
1540{
1541 __table_.rehash(__u.bucket_count());
1542 insert(__u.begin(), __u.end());
1543}
1544
Howard Hinnant73d21a42010-09-04 23:28:19 +00001545#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001546
1547template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001548inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001549unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1550 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001551 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001552 : __table_(_STD::move(__u.__table_))
1553{
1554}
1555
1556template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1557unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1558 unordered_multimap&& __u, const allocator_type& __a)
1559 : __table_(_STD::move(__u.__table_), __a)
1560{
1561 if (__a != __u.get_allocator())
1562 {
1563 iterator __i = __u.begin();
1564 while (__u.size() != 0)
1565{
1566 __table_.__insert_multi(
1567 _STD::move(__u.__table_.remove((__i++).__i_)->__value_)
1568 );
1569}
1570 }
1571}
1572
Howard Hinnant73d21a42010-09-04 23:28:19 +00001573#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001574
1575template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1576unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1577 initializer_list<value_type> __il)
1578{
1579 insert(__il.begin(), __il.end());
1580}
1581
1582template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1583unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1584 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1585 const key_equal& __eql)
1586 : __table_(__hf, __eql)
1587{
1588 __table_.rehash(__n);
1589 insert(__il.begin(), __il.end());
1590}
1591
1592template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1593unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1594 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1595 const key_equal& __eql, const allocator_type& __a)
1596 : __table_(__hf, __eql, __a)
1597{
1598 __table_.rehash(__n);
1599 insert(__il.begin(), __il.end());
1600}
1601
Howard Hinnant73d21a42010-09-04 23:28:19 +00001602#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001603
1604template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001605inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001606unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1607unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001608 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001609{
1610 __table_ = _STD::move(__u.__table_);
1611 return *this;
1612}
1613
Howard Hinnant73d21a42010-09-04 23:28:19 +00001614#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001615
1616template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001617inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001618unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1619unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1620 initializer_list<value_type> __il)
1621{
1622 __table_.__assign_multi(__il.begin(), __il.end());
1623 return *this;
1624}
1625
Howard Hinnant73d21a42010-09-04 23:28:19 +00001626#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1627#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001628
1629template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1630template <class _A0, class... _Args,
1631 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1632 >
1633typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1634unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1635 _A0&& __a0, _Args&&... __args)
1636{
1637 __node_allocator& __na = __table_.__node_alloc();
1638 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant2529d022011-02-02 17:36:20 +00001639 __node_traits::construct(__na, _STD::addressof(__h->__value_.first),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001640 _STD::forward<_A0>(__a0));
1641 __h.get_deleter().__first_constructed = true;
Howard Hinnant2529d022011-02-02 17:36:20 +00001642 __node_traits::construct(__na, _STD::addressof(__h->__value_.second),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001643 _STD::forward<_Args>(__args)...);
1644 __h.get_deleter().__second_constructed = true;
1645 return __h;
1646}
1647
Howard Hinnant73d21a42010-09-04 23:28:19 +00001648#endif // _LIBCPP_HAS_NO_VARIADICS
1649
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001650template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1651template <class _A0,
1652 class // = typename enable_if<is_convertible<_A0, value_type>::value>::type
1653 >
1654typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1655unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1656{
1657 __node_allocator& __na = __table_.__node_alloc();
1658 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant2529d022011-02-02 17:36:20 +00001659 __node_traits::construct(__na, _STD::addressof(__h->__value_),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001660 _STD::forward<_A0>(__a0));
1661 __h.get_deleter().__first_constructed = true;
1662 __h.get_deleter().__second_constructed = true;
1663 return __h;
1664}
1665
Howard Hinnant73d21a42010-09-04 23:28:19 +00001666#ifndef _LIBCPP_HAS_NO_VARIADICS
1667
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001668template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1669template <class _A0, class... _Args,
1670 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1671 >
1672typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1673unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1674{
1675 __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1676 _STD::forward<_Args>(__args)...);
1677 iterator __r = __table_.__node_insert_multi(__h.get());
1678 __h.release();
1679 return __r;
1680}
1681
1682template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1683template <class _A0, class... _Args,
1684 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1685 >
1686typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1687unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1688 const_iterator __p, _A0&& __a0, _Args&&... __args)
1689{
1690 __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1691 _STD::forward<_Args>(__args)...);
1692 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1693 __h.release();
1694 return __r;
1695}
1696
Howard Hinnant73d21a42010-09-04 23:28:19 +00001697#endif // _LIBCPP_HAS_NO_VARIADICS
1698#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001699
1700template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1701template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001702inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001703void
1704unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1705 _InputIterator __last)
1706{
1707 for (; __first != __last; ++__first)
1708 __table_.__insert_multi(*__first);
1709}
1710
1711template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001712inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001713void
1714swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1715 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001716 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001717{
1718 __x.swap(__y);
1719}
1720
1721template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1722bool
1723operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1724 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1725{
1726 if (__x.size() != __y.size())
1727 return false;
1728 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1729 const_iterator;
1730 typedef pair<const_iterator, const_iterator> _EqRng;
1731 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1732 {
1733 _EqRng __xeq = __x.equal_range(__i->first);
1734 _EqRng __yeq = __y.equal_range(__i->first);
1735 if (_STD::distance(__xeq.first, __xeq.second) !=
1736 _STD::distance(__yeq.first, __yeq.second) ||
1737 !_STD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1738 return false;
1739 __i = __xeq.second;
1740 }
1741 return true;
1742}
1743
1744template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001745inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001746bool
1747operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1748 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1749{
1750 return !(__x == __y);
1751}
1752
1753_LIBCPP_END_NAMESPACE_STD
1754
1755#endif // _LIBCPP_UNORDERED_MAP