1457 lines · plain
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_UNORDERED_MAP11#define _LIBCPP___CXX03_UNORDERED_MAP12 13/*14 15 unordered_map synopsis16 17#include <__cxx03/initializer_list>18 19namespace std20{21 22template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,23 class Alloc = allocator<pair<const Key, T>>>24class unordered_map25{26public:27 // types28 typedef Key key_type;29 typedef T mapped_type;30 typedef Hash hasher;31 typedef Pred key_equal;32 typedef Alloc allocator_type;33 typedef pair<const key_type, mapped_type> value_type;34 typedef value_type& reference;35 typedef const value_type& const_reference;36 typedef typename allocator_traits<allocator_type>::pointer pointer;37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;38 typedef typename allocator_traits<allocator_type>::size_type size_type;39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;40 41 typedef /unspecified/ iterator;42 typedef /unspecified/ const_iterator;43 typedef /unspecified/ local_iterator;44 typedef /unspecified/ const_local_iterator;45 46 typedef unspecified node_type; // C++1747 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++1748 49 unordered_map()50 noexcept(51 is_nothrow_default_constructible<hasher>::value &&52 is_nothrow_default_constructible<key_equal>::value &&53 is_nothrow_default_constructible<allocator_type>::value);54 explicit unordered_map(size_type n, const hasher& hf = hasher(),55 const key_equal& eql = key_equal(),56 const allocator_type& a = allocator_type());57 template <class InputIterator>58 unordered_map(InputIterator f, InputIterator l,59 size_type n = 0, const hasher& hf = hasher(),60 const key_equal& eql = key_equal(),61 const allocator_type& a = allocator_type());62 template<container-compatible-range<value_type> R>63 unordered_map(from_range_t, R&& rg, size_type n = see below,64 const hasher& hf = hasher(), const key_equal& eql = key_equal(),65 const allocator_type& a = allocator_type()); // C++2366 67 explicit unordered_map(const allocator_type&);68 unordered_map(const unordered_map&);69 unordered_map(const unordered_map&, const Allocator&);70 unordered_map(unordered_map&&)71 noexcept(72 is_nothrow_move_constructible<hasher>::value &&73 is_nothrow_move_constructible<key_equal>::value &&74 is_nothrow_move_constructible<allocator_type>::value);75 unordered_map(unordered_map&&, const Allocator&);76 unordered_map(initializer_list<value_type>, size_type n = 0,77 const hasher& hf = hasher(), const key_equal& eql = key_equal(),78 const allocator_type& a = allocator_type());79 unordered_map(size_type n, const allocator_type& a)80 : unordered_map(n, hasher(), key_equal(), a) {} // C++1481 unordered_map(size_type n, const hasher& hf, const allocator_type& a)82 : unordered_map(n, hf, key_equal(), a) {} // C++1483 template <class InputIterator>84 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)85 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++1486 template <class InputIterator>87 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,88 const allocator_type& a)89 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++1490 template<container-compatible-range<value_type> R>91 unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)92 : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++2393 template<container-compatible-range<value_type> R>94 unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)95 : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++2396 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)97 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++1498 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,99 const allocator_type& a)100 : unordered_map(il, n, hf, key_equal(), a) {} // C++14101 ~unordered_map();102 unordered_map& operator=(const unordered_map&);103 unordered_map& operator=(unordered_map&&)104 noexcept(105 allocator_type::propagate_on_container_move_assignment::value &&106 is_nothrow_move_assignable<allocator_type>::value &&107 is_nothrow_move_assignable<hasher>::value &&108 is_nothrow_move_assignable<key_equal>::value);109 unordered_map& operator=(initializer_list<value_type>);110 111 allocator_type get_allocator() const noexcept;112 113 bool empty() const noexcept;114 size_type size() const noexcept;115 size_type max_size() const noexcept;116 117 iterator begin() noexcept;118 iterator end() noexcept;119 const_iterator begin() const noexcept;120 const_iterator end() const noexcept;121 const_iterator cbegin() const noexcept;122 const_iterator cend() const noexcept;123 124 template <class... Args>125 pair<iterator, bool> emplace(Args&&... args);126 template <class... Args>127 iterator emplace_hint(const_iterator position, Args&&... args);128 pair<iterator, bool> insert(const value_type& obj);129 template <class P>130 pair<iterator, bool> insert(P&& obj);131 iterator insert(const_iterator hint, const value_type& obj);132 template <class P>133 iterator insert(const_iterator hint, P&& obj);134 template <class InputIterator>135 void insert(InputIterator first, InputIterator last);136 template<container-compatible-range<value_type> R>137 void insert_range(R&& rg); // C++23138 void insert(initializer_list<value_type>);139 140 node_type extract(const_iterator position); // C++17141 node_type extract(const key_type& x); // C++17142 insert_return_type insert(node_type&& nh); // C++17143 iterator insert(const_iterator hint, node_type&& nh); // C++17144 145 template <class... Args>146 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17147 template <class... Args>148 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17149 template <class... Args>150 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17151 template <class... Args>152 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17153 template <class M>154 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17155 template <class M>156 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17157 template <class M>158 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17159 template <class M>160 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17161 162 iterator erase(const_iterator position);163 iterator erase(iterator position); // C++14164 size_type erase(const key_type& k);165 iterator erase(const_iterator first, const_iterator last);166 void clear() noexcept;167 168 template<class H2, class P2>169 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17170 template<class H2, class P2>171 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17172 template<class H2, class P2>173 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17174 template<class H2, class P2>175 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17176 177 void swap(unordered_map&)178 noexcept(179 (!allocator_type::propagate_on_container_swap::value ||180 __is_nothrow_swappable<allocator_type>::value) &&181 __is_nothrow_swappable<hasher>::value &&182 __is_nothrow_swappable<key_equal>::value);183 184 hasher hash_function() const;185 key_equal key_eq() const;186 187 iterator find(const key_type& k);188 const_iterator find(const key_type& k) const;189 template<typename K>190 iterator find(const K& x); // C++20191 template<typename K>192 const_iterator find(const K& x) const; // C++20193 size_type count(const key_type& k) const;194 template<typename K>195 size_type count(const K& k) const; // C++20196 bool contains(const key_type& k) const; // C++20197 template<typename K>198 bool contains(const K& k) const; // C++20199 pair<iterator, iterator> equal_range(const key_type& k);200 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;201 template<typename K>202 pair<iterator, iterator> equal_range(const K& k); // C++20203 template<typename K>204 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20205 206 mapped_type& operator[](const key_type& k);207 mapped_type& operator[](key_type&& k);208 209 mapped_type& at(const key_type& k);210 const mapped_type& at(const key_type& k) const;211 212 size_type bucket_count() const noexcept;213 size_type max_bucket_count() const noexcept;214 215 size_type bucket_size(size_type n) const;216 size_type bucket(const key_type& k) const;217 218 local_iterator begin(size_type n);219 local_iterator end(size_type n);220 const_local_iterator begin(size_type n) const;221 const_local_iterator end(size_type n) const;222 const_local_iterator cbegin(size_type n) const;223 const_local_iterator cend(size_type n) const;224 225 float load_factor() const noexcept;226 float max_load_factor() const noexcept;227 void max_load_factor(float z);228 void rehash(size_type n);229 void reserve(size_type n);230};231 232template<class InputIterator,233 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,234 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>235unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,236 Hash = Hash(), Pred = Pred(), Allocator = Allocator())237 -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,238 Allocator>; // C++17239 240template<ranges::input_range R, class Hash = hash<range-key-type<R>>,241 class Pred = equal_to<range-key-type<R>>,242 class Allocator = allocator<range-to-alloc-type<R>>>243 unordered_map(from_range_t, R&&, typename see below::size_type = see below,244 Hash = Hash(), Pred = Pred(), Allocator = Allocator())245 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23246 247template<class Key, class T, class Hash = hash<Key>,248 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>249unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,250 Hash = Hash(), Pred = Pred(), Allocator = Allocator())251 -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17252 253template<class InputIterator, class Allocator>254unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)255 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,256 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17257 258template<class InputIterator, class Allocator>259unordered_map(InputIterator, InputIterator, Allocator)260 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,261 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17262 263template<class InputIterator, class Hash, class Allocator>264unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)265 -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,266 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17267 268template<ranges::input_range R, class Allocator>269 unordered_map(from_range_t, R&&, typename see below::size_type, Allocator)270 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,271 equal_to<range-key-type<R>>, Allocator>; // C++23272 273template<ranges::input_range R, class Allocator>274 unordered_map(from_range_t, R&&, Allocator)275 -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,276 equal_to<range-key-type<R>>, Allocator>; // C++23277 278template<ranges::input_range R, class Hash, class Allocator>279 unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator)280 -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash,281 equal_to<range-key-type<R>>, Allocator>; // C++23282 283template<class Key, class T, typename Allocator>284unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)285 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17286 287template<class Key, class T, typename Allocator>288unordered_map(initializer_list<pair<const Key, T>>, Allocator)289 -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17290 291template<class Key, class T, class Hash, class Allocator>292unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator)293 -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17294 295template <class Key, class T, class Hash, class Pred, class Alloc>296 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,297 unordered_map<Key, T, Hash, Pred, Alloc>& y)298 noexcept(noexcept(x.swap(y)));299 300template <class Key, class T, class Hash, class Pred, class Alloc>301 bool302 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,303 const unordered_map<Key, T, Hash, Pred, Alloc>& y);304 305template <class Key, class T, class Hash, class Pred, class Alloc>306 bool307 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,308 const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20309 310template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,311 class Alloc = allocator<pair<const Key, T>>>312class unordered_multimap313{314public:315 // types316 typedef Key key_type;317 typedef T mapped_type;318 typedef Hash hasher;319 typedef Pred key_equal;320 typedef Alloc allocator_type;321 typedef pair<const key_type, mapped_type> value_type;322 typedef value_type& reference;323 typedef const value_type& const_reference;324 typedef typename allocator_traits<allocator_type>::pointer pointer;325 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;326 typedef typename allocator_traits<allocator_type>::size_type size_type;327 typedef typename allocator_traits<allocator_type>::difference_type difference_type;328 329 typedef /unspecified/ iterator;330 typedef /unspecified/ const_iterator;331 typedef /unspecified/ local_iterator;332 typedef /unspecified/ const_local_iterator;333 334 typedef unspecified node_type; // C++17335 336 unordered_multimap()337 noexcept(338 is_nothrow_default_constructible<hasher>::value &&339 is_nothrow_default_constructible<key_equal>::value &&340 is_nothrow_default_constructible<allocator_type>::value);341 explicit unordered_multimap(size_type n, const hasher& hf = hasher(),342 const key_equal& eql = key_equal(),343 const allocator_type& a = allocator_type());344 template <class InputIterator>345 unordered_multimap(InputIterator f, InputIterator l,346 size_type n = 0, const hasher& hf = hasher(),347 const key_equal& eql = key_equal(),348 const allocator_type& a = allocator_type());349 template<container-compatible-range<value_type> R>350 unordered_multimap(from_range_t, R&& rg, size_type n = see below,351 const hasher& hf = hasher(), const key_equal& eql = key_equal(),352 const allocator_type& a = allocator_type()); // C++23353 explicit unordered_multimap(const allocator_type&);354 unordered_multimap(const unordered_multimap&);355 unordered_multimap(const unordered_multimap&, const Allocator&);356 unordered_multimap(unordered_multimap&&)357 noexcept(358 is_nothrow_move_constructible<hasher>::value &&359 is_nothrow_move_constructible<key_equal>::value &&360 is_nothrow_move_constructible<allocator_type>::value);361 unordered_multimap(unordered_multimap&&, const Allocator&);362 unordered_multimap(initializer_list<value_type>, size_type n = 0,363 const hasher& hf = hasher(), const key_equal& eql = key_equal(),364 const allocator_type& a = allocator_type());365 unordered_multimap(size_type n, const allocator_type& a)366 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14367 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)368 : unordered_multimap(n, hf, key_equal(), a) {} // C++14369 template <class InputIterator>370 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)371 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14372 template <class InputIterator>373 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,374 const allocator_type& a)375 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14376 template<container-compatible-range<value_type> R>377 unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)378 : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23379 template<container-compatible-range<value_type> R>380 unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)381 : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23382 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)383 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14384 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,385 const allocator_type& a)386 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14387 ~unordered_multimap();388 unordered_multimap& operator=(const unordered_multimap&);389 unordered_multimap& operator=(unordered_multimap&&)390 noexcept(391 allocator_type::propagate_on_container_move_assignment::value &&392 is_nothrow_move_assignable<allocator_type>::value &&393 is_nothrow_move_assignable<hasher>::value &&394 is_nothrow_move_assignable<key_equal>::value);395 unordered_multimap& operator=(initializer_list<value_type>);396 397 allocator_type get_allocator() const noexcept;398 399 bool empty() const noexcept;400 size_type size() const noexcept;401 size_type max_size() const noexcept;402 403 iterator begin() noexcept;404 iterator end() noexcept;405 const_iterator begin() const noexcept;406 const_iterator end() const noexcept;407 const_iterator cbegin() const noexcept;408 const_iterator cend() const noexcept;409 410 template <class... Args>411 iterator emplace(Args&&... args);412 template <class... Args>413 iterator emplace_hint(const_iterator position, Args&&... args);414 iterator insert(const value_type& obj);415 template <class P>416 iterator insert(P&& obj);417 iterator insert(const_iterator hint, const value_type& obj);418 template <class P>419 iterator insert(const_iterator hint, P&& obj);420 template <class InputIterator>421 void insert(InputIterator first, InputIterator last);422 template<container-compatible-range<value_type> R>423 void insert_range(R&& rg); // C++23424 void insert(initializer_list<value_type>);425 426 node_type extract(const_iterator position); // C++17427 node_type extract(const key_type& x); // C++17428 iterator insert(node_type&& nh); // C++17429 iterator insert(const_iterator hint, node_type&& nh); // C++17430 431 iterator erase(const_iterator position);432 iterator erase(iterator position); // C++14433 size_type erase(const key_type& k);434 iterator erase(const_iterator first, const_iterator last);435 void clear() noexcept;436 437 template<class H2, class P2>438 void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17439 template<class H2, class P2>440 void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17441 template<class H2, class P2>442 void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17443 template<class H2, class P2>444 void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17445 446 void swap(unordered_multimap&)447 noexcept(448 (!allocator_type::propagate_on_container_swap::value ||449 __is_nothrow_swappable<allocator_type>::value) &&450 __is_nothrow_swappable<hasher>::value &&451 __is_nothrow_swappable<key_equal>::value);452 453 hasher hash_function() const;454 key_equal key_eq() const;455 456 iterator find(const key_type& k);457 const_iterator find(const key_type& k) const;458 template<typename K>459 iterator find(const K& x); // C++20460 template<typename K>461 const_iterator find(const K& x) const; // C++20462 size_type count(const key_type& k) const;463 template<typename K>464 size_type count(const K& k) const; // C++20465 bool contains(const key_type& k) const; // C++20466 template<typename K>467 bool contains(const K& k) const; // C++20468 pair<iterator, iterator> equal_range(const key_type& k);469 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;470 template<typename K>471 pair<iterator, iterator> equal_range(const K& k); // C++20472 template<typename K>473 pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20474 475 size_type bucket_count() const noexcept;476 size_type max_bucket_count() const noexcept;477 478 size_type bucket_size(size_type n) const;479 size_type bucket(const key_type& k) const;480 481 local_iterator begin(size_type n);482 local_iterator end(size_type n);483 const_local_iterator begin(size_type n) const;484 const_local_iterator end(size_type n) const;485 const_local_iterator cbegin(size_type n) const;486 const_local_iterator cend(size_type n) const;487 488 float load_factor() const noexcept;489 float max_load_factor() const noexcept;490 void max_load_factor(float z);491 void rehash(size_type n);492 void reserve(size_type n);493};494 495template<class InputIterator,496 class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>498unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below,499 Hash = Hash(), Pred = Pred(), Allocator = Allocator())500 -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,501 Allocator>; // C++17502 503template<ranges::input_range R, class Hash = hash<range-key-type<R>>,504 class Pred = equal_to<range-key-type<R>>,505 class Allocator = allocator<range-to-alloc-type<R>>>506 unordered_multimap(from_range_t, R&&, typename see below::size_type = see below,507 Hash = Hash(), Pred = Pred(), Allocator = Allocator())508 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23509 510template<class Key, class T, class Hash = hash<Key>,511 class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>512unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,513 Hash = Hash(), Pred = Pred(), Allocator = Allocator())514 -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17515 516template<class InputIterator, class Allocator>517unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)518 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,519 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17520 521template<class InputIterator, class Allocator>522unordered_multimap(InputIterator, InputIterator, Allocator)523 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,524 hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17525 526template<class InputIterator, class Hash, class Allocator>527unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)528 -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,529 equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17530 531template<ranges::input_range R, class Allocator>532 unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator)533 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,534 equal_to<range-key-type<R>>, Allocator>; // C++23535 536template<ranges::input_range R, class Allocator>537 unordered_multimap(from_range_t, R&&, Allocator)538 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,539 equal_to<range-key-type<R>>, Allocator>; // C++23540 541template<ranges::input_range R, class Hash, class Allocator>542 unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator)543 -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash,544 equal_to<range-key-type<R>>, Allocator>; // C++23545 546template<class Key, class T, typename Allocator>547unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)548 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17549 550template<class Key, class T, typename Allocator>551unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)552 -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17553 554template<class Key, class T, class Hash, class Allocator>555unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,556 Allocator)557 -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17558 559template <class Key, class T, class Hash, class Pred, class Alloc>560 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,561 unordered_multimap<Key, T, Hash, Pred, Alloc>& y)562 noexcept(noexcept(x.swap(y)));563 564template <class K, class T, class H, class P, class A, class Predicate>565 typename unordered_map<K, T, H, P, A>::size_type566 erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20567 568template <class K, class T, class H, class P, class A, class Predicate>569 typename unordered_multimap<K, T, H, P, A>::size_type570 erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20571 572template <class Key, class T, class Hash, class Pred, class Alloc>573 bool574 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,575 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);576 577template <class Key, class T, class Hash, class Pred, class Alloc>578 bool579 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,580 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20581 582} // std583 584*/585 586#include <__cxx03/__algorithm/is_permutation.h>587#include <__cxx03/__assert>588#include <__cxx03/__config>589#include <__cxx03/__functional/operations.h>590#include <__cxx03/__hash_table>591#include <__cxx03/__iterator/distance.h>592#include <__cxx03/__iterator/erase_if_container.h>593#include <__cxx03/__iterator/iterator_traits.h>594#include <__cxx03/__memory/addressof.h>595#include <__cxx03/__memory/allocator.h>596#include <__cxx03/__type_traits/is_allocator.h>597#include <__cxx03/__type_traits/type_identity.h>598#include <__cxx03/__utility/forward.h>599#include <__cxx03/stdexcept>600#include <__cxx03/version>601 602// standard-mandated includes603 604// [iterator.range]605#include <__cxx03/__iterator/access.h>606 607#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)608# pragma GCC system_header609#endif610 611_LIBCPP_PUSH_MACROS612#include <__cxx03/__undef_macros>613 614_LIBCPP_BEGIN_NAMESPACE_STD615 616template <class _Key,617 class _Cp,618 class _Hash,619 class _Pred,620 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>621class __unordered_map_hasher : private _Hash {622public:623 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() : _Hash() {}624 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) : _Hash(__h) {}625 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; }626 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const {627 return static_cast<const _Hash&>(*this)(__x.__get_value().first);628 }629 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); }630 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) {631 using std::swap;632 swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));633 }634};635 636template <class _Key, class _Cp, class _Hash, class _Pred>637class __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> {638 _Hash __hash_;639 640public:641 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() : __hash_() {}642 _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) : __hash_(__h) {}643 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }644 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); }645 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }646 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) {647 using std::swap;648 swap(__hash_, __y.__hash_);649 }650};651 652template <class _Key, class _Cp, class _Hash, class _Pred, bool __b>653inline _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,654 __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) {655 __x.swap(__y);656}657 658template <class _Key,659 class _Cp,660 class _Pred,661 class _Hash,662 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>663class __unordered_map_equal : private _Pred {664public:665 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() : _Pred() {}666 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) : _Pred(__p) {}667 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; }668 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {669 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);670 }671 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {672 return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);673 }674 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {675 return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);676 }677 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) {678 using std::swap;679 swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));680 }681};682 683template <class _Key, class _Cp, class _Pred, class _Hash>684class __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> {685 _Pred __pred_;686 687public:688 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() : __pred_() {}689 _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) : __pred_(__p) {}690 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }691 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {692 return __pred_(__x.__get_value().first, __y.__get_value().first);693 }694 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {695 return __pred_(__x.__get_value().first, __y);696 }697 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {698 return __pred_(__x, __y.__get_value().first);699 }700 _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) {701 using std::swap;702 swap(__pred_, __y.__pred_);703 }704};705 706template <class _Key, class _Cp, class _Pred, class _Hash, bool __b>707inline _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x,708 __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y) {709 __x.swap(__y);710}711 712template <class _Alloc>713class __hash_map_node_destructor {714 typedef _Alloc allocator_type;715 typedef allocator_traits<allocator_type> __alloc_traits;716 717public:718 typedef typename __alloc_traits::pointer pointer;719 720private:721 allocator_type& __na_;722 723public:724 bool __first_constructed;725 bool __second_constructed;726 727 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;728 729 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT730 : __na_(__na),731 __first_constructed(false),732 __second_constructed(false) {}733 734 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)735 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {736 const_cast<bool&>(__x.__value_constructed) = false;737 }738 739 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {740 if (__second_constructed)741 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second));742 if (__first_constructed)743 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first));744 if (__p)745 __alloc_traits::deallocate(__na_, __p, 1);746 }747};748 749template <class _Key, class _Tp>750struct __hash_value_type {751 typedef _Key key_type;752 typedef _Tp mapped_type;753 typedef pair<const key_type, mapped_type> value_type;754 755private:756 value_type __cc_;757 758public:759 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }760 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }761 762 ~__hash_value_type() = delete;763};764 765template <class _HashIterator>766class _LIBCPP_TEMPLATE_VIS __hash_map_iterator {767 _HashIterator __i_;768 769 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;770 771public:772 typedef forward_iterator_tag iterator_category;773 typedef typename _NodeTypes::__map_value_type value_type;774 typedef typename _NodeTypes::difference_type difference_type;775 typedef value_type& reference;776 typedef typename _NodeTypes::__map_value_type_pointer pointer;777 778 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}779 780 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}781 782 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }783 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }784 785 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {786 ++__i_;787 return *this;788 }789 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {790 __hash_map_iterator __t(*this);791 ++(*this);792 return __t;793 }794 795 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {796 return __x.__i_ == __y.__i_;797 }798 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {799 return __x.__i_ != __y.__i_;800 }801 802 template <class, class, class, class, class>803 friend class _LIBCPP_TEMPLATE_VIS unordered_map;804 template <class, class, class, class, class>805 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;806 template <class>807 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;808 template <class>809 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;810 template <class>811 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;812};813 814template <class _HashIterator>815class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {816 _HashIterator __i_;817 818 typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;819 820public:821 typedef forward_iterator_tag iterator_category;822 typedef typename _NodeTypes::__map_value_type value_type;823 typedef typename _NodeTypes::difference_type difference_type;824 typedef const value_type& reference;825 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;826 827 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}828 829 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}830 _LIBCPP_HIDE_FROM_ABI831 __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT832 : __i_(__i.__i_) {}833 834 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }835 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }836 837 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {838 ++__i_;839 return *this;840 }841 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {842 __hash_map_const_iterator __t(*this);843 ++(*this);844 return __t;845 }846 847 friend _LIBCPP_HIDE_FROM_ABI bool848 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {849 return __x.__i_ == __y.__i_;850 }851 friend _LIBCPP_HIDE_FROM_ABI bool852 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {853 return __x.__i_ != __y.__i_;854 }855 856 template <class, class, class, class, class>857 friend class _LIBCPP_TEMPLATE_VIS unordered_map;858 template <class, class, class, class, class>859 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;860 template <class>861 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;862 template <class>863 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;864};865 866template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>867class unordered_multimap;868 869template <class _Key,870 class _Tp,871 class _Hash = hash<_Key>,872 class _Pred = equal_to<_Key>,873 class _Alloc = allocator<pair<const _Key, _Tp> > >874class _LIBCPP_TEMPLATE_VIS unordered_map {875public:876 // types877 typedef _Key key_type;878 typedef _Tp mapped_type;879 typedef __type_identity_t<_Hash> hasher;880 typedef __type_identity_t<_Pred> key_equal;881 typedef __type_identity_t<_Alloc> allocator_type;882 typedef pair<const key_type, mapped_type> value_type;883 typedef value_type& reference;884 typedef const value_type& const_reference;885 static_assert(is_same<value_type, typename allocator_type::value_type>::value,886 "Allocator::value_type must be same type as value_type");887 888private:889 typedef __hash_value_type<key_type, mapped_type> __value_type;890 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;891 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;892 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;893 894 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;895 896 __table __table_;897 898 typedef typename __table::_NodeTypes _NodeTypes;899 typedef typename __table::__node_pointer __node_pointer;900 typedef typename __table::__node_const_pointer __node_const_pointer;901 typedef typename __table::__node_traits __node_traits;902 typedef typename __table::__node_allocator __node_allocator;903 typedef typename __table::__node __node;904 typedef __hash_map_node_destructor<__node_allocator> _Dp;905 typedef unique_ptr<__node, _Dp> __node_holder;906 typedef allocator_traits<allocator_type> __alloc_traits;907 908 static_assert(__check_valid_allocator<allocator_type>::value, "");909 910 static_assert(is_same<typename __table::__container_value_type, value_type>::value, "");911 static_assert(is_same<typename __table::__node_value_type, __value_type>::value, "");912 913public:914 typedef typename __alloc_traits::pointer pointer;915 typedef typename __alloc_traits::const_pointer const_pointer;916 typedef typename __table::size_type size_type;917 typedef typename __table::difference_type difference_type;918 919 typedef __hash_map_iterator<typename __table::iterator> iterator;920 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;921 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;922 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;923 924 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>925 friend class _LIBCPP_TEMPLATE_VIS unordered_map;926 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>927 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;928 929 _LIBCPP_HIDE_FROM_ABI unordered_map() {}930 explicit _LIBCPP_HIDE_FROM_ABI931 unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());932 _LIBCPP_HIDE_FROM_ABI933 unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);934 template <class _InputIterator>935 _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);936 template <class _InputIterator>937 _LIBCPP_HIDE_FROM_ABI938 unordered_map(_InputIterator __first,939 _InputIterator __last,940 size_type __n,941 const hasher& __hf = hasher(),942 const key_equal& __eql = key_equal());943 template <class _InputIterator>944 _LIBCPP_HIDE_FROM_ABI unordered_map(945 _InputIterator __first,946 _InputIterator __last,947 size_type __n,948 const hasher& __hf,949 const key_equal& __eql,950 const allocator_type& __a);951 952 _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);953 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u);954 _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);955 956 _LIBCPP_HIDE_FROM_ABI ~unordered_map() {957 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");958 }959 960 _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) {961 if (this != std::addressof(__u)) {962 __table_.clear();963 __table_.hash_function() = __u.__table_.hash_function();964 __table_.key_eq() = __u.__table_.key_eq();965 __table_.max_load_factor() = __u.__table_.max_load_factor();966 __table_.__copy_assign_alloc(__u.__table_);967 insert(__u.begin(), __u.end());968 }969 return *this;970 }971 972 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {973 return allocator_type(__table_.__node_alloc());974 }975 976 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }977 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }978 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }979 980 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }981 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }982 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }983 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }984 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }985 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }986 987 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }988 989 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }990 991 template <class _InputIterator>992 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);993 994 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }995 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }996 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }997 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {998 return __table_.erase(__first.__i_, __last.__i_);999 }1000 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }1001 1002 _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) { __table_.swap(__u.__table_); }1003 1004 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }1005 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }1006 1007 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }1008 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }1009 1010 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }1011 1012 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1013 return __table_.__equal_range_unique(__k);1014 }1015 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1016 return __table_.__equal_range_unique(__k);1017 }1018 1019 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);1020 1021 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);1022 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;1023 1024 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }1025 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }1026 1027 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }1028 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }1029 1030 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }1031 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }1032 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }1033 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }1034 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }1035 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }1036 1037 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }1038 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }1039 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }1040 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }1041 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }1042 1043private:1044 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);1045};1046 1047template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1048unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)1049 : __table_(__hf, __eql) {1050 __table_.__rehash_unique(__n);1051}1052 1053template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1054unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1055 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)1056 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1057 __table_.__rehash_unique(__n);1058}1059 1060template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1061inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)1062 : __table_(typename __table::allocator_type(__a)) {}1063 1064template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1065template <class _InputIterator>1066unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {1067 insert(__first, __last);1068}1069 1070template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1071template <class _InputIterator>1072unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1073 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)1074 : __table_(__hf, __eql) {1075 __table_.__rehash_unique(__n);1076 insert(__first, __last);1077}1078 1079template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1080template <class _InputIterator>1081unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1082 _InputIterator __first,1083 _InputIterator __last,1084 size_type __n,1085 const hasher& __hf,1086 const key_equal& __eql,1087 const allocator_type& __a)1088 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1089 __table_.__rehash_unique(__n);1090 insert(__first, __last);1091}1092 1093template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1094unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) {1095 __table_.__rehash_unique(__u.bucket_count());1096 insert(__u.begin(), __u.end());1097}1098 1099template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1100unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)1101 : __table_(__u.__table_, typename __table::allocator_type(__a)) {1102 __table_.__rehash_unique(__u.bucket_count());1103 insert(__u.begin(), __u.end());1104}1105 1106template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1107template <class _InputIterator>1108inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {1109 for (; __first != __last; ++__first)1110 __table_.__insert_unique(*__first);1111}1112 1113template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1114typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder1115unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {1116 __node_allocator& __na = __table_.__node_alloc();1117 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1118 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k);1119 __h.get_deleter().__first_constructed = true;1120 __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second));1121 __h.get_deleter().__second_constructed = true;1122 return __h;1123}1124 1125template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1126_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {1127 iterator __i = find(__k);1128 if (__i != end())1129 return __i->second;1130 __node_holder __h = __construct_node_with_key(__k);1131 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());1132 __h.release();1133 return __r.first->second;1134}1135 1136template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1137_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {1138 iterator __i = find(__k);1139 if (__i == end())1140 __throw_out_of_range("unordered_map::at: key not found");1141 return __i->second;1142}1143 1144template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1145const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {1146 const_iterator __i = find(__k);1147 if (__i == end())1148 __throw_out_of_range("unordered_map::at: key not found");1149 return __i->second;1150}1151 1152template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1153inline _LIBCPP_HIDE_FROM_ABI void1154swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1155 __x.swap(__y);1156}1157 1158template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1159_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1160 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1161 if (__x.size() != __y.size())1162 return false;1163 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;1164 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {1165 const_iterator __j = __y.find(__i->first);1166 if (__j == __ey || !(*__i == *__j))1167 return false;1168 }1169 return true;1170}1171 1172template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1173inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1174 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1175 return !(__x == __y);1176}1177 1178template <class _Key,1179 class _Tp,1180 class _Hash = hash<_Key>,1181 class _Pred = equal_to<_Key>,1182 class _Alloc = allocator<pair<const _Key, _Tp> > >1183class _LIBCPP_TEMPLATE_VIS unordered_multimap {1184public:1185 // types1186 typedef _Key key_type;1187 typedef _Tp mapped_type;1188 typedef __type_identity_t<_Hash> hasher;1189 typedef __type_identity_t<_Pred> key_equal;1190 typedef __type_identity_t<_Alloc> allocator_type;1191 typedef pair<const key_type, mapped_type> value_type;1192 typedef value_type& reference;1193 typedef const value_type& const_reference;1194 static_assert(__check_valid_allocator<allocator_type>::value, "");1195 static_assert(is_same<value_type, typename allocator_type::value_type>::value,1196 "Allocator::value_type must be same type as value_type");1197 1198private:1199 typedef __hash_value_type<key_type, mapped_type> __value_type;1200 typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;1201 typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;1202 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;1203 1204 typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;1205 1206 __table __table_;1207 1208 typedef typename __table::_NodeTypes _NodeTypes;1209 typedef typename __table::__node_traits __node_traits;1210 typedef typename __table::__node_allocator __node_allocator;1211 typedef typename __table::__node __node;1212 typedef __hash_map_node_destructor<__node_allocator> _Dp;1213 typedef unique_ptr<__node, _Dp> __node_holder;1214 typedef allocator_traits<allocator_type> __alloc_traits;1215 static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value,1216 "Allocator uses different size_type for different types");1217 1218public:1219 typedef typename __alloc_traits::pointer pointer;1220 typedef typename __alloc_traits::const_pointer const_pointer;1221 typedef typename __table::size_type size_type;1222 typedef typename __table::difference_type difference_type;1223 1224 typedef __hash_map_iterator<typename __table::iterator> iterator;1225 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;1226 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;1227 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;1228 1229 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>1230 friend class _LIBCPP_TEMPLATE_VIS unordered_map;1231 template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>1232 friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;1233 1234 _LIBCPP_HIDE_FROM_ABI unordered_multimap() {}1235 explicit _LIBCPP_HIDE_FROM_ABI1236 unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());1237 _LIBCPP_HIDE_FROM_ABI1238 unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);1239 template <class _InputIterator>1240 _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);1241 template <class _InputIterator>1242 _LIBCPP_HIDE_FROM_ABI unordered_multimap(1243 _InputIterator __first,1244 _InputIterator __last,1245 size_type __n,1246 const hasher& __hf = hasher(),1247 const key_equal& __eql = key_equal());1248 template <class _InputIterator>1249 _LIBCPP_HIDE_FROM_ABI unordered_multimap(1250 _InputIterator __first,1251 _InputIterator __last,1252 size_type __n,1253 const hasher& __hf,1254 const key_equal& __eql,1255 const allocator_type& __a);1256 1257 _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);1258 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u);1259 _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);1260 1261 _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {1262 static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");1263 }1264 1265 _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) {1266 if (this != std::addressof(__u)) {1267 __table_.clear();1268 __table_.hash_function() = __u.__table_.hash_function();1269 __table_.key_eq() = __u.__table_.key_eq();1270 __table_.max_load_factor() = __u.__table_.max_load_factor();1271 __table_.__copy_assign_alloc(__u.__table_);1272 insert(__u.begin(), __u.end());1273 }1274 return *this;1275 }1276 1277 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {1278 return allocator_type(__table_.__node_alloc());1279 }1280 1281 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }1282 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }1283 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }1284 1285 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }1286 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }1287 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }1288 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }1289 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }1290 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }1291 1292 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }1293 1294 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {1295 return __table_.__insert_multi(__p.__i_, __x);1296 }1297 1298 template <class _InputIterator>1299 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);1300 1301 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }1302 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }1303 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }1304 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {1305 return __table_.erase(__first.__i_, __last.__i_);1306 }1307 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }1308 1309 _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) { __table_.swap(__u.__table_); }1310 1311 _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }1312 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }1313 1314 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }1315 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }1316 1317 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }1318 1319 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1320 return __table_.__equal_range_multi(__k);1321 }1322 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1323 return __table_.__equal_range_multi(__k);1324 }1325 1326 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }1327 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }1328 1329 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }1330 _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }1331 1332 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }1333 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }1334 _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }1335 _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }1336 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }1337 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }1338 1339 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }1340 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }1341 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }1342 _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }1343 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }1344};1345 1346template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1347unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(1348 size_type __n, const hasher& __hf, const key_equal& __eql)1349 : __table_(__hf, __eql) {1350 __table_.__rehash_multi(__n);1351}1352 1353template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1354unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(1355 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)1356 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1357 __table_.__rehash_multi(__n);1358}1359 1360template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1361template <class _InputIterator>1362unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {1363 insert(__first, __last);1364}1365 1366template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1367template <class _InputIterator>1368unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(1369 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)1370 : __table_(__hf, __eql) {1371 __table_.__rehash_multi(__n);1372 insert(__first, __last);1373}1374 1375template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1376template <class _InputIterator>1377unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(1378 _InputIterator __first,1379 _InputIterator __last,1380 size_type __n,1381 const hasher& __hf,1382 const key_equal& __eql,1383 const allocator_type& __a)1384 : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1385 __table_.__rehash_multi(__n);1386 insert(__first, __last);1387}1388 1389template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1390inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)1391 : __table_(typename __table::allocator_type(__a)) {}1392 1393template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1394unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u)1395 : __table_(__u.__table_) {1396 __table_.__rehash_multi(__u.bucket_count());1397 insert(__u.begin(), __u.end());1398}1399 1400template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1401unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(1402 const unordered_multimap& __u, const allocator_type& __a)1403 : __table_(__u.__table_, typename __table::allocator_type(__a)) {1404 __table_.__rehash_multi(__u.bucket_count());1405 insert(__u.begin(), __u.end());1406}1407 1408template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1409template <class _InputIterator>1410inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {1411 for (; __first != __last; ++__first)1412 __table_.__insert_multi(*__first);1413}1414 1415template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1416inline _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1417 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1418 __x.swap(__y);1419}1420 1421template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1422_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1423 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1424 if (__x.size() != __y.size())1425 return false;1426 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;1427 typedef pair<const_iterator, const_iterator> _EqRng;1428 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {1429 _EqRng __xeq = __x.equal_range(__i->first);1430 _EqRng __yeq = __y.equal_range(__i->first);1431 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||1432 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))1433 return false;1434 __i = __xeq.second;1435 }1436 return true;1437}1438 1439template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1440inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1441 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1442 return !(__x == __y);1443}1444 1445_LIBCPP_END_NAMESPACE_STD1446 1447_LIBCPP_POP_MACROS1448 1449#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)1450# include <__cxx03/algorithm>1451# include <__cxx03/cstdlib>1452# include <__cxx03/iterator>1453# include <__cxx03/type_traits>1454#endif1455 1456#endif // _LIBCPP___CXX03_UNORDERED_MAP1457