master
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_HASH_MAP
11#define _LIBCPP_HASH_MAP
12
13/*
14
15 hash_map synopsis
16
17namespace __gnu_cxx
18{
19
20template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
21 class Alloc = allocator<pair<const Key, T>>>
22class hash_map
23{
24public:
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
98template <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
102template <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
107template <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
112template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
113 class Alloc = allocator<pair<const Key, T>>>
114class hash_multimap
115{
116public:
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
186template <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
190template <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
195template <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#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
205# include <__cxx03/ext/hash_map>
206#else
207# include <__config>
208# include <__hash_table>
209# include <algorithm>
210# include <ext/__hash>
211# include <functional>
212
213# if defined(__DEPRECATED) && __DEPRECATED
214# if defined(_LIBCPP_WARNING)
215_LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")
216# else
217# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>
218# endif
219# endif
220
221# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
222# pragma GCC system_header
223# endif
224
225namespace __gnu_cxx {
226
227template <class _Tp, class _Hash, bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value >
228class __hash_map_hasher : private _Hash {
229public:
230 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {}
231 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
232 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return *this; }
233 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); }
234 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const {
235 return static_cast<const _Hash&>(*this)(__x);
236 }
237};
238
239template <class _Tp, class _Hash>
240class __hash_map_hasher<_Tp, _Hash, false> {
241 _Hash __hash_;
242
243public:
244 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {}
245 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
246 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; }
247 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); }
248 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); }
249};
250
251template <class _Tp, class _Pred, bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value >
252class __hash_map_equal : private _Pred {
253public:
254 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {}
255 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
256 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return *this; }
257 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const {
258 return static_cast<const _Pred&>(*this)(__x.first, __y.first);
259 }
260 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
261 return static_cast<const _Pred&>(*this)(__x, __y.first);
262 }
263 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
264 return static_cast<const _Pred&>(*this)(__x.first, __y);
265 }
266 _LIBCPP_HIDE_FROM_ABI bool
267 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
268 return static_cast<const _Pred&>(*this)(__x, __y);
269 }
270};
271
272template <class _Tp, class _Pred>
273class __hash_map_equal<_Tp, _Pred, false> {
274 _Pred __pred_;
275
276public:
277 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {}
278 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
279 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; }
280 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); }
281 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
282 return __pred_(__x, __y.first);
283 }
284 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
285 return __pred_(__x.first, __y);
286 }
287 _LIBCPP_HIDE_FROM_ABI bool
288 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
289 return __pred_(__x, __y);
290 }
291};
292
293template <class _Alloc>
294class __hash_map_node_destructor {
295 typedef _Alloc allocator_type;
296 typedef std::allocator_traits<allocator_type> __alloc_traits;
297 typedef typename __alloc_traits::value_type::__node_value_type value_type;
298
299public:
300 typedef typename __alloc_traits::pointer pointer;
301
302private:
303 typedef typename value_type::first_type first_type;
304 typedef typename value_type::second_type second_type;
305
306 allocator_type& __na_;
307
308public:
309 bool __first_constructed;
310 bool __second_constructed;
311
312 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default;
313 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
314
315 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na)
316 : __na_(__na), __first_constructed(false), __second_constructed(false) {}
317
318# ifndef _LIBCPP_CXX03_LANG
319 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x)
320 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
321 __x.__value_constructed = false;
322 }
323# else // _LIBCPP_CXX03_LANG
324 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x)
325 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
326 const_cast<bool&>(__x.__value_constructed) = false;
327 }
328# endif // _LIBCPP_CXX03_LANG
329
330 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) {
331 if (__second_constructed)
332 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));
333 if (__first_constructed)
334 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));
335 if (__p)
336 __alloc_traits::deallocate(__na_, __p, 1);
337 }
338};
339
340template <class _HashIterator>
341class __hash_map_iterator {
342 _HashIterator __i_;
343
344 typedef const typename _HashIterator::value_type::first_type key_type;
345 typedef typename _HashIterator::value_type::second_type mapped_type;
346
347public:
348 typedef std::forward_iterator_tag iterator_category;
349 typedef std::pair<key_type, mapped_type> value_type;
350 typedef typename _HashIterator::difference_type difference_type;
351 typedef value_type& reference;
352 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> pointer;
353
354 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {}
355
356 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
357
358 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
359 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
360
361 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
362 ++__i_;
363 return *this;
364 }
365 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
366 __hash_map_iterator __t(*this);
367 ++(*this);
368 return __t;
369 }
370
371 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
372 return __x.__i_ == __y.__i_;
373 }
374 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
375 return __x.__i_ != __y.__i_;
376 }
377
378 template <class, class, class, class, class>
379 friend class hash_map;
380 template <class, class, class, class, class>
381 friend class hash_multimap;
382 template <class>
383 friend class __hash_const_iterator;
384 template <class>
385 friend class __hash_const_local_iterator;
386 template <class>
387 friend class __hash_map_const_iterator;
388};
389
390template <class _HashIterator>
391class __hash_map_const_iterator {
392 _HashIterator __i_;
393
394 typedef const typename _HashIterator::value_type::first_type key_type;
395 typedef typename _HashIterator::value_type::second_type mapped_type;
396
397public:
398 typedef std::forward_iterator_tag iterator_category;
399 typedef std::pair<key_type, mapped_type> value_type;
400 typedef typename _HashIterator::difference_type difference_type;
401 typedef const value_type& reference;
402 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> pointer;
403
404 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {}
405
406 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
407 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
408 : __i_(__i.__i_) {}
409
410 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
411 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
412
413 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
414 ++__i_;
415 return *this;
416 }
417 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
418 __hash_map_const_iterator __t(*this);
419 ++(*this);
420 return __t;
421 }
422
423 friend _LIBCPP_HIDE_FROM_ABI bool
424 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
425 return __x.__i_ == __y.__i_;
426 }
427 friend _LIBCPP_HIDE_FROM_ABI bool
428 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
429 return __x.__i_ != __y.__i_;
430 }
431
432 template <class, class, class, class, class>
433 friend class hash_map;
434 template <class, class, class, class, class>
435 friend class hash_multimap;
436 template <class>
437 friend class __hash_const_iterator;
438 template <class>
439 friend class __hash_const_local_iterator;
440};
441
442template <class _Key,
443 class _Tp,
444 class _Hash = hash<_Key>,
445 class _Pred = std::equal_to<_Key>,
446 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
447class hash_map {
448public:
449 // types
450 typedef _Key key_type;
451 typedef _Tp mapped_type;
452 typedef _Tp data_type;
453 typedef _Hash hasher;
454 typedef _Pred key_equal;
455 typedef _Alloc allocator_type;
456 typedef std::pair<const key_type, mapped_type> value_type;
457 typedef value_type& reference;
458 typedef const value_type& const_reference;
459
460private:
461 typedef std::pair<key_type, mapped_type> __value_type;
462 typedef __hash_map_hasher<__value_type, hasher> __hasher;
463 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
464 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
465
466 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
467
468 __table __table_;
469
470 typedef typename __table::__node_pointer __node_pointer;
471 typedef typename __table::__node_const_pointer __node_const_pointer;
472 typedef typename __table::__node_traits __node_traits;
473 typedef typename __table::__node_allocator __node_allocator;
474 typedef typename __table::__node __node;
475 typedef __hash_map_node_destructor<__node_allocator> _Dp;
476 typedef std::unique_ptr<__node, _Dp> __node_holder;
477 typedef std::allocator_traits<allocator_type> __alloc_traits;
478
479public:
480 typedef typename __alloc_traits::pointer pointer;
481 typedef typename __alloc_traits::const_pointer const_pointer;
482 typedef typename __alloc_traits::size_type size_type;
483 typedef typename __alloc_traits::difference_type difference_type;
484
485 typedef __hash_map_iterator<typename __table::iterator> iterator;
486 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
487
488 _LIBCPP_HIDE_FROM_ABI hash_map() {}
489 explicit _LIBCPP_HIDE_FROM_ABI
490 hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
491 _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
492 template <class _InputIterator>
493 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last);
494 template <class _InputIterator>
495 _LIBCPP_HIDE_FROM_ABI
496 hash_map(_InputIterator __first,
497 _InputIterator __last,
498 size_type __n,
499 const hasher& __hf = hasher(),
500 const key_equal& __eql = key_equal());
501 template <class _InputIterator>
502 _LIBCPP_HIDE_FROM_ABI
503 hash_map(_InputIterator __first,
504 _InputIterator __last,
505 size_type __n,
506 const hasher& __hf,
507 const key_equal& __eql,
508 const allocator_type& __a);
509 _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u);
510
511 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
512
513 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
514 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
515 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
516
517 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
518 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
519 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
520 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
521
522 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
523 return __table_.__emplace_unique(__x);
524 }
525 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
526 template <class _InputIterator>
527 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
528
529 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
530 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
531 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
532 __table_.erase(__first.__i_, __last.__i_);
533 }
534 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
535
536 _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); }
537
538 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
539 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
540
541 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
542 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
543 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
544 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
545 return __table_.__equal_range_unique(__k);
546 }
547 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
548 return __table_.__equal_range_unique(__k);
549 }
550
551 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
552
553 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
554 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
555
556 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
557
558 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
559
560private:
561 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k);
562};
563
564template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
565hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql)
566 : __table_(__hf, __eql) {
567 __table_.__rehash_unique(__n);
568}
569
570template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
571hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
572 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
573 : __table_(__hf, __eql, __a) {
574 __table_.__rehash_unique(__n);
575}
576
577template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
578template <class _InputIterator>
579hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) {
580 insert(__first, __last);
581}
582
583template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
584template <class _InputIterator>
585hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
586 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
587 : __table_(__hf, __eql) {
588 __table_.__rehash_unique(__n);
589 insert(__first, __last);
590}
591
592template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
593template <class _InputIterator>
594hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
595 _InputIterator __first,
596 _InputIterator __last,
597 size_type __n,
598 const hasher& __hf,
599 const key_equal& __eql,
600 const allocator_type& __a)
601 : __table_(__hf, __eql, __a) {
602 __table_.__rehash_unique(__n);
603 insert(__first, __last);
604}
605
606template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
607hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) {
608 __table_.__rehash_unique(__u.bucket_count());
609 insert(__u.begin(), __u.end());
610}
611
612template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
613typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
614hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) {
615 __node_allocator& __na = __table_.__node_alloc();
616 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
617 __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);
618 __h.get_deleter().__first_constructed = true;
619 __node_traits::construct(__na, std::addressof(__h->__get_value().second));
620 __h.get_deleter().__second_constructed = true;
621 return __h;
622}
623
624template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
625template <class _InputIterator>
626inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
627 for (; __first != __last; ++__first)
628 __table_.__emplace_unique(*__first);
629}
630
631template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
632_Tp& hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
633 iterator __i = find(__k);
634 if (__i != end())
635 return __i->second;
636 __node_holder __h = __construct_node(__k);
637 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
638 __h.release();
639 return __r.first->second;
640}
641
642template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
643inline _LIBCPP_HIDE_FROM_ABI void
644swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
645 __x.swap(__y);
646}
647
648template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
649_LIBCPP_HIDE_FROM_ABI bool
650operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
651 if (__x.size() != __y.size())
652 return false;
653 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
654 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
655 const_iterator __j = __y.find(__i->first);
656 if (__j == __ey || !(*__i == *__j))
657 return false;
658 }
659 return true;
660}
661
662template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
663inline _LIBCPP_HIDE_FROM_ABI bool
664operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
665 return !(__x == __y);
666}
667
668template <class _Key,
669 class _Tp,
670 class _Hash = hash<_Key>,
671 class _Pred = std::equal_to<_Key>,
672 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
673class hash_multimap {
674public:
675 // types
676 typedef _Key key_type;
677 typedef _Tp mapped_type;
678 typedef _Tp data_type;
679 typedef _Hash hasher;
680 typedef _Pred key_equal;
681 typedef _Alloc allocator_type;
682 typedef std::pair<const key_type, mapped_type> value_type;
683 typedef value_type& reference;
684 typedef const value_type& const_reference;
685
686private:
687 typedef std::pair<key_type, mapped_type> __value_type;
688 typedef __hash_map_hasher<__value_type, hasher> __hasher;
689 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
690 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
691
692 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
693
694 __table __table_;
695
696 typedef typename __table::__node_traits __node_traits;
697 typedef typename __table::__node_allocator __node_allocator;
698 typedef typename __table::__node __node;
699 typedef __hash_map_node_destructor<__node_allocator> _Dp;
700 typedef std::unique_ptr<__node, _Dp> __node_holder;
701 typedef std::allocator_traits<allocator_type> __alloc_traits;
702
703public:
704 typedef typename __alloc_traits::pointer pointer;
705 typedef typename __alloc_traits::const_pointer const_pointer;
706 typedef typename __alloc_traits::size_type size_type;
707 typedef typename __alloc_traits::difference_type difference_type;
708
709 typedef __hash_map_iterator<typename __table::iterator> iterator;
710 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
711
712 _LIBCPP_HIDE_FROM_ABI hash_multimap() {}
713 explicit _LIBCPP_HIDE_FROM_ABI
714 hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
715 _LIBCPP_HIDE_FROM_ABI
716 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
717 template <class _InputIterator>
718 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last);
719 template <class _InputIterator>
720 _LIBCPP_HIDE_FROM_ABI
721 hash_multimap(_InputIterator __first,
722 _InputIterator __last,
723 size_type __n,
724 const hasher& __hf = hasher(),
725 const key_equal& __eql = key_equal());
726 template <class _InputIterator>
727 _LIBCPP_HIDE_FROM_ABI hash_multimap(
728 _InputIterator __first,
729 _InputIterator __last,
730 size_type __n,
731 const hasher& __hf,
732 const key_equal& __eql,
733 const allocator_type& __a);
734 _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u);
735
736 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
737
738 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
739 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
740 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
741
742 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
743 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
744 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
745 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
746
747 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); }
748 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
749 template <class _InputIterator>
750 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
751
752 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
753 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
754 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
755 __table_.erase(__first.__i_, __last.__i_);
756 }
757 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
758
759 _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); }
760
761 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
762 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
763
764 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
765 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
766 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
767 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
768 return __table_.__equal_range_multi(__k);
769 }
770 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
771 return __table_.__equal_range_multi(__k);
772 }
773
774 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
775 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
776
777 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
778
779 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
780};
781
782template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
783hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql)
784 : __table_(__hf, __eql) {
785 __table_.__rehash_multi(__n);
786}
787
788template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
789hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
790 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
791 : __table_(__hf, __eql, __a) {
792 __table_.__rehash_multi(__n);
793}
794
795template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
796template <class _InputIterator>
797hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) {
798 insert(__first, __last);
799}
800
801template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
802template <class _InputIterator>
803hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
804 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
805 : __table_(__hf, __eql) {
806 __table_.__rehash_multi(__n);
807 insert(__first, __last);
808}
809
810template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
811template <class _InputIterator>
812hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
813 _InputIterator __first,
814 _InputIterator __last,
815 size_type __n,
816 const hasher& __hf,
817 const key_equal& __eql,
818 const allocator_type& __a)
819 : __table_(__hf, __eql, __a) {
820 __table_.__rehash_multi(__n);
821 insert(__first, __last);
822}
823
824template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
825hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) {
826 __table_.__rehash_multi(__u.bucket_count());
827 insert(__u.begin(), __u.end());
828}
829
830template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
831template <class _InputIterator>
832inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
833 for (; __first != __last; ++__first)
834 __table_.__emplace_multi(*__first);
835}
836
837template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
838inline _LIBCPP_HIDE_FROM_ABI void
839swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
840 __x.swap(__y);
841}
842
843template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
844_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
845 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
846 if (__x.size() != __y.size())
847 return false;
848 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
849 typedef std::pair<const_iterator, const_iterator> _EqRng;
850 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
851 _EqRng __xeq = __x.equal_range(__i->first);
852 _EqRng __yeq = __y.equal_range(__i->first);
853 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
854 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
855 return false;
856 __i = __xeq.second;
857 }
858 return true;
859}
860
861template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
862inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
863 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
864 return !(__x == __y);
865}
866
867} // namespace __gnu_cxx
868
869# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
870# include <concepts>
871# include <iterator>
872# include <type_traits>
873# endif
874#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
875
876#endif // _LIBCPP_HASH_MAP