Debian Codegraph @

libcxx/include/__cxx03/ext/hash_map

raw
1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___CXX03_HASH_MAP
11 #define _LIBCPP___CXX03_HASH_MAP
12
13 /*
14
15 hash_map synopsis
16
17 namespace __gnu_cxx
18 {
19
20 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
21 class Alloc = allocator<pair<const Key, T>>>
22 class hash_map
23 {
24 public:
25 // types
26 typedef Key key_type;
27 typedef T mapped_type;
28 typedef Hash hasher;
29 typedef Pred key_equal;
30 typedef Alloc allocator_type;
31 typedef pair<const key_type, mapped_type> value_type;
32 typedef value_type& reference;
33 typedef const value_type& const_reference;
34 typedef typename allocator_traits<allocator_type>::pointer pointer;
35 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
36 typedef typename allocator_traits<allocator_type>::size_type size_type;
37 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
38
39 typedef /unspecified/ iterator;
40 typedef /unspecified/ const_iterator;
41
42 hash_map();
43 explicit hash_map(size_type n, const hasher& hf = hasher(),
44 const key_equal& eql = key_equal(),
45 const allocator_type& a = allocator_type());
46 template <class InputIterator>
47 hash_map(InputIterator f, InputIterator l);
48 template <class InputIterator>
49 hash_map(InputIterator f, InputIterator l,
50 size_type n, const hasher& hf = hasher(),
51 const key_equal& eql = key_equal(),
52 const allocator_type& a = allocator_type());
53 hash_map(const hash_map&);
54 ~hash_map();
55 hash_map& operator=(const hash_map&);
56
57 allocator_type get_allocator() const;
58
59 bool empty() const;
60 size_type size() const;
61 size_type max_size() const;
62
63 iterator begin();
64 iterator end();
65 const_iterator begin() const;
66 const_iterator end() const;
67
68 pair<iterator, bool> insert(const value_type& obj);
69 template <class InputIterator>
70 void insert(InputIterator first, InputIterator last);
71
72 void erase(const_iterator position);
73 size_type erase(const key_type& k);
74 void erase(const_iterator first, const_iterator last);
75 void clear();
76
77 void swap(hash_map&);
78
79 hasher hash_funct() const;
80 key_equal key_eq() const;
81
82 iterator find(const key_type& k);
83 const_iterator find(const key_type& k) const;
84 size_type count(const key_type& k) const;
85 pair<iterator, iterator> equal_range(const key_type& k);
86 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
87
88 mapped_type& operator[](const key_type& k);
89
90 size_type bucket_count() const;
91 size_type max_bucket_count() const;
92
93 size_type elems_in_bucket(size_type n) const;
94
95 void resize(size_type n);
96 };
97
98 template <class Key, class T, class Hash, class Pred, class Alloc>
99 void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,
100 hash_map<Key, T, Hash, Pred, Alloc>& y);
101
102 template <class Key, class T, class Hash, class Pred, class Alloc>
103 bool
104 operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
105 const hash_map<Key, T, Hash, Pred, Alloc>& y);
106
107 template <class Key, class T, class Hash, class Pred, class Alloc>
108 bool
109 operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
110 const hash_map<Key, T, Hash, Pred, Alloc>& y);
111
112 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
113 class Alloc = allocator<pair<const Key, T>>>
114 class hash_multimap
115 {
116 public:
117 // types
118 typedef Key key_type;
119 typedef T mapped_type;
120 typedef Hash hasher;
121 typedef Pred key_equal;
122 typedef Alloc allocator_type;
123 typedef pair<const key_type, mapped_type> value_type;
124 typedef value_type& reference;
125 typedef const value_type& const_reference;
126 typedef typename allocator_traits<allocator_type>::pointer pointer;
127 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
128 typedef typename allocator_traits<allocator_type>::size_type size_type;
129 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
130
131 typedef /unspecified/ iterator;
132 typedef /unspecified/ const_iterator;
133
134 explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),
135 const key_equal& eql = key_equal(),
136 const allocator_type& a = allocator_type());
137 template <class InputIterator>
138 hash_multimap(InputIterator f, InputIterator l,
139 size_type n = 193, const hasher& hf = hasher(),
140 const key_equal& eql = key_equal(),
141 const allocator_type& a = allocator_type());
142 explicit hash_multimap(const allocator_type&);
143 hash_multimap(const hash_multimap&);
144 ~hash_multimap();
145 hash_multimap& operator=(const hash_multimap&);
146
147 allocator_type get_allocator() const;
148
149 bool empty() const;
150 size_type size() const;
151 size_type max_size() const;
152
153 iterator begin();
154 iterator end();
155 const_iterator begin() const;
156 const_iterator end() const;
157
158 iterator insert(const value_type& obj);
159 template <class InputIterator>
160 void insert(InputIterator first, InputIterator last);
161
162 void erase(const_iterator position);
163 size_type erase(const key_type& k);
164 void erase(const_iterator first, const_iterator last);
165 void clear();
166
167 void swap(hash_multimap&);
168
169 hasher hash_funct() const;
170 key_equal key_eq() const;
171
172 iterator find(const key_type& k);
173 const_iterator find(const key_type& k) const;
174 size_type count(const key_type& k) const;
175 pair<iterator, iterator> equal_range(const key_type& k);
176 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
177
178 size_type bucket_count() const;
179 size_type max_bucket_count() const;
180
181 size_type elems_in_bucket(size_type n) const;
182
183 void resize(size_type n);
184 };
185
186 template <class Key, class T, class Hash, class Pred, class Alloc>
187 void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,
188 hash_multimap<Key, T, Hash, Pred, Alloc>& y);
189
190 template <class Key, class T, class Hash, class Pred, class Alloc>
191 bool
192 operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
193 const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
194
195 template <class Key, class T, class Hash, class Pred, class Alloc>
196 bool
197 operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
198 const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
199
200 } // __gnu_cxx
201
202 */
203
204 #include <__cxx03/__config>
205 #include <__cxx03/__hash_table>
206 #include <__cxx03/algorithm>
207 #include <__cxx03/ext/__hash>
208 #include <__cxx03/functional>
209
210 #if defined(__DEPRECATED) && __DEPRECATED
211 # if defined(_LIBCPP_WARNING)
212 _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")
213 # else
214 # warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>
215 # endif
216 #endif
217
218 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
219 # pragma GCC system_header
220 #endif
221
222 namespace __gnu_cxx {
223
224 template <class _Tp, class _Hash, bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value >
225 class __hash_map_hasher : private _Hash {
226 public:
227 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {}
228 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
229 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return *this; }
230 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); }
231 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const {
232 return static_cast<const _Hash&>(*this)(__x);
233 }
234 };
235
236 template <class _Tp, class _Hash>
237 class __hash_map_hasher<_Tp, _Hash, false> {
238 _Hash __hash_;
239
240 public:
241 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {}
242 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
243 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; }
244 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); }
245 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); }
246 };
247
248 template <class _Tp, class _Pred, bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value >
249 class __hash_map_equal : private _Pred {
250 public:
251 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {}
252 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
253 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return *this; }
254 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const {
255 return static_cast<const _Pred&>(*this)(__x.first, __y.first);
256 }
257 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
258 return static_cast<const _Pred&>(*this)(__x, __y.first);
259 }
260 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
261 return static_cast<const _Pred&>(*this)(__x.first, __y);
262 }
263 _LIBCPP_HIDE_FROM_ABI bool
264 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
265 return static_cast<const _Pred&>(*this)(__x, __y);
266 }
267 };
268
269 template <class _Tp, class _Pred>
270 class __hash_map_equal<_Tp, _Pred, false> {
271 _Pred __pred_;
272
273 public:
274 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {}
275 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
276 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; }
277 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); }
278 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
279 return __pred_(__x, __y.first);
280 }
281 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
282 return __pred_(__x.first, __y);
283 }
284 _LIBCPP_HIDE_FROM_ABI bool
285 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
286 return __pred_(__x, __y);
287 }
288 };
289
290 template <class _Alloc>
291 class __hash_map_node_destructor {
292 typedef _Alloc allocator_type;
293 typedef std::allocator_traits<allocator_type> __alloc_traits;
294 typedef typename __alloc_traits::value_type::__node_value_type value_type;
295
296 public:
297 typedef typename __alloc_traits::pointer pointer;
298
299 private:
300 typedef typename value_type::first_type first_type;
301 typedef typename value_type::second_type second_type;
302
303 allocator_type& __na_;
304
305 public:
306 bool __first_constructed;
307 bool __second_constructed;
308
309 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default;
310 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
311
312 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na)
313 : __na_(__na), __first_constructed(false), __second_constructed(false) {}
314
315 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x)
316 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
317 const_cast<bool&>(__x.__value_constructed) = false;
318 }
319
320 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) {
321 if (__second_constructed)
322 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));
323 if (__first_constructed)
324 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));
325 if (__p)
326 __alloc_traits::deallocate(__na_, __p, 1);
327 }
328 };
329
330 template <class _HashIterator>
331 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
332 _HashIterator __i_;
333
334 typedef const typename _HashIterator::value_type::first_type key_type;
335 typedef typename _HashIterator::value_type::second_type mapped_type;
336
337 public:
338 typedef std::forward_iterator_tag iterator_category;
339 typedef std::pair<key_type, mapped_type> value_type;
340 typedef typename _HashIterator::difference_type difference_type;
341 typedef value_type& reference;
342 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> pointer;
343
344 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {}
345
346 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
347
348 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
349 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
350
351 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
352 ++__i_;
353 return *this;
354 }
355 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
356 __hash_map_iterator __t(*this);
357 ++(*this);
358 return __t;
359 }
360
361 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
362 return __x.__i_ == __y.__i_;
363 }
364 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
365 return __x.__i_ != __y.__i_;
366 }
367
368 template <class, class, class, class, class>
369 friend class _LIBCPP_TEMPLATE_VIS hash_map;
370 template <class, class, class, class, class>
371 friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
372 template <class>
373 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
374 template <class>
375 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
376 template <class>
377 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
378 };
379
380 template <class _HashIterator>
381 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
382 _HashIterator __i_;
383
384 typedef const typename _HashIterator::value_type::first_type key_type;
385 typedef typename _HashIterator::value_type::second_type mapped_type;
386
387 public:
388 typedef std::forward_iterator_tag iterator_category;
389 typedef std::pair<key_type, mapped_type> value_type;
390 typedef typename _HashIterator::difference_type difference_type;
391 typedef const value_type& reference;
392 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> pointer;
393
394 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {}
395
396 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
397 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
398 : __i_(__i.__i_) {}
399
400 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
401 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
402
403 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
404 ++__i_;
405 return *this;
406 }
407 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
408 __hash_map_const_iterator __t(*this);
409 ++(*this);
410 return __t;
411 }
412
413 friend _LIBCPP_HIDE_FROM_ABI bool
414 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
415 return __x.__i_ == __y.__i_;
416 }
417 friend _LIBCPP_HIDE_FROM_ABI bool
418 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
419 return __x.__i_ != __y.__i_;
420 }
421
422 template <class, class, class, class, class>
423 friend class _LIBCPP_TEMPLATE_VIS hash_map;
424 template <class, class, class, class, class>
425 friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
426 template <class>
427 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
428 template <class>
429 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
430 };
431
432 template <class _Key,
433 class _Tp,
434 class _Hash = hash<_Key>,
435 class _Pred = std::equal_to<_Key>,
436 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
437 class _LIBCPP_TEMPLATE_VIS hash_map {
438 public:
439 // types
440 typedef _Key key_type;
441 typedef _Tp mapped_type;
442 typedef _Tp data_type;
443 typedef _Hash hasher;
444 typedef _Pred key_equal;
445 typedef _Alloc allocator_type;
446 typedef std::pair<const key_type, mapped_type> value_type;
447 typedef value_type& reference;
448 typedef const value_type& const_reference;
449
450 private:
451 typedef std::pair<key_type, mapped_type> __value_type;
452 typedef __hash_map_hasher<__value_type, hasher> __hasher;
453 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
454 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
455
456 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
457
458 __table __table_;
459
460 typedef typename __table::__node_pointer __node_pointer;
461 typedef typename __table::__node_const_pointer __node_const_pointer;
462 typedef typename __table::__node_traits __node_traits;
463 typedef typename __table::__node_allocator __node_allocator;
464 typedef typename __table::__node __node;
465 typedef __hash_map_node_destructor<__node_allocator> _Dp;
466 typedef std::unique_ptr<__node, _Dp> __node_holder;
467 typedef std::allocator_traits<allocator_type> __alloc_traits;
468
469 public:
470 typedef typename __alloc_traits::pointer pointer;
471 typedef typename __alloc_traits::const_pointer const_pointer;
472 typedef typename __alloc_traits::size_type size_type;
473 typedef typename __alloc_traits::difference_type difference_type;
474
475 typedef __hash_map_iterator<typename __table::iterator> iterator;
476 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
477
478 _LIBCPP_HIDE_FROM_ABI hash_map() {}
479 explicit _LIBCPP_HIDE_FROM_ABI
480 hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
481 _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
482 template <class _InputIterator>
483 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last);
484 template <class _InputIterator>
485 _LIBCPP_HIDE_FROM_ABI
486 hash_map(_InputIterator __first,
487 _InputIterator __last,
488 size_type __n,
489 const hasher& __hf = hasher(),
490 const key_equal& __eql = key_equal());
491 template <class _InputIterator>
492 _LIBCPP_HIDE_FROM_ABI
493 hash_map(_InputIterator __first,
494 _InputIterator __last,
495 size_type __n,
496 const hasher& __hf,
497 const key_equal& __eql,
498 const allocator_type& __a);
499 _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u);
500
501 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
502
503 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
504 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
505 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
506
507 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
508 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
509 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
510 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
511
512 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
513 return __table_.__insert_unique(__x);
514 }
515 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
516 template <class _InputIterator>
517 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
518
519 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
520 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
521 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
522 __table_.erase(__first.__i_, __last.__i_);
523 }
524 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
525
526 _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); }
527
528 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
529 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
530
531 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
532 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
533 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
534 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
535 return __table_.__equal_range_unique(__k);
536 }
537 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
538 return __table_.__equal_range_unique(__k);
539 }
540
541 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
542
543 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
544 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
545
546 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
547
548 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
549
550 private:
551 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k);
552 };
553
554 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
555 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql)
556 : __table_(__hf, __eql) {
557 __table_.__rehash_unique(__n);
558 }
559
560 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
561 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
562 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
563 : __table_(__hf, __eql, __a) {
564 __table_.__rehash_unique(__n);
565 }
566
567 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
568 template <class _InputIterator>
569 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) {
570 insert(__first, __last);
571 }
572
573 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
574 template <class _InputIterator>
575 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
576 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
577 : __table_(__hf, __eql) {
578 __table_.__rehash_unique(__n);
579 insert(__first, __last);
580 }
581
582 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
583 template <class _InputIterator>
584 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
585 _InputIterator __first,
586 _InputIterator __last,
587 size_type __n,
588 const hasher& __hf,
589 const key_equal& __eql,
590 const allocator_type& __a)
591 : __table_(__hf, __eql, __a) {
592 __table_.__rehash_unique(__n);
593 insert(__first, __last);
594 }
595
596 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
597 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) {
598 __table_.__rehash_unique(__u.bucket_count());
599 insert(__u.begin(), __u.end());
600 }
601
602 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
603 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
604 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) {
605 __node_allocator& __na = __table_.__node_alloc();
606 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
607 __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);
608 __h.get_deleter().__first_constructed = true;
609 __node_traits::construct(__na, std::addressof(__h->__get_value().second));
610 __h.get_deleter().__second_constructed = true;
611 return __h;
612 }
613
614 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
615 template <class _InputIterator>
616 inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
617 for (; __first != __last; ++__first)
618 __table_.__insert_unique(*__first);
619 }
620
621 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
622 _Tp& hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
623 iterator __i = find(__k);
624 if (__i != end())
625 return __i->second;
626 __node_holder __h = __construct_node(__k);
627 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
628 __h.release();
629 return __r.first->second;
630 }
631
632 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
633 inline _LIBCPP_HIDE_FROM_ABI void
634 swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
635 __x.swap(__y);
636 }
637
638 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
639 _LIBCPP_HIDE_FROM_ABI bool
640 operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
641 if (__x.size() != __y.size())
642 return false;
643 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
644 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
645 const_iterator __j = __y.find(__i->first);
646 if (__j == __ey || !(*__i == *__j))
647 return false;
648 }
649 return true;
650 }
651
652 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
653 inline _LIBCPP_HIDE_FROM_ABI bool
654 operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
655 return !(__x == __y);
656 }
657
658 template <class _Key,
659 class _Tp,
660 class _Hash = hash<_Key>,
661 class _Pred = std::equal_to<_Key>,
662 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
663 class _LIBCPP_TEMPLATE_VIS hash_multimap {
664 public:
665 // types
666 typedef _Key key_type;
667 typedef _Tp mapped_type;
668 typedef _Tp data_type;
669 typedef _Hash hasher;
670 typedef _Pred key_equal;
671 typedef _Alloc allocator_type;
672 typedef std::pair<const key_type, mapped_type> value_type;
673 typedef value_type& reference;
674 typedef const value_type& const_reference;
675
676 private:
677 typedef std::pair<key_type, mapped_type> __value_type;
678 typedef __hash_map_hasher<__value_type, hasher> __hasher;
679 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
680 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
681
682 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
683
684 __table __table_;
685
686 typedef typename __table::__node_traits __node_traits;
687 typedef typename __table::__node_allocator __node_allocator;
688 typedef typename __table::__node __node;
689 typedef __hash_map_node_destructor<__node_allocator> _Dp;
690 typedef std::unique_ptr<__node, _Dp> __node_holder;
691 typedef std::allocator_traits<allocator_type> __alloc_traits;
692
693 public:
694 typedef typename __alloc_traits::pointer pointer;
695 typedef typename __alloc_traits::const_pointer const_pointer;
696 typedef typename __alloc_traits::size_type size_type;
697 typedef typename __alloc_traits::difference_type difference_type;
698
699 typedef __hash_map_iterator<typename __table::iterator> iterator;
700 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
701
702 _LIBCPP_HIDE_FROM_ABI hash_multimap() {}
703 explicit _LIBCPP_HIDE_FROM_ABI
704 hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
705 _LIBCPP_HIDE_FROM_ABI
706 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
707 template <class _InputIterator>
708 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last);
709 template <class _InputIterator>
710 _LIBCPP_HIDE_FROM_ABI
711 hash_multimap(_InputIterator __first,
712 _InputIterator __last,
713 size_type __n,
714 const hasher& __hf = hasher(),
715 const key_equal& __eql = key_equal());
716 template <class _InputIterator>
717 _LIBCPP_HIDE_FROM_ABI hash_multimap(
718 _InputIterator __first,
719 _InputIterator __last,
720 size_type __n,
721 const hasher& __hf,
722 const key_equal& __eql,
723 const allocator_type& __a);
724 _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u);
725
726 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
727
728 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
729 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
730 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
731
732 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
733 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
734 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
735 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
736
737 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
738 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
739 template <class _InputIterator>
740 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
741
742 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
743 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
744 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
745 __table_.erase(__first.__i_, __last.__i_);
746 }
747 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
748
749 _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); }
750
751 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
752 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
753
754 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
755 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
756 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
757 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
758 return __table_.__equal_range_multi(__k);
759 }
760 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
761 return __table_.__equal_range_multi(__k);
762 }
763
764 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
765 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
766
767 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
768
769 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
770 };
771
772 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
773 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql)
774 : __table_(__hf, __eql) {
775 __table_.__rehash_multi(__n);
776 }
777
778 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
779 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
780 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
781 : __table_(__hf, __eql, __a) {
782 __table_.__rehash_multi(__n);
783 }
784
785 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
786 template <class _InputIterator>
787 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) {
788 insert(__first, __last);
789 }
790
791 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
792 template <class _InputIterator>
793 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
794 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
795 : __table_(__hf, __eql) {
796 __table_.__rehash_multi(__n);
797 insert(__first, __last);
798 }
799
800 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
801 template <class _InputIterator>
802 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
803 _InputIterator __first,
804 _InputIterator __last,
805 size_type __n,
806 const hasher& __hf,
807 const key_equal& __eql,
808 const allocator_type& __a)
809 : __table_(__hf, __eql, __a) {
810 __table_.__rehash_multi(__n);
811 insert(__first, __last);
812 }
813
814 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
815 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) {
816 __table_.__rehash_multi(__u.bucket_count());
817 insert(__u.begin(), __u.end());
818 }
819
820 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
821 template <class _InputIterator>
822 inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
823 for (; __first != __last; ++__first)
824 __table_.__insert_multi(*__first);
825 }
826
827 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
828 inline _LIBCPP_HIDE_FROM_ABI void
829 swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
830 __x.swap(__y);
831 }
832
833 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
834 _LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
835 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
836 if (__x.size() != __y.size())
837 return false;
838 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
839 typedef std::pair<const_iterator, const_iterator> _EqRng;
840 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
841 _EqRng __xeq = __x.equal_range(__i->first);
842 _EqRng __yeq = __y.equal_range(__i->first);
843 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
844 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
845 return false;
846 __i = __xeq.second;
847 }
848 return true;
849 }
850
851 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
852 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
853 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
854 return !(__x == __y);
855 }
856
857 } // namespace __gnu_cxx
858
859 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)
860 # include <__cxx03/iterator>
861 # include <__cxx03/type_traits>
862 #endif
863
864 #endif // _LIBCPP___CXX03_HASH_MAP