Warning, /include/c++/v1/ext/hash_map is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP_HASH_MAP
0011 #define _LIBCPP_HASH_MAP
0012
0013 /*
0014
0015 hash_map synopsis
0016
0017 namespace __gnu_cxx
0018 {
0019
0020 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
0021 class Alloc = allocator<pair<const Key, T>>>
0022 class hash_map
0023 {
0024 public:
0025 // types
0026 typedef Key key_type;
0027 typedef T mapped_type;
0028 typedef Hash hasher;
0029 typedef Pred key_equal;
0030 typedef Alloc allocator_type;
0031 typedef pair<const key_type, mapped_type> value_type;
0032 typedef value_type& reference;
0033 typedef const value_type& const_reference;
0034 typedef typename allocator_traits<allocator_type>::pointer pointer;
0035 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0036 typedef typename allocator_traits<allocator_type>::size_type size_type;
0037 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0038
0039 typedef /unspecified/ iterator;
0040 typedef /unspecified/ const_iterator;
0041
0042 hash_map();
0043 explicit hash_map(size_type n, const hasher& hf = hasher(),
0044 const key_equal& eql = key_equal(),
0045 const allocator_type& a = allocator_type());
0046 template <class InputIterator>
0047 hash_map(InputIterator f, InputIterator l);
0048 template <class InputIterator>
0049 hash_map(InputIterator f, InputIterator l,
0050 size_type n, const hasher& hf = hasher(),
0051 const key_equal& eql = key_equal(),
0052 const allocator_type& a = allocator_type());
0053 hash_map(const hash_map&);
0054 ~hash_map();
0055 hash_map& operator=(const hash_map&);
0056
0057 allocator_type get_allocator() const;
0058
0059 bool empty() const;
0060 size_type size() const;
0061 size_type max_size() const;
0062
0063 iterator begin();
0064 iterator end();
0065 const_iterator begin() const;
0066 const_iterator end() const;
0067
0068 pair<iterator, bool> insert(const value_type& obj);
0069 template <class InputIterator>
0070 void insert(InputIterator first, InputIterator last);
0071
0072 void erase(const_iterator position);
0073 size_type erase(const key_type& k);
0074 void erase(const_iterator first, const_iterator last);
0075 void clear();
0076
0077 void swap(hash_map&);
0078
0079 hasher hash_funct() const;
0080 key_equal key_eq() const;
0081
0082 iterator find(const key_type& k);
0083 const_iterator find(const key_type& k) const;
0084 size_type count(const key_type& k) const;
0085 pair<iterator, iterator> equal_range(const key_type& k);
0086 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
0087
0088 mapped_type& operator[](const key_type& k);
0089
0090 size_type bucket_count() const;
0091 size_type max_bucket_count() const;
0092
0093 size_type elems_in_bucket(size_type n) const;
0094
0095 void resize(size_type n);
0096 };
0097
0098 template <class Key, class T, class Hash, class Pred, class Alloc>
0099 void swap(hash_map<Key, T, Hash, Pred, Alloc>& x,
0100 hash_map<Key, T, Hash, Pred, Alloc>& y);
0101
0102 template <class Key, class T, class Hash, class Pred, class Alloc>
0103 bool
0104 operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x,
0105 const hash_map<Key, T, Hash, Pred, Alloc>& y);
0106
0107 template <class Key, class T, class Hash, class Pred, class Alloc>
0108 bool
0109 operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x,
0110 const hash_map<Key, T, Hash, Pred, Alloc>& y);
0111
0112 template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
0113 class Alloc = allocator<pair<const Key, T>>>
0114 class hash_multimap
0115 {
0116 public:
0117 // types
0118 typedef Key key_type;
0119 typedef T mapped_type;
0120 typedef Hash hasher;
0121 typedef Pred key_equal;
0122 typedef Alloc allocator_type;
0123 typedef pair<const key_type, mapped_type> value_type;
0124 typedef value_type& reference;
0125 typedef const value_type& const_reference;
0126 typedef typename allocator_traits<allocator_type>::pointer pointer;
0127 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0128 typedef typename allocator_traits<allocator_type>::size_type size_type;
0129 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0130
0131 typedef /unspecified/ iterator;
0132 typedef /unspecified/ const_iterator;
0133
0134 explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(),
0135 const key_equal& eql = key_equal(),
0136 const allocator_type& a = allocator_type());
0137 template <class InputIterator>
0138 hash_multimap(InputIterator f, InputIterator l,
0139 size_type n = 193, const hasher& hf = hasher(),
0140 const key_equal& eql = key_equal(),
0141 const allocator_type& a = allocator_type());
0142 explicit hash_multimap(const allocator_type&);
0143 hash_multimap(const hash_multimap&);
0144 ~hash_multimap();
0145 hash_multimap& operator=(const hash_multimap&);
0146
0147 allocator_type get_allocator() const;
0148
0149 bool empty() const;
0150 size_type size() const;
0151 size_type max_size() const;
0152
0153 iterator begin();
0154 iterator end();
0155 const_iterator begin() const;
0156 const_iterator end() const;
0157
0158 iterator insert(const value_type& obj);
0159 template <class InputIterator>
0160 void insert(InputIterator first, InputIterator last);
0161
0162 void erase(const_iterator position);
0163 size_type erase(const key_type& k);
0164 void erase(const_iterator first, const_iterator last);
0165 void clear();
0166
0167 void swap(hash_multimap&);
0168
0169 hasher hash_funct() const;
0170 key_equal key_eq() const;
0171
0172 iterator find(const key_type& k);
0173 const_iterator find(const key_type& k) const;
0174 size_type count(const key_type& k) const;
0175 pair<iterator, iterator> equal_range(const key_type& k);
0176 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
0177
0178 size_type bucket_count() const;
0179 size_type max_bucket_count() const;
0180
0181 size_type elems_in_bucket(size_type n) const;
0182
0183 void resize(size_type n);
0184 };
0185
0186 template <class Key, class T, class Hash, class Pred, class Alloc>
0187 void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x,
0188 hash_multimap<Key, T, Hash, Pred, Alloc>& y);
0189
0190 template <class Key, class T, class Hash, class Pred, class Alloc>
0191 bool
0192 operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
0193 const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
0194
0195 template <class Key, class T, class Hash, class Pred, class Alloc>
0196 bool
0197 operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x,
0198 const hash_multimap<Key, T, Hash, Pred, Alloc>& y);
0199
0200 } // __gnu_cxx
0201
0202 */
0203
0204 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0205 # include <__cxx03/ext/hash_map>
0206 #else
0207 # include <__config>
0208 # include <__hash_table>
0209 # include <algorithm>
0210 # include <ext/__hash>
0211 # include <functional>
0212
0213 # if defined(__DEPRECATED) && __DEPRECATED
0214 # if defined(_LIBCPP_WARNING)
0215 _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")
0216 # else
0217 # warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>
0218 # endif
0219 # endif
0220
0221 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0222 # pragma GCC system_header
0223 # endif
0224
0225 namespace __gnu_cxx {
0226
0227 template <class _Tp, class _Hash, bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value >
0228 class __hash_map_hasher : private _Hash {
0229 public:
0230 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {}
0231 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
0232 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return *this; }
0233 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); }
0234 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const {
0235 return static_cast<const _Hash&>(*this)(__x);
0236 }
0237 };
0238
0239 template <class _Tp, class _Hash>
0240 class __hash_map_hasher<_Tp, _Hash, false> {
0241 _Hash __hash_;
0242
0243 public:
0244 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {}
0245 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
0246 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; }
0247 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); }
0248 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); }
0249 };
0250
0251 template <class _Tp, class _Pred, bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value >
0252 class __hash_map_equal : private _Pred {
0253 public:
0254 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {}
0255 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
0256 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return *this; }
0257 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const {
0258 return static_cast<const _Pred&>(*this)(__x.first, __y.first);
0259 }
0260 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
0261 return static_cast<const _Pred&>(*this)(__x, __y.first);
0262 }
0263 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
0264 return static_cast<const _Pred&>(*this)(__x.first, __y);
0265 }
0266 _LIBCPP_HIDE_FROM_ABI bool
0267 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
0268 return static_cast<const _Pred&>(*this)(__x, __y);
0269 }
0270 };
0271
0272 template <class _Tp, class _Pred>
0273 class __hash_map_equal<_Tp, _Pred, false> {
0274 _Pred __pred_;
0275
0276 public:
0277 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {}
0278 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
0279 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; }
0280 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); }
0281 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
0282 return __pred_(__x, __y.first);
0283 }
0284 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
0285 return __pred_(__x.first, __y);
0286 }
0287 _LIBCPP_HIDE_FROM_ABI bool
0288 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
0289 return __pred_(__x, __y);
0290 }
0291 };
0292
0293 template <class _Alloc>
0294 class __hash_map_node_destructor {
0295 typedef _Alloc allocator_type;
0296 typedef std::allocator_traits<allocator_type> __alloc_traits;
0297 typedef typename __alloc_traits::value_type::__node_value_type value_type;
0298
0299 public:
0300 typedef typename __alloc_traits::pointer pointer;
0301
0302 private:
0303 typedef typename value_type::first_type first_type;
0304 typedef typename value_type::second_type second_type;
0305
0306 allocator_type& __na_;
0307
0308 public:
0309 bool __first_constructed;
0310 bool __second_constructed;
0311
0312 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default;
0313 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
0314
0315 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na)
0316 : __na_(__na), __first_constructed(false), __second_constructed(false) {}
0317
0318 # ifndef _LIBCPP_CXX03_LANG
0319 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x)
0320 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
0321 __x.__value_constructed = false;
0322 }
0323 # else // _LIBCPP_CXX03_LANG
0324 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x)
0325 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
0326 const_cast<bool&>(__x.__value_constructed) = false;
0327 }
0328 # endif // _LIBCPP_CXX03_LANG
0329
0330 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) {
0331 if (__second_constructed)
0332 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));
0333 if (__first_constructed)
0334 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));
0335 if (__p)
0336 __alloc_traits::deallocate(__na_, __p, 1);
0337 }
0338 };
0339
0340 template <class _HashIterator>
0341 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
0342 _HashIterator __i_;
0343
0344 typedef const typename _HashIterator::value_type::first_type key_type;
0345 typedef typename _HashIterator::value_type::second_type mapped_type;
0346
0347 public:
0348 typedef std::forward_iterator_tag iterator_category;
0349 typedef std::pair<key_type, mapped_type> value_type;
0350 typedef typename _HashIterator::difference_type difference_type;
0351 typedef value_type& reference;
0352 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> pointer;
0353
0354 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {}
0355
0356 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
0357
0358 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
0359 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
0360
0361 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
0362 ++__i_;
0363 return *this;
0364 }
0365 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
0366 __hash_map_iterator __t(*this);
0367 ++(*this);
0368 return __t;
0369 }
0370
0371 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
0372 return __x.__i_ == __y.__i_;
0373 }
0374 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
0375 return __x.__i_ != __y.__i_;
0376 }
0377
0378 template <class, class, class, class, class>
0379 friend class _LIBCPP_TEMPLATE_VIS hash_map;
0380 template <class, class, class, class, class>
0381 friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
0382 template <class>
0383 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
0384 template <class>
0385 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
0386 template <class>
0387 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
0388 };
0389
0390 template <class _HashIterator>
0391 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
0392 _HashIterator __i_;
0393
0394 typedef const typename _HashIterator::value_type::first_type key_type;
0395 typedef typename _HashIterator::value_type::second_type mapped_type;
0396
0397 public:
0398 typedef std::forward_iterator_tag iterator_category;
0399 typedef std::pair<key_type, mapped_type> value_type;
0400 typedef typename _HashIterator::difference_type difference_type;
0401 typedef const value_type& reference;
0402 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> pointer;
0403
0404 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {}
0405
0406 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
0407 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
0408 : __i_(__i.__i_) {}
0409
0410 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
0411 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
0412
0413 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
0414 ++__i_;
0415 return *this;
0416 }
0417 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
0418 __hash_map_const_iterator __t(*this);
0419 ++(*this);
0420 return __t;
0421 }
0422
0423 friend _LIBCPP_HIDE_FROM_ABI bool
0424 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
0425 return __x.__i_ == __y.__i_;
0426 }
0427 friend _LIBCPP_HIDE_FROM_ABI bool
0428 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
0429 return __x.__i_ != __y.__i_;
0430 }
0431
0432 template <class, class, class, class, class>
0433 friend class _LIBCPP_TEMPLATE_VIS hash_map;
0434 template <class, class, class, class, class>
0435 friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
0436 template <class>
0437 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
0438 template <class>
0439 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
0440 };
0441
0442 template <class _Key,
0443 class _Tp,
0444 class _Hash = hash<_Key>,
0445 class _Pred = std::equal_to<_Key>,
0446 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
0447 class _LIBCPP_TEMPLATE_VIS hash_map {
0448 public:
0449 // types
0450 typedef _Key key_type;
0451 typedef _Tp mapped_type;
0452 typedef _Tp data_type;
0453 typedef _Hash hasher;
0454 typedef _Pred key_equal;
0455 typedef _Alloc allocator_type;
0456 typedef std::pair<const key_type, mapped_type> value_type;
0457 typedef value_type& reference;
0458 typedef const value_type& const_reference;
0459
0460 private:
0461 typedef std::pair<key_type, mapped_type> __value_type;
0462 typedef __hash_map_hasher<__value_type, hasher> __hasher;
0463 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
0464 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
0465
0466 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
0467
0468 __table __table_;
0469
0470 typedef typename __table::__node_pointer __node_pointer;
0471 typedef typename __table::__node_const_pointer __node_const_pointer;
0472 typedef typename __table::__node_traits __node_traits;
0473 typedef typename __table::__node_allocator __node_allocator;
0474 typedef typename __table::__node __node;
0475 typedef __hash_map_node_destructor<__node_allocator> _Dp;
0476 typedef std::unique_ptr<__node, _Dp> __node_holder;
0477 typedef std::allocator_traits<allocator_type> __alloc_traits;
0478
0479 public:
0480 typedef typename __alloc_traits::pointer pointer;
0481 typedef typename __alloc_traits::const_pointer const_pointer;
0482 typedef typename __alloc_traits::size_type size_type;
0483 typedef typename __alloc_traits::difference_type difference_type;
0484
0485 typedef __hash_map_iterator<typename __table::iterator> iterator;
0486 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
0487
0488 _LIBCPP_HIDE_FROM_ABI hash_map() {}
0489 explicit _LIBCPP_HIDE_FROM_ABI
0490 hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0491 _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0492 template <class _InputIterator>
0493 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last);
0494 template <class _InputIterator>
0495 _LIBCPP_HIDE_FROM_ABI
0496 hash_map(_InputIterator __first,
0497 _InputIterator __last,
0498 size_type __n,
0499 const hasher& __hf = hasher(),
0500 const key_equal& __eql = key_equal());
0501 template <class _InputIterator>
0502 _LIBCPP_HIDE_FROM_ABI
0503 hash_map(_InputIterator __first,
0504 _InputIterator __last,
0505 size_type __n,
0506 const hasher& __hf,
0507 const key_equal& __eql,
0508 const allocator_type& __a);
0509 _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u);
0510
0511 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0512
0513 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0514 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0515 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0516
0517 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0518 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0519 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0520 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0521
0522 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
0523 return __table_.__insert_unique(__x);
0524 }
0525 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
0526 template <class _InputIterator>
0527 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0528
0529 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
0530 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
0531 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
0532 __table_.erase(__first.__i_, __last.__i_);
0533 }
0534 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0535
0536 _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); }
0537
0538 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
0539 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
0540
0541 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0542 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0543 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
0544 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0545 return __table_.__equal_range_unique(__k);
0546 }
0547 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0548 return __table_.__equal_range_unique(__k);
0549 }
0550
0551 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
0552
0553 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0554 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0555
0556 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0557
0558 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
0559
0560 private:
0561 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k);
0562 };
0563
0564 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0565 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql)
0566 : __table_(__hf, __eql) {
0567 __table_.__rehash_unique(__n);
0568 }
0569
0570 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0571 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
0572 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0573 : __table_(__hf, __eql, __a) {
0574 __table_.__rehash_unique(__n);
0575 }
0576
0577 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0578 template <class _InputIterator>
0579 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) {
0580 insert(__first, __last);
0581 }
0582
0583 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0584 template <class _InputIterator>
0585 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
0586 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0587 : __table_(__hf, __eql) {
0588 __table_.__rehash_unique(__n);
0589 insert(__first, __last);
0590 }
0591
0592 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0593 template <class _InputIterator>
0594 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
0595 _InputIterator __first,
0596 _InputIterator __last,
0597 size_type __n,
0598 const hasher& __hf,
0599 const key_equal& __eql,
0600 const allocator_type& __a)
0601 : __table_(__hf, __eql, __a) {
0602 __table_.__rehash_unique(__n);
0603 insert(__first, __last);
0604 }
0605
0606 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0607 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) {
0608 __table_.__rehash_unique(__u.bucket_count());
0609 insert(__u.begin(), __u.end());
0610 }
0611
0612 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0613 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
0614 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) {
0615 __node_allocator& __na = __table_.__node_alloc();
0616 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
0617 __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);
0618 __h.get_deleter().__first_constructed = true;
0619 __node_traits::construct(__na, std::addressof(__h->__get_value().second));
0620 __h.get_deleter().__second_constructed = true;
0621 return __h;
0622 }
0623
0624 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0625 template <class _InputIterator>
0626 inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0627 for (; __first != __last; ++__first)
0628 __table_.__insert_unique(*__first);
0629 }
0630
0631 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0632 _Tp& hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
0633 iterator __i = find(__k);
0634 if (__i != end())
0635 return __i->second;
0636 __node_holder __h = __construct_node(__k);
0637 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
0638 __h.release();
0639 return __r.first->second;
0640 }
0641
0642 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0643 inline _LIBCPP_HIDE_FROM_ABI void
0644 swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0645 __x.swap(__y);
0646 }
0647
0648 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0649 _LIBCPP_HIDE_FROM_ABI bool
0650 operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0651 if (__x.size() != __y.size())
0652 return false;
0653 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0654 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
0655 const_iterator __j = __y.find(__i->first);
0656 if (__j == __ey || !(*__i == *__j))
0657 return false;
0658 }
0659 return true;
0660 }
0661
0662 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0663 inline _LIBCPP_HIDE_FROM_ABI bool
0664 operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0665 return !(__x == __y);
0666 }
0667
0668 template <class _Key,
0669 class _Tp,
0670 class _Hash = hash<_Key>,
0671 class _Pred = std::equal_to<_Key>,
0672 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
0673 class _LIBCPP_TEMPLATE_VIS hash_multimap {
0674 public:
0675 // types
0676 typedef _Key key_type;
0677 typedef _Tp mapped_type;
0678 typedef _Tp data_type;
0679 typedef _Hash hasher;
0680 typedef _Pred key_equal;
0681 typedef _Alloc allocator_type;
0682 typedef std::pair<const key_type, mapped_type> value_type;
0683 typedef value_type& reference;
0684 typedef const value_type& const_reference;
0685
0686 private:
0687 typedef std::pair<key_type, mapped_type> __value_type;
0688 typedef __hash_map_hasher<__value_type, hasher> __hasher;
0689 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
0690 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
0691
0692 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
0693
0694 __table __table_;
0695
0696 typedef typename __table::__node_traits __node_traits;
0697 typedef typename __table::__node_allocator __node_allocator;
0698 typedef typename __table::__node __node;
0699 typedef __hash_map_node_destructor<__node_allocator> _Dp;
0700 typedef std::unique_ptr<__node, _Dp> __node_holder;
0701 typedef std::allocator_traits<allocator_type> __alloc_traits;
0702
0703 public:
0704 typedef typename __alloc_traits::pointer pointer;
0705 typedef typename __alloc_traits::const_pointer const_pointer;
0706 typedef typename __alloc_traits::size_type size_type;
0707 typedef typename __alloc_traits::difference_type difference_type;
0708
0709 typedef __hash_map_iterator<typename __table::iterator> iterator;
0710 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
0711
0712 _LIBCPP_HIDE_FROM_ABI hash_multimap() {}
0713 explicit _LIBCPP_HIDE_FROM_ABI
0714 hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0715 _LIBCPP_HIDE_FROM_ABI
0716 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0717 template <class _InputIterator>
0718 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last);
0719 template <class _InputIterator>
0720 _LIBCPP_HIDE_FROM_ABI
0721 hash_multimap(_InputIterator __first,
0722 _InputIterator __last,
0723 size_type __n,
0724 const hasher& __hf = hasher(),
0725 const key_equal& __eql = key_equal());
0726 template <class _InputIterator>
0727 _LIBCPP_HIDE_FROM_ABI hash_multimap(
0728 _InputIterator __first,
0729 _InputIterator __last,
0730 size_type __n,
0731 const hasher& __hf,
0732 const key_equal& __eql,
0733 const allocator_type& __a);
0734 _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u);
0735
0736 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0737
0738 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0739 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0740 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0741
0742 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0743 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0744 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0745 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0746
0747 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
0748 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
0749 template <class _InputIterator>
0750 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0751
0752 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
0753 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
0754 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
0755 __table_.erase(__first.__i_, __last.__i_);
0756 }
0757 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0758
0759 _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); }
0760
0761 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
0762 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
0763
0764 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0765 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0766 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
0767 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0768 return __table_.__equal_range_multi(__k);
0769 }
0770 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0771 return __table_.__equal_range_multi(__k);
0772 }
0773
0774 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0775 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0776
0777 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0778
0779 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
0780 };
0781
0782 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0783 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql)
0784 : __table_(__hf, __eql) {
0785 __table_.__rehash_multi(__n);
0786 }
0787
0788 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0789 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
0790 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0791 : __table_(__hf, __eql, __a) {
0792 __table_.__rehash_multi(__n);
0793 }
0794
0795 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0796 template <class _InputIterator>
0797 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) {
0798 insert(__first, __last);
0799 }
0800
0801 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0802 template <class _InputIterator>
0803 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
0804 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0805 : __table_(__hf, __eql) {
0806 __table_.__rehash_multi(__n);
0807 insert(__first, __last);
0808 }
0809
0810 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0811 template <class _InputIterator>
0812 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
0813 _InputIterator __first,
0814 _InputIterator __last,
0815 size_type __n,
0816 const hasher& __hf,
0817 const key_equal& __eql,
0818 const allocator_type& __a)
0819 : __table_(__hf, __eql, __a) {
0820 __table_.__rehash_multi(__n);
0821 insert(__first, __last);
0822 }
0823
0824 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0825 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) {
0826 __table_.__rehash_multi(__u.bucket_count());
0827 insert(__u.begin(), __u.end());
0828 }
0829
0830 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0831 template <class _InputIterator>
0832 inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0833 for (; __first != __last; ++__first)
0834 __table_.__insert_multi(*__first);
0835 }
0836
0837 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0838 inline _LIBCPP_HIDE_FROM_ABI void
0839 swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0840 __x.swap(__y);
0841 }
0842
0843 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0844 _LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
0845 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0846 if (__x.size() != __y.size())
0847 return false;
0848 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0849 typedef std::pair<const_iterator, const_iterator> _EqRng;
0850 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
0851 _EqRng __xeq = __x.equal_range(__i->first);
0852 _EqRng __yeq = __y.equal_range(__i->first);
0853 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
0854 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
0855 return false;
0856 __i = __xeq.second;
0857 }
0858 return true;
0859 }
0860
0861 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0862 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
0863 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0864 return !(__x == __y);
0865 }
0866
0867 } // namespace __gnu_cxx
0868
0869 # if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0870 # include <concepts>
0871 # include <iterator>
0872 # include <type_traits>
0873 # endif
0874 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0875
0876 #endif // _LIBCPP_HASH_MAP
