blob: 56f1ee16c04195deb388ecf3254a6d14a499735c [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
47 explicit unordered_map(size_type n = 0, const hasher& hf = hasher(),
48 const key_equal& eql = key_equal(),
49 const allocator_type& a = allocator_type());
50 template <class InputIterator>
51 unordered_map(InputIterator f, InputIterator l,
52 size_type n = 0, const hasher& hf = hasher(),
53 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 explicit unordered_map(const allocator_type&);
56 unordered_map(const unordered_map&);
57 unordered_map(const unordered_map&, const Allocator&);
58 unordered_map(unordered_map&&);
59 unordered_map(unordered_map&&, const Allocator&);
60 unordered_map(initializer_list<value_type>, size_type n = 0,
61 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
62 const allocator_type& a = allocator_type());
63 ~unordered_map();
64 unordered_map& operator=(const unordered_map&);
65 unordered_map& operator=(unordered_map&&);
66 unordered_map& operator=(initializer_list<value_type>);
67
68 allocator_type get_allocator() const;
69
70 bool empty() const;
71 size_type size() const;
72 size_type max_size() const;
73
74 iterator begin();
75 iterator end();
76 const_iterator begin() const;
77 const_iterator end() const;
78 const_iterator cbegin() const;
79 const_iterator cend() const;
80
81 template <class... Args>
82 pair<iterator, bool> emplace(Args&&... args);
83 template <class... Args>
84 iterator emplace_hint(const_iterator position, Args&&... args);
85 pair<iterator, bool> insert(const value_type& obj);
86 template <class P>
87 pair<iterator, bool> insert(P&& obj);
88 iterator insert(const_iterator hint, const value_type& obj);
89 template <class P>
90 iterator insert(const_iterator hint, P&& obj);
91 template <class InputIterator>
92 void insert(InputIterator first, InputIterator last);
93 void insert(initializer_list<value_type>);
94
95 iterator erase(const_iterator position);
96 size_type erase(const key_type& k);
97 iterator erase(const_iterator first, const_iterator last);
98 void clear();
99
100 void swap(unordered_map&);
101
102 hasher hash_function() const;
103 key_equal key_eq() const;
104
105 iterator find(const key_type& k);
106 const_iterator find(const key_type& k) const;
107 size_type count(const key_type& k) const;
108 pair<iterator, iterator> equal_range(const key_type& k);
109 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
110
111 mapped_type& operator[](const key_type& k);
112 mapped_type& operator[](key_type&& k);
113
114 mapped_type& at(const key_type& k);
115 const mapped_type& at(const key_type& k) const;
116
117 size_type bucket_count() const;
118 size_type max_bucket_count() const;
119
120 size_type bucket_size(size_type n) const;
121 size_type bucket(const key_type& k) const;
122
123 local_iterator begin(size_type n);
124 local_iterator end(size_type n);
125 const_local_iterator begin(size_type n) const;
126 const_local_iterator end(size_type n) const;
127 const_local_iterator cbegin(size_type n) const;
128 const_local_iterator cend(size_type n) const;
129
130 float load_factor() const;
131 float max_load_factor() const;
132 void max_load_factor(float z);
133 void rehash(size_type n);
134 void reserve(size_type n);
135};
136
137template <class Key, class T, class Hash, class Pred, class Alloc>
138 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
139 unordered_map<Key, T, Hash, Pred, Alloc>& y);
140
141template <class Key, class T, class Hash, class Pred, class Alloc>
142 bool
143 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
144 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
145
146template <class Key, class T, class Hash, class Pred, class Alloc>
147 bool
148 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
149 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
150
151template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
152 class Alloc = allocator<pair<const Key, T>>>
153class unordered_multimap
154{
155public:
156 // types
157 typedef Key key_type;
158 typedef T mapped_type;
159 typedef Hash hasher;
160 typedef Pred key_equal;
161 typedef Alloc allocator_type;
162 typedef pair<const key_type, mapped_type> value_type;
163 typedef value_type& reference;
164 typedef const value_type& const_reference;
165 typedef typename allocator_traits<allocator_type>::pointer pointer;
166 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
167 typedef typename allocator_traits<allocator_type>::size_type size_type;
168 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
169
170 typedef /unspecified/ iterator;
171 typedef /unspecified/ const_iterator;
172 typedef /unspecified/ local_iterator;
173 typedef /unspecified/ const_local_iterator;
174
175 explicit unordered_multimap(size_type n = 0, const hasher& hf = hasher(),
176 const key_equal& eql = key_equal(),
177 const allocator_type& a = allocator_type());
178 template <class InputIterator>
179 unordered_multimap(InputIterator f, InputIterator l,
180 size_type n = 0, const hasher& hf = hasher(),
181 const key_equal& eql = key_equal(),
182 const allocator_type& a = allocator_type());
183 explicit unordered_multimap(const allocator_type&);
184 unordered_multimap(const unordered_multimap&);
185 unordered_multimap(const unordered_multimap&, const Allocator&);
186 unordered_multimap(unordered_multimap&&);
187 unordered_multimap(unordered_multimap&&, const Allocator&);
188 unordered_multimap(initializer_list<value_type>, size_type n = 0,
189 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
190 const allocator_type& a = allocator_type());
191 ~unordered_multimap();
192 unordered_multimap& operator=(const unordered_multimap&);
193 unordered_multimap& operator=(unordered_multimap&&);
194 unordered_multimap& operator=(initializer_list<value_type>);
195
196 allocator_type get_allocator() const;
197
198 bool empty() const;
199 size_type size() const;
200 size_type max_size() const;
201
202 iterator begin();
203 iterator end();
204 const_iterator begin() const;
205 const_iterator end() const;
206 const_iterator cbegin() const;
207 const_iterator cend() const;
208
209 template <class... Args>
210 iterator emplace(Args&&... args);
211 template <class... Args>
212 iterator emplace_hint(const_iterator position, Args&&... args);
213 iterator insert(const value_type& obj);
214 template <class P>
215 iterator insert(P&& obj);
216 iterator insert(const_iterator hint, const value_type& obj);
217 template <class P>
218 iterator insert(const_iterator hint, P&& obj);
219 template <class InputIterator>
220 void insert(InputIterator first, InputIterator last);
221 void insert(initializer_list<value_type>);
222
223 iterator erase(const_iterator position);
224 size_type erase(const key_type& k);
225 iterator erase(const_iterator first, const_iterator last);
226 void clear();
227
228 void swap(unordered_multimap&);
229
230 hasher hash_function() const;
231 key_equal key_eq() const;
232
233 iterator find(const key_type& k);
234 const_iterator find(const key_type& k) const;
235 size_type count(const key_type& k) const;
236 pair<iterator, iterator> equal_range(const key_type& k);
237 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
238
239 size_type bucket_count() const;
240 size_type max_bucket_count() const;
241
242 size_type bucket_size(size_type n) const;
243 size_type bucket(const key_type& k) const;
244
245 local_iterator begin(size_type n);
246 local_iterator end(size_type n);
247 const_local_iterator begin(size_type n) const;
248 const_local_iterator end(size_type n) const;
249 const_local_iterator cbegin(size_type n) const;
250 const_local_iterator cend(size_type n) const;
251
252 float load_factor() const;
253 float max_load_factor() const;
254 void max_load_factor(float z);
255 void rehash(size_type n);
256 void reserve(size_type n);
257};
258
259template <class Key, class T, class Hash, class Pred, class Alloc>
260 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
261 unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
262
263template <class Key, class T, class Hash, class Pred, class Alloc>
264 bool
265 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
266 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
267
268template <class Key, class T, class Hash, class Pred, class Alloc>
269 bool
270 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
271 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
272
273} // std
274
275*/
276
277#include <__config>
278#include <__hash_table>
279#include <functional>
280#include <stdexcept>
281
282#pragma GCC system_header
283
284_LIBCPP_BEGIN_NAMESPACE_STD
285
286template <class _Tp, class _Hash, bool = is_empty<_Hash>::value>
287class __unordered_map_hasher
288 : private _Hash
289{
290public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000291 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000292 __unordered_map_hasher() : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000293 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000294 __unordered_map_hasher(const _Hash& __h) : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000295 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000296 const _Hash& hash_function() const {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000297 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000298 size_t operator()(const _Tp& __x) const
299 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000300 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000301 size_t operator()(const typename _Tp::first_type& __x) const
302 {return static_cast<const _Hash&>(*this)(__x);}
303};
304
305template <class _Tp, class _Hash>
306class __unordered_map_hasher<_Tp, _Hash, false>
307{
308 _Hash __hash_;
309public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000310 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000311 __unordered_map_hasher() : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000312 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000313 __unordered_map_hasher(const _Hash& __h) : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000314 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000315 const _Hash& hash_function() const {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000316 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000317 size_t operator()(const _Tp& __x) const
318 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000319 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000320 size_t operator()(const typename _Tp::first_type& __x) const
321 {return __hash_(__x);}
322};
323
324template <class _Tp, class _Pred, bool = is_empty<_Pred>::value>
325class __unordered_map_equal
326 : private _Pred
327{
328public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000329 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000330 __unordered_map_equal() : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000331 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000332 __unordered_map_equal(const _Pred& __p) : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000333 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000334 const _Pred& key_eq() const {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000336 bool operator()(const _Tp& __x, const _Tp& __y) const
337 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000338 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000339 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
340 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000342 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
343 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000344 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant324bb032010-08-22 00:02:43 +0000345 bool operator()(const typename _Tp::first_type& __x,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000346 const typename _Tp::first_type& __y) const
347 {return static_cast<const _Pred&>(*this)(__x, __y);}
348};
349
350template <class _Tp, class _Pred>
351class __unordered_map_equal<_Tp, _Pred, false>
352{
353 _Pred __pred_;
354public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000355 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000356 __unordered_map_equal() : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000357 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000358 __unordered_map_equal(const _Pred& __p) : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000359 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000360 const _Pred& key_eq() const {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000361 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000362 bool operator()(const _Tp& __x, const _Tp& __y) const
363 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000365 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
366 {return __pred_(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000367 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000368 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
369 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000370 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000371 bool operator()(const typename _Tp::first_type& __x,
372 const typename _Tp::first_type& __y) const
373 {return __pred_(__x, __y);}
374};
375
376template <class _Alloc>
377class __hash_map_node_destructor
378{
379 typedef _Alloc allocator_type;
380 typedef allocator_traits<allocator_type> __alloc_traits;
381 typedef typename __alloc_traits::value_type::value_type value_type;
382public:
383 typedef typename __alloc_traits::pointer pointer;
384private:
385 typedef typename value_type::first_type first_type;
386 typedef typename value_type::second_type second_type;
387
388 allocator_type& __na_;
389
390 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
391
392public:
393 bool __first_constructed;
394 bool __second_constructed;
395
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000397 explicit __hash_map_node_destructor(allocator_type& __na)
398 : __na_(__na),
399 __first_constructed(false),
400 __second_constructed(false)
401 {}
402
Howard Hinnant73d21a42010-09-04 23:28:19 +0000403#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000405 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
406 : __na_(__x.__na_),
407 __first_constructed(__x.__value_constructed),
408 __second_constructed(__x.__value_constructed)
409 {
410 __x.__value_constructed = false;
411 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000412#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000414 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
415 : __na_(__x.__na_),
416 __first_constructed(__x.__value_constructed),
417 __second_constructed(__x.__value_constructed)
418 {
419 const_cast<bool&>(__x.__value_constructed) = false;
420 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000421#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000422
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000424 void operator()(pointer __p)
425 {
426 if (__second_constructed)
427 __alloc_traits::destroy(__na_, addressof(__p->__value_.second));
428 if (__first_constructed)
429 __alloc_traits::destroy(__na_, addressof(__p->__value_.first));
430 if (__p)
431 __alloc_traits::deallocate(__na_, __p, 1);
432 }
433};
434
435template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000436class _LIBCPP_VISIBLE __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000437{
438 _HashIterator __i_;
439
440 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
441 typedef const typename _HashIterator::value_type::first_type key_type;
442 typedef typename _HashIterator::value_type::second_type mapped_type;
443public:
444 typedef forward_iterator_tag iterator_category;
445 typedef pair<key_type, mapped_type> value_type;
446 typedef typename _HashIterator::difference_type difference_type;
447 typedef value_type& reference;
448 typedef typename __pointer_traits::template
449#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
450 rebind<value_type>
451#else
452 rebind<value_type>::other
453#endif
454 pointer;
455
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000456 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000457 __hash_map_iterator() {}
458
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000460 __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
461
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000462 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000463 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000464 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000465 pointer operator->() const {return (pointer)__i_.operator->();}
466
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000468 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000469 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000470 __hash_map_iterator operator++(int)
471 {
472 __hash_map_iterator __t(*this);
473 ++(*this);
474 return __t;
475 }
476
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000477 friend _LIBCPP_INLINE_VISIBILITY
478 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000479 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000480 friend _LIBCPP_INLINE_VISIBILITY
481 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000482 {return __x.__i_ != __y.__i_;}
483
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000484 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
485 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
486 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
487 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
488 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489};
490
491template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000492class _LIBCPP_VISIBLE __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000493{
494 _HashIterator __i_;
495
496 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
497 typedef const typename _HashIterator::value_type::first_type key_type;
498 typedef typename _HashIterator::value_type::second_type mapped_type;
499public:
500 typedef forward_iterator_tag iterator_category;
501 typedef pair<key_type, mapped_type> value_type;
502 typedef typename _HashIterator::difference_type difference_type;
503 typedef const value_type& reference;
504 typedef typename __pointer_traits::template
505#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
506 rebind<value_type>
507#else
508 rebind<value_type>::other
509#endif
510 pointer;
511
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000512 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000513 __hash_map_const_iterator() {}
514
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000515 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000516 __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000517 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000518 __hash_map_const_iterator(
519 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
520 : __i_(__i.__i_) {}
521
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000522 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000523 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525 pointer operator->() const {return (pointer)__i_.operator->();}
526
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000528 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000530 __hash_map_const_iterator operator++(int)
531 {
532 __hash_map_const_iterator __t(*this);
533 ++(*this);
534 return __t;
535 }
536
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000537 friend _LIBCPP_INLINE_VISIBILITY
538 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000539 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000540 friend _LIBCPP_INLINE_VISIBILITY
541 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000542 {return __x.__i_ != __y.__i_;}
543
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000544 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
545 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
546 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
547 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000548};
549
550template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
551 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000552class _LIBCPP_VISIBLE unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000553{
554public:
555 // types
556 typedef _Key key_type;
557 typedef _Tp mapped_type;
558 typedef _Hash hasher;
559 typedef _Pred key_equal;
560 typedef _Alloc allocator_type;
561 typedef pair<const key_type, mapped_type> value_type;
562 typedef value_type& reference;
563 typedef const value_type& const_reference;
564
565private:
566 typedef pair<key_type, mapped_type> __value_type;
567 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
568 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
569 typedef typename allocator_traits<allocator_type>::template
570#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
571 rebind_alloc<__value_type>
572#else
573 rebind_alloc<__value_type>::other
574#endif
575 __allocator_type;
576
577 typedef __hash_table<__value_type, __hasher,
578 __key_equal, __allocator_type> __table;
579
580 __table __table_;
581
582 typedef typename __table::__node_pointer __node_pointer;
583 typedef typename __table::__node_const_pointer __node_const_pointer;
584 typedef typename __table::__node_traits __node_traits;
585 typedef typename __table::__node_allocator __node_allocator;
586 typedef typename __table::__node __node;
587 typedef __hash_map_node_destructor<__node_allocator> _D;
588 typedef unique_ptr<__node, _D> __node_holder;
589 typedef allocator_traits<allocator_type> __alloc_traits;
590public:
591 typedef typename __alloc_traits::pointer pointer;
592 typedef typename __alloc_traits::const_pointer const_pointer;
593 typedef typename __alloc_traits::size_type size_type;
594 typedef typename __alloc_traits::difference_type difference_type;
595
596 typedef __hash_map_iterator<typename __table::iterator> iterator;
597 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
598 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
599 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
600
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000601 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000602 unordered_map() {} // = default;
603 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
604 const key_equal& __eql = key_equal());
605 unordered_map(size_type __n, const hasher& __hf,
606 const key_equal& __eql,
607 const allocator_type& __a);
608 template <class _InputIterator>
609 unordered_map(_InputIterator __first, _InputIterator __last);
610 template <class _InputIterator>
611 unordered_map(_InputIterator __first, _InputIterator __last,
612 size_type __n, const hasher& __hf = hasher(),
613 const key_equal& __eql = key_equal());
614 template <class _InputIterator>
615 unordered_map(_InputIterator __first, _InputIterator __last,
616 size_type __n, const hasher& __hf,
617 const key_equal& __eql,
618 const allocator_type& __a);
619 explicit unordered_map(const allocator_type& __a);
620 unordered_map(const unordered_map& __u);
621 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000622#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000623 unordered_map(unordered_map&& __u);
624 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000625#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000626 unordered_map(initializer_list<value_type> __il);
627 unordered_map(initializer_list<value_type> __il, size_type __n,
628 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
629 unordered_map(initializer_list<value_type> __il, size_type __n,
630 const hasher& __hf, const key_equal& __eql,
631 const allocator_type& __a);
632 // ~unordered_map() = default;
633 // unordered_map& operator=(const unordered_map& __u) = default;
Howard Hinnant73d21a42010-09-04 23:28:19 +0000634#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000635 unordered_map& operator=(unordered_map&& __u);
636#endif
637 unordered_map& operator=(initializer_list<value_type> __il);
638
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000639 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000640 allocator_type get_allocator() const
641 {return allocator_type(__table_.__node_alloc());}
642
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000643 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000644 bool empty() const {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000645 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000646 size_type size() const {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000647 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000648 size_type max_size() const {return __table_.max_size();}
649
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000650 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000651 iterator begin() {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000652 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000653 iterator end() {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000654 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000655 const_iterator begin() const {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000656 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000657 const_iterator end() const {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000658 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000659 const_iterator cbegin() const {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000660 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000661 const_iterator cend() const {return __table_.end();}
662
Howard Hinnant73d21a42010-09-04 23:28:19 +0000663#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000664 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000665 pair<iterator, bool> emplace()
666 {return __table_.__emplace_unique();}
667
668 template <class _A0,
669 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000670 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000671 pair<iterator, bool> emplace(_A0&& __a0)
672 {return __table_.__emplace_unique(_STD::forward<_A0>(__a0));}
673
Howard Hinnant73d21a42010-09-04 23:28:19 +0000674#ifndef _LIBCPP_HAS_NO_VARIADICS
675
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000676 template <class _A0, class... _Args,
677 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
678 pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args);
679
Howard Hinnant73d21a42010-09-04 23:28:19 +0000680#endif // _LIBCPP_HAS_NO_VARIADICS
681
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000682 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000683 iterator emplace_hint(const_iterator)
684 {return __table_.__emplace_unique().first;}
685
686 template <class _A0,
687 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000688 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000689 iterator emplace_hint(const_iterator, _A0&& __a0)
690 {return __table_.__emplace_unique(_STD::forward<_A0>(__a0)).first;}
691
Howard Hinnant73d21a42010-09-04 23:28:19 +0000692#ifndef _LIBCPP_HAS_NO_VARIADICS
693
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000694 template <class _A0, class... _Args,
695 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000696 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000697 iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args)
698 {return emplace(_STD::forward<_A0>(__a0),
699 _STD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000700#endif // _LIBCPP_HAS_NO_VARIADICS
701#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000702 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000703 pair<iterator, bool> insert(const value_type& __x)
704 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000705#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000706 template <class _P,
707 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000708 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000709 pair<iterator, bool> insert(_P&& __x)
710 {return __table_.__insert_unique(_STD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000711#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000712 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000713 iterator insert(const_iterator, const value_type& __x)
714 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000715#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000716 template <class _P,
717 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000719 iterator insert(const_iterator, _P&& __x)
720 {return insert(_STD::forward<_P>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000721#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000722 template <class _InputIterator>
723 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000724 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000725 void insert(initializer_list<value_type> __il)
726 {insert(__il.begin(), __il.end());}
727
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000728 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000729 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000730 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000731 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000732 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000733 iterator erase(const_iterator __first, const_iterator __last)
734 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000735 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000736 void clear() {__table_.clear();}
737
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000739 void swap(unordered_map& __u) {__table_.swap(__u.__table_);}
740
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000741 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000742 hasher hash_function() const
743 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000744 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000745 key_equal key_eq() const
746 {return __table_.key_eq().key_eq();}
747
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000748 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000749 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000750 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000751 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000752 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000753 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000754 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000755 pair<iterator, iterator> equal_range(const key_type& __k)
756 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000757 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000758 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
759 {return __table_.__equal_range_unique(__k);}
760
761 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000762#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000763 mapped_type& operator[](key_type&& __k);
764#endif
765
766 mapped_type& at(const key_type& __k);
767 const mapped_type& at(const key_type& __k) const;
768
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000769 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000770 size_type bucket_count() const {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000771 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000772 size_type max_bucket_count() const {return __table_.max_bucket_count();}
773
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000774 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000775 size_type bucket_size(size_type __n) const
776 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000777 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000778 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
779
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000781 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000782 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000783 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000784 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000785 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000786 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000787 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000788 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000789 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000790 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000791 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
792
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000794 float load_factor() const {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000795 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000796 float max_load_factor() const {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000797 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000798 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000799 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000800 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000801 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000802 void reserve(size_type __n) {__table_.reserve(__n);}
803
804private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000805#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
806#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000807 template <class _A0, class... _Args,
808 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
809 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000810#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000811 template <class _A0,
812 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
813 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000814#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000815 __node_holder __construct_node(const key_type& __k);
816#endif
817};
818
819template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
820unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
821 size_type __n, const hasher& __hf, const key_equal& __eql)
822 : __table_(__hf, __eql)
823{
824 __table_.rehash(__n);
825}
826
827template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
828unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
829 size_type __n, const hasher& __hf, const key_equal& __eql,
830 const allocator_type& __a)
831 : __table_(__hf, __eql, __a)
832{
833 __table_.rehash(__n);
834}
835
836template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000837inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000838unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
839 const allocator_type& __a)
840 : __table_(__a)
841{
842}
843
844template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
845template <class _InputIterator>
846unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
847 _InputIterator __first, _InputIterator __last)
848{
849 insert(__first, __last);
850}
851
852template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
853template <class _InputIterator>
854unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
855 _InputIterator __first, _InputIterator __last, size_type __n,
856 const hasher& __hf, const key_equal& __eql)
857 : __table_(__hf, __eql)
858{
859 __table_.rehash(__n);
860 insert(__first, __last);
861}
862
863template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
864template <class _InputIterator>
865unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
866 _InputIterator __first, _InputIterator __last, size_type __n,
867 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
868 : __table_(__hf, __eql, __a)
869{
870 __table_.rehash(__n);
871 insert(__first, __last);
872}
873
874template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
875unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
876 const unordered_map& __u)
877 : __table_(__u.__table_)
878{
879 __table_.rehash(__u.bucket_count());
880 insert(__u.begin(), __u.end());
881}
882
883template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
884unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
885 const unordered_map& __u, const allocator_type& __a)
886 : __table_(__u.__table_, __a)
887{
888 __table_.rehash(__u.bucket_count());
889 insert(__u.begin(), __u.end());
890}
891
Howard Hinnant73d21a42010-09-04 23:28:19 +0000892#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000893
894template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000895inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000896unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
897 unordered_map&& __u)
898 : __table_(_STD::move(__u.__table_))
899{
900}
901
902template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
903unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
904 unordered_map&& __u, const allocator_type& __a)
905 : __table_(_STD::move(__u.__table_), __a)
906{
907 if (__a != __u.get_allocator())
908 {
909 iterator __i = __u.begin();
910 while (__u.size() != 0)
911 __table_.__insert_unique(
912 _STD::move(__u.__table_.remove((__i++).__i_)->__value_)
913 );
914 }
915}
916
Howard Hinnant73d21a42010-09-04 23:28:19 +0000917#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000918
919template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
920unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
921 initializer_list<value_type> __il)
922{
923 insert(__il.begin(), __il.end());
924}
925
926template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
927unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
928 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
929 const key_equal& __eql)
930 : __table_(__hf, __eql)
931{
932 __table_.rehash(__n);
933 insert(__il.begin(), __il.end());
934}
935
936template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
937unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
938 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
939 const key_equal& __eql, const allocator_type& __a)
940 : __table_(__hf, __eql, __a)
941{
942 __table_.rehash(__n);
943 insert(__il.begin(), __il.end());
944}
945
Howard Hinnant73d21a42010-09-04 23:28:19 +0000946#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000947
948template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000949inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000950unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
951unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
952{
953 __table_ = _STD::move(__u.__table_);
954 return *this;
955}
956
Howard Hinnant73d21a42010-09-04 23:28:19 +0000957#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000958
959template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000960inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000961unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
962unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
963 initializer_list<value_type> __il)
964{
965 __table_.__assign_unique(__il.begin(), __il.end());
966 return *this;
967}
968
Howard Hinnant73d21a42010-09-04 23:28:19 +0000969#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
970#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000971
972template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
973template <class _A0, class... _Args,
974 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
975 >
976typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
977unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
978 _Args&&... __args)
979{
980 __node_allocator& __na = __table_.__node_alloc();
981 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
982 __node_traits::construct(__na, addressof(__h->__value_.first),
983 _STD::forward<_A0>(__a0));
984 __h.get_deleter().__first_constructed = true;
985 __node_traits::construct(__na, addressof(__h->__value_.second),
986 _STD::forward<_Args>(__args)...);
987 __h.get_deleter().__second_constructed = true;
988 return __h;
989}
990
Howard Hinnant73d21a42010-09-04 23:28:19 +0000991#endif // _LIBCPP_HAS_NO_VARIADICS
992
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000993template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
994template <class _A0,
995 class // = typename enable_if<is_convertible<_A0, value_type>::value>::type
996 >
997typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
998unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
999{
1000 __node_allocator& __na = __table_.__node_alloc();
1001 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1002 __node_traits::construct(__na, addressof(__h->__value_),
1003 _STD::forward<_A0>(__a0));
1004 __h.get_deleter().__first_constructed = true;
1005 __h.get_deleter().__second_constructed = true;
1006 return __h;
1007}
1008
Howard Hinnant73d21a42010-09-04 23:28:19 +00001009#ifndef _LIBCPP_HAS_NO_VARIADICS
1010
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001011template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1012template <class _A0, class... _Args,
1013 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1014 >
1015pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1016unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1017{
1018 __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1019 _STD::forward<_Args>(__args)...);
1020 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1021 if (__r.second)
1022 __h.release();
1023 return __r;
1024}
1025
Howard Hinnant73d21a42010-09-04 23:28:19 +00001026#endif // _LIBCPP_HAS_NO_VARIADICS
1027#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001028
1029template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1030typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1031unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1032{
1033 __node_allocator& __na = __table_.__node_alloc();
1034 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1035 __node_traits::construct(__na, addressof(__h->__value_.first), __k);
1036 __h.get_deleter().__first_constructed = true;
1037 __node_traits::construct(__na, addressof(__h->__value_.second));
1038 __h.get_deleter().__second_constructed = true;
1039 return _STD::move(__h);
1040}
1041
Howard Hinnant73d21a42010-09-04 23:28:19 +00001042#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001043
1044template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1045template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001046inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001047void
1048unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1049 _InputIterator __last)
1050{
1051 for (; __first != __last; ++__first)
1052 __table_.__insert_unique(*__first);
1053}
1054
1055template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1056_Tp&
1057unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1058{
1059 iterator __i = find(__k);
1060 if (__i != end())
1061 return __i->second;
1062 __node_holder __h = __construct_node(__k);
1063 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1064 __h.release();
1065 return __r.first->second;
1066}
1067
Howard Hinnant73d21a42010-09-04 23:28:19 +00001068#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001069
1070template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1071_Tp&
1072unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1073{
1074 iterator __i = find(__k);
1075 if (__i != end())
1076 return __i->second;
1077 __node_holder __h = __construct_node(_STD::move(__k));
1078 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1079 __h.release();
1080 return __r.first->second;
1081}
1082
Howard Hinnant73d21a42010-09-04 23:28:19 +00001083#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001084
1085template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1086_Tp&
1087unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1088{
1089 iterator __i = find(__k);
1090#ifndef _LIBCPP_NO_EXCEPTIONS
1091 if (__i == end())
1092 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001093#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001094 return __i->second;
1095}
1096
1097template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1098const _Tp&
1099unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1100{
1101 const_iterator __i = find(__k);
1102#ifndef _LIBCPP_NO_EXCEPTIONS
1103 if (__i == end())
1104 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001105#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001106 return __i->second;
1107}
1108
1109template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001110inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001111void
1112swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1113 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1114{
1115 __x.swap(__y);
1116}
1117
1118template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1119bool
1120operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1121 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1122{
1123 if (__x.size() != __y.size())
1124 return false;
1125 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1126 const_iterator;
1127 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1128 __i != __ex; ++__i)
1129 {
1130 const_iterator __j = __y.find(__i->first);
1131 if (__j == __ey || !(*__i == *__j))
1132 return false;
1133 }
1134 return true;
1135}
1136
1137template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001138inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001139bool
1140operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1141 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1142{
1143 return !(__x == __y);
1144}
1145
1146template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1147 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001148class _LIBCPP_VISIBLE unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001149{
1150public:
1151 // types
1152 typedef _Key key_type;
1153 typedef _Tp mapped_type;
1154 typedef _Hash hasher;
1155 typedef _Pred key_equal;
1156 typedef _Alloc allocator_type;
1157 typedef pair<const key_type, mapped_type> value_type;
1158 typedef value_type& reference;
1159 typedef const value_type& const_reference;
1160
1161private:
1162 typedef pair<key_type, mapped_type> __value_type;
1163 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
1164 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
1165 typedef typename allocator_traits<allocator_type>::template
1166#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1167 rebind_alloc<__value_type>
1168#else
1169 rebind_alloc<__value_type>::other
1170#endif
1171 __allocator_type;
1172
1173 typedef __hash_table<__value_type, __hasher,
1174 __key_equal, __allocator_type> __table;
1175
1176 __table __table_;
1177
1178 typedef typename __table::__node_traits __node_traits;
1179 typedef typename __table::__node_allocator __node_allocator;
1180 typedef typename __table::__node __node;
1181 typedef __hash_map_node_destructor<__node_allocator> _D;
1182 typedef unique_ptr<__node, _D> __node_holder;
1183 typedef allocator_traits<allocator_type> __alloc_traits;
1184public:
1185 typedef typename __alloc_traits::pointer pointer;
1186 typedef typename __alloc_traits::const_pointer const_pointer;
1187 typedef typename __alloc_traits::size_type size_type;
1188 typedef typename __alloc_traits::difference_type difference_type;
1189
1190 typedef __hash_map_iterator<typename __table::iterator> iterator;
1191 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1192 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1193 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1194
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001195 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001196 unordered_multimap() {} // = default
1197 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1198 const key_equal& __eql = key_equal());
1199 unordered_multimap(size_type __n, const hasher& __hf,
1200 const key_equal& __eql,
1201 const allocator_type& __a);
1202 template <class _InputIterator>
1203 unordered_multimap(_InputIterator __first, _InputIterator __last);
1204 template <class _InputIterator>
1205 unordered_multimap(_InputIterator __first, _InputIterator __last,
1206 size_type __n, const hasher& __hf = hasher(),
1207 const key_equal& __eql = key_equal());
1208 template <class _InputIterator>
1209 unordered_multimap(_InputIterator __first, _InputIterator __last,
1210 size_type __n, const hasher& __hf,
1211 const key_equal& __eql,
1212 const allocator_type& __a);
1213 explicit unordered_multimap(const allocator_type& __a);
1214 unordered_multimap(const unordered_multimap& __u);
1215 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001216#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001217 unordered_multimap(unordered_multimap&& __u);
1218 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001219#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001220 unordered_multimap(initializer_list<value_type> __il);
1221 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1222 const hasher& __hf = hasher(),
1223 const key_equal& __eql = key_equal());
1224 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1225 const hasher& __hf, const key_equal& __eql,
1226 const allocator_type& __a);
1227 // ~unordered_multimap() = default;
1228 // unordered_multimap& operator=(const unordered_multimap& __u) = default;
Howard Hinnant73d21a42010-09-04 23:28:19 +00001229#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001230 unordered_multimap& operator=(unordered_multimap&& __u);
1231#endif
1232 unordered_multimap& operator=(initializer_list<value_type> __il);
1233
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001234 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001235 allocator_type get_allocator() const
1236 {return allocator_type(__table_.__node_alloc());}
1237
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001238 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001239 bool empty() const {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001240 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001241 size_type size() const {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001242 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001243 size_type max_size() const {return __table_.max_size();}
1244
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001245 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001246 iterator begin() {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001247 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001248 iterator end() {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001249 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001250 const_iterator begin() const {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001251 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001252 const_iterator end() const {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001253 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001254 const_iterator cbegin() const {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001255 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001256 const_iterator cend() const {return __table_.end();}
1257
Howard Hinnant73d21a42010-09-04 23:28:19 +00001258#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001259 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001260 iterator emplace()
1261 {return __table_.__emplace_multi();}
1262
1263 template <class _A0,
1264 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001265 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001266 iterator emplace(_A0&& __a0)
1267 {return __table_.__emplace_multi(_STD::forward<_A0>(__a0));}
1268
Howard Hinnant73d21a42010-09-04 23:28:19 +00001269#ifndef _LIBCPP_HAS_NO_VARIADICS
1270
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001271 template <class _A0, class... _Args,
1272 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1273 iterator emplace(_A0&& __a0, _Args&&... __args);
1274
Howard Hinnant73d21a42010-09-04 23:28:19 +00001275#endif // _LIBCPP_HAS_NO_VARIADICS
1276
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001277 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001278 iterator emplace_hint(const_iterator __p)
1279 {return __table_.__emplace_hint_multi(__p.__i_);}
1280
1281 template <class _A0,
1282 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001283 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001284 iterator emplace_hint(const_iterator __p, _A0&& __a0)
1285 {return __table_.__emplace_hint_multi(__p.__i_, _STD::forward<_A0>(__a0));}
1286
Howard Hinnant73d21a42010-09-04 23:28:19 +00001287#ifndef _LIBCPP_HAS_NO_VARIADICS
1288
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001289 template <class _A0, class... _Args,
1290 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1291 iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001292#endif // _LIBCPP_HAS_NO_VARIADICS
1293#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001294 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001295 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001296#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001297 template <class _P,
1298 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001299 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001300 iterator insert(_P&& __x)
1301 {return __table_.__insert_multi(_STD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001302#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001303 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001304 iterator insert(const_iterator __p, const value_type& __x)
1305 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001306#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001307 template <class _P,
1308 class = typename enable_if<is_convertible<_P, value_type>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001309 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001310 iterator insert(const_iterator __p, _P&& __x)
1311 {return __table_.__insert_multi(__p.__i_, _STD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001312#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001313 template <class _InputIterator>
1314 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001315 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001316 void insert(initializer_list<value_type> __il)
1317 {insert(__il.begin(), __il.end());}
1318
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001319 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001320 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001321 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001322 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001323 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001324 iterator erase(const_iterator __first, const_iterator __last)
1325 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001326 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001327 void clear() {__table_.clear();}
1328
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001329 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001330 void swap(unordered_multimap& __u) {__table_.swap(__u.__table_);}
1331
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001332 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001333 hasher hash_function() const
1334 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001336 key_equal key_eq() const
1337 {return __table_.key_eq().key_eq();}
1338
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001340 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001342 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001343 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001344 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001345 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001346 pair<iterator, iterator> equal_range(const key_type& __k)
1347 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001349 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1350 {return __table_.__equal_range_multi(__k);}
1351
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001353 size_type bucket_count() const {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001355 size_type max_bucket_count() const {return __table_.max_bucket_count();}
1356
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001357 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001358 size_type bucket_size(size_type __n) const
1359 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001361 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1362
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001363 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001364 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001365 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001366 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001367 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001368 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001369 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001370 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001371 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001372 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001373 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001374 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1375
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001376 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001377 float load_factor() const {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001378 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001379 float max_load_factor() const {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001380 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001381 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001382 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001383 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001384 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001385 void reserve(size_type __n) {__table_.reserve(__n);}
1386
1387private:
Howard Hinnant73d21a42010-09-04 23:28:19 +00001388#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001389 template <class _A0, class... _Args,
1390 class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1391 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
1392 template <class _A0,
1393 class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
1394 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001395#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001396};
1397
1398template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1399unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1400 size_type __n, const hasher& __hf, const key_equal& __eql)
1401 : __table_(__hf, __eql)
1402{
1403 __table_.rehash(__n);
1404}
1405
1406template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1407unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1408 size_type __n, const hasher& __hf, const key_equal& __eql,
1409 const allocator_type& __a)
1410 : __table_(__hf, __eql, __a)
1411{
1412 __table_.rehash(__n);
1413}
1414
1415template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1416template <class _InputIterator>
1417unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1418 _InputIterator __first, _InputIterator __last)
1419{
1420 insert(__first, __last);
1421}
1422
1423template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1424template <class _InputIterator>
1425unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1426 _InputIterator __first, _InputIterator __last, size_type __n,
1427 const hasher& __hf, const key_equal& __eql)
1428 : __table_(__hf, __eql)
1429{
1430 __table_.rehash(__n);
1431 insert(__first, __last);
1432}
1433
1434template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1435template <class _InputIterator>
1436unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1437 _InputIterator __first, _InputIterator __last, size_type __n,
1438 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1439 : __table_(__hf, __eql, __a)
1440{
1441 __table_.rehash(__n);
1442 insert(__first, __last);
1443}
1444
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001445template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001446inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001447unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1448 const allocator_type& __a)
1449 : __table_(__a)
1450{
1451}
1452
1453template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1454unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1455 const unordered_multimap& __u)
1456 : __table_(__u.__table_)
1457{
1458 __table_.rehash(__u.bucket_count());
1459 insert(__u.begin(), __u.end());
1460}
1461
1462template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1463unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1464 const unordered_multimap& __u, const allocator_type& __a)
1465 : __table_(__u.__table_, __a)
1466{
1467 __table_.rehash(__u.bucket_count());
1468 insert(__u.begin(), __u.end());
1469}
1470
Howard Hinnant73d21a42010-09-04 23:28:19 +00001471#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001472
1473template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001474inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001475unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1476 unordered_multimap&& __u)
1477 : __table_(_STD::move(__u.__table_))
1478{
1479}
1480
1481template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1482unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1483 unordered_multimap&& __u, const allocator_type& __a)
1484 : __table_(_STD::move(__u.__table_), __a)
1485{
1486 if (__a != __u.get_allocator())
1487 {
1488 iterator __i = __u.begin();
1489 while (__u.size() != 0)
1490{
1491 __table_.__insert_multi(
1492 _STD::move(__u.__table_.remove((__i++).__i_)->__value_)
1493 );
1494}
1495 }
1496}
1497
Howard Hinnant73d21a42010-09-04 23:28:19 +00001498#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001499
1500template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1501unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1502 initializer_list<value_type> __il)
1503{
1504 insert(__il.begin(), __il.end());
1505}
1506
1507template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1508unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1509 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1510 const key_equal& __eql)
1511 : __table_(__hf, __eql)
1512{
1513 __table_.rehash(__n);
1514 insert(__il.begin(), __il.end());
1515}
1516
1517template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1518unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1519 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1520 const key_equal& __eql, const allocator_type& __a)
1521 : __table_(__hf, __eql, __a)
1522{
1523 __table_.rehash(__n);
1524 insert(__il.begin(), __il.end());
1525}
1526
Howard Hinnant73d21a42010-09-04 23:28:19 +00001527#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001528
1529template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001530inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001531unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1532unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
1533{
1534 __table_ = _STD::move(__u.__table_);
1535 return *this;
1536}
1537
Howard Hinnant73d21a42010-09-04 23:28:19 +00001538#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001539
1540template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001541inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001542unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1543unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1544 initializer_list<value_type> __il)
1545{
1546 __table_.__assign_multi(__il.begin(), __il.end());
1547 return *this;
1548}
1549
Howard Hinnant73d21a42010-09-04 23:28:19 +00001550#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1551#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001552
1553template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1554template <class _A0, class... _Args,
1555 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1556 >
1557typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1558unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1559 _A0&& __a0, _Args&&... __args)
1560{
1561 __node_allocator& __na = __table_.__node_alloc();
1562 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1563 __node_traits::construct(__na, addressof(__h->__value_.first),
1564 _STD::forward<_A0>(__a0));
1565 __h.get_deleter().__first_constructed = true;
1566 __node_traits::construct(__na, addressof(__h->__value_.second),
1567 _STD::forward<_Args>(__args)...);
1568 __h.get_deleter().__second_constructed = true;
1569 return __h;
1570}
1571
Howard Hinnant73d21a42010-09-04 23:28:19 +00001572#endif // _LIBCPP_HAS_NO_VARIADICS
1573
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001574template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1575template <class _A0,
1576 class // = typename enable_if<is_convertible<_A0, value_type>::value>::type
1577 >
1578typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1579unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1580{
1581 __node_allocator& __na = __table_.__node_alloc();
1582 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1583 __node_traits::construct(__na, addressof(__h->__value_),
1584 _STD::forward<_A0>(__a0));
1585 __h.get_deleter().__first_constructed = true;
1586 __h.get_deleter().__second_constructed = true;
1587 return __h;
1588}
1589
Howard Hinnant73d21a42010-09-04 23:28:19 +00001590#ifndef _LIBCPP_HAS_NO_VARIADICS
1591
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001592template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1593template <class _A0, class... _Args,
1594 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1595 >
1596typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1597unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1598{
1599 __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1600 _STD::forward<_Args>(__args)...);
1601 iterator __r = __table_.__node_insert_multi(__h.get());
1602 __h.release();
1603 return __r;
1604}
1605
1606template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1607template <class _A0, class... _Args,
1608 class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1609 >
1610typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1611unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1612 const_iterator __p, _A0&& __a0, _Args&&... __args)
1613{
1614 __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1615 _STD::forward<_Args>(__args)...);
1616 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1617 __h.release();
1618 return __r;
1619}
1620
Howard Hinnant73d21a42010-09-04 23:28:19 +00001621#endif // _LIBCPP_HAS_NO_VARIADICS
1622#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001623
1624template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1625template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001626inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001627void
1628unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1629 _InputIterator __last)
1630{
1631 for (; __first != __last; ++__first)
1632 __table_.__insert_multi(*__first);
1633}
1634
1635template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001636inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001637void
1638swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1639 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1640{
1641 __x.swap(__y);
1642}
1643
1644template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1645bool
1646operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1647 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1648{
1649 if (__x.size() != __y.size())
1650 return false;
1651 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1652 const_iterator;
1653 typedef pair<const_iterator, const_iterator> _EqRng;
1654 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1655 {
1656 _EqRng __xeq = __x.equal_range(__i->first);
1657 _EqRng __yeq = __y.equal_range(__i->first);
1658 if (_STD::distance(__xeq.first, __xeq.second) !=
1659 _STD::distance(__yeq.first, __yeq.second) ||
1660 !_STD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1661 return false;
1662 __i = __xeq.second;
1663 }
1664 return true;
1665}
1666
1667template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001668inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001669bool
1670operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1671 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1672{
1673 return !(__x == __y);
1674}
1675
1676_LIBCPP_END_NAMESPACE_STD
1677
1678#endif // _LIBCPP_UNORDERED_MAP