10b57cec5SDimitry Andric// -*- C++ -*- 2349cc55cSDimitry Andric//===----------------------------------------------------------------------===// 30b57cec5SDimitry Andric// 40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 70b57cec5SDimitry Andric// 80b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 90b57cec5SDimitry Andric 100b57cec5SDimitry Andric#ifndef _LIBCPP_UNORDERED_MAP 110b57cec5SDimitry Andric#define _LIBCPP_UNORDERED_MAP 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric/* 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric unordered_map synopsis 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric#include <initializer_list> 180b57cec5SDimitry Andric 190b57cec5SDimitry Andricnamespace std 200b57cec5SDimitry Andric{ 210b57cec5SDimitry Andric 220b57cec5SDimitry Andrictemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 230b57cec5SDimitry Andric class Alloc = allocator<pair<const Key, T>>> 240b57cec5SDimitry Andricclass unordered_map 250b57cec5SDimitry Andric{ 260b57cec5SDimitry Andricpublic: 270b57cec5SDimitry Andric // types 280b57cec5SDimitry Andric typedef Key key_type; 290b57cec5SDimitry Andric typedef T mapped_type; 300b57cec5SDimitry Andric typedef Hash hasher; 310b57cec5SDimitry Andric typedef Pred key_equal; 320b57cec5SDimitry Andric typedef Alloc allocator_type; 330b57cec5SDimitry Andric typedef pair<const key_type, mapped_type> value_type; 340b57cec5SDimitry Andric typedef value_type& reference; 350b57cec5SDimitry Andric typedef const value_type& const_reference; 360b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::pointer pointer; 370b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 380b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::size_type size_type; 390b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::difference_type difference_type; 400b57cec5SDimitry Andric 410b57cec5SDimitry Andric typedef /unspecified/ iterator; 420b57cec5SDimitry Andric typedef /unspecified/ const_iterator; 430b57cec5SDimitry Andric typedef /unspecified/ local_iterator; 440b57cec5SDimitry Andric typedef /unspecified/ const_local_iterator; 450b57cec5SDimitry Andric 460b57cec5SDimitry Andric typedef unspecified node_type; // C++17 470b57cec5SDimitry Andric typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 480b57cec5SDimitry Andric 490b57cec5SDimitry Andric unordered_map() 500b57cec5SDimitry Andric noexcept( 510b57cec5SDimitry Andric is_nothrow_default_constructible<hasher>::value && 520b57cec5SDimitry Andric is_nothrow_default_constructible<key_equal>::value && 530b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value); 540b57cec5SDimitry Andric explicit unordered_map(size_type n, const hasher& hf = hasher(), 550b57cec5SDimitry Andric const key_equal& eql = key_equal(), 560b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 570b57cec5SDimitry Andric template <class InputIterator> 580b57cec5SDimitry Andric unordered_map(InputIterator f, InputIterator l, 590b57cec5SDimitry Andric size_type n = 0, const hasher& hf = hasher(), 600b57cec5SDimitry Andric const key_equal& eql = key_equal(), 610b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 6206c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 6306c3fb27SDimitry Andric unordered_map(from_range_t, R&& rg, size_type n = see below, 6406c3fb27SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 6506c3fb27SDimitry Andric const allocator_type& a = allocator_type()); // C++23 6606c3fb27SDimitry Andric 670b57cec5SDimitry Andric explicit unordered_map(const allocator_type&); 680b57cec5SDimitry Andric unordered_map(const unordered_map&); 690b57cec5SDimitry Andric unordered_map(const unordered_map&, const Allocator&); 700b57cec5SDimitry Andric unordered_map(unordered_map&&) 710b57cec5SDimitry Andric noexcept( 720b57cec5SDimitry Andric is_nothrow_move_constructible<hasher>::value && 730b57cec5SDimitry Andric is_nothrow_move_constructible<key_equal>::value && 740b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value); 750b57cec5SDimitry Andric unordered_map(unordered_map&&, const Allocator&); 760b57cec5SDimitry Andric unordered_map(initializer_list<value_type>, size_type n = 0, 770b57cec5SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 780b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 790b57cec5SDimitry Andric unordered_map(size_type n, const allocator_type& a) 800b57cec5SDimitry Andric : unordered_map(n, hasher(), key_equal(), a) {} // C++14 810b57cec5SDimitry Andric unordered_map(size_type n, const hasher& hf, const allocator_type& a) 820b57cec5SDimitry Andric : unordered_map(n, hf, key_equal(), a) {} // C++14 830b57cec5SDimitry Andric template <class InputIterator> 840b57cec5SDimitry Andric unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 850b57cec5SDimitry Andric : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 860b57cec5SDimitry Andric template <class InputIterator> 870b57cec5SDimitry Andric unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 880b57cec5SDimitry Andric const allocator_type& a) 890b57cec5SDimitry Andric : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 9006c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 9106c3fb27SDimitry Andric unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a) 9206c3fb27SDimitry Andric : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 9306c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 9406c3fb27SDimitry Andric unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 9506c3fb27SDimitry Andric : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 960b57cec5SDimitry Andric unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 970b57cec5SDimitry Andric : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 980b57cec5SDimitry Andric unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 990b57cec5SDimitry Andric const allocator_type& a) 1000b57cec5SDimitry Andric : unordered_map(il, n, hf, key_equal(), a) {} // C++14 1010b57cec5SDimitry Andric ~unordered_map(); 1020b57cec5SDimitry Andric unordered_map& operator=(const unordered_map&); 1030b57cec5SDimitry Andric unordered_map& operator=(unordered_map&&) 1040b57cec5SDimitry Andric noexcept( 1050b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 1060b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 1070b57cec5SDimitry Andric is_nothrow_move_assignable<hasher>::value && 1080b57cec5SDimitry Andric is_nothrow_move_assignable<key_equal>::value); 1090b57cec5SDimitry Andric unordered_map& operator=(initializer_list<value_type>); 1100b57cec5SDimitry Andric 1110b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 1120b57cec5SDimitry Andric 1130b57cec5SDimitry Andric bool empty() const noexcept; 1140b57cec5SDimitry Andric size_type size() const noexcept; 1150b57cec5SDimitry Andric size_type max_size() const noexcept; 1160b57cec5SDimitry Andric 1170b57cec5SDimitry Andric iterator begin() noexcept; 1180b57cec5SDimitry Andric iterator end() noexcept; 1190b57cec5SDimitry Andric const_iterator begin() const noexcept; 1200b57cec5SDimitry Andric const_iterator end() const noexcept; 1210b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 1220b57cec5SDimitry Andric const_iterator cend() const noexcept; 1230b57cec5SDimitry Andric 1240b57cec5SDimitry Andric template <class... Args> 1250b57cec5SDimitry Andric pair<iterator, bool> emplace(Args&&... args); 1260b57cec5SDimitry Andric template <class... Args> 1270b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 1280b57cec5SDimitry Andric pair<iterator, bool> insert(const value_type& obj); 1290b57cec5SDimitry Andric template <class P> 1300b57cec5SDimitry Andric pair<iterator, bool> insert(P&& obj); 1310b57cec5SDimitry Andric iterator insert(const_iterator hint, const value_type& obj); 1320b57cec5SDimitry Andric template <class P> 1330b57cec5SDimitry Andric iterator insert(const_iterator hint, P&& obj); 1340b57cec5SDimitry Andric template <class InputIterator> 1350b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 13606c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 13706c3fb27SDimitry Andric void insert_range(R&& rg); // C++23 1380b57cec5SDimitry Andric void insert(initializer_list<value_type>); 1390b57cec5SDimitry Andric 1400b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 1410b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 1420b57cec5SDimitry Andric insert_return_type insert(node_type&& nh); // C++17 1430b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 1440b57cec5SDimitry Andric 1450b57cec5SDimitry Andric template <class... Args> 1460b57cec5SDimitry Andric pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17 1470b57cec5SDimitry Andric template <class... Args> 1480b57cec5SDimitry Andric pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17 1490b57cec5SDimitry Andric template <class... Args> 1500b57cec5SDimitry Andric iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17 1510b57cec5SDimitry Andric template <class... Args> 1520b57cec5SDimitry Andric iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17 1530b57cec5SDimitry Andric template <class M> 1540b57cec5SDimitry Andric pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 1550b57cec5SDimitry Andric template <class M> 1560b57cec5SDimitry Andric pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 1570b57cec5SDimitry Andric template <class M> 1580b57cec5SDimitry Andric iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 1590b57cec5SDimitry Andric template <class M> 1600b57cec5SDimitry Andric iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 1610b57cec5SDimitry Andric 1620b57cec5SDimitry Andric iterator erase(const_iterator position); 1630b57cec5SDimitry Andric iterator erase(iterator position); // C++14 1640b57cec5SDimitry Andric size_type erase(const key_type& k); 1650b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 1660b57cec5SDimitry Andric void clear() noexcept; 1670b57cec5SDimitry Andric 1680b57cec5SDimitry Andric template<class H2, class P2> 1690b57cec5SDimitry Andric void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 1700b57cec5SDimitry Andric template<class H2, class P2> 1710b57cec5SDimitry Andric void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 1720b57cec5SDimitry Andric template<class H2, class P2> 1730b57cec5SDimitry Andric void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 1740b57cec5SDimitry Andric template<class H2, class P2> 1750b57cec5SDimitry Andric void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 1760b57cec5SDimitry Andric 1770b57cec5SDimitry Andric void swap(unordered_map&) 1780b57cec5SDimitry Andric noexcept( 1790b57cec5SDimitry Andric (!allocator_type::propagate_on_container_swap::value || 1800b57cec5SDimitry Andric __is_nothrow_swappable<allocator_type>::value) && 1810b57cec5SDimitry Andric __is_nothrow_swappable<hasher>::value && 1820b57cec5SDimitry Andric __is_nothrow_swappable<key_equal>::value); 1830b57cec5SDimitry Andric 1840b57cec5SDimitry Andric hasher hash_function() const; 1850b57cec5SDimitry Andric key_equal key_eq() const; 1860b57cec5SDimitry Andric 1870b57cec5SDimitry Andric iterator find(const key_type& k); 1880b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 189e8d8bef9SDimitry Andric template<typename K> 190e8d8bef9SDimitry Andric iterator find(const K& x); // C++20 191e8d8bef9SDimitry Andric template<typename K> 192e8d8bef9SDimitry Andric const_iterator find(const K& x) const; // C++20 1930b57cec5SDimitry Andric size_type count(const key_type& k) const; 194e8d8bef9SDimitry Andric template<typename K> 195e8d8bef9SDimitry Andric size_type count(const K& k) const; // C++20 1960b57cec5SDimitry Andric bool contains(const key_type& k) const; // C++20 197e8d8bef9SDimitry Andric template<typename K> 198e8d8bef9SDimitry Andric bool contains(const K& k) const; // C++20 1990b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& k); 2000b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 201e8d8bef9SDimitry Andric template<typename K> 202e8d8bef9SDimitry Andric pair<iterator, iterator> equal_range(const K& k); // C++20 203e8d8bef9SDimitry Andric template<typename K> 204e8d8bef9SDimitry Andric pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 2050b57cec5SDimitry Andric 2060b57cec5SDimitry Andric mapped_type& operator[](const key_type& k); 2070b57cec5SDimitry Andric mapped_type& operator[](key_type&& k); 2080b57cec5SDimitry Andric 2090b57cec5SDimitry Andric mapped_type& at(const key_type& k); 2100b57cec5SDimitry Andric const mapped_type& at(const key_type& k) const; 2110b57cec5SDimitry Andric 2120b57cec5SDimitry Andric size_type bucket_count() const noexcept; 2130b57cec5SDimitry Andric size_type max_bucket_count() const noexcept; 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andric size_type bucket_size(size_type n) const; 2160b57cec5SDimitry Andric size_type bucket(const key_type& k) const; 2170b57cec5SDimitry Andric 2180b57cec5SDimitry Andric local_iterator begin(size_type n); 2190b57cec5SDimitry Andric local_iterator end(size_type n); 2200b57cec5SDimitry Andric const_local_iterator begin(size_type n) const; 2210b57cec5SDimitry Andric const_local_iterator end(size_type n) const; 2220b57cec5SDimitry Andric const_local_iterator cbegin(size_type n) const; 2230b57cec5SDimitry Andric const_local_iterator cend(size_type n) const; 2240b57cec5SDimitry Andric 2250b57cec5SDimitry Andric float load_factor() const noexcept; 2260b57cec5SDimitry Andric float max_load_factor() const noexcept; 2270b57cec5SDimitry Andric void max_load_factor(float z); 2280b57cec5SDimitry Andric void rehash(size_type n); 2290b57cec5SDimitry Andric void reserve(size_type n); 2300b57cec5SDimitry Andric}; 2310b57cec5SDimitry Andric 232349cc55cSDimitry Andrictemplate<class InputIterator, 233349cc55cSDimitry Andric class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>, 234349cc55cSDimitry Andric class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 235349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, typename see below::size_type = see below, 236349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 237349cc55cSDimitry Andric -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, 238349cc55cSDimitry Andric Allocator>; // C++17 239349cc55cSDimitry Andric 24006c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash = hash<range-key-type<R>>, 24106c3fb27SDimitry Andric class Pred = equal_to<range-key-type<R>>, 24206c3fb27SDimitry Andric class Allocator = allocator<range-to-alloc-type<R>>> 24306c3fb27SDimitry Andric unordered_map(from_range_t, R&&, typename see below::size_type = see below, 24406c3fb27SDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 24506c3fb27SDimitry Andric -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23 24606c3fb27SDimitry Andric 247349cc55cSDimitry Andrictemplate<class Key, class T, class Hash = hash<Key>, 248349cc55cSDimitry Andric class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> 249349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, 250349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 251349cc55cSDimitry Andric -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17 252349cc55cSDimitry Andric 253349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 254349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator) 255349cc55cSDimitry Andric -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 256349cc55cSDimitry Andric hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 257349cc55cSDimitry Andric 258349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 259349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, Allocator) 260349cc55cSDimitry Andric -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 261349cc55cSDimitry Andric hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 262349cc55cSDimitry Andric 263349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator> 264349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator) 265349cc55cSDimitry Andric -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, 266349cc55cSDimitry Andric equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 267349cc55cSDimitry Andric 26806c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 26906c3fb27SDimitry Andric unordered_map(from_range_t, R&&, typename see below::size_type, Allocator) 27006c3fb27SDimitry Andric -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 27106c3fb27SDimitry Andric equal_to<range-key-type<R>>, Allocator>; // C++23 27206c3fb27SDimitry Andric 27306c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 27406c3fb27SDimitry Andric unordered_map(from_range_t, R&&, Allocator) 27506c3fb27SDimitry Andric -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 27606c3fb27SDimitry Andric equal_to<range-key-type<R>>, Allocator>; // C++23 27706c3fb27SDimitry Andric 27806c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator> 27906c3fb27SDimitry Andric unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 28006c3fb27SDimitry Andric -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, 28106c3fb27SDimitry Andric equal_to<range-key-type<R>>, Allocator>; // C++23 28206c3fb27SDimitry Andric 283349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator> 284349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) 285349cc55cSDimitry Andric -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 286349cc55cSDimitry Andric 287349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator> 288349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, Allocator) 289349cc55cSDimitry Andric -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 290349cc55cSDimitry Andric 291349cc55cSDimitry Andrictemplate<class Key, class T, class Hash, class Allocator> 292349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator) 293349cc55cSDimitry Andric -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17 294349cc55cSDimitry Andric 2950b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc> 2960b57cec5SDimitry Andric void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 2970b57cec5SDimitry Andric unordered_map<Key, T, Hash, Pred, Alloc>& y) 2980b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 2990b57cec5SDimitry Andric 3000b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc> 3010b57cec5SDimitry Andric bool 3020b57cec5SDimitry Andric operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 3030b57cec5SDimitry Andric const unordered_map<Key, T, Hash, Pred, Alloc>& y); 3040b57cec5SDimitry Andric 3050b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc> 3060b57cec5SDimitry Andric bool 3070b57cec5SDimitry Andric operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 30806c3fb27SDimitry Andric const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20 3090b57cec5SDimitry Andric 3100b57cec5SDimitry Andrictemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 3110b57cec5SDimitry Andric class Alloc = allocator<pair<const Key, T>>> 3120b57cec5SDimitry Andricclass unordered_multimap 3130b57cec5SDimitry Andric{ 3140b57cec5SDimitry Andricpublic: 3150b57cec5SDimitry Andric // types 3160b57cec5SDimitry Andric typedef Key key_type; 3170b57cec5SDimitry Andric typedef T mapped_type; 3180b57cec5SDimitry Andric typedef Hash hasher; 3190b57cec5SDimitry Andric typedef Pred key_equal; 3200b57cec5SDimitry Andric typedef Alloc allocator_type; 3210b57cec5SDimitry Andric typedef pair<const key_type, mapped_type> value_type; 3220b57cec5SDimitry Andric typedef value_type& reference; 3230b57cec5SDimitry Andric typedef const value_type& const_reference; 3240b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::pointer pointer; 3250b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 3260b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::size_type size_type; 3270b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::difference_type difference_type; 3280b57cec5SDimitry Andric 3290b57cec5SDimitry Andric typedef /unspecified/ iterator; 3300b57cec5SDimitry Andric typedef /unspecified/ const_iterator; 3310b57cec5SDimitry Andric typedef /unspecified/ local_iterator; 3320b57cec5SDimitry Andric typedef /unspecified/ const_local_iterator; 3330b57cec5SDimitry Andric 3340b57cec5SDimitry Andric typedef unspecified node_type; // C++17 3350b57cec5SDimitry Andric 3360b57cec5SDimitry Andric unordered_multimap() 3370b57cec5SDimitry Andric noexcept( 3380b57cec5SDimitry Andric is_nothrow_default_constructible<hasher>::value && 3390b57cec5SDimitry Andric is_nothrow_default_constructible<key_equal>::value && 3400b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value); 3410b57cec5SDimitry Andric explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 3420b57cec5SDimitry Andric const key_equal& eql = key_equal(), 3430b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 3440b57cec5SDimitry Andric template <class InputIterator> 3450b57cec5SDimitry Andric unordered_multimap(InputIterator f, InputIterator l, 3460b57cec5SDimitry Andric size_type n = 0, const hasher& hf = hasher(), 3470b57cec5SDimitry Andric const key_equal& eql = key_equal(), 3480b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 34906c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 35006c3fb27SDimitry Andric unordered_multimap(from_range_t, R&& rg, size_type n = see below, 35106c3fb27SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 35206c3fb27SDimitry Andric const allocator_type& a = allocator_type()); // C++23 3530b57cec5SDimitry Andric explicit unordered_multimap(const allocator_type&); 3540b57cec5SDimitry Andric unordered_multimap(const unordered_multimap&); 3550b57cec5SDimitry Andric unordered_multimap(const unordered_multimap&, const Allocator&); 3560b57cec5SDimitry Andric unordered_multimap(unordered_multimap&&) 3570b57cec5SDimitry Andric noexcept( 3580b57cec5SDimitry Andric is_nothrow_move_constructible<hasher>::value && 3590b57cec5SDimitry Andric is_nothrow_move_constructible<key_equal>::value && 3600b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value); 3610b57cec5SDimitry Andric unordered_multimap(unordered_multimap&&, const Allocator&); 3620b57cec5SDimitry Andric unordered_multimap(initializer_list<value_type>, size_type n = 0, 3630b57cec5SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 3640b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 3650b57cec5SDimitry Andric unordered_multimap(size_type n, const allocator_type& a) 3660b57cec5SDimitry Andric : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 3670b57cec5SDimitry Andric unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 3680b57cec5SDimitry Andric : unordered_multimap(n, hf, key_equal(), a) {} // C++14 3690b57cec5SDimitry Andric template <class InputIterator> 3700b57cec5SDimitry Andric unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 3710b57cec5SDimitry Andric : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 3720b57cec5SDimitry Andric template <class InputIterator> 3730b57cec5SDimitry Andric unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 3740b57cec5SDimitry Andric const allocator_type& a) 3750b57cec5SDimitry Andric : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 37606c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 37706c3fb27SDimitry Andric unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a) 37806c3fb27SDimitry Andric : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 37906c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 38006c3fb27SDimitry Andric unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 38106c3fb27SDimitry Andric : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 3820b57cec5SDimitry Andric unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 3830b57cec5SDimitry Andric : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 3840b57cec5SDimitry Andric unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 3850b57cec5SDimitry Andric const allocator_type& a) 3860b57cec5SDimitry Andric : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 3870b57cec5SDimitry Andric ~unordered_multimap(); 3880b57cec5SDimitry Andric unordered_multimap& operator=(const unordered_multimap&); 3890b57cec5SDimitry Andric unordered_multimap& operator=(unordered_multimap&&) 3900b57cec5SDimitry Andric noexcept( 3910b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 3920b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 3930b57cec5SDimitry Andric is_nothrow_move_assignable<hasher>::value && 3940b57cec5SDimitry Andric is_nothrow_move_assignable<key_equal>::value); 3950b57cec5SDimitry Andric unordered_multimap& operator=(initializer_list<value_type>); 3960b57cec5SDimitry Andric 3970b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 3980b57cec5SDimitry Andric 3990b57cec5SDimitry Andric bool empty() const noexcept; 4000b57cec5SDimitry Andric size_type size() const noexcept; 4010b57cec5SDimitry Andric size_type max_size() const noexcept; 4020b57cec5SDimitry Andric 4030b57cec5SDimitry Andric iterator begin() noexcept; 4040b57cec5SDimitry Andric iterator end() noexcept; 4050b57cec5SDimitry Andric const_iterator begin() const noexcept; 4060b57cec5SDimitry Andric const_iterator end() const noexcept; 4070b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 4080b57cec5SDimitry Andric const_iterator cend() const noexcept; 4090b57cec5SDimitry Andric 4100b57cec5SDimitry Andric template <class... Args> 4110b57cec5SDimitry Andric iterator emplace(Args&&... args); 4120b57cec5SDimitry Andric template <class... Args> 4130b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 4140b57cec5SDimitry Andric iterator insert(const value_type& obj); 4150b57cec5SDimitry Andric template <class P> 4160b57cec5SDimitry Andric iterator insert(P&& obj); 4170b57cec5SDimitry Andric iterator insert(const_iterator hint, const value_type& obj); 4180b57cec5SDimitry Andric template <class P> 4190b57cec5SDimitry Andric iterator insert(const_iterator hint, P&& obj); 4200b57cec5SDimitry Andric template <class InputIterator> 4210b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 42206c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 42306c3fb27SDimitry Andric void insert_range(R&& rg); // C++23 4240b57cec5SDimitry Andric void insert(initializer_list<value_type>); 4250b57cec5SDimitry Andric 4260b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 4270b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 4280b57cec5SDimitry Andric iterator insert(node_type&& nh); // C++17 4290b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 4300b57cec5SDimitry Andric 4310b57cec5SDimitry Andric iterator erase(const_iterator position); 4320b57cec5SDimitry Andric iterator erase(iterator position); // C++14 4330b57cec5SDimitry Andric size_type erase(const key_type& k); 4340b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 4350b57cec5SDimitry Andric void clear() noexcept; 4360b57cec5SDimitry Andric 4370b57cec5SDimitry Andric template<class H2, class P2> 4380b57cec5SDimitry Andric void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source); // C++17 4390b57cec5SDimitry Andric template<class H2, class P2> 4400b57cec5SDimitry Andric void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source); // C++17 4410b57cec5SDimitry Andric template<class H2, class P2> 4420b57cec5SDimitry Andric void merge(unordered_map<Key, T, H2, P2, Allocator>& source); // C++17 4430b57cec5SDimitry Andric template<class H2, class P2> 4440b57cec5SDimitry Andric void merge(unordered_map<Key, T, H2, P2, Allocator>&& source); // C++17 4450b57cec5SDimitry Andric 4460b57cec5SDimitry Andric void swap(unordered_multimap&) 4470b57cec5SDimitry Andric noexcept( 4480b57cec5SDimitry Andric (!allocator_type::propagate_on_container_swap::value || 4490b57cec5SDimitry Andric __is_nothrow_swappable<allocator_type>::value) && 4500b57cec5SDimitry Andric __is_nothrow_swappable<hasher>::value && 4510b57cec5SDimitry Andric __is_nothrow_swappable<key_equal>::value); 4520b57cec5SDimitry Andric 4530b57cec5SDimitry Andric hasher hash_function() const; 4540b57cec5SDimitry Andric key_equal key_eq() const; 4550b57cec5SDimitry Andric 4560b57cec5SDimitry Andric iterator find(const key_type& k); 4570b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 458e8d8bef9SDimitry Andric template<typename K> 459e8d8bef9SDimitry Andric iterator find(const K& x); // C++20 460e8d8bef9SDimitry Andric template<typename K> 461e8d8bef9SDimitry Andric const_iterator find(const K& x) const; // C++20 4620b57cec5SDimitry Andric size_type count(const key_type& k) const; 463e8d8bef9SDimitry Andric template<typename K> 464e8d8bef9SDimitry Andric size_type count(const K& k) const; // C++20 4650b57cec5SDimitry Andric bool contains(const key_type& k) const; // C++20 466e8d8bef9SDimitry Andric template<typename K> 467e8d8bef9SDimitry Andric bool contains(const K& k) const; // C++20 4680b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& k); 4690b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 470e8d8bef9SDimitry Andric template<typename K> 471e8d8bef9SDimitry Andric pair<iterator, iterator> equal_range(const K& k); // C++20 472e8d8bef9SDimitry Andric template<typename K> 473e8d8bef9SDimitry Andric pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 4740b57cec5SDimitry Andric 4750b57cec5SDimitry Andric size_type bucket_count() const noexcept; 4760b57cec5SDimitry Andric size_type max_bucket_count() const noexcept; 4770b57cec5SDimitry Andric 4780b57cec5SDimitry Andric size_type bucket_size(size_type n) const; 4790b57cec5SDimitry Andric size_type bucket(const key_type& k) const; 4800b57cec5SDimitry Andric 4810b57cec5SDimitry Andric local_iterator begin(size_type n); 4820b57cec5SDimitry Andric local_iterator end(size_type n); 4830b57cec5SDimitry Andric const_local_iterator begin(size_type n) const; 4840b57cec5SDimitry Andric const_local_iterator end(size_type n) const; 4850b57cec5SDimitry Andric const_local_iterator cbegin(size_type n) const; 4860b57cec5SDimitry Andric const_local_iterator cend(size_type n) const; 4870b57cec5SDimitry Andric 4880b57cec5SDimitry Andric float load_factor() const noexcept; 4890b57cec5SDimitry Andric float max_load_factor() const noexcept; 4900b57cec5SDimitry Andric void max_load_factor(float z); 4910b57cec5SDimitry Andric void rehash(size_type n); 4920b57cec5SDimitry Andric void reserve(size_type n); 4930b57cec5SDimitry Andric}; 4940b57cec5SDimitry Andric 495349cc55cSDimitry Andrictemplate<class InputIterator, 496349cc55cSDimitry Andric class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>, 497349cc55cSDimitry Andric class Allocator = allocator<iter_to_alloc_t<InputIterator>>> 498349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below, 499349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 500349cc55cSDimitry Andric -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred, 501349cc55cSDimitry Andric Allocator>; // C++17 502349cc55cSDimitry Andric 50306c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash = hash<range-key-type<R>>, 50406c3fb27SDimitry Andric class Pred = equal_to<range-key-type<R>>, 50506c3fb27SDimitry Andric class Allocator = allocator<range-to-alloc-type<R>>> 50606c3fb27SDimitry Andric unordered_multimap(from_range_t, R&&, typename see below::size_type = see below, 50706c3fb27SDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 50806c3fb27SDimitry Andric -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23 50906c3fb27SDimitry Andric 510349cc55cSDimitry Andrictemplate<class Key, class T, class Hash = hash<Key>, 511349cc55cSDimitry Andric class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> 512349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below, 513349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 514349cc55cSDimitry Andric -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17 515349cc55cSDimitry Andric 516349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 517349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator) 518349cc55cSDimitry Andric -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 519349cc55cSDimitry Andric hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 520349cc55cSDimitry Andric 521349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 522349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, Allocator) 523349cc55cSDimitry Andric -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, 524349cc55cSDimitry Andric hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 525349cc55cSDimitry Andric 526349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator> 527349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator) 528349cc55cSDimitry Andric -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash, 529349cc55cSDimitry Andric equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17 530349cc55cSDimitry Andric 53106c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 53206c3fb27SDimitry Andric unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator) 53306c3fb27SDimitry Andric -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 53406c3fb27SDimitry Andric equal_to<range-key-type<R>>, Allocator>; // C++23 53506c3fb27SDimitry Andric 53606c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 53706c3fb27SDimitry Andric unordered_multimap(from_range_t, R&&, Allocator) 53806c3fb27SDimitry Andric -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>, 53906c3fb27SDimitry Andric equal_to<range-key-type<R>>, Allocator>; // C++23 54006c3fb27SDimitry Andric 54106c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator> 54206c3fb27SDimitry Andric unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 54306c3fb27SDimitry Andric -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, 54406c3fb27SDimitry Andric equal_to<range-key-type<R>>, Allocator>; // C++23 54506c3fb27SDimitry Andric 546349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator> 547349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator) 548349cc55cSDimitry Andric -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 549349cc55cSDimitry Andric 550349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator> 551349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, Allocator) 552349cc55cSDimitry Andric -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17 553349cc55cSDimitry Andric 554349cc55cSDimitry Andrictemplate<class Key, class T, class Hash, class Allocator> 555349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, 556349cc55cSDimitry Andric Allocator) 557349cc55cSDimitry Andric -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17 558349cc55cSDimitry Andric 5590b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc> 5600b57cec5SDimitry Andric void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 5610b57cec5SDimitry Andric unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 5620b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 5630b57cec5SDimitry Andric 5640b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate> 5655ffd83dbSDimitry Andric typename unordered_map<K, T, H, P, A>::size_type 5665ffd83dbSDimitry Andric erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred); // C++20 5670b57cec5SDimitry Andric 5680b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate> 5695ffd83dbSDimitry Andric typename unordered_multimap<K, T, H, P, A>::size_type 5705ffd83dbSDimitry Andric erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred); // C++20 5710b57cec5SDimitry Andric 5720b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc> 5730b57cec5SDimitry Andric bool 5740b57cec5SDimitry Andric operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 5750b57cec5SDimitry Andric const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 5760b57cec5SDimitry Andric 5770b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc> 5780b57cec5SDimitry Andric bool 5790b57cec5SDimitry Andric operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 58006c3fb27SDimitry Andric const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20 5810b57cec5SDimitry Andric 5820b57cec5SDimitry Andric} // std 5830b57cec5SDimitry Andric 5840b57cec5SDimitry Andric*/ 5850b57cec5SDimitry Andric 58681ad6265SDimitry Andric#include <__algorithm/is_permutation.h> 58781ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler 58806c3fb27SDimitry Andric#include <__availability> 5890b57cec5SDimitry Andric#include <__config> 590fe6060f1SDimitry Andric#include <__functional/is_transparent.h> 59181ad6265SDimitry Andric#include <__functional/operations.h> 5920b57cec5SDimitry Andric#include <__hash_table> 59381ad6265SDimitry Andric#include <__iterator/distance.h> 59481ad6265SDimitry Andric#include <__iterator/erase_if_container.h> 59504eeddc0SDimitry Andric#include <__iterator/iterator_traits.h> 59606c3fb27SDimitry Andric#include <__iterator/ranges_iterator_traits.h> 59704eeddc0SDimitry Andric#include <__memory/addressof.h> 598bdd1243dSDimitry Andric#include <__memory/allocator.h> 599bdd1243dSDimitry Andric#include <__memory_resource/polymorphic_allocator.h> 6000b57cec5SDimitry Andric#include <__node_handle> 60106c3fb27SDimitry Andric#include <__ranges/concepts.h> 60206c3fb27SDimitry Andric#include <__ranges/container_compatible_range.h> 60306c3fb27SDimitry Andric#include <__ranges/from_range.h> 604bdd1243dSDimitry Andric#include <__type_traits/is_allocator.h> 60506c3fb27SDimitry Andric#include <__type_traits/type_identity.h> 606fe6060f1SDimitry Andric#include <__utility/forward.h> 6070b57cec5SDimitry Andric#include <stdexcept> 6080b57cec5SDimitry Andric#include <tuple> 6090b57cec5SDimitry Andric#include <version> 6100b57cec5SDimitry Andric 61181ad6265SDimitry Andric// standard-mandated includes 61281ad6265SDimitry Andric 61381ad6265SDimitry Andric// [iterator.range] 61481ad6265SDimitry Andric#include <__iterator/access.h> 61581ad6265SDimitry Andric#include <__iterator/data.h> 61681ad6265SDimitry Andric#include <__iterator/empty.h> 61781ad6265SDimitry Andric#include <__iterator/reverse_access.h> 61881ad6265SDimitry Andric#include <__iterator/size.h> 61981ad6265SDimitry Andric 62081ad6265SDimitry Andric// [unord.map.syn] 62181ad6265SDimitry Andric#include <compare> 62281ad6265SDimitry Andric#include <initializer_list> 62381ad6265SDimitry Andric 6240b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 6250b57cec5SDimitry Andric# pragma GCC system_header 6260b57cec5SDimitry Andric#endif 6270b57cec5SDimitry Andric 628*b3edf446SDimitry Andric_LIBCPP_PUSH_MACROS 629*b3edf446SDimitry Andric#include <__undef_macros> 630*b3edf446SDimitry Andric 6310b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 6320b57cec5SDimitry Andric 633cb14a3feSDimitry Andrictemplate <class _Key, 634cb14a3feSDimitry Andric class _Cp, 635cb14a3feSDimitry Andric class _Hash, 636cb14a3feSDimitry Andric class _Pred, 6370b57cec5SDimitry Andric bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value> 638cb14a3feSDimitry Andricclass __unordered_map_hasher : private _Hash { 6390b57cec5SDimitry Andricpublic: 640cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) : _Hash() {} 641cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 6420b57cec5SDimitry Andric : _Hash(__h) {} 643cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; } 644cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { 645cb14a3feSDimitry Andric return static_cast<const _Hash&>(*this)(__x.__get_value().first); 646cb14a3feSDimitry Andric } 647cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); } 64806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 649349cc55cSDimitry Andric template <typename _K2> 650cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const { 651cb14a3feSDimitry Andric return static_cast<const _Hash&>(*this)(__x); 652cb14a3feSDimitry Andric } 653e8d8bef9SDimitry Andric#endif 654cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) { 6555f757f3fSDimitry Andric using std::swap; 6560b57cec5SDimitry Andric swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y)); 6570b57cec5SDimitry Andric } 6580b57cec5SDimitry Andric}; 6590b57cec5SDimitry Andric 660e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Hash, class _Pred> 661cb14a3feSDimitry Andricclass __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> { 6620b57cec5SDimitry Andric _Hash __hash_; 663cb14a3feSDimitry Andric 6640b57cec5SDimitry Andricpublic: 665cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 6660b57cec5SDimitry Andric : __hash_() {} 667cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 6680b57cec5SDimitry Andric : __hash_(__h) {} 669cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; } 670cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); } 671cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); } 67206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 673349cc55cSDimitry Andric template <typename _K2> 674cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const { 675cb14a3feSDimitry Andric return __hash_(__x); 676cb14a3feSDimitry Andric } 677e8d8bef9SDimitry Andric#endif 678cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) { 6795f757f3fSDimitry Andric using std::swap; 6800b57cec5SDimitry Andric swap(__hash_, __y.__hash_); 6810b57cec5SDimitry Andric } 6820b57cec5SDimitry Andric}; 6830b57cec5SDimitry Andric 684e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Hash, class _Pred, bool __b> 685cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 686e8d8bef9SDimitry Andricswap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x, 687cb14a3feSDimitry Andric __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 6880b57cec5SDimitry Andric __x.swap(__y); 6890b57cec5SDimitry Andric} 6900b57cec5SDimitry Andric 691cb14a3feSDimitry Andrictemplate <class _Key, 692cb14a3feSDimitry Andric class _Cp, 693cb14a3feSDimitry Andric class _Pred, 694cb14a3feSDimitry Andric class _Hash, 6950b57cec5SDimitry Andric bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value> 696cb14a3feSDimitry Andricclass __unordered_map_equal : private _Pred { 6970b57cec5SDimitry Andricpublic: 698cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) : _Pred() {} 699cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 7000b57cec5SDimitry Andric : _Pred(__p) {} 701cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; } 702cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { 703cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first); 704cb14a3feSDimitry Andric } 705cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { 706cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y); 707cb14a3feSDimitry Andric } 708cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { 709cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first); 710cb14a3feSDimitry Andric } 71106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 712349cc55cSDimitry Andric template <typename _K2> 713cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const { 714cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y); 715cb14a3feSDimitry Andric } 716349cc55cSDimitry Andric template <typename _K2> 717cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const { 718cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first); 719cb14a3feSDimitry Andric } 720349cc55cSDimitry Andric template <typename _K2> 721cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const { 722cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x, __y); 723cb14a3feSDimitry Andric } 724349cc55cSDimitry Andric template <typename _K2> 725cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const { 726cb14a3feSDimitry Andric return static_cast<const _Pred&>(*this)(__x, __y); 727cb14a3feSDimitry Andric } 728e8d8bef9SDimitry Andric#endif 729cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) { 7305f757f3fSDimitry Andric using std::swap; 7310b57cec5SDimitry Andric swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y)); 7320b57cec5SDimitry Andric } 7330b57cec5SDimitry Andric}; 7340b57cec5SDimitry Andric 735e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Pred, class _Hash> 736cb14a3feSDimitry Andricclass __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> { 7370b57cec5SDimitry Andric _Pred __pred_; 738cb14a3feSDimitry Andric 7390b57cec5SDimitry Andricpublic: 740cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 7410b57cec5SDimitry Andric : __pred_() {} 742cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 7430b57cec5SDimitry Andric : __pred_(__p) {} 744cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; } 745cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { 746cb14a3feSDimitry Andric return __pred_(__x.__get_value().first, __y.__get_value().first); 747cb14a3feSDimitry Andric } 748cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { 749cb14a3feSDimitry Andric return __pred_(__x.__get_value().first, __y); 750cb14a3feSDimitry Andric } 751cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { 752cb14a3feSDimitry Andric return __pred_(__x, __y.__get_value().first); 753cb14a3feSDimitry Andric } 75406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 755349cc55cSDimitry Andric template <typename _K2> 756cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const { 757cb14a3feSDimitry Andric return __pred_(__x.__get_value().first, __y); 758cb14a3feSDimitry Andric } 759349cc55cSDimitry Andric template <typename _K2> 760cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const { 761cb14a3feSDimitry Andric return __pred_(__x, __y.__get_value().first); 762cb14a3feSDimitry Andric } 763349cc55cSDimitry Andric template <typename _K2> 764cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const { 765cb14a3feSDimitry Andric return __pred_(__x, __y); 766cb14a3feSDimitry Andric } 767349cc55cSDimitry Andric template <typename _K2> 768cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const { 769cb14a3feSDimitry Andric return __pred_(__x, __y); 770cb14a3feSDimitry Andric } 771e8d8bef9SDimitry Andric#endif 772cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) { 7735f757f3fSDimitry Andric using std::swap; 7740b57cec5SDimitry Andric swap(__pred_, __y.__pred_); 7750b57cec5SDimitry Andric } 7760b57cec5SDimitry Andric}; 7770b57cec5SDimitry Andric 778e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Pred, class _Hash, bool __b> 779cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 780cb14a3feSDimitry Andricswap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y) 781cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 7820b57cec5SDimitry Andric __x.swap(__y); 7830b57cec5SDimitry Andric} 7840b57cec5SDimitry Andric 7850b57cec5SDimitry Andrictemplate <class _Alloc> 786cb14a3feSDimitry Andricclass __hash_map_node_destructor { 7870b57cec5SDimitry Andric typedef _Alloc allocator_type; 7880b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 7890b57cec5SDimitry Andric 7900b57cec5SDimitry Andricpublic: 7910b57cec5SDimitry Andric typedef typename __alloc_traits::pointer pointer; 7920b57cec5SDimitry Andric 793cb14a3feSDimitry Andricprivate: 7940b57cec5SDimitry Andric allocator_type& __na_; 7950b57cec5SDimitry Andric 7960b57cec5SDimitry Andric __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 7970b57cec5SDimitry Andric 7980b57cec5SDimitry Andricpublic: 7990b57cec5SDimitry Andric bool __first_constructed; 8000b57cec5SDimitry Andric bool __second_constructed; 8010b57cec5SDimitry Andric 802cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 8030b57cec5SDimitry Andric : __na_(__na), 8040b57cec5SDimitry Andric __first_constructed(false), 805cb14a3feSDimitry Andric __second_constructed(false) {} 8060b57cec5SDimitry Andric 8070b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 808cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT 8090b57cec5SDimitry Andric : __na_(__x.__na_), 8100b57cec5SDimitry Andric __first_constructed(__x.__value_constructed), 811cb14a3feSDimitry Andric __second_constructed(__x.__value_constructed) { 8120b57cec5SDimitry Andric __x.__value_constructed = false; 8130b57cec5SDimitry Andric } 8140b57cec5SDimitry Andric#else // _LIBCPP_CXX03_LANG 815cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 816cb14a3feSDimitry Andric : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { 8170b57cec5SDimitry Andric const_cast<bool&>(__x.__value_constructed) = false; 8180b57cec5SDimitry Andric } 8190b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 8200b57cec5SDimitry Andric 821cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { 8220b57cec5SDimitry Andric if (__second_constructed) 8235f757f3fSDimitry Andric __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second)); 8240b57cec5SDimitry Andric if (__first_constructed) 8255f757f3fSDimitry Andric __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first)); 8260b57cec5SDimitry Andric if (__p) 8270b57cec5SDimitry Andric __alloc_traits::deallocate(__na_, __p, 1); 8280b57cec5SDimitry Andric } 8290b57cec5SDimitry Andric}; 8300b57cec5SDimitry Andric 8310b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 8320b57cec5SDimitry Andrictemplate <class _Key, class _Tp> 833cb14a3feSDimitry Andricstruct _LIBCPP_STANDALONE_DEBUG __hash_value_type { 8340b57cec5SDimitry Andric typedef _Key key_type; 8350b57cec5SDimitry Andric typedef _Tp mapped_type; 8360b57cec5SDimitry Andric typedef pair<const key_type, mapped_type> value_type; 8370b57cec5SDimitry Andric typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; 8380b57cec5SDimitry Andric typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; 8390b57cec5SDimitry Andric 8400b57cec5SDimitry Andricprivate: 841bdd1243dSDimitry Andric value_type __cc_; 8420b57cec5SDimitry Andric 8430b57cec5SDimitry Andricpublic: 844cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { 84506c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 8465f757f3fSDimitry Andric return *std::launder(std::addressof(__cc_)); 8470b57cec5SDimitry Andric# else 848bdd1243dSDimitry Andric return __cc_; 8490b57cec5SDimitry Andric# endif 8500b57cec5SDimitry Andric } 8510b57cec5SDimitry Andric 852cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { 85306c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 17 8545f757f3fSDimitry Andric return *std::launder(std::addressof(__cc_)); 8550b57cec5SDimitry Andric# else 856bdd1243dSDimitry Andric return __cc_; 8570b57cec5SDimitry Andric# endif 8580b57cec5SDimitry Andric } 8590b57cec5SDimitry Andric 860cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() { 8610b57cec5SDimitry Andric value_type& __v = __get_value(); 8620b57cec5SDimitry Andric return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); 8630b57cec5SDimitry Andric } 8640b57cec5SDimitry Andric 865cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() { 8660b57cec5SDimitry Andric value_type& __v = __get_value(); 867cb14a3feSDimitry Andric return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second)); 8680b57cec5SDimitry Andric } 8690b57cec5SDimitry Andric 870cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(const __hash_value_type& __v) { 8710b57cec5SDimitry Andric __ref() = __v.__get_value(); 8720b57cec5SDimitry Andric return *this; 8730b57cec5SDimitry Andric } 8740b57cec5SDimitry Andric 875cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(__hash_value_type&& __v) { 8760b57cec5SDimitry Andric __ref() = __v.__move(); 8770b57cec5SDimitry Andric return *this; 8780b57cec5SDimitry Andric } 8790b57cec5SDimitry Andric 880cb14a3feSDimitry Andric template <class _ValueTp, class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value> > 881cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(_ValueTp&& __v) { 8825f757f3fSDimitry Andric __ref() = std::forward<_ValueTp>(__v); 8830b57cec5SDimitry Andric return *this; 8840b57cec5SDimitry Andric } 8850b57cec5SDimitry Andric 8860b57cec5SDimitry Andricprivate: 8870b57cec5SDimitry Andric __hash_value_type(const __hash_value_type& __v) = delete; 8880b57cec5SDimitry Andric __hash_value_type(__hash_value_type&& __v) = delete; 8890b57cec5SDimitry Andric template <class... _Args> 8900b57cec5SDimitry Andric explicit __hash_value_type(_Args&&... __args) = delete; 8910b57cec5SDimitry Andric 8920b57cec5SDimitry Andric ~__hash_value_type() = delete; 8930b57cec5SDimitry Andric}; 8940b57cec5SDimitry Andric 8950b57cec5SDimitry Andric#else 8960b57cec5SDimitry Andric 8970b57cec5SDimitry Andrictemplate <class _Key, class _Tp> 898cb14a3feSDimitry Andricstruct __hash_value_type { 8990b57cec5SDimitry Andric typedef _Key key_type; 9000b57cec5SDimitry Andric typedef _Tp mapped_type; 9010b57cec5SDimitry Andric typedef pair<const key_type, mapped_type> value_type; 9020b57cec5SDimitry Andric 9030b57cec5SDimitry Andricprivate: 904bdd1243dSDimitry Andric value_type __cc_; 9050b57cec5SDimitry Andric 9060b57cec5SDimitry Andricpublic: 907cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; } 908cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; } 9090b57cec5SDimitry Andric 9100b57cec5SDimitry Andricprivate: 9110b57cec5SDimitry Andric ~__hash_value_type(); 9120b57cec5SDimitry Andric}; 9130b57cec5SDimitry Andric 9140b57cec5SDimitry Andric#endif 9150b57cec5SDimitry Andric 9160b57cec5SDimitry Andrictemplate <class _HashIterator> 917cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __hash_map_iterator { 9180b57cec5SDimitry Andric _HashIterator __i_; 9190b57cec5SDimitry Andric 9200b57cec5SDimitry Andric typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 9210b57cec5SDimitry Andric 9220b57cec5SDimitry Andricpublic: 9230b57cec5SDimitry Andric typedef forward_iterator_tag iterator_category; 9240b57cec5SDimitry Andric typedef typename _NodeTypes::__map_value_type value_type; 9250b57cec5SDimitry Andric typedef typename _NodeTypes::difference_type difference_type; 9260b57cec5SDimitry Andric typedef value_type& reference; 9270b57cec5SDimitry Andric typedef typename _NodeTypes::__map_value_type_pointer pointer; 9280b57cec5SDimitry Andric 929cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {} 9300b57cec5SDimitry Andric 931cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 9320b57cec5SDimitry Andric 933cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 934cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 9350b57cec5SDimitry Andric 936cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() { 937cb14a3feSDimitry Andric ++__i_; 938cb14a3feSDimitry Andric return *this; 939cb14a3feSDimitry Andric } 940cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) { 9410b57cec5SDimitry Andric __hash_map_iterator __t(*this); 9420b57cec5SDimitry Andric ++(*this); 9430b57cec5SDimitry Andric return __t; 9440b57cec5SDimitry Andric } 9450b57cec5SDimitry Andric 946cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 947cb14a3feSDimitry Andric return __x.__i_ == __y.__i_; 948cb14a3feSDimitry Andric } 94906c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 950cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 951cb14a3feSDimitry Andric return __x.__i_ != __y.__i_; 952cb14a3feSDimitry Andric } 95306c3fb27SDimitry Andric#endif 9540b57cec5SDimitry Andric 955cb14a3feSDimitry Andric template <class, class, class, class, class> 956cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_map; 957cb14a3feSDimitry Andric template <class, class, class, class, class> 958cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 959cb14a3feSDimitry Andric template <class> 960cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 961cb14a3feSDimitry Andric template <class> 962cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 963cb14a3feSDimitry Andric template <class> 964cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 9650b57cec5SDimitry Andric}; 9660b57cec5SDimitry Andric 9670b57cec5SDimitry Andrictemplate <class _HashIterator> 968cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator { 9690b57cec5SDimitry Andric _HashIterator __i_; 9700b57cec5SDimitry Andric 9710b57cec5SDimitry Andric typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes; 9720b57cec5SDimitry Andric 9730b57cec5SDimitry Andricpublic: 9740b57cec5SDimitry Andric typedef forward_iterator_tag iterator_category; 9750b57cec5SDimitry Andric typedef typename _NodeTypes::__map_value_type value_type; 9760b57cec5SDimitry Andric typedef typename _NodeTypes::difference_type difference_type; 9770b57cec5SDimitry Andric typedef const value_type& reference; 9780b57cec5SDimitry Andric typedef typename _NodeTypes::__const_map_value_type_pointer pointer; 9790b57cec5SDimitry Andric 980cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {} 9810b57cec5SDimitry Andric 982cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 9835f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 984cb14a3feSDimitry Andric __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT 9850b57cec5SDimitry Andric : __i_(__i.__i_) {} 9860b57cec5SDimitry Andric 987cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } 988cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } 9890b57cec5SDimitry Andric 990cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() { 991cb14a3feSDimitry Andric ++__i_; 992cb14a3feSDimitry Andric return *this; 993cb14a3feSDimitry Andric } 994cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) { 9950b57cec5SDimitry Andric __hash_map_const_iterator __t(*this); 9960b57cec5SDimitry Andric ++(*this); 9970b57cec5SDimitry Andric return __t; 9980b57cec5SDimitry Andric } 9990b57cec5SDimitry Andric 1000cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool 1001cb14a3feSDimitry Andric operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 1002cb14a3feSDimitry Andric return __x.__i_ == __y.__i_; 1003cb14a3feSDimitry Andric } 100406c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 1005cb14a3feSDimitry Andric friend _LIBCPP_HIDE_FROM_ABI bool 1006cb14a3feSDimitry Andric operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 1007cb14a3feSDimitry Andric return __x.__i_ != __y.__i_; 1008cb14a3feSDimitry Andric } 100906c3fb27SDimitry Andric#endif 10100b57cec5SDimitry Andric 1011cb14a3feSDimitry Andric template <class, class, class, class, class> 1012cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1013cb14a3feSDimitry Andric template <class, class, class, class, class> 1014cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1015cb14a3feSDimitry Andric template <class> 1016cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 1017cb14a3feSDimitry Andric template <class> 1018cb14a3feSDimitry Andric friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 10190b57cec5SDimitry Andric}; 10200b57cec5SDimitry Andric 10210b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 10220b57cec5SDimitry Andricclass unordered_multimap; 10230b57cec5SDimitry Andric 1024cb14a3feSDimitry Andrictemplate <class _Key, 1025cb14a3feSDimitry Andric class _Tp, 1026cb14a3feSDimitry Andric class _Hash = hash<_Key>, 1027cb14a3feSDimitry Andric class _Pred = equal_to<_Key>, 10280b57cec5SDimitry Andric class _Alloc = allocator<pair<const _Key, _Tp> > > 1029cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_map { 10300b57cec5SDimitry Andricpublic: 10310b57cec5SDimitry Andric // types 10320b57cec5SDimitry Andric typedef _Key key_type; 10330b57cec5SDimitry Andric typedef _Tp mapped_type; 103481ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 103581ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 103681ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 10370b57cec5SDimitry Andric typedef pair<const key_type, mapped_type> value_type; 10380b57cec5SDimitry Andric typedef value_type& reference; 10390b57cec5SDimitry Andric typedef const value_type& const_reference; 10400b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 104106c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 10420b57cec5SDimitry Andric 10430b57cec5SDimitry Andricprivate: 10440b57cec5SDimitry Andric typedef __hash_value_type<key_type, mapped_type> __value_type; 1045e8d8bef9SDimitry Andric typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1046e8d8bef9SDimitry Andric typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1047bdd1243dSDimitry Andric typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 10480b57cec5SDimitry Andric 1049cb14a3feSDimitry Andric typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 10500b57cec5SDimitry Andric 10510b57cec5SDimitry Andric __table __table_; 10520b57cec5SDimitry Andric 10530b57cec5SDimitry Andric typedef typename __table::_NodeTypes _NodeTypes; 10540b57cec5SDimitry Andric typedef typename __table::__node_pointer __node_pointer; 10550b57cec5SDimitry Andric typedef typename __table::__node_const_pointer __node_const_pointer; 10560b57cec5SDimitry Andric typedef typename __table::__node_traits __node_traits; 10570b57cec5SDimitry Andric typedef typename __table::__node_allocator __node_allocator; 10580b57cec5SDimitry Andric typedef typename __table::__node __node; 10590b57cec5SDimitry Andric typedef __hash_map_node_destructor<__node_allocator> _Dp; 10600b57cec5SDimitry Andric typedef unique_ptr<__node, _Dp> __node_holder; 10610b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 10620b57cec5SDimitry Andric 1063bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, 1064bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 1065bdd1243dSDimitry Andric "original allocator"); 1066bdd1243dSDimitry Andric 10670b57cec5SDimitry Andric static_assert((is_same<typename __table::__container_value_type, value_type>::value), ""); 10680b57cec5SDimitry Andric static_assert((is_same<typename __table::__node_value_type, __value_type>::value), ""); 1069cb14a3feSDimitry Andric 10700b57cec5SDimitry Andricpublic: 10710b57cec5SDimitry Andric typedef typename __alloc_traits::pointer pointer; 10720b57cec5SDimitry Andric typedef typename __alloc_traits::const_pointer const_pointer; 10730b57cec5SDimitry Andric typedef typename __table::size_type size_type; 10740b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 10750b57cec5SDimitry Andric 10760b57cec5SDimitry Andric typedef __hash_map_iterator<typename __table::iterator> iterator; 10770b57cec5SDimitry Andric typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 10780b57cec5SDimitry Andric typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 10790b57cec5SDimitry Andric typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 10800b57cec5SDimitry Andric 108106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 10820b57cec5SDimitry Andric typedef __map_node_handle<__node, allocator_type> node_type; 10830b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 10840b57cec5SDimitry Andric#endif 10850b57cec5SDimitry Andric 10860b57cec5SDimitry Andric template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 10870b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_map; 10880b57cec5SDimitry Andric template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 10890b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 10900b57cec5SDimitry Andric 1091cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1092cb14a3feSDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI 1093cb14a3feSDimitry Andric unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 10945f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1095cb14a3feSDimitry Andric unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 10960b57cec5SDimitry Andric template <class _InputIterator> 109706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last); 10980b57cec5SDimitry Andric template <class _InputIterator> 1099cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1100cb14a3feSDimitry Andric unordered_map(_InputIterator __first, 1101cb14a3feSDimitry Andric _InputIterator __last, 1102cb14a3feSDimitry Andric size_type __n, 1103cb14a3feSDimitry Andric const hasher& __hf = hasher(), 11040b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 11050b57cec5SDimitry Andric template <class _InputIterator> 1106cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map( 1107cb14a3feSDimitry Andric _InputIterator __first, 1108cb14a3feSDimitry Andric _InputIterator __last, 1109cb14a3feSDimitry Andric size_type __n, 1110cb14a3feSDimitry Andric const hasher& __hf, 11110b57cec5SDimitry Andric const key_equal& __eql, 11120b57cec5SDimitry Andric const allocator_type& __a); 111306c3fb27SDimitry Andric 111406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 111506c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1116cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map( 1117cb14a3feSDimitry Andric from_range_t, 1118cb14a3feSDimitry Andric _Range&& __range, 1119cb14a3feSDimitry Andric size_type __n = /*implementation-defined*/ 0, 1120cb14a3feSDimitry Andric const hasher& __hf = hasher(), 1121cb14a3feSDimitry Andric const key_equal& __eql = key_equal(), 112206c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 112306c3fb27SDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 112406c3fb27SDimitry Andric if (__n > 0) { 112506c3fb27SDimitry Andric __table_.__rehash_unique(__n); 112606c3fb27SDimitry Andric } 112706c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 112806c3fb27SDimitry Andric } 112906c3fb27SDimitry Andric#endif 113006c3fb27SDimitry Andric 1131cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a); 113206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u); 113306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a); 11340b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1135cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 113606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a); 113706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il); 1138cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1139cb14a3feSDimitry Andric unordered_map(initializer_list<value_type> __il, 1140cb14a3feSDimitry Andric size_type __n, 1141cb14a3feSDimitry Andric const hasher& __hf = hasher(), 1142cb14a3feSDimitry Andric const key_equal& __eql = key_equal()); 1143cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map( 1144cb14a3feSDimitry Andric initializer_list<value_type> __il, 1145cb14a3feSDimitry Andric size_type __n, 1146cb14a3feSDimitry Andric const hasher& __hf, 1147cb14a3feSDimitry Andric const key_equal& __eql, 11480b57cec5SDimitry Andric const allocator_type& __a); 11490b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 115006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 1151cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a) 11520b57cec5SDimitry Andric : unordered_map(__n, hasher(), key_equal(), __a) {} 1153cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 11540b57cec5SDimitry Andric : unordered_map(__n, __hf, key_equal(), __a) {} 11550b57cec5SDimitry Andric template <class _InputIterator> 11565f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 11570b57cec5SDimitry Andric unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 11580b57cec5SDimitry Andric : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 11590b57cec5SDimitry Andric template <class _InputIterator> 1160cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map( 1161cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 11620b57cec5SDimitry Andric : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 116306c3fb27SDimitry Andric 116406c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 116506c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1166cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 116706c3fb27SDimitry Andric : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 116806c3fb27SDimitry Andric 116906c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 117006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 117106c3fb27SDimitry Andric unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 117206c3fb27SDimitry Andric : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 117306c3fb27SDimitry Andric# endif 117406c3fb27SDimitry Andric 1175cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 11760b57cec5SDimitry Andric : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 11775f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1178cb14a3feSDimitry Andric unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 11790b57cec5SDimitry Andric : unordered_map(__il, __n, __hf, key_equal(), __a) {} 11800b57cec5SDimitry Andric#endif 1181cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~unordered_map() { 1182bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 11830b57cec5SDimitry Andric } 11840b57cec5SDimitry Andric 1185cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) { 11860b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 11870b57cec5SDimitry Andric __table_ = __u.__table_; 11880b57cec5SDimitry Andric#else 11895f757f3fSDimitry Andric if (this != std::addressof(__u)) { 11900b57cec5SDimitry Andric __table_.clear(); 11910b57cec5SDimitry Andric __table_.hash_function() = __u.__table_.hash_function(); 11920b57cec5SDimitry Andric __table_.key_eq() = __u.__table_.key_eq(); 11930b57cec5SDimitry Andric __table_.max_load_factor() = __u.__table_.max_load_factor(); 11940b57cec5SDimitry Andric __table_.__copy_assign_alloc(__u.__table_); 11950b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 11960b57cec5SDimitry Andric } 11970b57cec5SDimitry Andric#endif 11980b57cec5SDimitry Andric return *this; 11990b57cec5SDimitry Andric } 12000b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1201cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u) 12020b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1203cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il); 12040b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12050b57cec5SDimitry Andric 1206cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1207cb14a3feSDimitry Andric return allocator_type(__table_.__node_alloc()); 12080b57cec5SDimitry Andric } 12090b57cec5SDimitry Andric 1210cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1211cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1212cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 1213cb14a3feSDimitry Andric 1214cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1215cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1216cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1217cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1218cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1219cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 1220cb14a3feSDimitry Andric 1221cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 1222cb14a3feSDimitry Andric 1223cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 1224cb14a3feSDimitry Andric 12250b57cec5SDimitry Andric template <class _InputIterator> 1226cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 12270b57cec5SDimitry Andric 122806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 122906c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1230cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 123106c3fb27SDimitry Andric for (auto&& __element : __range) { 123206c3fb27SDimitry Andric __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 123306c3fb27SDimitry Andric } 123406c3fb27SDimitry Andric } 123506c3fb27SDimitry Andric#endif 123606c3fb27SDimitry Andric 12370b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1238cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 12390b57cec5SDimitry Andric 1240cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { 1241cb14a3feSDimitry Andric return __table_.__insert_unique(std::move(__x)); 1242cb14a3feSDimitry Andric } 12430b57cec5SDimitry Andric 124406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { 12455f757f3fSDimitry Andric return __table_.__insert_unique(std::move(__x)).first; 12460b57cec5SDimitry Andric } 12470b57cec5SDimitry Andric 1248cb14a3feSDimitry Andric template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > 1249cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) { 1250cb14a3feSDimitry Andric return __table_.__insert_unique(std::forward<_Pp>(__x)); 1251cb14a3feSDimitry Andric } 12520b57cec5SDimitry Andric 1253cb14a3feSDimitry Andric template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > 1254cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) { 12555f757f3fSDimitry Andric return insert(std::forward<_Pp>(__x)).first; 12560b57cec5SDimitry Andric } 12570b57cec5SDimitry Andric 12580b57cec5SDimitry Andric template <class... _Args> 1259cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 12605f757f3fSDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...); 12610b57cec5SDimitry Andric } 12620b57cec5SDimitry Andric 12630b57cec5SDimitry Andric template <class... _Args> 1264cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) { 12655f757f3fSDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 12660b57cec5SDimitry Andric } 12670b57cec5SDimitry Andric 12680b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12690b57cec5SDimitry Andric 127006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 12710b57cec5SDimitry Andric template <class... _Args> 1272cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { 1273cb14a3feSDimitry Andric return __table_.__emplace_unique_key_args( 1274cb14a3feSDimitry Andric __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...)); 12750b57cec5SDimitry Andric } 12760b57cec5SDimitry Andric 12770b57cec5SDimitry Andric template <class... _Args> 1278cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { 1279cb14a3feSDimitry Andric return __table_.__emplace_unique_key_args( 1280cb14a3feSDimitry Andric __k, 1281cb14a3feSDimitry Andric piecewise_construct, 12825f757f3fSDimitry Andric std::forward_as_tuple(std::move(__k)), 12835f757f3fSDimitry Andric std::forward_as_tuple(std::forward<_Args>(__args)...)); 12840b57cec5SDimitry Andric } 12850b57cec5SDimitry Andric 12860b57cec5SDimitry Andric template <class... _Args> 1287cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) { 12885f757f3fSDimitry Andric return try_emplace(__k, std::forward<_Args>(__args)...).first; 12890b57cec5SDimitry Andric } 12900b57cec5SDimitry Andric 12910b57cec5SDimitry Andric template <class... _Args> 1292cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) { 12935f757f3fSDimitry Andric return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first; 12940b57cec5SDimitry Andric } 12950b57cec5SDimitry Andric 12960b57cec5SDimitry Andric template <class _Vp> 1297cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { 1298cb14a3feSDimitry Andric pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v)); 12990b57cec5SDimitry Andric if (!__res.second) { 13005f757f3fSDimitry Andric __res.first->second = std::forward<_Vp>(__v); 13010b57cec5SDimitry Andric } 13020b57cec5SDimitry Andric return __res; 13030b57cec5SDimitry Andric } 13040b57cec5SDimitry Andric 13050b57cec5SDimitry Andric template <class _Vp> 1306cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { 1307cb14a3feSDimitry Andric pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v)); 13080b57cec5SDimitry Andric if (!__res.second) { 13095f757f3fSDimitry Andric __res.first->second = std::forward<_Vp>(__v); 13100b57cec5SDimitry Andric } 13110b57cec5SDimitry Andric return __res; 13120b57cec5SDimitry Andric } 13130b57cec5SDimitry Andric 13140b57cec5SDimitry Andric template <class _Vp> 1315cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) { 13165f757f3fSDimitry Andric return insert_or_assign(__k, std::forward<_Vp>(__v)).first; 13170b57cec5SDimitry Andric } 13180b57cec5SDimitry Andric 13190b57cec5SDimitry Andric template <class _Vp> 1320cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) { 13215f757f3fSDimitry Andric return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first; 13220b57cec5SDimitry Andric } 132306c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 17 13240b57cec5SDimitry Andric 1325cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); } 1326cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); } 1327cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 1328cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1329cb14a3feSDimitry Andric return __table_.erase(__first.__i_, __last.__i_); 1330cb14a3feSDimitry Andric } 1331cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 13320b57cec5SDimitry Andric 133306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1334cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 133506c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 13360b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_map::insert()"); 1337cb14a3feSDimitry Andric return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 13380b57cec5SDimitry Andric } 1339cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 134006c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 13410b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_map::insert()"); 1342cb14a3feSDimitry Andric return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh)); 13430b57cec5SDimitry Andric } 1344cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 13450b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 13460b57cec5SDimitry Andric } 1347cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 1348cb14a3feSDimitry Andric return __table_.template __node_handle_extract<node_type>(__it.__i_); 13490b57cec5SDimitry Andric } 13500b57cec5SDimitry Andric 13510b57cec5SDimitry Andric template <class _H2, class _P2> 1352cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 1353cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1354cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 13550b57cec5SDimitry Andric return __table_.__node_handle_merge_unique(__source.__table_); 13560b57cec5SDimitry Andric } 13570b57cec5SDimitry Andric template <class _H2, class _P2> 1358cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 1359cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1360cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 13610b57cec5SDimitry Andric return __table_.__node_handle_merge_unique(__source.__table_); 13620b57cec5SDimitry Andric } 13630b57cec5SDimitry Andric template <class _H2, class _P2> 1364cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 1365cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1366cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 13670b57cec5SDimitry Andric return __table_.__node_handle_merge_unique(__source.__table_); 13680b57cec5SDimitry Andric } 13690b57cec5SDimitry Andric template <class _H2, class _P2> 1370cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 1371cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1372cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 13730b57cec5SDimitry Andric return __table_.__node_handle_merge_unique(__source.__table_); 13740b57cec5SDimitry Andric } 13750b57cec5SDimitry Andric#endif 13760b57cec5SDimitry Andric 1377cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 1378cb14a3feSDimitry Andric __table_.swap(__u.__table_); 1379cb14a3feSDimitry Andric } 13800b57cec5SDimitry Andric 1381cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); } 1382cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 13830b57cec5SDimitry Andric 1384cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1385cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 138606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1387cb14a3feSDimitry Andric template <class _K2, 1388cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1389cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1390cb14a3feSDimitry Andric return __table_.find(__k); 1391cb14a3feSDimitry Andric } 1392cb14a3feSDimitry Andric template <class _K2, 1393cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1394cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1395cb14a3feSDimitry Andric return __table_.find(__k); 1396cb14a3feSDimitry Andric } 139706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1398e8d8bef9SDimitry Andric 1399cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 140006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1401cb14a3feSDimitry Andric template <class _K2, 1402cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1403cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1404cb14a3feSDimitry Andric return __table_.__count_unique(__k); 1405cb14a3feSDimitry Andric } 140606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1407349cc55cSDimitry Andric 140806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1409cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1410e8d8bef9SDimitry Andric 1411cb14a3feSDimitry Andric template <class _K2, 1412cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1413cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1414cb14a3feSDimitry Andric return find(__k) != end(); 1415cb14a3feSDimitry Andric } 141606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1417349cc55cSDimitry Andric 1418cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1419cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 1420cb14a3feSDimitry Andric } 1421cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1422cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 1423cb14a3feSDimitry Andric } 142406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1425cb14a3feSDimitry Andric template <class _K2, 1426cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1427cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1428cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 1429cb14a3feSDimitry Andric } 1430cb14a3feSDimitry Andric template <class _K2, 1431cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1432cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1433cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 1434cb14a3feSDimitry Andric } 143506c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 14360b57cec5SDimitry Andric 143706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 14380b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 143906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k); 14400b57cec5SDimitry Andric#endif 14410b57cec5SDimitry Andric 144206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); 144306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; 14440b57cec5SDimitry Andric 1445cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1446cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 14470b57cec5SDimitry Andric 1448cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1449cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 14500b57cec5SDimitry Andric 1451cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1452cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1453cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1454cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1455cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1456cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 14570b57cec5SDimitry Andric 1458cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1459cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1460cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1461cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 1462cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 14630b57cec5SDimitry Andric 14640b57cec5SDimitry Andricprivate: 14650b57cec5SDimitry Andric#ifdef _LIBCPP_CXX03_LANG 146606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); 14670b57cec5SDimitry Andric#endif 14680b57cec5SDimitry Andric}; 14690b57cec5SDimitry Andric 1470349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 14710b57cec5SDimitry Andrictemplate <class _InputIterator, 14720b57cec5SDimitry Andric class _Hash = hash<__iter_key_type<_InputIterator>>, 14730b57cec5SDimitry Andric class _Pred = equal_to<__iter_key_type<_InputIterator>>, 14740b57cec5SDimitry Andric class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 147506c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1476349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1477349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1478349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1479349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1480cb14a3feSDimitry Andricunordered_map(_InputIterator, 1481cb14a3feSDimitry Andric _InputIterator, 1482cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1483cb14a3feSDimitry Andric _Hash = _Hash(), 1484cb14a3feSDimitry Andric _Pred = _Pred(), 1485cb14a3feSDimitry Andric _Allocator = _Allocator()) 14860b57cec5SDimitry Andric -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>; 14870b57cec5SDimitry Andric 148806c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 148906c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 149006c3fb27SDimitry Andric class _Hash = hash<__range_key_type<_Range>>, 149106c3fb27SDimitry Andric class _Pred = equal_to<__range_key_type<_Range>>, 149206c3fb27SDimitry Andric class _Allocator = allocator<__range_to_alloc_type<_Range>>, 149306c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 149406c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 149506c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 149606c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1497cb14a3feSDimitry Andricunordered_map(from_range_t, 1498cb14a3feSDimitry Andric _Range&&, 1499cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1500cb14a3feSDimitry Andric _Hash = _Hash(), 1501cb14a3feSDimitry Andric _Pred = _Pred(), 1502cb14a3feSDimitry Andric _Allocator = _Allocator()) 150306c3fb27SDimitry Andric -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23 150406c3fb27SDimitry Andric# endif 150506c3fb27SDimitry Andric 1506cb14a3feSDimitry Andrictemplate <class _Key, 1507cb14a3feSDimitry Andric class _Tp, 1508cb14a3feSDimitry Andric class _Hash = hash<remove_const_t<_Key>>, 15090b57cec5SDimitry Andric class _Pred = equal_to<remove_const_t<_Key>>, 15100b57cec5SDimitry Andric class _Allocator = allocator<pair<const _Key, _Tp>>, 1511349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1512349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1513349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1514349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1515cb14a3feSDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, 1516cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1517cb14a3feSDimitry Andric _Hash = _Hash(), 1518cb14a3feSDimitry Andric _Pred = _Pred(), 1519cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 15200b57cec5SDimitry Andric 1521cb14a3feSDimitry Andrictemplate <class _InputIterator, 1522cb14a3feSDimitry Andric class _Allocator, 152306c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1524349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 15250b57cec5SDimitry Andricunordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 1526cb14a3feSDimitry Andric -> unordered_map<__iter_key_type<_InputIterator>, 1527cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 1528cb14a3feSDimitry Andric hash<__iter_key_type<_InputIterator>>, 1529cb14a3feSDimitry Andric equal_to<__iter_key_type<_InputIterator>>, 1530cb14a3feSDimitry Andric _Allocator>; 15310b57cec5SDimitry Andric 1532cb14a3feSDimitry Andrictemplate <class _InputIterator, 1533cb14a3feSDimitry Andric class _Allocator, 153406c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1535349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 15360b57cec5SDimitry Andricunordered_map(_InputIterator, _InputIterator, _Allocator) 1537cb14a3feSDimitry Andric -> unordered_map<__iter_key_type<_InputIterator>, 1538cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 1539cb14a3feSDimitry Andric hash<__iter_key_type<_InputIterator>>, 1540cb14a3feSDimitry Andric equal_to<__iter_key_type<_InputIterator>>, 1541cb14a3feSDimitry Andric _Allocator>; 15420b57cec5SDimitry Andric 1543cb14a3feSDimitry Andrictemplate <class _InputIterator, 1544cb14a3feSDimitry Andric class _Hash, 1545cb14a3feSDimitry Andric class _Allocator, 154606c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1547349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1548349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1549349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 15500b57cec5SDimitry Andricunordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1551cb14a3feSDimitry Andric -> unordered_map<__iter_key_type<_InputIterator>, 1552cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 1553cb14a3feSDimitry Andric _Hash, 1554cb14a3feSDimitry Andric equal_to<__iter_key_type<_InputIterator>>, 1555cb14a3feSDimitry Andric _Allocator>; 15560b57cec5SDimitry Andric 155706c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 155806c3fb27SDimitry Andric 1559cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 156006c3fb27SDimitry Andricunordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1561cb14a3feSDimitry Andric -> unordered_map<__range_key_type<_Range>, 1562cb14a3feSDimitry Andric __range_mapped_type<_Range>, 1563cb14a3feSDimitry Andric hash<__range_key_type<_Range>>, 1564cb14a3feSDimitry Andric equal_to<__range_key_type<_Range>>, 1565cb14a3feSDimitry Andric _Allocator>; 156606c3fb27SDimitry Andric 1567cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 156806c3fb27SDimitry Andricunordered_map(from_range_t, _Range&&, _Allocator) 1569cb14a3feSDimitry Andric -> unordered_map<__range_key_type<_Range>, 1570cb14a3feSDimitry Andric __range_mapped_type<_Range>, 1571cb14a3feSDimitry Andric hash<__range_key_type<_Range>>, 1572cb14a3feSDimitry Andric equal_to<__range_key_type<_Range>>, 1573cb14a3feSDimitry Andric _Allocator>; 157406c3fb27SDimitry Andric 1575cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 1576cb14a3feSDimitry Andric class _Hash, 1577cb14a3feSDimitry Andric class _Allocator, 157806c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 157906c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 158006c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 158106c3fb27SDimitry Andricunordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1582cb14a3feSDimitry Andric -> unordered_map<__range_key_type<_Range>, 1583cb14a3feSDimitry Andric __range_mapped_type<_Range>, 1584cb14a3feSDimitry Andric _Hash, 1585cb14a3feSDimitry Andric equal_to<__range_key_type<_Range>>, 1586cb14a3feSDimitry Andric _Allocator>; 158706c3fb27SDimitry Andric 158806c3fb27SDimitry Andric# endif 158906c3fb27SDimitry Andric 1590cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 15910b57cec5SDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 1592cb14a3feSDimitry Andric -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>; 15930b57cec5SDimitry Andric 1594cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 15950b57cec5SDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1596cb14a3feSDimitry Andric -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>; 15970b57cec5SDimitry Andric 1598cb14a3feSDimitry Andrictemplate <class _Key, 1599cb14a3feSDimitry Andric class _Tp, 1600cb14a3feSDimitry Andric class _Hash, 1601cb14a3feSDimitry Andric class _Allocator, 1602349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1603349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1604349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 16050b57cec5SDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1606cb14a3feSDimitry Andric -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>; 16070b57cec5SDimitry Andric#endif 16080b57cec5SDimitry Andric 16090b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1610cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql) 1611cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1612753f127fSDimitry Andric __table_.__rehash_unique(__n); 16130b57cec5SDimitry Andric} 16140b57cec5SDimitry Andric 16150b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 16160b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1617cb14a3feSDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1618cb14a3feSDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1619cb14a3feSDimitry Andric __table_.__rehash_unique(__n); 1620cb14a3feSDimitry Andric} 1621cb14a3feSDimitry Andric 1622cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1623cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a) 1624cb14a3feSDimitry Andric : __table_(typename __table::allocator_type(__a)) {} 1625cb14a3feSDimitry Andric 1626cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1627cb14a3feSDimitry Andrictemplate <class _InputIterator> 1628cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) { 1629cb14a3feSDimitry Andric insert(__first, __last); 1630cb14a3feSDimitry Andric} 1631cb14a3feSDimitry Andric 1632cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1633cb14a3feSDimitry Andrictemplate <class _InputIterator> 1634cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1635cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1636cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1637cb14a3feSDimitry Andric __table_.__rehash_unique(__n); 1638cb14a3feSDimitry Andric insert(__first, __last); 1639cb14a3feSDimitry Andric} 1640cb14a3feSDimitry Andric 1641cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1642cb14a3feSDimitry Andrictemplate <class _InputIterator> 1643cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1644cb14a3feSDimitry Andric _InputIterator __first, 1645cb14a3feSDimitry Andric _InputIterator __last, 1646cb14a3feSDimitry Andric size_type __n, 1647cb14a3feSDimitry Andric const hasher& __hf, 1648cb14a3feSDimitry Andric const key_equal& __eql, 16490b57cec5SDimitry Andric const allocator_type& __a) 1650cb14a3feSDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1651753f127fSDimitry Andric __table_.__rehash_unique(__n); 16520b57cec5SDimitry Andric insert(__first, __last); 16530b57cec5SDimitry Andric} 16540b57cec5SDimitry Andric 16550b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1656cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) { 1657753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 16580b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16590b57cec5SDimitry Andric} 16600b57cec5SDimitry Andric 16610b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1662cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a) 1663cb14a3feSDimitry Andric : __table_(__u.__table_, typename __table::allocator_type(__a)) { 1664753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 16650b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16660b57cec5SDimitry Andric} 16670b57cec5SDimitry Andric 16680b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 16690b57cec5SDimitry Andric 16700b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1671cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u) 16720b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1673cb14a3feSDimitry Andric : __table_(std::move(__u.__table_)) {} 16740b57cec5SDimitry Andric 16750b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1676cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a) 1677cb14a3feSDimitry Andric : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) { 1678cb14a3feSDimitry Andric if (__a != __u.get_allocator()) { 16790b57cec5SDimitry Andric iterator __i = __u.begin(); 16800b57cec5SDimitry Andric while (__u.size() != 0) { 1681cb14a3feSDimitry Andric __table_.__emplace_unique(__u.__table_.remove((__i++).__i_)->__get_value().__move()); 16820b57cec5SDimitry Andric } 16830b57cec5SDimitry Andric } 16840b57cec5SDimitry Andric} 16850b57cec5SDimitry Andric 16860b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1687cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) { 16880b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 16890b57cec5SDimitry Andric} 16900b57cec5SDimitry Andric 16910b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 16920b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1693cb14a3feSDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1694cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1695753f127fSDimitry Andric __table_.__rehash_unique(__n); 16960b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 16970b57cec5SDimitry Andric} 16980b57cec5SDimitry Andric 16990b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 17000b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1701cb14a3feSDimitry Andric initializer_list<value_type> __il, 1702cb14a3feSDimitry Andric size_type __n, 1703cb14a3feSDimitry Andric const hasher& __hf, 1704cb14a3feSDimitry Andric const key_equal& __eql, 1705cb14a3feSDimitry Andric const allocator_type& __a) 1706cb14a3feSDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 1707753f127fSDimitry Andric __table_.__rehash_unique(__n); 17080b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17090b57cec5SDimitry Andric} 17100b57cec5SDimitry Andric 17110b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1712cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 17130b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1714cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 17155f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 17160b57cec5SDimitry Andric return *this; 17170b57cec5SDimitry Andric} 17180b57cec5SDimitry Andric 17190b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1720cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1721cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 17220b57cec5SDimitry Andric __table_.__assign_unique(__il.begin(), __il.end()); 17230b57cec5SDimitry Andric return *this; 17240b57cec5SDimitry Andric} 17250b57cec5SDimitry Andric 17260b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 17270b57cec5SDimitry Andric 17280b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 17290b57cec5SDimitry Andrictemplate <class _InputIterator> 1730cb14a3feSDimitry Andricinline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 17310b57cec5SDimitry Andric for (; __first != __last; ++__first) 17320b57cec5SDimitry Andric __table_.__insert_unique(*__first); 17330b57cec5SDimitry Andric} 17340b57cec5SDimitry Andric 17350b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 17360b57cec5SDimitry Andric 17370b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1738cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { 1739cb14a3feSDimitry Andric return __table_ 1740cb14a3feSDimitry Andric .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) 1741cb14a3feSDimitry Andric .first->__get_value() 1742cb14a3feSDimitry Andric .second; 17430b57cec5SDimitry Andric} 17440b57cec5SDimitry Andric 17450b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1746cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) { 1747cb14a3feSDimitry Andric return __table_ 1748cb14a3feSDimitry Andric .__emplace_unique_key_args( 1749cb14a3feSDimitry Andric __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) 1750cb14a3feSDimitry Andric .first->__get_value() 1751cb14a3feSDimitry Andric .second; 17520b57cec5SDimitry Andric} 17530b57cec5SDimitry Andric#else // _LIBCPP_CXX03_LANG 17540b57cec5SDimitry Andric 17550b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 17560b57cec5SDimitry Andrictypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1757cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) { 17580b57cec5SDimitry Andric __node_allocator& __na = __table_.__node_alloc(); 17590b57cec5SDimitry Andric __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 17605f757f3fSDimitry Andric __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k); 17610b57cec5SDimitry Andric __h.get_deleter().__first_constructed = true; 17625f757f3fSDimitry Andric __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second)); 17630b57cec5SDimitry Andric __h.get_deleter().__second_constructed = true; 1764e8d8bef9SDimitry Andric return __h; 17650b57cec5SDimitry Andric} 17660b57cec5SDimitry Andric 17670b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1768cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { 17690b57cec5SDimitry Andric iterator __i = find(__k); 17700b57cec5SDimitry Andric if (__i != end()) 17710b57cec5SDimitry Andric return __i->second; 17720b57cec5SDimitry Andric __node_holder __h = __construct_node_with_key(__k); 17730b57cec5SDimitry Andric pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 17740b57cec5SDimitry Andric __h.release(); 17750b57cec5SDimitry Andric return __r.first->second; 17760b57cec5SDimitry Andric} 17770b57cec5SDimitry Andric 1778fe6060f1SDimitry Andric#endif // _LIBCPP_CXX03_LANG 17790b57cec5SDimitry Andric 17800b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1781cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) { 17820b57cec5SDimitry Andric iterator __i = find(__k); 17830b57cec5SDimitry Andric if (__i == end()) 17840b57cec5SDimitry Andric __throw_out_of_range("unordered_map::at: key not found"); 17850b57cec5SDimitry Andric return __i->second; 17860b57cec5SDimitry Andric} 17870b57cec5SDimitry Andric 17880b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1789cb14a3feSDimitry Andricconst _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const { 17900b57cec5SDimitry Andric const_iterator __i = find(__k); 17910b57cec5SDimitry Andric if (__i == end()) 17920b57cec5SDimitry Andric __throw_out_of_range("unordered_map::at: key not found"); 17930b57cec5SDimitry Andric return __i->second; 17940b57cec5SDimitry Andric} 17950b57cec5SDimitry Andric 17960b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1797cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 1798cb14a3feSDimitry Andricswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1799cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 18000b57cec5SDimitry Andric __x.swap(__y); 18010b57cec5SDimitry Andric} 18020b57cec5SDimitry Andric 180306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1804cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate> 1805cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 1806cb14a3feSDimitry Andricerase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 18075f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 18085ffd83dbSDimitry Andric} 18090b57cec5SDimitry Andric#endif 18100b57cec5SDimitry Andric 18110b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1812cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1813cb14a3feSDimitry Andric const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 18140b57cec5SDimitry Andric if (__x.size() != __y.size()) 18150b57cec5SDimitry Andric return false; 1816cb14a3feSDimitry Andric typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1817cb14a3feSDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 18180b57cec5SDimitry Andric const_iterator __j = __y.find(__i->first); 18190b57cec5SDimitry Andric if (__j == __ey || !(*__i == *__j)) 18200b57cec5SDimitry Andric return false; 18210b57cec5SDimitry Andric } 18220b57cec5SDimitry Andric return true; 18230b57cec5SDimitry Andric} 18240b57cec5SDimitry Andric 182506c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 182606c3fb27SDimitry Andric 18270b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1828cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1829cb14a3feSDimitry Andric const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 18300b57cec5SDimitry Andric return !(__x == __y); 18310b57cec5SDimitry Andric} 18320b57cec5SDimitry Andric 183306c3fb27SDimitry Andric#endif 183406c3fb27SDimitry Andric 1835cb14a3feSDimitry Andrictemplate <class _Key, 1836cb14a3feSDimitry Andric class _Tp, 1837cb14a3feSDimitry Andric class _Hash = hash<_Key>, 1838cb14a3feSDimitry Andric class _Pred = equal_to<_Key>, 18390b57cec5SDimitry Andric class _Alloc = allocator<pair<const _Key, _Tp> > > 1840cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multimap { 18410b57cec5SDimitry Andricpublic: 18420b57cec5SDimitry Andric // types 18430b57cec5SDimitry Andric typedef _Key key_type; 18440b57cec5SDimitry Andric typedef _Tp mapped_type; 184581ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 184681ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 184781ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 18480b57cec5SDimitry Andric typedef pair<const key_type, mapped_type> value_type; 18490b57cec5SDimitry Andric typedef value_type& reference; 18500b57cec5SDimitry Andric typedef const value_type& const_reference; 18510b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 185206c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 18530b57cec5SDimitry Andric 18540b57cec5SDimitry Andricprivate: 18550b57cec5SDimitry Andric typedef __hash_value_type<key_type, mapped_type> __value_type; 1856e8d8bef9SDimitry Andric typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher; 1857e8d8bef9SDimitry Andric typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal; 1858bdd1243dSDimitry Andric typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; 18590b57cec5SDimitry Andric 1860cb14a3feSDimitry Andric typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 18610b57cec5SDimitry Andric 18620b57cec5SDimitry Andric __table __table_; 18630b57cec5SDimitry Andric 18640b57cec5SDimitry Andric typedef typename __table::_NodeTypes _NodeTypes; 18650b57cec5SDimitry Andric typedef typename __table::__node_traits __node_traits; 18660b57cec5SDimitry Andric typedef typename __table::__node_allocator __node_allocator; 18670b57cec5SDimitry Andric typedef typename __table::__node __node; 18680b57cec5SDimitry Andric typedef __hash_map_node_destructor<__node_allocator> _Dp; 18690b57cec5SDimitry Andric typedef unique_ptr<__node, _Dp> __node_holder; 18700b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 1871cb14a3feSDimitry Andric static_assert((is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value), 18720b57cec5SDimitry Andric "Allocator uses different size_type for different types"); 1873bdd1243dSDimitry Andric 1874bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, 1875bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 1876bdd1243dSDimitry Andric "original allocator"); 1877bdd1243dSDimitry Andric 18780b57cec5SDimitry Andricpublic: 18790b57cec5SDimitry Andric typedef typename __alloc_traits::pointer pointer; 18800b57cec5SDimitry Andric typedef typename __alloc_traits::const_pointer const_pointer; 18810b57cec5SDimitry Andric typedef typename __table::size_type size_type; 18820b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 18830b57cec5SDimitry Andric 18840b57cec5SDimitry Andric typedef __hash_map_iterator<typename __table::iterator> iterator; 18850b57cec5SDimitry Andric typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 18860b57cec5SDimitry Andric typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 18870b57cec5SDimitry Andric typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 18880b57cec5SDimitry Andric 188906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 18900b57cec5SDimitry Andric typedef __map_node_handle<__node, allocator_type> node_type; 18910b57cec5SDimitry Andric#endif 18920b57cec5SDimitry Andric 18930b57cec5SDimitry Andric template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 18940b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_map; 18950b57cec5SDimitry Andric template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2> 18960b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 18970b57cec5SDimitry Andric 1898cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1899cb14a3feSDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI 1900cb14a3feSDimitry Andric unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 19015f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1902cb14a3feSDimitry Andric unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 19030b57cec5SDimitry Andric template <class _InputIterator> 190406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last); 19050b57cec5SDimitry Andric template <class _InputIterator> 1906cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1907cb14a3feSDimitry Andric _InputIterator __first, 1908cb14a3feSDimitry Andric _InputIterator __last, 1909cb14a3feSDimitry Andric size_type __n, 1910cb14a3feSDimitry Andric const hasher& __hf = hasher(), 19110b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 19120b57cec5SDimitry Andric template <class _InputIterator> 1913cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1914cb14a3feSDimitry Andric _InputIterator __first, 1915cb14a3feSDimitry Andric _InputIterator __last, 1916cb14a3feSDimitry Andric size_type __n, 1917cb14a3feSDimitry Andric const hasher& __hf, 19180b57cec5SDimitry Andric const key_equal& __eql, 19190b57cec5SDimitry Andric const allocator_type& __a); 192006c3fb27SDimitry Andric 192106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 192206c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1923cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1924cb14a3feSDimitry Andric from_range_t, 1925cb14a3feSDimitry Andric _Range&& __range, 1926cb14a3feSDimitry Andric size_type __n = /*implementation-defined*/ 0, 1927cb14a3feSDimitry Andric const hasher& __hf = hasher(), 1928cb14a3feSDimitry Andric const key_equal& __eql = key_equal(), 192906c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 193006c3fb27SDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 193106c3fb27SDimitry Andric if (__n > 0) { 193206c3fb27SDimitry Andric __table_.__rehash_multi(__n); 193306c3fb27SDimitry Andric } 193406c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 193506c3fb27SDimitry Andric } 193606c3fb27SDimitry Andric#endif 193706c3fb27SDimitry Andric 1938cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a); 193906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u); 194006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 19410b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1942cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u) 19430b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 194406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 194506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il); 1946cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1947cb14a3feSDimitry Andric initializer_list<value_type> __il, 1948cb14a3feSDimitry Andric size_type __n, 19490b57cec5SDimitry Andric const hasher& __hf = hasher(), 19500b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 1951cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1952cb14a3feSDimitry Andric initializer_list<value_type> __il, 1953cb14a3feSDimitry Andric size_type __n, 1954cb14a3feSDimitry Andric const hasher& __hf, 1955cb14a3feSDimitry Andric const key_equal& __eql, 19560b57cec5SDimitry Andric const allocator_type& __a); 19570b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 195806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 1959cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a) 19600b57cec5SDimitry Andric : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1961cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 19620b57cec5SDimitry Andric : unordered_multimap(__n, __hf, key_equal(), __a) {} 19630b57cec5SDimitry Andric template <class _InputIterator> 19645f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 19650b57cec5SDimitry Andric unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 19660b57cec5SDimitry Andric : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 19670b57cec5SDimitry Andric template <class _InputIterator> 1968cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap( 1969cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 19700b57cec5SDimitry Andric : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 197106c3fb27SDimitry Andric 197206c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 197306c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1974cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 197506c3fb27SDimitry Andric : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 197606c3fb27SDimitry Andric 197706c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 197806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 197906c3fb27SDimitry Andric unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 198006c3fb27SDimitry Andric : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 198106c3fb27SDimitry Andric# endif 198206c3fb27SDimitry Andric 1983cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 19840b57cec5SDimitry Andric : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 19855f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1986cb14a3feSDimitry Andric unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 19870b57cec5SDimitry Andric : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 19880b57cec5SDimitry Andric#endif 1989cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() { 1990bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), ""); 19910b57cec5SDimitry Andric } 19920b57cec5SDimitry Andric 1993cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) { 19940b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 19950b57cec5SDimitry Andric __table_ = __u.__table_; 19960b57cec5SDimitry Andric#else 19975f757f3fSDimitry Andric if (this != std::addressof(__u)) { 19980b57cec5SDimitry Andric __table_.clear(); 19990b57cec5SDimitry Andric __table_.hash_function() = __u.__table_.hash_function(); 20000b57cec5SDimitry Andric __table_.key_eq() = __u.__table_.key_eq(); 20010b57cec5SDimitry Andric __table_.max_load_factor() = __u.__table_.max_load_factor(); 20020b57cec5SDimitry Andric __table_.__copy_assign_alloc(__u.__table_); 20030b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 20040b57cec5SDimitry Andric } 20050b57cec5SDimitry Andric#endif 20060b57cec5SDimitry Andric return *this; 20070b57cec5SDimitry Andric } 20080b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 2009cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u) 20100b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 2011cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il); 20120b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 20130b57cec5SDimitry Andric 2014cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 2015cb14a3feSDimitry Andric return allocator_type(__table_.__node_alloc()); 2016cb14a3feSDimitry Andric } 20170b57cec5SDimitry Andric 2018cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 2019cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 2020cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 20210b57cec5SDimitry Andric 2022cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 2023cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 2024cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 2025cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 2026cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 2027cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 20280b57cec5SDimitry Andric 2029cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 20300b57cec5SDimitry Andric 2031cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 2032cb14a3feSDimitry Andric return __table_.__insert_multi(__p.__i_, __x); 2033cb14a3feSDimitry Andric } 20340b57cec5SDimitry Andric 20350b57cec5SDimitry Andric template <class _InputIterator> 2036cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 20370b57cec5SDimitry Andric 203806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 203906c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 2040cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 204106c3fb27SDimitry Andric for (auto&& __element : __range) { 204206c3fb27SDimitry Andric __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 204306c3fb27SDimitry Andric } 204406c3fb27SDimitry Andric } 204506c3fb27SDimitry Andric#endif 204606c3fb27SDimitry Andric 20470b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 2048cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 2049cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); } 20500b57cec5SDimitry Andric 2051cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 2052cb14a3feSDimitry Andric return __table_.__insert_multi(__p.__i_, std::move(__x)); 2053cb14a3feSDimitry Andric } 20540b57cec5SDimitry Andric 2055cb14a3feSDimitry Andric template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > 2056cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) { 2057cb14a3feSDimitry Andric return __table_.__insert_multi(std::forward<_Pp>(__x)); 2058cb14a3feSDimitry Andric } 20590b57cec5SDimitry Andric 2060cb14a3feSDimitry Andric template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > 2061cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) { 2062cb14a3feSDimitry Andric return __table_.__insert_multi(__p.__i_, std::forward<_Pp>(__x)); 2063cb14a3feSDimitry Andric } 20640b57cec5SDimitry Andric 20650b57cec5SDimitry Andric template <class... _Args> 206606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 20675f757f3fSDimitry Andric return __table_.__emplace_multi(std::forward<_Args>(__args)...); 20680b57cec5SDimitry Andric } 20690b57cec5SDimitry Andric 20700b57cec5SDimitry Andric template <class... _Args> 207106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 20725f757f3fSDimitry Andric return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...); 20730b57cec5SDimitry Andric } 20740b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 20750b57cec5SDimitry Andric 2076cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); } 2077cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); } 2078cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 2079cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 2080cb14a3feSDimitry Andric return __table_.erase(__first.__i_, __last.__i_); 2081cb14a3feSDimitry Andric } 2082cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 20830b57cec5SDimitry Andric 208406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 2085cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 208606c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 20870b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2088cb14a3feSDimitry Andric return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 20890b57cec5SDimitry Andric } 2090cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 209106c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 20920b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multimap::insert()"); 2093cb14a3feSDimitry Andric return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh)); 20940b57cec5SDimitry Andric } 2095cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 20960b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 20970b57cec5SDimitry Andric } 2098cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 2099cb14a3feSDimitry Andric return __table_.template __node_handle_extract<node_type>(__it.__i_); 21000b57cec5SDimitry Andric } 21010b57cec5SDimitry Andric 21020b57cec5SDimitry Andric template <class _H2, class _P2> 2103cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 2104cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2105cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 21060b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 21070b57cec5SDimitry Andric } 21080b57cec5SDimitry Andric template <class _H2, class _P2> 2109cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 2110cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2111cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 21120b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 21130b57cec5SDimitry Andric } 21140b57cec5SDimitry Andric template <class _H2, class _P2> 2115cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) { 2116cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2117cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 21180b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 21190b57cec5SDimitry Andric } 21200b57cec5SDimitry Andric template <class _H2, class _P2> 2121cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) { 2122cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 2123cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 21240b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 21250b57cec5SDimitry Andric } 21260b57cec5SDimitry Andric#endif 21270b57cec5SDimitry Andric 2128cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 2129cb14a3feSDimitry Andric __table_.swap(__u.__table_); 2130cb14a3feSDimitry Andric } 21310b57cec5SDimitry Andric 2132cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); } 2133cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 21340b57cec5SDimitry Andric 2135cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 2136cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 213706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 2138cb14a3feSDimitry Andric template <class _K2, 2139cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2140cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 2141cb14a3feSDimitry Andric return __table_.find(__k); 2142cb14a3feSDimitry Andric } 2143cb14a3feSDimitry Andric template <class _K2, 2144cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2145cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 2146cb14a3feSDimitry Andric return __table_.find(__k); 2147cb14a3feSDimitry Andric } 214806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 2149349cc55cSDimitry Andric 2150cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 215106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 2152cb14a3feSDimitry Andric template <class _K2, 2153cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2154cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 2155cb14a3feSDimitry Andric return __table_.__count_multi(__k); 2156cb14a3feSDimitry Andric } 215706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 2158349cc55cSDimitry Andric 215906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 2160cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 2161e8d8bef9SDimitry Andric 2162cb14a3feSDimitry Andric template <class _K2, 2163cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2164cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 2165cb14a3feSDimitry Andric return find(__k) != end(); 2166cb14a3feSDimitry Andric } 216706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 2168349cc55cSDimitry Andric 2169cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 2170cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 2171cb14a3feSDimitry Andric } 2172cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 2173cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 2174cb14a3feSDimitry Andric } 217506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 2176cb14a3feSDimitry Andric template <class _K2, 2177cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2178cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 2179cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 2180cb14a3feSDimitry Andric } 2181cb14a3feSDimitry Andric template <class _K2, 2182cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 2183cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 2184cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 2185cb14a3feSDimitry Andric } 218606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 21870b57cec5SDimitry Andric 2188cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 2189cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 21900b57cec5SDimitry Andric 2191cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 2192cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 21930b57cec5SDimitry Andric 2194cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 2195cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 2196cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 2197cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 2198cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 2199cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 22000b57cec5SDimitry Andric 2201cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 2202cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 2203cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 2204cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 2205cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 22060b57cec5SDimitry Andric}; 22070b57cec5SDimitry Andric 2208349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 22090b57cec5SDimitry Andrictemplate <class _InputIterator, 22100b57cec5SDimitry Andric class _Hash = hash<__iter_key_type<_InputIterator>>, 22110b57cec5SDimitry Andric class _Pred = equal_to<__iter_key_type<_InputIterator>>, 22120b57cec5SDimitry Andric class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, 221306c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2214349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 2215349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 2216349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 2217349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 2218cb14a3feSDimitry Andricunordered_multimap(_InputIterator, 2219cb14a3feSDimitry Andric _InputIterator, 2220cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 2221cb14a3feSDimitry Andric _Hash = _Hash(), 2222cb14a3feSDimitry Andric _Pred = _Pred(), 2223cb14a3feSDimitry Andric _Allocator = _Allocator()) 2224cb14a3feSDimitry Andric -> unordered_multimap<__iter_key_type<_InputIterator>, 2225cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 2226cb14a3feSDimitry Andric _Hash, 2227cb14a3feSDimitry Andric _Pred, 2228cb14a3feSDimitry Andric _Allocator>; 22290b57cec5SDimitry Andric 223006c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 223106c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 223206c3fb27SDimitry Andric class _Hash = hash<__range_key_type<_Range>>, 223306c3fb27SDimitry Andric class _Pred = equal_to<__range_key_type<_Range>>, 223406c3fb27SDimitry Andric class _Allocator = allocator<__range_to_alloc_type<_Range>>, 223506c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 223606c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 223706c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 223806c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 2239cb14a3feSDimitry Andricunordered_multimap(from_range_t, 2240cb14a3feSDimitry Andric _Range&&, 2241cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 2242cb14a3feSDimitry Andric _Hash = _Hash(), 2243cb14a3feSDimitry Andric _Pred = _Pred(), 2244cb14a3feSDimitry Andric _Allocator = _Allocator()) 224506c3fb27SDimitry Andric -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; 224606c3fb27SDimitry Andric# endif 224706c3fb27SDimitry Andric 2248cb14a3feSDimitry Andrictemplate <class _Key, 2249cb14a3feSDimitry Andric class _Tp, 2250cb14a3feSDimitry Andric class _Hash = hash<remove_const_t<_Key>>, 22510b57cec5SDimitry Andric class _Pred = equal_to<remove_const_t<_Key>>, 22520b57cec5SDimitry Andric class _Allocator = allocator<pair<const _Key, _Tp>>, 2253349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 2254349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 2255349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 2256349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 2257cb14a3feSDimitry Andricunordered_multimap(initializer_list<pair<_Key, _Tp>>, 2258cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 2259cb14a3feSDimitry Andric _Hash = _Hash(), 2260cb14a3feSDimitry Andric _Pred = _Pred(), 2261cb14a3feSDimitry Andric _Allocator = _Allocator()) 22620b57cec5SDimitry Andric -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>; 22630b57cec5SDimitry Andric 2264cb14a3feSDimitry Andrictemplate <class _InputIterator, 2265cb14a3feSDimitry Andric class _Allocator, 226606c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2267349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 22680b57cec5SDimitry Andricunordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 2269cb14a3feSDimitry Andric -> unordered_multimap<__iter_key_type<_InputIterator>, 2270cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 2271cb14a3feSDimitry Andric hash<__iter_key_type<_InputIterator>>, 2272cb14a3feSDimitry Andric equal_to<__iter_key_type<_InputIterator>>, 2273cb14a3feSDimitry Andric _Allocator>; 22740b57cec5SDimitry Andric 2275cb14a3feSDimitry Andrictemplate <class _InputIterator, 2276cb14a3feSDimitry Andric class _Allocator, 227706c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2278349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 22790b57cec5SDimitry Andricunordered_multimap(_InputIterator, _InputIterator, _Allocator) 2280cb14a3feSDimitry Andric -> unordered_multimap<__iter_key_type<_InputIterator>, 2281cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 2282cb14a3feSDimitry Andric hash<__iter_key_type<_InputIterator>>, 2283cb14a3feSDimitry Andric equal_to<__iter_key_type<_InputIterator>>, 2284cb14a3feSDimitry Andric _Allocator>; 22850b57cec5SDimitry Andric 2286cb14a3feSDimitry Andrictemplate <class _InputIterator, 2287cb14a3feSDimitry Andric class _Hash, 2288cb14a3feSDimitry Andric class _Allocator, 228906c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 2290349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 2291349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 2292349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 22930b57cec5SDimitry Andricunordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2294cb14a3feSDimitry Andric -> unordered_multimap<__iter_key_type<_InputIterator>, 2295cb14a3feSDimitry Andric __iter_mapped_type<_InputIterator>, 2296cb14a3feSDimitry Andric _Hash, 2297cb14a3feSDimitry Andric equal_to<__iter_key_type<_InputIterator>>, 2298cb14a3feSDimitry Andric _Allocator>; 22990b57cec5SDimitry Andric 230006c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 230106c3fb27SDimitry Andric 2302cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 230306c3fb27SDimitry Andricunordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 2304cb14a3feSDimitry Andric -> unordered_multimap<__range_key_type<_Range>, 2305cb14a3feSDimitry Andric __range_mapped_type<_Range>, 2306cb14a3feSDimitry Andric hash<__range_key_type<_Range>>, 2307cb14a3feSDimitry Andric equal_to<__range_key_type<_Range>>, 2308cb14a3feSDimitry Andric _Allocator>; 230906c3fb27SDimitry Andric 2310cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 231106c3fb27SDimitry Andricunordered_multimap(from_range_t, _Range&&, _Allocator) 2312cb14a3feSDimitry Andric -> unordered_multimap<__range_key_type<_Range>, 2313cb14a3feSDimitry Andric __range_mapped_type<_Range>, 2314cb14a3feSDimitry Andric hash<__range_key_type<_Range>>, 2315cb14a3feSDimitry Andric equal_to<__range_key_type<_Range>>, 2316cb14a3feSDimitry Andric _Allocator>; 231706c3fb27SDimitry Andric 2318cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 2319cb14a3feSDimitry Andric class _Hash, 2320cb14a3feSDimitry Andric class _Allocator, 232106c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 232206c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 232306c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 232406c3fb27SDimitry Andricunordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2325cb14a3feSDimitry Andric -> unordered_multimap<__range_key_type<_Range>, 2326cb14a3feSDimitry Andric __range_mapped_type<_Range>, 2327cb14a3feSDimitry Andric _Hash, 2328cb14a3feSDimitry Andric equal_to<__range_key_type<_Range>>, 2329cb14a3feSDimitry Andric _Allocator>; 233006c3fb27SDimitry Andric 233106c3fb27SDimitry Andric# endif 233206c3fb27SDimitry Andric 2333cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 23340b57cec5SDimitry Andricunordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator) 2335cb14a3feSDimitry Andric -> unordered_multimap<remove_const_t<_Key>, 2336cb14a3feSDimitry Andric _Tp, 23370b57cec5SDimitry Andric hash<remove_const_t<_Key>>, 2338cb14a3feSDimitry Andric equal_to<remove_const_t<_Key>>, 2339cb14a3feSDimitry Andric _Allocator>; 23400b57cec5SDimitry Andric 2341cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 23420b57cec5SDimitry Andricunordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2343cb14a3feSDimitry Andric -> unordered_multimap<remove_const_t<_Key>, 2344cb14a3feSDimitry Andric _Tp, 23450b57cec5SDimitry Andric hash<remove_const_t<_Key>>, 2346cb14a3feSDimitry Andric equal_to<remove_const_t<_Key>>, 2347cb14a3feSDimitry Andric _Allocator>; 23480b57cec5SDimitry Andric 2349cb14a3feSDimitry Andrictemplate <class _Key, 2350cb14a3feSDimitry Andric class _Tp, 2351cb14a3feSDimitry Andric class _Hash, 2352cb14a3feSDimitry Andric class _Allocator, 2353349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 2354349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 2355349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 2356cb14a3feSDimitry Andricunordered_multimap( 2357cb14a3feSDimitry Andric initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 2358cb14a3feSDimitry Andric -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>; 23590b57cec5SDimitry Andric#endif 23600b57cec5SDimitry Andric 23610b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 23620b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 23630b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql) 2364cb14a3feSDimitry Andric : __table_(__hf, __eql) { 2365753f127fSDimitry Andric __table_.__rehash_multi(__n); 23660b57cec5SDimitry Andric} 23670b57cec5SDimitry Andric 23680b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 23690b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2370cb14a3feSDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 2371cb14a3feSDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 2372cb14a3feSDimitry Andric __table_.__rehash_multi(__n); 2373cb14a3feSDimitry Andric} 2374cb14a3feSDimitry Andric 2375cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2376cb14a3feSDimitry Andrictemplate <class _InputIterator> 2377cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) { 2378cb14a3feSDimitry Andric insert(__first, __last); 2379cb14a3feSDimitry Andric} 2380cb14a3feSDimitry Andric 2381cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2382cb14a3feSDimitry Andrictemplate <class _InputIterator> 2383cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2384cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 2385cb14a3feSDimitry Andric : __table_(__hf, __eql) { 2386cb14a3feSDimitry Andric __table_.__rehash_multi(__n); 2387cb14a3feSDimitry Andric insert(__first, __last); 2388cb14a3feSDimitry Andric} 2389cb14a3feSDimitry Andric 2390cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2391cb14a3feSDimitry Andrictemplate <class _InputIterator> 2392cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2393cb14a3feSDimitry Andric _InputIterator __first, 2394cb14a3feSDimitry Andric _InputIterator __last, 2395cb14a3feSDimitry Andric size_type __n, 2396cb14a3feSDimitry Andric const hasher& __hf, 2397cb14a3feSDimitry Andric const key_equal& __eql, 23980b57cec5SDimitry Andric const allocator_type& __a) 2399cb14a3feSDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 2400753f127fSDimitry Andric __table_.__rehash_multi(__n); 24010b57cec5SDimitry Andric insert(__first, __last); 24020b57cec5SDimitry Andric} 24030b57cec5SDimitry Andric 24040b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2405cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a) 2406cb14a3feSDimitry Andric : __table_(typename __table::allocator_type(__a)) {} 24070b57cec5SDimitry Andric 24080b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2409cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u) 2410cb14a3feSDimitry Andric : __table_(__u.__table_) { 2411753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 24120b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 24130b57cec5SDimitry Andric} 24140b57cec5SDimitry Andric 24150b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 24160b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 24170b57cec5SDimitry Andric const unordered_multimap& __u, const allocator_type& __a) 2418cb14a3feSDimitry Andric : __table_(__u.__table_, typename __table::allocator_type(__a)) { 2419753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 24200b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 24210b57cec5SDimitry Andric} 24220b57cec5SDimitry Andric 24230b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 24240b57cec5SDimitry Andric 24250b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2426cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(unordered_multimap&& __u) 24270b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 2428cb14a3feSDimitry Andric : __table_(std::move(__u.__table_)) {} 24290b57cec5SDimitry Andric 24300b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 24310b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 24320b57cec5SDimitry Andric unordered_multimap&& __u, const allocator_type& __a) 2433cb14a3feSDimitry Andric : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) { 2434cb14a3feSDimitry Andric if (__a != __u.get_allocator()) { 24350b57cec5SDimitry Andric iterator __i = __u.begin(); 2436cb14a3feSDimitry Andric while (__u.size() != 0) { 2437cb14a3feSDimitry Andric __table_.__insert_multi(__u.__table_.remove((__i++).__i_)->__get_value().__move()); 24380b57cec5SDimitry Andric } 24390b57cec5SDimitry Andric } 24400b57cec5SDimitry Andric} 24410b57cec5SDimitry Andric 24420b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2443cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) { 24440b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 24450b57cec5SDimitry Andric} 24460b57cec5SDimitry Andric 24470b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 24480b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2449cb14a3feSDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 2450cb14a3feSDimitry Andric : __table_(__hf, __eql) { 2451753f127fSDimitry Andric __table_.__rehash_multi(__n); 24520b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 24530b57cec5SDimitry Andric} 24540b57cec5SDimitry Andric 24550b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 24560b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 2457cb14a3feSDimitry Andric initializer_list<value_type> __il, 2458cb14a3feSDimitry Andric size_type __n, 2459cb14a3feSDimitry Andric const hasher& __hf, 2460cb14a3feSDimitry Andric const key_equal& __eql, 2461cb14a3feSDimitry Andric const allocator_type& __a) 2462cb14a3feSDimitry Andric : __table_(__hf, __eql, typename __table::allocator_type(__a)) { 2463753f127fSDimitry Andric __table_.__rehash_multi(__n); 24640b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 24650b57cec5SDimitry Andric} 24660b57cec5SDimitry Andric 24670b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2468cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 24690b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 2470cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 24715f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 24720b57cec5SDimitry Andric return *this; 24730b57cec5SDimitry Andric} 24740b57cec5SDimitry Andric 24750b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2476cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 2477cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 24780b57cec5SDimitry Andric __table_.__assign_multi(__il.begin(), __il.end()); 24790b57cec5SDimitry Andric return *this; 24800b57cec5SDimitry Andric} 24810b57cec5SDimitry Andric 24820b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 24830b57cec5SDimitry Andric 24840b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 24850b57cec5SDimitry Andrictemplate <class _InputIterator> 2486cb14a3feSDimitry Andricinline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 24870b57cec5SDimitry Andric for (; __first != __last; ++__first) 24880b57cec5SDimitry Andric __table_.__insert_multi(*__first); 24890b57cec5SDimitry Andric} 24900b57cec5SDimitry Andric 24910b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2492cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 2493cb14a3feSDimitry Andricswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2494cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 24950b57cec5SDimitry Andric __x.swap(__y); 24960b57cec5SDimitry Andric} 24970b57cec5SDimitry Andric 249806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 2499cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate> 2500cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type 2501cb14a3feSDimitry Andricerase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 25025f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 25035ffd83dbSDimitry Andric} 25040b57cec5SDimitry Andric#endif 25050b57cec5SDimitry Andric 25060b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2507cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2508cb14a3feSDimitry Andric const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 25090b57cec5SDimitry Andric if (__x.size() != __y.size()) 25100b57cec5SDimitry Andric return false; 2511cb14a3feSDimitry Andric typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 25120b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _EqRng; 2513cb14a3feSDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 25140b57cec5SDimitry Andric _EqRng __xeq = __x.equal_range(__i->first); 25150b57cec5SDimitry Andric _EqRng __yeq = __y.equal_range(__i->first); 2516cb14a3feSDimitry Andric if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 25175f757f3fSDimitry Andric !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 25180b57cec5SDimitry Andric return false; 25190b57cec5SDimitry Andric __i = __xeq.second; 25200b57cec5SDimitry Andric } 25210b57cec5SDimitry Andric return true; 25220b57cec5SDimitry Andric} 25230b57cec5SDimitry Andric 252406c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 252506c3fb27SDimitry Andric 25260b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2527cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2528cb14a3feSDimitry Andric const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 25290b57cec5SDimitry Andric return !(__x == __y); 25300b57cec5SDimitry Andric} 25310b57cec5SDimitry Andric 253206c3fb27SDimitry Andric#endif 253306c3fb27SDimitry Andric 25340b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 25350b57cec5SDimitry Andric 253606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 2537bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 2538bdd1243dSDimitry Andricnamespace pmr { 2539bdd1243dSDimitry Andrictemplate <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 254006c3fb27SDimitry Andricusing unordered_map _LIBCPP_AVAILABILITY_PMR = 2541bdd1243dSDimitry Andric std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; 2542bdd1243dSDimitry Andric 2543bdd1243dSDimitry Andrictemplate <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 254406c3fb27SDimitry Andricusing unordered_multimap _LIBCPP_AVAILABILITY_PMR = 2545bdd1243dSDimitry Andric std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; 2546bdd1243dSDimitry Andric} // namespace pmr 2547bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD 2548bdd1243dSDimitry Andric#endif 2549bdd1243dSDimitry Andric 2550*b3edf446SDimitry Andric_LIBCPP_POP_MACROS 2551*b3edf446SDimitry Andric 2552bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 2553bdd1243dSDimitry Andric# include <algorithm> 2554bdd1243dSDimitry Andric# include <bit> 2555bdd1243dSDimitry Andric# include <concepts> 255606c3fb27SDimitry Andric# include <cstdlib> 2557bdd1243dSDimitry Andric# include <iterator> 255806c3fb27SDimitry Andric# include <type_traits> 2559bdd1243dSDimitry Andric#endif 2560bdd1243dSDimitry Andric 25610b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_MAP 2562