blob: 56645e09b924d6a0a8090b14da8ae5fa99c7df78 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- unordered_map -----------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UNORDERED_MAP
12#define _LIBCPP_UNORDERED_MAP
13
14/*
15
16 unordered_map synopsis
17
18#include <initializer_list>
19
20namespace std
21{
22
23template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
24 class Alloc = allocator<pair<const Key, T>>>
25class unordered_map
26{
27public:
28 // types
29 typedef Key key_type;
30 typedef T mapped_type;
31 typedef Hash hasher;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef pair<const key_type, mapped_type> value_type;
35 typedef value_type& reference;
36 typedef const value_type& const_reference;
37 typedef typename allocator_traits<allocator_type>::pointer pointer;
38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
39 typedef typename allocator_traits<allocator_type>::size_type size_type;
40 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41
42 typedef /unspecified/ iterator;
43 typedef /unspecified/ const_iterator;
44 typedef /unspecified/ local_iterator;
45 typedef /unspecified/ const_local_iterator;
46
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000047 unordered_map()
48 noexcept(
49 is_nothrow_default_constructible<hasher>::value &&
50 is_nothrow_default_constructible<key_equal>::value &&
51 is_nothrow_default_constructible<allocator_type>::value);
52 explicit unordered_map(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000053 const key_equal& eql = key_equal(),
54 const allocator_type& a = allocator_type());
55 template <class InputIterator>
56 unordered_map(InputIterator f, InputIterator l,
57 size_type n = 0, const hasher& hf = hasher(),
58 const key_equal& eql = key_equal(),
59 const allocator_type& a = allocator_type());
60 explicit unordered_map(const allocator_type&);
61 unordered_map(const unordered_map&);
62 unordered_map(const unordered_map&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000063 unordered_map(unordered_map&&)
64 noexcept(
65 is_nothrow_move_constructible<hasher>::value &&
66 is_nothrow_move_constructible<key_equal>::value &&
67 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000068 unordered_map(unordered_map&&, const Allocator&);
69 unordered_map(initializer_list<value_type>, size_type n = 0,
70 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
71 const allocator_type& a = allocator_type());
72 ~unordered_map();
73 unordered_map& operator=(const unordered_map&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000074 unordered_map& operator=(unordered_map&&)
75 noexcept(
76 allocator_type::propagate_on_container_move_assignment::value &&
77 is_nothrow_move_assignable<allocator_type>::value &&
78 is_nothrow_move_assignable<hasher>::value &&
79 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000080 unordered_map& operator=(initializer_list<value_type>);
81
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000082 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000083
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000084 bool empty() const noexcept;
85 size_type size() const noexcept;
86 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000087
Howard Hinnant5f2f14c2011-06-04 18:54:24 +000088 iterator begin() noexcept;
89 iterator end() noexcept;
90 const_iterator begin() const noexcept;
91 const_iterator end() const noexcept;
92 const_iterator cbegin() const noexcept;
93 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000094
95 template <class... Args>
96 pair<iterator, bool> emplace(Args&&... args);
97 template <class... Args>
98 iterator emplace_hint(const_iterator position, Args&&... args);
99 pair<iterator, bool> insert(const value_type& obj);
100 template <class P>
101 pair<iterator, bool> insert(P&& obj);
102 iterator insert(const_iterator hint, const value_type& obj);
103 template <class P>
104 iterator insert(const_iterator hint, P&& obj);
105 template <class InputIterator>
106 void insert(InputIterator first, InputIterator last);
107 void insert(initializer_list<value_type>);
108
109 iterator erase(const_iterator position);
110 size_type erase(const key_type& k);
111 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000112 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000113
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000114 void swap(unordered_map&)
115 noexcept(
116 (!allocator_type::propagate_on_container_swap::value ||
117 __is_nothrow_swappable<allocator_type>::value) &&
118 __is_nothrow_swappable<hasher>::value &&
119 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120
121 hasher hash_function() const;
122 key_equal key_eq() const;
123
124 iterator find(const key_type& k);
125 const_iterator find(const key_type& k) const;
126 size_type count(const key_type& k) const;
127 pair<iterator, iterator> equal_range(const key_type& k);
128 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
129
130 mapped_type& operator[](const key_type& k);
131 mapped_type& operator[](key_type&& k);
132
133 mapped_type& at(const key_type& k);
134 const mapped_type& at(const key_type& k) const;
135
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
141
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
148
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
154};
155
156template <class Key, class T, class Hash, class Pred, class Alloc>
157 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000158 unordered_map<Key, T, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000160
161template <class Key, class T, class Hash, class Pred, class Alloc>
162 bool
163 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
164 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
165
166template <class Key, class T, class Hash, class Pred, class Alloc>
167 bool
168 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
169 const unordered_map<Key, T, Hash, Pred, Alloc>& y);
170
171template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
172 class Alloc = allocator<pair<const Key, T>>>
173class unordered_multimap
174{
175public:
176 // types
177 typedef Key key_type;
178 typedef T mapped_type;
179 typedef Hash hasher;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef pair<const key_type, mapped_type> value_type;
183 typedef value_type& reference;
184 typedef const value_type& const_reference;
185 typedef typename allocator_traits<allocator_type>::pointer pointer;
186 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
187 typedef typename allocator_traits<allocator_type>::size_type size_type;
188 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189
190 typedef /unspecified/ iterator;
191 typedef /unspecified/ const_iterator;
192 typedef /unspecified/ local_iterator;
193 typedef /unspecified/ const_local_iterator;
194
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000195 unordered_multimap()
196 noexcept(
197 is_nothrow_default_constructible<hasher>::value &&
198 is_nothrow_default_constructible<key_equal>::value &&
199 is_nothrow_default_constructible<allocator_type>::value);
200 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 const key_equal& eql = key_equal(),
202 const allocator_type& a = allocator_type());
203 template <class InputIterator>
204 unordered_multimap(InputIterator f, InputIterator l,
205 size_type n = 0, const hasher& hf = hasher(),
206 const key_equal& eql = key_equal(),
207 const allocator_type& a = allocator_type());
208 explicit unordered_multimap(const allocator_type&);
209 unordered_multimap(const unordered_multimap&);
210 unordered_multimap(const unordered_multimap&, const Allocator&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000211 unordered_multimap(unordered_multimap&&)
212 noexcept(
213 is_nothrow_move_constructible<hasher>::value &&
214 is_nothrow_move_constructible<key_equal>::value &&
215 is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000216 unordered_multimap(unordered_multimap&&, const Allocator&);
217 unordered_multimap(initializer_list<value_type>, size_type n = 0,
218 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
219 const allocator_type& a = allocator_type());
220 ~unordered_multimap();
221 unordered_multimap& operator=(const unordered_multimap&);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000222 unordered_multimap& operator=(unordered_multimap&&)
223 noexcept(
224 allocator_type::propagate_on_container_move_assignment::value &&
225 is_nothrow_move_assignable<allocator_type>::value &&
226 is_nothrow_move_assignable<hasher>::value &&
227 is_nothrow_move_assignable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000228 unordered_multimap& operator=(initializer_list<value_type>);
229
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000230 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000231
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000232 bool empty() const noexcept;
233 size_type size() const noexcept;
234 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000236 iterator begin() noexcept;
237 iterator end() noexcept;
238 const_iterator begin() const noexcept;
239 const_iterator end() const noexcept;
240 const_iterator cbegin() const noexcept;
241 const_iterator cend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000242
243 template <class... Args>
244 iterator emplace(Args&&... args);
245 template <class... Args>
246 iterator emplace_hint(const_iterator position, Args&&... args);
247 iterator insert(const value_type& obj);
248 template <class P>
249 iterator insert(P&& obj);
250 iterator insert(const_iterator hint, const value_type& obj);
251 template <class P>
252 iterator insert(const_iterator hint, P&& obj);
253 template <class InputIterator>
254 void insert(InputIterator first, InputIterator last);
255 void insert(initializer_list<value_type>);
256
257 iterator erase(const_iterator position);
258 size_type erase(const key_type& k);
259 iterator erase(const_iterator first, const_iterator last);
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000260 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000261
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000262 void swap(unordered_multimap&)
263 noexcept(
264 (!allocator_type::propagate_on_container_swap::value ||
265 __is_nothrow_swappable<allocator_type>::value) &&
266 __is_nothrow_swappable<hasher>::value &&
267 __is_nothrow_swappable<key_equal>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000268
269 hasher hash_function() const;
270 key_equal key_eq() const;
271
272 iterator find(const key_type& k);
273 const_iterator find(const key_type& k) const;
274 size_type count(const key_type& k) const;
275 pair<iterator, iterator> equal_range(const key_type& k);
276 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
277
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000278 size_type bucket_count() const noexcept;
279 size_type max_bucket_count() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000280
281 size_type bucket_size(size_type n) const;
282 size_type bucket(const key_type& k) const;
283
284 local_iterator begin(size_type n);
285 local_iterator end(size_type n);
286 const_local_iterator begin(size_type n) const;
287 const_local_iterator end(size_type n) const;
288 const_local_iterator cbegin(size_type n) const;
289 const_local_iterator cend(size_type n) const;
290
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000291 float load_factor() const noexcept;
292 float max_load_factor() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000293 void max_load_factor(float z);
294 void rehash(size_type n);
295 void reserve(size_type n);
296};
297
298template <class Key, class T, class Hash, class Pred, class Alloc>
299 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000300 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
301 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302
303template <class Key, class T, class Hash, class Pred, class Alloc>
304 bool
305 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
306 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
307
308template <class Key, class T, class Hash, class Pred, class Alloc>
309 bool
310 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
311 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
312
313} // std
314
315*/
316
317#include <__config>
318#include <__hash_table>
319#include <functional>
320#include <stdexcept>
321
Howard Hinnant08e17472011-10-17 20:05:10 +0000322#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000323#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000324#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000325
326_LIBCPP_BEGIN_NAMESPACE_STD
327
328template <class _Tp, class _Hash, bool = is_empty<_Hash>::value>
329class __unordered_map_hasher
330 : private _Hash
331{
332public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000333 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000334 __unordered_map_hasher()
335 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
336 : _Hash() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000337 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000338 __unordered_map_hasher(const _Hash& __h)
339 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
340 : _Hash(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000342 const _Hash& hash_function() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000343 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000344 size_t operator()(const _Tp& __x) const
345 {return static_cast<const _Hash&>(*this)(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000346 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000347 size_t operator()(const typename _Tp::first_type& __x) const
348 {return static_cast<const _Hash&>(*this)(__x);}
349};
350
351template <class _Tp, class _Hash>
352class __unordered_map_hasher<_Tp, _Hash, false>
353{
354 _Hash __hash_;
355public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000356 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000357 __unordered_map_hasher()
358 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
359 : __hash_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000361 __unordered_map_hasher(const _Hash& __h)
362 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
363 : __hash_(__h) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000364 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000365 const _Hash& hash_function() const _NOEXCEPT {return __hash_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000366 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000367 size_t operator()(const _Tp& __x) const
368 {return __hash_(__x.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000369 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000370 size_t operator()(const typename _Tp::first_type& __x) const
371 {return __hash_(__x);}
372};
373
374template <class _Tp, class _Pred, bool = is_empty<_Pred>::value>
375class __unordered_map_equal
376 : private _Pred
377{
378public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000379 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000380 __unordered_map_equal()
381 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
382 : _Pred() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000383 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000384 __unordered_map_equal(const _Pred& __p)
385 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
386 : _Pred(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000387 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000388 const _Pred& key_eq() const _NOEXCEPT {return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000390 bool operator()(const _Tp& __x, const _Tp& __y) const
391 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000393 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
394 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000395 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000396 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
397 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000398 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant324bb032010-08-22 00:02:43 +0000399 bool operator()(const typename _Tp::first_type& __x,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000400 const typename _Tp::first_type& __y) const
401 {return static_cast<const _Pred&>(*this)(__x, __y);}
402};
403
404template <class _Tp, class _Pred>
405class __unordered_map_equal<_Tp, _Pred, false>
406{
407 _Pred __pred_;
408public:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000409 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000410 __unordered_map_equal()
411 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
412 : __pred_() {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000414 __unordered_map_equal(const _Pred& __p)
415 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
416 : __pred_(__p) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000418 const _Pred& key_eq() const _NOEXCEPT {return __pred_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000420 bool operator()(const _Tp& __x, const _Tp& __y) const
421 {return __pred_(__x.first, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000422 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000423 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
424 {return __pred_(__x, __y.first);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000426 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
427 {return __pred_(__x.first, __y);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000428 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000429 bool operator()(const typename _Tp::first_type& __x,
430 const typename _Tp::first_type& __y) const
431 {return __pred_(__x, __y);}
432};
433
434template <class _Alloc>
435class __hash_map_node_destructor
436{
437 typedef _Alloc allocator_type;
438 typedef allocator_traits<allocator_type> __alloc_traits;
439 typedef typename __alloc_traits::value_type::value_type value_type;
440public:
441 typedef typename __alloc_traits::pointer pointer;
442private:
443 typedef typename value_type::first_type first_type;
444 typedef typename value_type::second_type second_type;
445
446 allocator_type& __na_;
447
448 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
449
450public:
451 bool __first_constructed;
452 bool __second_constructed;
453
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000454 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000455 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000456 : __na_(__na),
457 __first_constructed(false),
458 __second_constructed(false)
459 {}
460
Howard Hinnant73d21a42010-09-04 23:28:19 +0000461#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000462 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000463 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000464 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000465 : __na_(__x.__na_),
466 __first_constructed(__x.__value_constructed),
467 __second_constructed(__x.__value_constructed)
468 {
469 __x.__value_constructed = false;
470 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000471#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000472 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000473 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
474 : __na_(__x.__na_),
475 __first_constructed(__x.__value_constructed),
476 __second_constructed(__x.__value_constructed)
477 {
478 const_cast<bool&>(__x.__value_constructed) = false;
479 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000480#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000481
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000482 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000483 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000484 {
485 if (__second_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000486 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000487 if (__first_constructed)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000488 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000489 if (__p)
490 __alloc_traits::deallocate(__na_, __p, 1);
491 }
492};
493
494template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000495class _LIBCPP_VISIBLE __hash_map_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000496{
497 _HashIterator __i_;
498
499 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
500 typedef const typename _HashIterator::value_type::first_type key_type;
501 typedef typename _HashIterator::value_type::second_type mapped_type;
502public:
503 typedef forward_iterator_tag iterator_category;
504 typedef pair<key_type, mapped_type> value_type;
505 typedef typename _HashIterator::difference_type difference_type;
506 typedef value_type& reference;
507 typedef typename __pointer_traits::template
508#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
509 rebind<value_type>
510#else
511 rebind<value_type>::other
512#endif
513 pointer;
514
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000515 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000516 __hash_map_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000517
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000518 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000519 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000520
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000522 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000524 pointer operator->() const {return (pointer)__i_.operator->();}
525
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000526 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527 __hash_map_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000528 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000529 __hash_map_iterator operator++(int)
530 {
531 __hash_map_iterator __t(*this);
532 ++(*this);
533 return __t;
534 }
535
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000536 friend _LIBCPP_INLINE_VISIBILITY
537 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000538 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000539 friend _LIBCPP_INLINE_VISIBILITY
540 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000541 {return __x.__i_ != __y.__i_;}
542
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000543 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
544 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
545 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
546 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
547 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000548};
549
550template <class _HashIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000551class _LIBCPP_VISIBLE __hash_map_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000552{
553 _HashIterator __i_;
554
555 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
556 typedef const typename _HashIterator::value_type::first_type key_type;
557 typedef typename _HashIterator::value_type::second_type mapped_type;
558public:
559 typedef forward_iterator_tag iterator_category;
560 typedef pair<key_type, mapped_type> value_type;
561 typedef typename _HashIterator::difference_type difference_type;
562 typedef const value_type& reference;
563 typedef typename __pointer_traits::template
564#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant099084d2011-07-23 16:14:35 +0000565 rebind<const value_type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000566#else
Howard Hinnant099084d2011-07-23 16:14:35 +0000567 rebind<const value_type>::other
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568#endif
569 pointer;
570
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000571 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000572 __hash_map_const_iterator() _NOEXCEPT {}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000573
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000575 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000577 __hash_map_const_iterator(
578 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000579 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000580 : __i_(__i.__i_) {}
581
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 reference operator*() const {return *operator->();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000585 pointer operator->() const {return (pointer)__i_.operator->();}
586
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000588 __hash_map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000590 __hash_map_const_iterator operator++(int)
591 {
592 __hash_map_const_iterator __t(*this);
593 ++(*this);
594 return __t;
595 }
596
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000597 friend _LIBCPP_INLINE_VISIBILITY
598 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000599 {return __x.__i_ == __y.__i_;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000600 friend _LIBCPP_INLINE_VISIBILITY
601 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000602 {return __x.__i_ != __y.__i_;}
603
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000604 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map;
605 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap;
606 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator;
607 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000608};
609
610template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
611 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000612class _LIBCPP_VISIBLE unordered_map
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000613{
614public:
615 // types
616 typedef _Key key_type;
617 typedef _Tp mapped_type;
618 typedef _Hash hasher;
619 typedef _Pred key_equal;
620 typedef _Alloc allocator_type;
621 typedef pair<const key_type, mapped_type> value_type;
622 typedef value_type& reference;
623 typedef const value_type& const_reference;
624
625private:
626 typedef pair<key_type, mapped_type> __value_type;
627 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
628 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
629 typedef typename allocator_traits<allocator_type>::template
630#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
631 rebind_alloc<__value_type>
632#else
633 rebind_alloc<__value_type>::other
634#endif
635 __allocator_type;
636
637 typedef __hash_table<__value_type, __hasher,
638 __key_equal, __allocator_type> __table;
639
640 __table __table_;
641
642 typedef typename __table::__node_pointer __node_pointer;
643 typedef typename __table::__node_const_pointer __node_const_pointer;
644 typedef typename __table::__node_traits __node_traits;
645 typedef typename __table::__node_allocator __node_allocator;
646 typedef typename __table::__node __node;
647 typedef __hash_map_node_destructor<__node_allocator> _D;
648 typedef unique_ptr<__node, _D> __node_holder;
649 typedef allocator_traits<allocator_type> __alloc_traits;
650public:
651 typedef typename __alloc_traits::pointer pointer;
652 typedef typename __alloc_traits::const_pointer const_pointer;
653 typedef typename __alloc_traits::size_type size_type;
654 typedef typename __alloc_traits::difference_type difference_type;
655
656 typedef __hash_map_iterator<typename __table::iterator> iterator;
657 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
658 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
659 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
660
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000661 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000662 unordered_map()
663 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
664 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000665 explicit unordered_map(size_type __n, const hasher& __hf = hasher(),
666 const key_equal& __eql = key_equal());
667 unordered_map(size_type __n, const hasher& __hf,
668 const key_equal& __eql,
669 const allocator_type& __a);
670 template <class _InputIterator>
671 unordered_map(_InputIterator __first, _InputIterator __last);
672 template <class _InputIterator>
673 unordered_map(_InputIterator __first, _InputIterator __last,
674 size_type __n, const hasher& __hf = hasher(),
675 const key_equal& __eql = key_equal());
676 template <class _InputIterator>
677 unordered_map(_InputIterator __first, _InputIterator __last,
678 size_type __n, const hasher& __hf,
679 const key_equal& __eql,
680 const allocator_type& __a);
681 explicit unordered_map(const allocator_type& __a);
682 unordered_map(const unordered_map& __u);
683 unordered_map(const unordered_map& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000684#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000685 unordered_map(unordered_map&& __u)
686 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000687 unordered_map(unordered_map&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000688#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000689#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000690 unordered_map(initializer_list<value_type> __il);
691 unordered_map(initializer_list<value_type> __il, size_type __n,
692 const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
693 unordered_map(initializer_list<value_type> __il, size_type __n,
694 const hasher& __hf, const key_equal& __eql,
695 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000696#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000697 // ~unordered_map() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +0000698 _LIBCPP_INLINE_VISIBILITY
699 unordered_map& operator=(const unordered_map& __u)
700 {
701 __table_ = __u.__table_;
702 return *this;
703 }
Howard Hinnant73d21a42010-09-04 23:28:19 +0000704#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000705 unordered_map& operator=(unordered_map&& __u)
706 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000707#endif
Howard Hinnante3e32912011-08-12 21:56:02 +0000708#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000709 unordered_map& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +0000710#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
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 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000714 {return allocator_type(__table_.__node_alloc());}
715
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000716 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000717 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000719 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000721 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000722
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000723 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000724 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000726 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000727 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000728 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000729 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000730 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000732 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000733 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000734 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000735
Howard Hinnant73d21a42010-09-04 23:28:19 +0000736#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000737 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000738 pair<iterator, bool> emplace()
739 {return __table_.__emplace_unique();}
740
741 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000742 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000743 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000744 pair<iterator, bool> emplace(_A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000745 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000746
Howard Hinnant73d21a42010-09-04 23:28:19 +0000747#ifndef _LIBCPP_HAS_NO_VARIADICS
748
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000749 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000750 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000751 pair<iterator, bool> emplace(_A0&& __a0, _Args&&... __args);
752
Howard Hinnant73d21a42010-09-04 23:28:19 +0000753#endif // _LIBCPP_HAS_NO_VARIADICS
754
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000755 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000756 iterator emplace_hint(const_iterator)
757 {return __table_.__emplace_unique().first;}
758
759 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000760 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000761 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000762 iterator emplace_hint(const_iterator, _A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000763 {return __table_.__emplace_unique(_VSTD::forward<_A0>(__a0)).first;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000764
Howard Hinnant73d21a42010-09-04 23:28:19 +0000765#ifndef _LIBCPP_HAS_NO_VARIADICS
766
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000767 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000768 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000769 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000770 iterator emplace_hint(const_iterator, _A0&& __a0, _Args&&... __args)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000771 {return emplace(_VSTD::forward<_A0>(__a0),
772 _VSTD::forward<_Args>(__args)...).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000773#endif // _LIBCPP_HAS_NO_VARIADICS
774#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000776 pair<iterator, bool> insert(const value_type& __x)
777 {return __table_.__insert_unique(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000778#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000779 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000780 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000781 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000782 pair<iterator, bool> insert(_P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000783 {return __table_.__insert_unique(_VSTD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000784#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000786 iterator insert(const_iterator, const value_type& __x)
787 {return insert(__x).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000788#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000789 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000790 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000792 iterator insert(const_iterator, _P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000793 {return insert(_VSTD::forward<_P>(__x)).first;}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000794#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000795 template <class _InputIterator>
796 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000797#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000798 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000799 void insert(initializer_list<value_type> __il)
800 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000801#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000802
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000804 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000806 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000807 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000808 iterator erase(const_iterator __first, const_iterator __last)
809 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000810 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000811 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000812
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000813 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000814 void swap(unordered_map& __u)
815 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
816 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000817
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000819 hasher hash_function() const
820 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000822 key_equal key_eq() const
823 {return __table_.key_eq().key_eq();}
824
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000825 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000826 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000827 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000828 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000829 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000830 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000831 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000832 pair<iterator, iterator> equal_range(const key_type& __k)
833 {return __table_.__equal_range_unique(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000834 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000835 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
836 {return __table_.__equal_range_unique(__k);}
837
838 mapped_type& operator[](const key_type& __k);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000839#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000840 mapped_type& operator[](key_type&& __k);
841#endif
842
843 mapped_type& at(const key_type& __k);
844 const mapped_type& at(const key_type& __k) const;
845
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000846 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000847 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000849 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000850
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000851 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000852 size_type bucket_size(size_type __n) const
853 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000855 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
856
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000857 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000858 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000860 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000862 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000864 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000865 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000866 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000867 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000868 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
869
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000870 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000871 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000872 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000873 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000874 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000875 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000876 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000877 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000878 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000879 void reserve(size_type __n) {__table_.reserve(__n);}
880
881private:
Howard Hinnant73d21a42010-09-04 23:28:19 +0000882#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
883#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000884 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000885 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000886 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000887#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000888 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +0000889 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000890 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000891#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000892 __node_holder __construct_node(const key_type& __k);
893#endif
894};
895
896template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
897unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
898 size_type __n, const hasher& __hf, const key_equal& __eql)
899 : __table_(__hf, __eql)
900{
901 __table_.rehash(__n);
902}
903
904template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
905unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
906 size_type __n, const hasher& __hf, const key_equal& __eql,
907 const allocator_type& __a)
908 : __table_(__hf, __eql, __a)
909{
910 __table_.rehash(__n);
911}
912
913template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000914inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000915unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
916 const allocator_type& __a)
917 : __table_(__a)
918{
919}
920
921template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
922template <class _InputIterator>
923unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
924 _InputIterator __first, _InputIterator __last)
925{
926 insert(__first, __last);
927}
928
929template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
930template <class _InputIterator>
931unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
932 _InputIterator __first, _InputIterator __last, size_type __n,
933 const hasher& __hf, const key_equal& __eql)
934 : __table_(__hf, __eql)
935{
936 __table_.rehash(__n);
937 insert(__first, __last);
938}
939
940template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
941template <class _InputIterator>
942unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
943 _InputIterator __first, _InputIterator __last, size_type __n,
944 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
945 : __table_(__hf, __eql, __a)
946{
947 __table_.rehash(__n);
948 insert(__first, __last);
949}
950
951template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
952unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
953 const unordered_map& __u)
954 : __table_(__u.__table_)
955{
956 __table_.rehash(__u.bucket_count());
957 insert(__u.begin(), __u.end());
958}
959
960template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
961unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
962 const unordered_map& __u, const allocator_type& __a)
963 : __table_(__u.__table_, __a)
964{
965 __table_.rehash(__u.bucket_count());
966 insert(__u.begin(), __u.end());
967}
968
Howard Hinnant73d21a42010-09-04 23:28:19 +0000969#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000970
971template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000972inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000973unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
974 unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +0000975 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000976 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000977{
978}
979
980template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
981unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
982 unordered_map&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +0000983 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000984{
985 if (__a != __u.get_allocator())
986 {
987 iterator __i = __u.begin();
988 while (__u.size() != 0)
989 __table_.__insert_unique(
Howard Hinnant0949eed2011-06-30 21:18:19 +0000990 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000991 );
992 }
993}
994
Howard Hinnant73d21a42010-09-04 23:28:19 +0000995#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000996
Howard Hinnante3e32912011-08-12 21:56:02 +0000997#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
998
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000999template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1000unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1001 initializer_list<value_type> __il)
1002{
1003 insert(__il.begin(), __il.end());
1004}
1005
1006template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1007unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1008 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1009 const key_equal& __eql)
1010 : __table_(__hf, __eql)
1011{
1012 __table_.rehash(__n);
1013 insert(__il.begin(), __il.end());
1014}
1015
1016template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1017unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1018 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1019 const key_equal& __eql, const allocator_type& __a)
1020 : __table_(__hf, __eql, __a)
1021{
1022 __table_.rehash(__n);
1023 insert(__il.begin(), __il.end());
1024}
1025
Howard Hinnante3e32912011-08-12 21:56:02 +00001026#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1027
Howard Hinnant73d21a42010-09-04 23:28:19 +00001028#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001029
1030template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001031inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001032unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1033unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001034 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001035{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001036 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001037 return *this;
1038}
1039
Howard Hinnant73d21a42010-09-04 23:28:19 +00001040#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001041
Howard Hinnante3e32912011-08-12 21:56:02 +00001042#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1043
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001044template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001045inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001046unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1047unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1048 initializer_list<value_type> __il)
1049{
1050 __table_.__assign_unique(__il.begin(), __il.end());
1051 return *this;
1052}
1053
Howard Hinnante3e32912011-08-12 21:56:02 +00001054#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1055
Howard Hinnant73d21a42010-09-04 23:28:19 +00001056#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1057#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001058
1059template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1060template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001061 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001062 >
1063typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1064unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0,
1065 _Args&&... __args)
1066{
1067 __node_allocator& __na = __table_.__node_alloc();
1068 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001069 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1070 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001071 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001072 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second),
1073 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001074 __h.get_deleter().__second_constructed = true;
1075 return __h;
1076}
1077
Howard Hinnant73d21a42010-09-04 23:28:19 +00001078#endif // _LIBCPP_HAS_NO_VARIADICS
1079
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001080template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1081template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001082 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001083 >
1084typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1085unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1086{
1087 __node_allocator& __na = __table_.__node_alloc();
1088 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001089 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1090 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001091 __h.get_deleter().__first_constructed = true;
1092 __h.get_deleter().__second_constructed = true;
1093 return __h;
1094}
1095
Howard Hinnant73d21a42010-09-04 23:28:19 +00001096#ifndef _LIBCPP_HAS_NO_VARIADICS
1097
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001098template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1099template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001100 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001101 >
1102pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool>
1103unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1104{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001105 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1106 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001107 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1108 if (__r.second)
1109 __h.release();
1110 return __r;
1111}
1112
Howard Hinnant73d21a42010-09-04 23:28:19 +00001113#endif // _LIBCPP_HAS_NO_VARIADICS
1114#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001115
1116template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1117typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1118unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
1119{
1120 __node_allocator& __na = __table_.__node_alloc();
1121 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001122 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001123 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001124 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001125 __h.get_deleter().__second_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001126 return _VSTD::move(__h);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001127}
1128
Howard Hinnant73d21a42010-09-04 23:28:19 +00001129#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001130
1131template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1132template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001133inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001134void
1135unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1136 _InputIterator __last)
1137{
1138 for (; __first != __last; ++__first)
1139 __table_.__insert_unique(*__first);
1140}
1141
1142template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1143_Tp&
1144unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
1145{
1146 iterator __i = find(__k);
1147 if (__i != end())
1148 return __i->second;
1149 __node_holder __h = __construct_node(__k);
1150 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1151 __h.release();
1152 return __r.first->second;
1153}
1154
Howard Hinnant73d21a42010-09-04 23:28:19 +00001155#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001156
1157template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1158_Tp&
1159unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k)
1160{
1161 iterator __i = find(__k);
1162 if (__i != end())
1163 return __i->second;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001164 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001165 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
1166 __h.release();
1167 return __r.first->second;
1168}
1169
Howard Hinnant73d21a42010-09-04 23:28:19 +00001170#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001171
1172template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1173_Tp&
1174unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k)
1175{
1176 iterator __i = find(__k);
1177#ifndef _LIBCPP_NO_EXCEPTIONS
1178 if (__i == end())
1179 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001180#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001181 return __i->second;
1182}
1183
1184template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1185const _Tp&
1186unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const
1187{
1188 const_iterator __i = find(__k);
1189#ifndef _LIBCPP_NO_EXCEPTIONS
1190 if (__i == end())
1191 throw out_of_range("unordered_map::at: key not found");
Howard Hinnant324bb032010-08-22 00:02:43 +00001192#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001193 return __i->second;
1194}
1195
1196template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001197inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001198void
1199swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1200 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001201 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001202{
1203 __x.swap(__y);
1204}
1205
1206template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1207bool
1208operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1209 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1210{
1211 if (__x.size() != __y.size())
1212 return false;
1213 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1214 const_iterator;
1215 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
1216 __i != __ex; ++__i)
1217 {
1218 const_iterator __j = __y.find(__i->first);
1219 if (__j == __ey || !(*__i == *__j))
1220 return false;
1221 }
1222 return true;
1223}
1224
1225template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001226inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001227bool
1228operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1229 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1230{
1231 return !(__x == __y);
1232}
1233
1234template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
1235 class _Alloc = allocator<pair<const _Key, _Tp> > >
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001236class _LIBCPP_VISIBLE unordered_multimap
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001237{
1238public:
1239 // types
1240 typedef _Key key_type;
1241 typedef _Tp mapped_type;
1242 typedef _Hash hasher;
1243 typedef _Pred key_equal;
1244 typedef _Alloc allocator_type;
1245 typedef pair<const key_type, mapped_type> value_type;
1246 typedef value_type& reference;
1247 typedef const value_type& const_reference;
1248
1249private:
1250 typedef pair<key_type, mapped_type> __value_type;
1251 typedef __unordered_map_hasher<__value_type, hasher> __hasher;
1252 typedef __unordered_map_equal<__value_type, key_equal> __key_equal;
1253 typedef typename allocator_traits<allocator_type>::template
1254#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1255 rebind_alloc<__value_type>
1256#else
1257 rebind_alloc<__value_type>::other
1258#endif
1259 __allocator_type;
1260
1261 typedef __hash_table<__value_type, __hasher,
1262 __key_equal, __allocator_type> __table;
1263
1264 __table __table_;
1265
1266 typedef typename __table::__node_traits __node_traits;
1267 typedef typename __table::__node_allocator __node_allocator;
1268 typedef typename __table::__node __node;
1269 typedef __hash_map_node_destructor<__node_allocator> _D;
1270 typedef unique_ptr<__node, _D> __node_holder;
1271 typedef allocator_traits<allocator_type> __alloc_traits;
1272public:
1273 typedef typename __alloc_traits::pointer pointer;
1274 typedef typename __alloc_traits::const_pointer const_pointer;
1275 typedef typename __alloc_traits::size_type size_type;
1276 typedef typename __alloc_traits::difference_type difference_type;
1277
1278 typedef __hash_map_iterator<typename __table::iterator> iterator;
1279 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
1280 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
1281 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
1282
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001283 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001284 unordered_multimap()
1285 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1286 {} // = default;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001287 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(),
1288 const key_equal& __eql = key_equal());
1289 unordered_multimap(size_type __n, const hasher& __hf,
1290 const key_equal& __eql,
1291 const allocator_type& __a);
1292 template <class _InputIterator>
1293 unordered_multimap(_InputIterator __first, _InputIterator __last);
1294 template <class _InputIterator>
1295 unordered_multimap(_InputIterator __first, _InputIterator __last,
1296 size_type __n, const hasher& __hf = hasher(),
1297 const key_equal& __eql = key_equal());
1298 template <class _InputIterator>
1299 unordered_multimap(_InputIterator __first, _InputIterator __last,
1300 size_type __n, const hasher& __hf,
1301 const key_equal& __eql,
1302 const allocator_type& __a);
1303 explicit unordered_multimap(const allocator_type& __a);
1304 unordered_multimap(const unordered_multimap& __u);
1305 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001306#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001307 unordered_multimap(unordered_multimap&& __u)
1308 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001309 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001310#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00001311#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001312 unordered_multimap(initializer_list<value_type> __il);
1313 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1314 const hasher& __hf = hasher(),
1315 const key_equal& __eql = key_equal());
1316 unordered_multimap(initializer_list<value_type> __il, size_type __n,
1317 const hasher& __hf, const key_equal& __eql,
1318 const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00001319#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001320 // ~unordered_multimap() = default;
Howard Hinnant61aa6012011-07-01 19:24:36 +00001321 _LIBCPP_INLINE_VISIBILITY
1322 unordered_multimap& operator=(const unordered_multimap& __u)
1323 {
1324 __table_ = __u.__table_;
1325 return *this;
1326 }
Howard Hinnant73d21a42010-09-04 23:28:19 +00001327#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001328 unordered_multimap& operator=(unordered_multimap&& __u)
1329 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001330#endif
Howard Hinnante3e32912011-08-12 21:56:02 +00001331#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001332 unordered_multimap& operator=(initializer_list<value_type> __il);
Howard Hinnante3e32912011-08-12 21:56:02 +00001333#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001334
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001336 allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001337 {return allocator_type(__table_.__node_alloc());}
1338
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001339 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001340 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001341 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001342 size_type size() const _NOEXCEPT {return __table_.size();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001343 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001344 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001345
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001346 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001347 iterator begin() _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001349 iterator end() _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001350 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001351 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001353 const_iterator end() const _NOEXCEPT {return __table_.end();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001354 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001355 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001356 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001357 const_iterator cend() const _NOEXCEPT {return __table_.end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001358
Howard Hinnant73d21a42010-09-04 23:28:19 +00001359#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001361 iterator emplace()
1362 {return __table_.__emplace_multi();}
1363
1364 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001365 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001366 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001367 iterator emplace(_A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001368 {return __table_.__emplace_multi(_VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001369
Howard Hinnant73d21a42010-09-04 23:28:19 +00001370#ifndef _LIBCPP_HAS_NO_VARIADICS
1371
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001372 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001373 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001374 iterator emplace(_A0&& __a0, _Args&&... __args);
1375
Howard Hinnant73d21a42010-09-04 23:28:19 +00001376#endif // _LIBCPP_HAS_NO_VARIADICS
1377
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001378 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001379 iterator emplace_hint(const_iterator __p)
1380 {return __table_.__emplace_hint_multi(__p.__i_);}
1381
1382 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001383 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001384 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001385 iterator emplace_hint(const_iterator __p, _A0&& __a0)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001386 {return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001387
Howard Hinnant73d21a42010-09-04 23:28:19 +00001388#ifndef _LIBCPP_HAS_NO_VARIADICS
1389
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001390 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001391 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001392 iterator emplace_hint(const_iterator __p, _A0&& __a0, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001393#endif // _LIBCPP_HAS_NO_VARIADICS
1394#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001395 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001396 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001397#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001398 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001399 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001400 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001401 iterator insert(_P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001402 {return __table_.__insert_multi(_VSTD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001403#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001405 iterator insert(const_iterator __p, const value_type& __x)
1406 {return __table_.__insert_multi(__p.__i_, __x);}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001407#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001408 template <class _P,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001409 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001410 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001411 iterator insert(const_iterator __p, _P&& __x)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001412 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_P>(__x));}
Howard Hinnant73d21a42010-09-04 23:28:19 +00001413#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001414 template <class _InputIterator>
1415 void insert(_InputIterator __first, _InputIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00001416#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001418 void insert(initializer_list<value_type> __il)
1419 {insert(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00001420#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001421
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001422 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001423 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001424 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001425 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001426 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001427 iterator erase(const_iterator __first, const_iterator __last)
1428 {return __table_.erase(__first.__i_, __last.__i_);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001429 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001430 void clear() _NOEXCEPT {__table_.clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001431
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001432 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001433 void swap(unordered_multimap& __u)
1434 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1435 {__table_.swap(__u.__table_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001436
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001437 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001438 hasher hash_function() const
1439 {return __table_.hash_function().hash_function();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001440 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001441 key_equal key_eq() const
1442 {return __table_.key_eq().key_eq();}
1443
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001444 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001445 iterator find(const key_type& __k) {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001446 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001447 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001448 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001449 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001450 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001451 pair<iterator, iterator> equal_range(const key_type& __k)
1452 {return __table_.__equal_range_multi(__k);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001453 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001454 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1455 {return __table_.__equal_range_multi(__k);}
1456
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001458 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001460 size_type max_bucket_count() const _NOEXCEPT
1461 {return __table_.max_bucket_count();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001462
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001464 size_type bucket_size(size_type __n) const
1465 {return __table_.bucket_size(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001467 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1468
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001469 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001470 local_iterator begin(size_type __n) {return __table_.begin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001472 local_iterator end(size_type __n) {return __table_.end(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001473 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001474 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001475 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001476 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001477 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001478 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001479 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001480 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1481
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001482 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001483 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001484 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001485 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001486 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001487 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001488 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001489 void rehash(size_type __n) {__table_.rehash(__n);}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001490 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001491 void reserve(size_type __n) {__table_.reserve(__n);}
1492
1493private:
Howard Hinnant73d21a42010-09-04 23:28:19 +00001494#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001495 template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001496 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001497 __node_holder __construct_node(_A0&& __a0, _Args&&... __args);
1498 template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001499 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001500 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001501#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001502};
1503
1504template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1505unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1506 size_type __n, const hasher& __hf, const key_equal& __eql)
1507 : __table_(__hf, __eql)
1508{
1509 __table_.rehash(__n);
1510}
1511
1512template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1513unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1514 size_type __n, const hasher& __hf, const key_equal& __eql,
1515 const allocator_type& __a)
1516 : __table_(__hf, __eql, __a)
1517{
1518 __table_.rehash(__n);
1519}
1520
1521template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1522template <class _InputIterator>
1523unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1524 _InputIterator __first, _InputIterator __last)
1525{
1526 insert(__first, __last);
1527}
1528
1529template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1530template <class _InputIterator>
1531unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1532 _InputIterator __first, _InputIterator __last, size_type __n,
1533 const hasher& __hf, const key_equal& __eql)
1534 : __table_(__hf, __eql)
1535{
1536 __table_.rehash(__n);
1537 insert(__first, __last);
1538}
1539
1540template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1541template <class _InputIterator>
1542unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1543 _InputIterator __first, _InputIterator __last, size_type __n,
1544 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1545 : __table_(__hf, __eql, __a)
1546{
1547 __table_.rehash(__n);
1548 insert(__first, __last);
1549}
1550
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001551template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001552inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001553unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1554 const allocator_type& __a)
1555 : __table_(__a)
1556{
1557}
1558
1559template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1560unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1561 const unordered_multimap& __u)
1562 : __table_(__u.__table_)
1563{
1564 __table_.rehash(__u.bucket_count());
1565 insert(__u.begin(), __u.end());
1566}
1567
1568template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1569unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1570 const unordered_multimap& __u, const allocator_type& __a)
1571 : __table_(__u.__table_, __a)
1572{
1573 __table_.rehash(__u.bucket_count());
1574 insert(__u.begin(), __u.end());
1575}
1576
Howard Hinnant73d21a42010-09-04 23:28:19 +00001577#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001578
1579template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001580inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001581unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1582 unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001583 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001584 : __table_(_VSTD::move(__u.__table_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001585{
1586}
1587
1588template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1589unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1590 unordered_multimap&& __u, const allocator_type& __a)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001591 : __table_(_VSTD::move(__u.__table_), __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001592{
1593 if (__a != __u.get_allocator())
1594 {
1595 iterator __i = __u.begin();
1596 while (__u.size() != 0)
1597{
1598 __table_.__insert_multi(
Howard Hinnant0949eed2011-06-30 21:18:19 +00001599 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001600 );
1601}
1602 }
1603}
1604
Howard Hinnant73d21a42010-09-04 23:28:19 +00001605#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001606
Howard Hinnante3e32912011-08-12 21:56:02 +00001607#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1608
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001609template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1610unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1611 initializer_list<value_type> __il)
1612{
1613 insert(__il.begin(), __il.end());
1614}
1615
1616template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1617unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1618 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1619 const key_equal& __eql)
1620 : __table_(__hf, __eql)
1621{
1622 __table_.rehash(__n);
1623 insert(__il.begin(), __il.end());
1624}
1625
1626template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1627unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
1628 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1629 const key_equal& __eql, const allocator_type& __a)
1630 : __table_(__hf, __eql, __a)
1631{
1632 __table_.rehash(__n);
1633 insert(__il.begin(), __il.end());
1634}
1635
Howard Hinnante3e32912011-08-12 21:56:02 +00001636#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1637
Howard Hinnant73d21a42010-09-04 23:28:19 +00001638#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001639
1640template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001641inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001642unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1643unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001644 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001645{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001646 __table_ = _VSTD::move(__u.__table_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001647 return *this;
1648}
1649
Howard Hinnant73d21a42010-09-04 23:28:19 +00001650#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001651
Howard Hinnante3e32912011-08-12 21:56:02 +00001652#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1653
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001654template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001655inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001656unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
1657unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(
1658 initializer_list<value_type> __il)
1659{
1660 __table_.__assign_multi(__il.begin(), __il.end());
1661 return *this;
1662}
1663
Howard Hinnante3e32912011-08-12 21:56:02 +00001664#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1665
Howard Hinnant73d21a42010-09-04 23:28:19 +00001666#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1667#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001668
1669template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1670template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001671 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001672 >
1673typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1674unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(
1675 _A0&& __a0, _Args&&... __args)
1676{
1677 __node_allocator& __na = __table_.__node_alloc();
1678 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001679 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first),
1680 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001681 __h.get_deleter().__first_constructed = true;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001682 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second),
1683 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001684 __h.get_deleter().__second_constructed = true;
1685 return __h;
1686}
1687
Howard Hinnant73d21a42010-09-04 23:28:19 +00001688#endif // _LIBCPP_HAS_NO_VARIADICS
1689
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001690template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1691template <class _A0,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001692 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001693 >
1694typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1695unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0)
1696{
1697 __node_allocator& __na = __table_.__node_alloc();
1698 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001699 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1700 _VSTD::forward<_A0>(__a0));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001701 __h.get_deleter().__first_constructed = true;
1702 __h.get_deleter().__second_constructed = true;
1703 return __h;
1704}
1705
Howard Hinnant73d21a42010-09-04 23:28:19 +00001706#ifndef _LIBCPP_HAS_NO_VARIADICS
1707
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001708template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1709template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001710 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001711 >
1712typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1713unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_A0&& __a0, _Args&&... __args)
1714{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001715 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1716 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001717 iterator __r = __table_.__node_insert_multi(__h.get());
1718 __h.release();
1719 return __r;
1720}
1721
1722template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1723template <class _A0, class... _Args,
Howard Hinnant7604fea2011-06-19 21:45:00 +00001724 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001725 >
1726typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator
1727unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint(
1728 const_iterator __p, _A0&& __a0, _Args&&... __args)
1729{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001730 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1731 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001732 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get());
1733 __h.release();
1734 return __r;
1735}
1736
Howard Hinnant73d21a42010-09-04 23:28:19 +00001737#endif // _LIBCPP_HAS_NO_VARIADICS
1738#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001739
1740template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1741template <class _InputIterator>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001742inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001743void
1744unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1745 _InputIterator __last)
1746{
1747 for (; __first != __last; ++__first)
1748 __table_.__insert_multi(*__first);
1749}
1750
1751template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001752inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001753void
1754swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1755 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
Howard Hinnant5f2f14c2011-06-04 18:54:24 +00001756 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001757{
1758 __x.swap(__y);
1759}
1760
1761template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1762bool
1763operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1764 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1765{
1766 if (__x.size() != __y.size())
1767 return false;
1768 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
1769 const_iterator;
1770 typedef pair<const_iterator, const_iterator> _EqRng;
1771 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1772 {
1773 _EqRng __xeq = __x.equal_range(__i->first);
1774 _EqRng __yeq = __y.equal_range(__i->first);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001775 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1776 _VSTD::distance(__yeq.first, __yeq.second) ||
1777 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001778 return false;
1779 __i = __xeq.second;
1780 }
1781 return true;
1782}
1783
1784template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
Howard Hinnantee6ccd02010-09-23 18:58:28 +00001785inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001786bool
1787operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1788 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1789{
1790 return !(__x == __y);
1791}
1792
1793_LIBCPP_END_NAMESPACE_STD
1794
1795#endif // _LIBCPP_UNORDERED_MAP