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_SET 110b57cec5SDimitry Andric#define _LIBCPP_UNORDERED_SET 120b57cec5SDimitry Andric 13*5f757f3fSDimitry Andric// clang-format off 14*5f757f3fSDimitry Andric 150b57cec5SDimitry Andric/* 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric unordered_set synopsis 180b57cec5SDimitry Andric 190b57cec5SDimitry Andric#include <initializer_list> 200b57cec5SDimitry Andric 210b57cec5SDimitry Andricnamespace std 220b57cec5SDimitry Andric{ 230b57cec5SDimitry Andric 240b57cec5SDimitry Andrictemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 250b57cec5SDimitry Andric class Alloc = allocator<Value>> 260b57cec5SDimitry Andricclass unordered_set 270b57cec5SDimitry Andric{ 280b57cec5SDimitry Andricpublic: 290b57cec5SDimitry Andric // types 300b57cec5SDimitry Andric typedef Value key_type; 310b57cec5SDimitry Andric typedef key_type value_type; 320b57cec5SDimitry Andric typedef Hash hasher; 330b57cec5SDimitry Andric typedef Pred key_equal; 340b57cec5SDimitry Andric typedef Alloc allocator_type; 350b57cec5SDimitry Andric typedef value_type& reference; 360b57cec5SDimitry Andric typedef const value_type& const_reference; 370b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::pointer pointer; 380b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 390b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::size_type size_type; 400b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::difference_type difference_type; 410b57cec5SDimitry Andric 420b57cec5SDimitry Andric typedef /unspecified/ iterator; 430b57cec5SDimitry Andric typedef /unspecified/ const_iterator; 440b57cec5SDimitry Andric typedef /unspecified/ local_iterator; 450b57cec5SDimitry Andric typedef /unspecified/ const_local_iterator; 460b57cec5SDimitry Andric 470b57cec5SDimitry Andric typedef unspecified node_type unspecified; // C++17 480b57cec5SDimitry Andric typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 490b57cec5SDimitry Andric 500b57cec5SDimitry Andric unordered_set() 510b57cec5SDimitry Andric noexcept( 520b57cec5SDimitry Andric is_nothrow_default_constructible<hasher>::value && 530b57cec5SDimitry Andric is_nothrow_default_constructible<key_equal>::value && 540b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value); 550b57cec5SDimitry Andric explicit unordered_set(size_type n, const hasher& hf = hasher(), 560b57cec5SDimitry Andric const key_equal& eql = key_equal(), 570b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 580b57cec5SDimitry Andric template <class InputIterator> 590b57cec5SDimitry Andric unordered_set(InputIterator f, InputIterator l, 600b57cec5SDimitry Andric size_type n = 0, const hasher& hf = hasher(), 610b57cec5SDimitry Andric const key_equal& eql = key_equal(), 620b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 6306c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 6406c3fb27SDimitry Andric unordered_set(from_range_t, R&& rg, size_type n = see below, 6506c3fb27SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 6606c3fb27SDimitry Andric const allocator_type& a = allocator_type()); // C++23 670b57cec5SDimitry Andric explicit unordered_set(const allocator_type&); 680b57cec5SDimitry Andric unordered_set(const unordered_set&); 690b57cec5SDimitry Andric unordered_set(const unordered_set&, const Allocator&); 700b57cec5SDimitry Andric unordered_set(unordered_set&&) 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_set(unordered_set&&, const Allocator&); 760b57cec5SDimitry Andric unordered_set(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_set(size_type n, const allocator_type& a); // C++14 800b57cec5SDimitry Andric unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 810b57cec5SDimitry Andric template <class InputIterator> 820b57cec5SDimitry Andric unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 830b57cec5SDimitry Andric template <class InputIterator> 840b57cec5SDimitry Andric unordered_set(InputIterator f, InputIterator l, size_type n, 850b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 8606c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 8706c3fb27SDimitry Andric unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a) 8806c3fb27SDimitry Andric : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 8906c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 9006c3fb27SDimitry Andric unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 9106c3fb27SDimitry Andric : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 920b57cec5SDimitry Andric unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 930b57cec5SDimitry Andric unordered_set(initializer_list<value_type> il, size_type n, 940b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 950b57cec5SDimitry Andric ~unordered_set(); 960b57cec5SDimitry Andric unordered_set& operator=(const unordered_set&); 970b57cec5SDimitry Andric unordered_set& operator=(unordered_set&&) 980b57cec5SDimitry Andric noexcept( 990b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 1000b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 1010b57cec5SDimitry Andric is_nothrow_move_assignable<hasher>::value && 1020b57cec5SDimitry Andric is_nothrow_move_assignable<key_equal>::value); 1030b57cec5SDimitry Andric unordered_set& operator=(initializer_list<value_type>); 1040b57cec5SDimitry Andric 1050b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 1060b57cec5SDimitry Andric 1070b57cec5SDimitry Andric bool empty() const noexcept; 1080b57cec5SDimitry Andric size_type size() const noexcept; 1090b57cec5SDimitry Andric size_type max_size() const noexcept; 1100b57cec5SDimitry Andric 1110b57cec5SDimitry Andric iterator begin() noexcept; 1120b57cec5SDimitry Andric iterator end() noexcept; 1130b57cec5SDimitry Andric const_iterator begin() const noexcept; 1140b57cec5SDimitry Andric const_iterator end() const noexcept; 1150b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 1160b57cec5SDimitry Andric const_iterator cend() const noexcept; 1170b57cec5SDimitry Andric 1180b57cec5SDimitry Andric template <class... Args> 1190b57cec5SDimitry Andric pair<iterator, bool> emplace(Args&&... args); 1200b57cec5SDimitry Andric template <class... Args> 1210b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 1220b57cec5SDimitry Andric pair<iterator, bool> insert(const value_type& obj); 1230b57cec5SDimitry Andric pair<iterator, bool> insert(value_type&& obj); 1240b57cec5SDimitry Andric iterator insert(const_iterator hint, const value_type& obj); 1250b57cec5SDimitry Andric iterator insert(const_iterator hint, value_type&& obj); 1260b57cec5SDimitry Andric template <class InputIterator> 1270b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 12806c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 12906c3fb27SDimitry Andric void insert_range(R&& rg); // C++23 1300b57cec5SDimitry Andric void insert(initializer_list<value_type>); 1310b57cec5SDimitry Andric 1320b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 1330b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 1340b57cec5SDimitry Andric insert_return_type insert(node_type&& nh); // C++17 1350b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 1360b57cec5SDimitry Andric 1370b57cec5SDimitry Andric iterator erase(const_iterator position); 1380b57cec5SDimitry Andric iterator erase(iterator position); // C++14 1390b57cec5SDimitry Andric size_type erase(const key_type& k); 1400b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 1410b57cec5SDimitry Andric void clear() noexcept; 1420b57cec5SDimitry Andric 1430b57cec5SDimitry Andric template<class H2, class P2> 1440b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 1450b57cec5SDimitry Andric template<class H2, class P2> 1460b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 1470b57cec5SDimitry Andric template<class H2, class P2> 1480b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 1490b57cec5SDimitry Andric template<class H2, class P2> 1500b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 1510b57cec5SDimitry Andric 1520b57cec5SDimitry Andric void swap(unordered_set&) 1530b57cec5SDimitry Andric noexcept(allocator_traits<Allocator>::is_always_equal::value && 1540b57cec5SDimitry Andric noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 1550b57cec5SDimitry Andric noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 1560b57cec5SDimitry Andric 1570b57cec5SDimitry Andric hasher hash_function() const; 1580b57cec5SDimitry Andric key_equal key_eq() const; 1590b57cec5SDimitry Andric 1600b57cec5SDimitry Andric iterator find(const key_type& k); 1610b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 162e8d8bef9SDimitry Andric template<typename K> 163e8d8bef9SDimitry Andric iterator find(const K& x); // C++20 164e8d8bef9SDimitry Andric template<typename K> 165e8d8bef9SDimitry Andric const_iterator find(const K& x) const; // C++20 1660b57cec5SDimitry Andric size_type count(const key_type& k) const; 167e8d8bef9SDimitry Andric template<typename K> 168e8d8bef9SDimitry Andric size_type count(const K& k) const; // C++20 1690b57cec5SDimitry Andric bool contains(const key_type& k) const; // C++20 170e8d8bef9SDimitry Andric template<typename K> 171e8d8bef9SDimitry Andric bool contains(const K& k) const; // C++20 1720b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& k); 1730b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 174e8d8bef9SDimitry Andric template<typename K> 175e8d8bef9SDimitry Andric pair<iterator, iterator> equal_range(const K& k); // C++20 176e8d8bef9SDimitry Andric template<typename K> 177e8d8bef9SDimitry Andric pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 1780b57cec5SDimitry Andric 1790b57cec5SDimitry Andric size_type bucket_count() const noexcept; 1800b57cec5SDimitry Andric size_type max_bucket_count() const noexcept; 1810b57cec5SDimitry Andric 1820b57cec5SDimitry Andric size_type bucket_size(size_type n) const; 1830b57cec5SDimitry Andric size_type bucket(const key_type& k) const; 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andric local_iterator begin(size_type n); 1860b57cec5SDimitry Andric local_iterator end(size_type n); 1870b57cec5SDimitry Andric const_local_iterator begin(size_type n) const; 1880b57cec5SDimitry Andric const_local_iterator end(size_type n) const; 1890b57cec5SDimitry Andric const_local_iterator cbegin(size_type n) const; 1900b57cec5SDimitry Andric const_local_iterator cend(size_type n) const; 1910b57cec5SDimitry Andric 1920b57cec5SDimitry Andric float load_factor() const noexcept; 1930b57cec5SDimitry Andric float max_load_factor() const noexcept; 1940b57cec5SDimitry Andric void max_load_factor(float z); 1950b57cec5SDimitry Andric void rehash(size_type n); 1960b57cec5SDimitry Andric void reserve(size_type n); 1970b57cec5SDimitry Andric}; 1980b57cec5SDimitry Andric 199349cc55cSDimitry Andrictemplate<class InputIterator, 200349cc55cSDimitry Andric class Hash = hash<typename iterator_traits<InputIterator>::value_type>, 201349cc55cSDimitry Andric class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>, 202349cc55cSDimitry Andric class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 203349cc55cSDimitry Andricunordered_set(InputIterator, InputIterator, typename see below::size_type = see below, 204349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 205349cc55cSDimitry Andric -> unordered_set<typename iterator_traits<InputIterator>::value_type, 206349cc55cSDimitry Andric Hash, Pred, Allocator>; // C++17 207349cc55cSDimitry Andric 20806c3fb27SDimitry Andrictemplate<ranges::input_range R, 20906c3fb27SDimitry Andric class Hash = hash<ranges::range_value_t<R>>, 21006c3fb27SDimitry Andric class Pred = equal_to<ranges::range_value_t<R>>, 21106c3fb27SDimitry Andric class Allocator = allocator<ranges::range_value_t<R>>> 21206c3fb27SDimitry Andric unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 21306c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23 21406c3fb27SDimitry Andric 215349cc55cSDimitry Andrictemplate<class T, class Hash = hash<T>, 216349cc55cSDimitry Andric class Pred = equal_to<T>, class Allocator = allocator<T>> 217349cc55cSDimitry Andricunordered_set(initializer_list<T>, typename see below::size_type = see below, 218349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 219349cc55cSDimitry Andric -> unordered_set<T, Hash, Pred, Allocator>; // C++17 220349cc55cSDimitry Andric 221349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 222349cc55cSDimitry Andricunordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator) 223349cc55cSDimitry Andric -> unordered_set<typename iterator_traits<InputIterator>::value_type, 224349cc55cSDimitry Andric hash<typename iterator_traits<InputIterator>::value_type>, 225349cc55cSDimitry Andric equal_to<typename iterator_traits<InputIterator>::value_type>, 226349cc55cSDimitry Andric Allocator>; // C++17 227349cc55cSDimitry Andric 228349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator> 229349cc55cSDimitry Andricunordered_set(InputIterator, InputIterator, typename see below::size_type, 230349cc55cSDimitry Andric Hash, Allocator) 231349cc55cSDimitry Andric -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash, 232349cc55cSDimitry Andric equal_to<typename iterator_traits<InputIterator>::value_type>, 233349cc55cSDimitry Andric Allocator>; // C++17 234349cc55cSDimitry Andric 23506c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 23606c3fb27SDimitry Andric unordered_set(from_range_t, R&&, typename see below::size_type, Allocator) 23706c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 23806c3fb27SDimitry Andric equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 23906c3fb27SDimitry Andric 24006c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 24106c3fb27SDimitry Andric unordered_set(from_range_t, R&&, Allocator) 24206c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 24306c3fb27SDimitry Andric equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 24406c3fb27SDimitry Andric 24506c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator> 24606c3fb27SDimitry Andric unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 24706c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<R>, Hash, 24806c3fb27SDimitry Andric equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 24906c3fb27SDimitry Andric 250349cc55cSDimitry Andrictemplate<class T, class Allocator> 251349cc55cSDimitry Andricunordered_set(initializer_list<T>, typename see below::size_type, Allocator) 252349cc55cSDimitry Andric -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17 253349cc55cSDimitry Andric 254349cc55cSDimitry Andrictemplate<class T, class Hash, class Allocator> 255349cc55cSDimitry Andricunordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator) 256349cc55cSDimitry Andric -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17 257349cc55cSDimitry Andric 2580b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 2590b57cec5SDimitry Andric void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 2600b57cec5SDimitry Andric unordered_set<Value, Hash, Pred, Alloc>& y) 2610b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 2620b57cec5SDimitry Andric 2630b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 2640b57cec5SDimitry Andric bool 2650b57cec5SDimitry Andric operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 2660b57cec5SDimitry Andric const unordered_set<Value, Hash, Pred, Alloc>& y); 2670b57cec5SDimitry Andric 2680b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 2690b57cec5SDimitry Andric bool 2700b57cec5SDimitry Andric operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 27106c3fb27SDimitry Andric const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20 2720b57cec5SDimitry Andric 2730b57cec5SDimitry Andrictemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 2740b57cec5SDimitry Andric class Alloc = allocator<Value>> 2750b57cec5SDimitry Andricclass unordered_multiset 2760b57cec5SDimitry Andric{ 2770b57cec5SDimitry Andricpublic: 2780b57cec5SDimitry Andric // types 2790b57cec5SDimitry Andric typedef Value key_type; 2800b57cec5SDimitry Andric typedef key_type value_type; 2810b57cec5SDimitry Andric typedef Hash hasher; 2820b57cec5SDimitry Andric typedef Pred key_equal; 2830b57cec5SDimitry Andric typedef Alloc allocator_type; 2840b57cec5SDimitry Andric typedef value_type& reference; 2850b57cec5SDimitry Andric typedef const value_type& const_reference; 2860b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::pointer pointer; 2870b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 2880b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::size_type size_type; 2890b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::difference_type difference_type; 2900b57cec5SDimitry Andric 2910b57cec5SDimitry Andric typedef /unspecified/ iterator; 2920b57cec5SDimitry Andric typedef /unspecified/ const_iterator; 2930b57cec5SDimitry Andric typedef /unspecified/ local_iterator; 2940b57cec5SDimitry Andric typedef /unspecified/ const_local_iterator; 2950b57cec5SDimitry Andric 2960b57cec5SDimitry Andric typedef unspecified node_type unspecified; // C++17 2970b57cec5SDimitry Andric 2980b57cec5SDimitry Andric unordered_multiset() 2990b57cec5SDimitry Andric noexcept( 3000b57cec5SDimitry Andric is_nothrow_default_constructible<hasher>::value && 3010b57cec5SDimitry Andric is_nothrow_default_constructible<key_equal>::value && 3020b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value); 3030b57cec5SDimitry Andric explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 3040b57cec5SDimitry Andric const key_equal& eql = key_equal(), 3050b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 3060b57cec5SDimitry Andric template <class InputIterator> 3070b57cec5SDimitry Andric unordered_multiset(InputIterator f, InputIterator l, 3080b57cec5SDimitry Andric size_type n = 0, const hasher& hf = hasher(), 3090b57cec5SDimitry Andric const key_equal& eql = key_equal(), 3100b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 31106c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 31206c3fb27SDimitry Andric unordered_multiset(from_range_t, R&& rg, size_type n = see below, 31306c3fb27SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 31406c3fb27SDimitry Andric const allocator_type& a = allocator_type()); // C++23 3150b57cec5SDimitry Andric explicit unordered_multiset(const allocator_type&); 3160b57cec5SDimitry Andric unordered_multiset(const unordered_multiset&); 3170b57cec5SDimitry Andric unordered_multiset(const unordered_multiset&, const Allocator&); 3180b57cec5SDimitry Andric unordered_multiset(unordered_multiset&&) 3190b57cec5SDimitry Andric noexcept( 3200b57cec5SDimitry Andric is_nothrow_move_constructible<hasher>::value && 3210b57cec5SDimitry Andric is_nothrow_move_constructible<key_equal>::value && 3220b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value); 3230b57cec5SDimitry Andric unordered_multiset(unordered_multiset&&, const Allocator&); 3240b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 3250b57cec5SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 3260b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 3270b57cec5SDimitry Andric unordered_multiset(size_type n, const allocator_type& a); // C++14 3280b57cec5SDimitry Andric unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 3290b57cec5SDimitry Andric template <class InputIterator> 3300b57cec5SDimitry Andric unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 3310b57cec5SDimitry Andric template <class InputIterator> 3320b57cec5SDimitry Andric unordered_multiset(InputIterator f, InputIterator l, size_type n, 3330b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 33406c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 33506c3fb27SDimitry Andric unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a) 33606c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23 33706c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 33806c3fb27SDimitry Andric unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a) 33906c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { } // C++23 3400b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 3410b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> il, size_type n, 3420b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 3430b57cec5SDimitry Andric ~unordered_multiset(); 3440b57cec5SDimitry Andric unordered_multiset& operator=(const unordered_multiset&); 3450b57cec5SDimitry Andric unordered_multiset& operator=(unordered_multiset&&) 3460b57cec5SDimitry Andric noexcept( 3470b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 3480b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 3490b57cec5SDimitry Andric is_nothrow_move_assignable<hasher>::value && 3500b57cec5SDimitry Andric is_nothrow_move_assignable<key_equal>::value); 3510b57cec5SDimitry Andric unordered_multiset& operator=(initializer_list<value_type>); 3520b57cec5SDimitry Andric 3530b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 3540b57cec5SDimitry Andric 3550b57cec5SDimitry Andric bool empty() const noexcept; 3560b57cec5SDimitry Andric size_type size() const noexcept; 3570b57cec5SDimitry Andric size_type max_size() const noexcept; 3580b57cec5SDimitry Andric 3590b57cec5SDimitry Andric iterator begin() noexcept; 3600b57cec5SDimitry Andric iterator end() noexcept; 3610b57cec5SDimitry Andric const_iterator begin() const noexcept; 3620b57cec5SDimitry Andric const_iterator end() const noexcept; 3630b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 3640b57cec5SDimitry Andric const_iterator cend() const noexcept; 3650b57cec5SDimitry Andric 3660b57cec5SDimitry Andric template <class... Args> 3670b57cec5SDimitry Andric iterator emplace(Args&&... args); 3680b57cec5SDimitry Andric template <class... Args> 3690b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 3700b57cec5SDimitry Andric iterator insert(const value_type& obj); 3710b57cec5SDimitry Andric iterator insert(value_type&& obj); 3720b57cec5SDimitry Andric iterator insert(const_iterator hint, const value_type& obj); 3730b57cec5SDimitry Andric iterator insert(const_iterator hint, value_type&& obj); 3740b57cec5SDimitry Andric template <class InputIterator> 3750b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 37606c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 37706c3fb27SDimitry Andric void insert_range(R&& rg); // C++23 3780b57cec5SDimitry Andric void insert(initializer_list<value_type>); 3790b57cec5SDimitry Andric 3800b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 3810b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 3820b57cec5SDimitry Andric iterator insert(node_type&& nh); // C++17 3830b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 3840b57cec5SDimitry Andric 3850b57cec5SDimitry Andric iterator erase(const_iterator position); 3860b57cec5SDimitry Andric iterator erase(iterator position); // C++14 3870b57cec5SDimitry Andric size_type erase(const key_type& k); 3880b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 3890b57cec5SDimitry Andric void clear() noexcept; 3900b57cec5SDimitry Andric 3910b57cec5SDimitry Andric template<class H2, class P2> 3920b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 3930b57cec5SDimitry Andric template<class H2, class P2> 3940b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 3950b57cec5SDimitry Andric template<class H2, class P2> 3960b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 3970b57cec5SDimitry Andric template<class H2, class P2> 3980b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 3990b57cec5SDimitry Andric 4000b57cec5SDimitry Andric void swap(unordered_multiset&) 4010b57cec5SDimitry Andric noexcept(allocator_traits<Allocator>::is_always_equal::value && 4020b57cec5SDimitry Andric noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 4030b57cec5SDimitry Andric noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 4040b57cec5SDimitry Andric 4050b57cec5SDimitry Andric hasher hash_function() const; 4060b57cec5SDimitry Andric key_equal key_eq() const; 4070b57cec5SDimitry Andric 4080b57cec5SDimitry Andric iterator find(const key_type& k); 4090b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 410e8d8bef9SDimitry Andric template<typename K> 411e8d8bef9SDimitry Andric iterator find(const K& x); // C++20 412e8d8bef9SDimitry Andric template<typename K> 413e8d8bef9SDimitry Andric const_iterator find(const K& x) const; // C++20 4140b57cec5SDimitry Andric size_type count(const key_type& k) const; 415e8d8bef9SDimitry Andric template<typename K> 416e8d8bef9SDimitry Andric size_type count(const K& k) const; // C++20 4170b57cec5SDimitry Andric bool contains(const key_type& k) const; // C++20 418e8d8bef9SDimitry Andric template<typename K> 419e8d8bef9SDimitry Andric bool contains(const K& k) const; // C++20 4200b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& k); 4210b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 422e8d8bef9SDimitry Andric template<typename K> 423e8d8bef9SDimitry Andric pair<iterator, iterator> equal_range(const K& k); // C++20 424e8d8bef9SDimitry Andric template<typename K> 425e8d8bef9SDimitry Andric pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 4260b57cec5SDimitry Andric 4270b57cec5SDimitry Andric size_type bucket_count() const noexcept; 4280b57cec5SDimitry Andric size_type max_bucket_count() const noexcept; 4290b57cec5SDimitry Andric 4300b57cec5SDimitry Andric size_type bucket_size(size_type n) const; 4310b57cec5SDimitry Andric size_type bucket(const key_type& k) const; 4320b57cec5SDimitry Andric 4330b57cec5SDimitry Andric local_iterator begin(size_type n); 4340b57cec5SDimitry Andric local_iterator end(size_type n); 4350b57cec5SDimitry Andric const_local_iterator begin(size_type n) const; 4360b57cec5SDimitry Andric const_local_iterator end(size_type n) const; 4370b57cec5SDimitry Andric const_local_iterator cbegin(size_type n) const; 4380b57cec5SDimitry Andric const_local_iterator cend(size_type n) const; 4390b57cec5SDimitry Andric 4400b57cec5SDimitry Andric float load_factor() const noexcept; 4410b57cec5SDimitry Andric float max_load_factor() const noexcept; 4420b57cec5SDimitry Andric void max_load_factor(float z); 4430b57cec5SDimitry Andric void rehash(size_type n); 4440b57cec5SDimitry Andric void reserve(size_type n); 4450b57cec5SDimitry Andric}; 4460b57cec5SDimitry Andric 447349cc55cSDimitry Andrictemplate<class InputIterator, 448349cc55cSDimitry Andric class Hash = hash<typename iterator_traits<InputIterator>::value_type>, 449349cc55cSDimitry Andric class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>, 450349cc55cSDimitry Andric class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 451349cc55cSDimitry Andricunordered_multiset(InputIterator, InputIterator, see below::size_type = see below, 452349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 453349cc55cSDimitry Andric -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, 454349cc55cSDimitry Andric Hash, Pred, Allocator>; // C++17 455349cc55cSDimitry Andric 45606c3fb27SDimitry Andrictemplate<ranges::input_range R, 45706c3fb27SDimitry Andric class Hash = hash<ranges::range_value_t<R>>, 45806c3fb27SDimitry Andric class Pred = equal_to<ranges::range_value_t<R>>, 45906c3fb27SDimitry Andric class Allocator = allocator<ranges::range_value_t<R>>> 46006c3fb27SDimitry Andric unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 46106c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23 46206c3fb27SDimitry Andric 463349cc55cSDimitry Andrictemplate<class T, class Hash = hash<T>, 464349cc55cSDimitry Andric class Pred = equal_to<T>, class Allocator = allocator<T>> 465349cc55cSDimitry Andricunordered_multiset(initializer_list<T>, typename see below::size_type = see below, 466349cc55cSDimitry Andric Hash = Hash(), Pred = Pred(), Allocator = Allocator()) 467349cc55cSDimitry Andric -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17 468349cc55cSDimitry Andric 469349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 470349cc55cSDimitry Andricunordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator) 471349cc55cSDimitry Andric -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, 472349cc55cSDimitry Andric hash<typename iterator_traits<InputIterator>::value_type>, 473349cc55cSDimitry Andric equal_to<typename iterator_traits<InputIterator>::value_type>, 474349cc55cSDimitry Andric Allocator>; // C++17 475349cc55cSDimitry Andric 476349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator> 477349cc55cSDimitry Andricunordered_multiset(InputIterator, InputIterator, typename see below::size_type, 478349cc55cSDimitry Andric Hash, Allocator) 479349cc55cSDimitry Andric -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash, 480349cc55cSDimitry Andric equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 481349cc55cSDimitry Andric 48206c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 48306c3fb27SDimitry Andric unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator) 48406c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 48506c3fb27SDimitry Andric equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 48606c3fb27SDimitry Andric 48706c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 48806c3fb27SDimitry Andric unordered_multiset(from_range_t, R&&, Allocator) 48906c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>, 49006c3fb27SDimitry Andric equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 49106c3fb27SDimitry Andric 49206c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator> 49306c3fb27SDimitry Andric unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator) 49406c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<R>, Hash, 49506c3fb27SDimitry Andric equal_to<ranges::range_value_t<R>>, Allocator>; // C++23 49606c3fb27SDimitry Andric 497349cc55cSDimitry Andrictemplate<class T, class Allocator> 498349cc55cSDimitry Andricunordered_multiset(initializer_list<T>, typename see below::size_type, Allocator) 499349cc55cSDimitry Andric -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17 500349cc55cSDimitry Andric 501349cc55cSDimitry Andrictemplate<class T, class Hash, class Allocator> 502349cc55cSDimitry Andricunordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator) 503349cc55cSDimitry Andric -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17 504349cc55cSDimitry Andric 5050b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 5060b57cec5SDimitry Andric void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 5070b57cec5SDimitry Andric unordered_multiset<Value, Hash, Pred, Alloc>& y) 5080b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate> 5115ffd83dbSDimitry Andric typename unordered_set<K, T, H, P, A>::size_type 5125ffd83dbSDimitry Andric erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20 5130b57cec5SDimitry Andric 5140b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate> 5155ffd83dbSDimitry Andric typename unordered_multiset<K, T, H, P, A>::size_type 5165ffd83dbSDimitry Andric erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20 5170b57cec5SDimitry Andric 5180b57cec5SDimitry Andric 5190b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 5200b57cec5SDimitry Andric bool 5210b57cec5SDimitry Andric operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 5220b57cec5SDimitry Andric const unordered_multiset<Value, Hash, Pred, Alloc>& y); 5230b57cec5SDimitry Andric 5240b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 5250b57cec5SDimitry Andric bool 5260b57cec5SDimitry Andric operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 52706c3fb27SDimitry Andric const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20 5280b57cec5SDimitry Andric} // std 5290b57cec5SDimitry Andric 5300b57cec5SDimitry Andric*/ 5310b57cec5SDimitry Andric 532*5f757f3fSDimitry Andric// clang-format on 533*5f757f3fSDimitry Andric 53481ad6265SDimitry Andric#include <__algorithm/is_permutation.h> 53581ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler 53606c3fb27SDimitry Andric#include <__availability> 5370b57cec5SDimitry Andric#include <__config> 538fe6060f1SDimitry Andric#include <__functional/is_transparent.h> 53981ad6265SDimitry Andric#include <__functional/operations.h> 5400b57cec5SDimitry Andric#include <__hash_table> 54181ad6265SDimitry Andric#include <__iterator/distance.h> 54281ad6265SDimitry Andric#include <__iterator/erase_if_container.h> 54381ad6265SDimitry Andric#include <__iterator/iterator_traits.h> 54406c3fb27SDimitry Andric#include <__iterator/ranges_iterator_traits.h> 54504eeddc0SDimitry Andric#include <__memory/addressof.h> 546bdd1243dSDimitry Andric#include <__memory/allocator.h> 547bdd1243dSDimitry Andric#include <__memory_resource/polymorphic_allocator.h> 5480b57cec5SDimitry Andric#include <__node_handle> 54906c3fb27SDimitry Andric#include <__ranges/concepts.h> 55006c3fb27SDimitry Andric#include <__ranges/container_compatible_range.h> 55106c3fb27SDimitry Andric#include <__ranges/from_range.h> 552bdd1243dSDimitry Andric#include <__type_traits/is_allocator.h> 553fe6060f1SDimitry Andric#include <__utility/forward.h> 5540b57cec5SDimitry Andric#include <version> 5550b57cec5SDimitry Andric 55681ad6265SDimitry Andric// standard-mandated includes 55781ad6265SDimitry Andric 55881ad6265SDimitry Andric// [iterator.range] 55981ad6265SDimitry Andric#include <__iterator/access.h> 56081ad6265SDimitry Andric#include <__iterator/data.h> 56181ad6265SDimitry Andric#include <__iterator/empty.h> 56281ad6265SDimitry Andric#include <__iterator/reverse_access.h> 56381ad6265SDimitry Andric#include <__iterator/size.h> 56481ad6265SDimitry Andric 56581ad6265SDimitry Andric// [unord.set.syn] 56681ad6265SDimitry Andric#include <compare> 56781ad6265SDimitry Andric#include <initializer_list> 56881ad6265SDimitry Andric 5690b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 5700b57cec5SDimitry Andric# pragma GCC system_header 5710b57cec5SDimitry Andric#endif 5720b57cec5SDimitry Andric 5730b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 5740b57cec5SDimitry Andric 5750b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 5760b57cec5SDimitry Andricclass unordered_multiset; 5770b57cec5SDimitry Andric 5780b57cec5SDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 5790b57cec5SDimitry Andric class _Alloc = allocator<_Value> > 5800b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_set 5810b57cec5SDimitry Andric{ 5820b57cec5SDimitry Andricpublic: 5830b57cec5SDimitry Andric // types 5840b57cec5SDimitry Andric typedef _Value key_type; 5850b57cec5SDimitry Andric typedef key_type value_type; 58681ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 58781ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 58881ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 5890b57cec5SDimitry Andric typedef value_type& reference; 5900b57cec5SDimitry Andric typedef const value_type& const_reference; 5910b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 59206c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 5930b57cec5SDimitry Andric 594bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value, 595bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 596bdd1243dSDimitry Andric "original allocator"); 597bdd1243dSDimitry Andric 5980b57cec5SDimitry Andric private: 5990b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 6000b57cec5SDimitry Andric 6010b57cec5SDimitry Andric __table __table_; 6020b57cec5SDimitry Andric 6030b57cec5SDimitry Andricpublic: 6040b57cec5SDimitry Andric typedef typename __table::pointer pointer; 6050b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 6060b57cec5SDimitry Andric typedef typename __table::size_type size_type; 6070b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 6080b57cec5SDimitry Andric 6090b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 6100b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 6110b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 6120b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 6130b57cec5SDimitry Andric 61406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 6150b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 6160b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 6170b57cec5SDimitry Andric#endif 6180b57cec5SDimitry Andric 6190b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 6200b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 6210b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 6220b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 6230b57cec5SDimitry Andric 624*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 6250b57cec5SDimitry Andric unordered_set() 6260b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 6270b57cec5SDimitry Andric { 6280b57cec5SDimitry Andric } 62906c3fb27SDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf = hasher(), 6300b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 63106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 632*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 6330b57cec5SDimitry Andric unordered_set(size_type __n, const allocator_type& __a) 6340b57cec5SDimitry Andric : unordered_set(__n, hasher(), key_equal(), __a) {} 635*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 6360b57cec5SDimitry Andric unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 6370b57cec5SDimitry Andric : unordered_set(__n, __hf, key_equal(), __a) {} 6380b57cec5SDimitry Andric#endif 63906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 6400b57cec5SDimitry Andric const allocator_type& __a); 6410b57cec5SDimitry Andric template <class _InputIterator> 64206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last); 6430b57cec5SDimitry Andric template <class _InputIterator> 64406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last, 6450b57cec5SDimitry Andric size_type __n, const hasher& __hf = hasher(), 6460b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 6470b57cec5SDimitry Andric template <class _InputIterator> 64806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last, 6490b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, 6500b57cec5SDimitry Andric const allocator_type& __a); 65106c3fb27SDimitry Andric 65206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 65306c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 65406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 65506c3fb27SDimitry Andric unordered_set(from_range_t, _Range&& __range, size_type __n = /*implementation-defined*/0, 65606c3fb27SDimitry Andric const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), 65706c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 65806c3fb27SDimitry Andric : __table_(__hf, __eql, __a) { 65906c3fb27SDimitry Andric if (__n > 0) { 66006c3fb27SDimitry Andric __table_.__rehash_unique(__n); 66106c3fb27SDimitry Andric } 66206c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 66306c3fb27SDimitry Andric } 66406c3fb27SDimitry Andric#endif 66506c3fb27SDimitry Andric 66606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 6670b57cec5SDimitry Andric template <class _InputIterator> 668*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 6690b57cec5SDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, 6700b57cec5SDimitry Andric size_type __n, const allocator_type& __a) 6710b57cec5SDimitry Andric : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 6720b57cec5SDimitry Andric template <class _InputIterator> 67306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last, 6740b57cec5SDimitry Andric size_type __n, const hasher& __hf, const allocator_type& __a) 6750b57cec5SDimitry Andric : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 6760b57cec5SDimitry Andric#endif 67706c3fb27SDimitry Andric 67806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 67906c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 68006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 68106c3fb27SDimitry Andric unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 68206c3fb27SDimitry Andric : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 68306c3fb27SDimitry Andric 68406c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 68506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 68606c3fb27SDimitry Andric unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 68706c3fb27SDimitry Andric : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 68806c3fb27SDimitry Andric#endif 68906c3fb27SDimitry Andric 690*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 6910b57cec5SDimitry Andric explicit unordered_set(const allocator_type& __a); 69206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u); 69306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a); 6940b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 695*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 6960b57cec5SDimitry Andric unordered_set(unordered_set&& __u) 6970b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 69806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a); 69906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il); 70006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il, size_type __n, 7010b57cec5SDimitry Andric const hasher& __hf = hasher(), 7020b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 70306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il, size_type __n, 7040b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, 7050b57cec5SDimitry Andric const allocator_type& __a); 70606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 707*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 7080b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, 7090b57cec5SDimitry Andric const allocator_type& __a) 7100b57cec5SDimitry Andric : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 711*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 7120b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, 7130b57cec5SDimitry Andric const hasher& __hf, const allocator_type& __a) 7140b57cec5SDimitry Andric : unordered_set(__il, __n, __hf, key_equal(), __a) {} 7150b57cec5SDimitry Andric#endif 7160b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 717*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7180b57cec5SDimitry Andric ~unordered_set() { 719bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 7200b57cec5SDimitry Andric } 7210b57cec5SDimitry Andric 722*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7230b57cec5SDimitry Andric unordered_set& operator=(const unordered_set& __u) 7240b57cec5SDimitry Andric { 7250b57cec5SDimitry Andric __table_ = __u.__table_; 7260b57cec5SDimitry Andric return *this; 7270b57cec5SDimitry Andric } 7280b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 729*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7300b57cec5SDimitry Andric unordered_set& operator=(unordered_set&& __u) 7310b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 732*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7330b57cec5SDimitry Andric unordered_set& operator=(initializer_list<value_type> __il); 7340b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7350b57cec5SDimitry Andric 736*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7370b57cec5SDimitry Andric allocator_type get_allocator() const _NOEXCEPT 7380b57cec5SDimitry Andric {return allocator_type(__table_.__node_alloc());} 7390b57cec5SDimitry Andric 740*5f757f3fSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI 7410b57cec5SDimitry Andric bool empty() const _NOEXCEPT {return __table_.size() == 0;} 742*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7430b57cec5SDimitry Andric size_type size() const _NOEXCEPT {return __table_.size();} 744*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7450b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT {return __table_.max_size();} 7460b57cec5SDimitry Andric 747*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7480b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return __table_.begin();} 749*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7500b57cec5SDimitry Andric iterator end() _NOEXCEPT {return __table_.end();} 751*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7520b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return __table_.begin();} 753*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7540b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return __table_.end();} 755*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7560b57cec5SDimitry Andric const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 757*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7580b57cec5SDimitry Andric const_iterator cend() const _NOEXCEPT {return __table_.end();} 7590b57cec5SDimitry Andric 7600b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 7610b57cec5SDimitry Andric template <class... _Args> 762*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7630b57cec5SDimitry Andric pair<iterator, bool> emplace(_Args&&... __args) 764*5f757f3fSDimitry Andric {return __table_.__emplace_unique(std::forward<_Args>(__args)...);} 7650b57cec5SDimitry Andric template <class... _Args> 766*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 76706c3fb27SDimitry Andric iterator emplace_hint(const_iterator, _Args&&... __args) { 76881ad6265SDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 7690b57cec5SDimitry Andric } 7700b57cec5SDimitry Andric 771*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7720b57cec5SDimitry Andric pair<iterator, bool> insert(value_type&& __x) 773*5f757f3fSDimitry Andric {return __table_.__insert_unique(std::move(__x));} 774*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 77506c3fb27SDimitry Andric iterator insert(const_iterator, value_type&& __x) { 77681ad6265SDimitry Andric return insert(std::move(__x)).first; 7770b57cec5SDimitry Andric } 77881ad6265SDimitry Andric 779*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7800b57cec5SDimitry Andric void insert(initializer_list<value_type> __il) 7810b57cec5SDimitry Andric {insert(__il.begin(), __il.end());} 7820b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 783*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7840b57cec5SDimitry Andric pair<iterator, bool> insert(const value_type& __x) 7850b57cec5SDimitry Andric {return __table_.__insert_unique(__x);} 7860b57cec5SDimitry Andric 787*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 78806c3fb27SDimitry Andric iterator insert(const_iterator, const value_type& __x) { 7890b57cec5SDimitry Andric return insert(__x).first; 7900b57cec5SDimitry Andric } 7910b57cec5SDimitry Andric template <class _InputIterator> 792*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 7930b57cec5SDimitry Andric void insert(_InputIterator __first, _InputIterator __last); 7940b57cec5SDimitry Andric 79506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 79606c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 79706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 79806c3fb27SDimitry Andric void insert_range(_Range&& __range) { 79906c3fb27SDimitry Andric for (auto&& __element : __range) { 80006c3fb27SDimitry Andric __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 80106c3fb27SDimitry Andric } 80206c3fb27SDimitry Andric } 80306c3fb27SDimitry Andric#endif 80406c3fb27SDimitry Andric 805*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8060b57cec5SDimitry Andric iterator erase(const_iterator __p) {return __table_.erase(__p);} 807*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8080b57cec5SDimitry Andric size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 809*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8100b57cec5SDimitry Andric iterator erase(const_iterator __first, const_iterator __last) 8110b57cec5SDimitry Andric {return __table_.erase(__first, __last);} 812*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8130b57cec5SDimitry Andric void clear() _NOEXCEPT {__table_.clear();} 8140b57cec5SDimitry Andric 81506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 816*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8170b57cec5SDimitry Andric insert_return_type insert(node_type&& __nh) 8180b57cec5SDimitry Andric { 81906c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 8200b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 8210b57cec5SDimitry Andric return __table_.template __node_handle_insert_unique< 822*5f757f3fSDimitry Andric node_type, insert_return_type>(std::move(__nh)); 8230b57cec5SDimitry Andric } 824*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8250b57cec5SDimitry Andric iterator insert(const_iterator __h, node_type&& __nh) 8260b57cec5SDimitry Andric { 82706c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 8280b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 8290b57cec5SDimitry Andric return __table_.template __node_handle_insert_unique<node_type>( 830*5f757f3fSDimitry Andric __h, std::move(__nh)); 8310b57cec5SDimitry Andric } 832*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8330b57cec5SDimitry Andric node_type extract(key_type const& __key) 8340b57cec5SDimitry Andric { 8350b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 8360b57cec5SDimitry Andric } 837*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8380b57cec5SDimitry Andric node_type extract(const_iterator __it) 8390b57cec5SDimitry Andric { 8400b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__it); 8410b57cec5SDimitry Andric } 8420b57cec5SDimitry Andric 8430b57cec5SDimitry Andric template<class _H2, class _P2> 844*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8450b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 8460b57cec5SDimitry Andric { 84706c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 8480b57cec5SDimitry Andric "merging container with incompatible allocator"); 8490b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8500b57cec5SDimitry Andric } 8510b57cec5SDimitry Andric template<class _H2, class _P2> 852*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8530b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) 8540b57cec5SDimitry Andric { 85506c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 8560b57cec5SDimitry Andric "merging container with incompatible allocator"); 8570b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8580b57cec5SDimitry Andric } 8590b57cec5SDimitry Andric template<class _H2, class _P2> 860*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8610b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 8620b57cec5SDimitry Andric { 86306c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 8640b57cec5SDimitry Andric "merging container with incompatible allocator"); 8650b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8660b57cec5SDimitry Andric } 8670b57cec5SDimitry Andric template<class _H2, class _P2> 868*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8690b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 8700b57cec5SDimitry Andric { 87106c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 8720b57cec5SDimitry Andric "merging container with incompatible allocator"); 8730b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8740b57cec5SDimitry Andric } 8750b57cec5SDimitry Andric#endif 8760b57cec5SDimitry Andric 877*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8780b57cec5SDimitry Andric void swap(unordered_set& __u) 8790b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 8800b57cec5SDimitry Andric {__table_.swap(__u.__table_);} 8810b57cec5SDimitry Andric 882*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8830b57cec5SDimitry Andric hasher hash_function() const {return __table_.hash_function();} 884*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8850b57cec5SDimitry Andric key_equal key_eq() const {return __table_.key_eq();} 8860b57cec5SDimitry Andric 887*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8880b57cec5SDimitry Andric iterator find(const key_type& __k) {return __table_.find(__k);} 889*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 8900b57cec5SDimitry Andric const_iterator find(const key_type& __k) const {return __table_.find(__k);} 89106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 892349cc55cSDimitry Andric template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 893*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 894349cc55cSDimitry Andric iterator find(const _K2& __k) {return __table_.find(__k);} 895349cc55cSDimitry Andric template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 896*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 897349cc55cSDimitry Andric const_iterator find(const _K2& __k) const {return __table_.find(__k);} 89806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 899349cc55cSDimitry Andric 900*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9010b57cec5SDimitry Andric size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 90206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 903349cc55cSDimitry Andric template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 904*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 905349cc55cSDimitry Andric size_type count(const _K2& __k) const {return __table_.__count_unique(__k);} 90606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 907349cc55cSDimitry Andric 90806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 909*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9100b57cec5SDimitry Andric bool contains(const key_type& __k) const {return find(__k) != end();} 911e8d8bef9SDimitry Andric 912349cc55cSDimitry Andric template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 913*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 914349cc55cSDimitry Andric bool contains(const _K2& __k) const {return find(__k) != end();} 91506c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 916349cc55cSDimitry Andric 917*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9180b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& __k) 9190b57cec5SDimitry Andric {return __table_.__equal_range_unique(__k);} 920*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9210b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 9220b57cec5SDimitry Andric {return __table_.__equal_range_unique(__k);} 92306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 924349cc55cSDimitry Andric template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 925*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 926349cc55cSDimitry Andric pair<iterator, iterator> equal_range(const _K2& __k) 927349cc55cSDimitry Andric {return __table_.__equal_range_unique(__k);} 928349cc55cSDimitry Andric template <class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 929*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 930349cc55cSDimitry Andric pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 931349cc55cSDimitry Andric {return __table_.__equal_range_unique(__k);} 93206c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 9330b57cec5SDimitry Andric 934*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9350b57cec5SDimitry Andric size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 936*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9370b57cec5SDimitry Andric size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 9380b57cec5SDimitry Andric 939*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9400b57cec5SDimitry Andric size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 941*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9420b57cec5SDimitry Andric size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 9430b57cec5SDimitry Andric 944*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9450b57cec5SDimitry Andric local_iterator begin(size_type __n) {return __table_.begin(__n);} 946*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9470b57cec5SDimitry Andric local_iterator end(size_type __n) {return __table_.end(__n);} 948*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9490b57cec5SDimitry Andric const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 950*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9510b57cec5SDimitry Andric const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 952*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9530b57cec5SDimitry Andric const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 954*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9550b57cec5SDimitry Andric const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 9560b57cec5SDimitry Andric 957*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9580b57cec5SDimitry Andric float load_factor() const _NOEXCEPT {return __table_.load_factor();} 959*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9600b57cec5SDimitry Andric float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 961*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 9620b57cec5SDimitry Andric void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 963*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 964753f127fSDimitry Andric void rehash(size_type __n) {__table_.__rehash_unique(__n);} 965*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 966753f127fSDimitry Andric void reserve(size_type __n) {__table_.__reserve_unique(__n);} 9670b57cec5SDimitry Andric}; 9680b57cec5SDimitry Andric 969349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 9700b57cec5SDimitry Andrictemplate<class _InputIterator, 9710b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 9720b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 9730b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 97406c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 975349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 976349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 977349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 978349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 9790b57cec5SDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 9800b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 9810b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 9820b57cec5SDimitry Andric 98306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 98406c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 98506c3fb27SDimitry Andric class _Hash = hash<ranges::range_value_t<_Range>>, 98606c3fb27SDimitry Andric class _Pred = equal_to<ranges::range_value_t<_Range>>, 98706c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 98806c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 98906c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 99006c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 99106c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 99206c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type = 0, 99306c3fb27SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 99406c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 99506c3fb27SDimitry Andric#endif 99606c3fb27SDimitry Andric 9970b57cec5SDimitry Andrictemplate<class _Tp, class _Hash = hash<_Tp>, 9980b57cec5SDimitry Andric class _Pred = equal_to<_Tp>, 9990b57cec5SDimitry Andric class _Allocator = allocator<_Tp>, 1000349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1001349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1002349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1003349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10040b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, 10050b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 10060b57cec5SDimitry Andric -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 10070b57cec5SDimitry Andric 10080b57cec5SDimitry Andrictemplate<class _InputIterator, class _Allocator, 100906c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1010349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10110b57cec5SDimitry Andricunordered_set(_InputIterator, _InputIterator, 10120b57cec5SDimitry Andric typename allocator_traits<_Allocator>::size_type, _Allocator) 10130b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, 10140b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 10150b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 10160b57cec5SDimitry Andric _Allocator>; 10170b57cec5SDimitry Andric 10180b57cec5SDimitry Andrictemplate<class _InputIterator, class _Hash, class _Allocator, 101906c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1020349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1021349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1022349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10230b57cec5SDimitry Andricunordered_set(_InputIterator, _InputIterator, 10240b57cec5SDimitry Andric typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 10250b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, _Hash, 10260b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 10270b57cec5SDimitry Andric _Allocator>; 10280b57cec5SDimitry Andric 102906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 103006c3fb27SDimitry Andric 103106c3fb27SDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, 103206c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 103306c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 103406c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, hash<ranges::range_value_t<_Range>>, 103506c3fb27SDimitry Andric equal_to<ranges::range_value_t<_Range>>, _Allocator>; 103606c3fb27SDimitry Andric 103706c3fb27SDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, 103806c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 103906c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, _Allocator) 104006c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, hash<ranges::range_value_t<_Range>>, 104106c3fb27SDimitry Andric equal_to<ranges::range_value_t<_Range>>, _Allocator>; 104206c3fb27SDimitry Andric 104306c3fb27SDimitry Andrictemplate <ranges::input_range _Range, class _Hash, class _Allocator, 104406c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 104506c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 104606c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 104706c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 104806c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 104906c3fb27SDimitry Andric 105006c3fb27SDimitry Andric#endif 105106c3fb27SDimitry Andric 10520b57cec5SDimitry Andrictemplate<class _Tp, class _Allocator, 1053349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10540b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 10550b57cec5SDimitry Andric -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 10560b57cec5SDimitry Andric 10570b57cec5SDimitry Andrictemplate<class _Tp, class _Hash, class _Allocator, 1058349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1059349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1060349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10610b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 10620b57cec5SDimitry Andric -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 10630b57cec5SDimitry Andric#endif 10640b57cec5SDimitry Andric 10650b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10660b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 10670b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql) 10680b57cec5SDimitry Andric : __table_(__hf, __eql) 10690b57cec5SDimitry Andric{ 1070753f127fSDimitry Andric __table_.__rehash_unique(__n); 10710b57cec5SDimitry Andric} 10720b57cec5SDimitry Andric 10730b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10740b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 10750b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 10760b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 10770b57cec5SDimitry Andric{ 1078753f127fSDimitry Andric __table_.__rehash_unique(__n); 10790b57cec5SDimitry Andric} 10800b57cec5SDimitry Andric 10810b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10820b57cec5SDimitry Andrictemplate <class _InputIterator> 10830b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 10840b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last) 10850b57cec5SDimitry Andric{ 10860b57cec5SDimitry Andric insert(__first, __last); 10870b57cec5SDimitry Andric} 10880b57cec5SDimitry Andric 10890b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10900b57cec5SDimitry Andrictemplate <class _InputIterator> 10910b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 10920b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 10930b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql) 10940b57cec5SDimitry Andric : __table_(__hf, __eql) 10950b57cec5SDimitry Andric{ 1096753f127fSDimitry Andric __table_.__rehash_unique(__n); 10970b57cec5SDimitry Andric insert(__first, __last); 10980b57cec5SDimitry Andric} 10990b57cec5SDimitry Andric 11000b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11010b57cec5SDimitry Andrictemplate <class _InputIterator> 11020b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11030b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 11040b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 11050b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 11060b57cec5SDimitry Andric{ 1107753f127fSDimitry Andric __table_.__rehash_unique(__n); 11080b57cec5SDimitry Andric insert(__first, __last); 11090b57cec5SDimitry Andric} 11100b57cec5SDimitry Andric 11110b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11120b57cec5SDimitry Andricinline 11130b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11140b57cec5SDimitry Andric const allocator_type& __a) 11150b57cec5SDimitry Andric : __table_(__a) 11160b57cec5SDimitry Andric{ 11170b57cec5SDimitry Andric} 11180b57cec5SDimitry Andric 11190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11200b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11210b57cec5SDimitry Andric const unordered_set& __u) 11220b57cec5SDimitry Andric : __table_(__u.__table_) 11230b57cec5SDimitry Andric{ 1124753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 11250b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 11260b57cec5SDimitry Andric} 11270b57cec5SDimitry Andric 11280b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11290b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11300b57cec5SDimitry Andric const unordered_set& __u, const allocator_type& __a) 11310b57cec5SDimitry Andric : __table_(__u.__table_, __a) 11320b57cec5SDimitry Andric{ 1133753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 11340b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 11350b57cec5SDimitry Andric} 11360b57cec5SDimitry Andric 11370b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 11380b57cec5SDimitry Andric 11390b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11400b57cec5SDimitry Andricinline 11410b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11420b57cec5SDimitry Andric unordered_set&& __u) 11430b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1144*5f757f3fSDimitry Andric : __table_(std::move(__u.__table_)) 11450b57cec5SDimitry Andric{ 11460b57cec5SDimitry Andric} 11470b57cec5SDimitry Andric 11480b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11490b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11500b57cec5SDimitry Andric unordered_set&& __u, const allocator_type& __a) 1151*5f757f3fSDimitry Andric : __table_(std::move(__u.__table_), __a) 11520b57cec5SDimitry Andric{ 11530b57cec5SDimitry Andric if (__a != __u.get_allocator()) 11540b57cec5SDimitry Andric { 11550b57cec5SDimitry Andric iterator __i = __u.begin(); 11560b57cec5SDimitry Andric while (__u.size() != 0) 1157*5f757f3fSDimitry Andric __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value())); 11580b57cec5SDimitry Andric } 11590b57cec5SDimitry Andric} 11600b57cec5SDimitry Andric 11610b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11620b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11630b57cec5SDimitry Andric initializer_list<value_type> __il) 11640b57cec5SDimitry Andric{ 11650b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11660b57cec5SDimitry Andric} 11670b57cec5SDimitry Andric 11680b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11690b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11700b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 11710b57cec5SDimitry Andric const key_equal& __eql) 11720b57cec5SDimitry Andric : __table_(__hf, __eql) 11730b57cec5SDimitry Andric{ 1174753f127fSDimitry Andric __table_.__rehash_unique(__n); 11750b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11760b57cec5SDimitry Andric} 11770b57cec5SDimitry Andric 11780b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11790b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 11800b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 11810b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a) 11820b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 11830b57cec5SDimitry Andric{ 1184753f127fSDimitry Andric __table_.__rehash_unique(__n); 11850b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11860b57cec5SDimitry Andric} 11870b57cec5SDimitry Andric 11880b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11890b57cec5SDimitry Andricinline 11900b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>& 11910b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 11920b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 11930b57cec5SDimitry Andric{ 1194*5f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 11950b57cec5SDimitry Andric return *this; 11960b57cec5SDimitry Andric} 11970b57cec5SDimitry Andric 11980b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11990b57cec5SDimitry Andricinline 12000b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>& 12010b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 12020b57cec5SDimitry Andric initializer_list<value_type> __il) 12030b57cec5SDimitry Andric{ 12040b57cec5SDimitry Andric __table_.__assign_unique(__il.begin(), __il.end()); 12050b57cec5SDimitry Andric return *this; 12060b57cec5SDimitry Andric} 12070b57cec5SDimitry Andric 12080b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12090b57cec5SDimitry Andric 12100b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 12110b57cec5SDimitry Andrictemplate <class _InputIterator> 12120b57cec5SDimitry Andricinline 12130b57cec5SDimitry Andricvoid 12140b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 12150b57cec5SDimitry Andric _InputIterator __last) 12160b57cec5SDimitry Andric{ 12170b57cec5SDimitry Andric for (; __first != __last; ++__first) 12180b57cec5SDimitry Andric __table_.__insert_unique(*__first); 12190b57cec5SDimitry Andric} 12200b57cec5SDimitry Andric 12210b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1222*5f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI 12230b57cec5SDimitry Andricvoid 12240b57cec5SDimitry Andricswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 12250b57cec5SDimitry Andric unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 12260b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 12270b57cec5SDimitry Andric{ 12280b57cec5SDimitry Andric __x.swap(__y); 12290b57cec5SDimitry Andric} 12300b57cec5SDimitry Andric 123106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 12325ffd83dbSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, 12335ffd83dbSDimitry Andric class _Predicate> 1234*5f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI 12355ffd83dbSDimitry Andric typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 12365ffd83dbSDimitry Andric erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, 12375ffd83dbSDimitry Andric _Predicate __pred) { 1238*5f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 12395ffd83dbSDimitry Andric} 12400b57cec5SDimitry Andric#endif 12410b57cec5SDimitry Andric 12420b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1243bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool 12440b57cec5SDimitry Andricoperator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 12450b57cec5SDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 12460b57cec5SDimitry Andric{ 12470b57cec5SDimitry Andric if (__x.size() != __y.size()) 12480b57cec5SDimitry Andric return false; 12490b57cec5SDimitry Andric typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 12500b57cec5SDimitry Andric const_iterator; 12510b57cec5SDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 12520b57cec5SDimitry Andric __i != __ex; ++__i) 12530b57cec5SDimitry Andric { 12540b57cec5SDimitry Andric const_iterator __j = __y.find(*__i); 12550b57cec5SDimitry Andric if (__j == __ey || !(*__i == *__j)) 12560b57cec5SDimitry Andric return false; 12570b57cec5SDimitry Andric } 12580b57cec5SDimitry Andric return true; 12590b57cec5SDimitry Andric} 12600b57cec5SDimitry Andric 126106c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 126206c3fb27SDimitry Andric 12630b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1264*5f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI 12650b57cec5SDimitry Andricbool 12660b57cec5SDimitry Andricoperator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 12670b57cec5SDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 12680b57cec5SDimitry Andric{ 12690b57cec5SDimitry Andric return !(__x == __y); 12700b57cec5SDimitry Andric} 12710b57cec5SDimitry Andric 127206c3fb27SDimitry Andric#endif 127306c3fb27SDimitry Andric 12740b57cec5SDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 12750b57cec5SDimitry Andric class _Alloc = allocator<_Value> > 12760b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multiset 12770b57cec5SDimitry Andric{ 12780b57cec5SDimitry Andricpublic: 12790b57cec5SDimitry Andric // types 12800b57cec5SDimitry Andric typedef _Value key_type; 12810b57cec5SDimitry Andric typedef key_type value_type; 128281ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 128381ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 128481ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 12850b57cec5SDimitry Andric typedef value_type& reference; 12860b57cec5SDimitry Andric typedef const value_type& const_reference; 12870b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 128806c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 12890b57cec5SDimitry Andric 12900b57cec5SDimitry Andricprivate: 12910b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 12920b57cec5SDimitry Andric 12930b57cec5SDimitry Andric __table __table_; 12940b57cec5SDimitry Andric 12950b57cec5SDimitry Andricpublic: 12960b57cec5SDimitry Andric typedef typename __table::pointer pointer; 12970b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 12980b57cec5SDimitry Andric typedef typename __table::size_type size_type; 12990b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 13000b57cec5SDimitry Andric 13010b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 13020b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 13030b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 13040b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 13050b57cec5SDimitry Andric 130606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 13070b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 13080b57cec5SDimitry Andric#endif 13090b57cec5SDimitry Andric 13100b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 13110b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 13120b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 13130b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 13140b57cec5SDimitry Andric 1315*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 13160b57cec5SDimitry Andric unordered_multiset() 13170b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 13180b57cec5SDimitry Andric { 13190b57cec5SDimitry Andric } 132006c3fb27SDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf = hasher(), 13210b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 132206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, 13230b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a); 132406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 1325*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13260b57cec5SDimitry Andric unordered_multiset(size_type __n, const allocator_type& __a) 13270b57cec5SDimitry Andric : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1328*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13290b57cec5SDimitry Andric unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 13300b57cec5SDimitry Andric : unordered_multiset(__n, __hf, key_equal(), __a) {} 13310b57cec5SDimitry Andric#endif 13320b57cec5SDimitry Andric template <class _InputIterator> 133306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last); 13340b57cec5SDimitry Andric template <class _InputIterator> 133506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last, 13360b57cec5SDimitry Andric size_type __n, const hasher& __hf = hasher(), 13370b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 13380b57cec5SDimitry Andric template <class _InputIterator> 133906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last, 13400b57cec5SDimitry Andric size_type __n , const hasher& __hf, 13410b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a); 134206c3fb27SDimitry Andric 134306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 134406c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 134506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 134606c3fb27SDimitry Andric unordered_multiset(from_range_t, _Range&& __range, size_type __n = /*implementation-defined*/0, 134706c3fb27SDimitry Andric const hasher& __hf = hasher(), const key_equal& __eql = key_equal(), 134806c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 134906c3fb27SDimitry Andric : __table_(__hf, __eql, __a) { 135006c3fb27SDimitry Andric if (__n > 0) { 135106c3fb27SDimitry Andric __table_.__rehash_multi(__n); 135206c3fb27SDimitry Andric } 135306c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 135406c3fb27SDimitry Andric } 135506c3fb27SDimitry Andric#endif 135606c3fb27SDimitry Andric 135706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 13580b57cec5SDimitry Andric template <class _InputIterator> 1359*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13600b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, 13610b57cec5SDimitry Andric size_type __n, const allocator_type& __a) 13620b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 13630b57cec5SDimitry Andric template <class _InputIterator> 1364*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13650b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, 13660b57cec5SDimitry Andric size_type __n, const hasher& __hf, const allocator_type& __a) 13670b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 13680b57cec5SDimitry Andric#endif 136906c3fb27SDimitry Andric 137006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 137106c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 137206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 137306c3fb27SDimitry Andric unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 137406c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 137506c3fb27SDimitry Andric 137606c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 137706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 137806c3fb27SDimitry Andric unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 137906c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 138006c3fb27SDimitry Andric#endif 138106c3fb27SDimitry Andric 1382*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 13830b57cec5SDimitry Andric explicit unordered_multiset(const allocator_type& __a); 138406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); 138506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 13860b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1387*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 13880b57cec5SDimitry Andric unordered_multiset(unordered_multiset&& __u) 13890b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 139006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 139106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il); 139206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il, size_type __n, 13930b57cec5SDimitry Andric const hasher& __hf = hasher(), 13940b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 139506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il, size_type __n, 13960b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, 13970b57cec5SDimitry Andric const allocator_type& __a); 139806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 1399*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 14000b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 14010b57cec5SDimitry Andric : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 1402*5f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 14030b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 14040b57cec5SDimitry Andric : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 14050b57cec5SDimitry Andric#endif 14060b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 1407*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14080b57cec5SDimitry Andric ~unordered_multiset() { 1409bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 14100b57cec5SDimitry Andric } 14110b57cec5SDimitry Andric 1412*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14130b57cec5SDimitry Andric unordered_multiset& operator=(const unordered_multiset& __u) 14140b57cec5SDimitry Andric { 14150b57cec5SDimitry Andric __table_ = __u.__table_; 14160b57cec5SDimitry Andric return *this; 14170b57cec5SDimitry Andric } 14180b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1419*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14200b57cec5SDimitry Andric unordered_multiset& operator=(unordered_multiset&& __u) 14210b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 142206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il); 14230b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 14240b57cec5SDimitry Andric 1425*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14260b57cec5SDimitry Andric allocator_type get_allocator() const _NOEXCEPT 14270b57cec5SDimitry Andric {return allocator_type(__table_.__node_alloc());} 14280b57cec5SDimitry Andric 1429*5f757f3fSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI 14300b57cec5SDimitry Andric bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1431*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14320b57cec5SDimitry Andric size_type size() const _NOEXCEPT {return __table_.size();} 1433*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14340b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT {return __table_.max_size();} 14350b57cec5SDimitry Andric 1436*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14370b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return __table_.begin();} 1438*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14390b57cec5SDimitry Andric iterator end() _NOEXCEPT {return __table_.end();} 1440*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14410b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1442*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14430b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return __table_.end();} 1444*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14450b57cec5SDimitry Andric const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1446*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14470b57cec5SDimitry Andric const_iterator cend() const _NOEXCEPT {return __table_.end();} 14480b57cec5SDimitry Andric 14490b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 14500b57cec5SDimitry Andric template <class... _Args> 1451*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14520b57cec5SDimitry Andric iterator emplace(_Args&&... __args) 1453*5f757f3fSDimitry Andric {return __table_.__emplace_multi(std::forward<_Args>(__args)...);} 14540b57cec5SDimitry Andric template <class... _Args> 1455*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14560b57cec5SDimitry Andric iterator emplace_hint(const_iterator __p, _Args&&... __args) 1457*5f757f3fSDimitry Andric {return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);} 14580b57cec5SDimitry Andric 1459*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1460*5f757f3fSDimitry Andric iterator insert(value_type&& __x) {return __table_.__insert_multi(std::move(__x));} 1461*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14620b57cec5SDimitry Andric iterator insert(const_iterator __p, value_type&& __x) 1463*5f757f3fSDimitry Andric {return __table_.__insert_multi(__p, std::move(__x));} 1464*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14650b57cec5SDimitry Andric void insert(initializer_list<value_type> __il) 14660b57cec5SDimitry Andric {insert(__il.begin(), __il.end());} 14670b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 14680b57cec5SDimitry Andric 1469*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14700b57cec5SDimitry Andric iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 14710b57cec5SDimitry Andric 1472*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14730b57cec5SDimitry Andric iterator insert(const_iterator __p, const value_type& __x) 14740b57cec5SDimitry Andric {return __table_.__insert_multi(__p, __x);} 14750b57cec5SDimitry Andric 14760b57cec5SDimitry Andric template <class _InputIterator> 1477*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14780b57cec5SDimitry Andric void insert(_InputIterator __first, _InputIterator __last); 14790b57cec5SDimitry Andric 148006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 148106c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 148206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 148306c3fb27SDimitry Andric void insert_range(_Range&& __range) { 148406c3fb27SDimitry Andric for (auto&& __element : __range) { 148506c3fb27SDimitry Andric __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 148606c3fb27SDimitry Andric } 148706c3fb27SDimitry Andric } 148806c3fb27SDimitry Andric#endif 148906c3fb27SDimitry Andric 149006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1491*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 14920b57cec5SDimitry Andric iterator insert(node_type&& __nh) 14930b57cec5SDimitry Andric { 149406c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 14950b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 14960b57cec5SDimitry Andric return __table_.template __node_handle_insert_multi<node_type>( 1497*5f757f3fSDimitry Andric std::move(__nh)); 14980b57cec5SDimitry Andric } 1499*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15000b57cec5SDimitry Andric iterator insert(const_iterator __hint, node_type&& __nh) 15010b57cec5SDimitry Andric { 150206c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 15030b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 15040b57cec5SDimitry Andric return __table_.template __node_handle_insert_multi<node_type>( 1505*5f757f3fSDimitry Andric __hint, std::move(__nh)); 15060b57cec5SDimitry Andric } 1507*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15080b57cec5SDimitry Andric node_type extract(const_iterator __position) 15090b57cec5SDimitry Andric { 15100b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>( 15110b57cec5SDimitry Andric __position); 15120b57cec5SDimitry Andric } 1513*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15140b57cec5SDimitry Andric node_type extract(key_type const& __key) 15150b57cec5SDimitry Andric { 15160b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 15170b57cec5SDimitry Andric } 15180b57cec5SDimitry Andric 15190b57cec5SDimitry Andric template <class _H2, class _P2> 1520*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15210b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 15220b57cec5SDimitry Andric { 152306c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 15240b57cec5SDimitry Andric "merging container with incompatible allocator"); 15250b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 15260b57cec5SDimitry Andric } 15270b57cec5SDimitry Andric template <class _H2, class _P2> 1528*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15290b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 15300b57cec5SDimitry Andric { 153106c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 15320b57cec5SDimitry Andric "merging container with incompatible allocator"); 15330b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 15340b57cec5SDimitry Andric } 15350b57cec5SDimitry Andric template <class _H2, class _P2> 1536*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15370b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 15380b57cec5SDimitry Andric { 153906c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 15400b57cec5SDimitry Andric "merging container with incompatible allocator"); 15410b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 15420b57cec5SDimitry Andric } 15430b57cec5SDimitry Andric template <class _H2, class _P2> 1544*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15450b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) 15460b57cec5SDimitry Andric { 154706c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), 15480b57cec5SDimitry Andric "merging container with incompatible allocator"); 15490b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 15500b57cec5SDimitry Andric } 15510b57cec5SDimitry Andric#endif 15520b57cec5SDimitry Andric 1553*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15540b57cec5SDimitry Andric iterator erase(const_iterator __p) {return __table_.erase(__p);} 1555*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15560b57cec5SDimitry Andric size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1557*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15580b57cec5SDimitry Andric iterator erase(const_iterator __first, const_iterator __last) 15590b57cec5SDimitry Andric {return __table_.erase(__first, __last);} 1560*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15610b57cec5SDimitry Andric void clear() _NOEXCEPT {__table_.clear();} 15620b57cec5SDimitry Andric 1563*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15640b57cec5SDimitry Andric void swap(unordered_multiset& __u) 15650b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 15660b57cec5SDimitry Andric {__table_.swap(__u.__table_);} 15670b57cec5SDimitry Andric 1568*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15690b57cec5SDimitry Andric hasher hash_function() const {return __table_.hash_function();} 1570*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15710b57cec5SDimitry Andric key_equal key_eq() const {return __table_.key_eq();} 15720b57cec5SDimitry Andric 1573*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15740b57cec5SDimitry Andric iterator find(const key_type& __k) {return __table_.find(__k);} 1575*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15760b57cec5SDimitry Andric const_iterator find(const key_type& __k) const {return __table_.find(__k);} 157706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1578349cc55cSDimitry Andric template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1579*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1580349cc55cSDimitry Andric iterator find(const _K2& __k) {return __table_.find(__k);} 1581349cc55cSDimitry Andric template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1582*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1583349cc55cSDimitry Andric const_iterator find(const _K2& __k) const {return __table_.find(__k);} 158406c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1585349cc55cSDimitry Andric 1586*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15870b57cec5SDimitry Andric size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 158806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1589349cc55cSDimitry Andric template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1590*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1591349cc55cSDimitry Andric size_type count(const _K2& __k) const {return __table_.__count_multi(__k);} 159206c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1593349cc55cSDimitry Andric 159406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1595*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 15960b57cec5SDimitry Andric bool contains(const key_type& __k) const {return find(__k) != end();} 1597e8d8bef9SDimitry Andric 1598349cc55cSDimitry Andric template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1599*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1600349cc55cSDimitry Andric bool contains(const _K2& __k) const {return find(__k) != end();} 160106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1602349cc55cSDimitry Andric 1603*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16040b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& __k) 16050b57cec5SDimitry Andric {return __table_.__equal_range_multi(__k);} 1606*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16070b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 16080b57cec5SDimitry Andric {return __table_.__equal_range_multi(__k);} 160906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1610349cc55cSDimitry Andric template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1611*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1612349cc55cSDimitry Andric pair<iterator, iterator> equal_range(const _K2& __k) 1613349cc55cSDimitry Andric {return __table_.__equal_range_multi(__k);} 1614349cc55cSDimitry Andric template<class _K2, enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1615*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1616349cc55cSDimitry Andric pair<const_iterator, const_iterator> equal_range(const _K2& __k) const 1617349cc55cSDimitry Andric {return __table_.__equal_range_multi(__k);} 161806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 16190b57cec5SDimitry Andric 1620*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16210b57cec5SDimitry Andric size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1622*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16230b57cec5SDimitry Andric size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 16240b57cec5SDimitry Andric 1625*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16260b57cec5SDimitry Andric size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 1627*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16280b57cec5SDimitry Andric size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 16290b57cec5SDimitry Andric 1630*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16310b57cec5SDimitry Andric local_iterator begin(size_type __n) {return __table_.begin(__n);} 1632*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16330b57cec5SDimitry Andric local_iterator end(size_type __n) {return __table_.end(__n);} 1634*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16350b57cec5SDimitry Andric const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1636*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16370b57cec5SDimitry Andric const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1638*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16390b57cec5SDimitry Andric const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1640*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16410b57cec5SDimitry Andric const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 16420b57cec5SDimitry Andric 1643*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16440b57cec5SDimitry Andric float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1645*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16460b57cec5SDimitry Andric float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1647*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 16480b57cec5SDimitry Andric void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1649*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1650753f127fSDimitry Andric void rehash(size_type __n) {__table_.__rehash_multi(__n);} 1651*5f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1652753f127fSDimitry Andric void reserve(size_type __n) {__table_.__reserve_multi(__n);} 16530b57cec5SDimitry Andric}; 16540b57cec5SDimitry Andric 1655349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 16560b57cec5SDimitry Andrictemplate<class _InputIterator, 16570b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 16580b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 16590b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 166006c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1661349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1662349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1663349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1664349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 16650b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 16660b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 16670b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 16680b57cec5SDimitry Andric 166906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 167006c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 167106c3fb27SDimitry Andric class _Hash = hash<ranges::range_value_t<_Range>>, 167206c3fb27SDimitry Andric class _Pred = equal_to<ranges::range_value_t<_Range>>, 167306c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 167406c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 167506c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 167606c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 167706c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 167806c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type = 0, 167906c3fb27SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 168006c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 168106c3fb27SDimitry Andric#endif 168206c3fb27SDimitry Andric 16830b57cec5SDimitry Andrictemplate<class _Tp, class _Hash = hash<_Tp>, 16840b57cec5SDimitry Andric class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>, 1685349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1686349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1687349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1688349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 16890b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, 16900b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 16910b57cec5SDimitry Andric -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 16920b57cec5SDimitry Andric 16930b57cec5SDimitry Andrictemplate<class _InputIterator, class _Allocator, 169406c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1695349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 16960b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 16970b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, 16980b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 16990b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 17000b57cec5SDimitry Andric _Allocator>; 17010b57cec5SDimitry Andric 17020b57cec5SDimitry Andrictemplate<class _InputIterator, class _Hash, class _Allocator, 170306c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1704349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1705349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1706349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 17070b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, 17080b57cec5SDimitry Andric _Hash, _Allocator) 17090b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, 17100b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 17110b57cec5SDimitry Andric _Allocator>; 17120b57cec5SDimitry Andric 171306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 171406c3fb27SDimitry Andric 171506c3fb27SDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, 171606c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 171706c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 171806c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, hash<ranges::range_value_t<_Range>>, 171906c3fb27SDimitry Andric equal_to<ranges::range_value_t<_Range>>, _Allocator>; 172006c3fb27SDimitry Andric 172106c3fb27SDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, 172206c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 172306c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, _Allocator) 172406c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, hash<ranges::range_value_t<_Range>>, 172506c3fb27SDimitry Andric equal_to<ranges::range_value_t<_Range>>, _Allocator>; 172606c3fb27SDimitry Andric 172706c3fb27SDimitry Andrictemplate <ranges::input_range _Range, class _Hash, class _Allocator, 172806c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 172906c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 173006c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 173106c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 173206c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 173306c3fb27SDimitry Andric 173406c3fb27SDimitry Andric#endif 173506c3fb27SDimitry Andric 17360b57cec5SDimitry Andrictemplate<class _Tp, class _Allocator, 1737349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 17380b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 17390b57cec5SDimitry Andric -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 17400b57cec5SDimitry Andric 17410b57cec5SDimitry Andrictemplate<class _Tp, class _Hash, class _Allocator, 1742349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1743349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1744349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 17450b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 17460b57cec5SDimitry Andric -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 17470b57cec5SDimitry Andric#endif 17480b57cec5SDimitry Andric 17490b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17500b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17510b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql) 17520b57cec5SDimitry Andric : __table_(__hf, __eql) 17530b57cec5SDimitry Andric{ 1754753f127fSDimitry Andric __table_.__rehash_multi(__n); 17550b57cec5SDimitry Andric} 17560b57cec5SDimitry Andric 17570b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17580b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17590b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, 17600b57cec5SDimitry Andric const allocator_type& __a) 17610b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 17620b57cec5SDimitry Andric{ 1763753f127fSDimitry Andric __table_.__rehash_multi(__n); 17640b57cec5SDimitry Andric} 17650b57cec5SDimitry Andric 17660b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17670b57cec5SDimitry Andrictemplate <class _InputIterator> 17680b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17690b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last) 17700b57cec5SDimitry Andric{ 17710b57cec5SDimitry Andric insert(__first, __last); 17720b57cec5SDimitry Andric} 17730b57cec5SDimitry Andric 17740b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17750b57cec5SDimitry Andrictemplate <class _InputIterator> 17760b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17770b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 17780b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql) 17790b57cec5SDimitry Andric : __table_(__hf, __eql) 17800b57cec5SDimitry Andric{ 1781753f127fSDimitry Andric __table_.__rehash_multi(__n); 17820b57cec5SDimitry Andric insert(__first, __last); 17830b57cec5SDimitry Andric} 17840b57cec5SDimitry Andric 17850b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17860b57cec5SDimitry Andrictemplate <class _InputIterator> 17870b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17880b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 17890b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 17900b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 17910b57cec5SDimitry Andric{ 1792753f127fSDimitry Andric __table_.__rehash_multi(__n); 17930b57cec5SDimitry Andric insert(__first, __last); 17940b57cec5SDimitry Andric} 17950b57cec5SDimitry Andric 17960b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17970b57cec5SDimitry Andricinline 17980b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17990b57cec5SDimitry Andric const allocator_type& __a) 18000b57cec5SDimitry Andric : __table_(__a) 18010b57cec5SDimitry Andric{ 18020b57cec5SDimitry Andric} 18030b57cec5SDimitry Andric 18040b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18050b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18060b57cec5SDimitry Andric const unordered_multiset& __u) 18070b57cec5SDimitry Andric : __table_(__u.__table_) 18080b57cec5SDimitry Andric{ 1809753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 18100b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 18110b57cec5SDimitry Andric} 18120b57cec5SDimitry Andric 18130b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18140b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18150b57cec5SDimitry Andric const unordered_multiset& __u, const allocator_type& __a) 18160b57cec5SDimitry Andric : __table_(__u.__table_, __a) 18170b57cec5SDimitry Andric{ 1818753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 18190b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 18200b57cec5SDimitry Andric} 18210b57cec5SDimitry Andric 18220b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 18230b57cec5SDimitry Andric 18240b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18250b57cec5SDimitry Andricinline 18260b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18270b57cec5SDimitry Andric unordered_multiset&& __u) 18280b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1829*5f757f3fSDimitry Andric : __table_(std::move(__u.__table_)) 18300b57cec5SDimitry Andric{ 18310b57cec5SDimitry Andric} 18320b57cec5SDimitry Andric 18330b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18340b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18350b57cec5SDimitry Andric unordered_multiset&& __u, const allocator_type& __a) 1836*5f757f3fSDimitry Andric : __table_(std::move(__u.__table_), __a) 18370b57cec5SDimitry Andric{ 18380b57cec5SDimitry Andric if (__a != __u.get_allocator()) 18390b57cec5SDimitry Andric { 18400b57cec5SDimitry Andric iterator __i = __u.begin(); 18410b57cec5SDimitry Andric while (__u.size() != 0) 1842*5f757f3fSDimitry Andric __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value())); 18430b57cec5SDimitry Andric } 18440b57cec5SDimitry Andric} 18450b57cec5SDimitry Andric 18460b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18470b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18480b57cec5SDimitry Andric initializer_list<value_type> __il) 18490b57cec5SDimitry Andric{ 18500b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 18510b57cec5SDimitry Andric} 18520b57cec5SDimitry Andric 18530b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18540b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18550b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 18560b57cec5SDimitry Andric const key_equal& __eql) 18570b57cec5SDimitry Andric : __table_(__hf, __eql) 18580b57cec5SDimitry Andric{ 1859753f127fSDimitry Andric __table_.__rehash_multi(__n); 18600b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 18610b57cec5SDimitry Andric} 18620b57cec5SDimitry Andric 18630b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18640b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 18650b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 18660b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a) 18670b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 18680b57cec5SDimitry Andric{ 1869753f127fSDimitry Andric __table_.__rehash_multi(__n); 18700b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 18710b57cec5SDimitry Andric} 18720b57cec5SDimitry Andric 18730b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18740b57cec5SDimitry Andricinline 18750b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 18760b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 18770b57cec5SDimitry Andric unordered_multiset&& __u) 18780b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 18790b57cec5SDimitry Andric{ 1880*5f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 18810b57cec5SDimitry Andric return *this; 18820b57cec5SDimitry Andric} 18830b57cec5SDimitry Andric 18840b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18850b57cec5SDimitry Andricinline 18860b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 18870b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 18880b57cec5SDimitry Andric initializer_list<value_type> __il) 18890b57cec5SDimitry Andric{ 18900b57cec5SDimitry Andric __table_.__assign_multi(__il.begin(), __il.end()); 18910b57cec5SDimitry Andric return *this; 18920b57cec5SDimitry Andric} 18930b57cec5SDimitry Andric 18940b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 18950b57cec5SDimitry Andric 18960b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 18970b57cec5SDimitry Andrictemplate <class _InputIterator> 18980b57cec5SDimitry Andricinline 18990b57cec5SDimitry Andricvoid 19000b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 19010b57cec5SDimitry Andric _InputIterator __last) 19020b57cec5SDimitry Andric{ 19030b57cec5SDimitry Andric for (; __first != __last; ++__first) 19040b57cec5SDimitry Andric __table_.__insert_multi(*__first); 19050b57cec5SDimitry Andric} 19060b57cec5SDimitry Andric 19070b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1908*5f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI 19090b57cec5SDimitry Andricvoid 19100b57cec5SDimitry Andricswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 19110b57cec5SDimitry Andric unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 19120b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 19130b57cec5SDimitry Andric{ 19140b57cec5SDimitry Andric __x.swap(__y); 19150b57cec5SDimitry Andric} 19160b57cec5SDimitry Andric 191706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 19185ffd83dbSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, 19195ffd83dbSDimitry Andric class _Predicate> 1920*5f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI 19215ffd83dbSDimitry Andric typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 19225ffd83dbSDimitry Andric erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, 19235ffd83dbSDimitry Andric _Predicate __pred) { 1924*5f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 19255ffd83dbSDimitry Andric} 19260b57cec5SDimitry Andric#endif 19270b57cec5SDimitry Andric 19280b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1929bdd1243dSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool 19300b57cec5SDimitry Andricoperator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 19310b57cec5SDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 19320b57cec5SDimitry Andric{ 19330b57cec5SDimitry Andric if (__x.size() != __y.size()) 19340b57cec5SDimitry Andric return false; 19350b57cec5SDimitry Andric typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 19360b57cec5SDimitry Andric const_iterator; 19370b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _EqRng; 19380b57cec5SDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 19390b57cec5SDimitry Andric { 19400b57cec5SDimitry Andric _EqRng __xeq = __x.equal_range(*__i); 19410b57cec5SDimitry Andric _EqRng __yeq = __y.equal_range(*__i); 1942*5f757f3fSDimitry Andric if (std::distance(__xeq.first, __xeq.second) != 1943*5f757f3fSDimitry Andric std::distance(__yeq.first, __yeq.second) || 1944*5f757f3fSDimitry Andric !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 19450b57cec5SDimitry Andric return false; 19460b57cec5SDimitry Andric __i = __xeq.second; 19470b57cec5SDimitry Andric } 19480b57cec5SDimitry Andric return true; 19490b57cec5SDimitry Andric} 19500b57cec5SDimitry Andric 195106c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 195206c3fb27SDimitry Andric 19530b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1954*5f757f3fSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI 19550b57cec5SDimitry Andricbool 19560b57cec5SDimitry Andricoperator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 19570b57cec5SDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 19580b57cec5SDimitry Andric{ 19590b57cec5SDimitry Andric return !(__x == __y); 19600b57cec5SDimitry Andric} 19610b57cec5SDimitry Andric 196206c3fb27SDimitry Andric#endif 196306c3fb27SDimitry Andric 19640b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 19650b57cec5SDimitry Andric 196606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1967bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 1968bdd1243dSDimitry Andricnamespace pmr { 1969bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 197006c3fb27SDimitry Andricusing unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1971bdd1243dSDimitry Andric 1972bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 197306c3fb27SDimitry Andricusing unordered_multiset _LIBCPP_AVAILABILITY_PMR = std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1974bdd1243dSDimitry Andric} // namespace pmr 1975bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD 1976bdd1243dSDimitry Andric#endif 1977bdd1243dSDimitry Andric 1978bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1979bdd1243dSDimitry Andric# include <concepts> 198006c3fb27SDimitry Andric# include <cstdlib> 1981bdd1243dSDimitry Andric# include <functional> 1982bdd1243dSDimitry Andric# include <iterator> 1983*5f757f3fSDimitry Andric# include <stdexcept> 198406c3fb27SDimitry Andric# include <type_traits> 1985bdd1243dSDimitry Andric#endif 1986bdd1243dSDimitry Andric 19870b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_SET 1988