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