2 //===-------------------------- hash_map ----------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_HASH_MAP
12 #define _LIBCPP_HASH_MAP
21 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
22 class Alloc = allocator<pair<const Key, T>>>
28 typedef T mapped_type;
30 typedef Pred key_equal;
31 typedef Alloc allocator_type;
32 typedef pair<const key_type, mapped_type> value_type;
33 typedef value_type& reference;
34 typedef const value_type& const_reference;
35 typedef typename allocator_traits<allocator_type>::pointer pointer;
36 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
37 typedef typename allocator_traits<allocator_type>::size_type size_type;
38 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
40 typedef /unspecified/ iterator;
41 typedef /unspecified/ const_iterator;
43 explicit hash_map(size_type n = 193, 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 size_type n = 193, const hasher& hf = hasher(),
49 const key_equal& eql = key_equal(),
50 const allocator_type& a = allocator_type());
51 hash_map(const hash_map&);
53 hash_map& operator=(const hash_map&);
55 allocator_type get_allocator() const;
58 size_type size() const;
59 size_type max_size() const;
63 const_iterator begin() const;
64 const_iterator end() const;
66 pair<iterator, bool> insert(const value_type& obj);
67 template <class InputIterator>
68 void insert(InputIterator first, InputIterator last);
70 void erase(const_iterator position);
71 size_type erase(const key_type& k);
72 void erase(const_iterator first, const_iterator last);
77 hasher hash_funct() const;
78 key_equal key_eq() const;
80 iterator find(const key_type& k);
81 const_iterator find(const key_type& k) const;
82 size_type count(const key_type& k) const;
83 pair<iterator, iterator> equal_range(const key_type& k);
84 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
86 mapped_type& operator[](const key_type& k);
88 size_type bucket_count() const;
89 size_type max_bucket_count() const;
91 size_type elems_in_bucket(size_type n) const;
93 void resize(size_type n);
96 template <class Key, class T, class Hash, class Pred, class Alloc>
97 void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,
98 hash_map<Key, T, Hash, Pred, Alloc>& y);
100 template <class Key, class T, class Hash, class Pred, class Alloc>
102 operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
103 const hash_map<Key, T, Hash, Pred, Alloc>& y);
105 template <class Key, class T, class Hash, class Pred, class Alloc>
107 operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
108 const hash_map<Key, T, Hash, Pred, Alloc>& y);
110 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
111 class Alloc = allocator<pair<const Key, T>>>
116 typedef Key key_type;
117 typedef T mapped_type;
119 typedef Pred key_equal;
120 typedef Alloc allocator_type;
121 typedef pair<const key_type, mapped_type> value_type;
122 typedef value_type& reference;
123 typedef const value_type& const_reference;
124 typedef typename allocator_traits<allocator_type>::pointer pointer;
125 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
126 typedef typename allocator_traits<allocator_type>::size_type size_type;
127 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
129 typedef /unspecified/ iterator;
130 typedef /unspecified/ const_iterator;
132 explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),
133 const key_equal& eql = key_equal(),
134 const allocator_type& a = allocator_type());
135 template <class InputIterator>
136 hash_multimap(InputIterator f, InputIterator l,
137 size_type n = 193, const hasher& hf = hasher(),
138 const key_equal& eql = key_equal(),
139 const allocator_type& a = allocator_type());
140 explicit hash_multimap(const allocator_type&);
141 hash_multimap(const hash_multimap&);
143 hash_multimap& operator=(const hash_multimap&);
145 allocator_type get_allocator() const;
148 size_type size() const;
149 size_type max_size() const;
153 const_iterator begin() const;
154 const_iterator end() const;
156 iterator insert(const value_type& obj);
157 template <class InputIterator>
158 void insert(InputIterator first, InputIterator last);
160 void erase(const_iterator position);
161 size_type erase(const key_type& k);
162 void erase(const_iterator first, const_iterator last);
165 void swap(hash_multimap&);
167 hasher hash_funct() const;
168 key_equal key_eq() const;
170 iterator find(const key_type& k);
171 const_iterator find(const key_type& k) const;
172 size_type count(const key_type& k) const;
173 pair<iterator, iterator> equal_range(const key_type& k);
174 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
176 size_type bucket_count() const;
177 size_type max_bucket_count() const;
179 size_type elems_in_bucket(size_type n) const;
181 void resize(size_type n);
184 template <class Key, class T, class Hash, class Pred, class Alloc>
185 void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,
186 hash_multimap<Key, T, Hash, Pred, Alloc>& y);
188 template <class Key, class T, class Hash, class Pred, class Alloc>
190 operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
191 const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
193 template <class Key, class T, class Hash, class Pred, class Alloc>
195 operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
196 const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
203 #include <__hash_table>
204 #include <functional>
206 #include <ext/__hash>
209 #if defined(_MSC_VER) && ! defined(__clang__)
210 _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")
212 # warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>
216 #pragma GCC system_header
218 namespace __gnu_cxx {
222 template <class _Tp, class _Hash, bool = is_empty<_Hash>::value
223 #if __has_feature(is_final)
224 && !__is_final(_Hash)
227 class __hash_map_hasher
231 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {}
232 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
233 _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;}
234 _LIBCPP_INLINE_VISIBILITY
235 size_t operator()(const _Tp& __x) const
236 {return static_cast<const _Hash&>(*this)(__x.first);}
237 _LIBCPP_INLINE_VISIBILITY
238 size_t operator()(const typename _Tp::first_type& __x) const
239 {return static_cast<const _Hash&>(*this)(__x);}
242 template <class _Tp, class _Hash>
243 class __hash_map_hasher<_Tp, _Hash, false>
247 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {}
248 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
249 _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;}
250 _LIBCPP_INLINE_VISIBILITY
251 size_t operator()(const _Tp& __x) const
252 {return __hash_(__x.first);}
253 _LIBCPP_INLINE_VISIBILITY
254 size_t operator()(const typename _Tp::first_type& __x) const
255 {return __hash_(__x);}
258 template <class _Tp, class _Pred, bool = is_empty<_Pred>::value
259 #if __has_feature(is_final)
260 && !__is_final(_Pred)
263 class __hash_map_equal
267 _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {}
268 _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
269 _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;}
270 _LIBCPP_INLINE_VISIBILITY
271 bool operator()(const _Tp& __x, const _Tp& __y) const
272 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);}
273 _LIBCPP_INLINE_VISIBILITY
274 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
275 {return static_cast<const _Pred&>(*this)(__x, __y.first);}
276 _LIBCPP_INLINE_VISIBILITY
277 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
278 {return static_cast<const _Pred&>(*this)(__x.first, __y);}
279 _LIBCPP_INLINE_VISIBILITY
280 bool operator()(const typename _Tp::first_type& __x,
281 const typename _Tp::first_type& __y) const
282 {return static_cast<const _Pred&>(*this)(__x, __y);}
285 template <class _Tp, class _Pred>
286 class __hash_map_equal<_Tp, _Pred, false>
290 _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {}
291 _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
292 _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;}
293 _LIBCPP_INLINE_VISIBILITY
294 bool operator()(const _Tp& __x, const _Tp& __y) const
295 {return __pred_(__x.first, __y.first);}
296 _LIBCPP_INLINE_VISIBILITY
297 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const
298 {return __pred_(__x, __y.first);}
299 _LIBCPP_INLINE_VISIBILITY
300 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const
301 {return __pred_(__x.first, __y);}
302 _LIBCPP_INLINE_VISIBILITY
303 bool operator()(const typename _Tp::first_type& __x,
304 const typename _Tp::first_type& __y) const
305 {return __pred_(__x, __y);}
308 template <class _Alloc>
309 class __hash_map_node_destructor
311 typedef _Alloc allocator_type;
312 typedef allocator_traits<allocator_type> __alloc_traits;
313 typedef typename __alloc_traits::value_type::value_type value_type;
315 typedef typename __alloc_traits::pointer pointer;
317 typedef typename value_type::first_type first_type;
318 typedef typename value_type::second_type second_type;
320 allocator_type& __na_;
322 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
325 bool __first_constructed;
326 bool __second_constructed;
328 _LIBCPP_INLINE_VISIBILITY
329 explicit __hash_map_node_destructor(allocator_type& __na)
331 __first_constructed(false),
332 __second_constructed(false)
335 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
336 _LIBCPP_INLINE_VISIBILITY
337 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x)
339 __first_constructed(__x.__value_constructed),
340 __second_constructed(__x.__value_constructed)
342 __x.__value_constructed = false;
344 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
345 _LIBCPP_INLINE_VISIBILITY
346 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
348 __first_constructed(__x.__value_constructed),
349 __second_constructed(__x.__value_constructed)
351 const_cast<bool&>(__x.__value_constructed) = false;
353 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
355 _LIBCPP_INLINE_VISIBILITY
356 void operator()(pointer __p)
358 if (__second_constructed)
359 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
360 if (__first_constructed)
361 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
363 __alloc_traits::deallocate(__na_, __p, 1);
367 template <class _HashIterator>
368 class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator
372 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
373 typedef const typename _HashIterator::value_type::first_type key_type;
374 typedef typename _HashIterator::value_type::second_type mapped_type;
376 typedef forward_iterator_tag iterator_category;
377 typedef pair<key_type, mapped_type> value_type;
378 typedef typename _HashIterator::difference_type difference_type;
379 typedef value_type& reference;
380 typedef typename __pointer_traits::template
381 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
384 rebind<value_type>::other
388 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {}
390 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
392 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();}
393 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();}
395 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;}
396 _LIBCPP_INLINE_VISIBILITY
397 __hash_map_iterator operator++(int)
399 __hash_map_iterator __t(*this);
404 friend _LIBCPP_INLINE_VISIBILITY
405 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
406 {return __x.__i_ == __y.__i_;}
407 friend _LIBCPP_INLINE_VISIBILITY
408 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y)
409 {return __x.__i_ != __y.__i_;}
411 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map;
412 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap;
413 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
414 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
415 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
418 template <class _HashIterator>
419 class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator
423 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits;
424 typedef const typename _HashIterator::value_type::first_type key_type;
425 typedef typename _HashIterator::value_type::second_type mapped_type;
427 typedef forward_iterator_tag iterator_category;
428 typedef pair<key_type, mapped_type> value_type;
429 typedef typename _HashIterator::difference_type difference_type;
430 typedef const value_type& reference;
431 typedef typename __pointer_traits::template
432 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
433 rebind<const value_type>
435 rebind<const value_type>::other
439 _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {}
441 _LIBCPP_INLINE_VISIBILITY
442 __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
443 _LIBCPP_INLINE_VISIBILITY
444 __hash_map_const_iterator(
445 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
448 _LIBCPP_INLINE_VISIBILITY
449 reference operator*() const {return *operator->();}
450 _LIBCPP_INLINE_VISIBILITY
451 pointer operator->() const {return (pointer)__i_.operator->();}
453 _LIBCPP_INLINE_VISIBILITY
454 __hash_map_const_iterator& operator++() {++__i_; return *this;}
455 _LIBCPP_INLINE_VISIBILITY
456 __hash_map_const_iterator operator++(int)
458 __hash_map_const_iterator __t(*this);
463 friend _LIBCPP_INLINE_VISIBILITY
464 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
465 {return __x.__i_ == __y.__i_;}
466 friend _LIBCPP_INLINE_VISIBILITY
467 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y)
468 {return __x.__i_ != __y.__i_;}
470 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_map;
471 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY hash_multimap;
472 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
473 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
476 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
477 class _Alloc = allocator<pair<const _Key, _Tp> > >
478 class _LIBCPP_TYPE_VIS_ONLY hash_map
482 typedef _Key key_type;
483 typedef _Tp mapped_type;
484 typedef _Tp data_type;
485 typedef _Hash hasher;
486 typedef _Pred key_equal;
487 typedef _Alloc allocator_type;
488 typedef pair<const key_type, mapped_type> value_type;
489 typedef value_type& reference;
490 typedef const value_type& const_reference;
493 typedef pair<key_type, mapped_type> __value_type;
494 typedef __hash_map_hasher<__value_type, hasher> __hasher;
495 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
496 typedef typename allocator_traits<allocator_type>::template
497 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
498 rebind_alloc<__value_type>
500 rebind_alloc<__value_type>::other
504 typedef __hash_table<__value_type, __hasher,
505 __key_equal, __allocator_type> __table;
509 typedef typename __table::__node_pointer __node_pointer;
510 typedef typename __table::__node_const_pointer __node_const_pointer;
511 typedef typename __table::__node_traits __node_traits;
512 typedef typename __table::__node_allocator __node_allocator;
513 typedef typename __table::__node __node;
514 typedef __hash_map_node_destructor<__node_allocator> _Dp;
515 typedef unique_ptr<__node, _Dp> __node_holder;
516 typedef allocator_traits<allocator_type> __alloc_traits;
518 typedef typename __alloc_traits::pointer pointer;
519 typedef typename __alloc_traits::const_pointer const_pointer;
520 typedef typename __alloc_traits::size_type size_type;
521 typedef typename __alloc_traits::difference_type difference_type;
523 typedef __hash_map_iterator<typename __table::iterator> iterator;
524 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
526 _LIBCPP_INLINE_VISIBILITY hash_map() {__table_.rehash(193);}
527 explicit hash_map(size_type __n, const hasher& __hf = hasher(),
528 const key_equal& __eql = key_equal());
529 hash_map(size_type __n, const hasher& __hf,
530 const key_equal& __eql,
531 const allocator_type& __a);
532 template <class _InputIterator>
533 hash_map(_InputIterator __first, _InputIterator __last);
534 template <class _InputIterator>
535 hash_map(_InputIterator __first, _InputIterator __last,
536 size_type __n, const hasher& __hf = hasher(),
537 const key_equal& __eql = key_equal());
538 template <class _InputIterator>
539 hash_map(_InputIterator __first, _InputIterator __last,
540 size_type __n, const hasher& __hf,
541 const key_equal& __eql,
542 const allocator_type& __a);
543 hash_map(const hash_map& __u);
545 _LIBCPP_INLINE_VISIBILITY
546 allocator_type get_allocator() const
547 {return allocator_type(__table_.__node_alloc());}
549 _LIBCPP_INLINE_VISIBILITY
550 bool empty() const {return __table_.size() == 0;}
551 _LIBCPP_INLINE_VISIBILITY
552 size_type size() const {return __table_.size();}
553 _LIBCPP_INLINE_VISIBILITY
554 size_type max_size() const {return __table_.max_size();}
556 _LIBCPP_INLINE_VISIBILITY
557 iterator begin() {return __table_.begin();}
558 _LIBCPP_INLINE_VISIBILITY
559 iterator end() {return __table_.end();}
560 _LIBCPP_INLINE_VISIBILITY
561 const_iterator begin() const {return __table_.begin();}
562 _LIBCPP_INLINE_VISIBILITY
563 const_iterator end() const {return __table_.end();}
565 _LIBCPP_INLINE_VISIBILITY
566 pair<iterator, bool> insert(const value_type& __x)
567 {return __table_.__insert_unique(__x);}
568 _LIBCPP_INLINE_VISIBILITY
569 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
570 template <class _InputIterator>
571 void insert(_InputIterator __first, _InputIterator __last);
573 _LIBCPP_INLINE_VISIBILITY
574 void erase(const_iterator __p) {__table_.erase(__p.__i_);}
575 _LIBCPP_INLINE_VISIBILITY
576 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
577 _LIBCPP_INLINE_VISIBILITY
578 void erase(const_iterator __first, const_iterator __last)
579 {__table_.erase(__first.__i_, __last.__i_);}
580 _LIBCPP_INLINE_VISIBILITY
581 void clear() {__table_.clear();}
583 _LIBCPP_INLINE_VISIBILITY
584 void swap(hash_map& __u) {__table_.swap(__u.__table_);}
586 _LIBCPP_INLINE_VISIBILITY
587 hasher hash_funct() const
588 {return __table_.hash_function().hash_function();}
589 _LIBCPP_INLINE_VISIBILITY
590 key_equal key_eq() const
591 {return __table_.key_eq().key_eq();}
593 _LIBCPP_INLINE_VISIBILITY
594 iterator find(const key_type& __k) {return __table_.find(__k);}
595 _LIBCPP_INLINE_VISIBILITY
596 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
597 _LIBCPP_INLINE_VISIBILITY
598 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
599 _LIBCPP_INLINE_VISIBILITY
600 pair<iterator, iterator> equal_range(const key_type& __k)
601 {return __table_.__equal_range_unique(__k);}
602 _LIBCPP_INLINE_VISIBILITY
603 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
604 {return __table_.__equal_range_unique(__k);}
606 mapped_type& operator[](const key_type& __k);
608 _LIBCPP_INLINE_VISIBILITY
609 size_type bucket_count() const {return __table_.bucket_count();}
610 _LIBCPP_INLINE_VISIBILITY
611 size_type max_bucket_count() const {return __table_.max_bucket_count();}
613 _LIBCPP_INLINE_VISIBILITY
614 size_type elems_in_bucket(size_type __n) const
615 {return __table_.bucket_size(__n);}
617 _LIBCPP_INLINE_VISIBILITY
618 void resize(size_type __n) {__table_.rehash(__n);}
621 __node_holder __construct_node(const key_type& __k);
624 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
625 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
626 size_type __n, const hasher& __hf, const key_equal& __eql)
627 : __table_(__hf, __eql)
629 __table_.rehash(__n);
632 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
633 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
634 size_type __n, const hasher& __hf, const key_equal& __eql,
635 const allocator_type& __a)
636 : __table_(__hf, __eql, __a)
638 __table_.rehash(__n);
641 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
642 template <class _InputIterator>
643 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
644 _InputIterator __first, _InputIterator __last)
646 __table_.rehash(193);
647 insert(__first, __last);
650 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
651 template <class _InputIterator>
652 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
653 _InputIterator __first, _InputIterator __last, size_type __n,
654 const hasher& __hf, const key_equal& __eql)
655 : __table_(__hf, __eql)
657 __table_.rehash(__n);
658 insert(__first, __last);
661 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
662 template <class _InputIterator>
663 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
664 _InputIterator __first, _InputIterator __last, size_type __n,
665 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
666 : __table_(__hf, __eql, __a)
668 __table_.rehash(__n);
669 insert(__first, __last);
672 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
673 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
675 : __table_(__u.__table_)
677 __table_.rehash(__u.bucket_count());
678 insert(__u.begin(), __u.end());
681 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
682 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
683 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k)
685 __node_allocator& __na = __table_.__node_alloc();
686 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
687 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
688 __h.get_deleter().__first_constructed = true;
689 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
690 __h.get_deleter().__second_constructed = true;
691 return _VSTD::move(__h); // explicitly moved for C++03
694 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
695 template <class _InputIterator>
696 inline _LIBCPP_INLINE_VISIBILITY
698 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
699 _InputIterator __last)
701 for (; __first != __last; ++__first)
702 __table_.__insert_unique(*__first);
705 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
707 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k)
709 iterator __i = find(__k);
712 __node_holder __h = __construct_node(__k);
713 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
715 return __r.first->second;
718 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
719 inline _LIBCPP_INLINE_VISIBILITY
721 swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
722 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
727 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
729 operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
730 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
732 if (__x.size() != __y.size())
734 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
736 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
739 const_iterator __j = __y.find(__i->first);
740 if (__j == __ey || !(*__i == *__j))
746 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
747 inline _LIBCPP_INLINE_VISIBILITY
749 operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
750 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
752 return !(__x == __y);
755 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
756 class _Alloc = allocator<pair<const _Key, _Tp> > >
757 class _LIBCPP_TYPE_VIS_ONLY hash_multimap
761 typedef _Key key_type;
762 typedef _Tp mapped_type;
763 typedef _Tp data_type;
764 typedef _Hash hasher;
765 typedef _Pred key_equal;
766 typedef _Alloc allocator_type;
767 typedef pair<const key_type, mapped_type> value_type;
768 typedef value_type& reference;
769 typedef const value_type& const_reference;
772 typedef pair<key_type, mapped_type> __value_type;
773 typedef __hash_map_hasher<__value_type, hasher> __hasher;
774 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
775 typedef typename allocator_traits<allocator_type>::template
776 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
777 rebind_alloc<__value_type>
779 rebind_alloc<__value_type>::other
783 typedef __hash_table<__value_type, __hasher,
784 __key_equal, __allocator_type> __table;
788 typedef typename __table::__node_traits __node_traits;
789 typedef typename __table::__node_allocator __node_allocator;
790 typedef typename __table::__node __node;
791 typedef __hash_map_node_destructor<__node_allocator> _Dp;
792 typedef unique_ptr<__node, _Dp> __node_holder;
793 typedef allocator_traits<allocator_type> __alloc_traits;
795 typedef typename __alloc_traits::pointer pointer;
796 typedef typename __alloc_traits::const_pointer const_pointer;
797 typedef typename __alloc_traits::size_type size_type;
798 typedef typename __alloc_traits::difference_type difference_type;
800 typedef __hash_map_iterator<typename __table::iterator> iterator;
801 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
803 _LIBCPP_INLINE_VISIBILITY
804 hash_multimap() {__table_.rehash(193);}
805 explicit hash_multimap(size_type __n, const hasher& __hf = hasher(),
806 const key_equal& __eql = key_equal());
807 hash_multimap(size_type __n, const hasher& __hf,
808 const key_equal& __eql,
809 const allocator_type& __a);
810 template <class _InputIterator>
811 hash_multimap(_InputIterator __first, _InputIterator __last);
812 template <class _InputIterator>
813 hash_multimap(_InputIterator __first, _InputIterator __last,
814 size_type __n, const hasher& __hf = hasher(),
815 const key_equal& __eql = key_equal());
816 template <class _InputIterator>
817 hash_multimap(_InputIterator __first, _InputIterator __last,
818 size_type __n, const hasher& __hf,
819 const key_equal& __eql,
820 const allocator_type& __a);
821 hash_multimap(const hash_multimap& __u);
823 _LIBCPP_INLINE_VISIBILITY
824 allocator_type get_allocator() const
825 {return allocator_type(__table_.__node_alloc());}
827 _LIBCPP_INLINE_VISIBILITY
828 bool empty() const {return __table_.size() == 0;}
829 _LIBCPP_INLINE_VISIBILITY
830 size_type size() const {return __table_.size();}
831 _LIBCPP_INLINE_VISIBILITY
832 size_type max_size() const {return __table_.max_size();}
834 _LIBCPP_INLINE_VISIBILITY
835 iterator begin() {return __table_.begin();}
836 _LIBCPP_INLINE_VISIBILITY
837 iterator end() {return __table_.end();}
838 _LIBCPP_INLINE_VISIBILITY
839 const_iterator begin() const {return __table_.begin();}
840 _LIBCPP_INLINE_VISIBILITY
841 const_iterator end() const {return __table_.end();}
843 _LIBCPP_INLINE_VISIBILITY
844 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
845 _LIBCPP_INLINE_VISIBILITY
846 iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
847 template <class _InputIterator>
848 void insert(_InputIterator __first, _InputIterator __last);
850 _LIBCPP_INLINE_VISIBILITY
851 void erase(const_iterator __p) {__table_.erase(__p.__i_);}
852 _LIBCPP_INLINE_VISIBILITY
853 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
854 _LIBCPP_INLINE_VISIBILITY
855 void erase(const_iterator __first, const_iterator __last)
856 {__table_.erase(__first.__i_, __last.__i_);}
857 _LIBCPP_INLINE_VISIBILITY
858 void clear() {__table_.clear();}
860 _LIBCPP_INLINE_VISIBILITY
861 void swap(hash_multimap& __u) {__table_.swap(__u.__table_);}
863 _LIBCPP_INLINE_VISIBILITY
864 hasher hash_funct() const
865 {return __table_.hash_function().hash_function();}
866 _LIBCPP_INLINE_VISIBILITY
867 key_equal key_eq() const
868 {return __table_.key_eq().key_eq();}
870 _LIBCPP_INLINE_VISIBILITY
871 iterator find(const key_type& __k) {return __table_.find(__k);}
872 _LIBCPP_INLINE_VISIBILITY
873 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
874 _LIBCPP_INLINE_VISIBILITY
875 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
876 _LIBCPP_INLINE_VISIBILITY
877 pair<iterator, iterator> equal_range(const key_type& __k)
878 {return __table_.__equal_range_multi(__k);}
879 _LIBCPP_INLINE_VISIBILITY
880 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
881 {return __table_.__equal_range_multi(__k);}
883 _LIBCPP_INLINE_VISIBILITY
884 size_type bucket_count() const {return __table_.bucket_count();}
885 _LIBCPP_INLINE_VISIBILITY
886 size_type max_bucket_count() const {return __table_.max_bucket_count();}
888 _LIBCPP_INLINE_VISIBILITY
889 size_type elems_in_bucket(size_type __n) const
890 {return __table_.bucket_size(__n);}
892 _LIBCPP_INLINE_VISIBILITY
893 void resize(size_type __n) {__table_.rehash(__n);}
896 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
897 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
898 size_type __n, const hasher& __hf, const key_equal& __eql)
899 : __table_(__hf, __eql)
901 __table_.rehash(__n);
904 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
905 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
906 size_type __n, const hasher& __hf, const key_equal& __eql,
907 const allocator_type& __a)
908 : __table_(__hf, __eql, __a)
910 __table_.rehash(__n);
913 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
914 template <class _InputIterator>
915 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
916 _InputIterator __first, _InputIterator __last)
918 __table_.rehash(193);
919 insert(__first, __last);
922 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
923 template <class _InputIterator>
924 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
925 _InputIterator __first, _InputIterator __last, size_type __n,
926 const hasher& __hf, const key_equal& __eql)
927 : __table_(__hf, __eql)
929 __table_.rehash(__n);
930 insert(__first, __last);
933 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
934 template <class _InputIterator>
935 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
936 _InputIterator __first, _InputIterator __last, size_type __n,
937 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
938 : __table_(__hf, __eql, __a)
940 __table_.rehash(__n);
941 insert(__first, __last);
944 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
945 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
946 const hash_multimap& __u)
947 : __table_(__u.__table_)
949 __table_.rehash(__u.bucket_count());
950 insert(__u.begin(), __u.end());
953 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
954 template <class _InputIterator>
955 inline _LIBCPP_INLINE_VISIBILITY
957 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
958 _InputIterator __last)
960 for (; __first != __last; ++__first)
961 __table_.__insert_multi(*__first);
964 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
965 inline _LIBCPP_INLINE_VISIBILITY
967 swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
968 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
973 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
975 operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
976 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
978 if (__x.size() != __y.size())
980 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator
982 typedef pair<const_iterator, const_iterator> _EqRng;
983 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
985 _EqRng __xeq = __x.equal_range(__i->first);
986 _EqRng __yeq = __y.equal_range(__i->first);
987 if (_VSTD::distance(__xeq.first, __xeq.second) !=
988 _VSTD::distance(__yeq.first, __yeq.second) ||
989 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
996 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
997 inline _LIBCPP_INLINE_VISIBILITY
999 operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1000 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1002 return !(__x == __y);
1007 #endif // _LIBCPP_HASH_MAP