Warning, /include/c++/v1/__cxx03/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___CXX03_HASH_MAP
0011 #define _LIBCPP___CXX03_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 #include <__cxx03/__config>
0205 #include <__cxx03/__hash_table>
0206 #include <__cxx03/algorithm>
0207 #include <__cxx03/ext/__hash>
0208 #include <__cxx03/functional>
0209
0210 #if defined(__DEPRECATED) && __DEPRECATED
0211 # if defined(_LIBCPP_WARNING)
0212 _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")
0213 # else
0214 # warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>
0215 # endif
0216 #endif
0217
0218 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0219 # pragma GCC system_header
0220 #endif
0221
0222 namespace __gnu_cxx {
0223
0224 template <class _Tp, class _Hash, bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value >
0225 class __hash_map_hasher : private _Hash {
0226 public:
0227 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {}
0228 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {}
0229 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return *this; }
0230 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); }
0231 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const {
0232 return static_cast<const _Hash&>(*this)(__x);
0233 }
0234 };
0235
0236 template <class _Tp, class _Hash>
0237 class __hash_map_hasher<_Tp, _Hash, false> {
0238 _Hash __hash_;
0239
0240 public:
0241 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {}
0242 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {}
0243 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; }
0244 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); }
0245 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); }
0246 };
0247
0248 template <class _Tp, class _Pred, bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value >
0249 class __hash_map_equal : private _Pred {
0250 public:
0251 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {}
0252 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {}
0253 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return *this; }
0254 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const {
0255 return static_cast<const _Pred&>(*this)(__x.first, __y.first);
0256 }
0257 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
0258 return static_cast<const _Pred&>(*this)(__x, __y.first);
0259 }
0260 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
0261 return static_cast<const _Pred&>(*this)(__x.first, __y);
0262 }
0263 _LIBCPP_HIDE_FROM_ABI bool
0264 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
0265 return static_cast<const _Pred&>(*this)(__x, __y);
0266 }
0267 };
0268
0269 template <class _Tp, class _Pred>
0270 class __hash_map_equal<_Tp, _Pred, false> {
0271 _Pred __pred_;
0272
0273 public:
0274 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {}
0275 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {}
0276 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; }
0277 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); }
0278 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const {
0279 return __pred_(__x, __y.first);
0280 }
0281 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const {
0282 return __pred_(__x.first, __y);
0283 }
0284 _LIBCPP_HIDE_FROM_ABI bool
0285 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const {
0286 return __pred_(__x, __y);
0287 }
0288 };
0289
0290 template <class _Alloc>
0291 class __hash_map_node_destructor {
0292 typedef _Alloc allocator_type;
0293 typedef std::allocator_traits<allocator_type> __alloc_traits;
0294 typedef typename __alloc_traits::value_type::__node_value_type value_type;
0295
0296 public:
0297 typedef typename __alloc_traits::pointer pointer;
0298
0299 private:
0300 typedef typename value_type::first_type first_type;
0301 typedef typename value_type::second_type second_type;
0302
0303 allocator_type& __na_;
0304
0305 public:
0306 bool __first_constructed;
0307 bool __second_constructed;
0308
0309 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default;
0310 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;
0311
0312 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na)
0313 : __na_(__na), __first_constructed(false), __second_constructed(false) {}
0314
0315 #ifndef _LIBCPP_CXX03_LANG
0316 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x)
0317 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
0318 __x.__value_constructed = false;
0319 }
0320 #else // _LIBCPP_CXX03_LANG
0321 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x)
0322 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
0323 const_cast<bool&>(__x.__value_constructed) = false;
0324 }
0325 #endif // _LIBCPP_CXX03_LANG
0326
0327 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) {
0328 if (__second_constructed)
0329 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));
0330 if (__first_constructed)
0331 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));
0332 if (__p)
0333 __alloc_traits::deallocate(__na_, __p, 1);
0334 }
0335 };
0336
0337 template <class _HashIterator>
0338 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
0339 _HashIterator __i_;
0340
0341 typedef const typename _HashIterator::value_type::first_type key_type;
0342 typedef typename _HashIterator::value_type::second_type mapped_type;
0343
0344 public:
0345 typedef std::forward_iterator_tag iterator_category;
0346 typedef std::pair<key_type, mapped_type> value_type;
0347 typedef typename _HashIterator::difference_type difference_type;
0348 typedef value_type& reference;
0349 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> pointer;
0350
0351 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {}
0352
0353 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {}
0354
0355 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
0356 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
0357
0358 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
0359 ++__i_;
0360 return *this;
0361 }
0362 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
0363 __hash_map_iterator __t(*this);
0364 ++(*this);
0365 return __t;
0366 }
0367
0368 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
0369 return __x.__i_ == __y.__i_;
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
0375 template <class, class, class, class, class>
0376 friend class _LIBCPP_TEMPLATE_VIS hash_map;
0377 template <class, class, class, class, class>
0378 friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
0379 template <class>
0380 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
0381 template <class>
0382 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
0383 template <class>
0384 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
0385 };
0386
0387 template <class _HashIterator>
0388 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
0389 _HashIterator __i_;
0390
0391 typedef const typename _HashIterator::value_type::first_type key_type;
0392 typedef typename _HashIterator::value_type::second_type mapped_type;
0393
0394 public:
0395 typedef std::forward_iterator_tag iterator_category;
0396 typedef std::pair<key_type, mapped_type> value_type;
0397 typedef typename _HashIterator::difference_type difference_type;
0398 typedef const value_type& reference;
0399 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> pointer;
0400
0401 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {}
0402
0403 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {}
0404 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i)
0405 : __i_(__i.__i_) {}
0406
0407 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); }
0408 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); }
0409
0410 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
0411 ++__i_;
0412 return *this;
0413 }
0414 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
0415 __hash_map_const_iterator __t(*this);
0416 ++(*this);
0417 return __t;
0418 }
0419
0420 friend _LIBCPP_HIDE_FROM_ABI bool
0421 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
0422 return __x.__i_ == __y.__i_;
0423 }
0424 friend _LIBCPP_HIDE_FROM_ABI bool
0425 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
0426 return __x.__i_ != __y.__i_;
0427 }
0428
0429 template <class, class, class, class, class>
0430 friend class _LIBCPP_TEMPLATE_VIS hash_map;
0431 template <class, class, class, class, class>
0432 friend class _LIBCPP_TEMPLATE_VIS hash_multimap;
0433 template <class>
0434 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
0435 template <class>
0436 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
0437 };
0438
0439 template <class _Key,
0440 class _Tp,
0441 class _Hash = hash<_Key>,
0442 class _Pred = std::equal_to<_Key>,
0443 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
0444 class _LIBCPP_TEMPLATE_VIS hash_map {
0445 public:
0446 // types
0447 typedef _Key key_type;
0448 typedef _Tp mapped_type;
0449 typedef _Tp data_type;
0450 typedef _Hash hasher;
0451 typedef _Pred key_equal;
0452 typedef _Alloc allocator_type;
0453 typedef std::pair<const key_type, mapped_type> value_type;
0454 typedef value_type& reference;
0455 typedef const value_type& const_reference;
0456
0457 private:
0458 typedef std::pair<key_type, mapped_type> __value_type;
0459 typedef __hash_map_hasher<__value_type, hasher> __hasher;
0460 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
0461 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
0462
0463 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
0464
0465 __table __table_;
0466
0467 typedef typename __table::__node_pointer __node_pointer;
0468 typedef typename __table::__node_const_pointer __node_const_pointer;
0469 typedef typename __table::__node_traits __node_traits;
0470 typedef typename __table::__node_allocator __node_allocator;
0471 typedef typename __table::__node __node;
0472 typedef __hash_map_node_destructor<__node_allocator> _Dp;
0473 typedef std::unique_ptr<__node, _Dp> __node_holder;
0474 typedef std::allocator_traits<allocator_type> __alloc_traits;
0475
0476 public:
0477 typedef typename __alloc_traits::pointer pointer;
0478 typedef typename __alloc_traits::const_pointer const_pointer;
0479 typedef typename __alloc_traits::size_type size_type;
0480 typedef typename __alloc_traits::difference_type difference_type;
0481
0482 typedef __hash_map_iterator<typename __table::iterator> iterator;
0483 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
0484
0485 _LIBCPP_HIDE_FROM_ABI hash_map() {}
0486 explicit _LIBCPP_HIDE_FROM_ABI
0487 hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0488 _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0489 template <class _InputIterator>
0490 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last);
0491 template <class _InputIterator>
0492 _LIBCPP_HIDE_FROM_ABI
0493 hash_map(_InputIterator __first,
0494 _InputIterator __last,
0495 size_type __n,
0496 const hasher& __hf = hasher(),
0497 const key_equal& __eql = key_equal());
0498 template <class _InputIterator>
0499 _LIBCPP_HIDE_FROM_ABI
0500 hash_map(_InputIterator __first,
0501 _InputIterator __last,
0502 size_type __n,
0503 const hasher& __hf,
0504 const key_equal& __eql,
0505 const allocator_type& __a);
0506 _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u);
0507
0508 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0509
0510 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0511 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0512 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0513
0514 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0515 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0516 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0517 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0518
0519 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
0520 return __table_.__insert_unique(__x);
0521 }
0522 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
0523 template <class _InputIterator>
0524 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0525
0526 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
0527 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
0528 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
0529 __table_.erase(__first.__i_, __last.__i_);
0530 }
0531 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0532
0533 _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); }
0534
0535 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
0536 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
0537
0538 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0539 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0540 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
0541 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0542 return __table_.__equal_range_unique(__k);
0543 }
0544 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0545 return __table_.__equal_range_unique(__k);
0546 }
0547
0548 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
0549
0550 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0551 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0552
0553 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0554
0555 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
0556
0557 private:
0558 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k);
0559 };
0560
0561 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0562 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql)
0563 : __table_(__hf, __eql) {
0564 __table_.__rehash_unique(__n);
0565 }
0566
0567 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0568 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
0569 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0570 : __table_(__hf, __eql, __a) {
0571 __table_.__rehash_unique(__n);
0572 }
0573
0574 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0575 template <class _InputIterator>
0576 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) {
0577 insert(__first, __last);
0578 }
0579
0580 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0581 template <class _InputIterator>
0582 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
0583 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0584 : __table_(__hf, __eql) {
0585 __table_.__rehash_unique(__n);
0586 insert(__first, __last);
0587 }
0588
0589 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0590 template <class _InputIterator>
0591 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(
0592 _InputIterator __first,
0593 _InputIterator __last,
0594 size_type __n,
0595 const hasher& __hf,
0596 const key_equal& __eql,
0597 const allocator_type& __a)
0598 : __table_(__hf, __eql, __a) {
0599 __table_.__rehash_unique(__n);
0600 insert(__first, __last);
0601 }
0602
0603 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0604 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) {
0605 __table_.__rehash_unique(__u.bucket_count());
0606 insert(__u.begin(), __u.end());
0607 }
0608
0609 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0610 typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
0611 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) {
0612 __node_allocator& __na = __table_.__node_alloc();
0613 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
0614 __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);
0615 __h.get_deleter().__first_constructed = true;
0616 __node_traits::construct(__na, std::addressof(__h->__get_value().second));
0617 __h.get_deleter().__second_constructed = true;
0618 return __h;
0619 }
0620
0621 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0622 template <class _InputIterator>
0623 inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0624 for (; __first != __last; ++__first)
0625 __table_.__insert_unique(*__first);
0626 }
0627
0628 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0629 _Tp& hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
0630 iterator __i = find(__k);
0631 if (__i != end())
0632 return __i->second;
0633 __node_holder __h = __construct_node(__k);
0634 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
0635 __h.release();
0636 return __r.first->second;
0637 }
0638
0639 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0640 inline _LIBCPP_HIDE_FROM_ABI void
0641 swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0642 __x.swap(__y);
0643 }
0644
0645 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0646 _LIBCPP_HIDE_FROM_ABI bool
0647 operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0648 if (__x.size() != __y.size())
0649 return false;
0650 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0651 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
0652 const_iterator __j = __y.find(__i->first);
0653 if (__j == __ey || !(*__i == *__j))
0654 return false;
0655 }
0656 return true;
0657 }
0658
0659 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0660 inline _LIBCPP_HIDE_FROM_ABI bool
0661 operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0662 return !(__x == __y);
0663 }
0664
0665 template <class _Key,
0666 class _Tp,
0667 class _Hash = hash<_Key>,
0668 class _Pred = std::equal_to<_Key>,
0669 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
0670 class _LIBCPP_TEMPLATE_VIS hash_multimap {
0671 public:
0672 // types
0673 typedef _Key key_type;
0674 typedef _Tp mapped_type;
0675 typedef _Tp data_type;
0676 typedef _Hash hasher;
0677 typedef _Pred key_equal;
0678 typedef _Alloc allocator_type;
0679 typedef std::pair<const key_type, mapped_type> value_type;
0680 typedef value_type& reference;
0681 typedef const value_type& const_reference;
0682
0683 private:
0684 typedef std::pair<key_type, mapped_type> __value_type;
0685 typedef __hash_map_hasher<__value_type, hasher> __hasher;
0686 typedef __hash_map_equal<__value_type, key_equal> __key_equal;
0687 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type;
0688
0689 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
0690
0691 __table __table_;
0692
0693 typedef typename __table::__node_traits __node_traits;
0694 typedef typename __table::__node_allocator __node_allocator;
0695 typedef typename __table::__node __node;
0696 typedef __hash_map_node_destructor<__node_allocator> _Dp;
0697 typedef std::unique_ptr<__node, _Dp> __node_holder;
0698 typedef std::allocator_traits<allocator_type> __alloc_traits;
0699
0700 public:
0701 typedef typename __alloc_traits::pointer pointer;
0702 typedef typename __alloc_traits::const_pointer const_pointer;
0703 typedef typename __alloc_traits::size_type size_type;
0704 typedef typename __alloc_traits::difference_type difference_type;
0705
0706 typedef __hash_map_iterator<typename __table::iterator> iterator;
0707 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
0708
0709 _LIBCPP_HIDE_FROM_ABI hash_multimap() {}
0710 explicit _LIBCPP_HIDE_FROM_ABI
0711 hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
0712 _LIBCPP_HIDE_FROM_ABI
0713 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
0714 template <class _InputIterator>
0715 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last);
0716 template <class _InputIterator>
0717 _LIBCPP_HIDE_FROM_ABI
0718 hash_multimap(_InputIterator __first,
0719 _InputIterator __last,
0720 size_type __n,
0721 const hasher& __hf = hasher(),
0722 const key_equal& __eql = key_equal());
0723 template <class _InputIterator>
0724 _LIBCPP_HIDE_FROM_ABI hash_multimap(
0725 _InputIterator __first,
0726 _InputIterator __last,
0727 size_type __n,
0728 const hasher& __hf,
0729 const key_equal& __eql,
0730 const allocator_type& __a);
0731 _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u);
0732
0733 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
0734
0735 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
0736 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
0737 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
0738
0739 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
0740 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
0741 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
0742 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
0743
0744 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
0745 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
0746 template <class _InputIterator>
0747 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
0748
0749 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); }
0750 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
0751 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) {
0752 __table_.erase(__first.__i_, __last.__i_);
0753 }
0754 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
0755
0756 _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); }
0757
0758 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); }
0759 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
0760
0761 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
0762 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
0763 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
0764 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
0765 return __table_.__equal_range_multi(__k);
0766 }
0767 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0768 return __table_.__equal_range_multi(__k);
0769 }
0770
0771 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
0772 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
0773
0774 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
0775
0776 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
0777 };
0778
0779 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0780 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql)
0781 : __table_(__hf, __eql) {
0782 __table_.__rehash_multi(__n);
0783 }
0784
0785 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0786 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
0787 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
0788 : __table_(__hf, __eql, __a) {
0789 __table_.__rehash_multi(__n);
0790 }
0791
0792 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0793 template <class _InputIterator>
0794 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) {
0795 insert(__first, __last);
0796 }
0797
0798 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0799 template <class _InputIterator>
0800 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
0801 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
0802 : __table_(__hf, __eql) {
0803 __table_.__rehash_multi(__n);
0804 insert(__first, __last);
0805 }
0806
0807 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0808 template <class _InputIterator>
0809 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(
0810 _InputIterator __first,
0811 _InputIterator __last,
0812 size_type __n,
0813 const hasher& __hf,
0814 const key_equal& __eql,
0815 const allocator_type& __a)
0816 : __table_(__hf, __eql, __a) {
0817 __table_.__rehash_multi(__n);
0818 insert(__first, __last);
0819 }
0820
0821 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0822 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) {
0823 __table_.__rehash_multi(__u.bucket_count());
0824 insert(__u.begin(), __u.end());
0825 }
0826
0827 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0828 template <class _InputIterator>
0829 inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
0830 for (; __first != __last; ++__first)
0831 __table_.__insert_multi(*__first);
0832 }
0833
0834 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0835 inline _LIBCPP_HIDE_FROM_ABI void
0836 swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0837 __x.swap(__y);
0838 }
0839
0840 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0841 _LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
0842 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0843 if (__x.size() != __y.size())
0844 return false;
0845 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
0846 typedef std::pair<const_iterator, const_iterator> _EqRng;
0847 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
0848 _EqRng __xeq = __x.equal_range(__i->first);
0849 _EqRng __yeq = __y.equal_range(__i->first);
0850 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
0851 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
0852 return false;
0853 __i = __xeq.second;
0854 }
0855 return true;
0856 }
0857
0858 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
0859 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
0860 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
0861 return !(__x == __y);
0862 }
0863
0864 } // namespace __gnu_cxx
0865
0866 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
0867 # include <__cxx03/concepts>
0868 # include <__cxx03/iterator>
0869 # include <__cxx03/type_traits>
0870 #endif
0871
0872 #endif // _LIBCPP___CXX03_HASH_MAP
