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 135f757f3fSDimitry Andric// clang-format off 145f757f3fSDimitry 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 5325f757f3fSDimitry Andric// clang-format on 5335f757f3fSDimitry 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 573b3edf446SDimitry Andric_LIBCPP_PUSH_MACROS 574b3edf446SDimitry Andric#include <__undef_macros> 575b3edf446SDimitry Andric 5760b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 5770b57cec5SDimitry Andric 5780b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 5790b57cec5SDimitry Andricclass unordered_multiset; 5800b57cec5SDimitry Andric 581cb14a3feSDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 582cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_set { 5830b57cec5SDimitry Andricpublic: 5840b57cec5SDimitry Andric // types 5850b57cec5SDimitry Andric typedef _Value key_type; 5860b57cec5SDimitry Andric typedef key_type value_type; 58781ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 58881ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 58981ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 5900b57cec5SDimitry Andric typedef value_type& reference; 5910b57cec5SDimitry Andric typedef const value_type& const_reference; 5920b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 59306c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 5940b57cec5SDimitry Andric 595bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value, 596bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 597bdd1243dSDimitry Andric "original allocator"); 598bdd1243dSDimitry Andric 5990b57cec5SDimitry Andricprivate: 6000b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 6010b57cec5SDimitry Andric 6020b57cec5SDimitry Andric __table __table_; 6030b57cec5SDimitry Andric 6040b57cec5SDimitry Andricpublic: 6050b57cec5SDimitry Andric typedef typename __table::pointer pointer; 6060b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 6070b57cec5SDimitry Andric typedef typename __table::size_type size_type; 6080b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 6090b57cec5SDimitry Andric 6100b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 6110b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 6120b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 6130b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 6140b57cec5SDimitry Andric 61506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 6160b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 6170b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 6180b57cec5SDimitry Andric#endif 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 6210b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 6220b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 6230b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 6240b57cec5SDimitry Andric 625cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 626cb14a3feSDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI 627cb14a3feSDimitry Andric unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 62806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 629cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a) 6300b57cec5SDimitry Andric : unordered_set(__n, hasher(), key_equal(), __a) {} 631cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 6320b57cec5SDimitry Andric : unordered_set(__n, __hf, key_equal(), __a) {} 6330b57cec5SDimitry Andric#endif 634cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 635cb14a3feSDimitry Andric unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 6360b57cec5SDimitry Andric template <class _InputIterator> 63706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last); 6380b57cec5SDimitry Andric template <class _InputIterator> 639cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 640cb14a3feSDimitry Andric unordered_set(_InputIterator __first, 641cb14a3feSDimitry Andric _InputIterator __last, 642cb14a3feSDimitry Andric size_type __n, 643cb14a3feSDimitry Andric const hasher& __hf = hasher(), 6440b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 6450b57cec5SDimitry Andric template <class _InputIterator> 646cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 647cb14a3feSDimitry Andric _InputIterator __first, 648cb14a3feSDimitry Andric _InputIterator __last, 649cb14a3feSDimitry Andric size_type __n, 650cb14a3feSDimitry Andric const hasher& __hf, 651cb14a3feSDimitry Andric const key_equal& __eql, 6520b57cec5SDimitry Andric const allocator_type& __a); 65306c3fb27SDimitry Andric 65406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 65506c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 656cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 657cb14a3feSDimitry Andric from_range_t, 658cb14a3feSDimitry Andric _Range&& __range, 659cb14a3feSDimitry Andric size_type __n = /*implementation-defined*/ 0, 660cb14a3feSDimitry Andric const hasher& __hf = hasher(), 661cb14a3feSDimitry Andric const key_equal& __eql = key_equal(), 66206c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 66306c3fb27SDimitry Andric : __table_(__hf, __eql, __a) { 66406c3fb27SDimitry Andric if (__n > 0) { 66506c3fb27SDimitry Andric __table_.__rehash_unique(__n); 66606c3fb27SDimitry Andric } 66706c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 66806c3fb27SDimitry Andric } 66906c3fb27SDimitry Andric#endif 67006c3fb27SDimitry Andric 67106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 6720b57cec5SDimitry Andric template <class _InputIterator> 6735f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 674cb14a3feSDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 6750b57cec5SDimitry Andric : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 6760b57cec5SDimitry Andric template <class _InputIterator> 677cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 678cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 6790b57cec5SDimitry Andric : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 6800b57cec5SDimitry Andric#endif 68106c3fb27SDimitry Andric 68206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 68306c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 684cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 68506c3fb27SDimitry Andric : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 68606c3fb27SDimitry Andric 68706c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 68806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 68906c3fb27SDimitry Andric unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 69006c3fb27SDimitry Andric : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 69106c3fb27SDimitry Andric#endif 69206c3fb27SDimitry Andric 693cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a); 69406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u); 69506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a); 6960b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 697cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _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); 700cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 701cb14a3feSDimitry Andric unordered_set(initializer_list<value_type> __il, 702cb14a3feSDimitry Andric size_type __n, 7030b57cec5SDimitry Andric const hasher& __hf = hasher(), 7040b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 705cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 706cb14a3feSDimitry Andric initializer_list<value_type> __il, 707cb14a3feSDimitry Andric size_type __n, 708cb14a3feSDimitry Andric const hasher& __hf, 709cb14a3feSDimitry Andric const key_equal& __eql, 7100b57cec5SDimitry Andric const allocator_type& __a); 71106c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 14 7125f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 713cb14a3feSDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 7140b57cec5SDimitry Andric : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 7155f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 716cb14a3feSDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 7170b57cec5SDimitry Andric : unordered_set(__il, __n, __hf, key_equal(), __a) {} 7180b57cec5SDimitry Andric# endif 7190b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 720cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~unordered_set() { 721bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 7220b57cec5SDimitry Andric } 7230b57cec5SDimitry Andric 724cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) { 7250b57cec5SDimitry Andric __table_ = __u.__table_; 7260b57cec5SDimitry Andric return *this; 7270b57cec5SDimitry Andric } 7280b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 729cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u) 7300b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 731cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il); 7320b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7330b57cec5SDimitry Andric 734cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 735cb14a3feSDimitry Andric return allocator_type(__table_.__node_alloc()); 736cb14a3feSDimitry Andric } 7370b57cec5SDimitry Andric 738cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 739cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 740cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 7410b57cec5SDimitry Andric 742cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 743cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 744cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 745cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 746cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 747cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 7480b57cec5SDimitry Andric 7490b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 7500b57cec5SDimitry Andric template <class... _Args> 751cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 752cb14a3feSDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...); 753cb14a3feSDimitry Andric } 7540b57cec5SDimitry Andric template <class... _Args> 755cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) { 75681ad6265SDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 7570b57cec5SDimitry Andric } 7580b57cec5SDimitry Andric 759cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { 760cb14a3feSDimitry Andric return __table_.__insert_unique(std::move(__x)); 7610b57cec5SDimitry Andric } 762cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; } 76381ad6265SDimitry Andric 764cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 7650b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 766cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 7670b57cec5SDimitry Andric 768cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 7690b57cec5SDimitry Andric template <class _InputIterator> 770cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 7710b57cec5SDimitry Andric 77206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 77306c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 774cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 77506c3fb27SDimitry Andric for (auto&& __element : __range) { 77606c3fb27SDimitry Andric __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 77706c3fb27SDimitry Andric } 77806c3fb27SDimitry Andric } 77906c3fb27SDimitry Andric#endif 78006c3fb27SDimitry Andric 781cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 782cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 783cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 784cb14a3feSDimitry Andric return __table_.erase(__first, __last); 785cb14a3feSDimitry Andric } 786cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 7870b57cec5SDimitry Andric 78806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 789cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 79006c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 7910b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 792cb14a3feSDimitry Andric return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 7930b57cec5SDimitry Andric } 794cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) { 79506c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 7960b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 797cb14a3feSDimitry Andric return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh)); 7980b57cec5SDimitry Andric } 799cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 8000b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 8010b57cec5SDimitry Andric } 802cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 8030b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__it); 8040b57cec5SDimitry Andric } 8050b57cec5SDimitry Andric 8060b57cec5SDimitry Andric template <class _H2, class _P2> 807cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 808cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 809cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8100b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8110b57cec5SDimitry Andric } 8120b57cec5SDimitry Andric template <class _H2, class _P2> 813cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 814cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 815cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8160b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8170b57cec5SDimitry Andric } 8180b57cec5SDimitry Andric template <class _H2, class _P2> 819cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 820cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 821cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8220b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8230b57cec5SDimitry Andric } 8240b57cec5SDimitry Andric template <class _H2, class _P2> 825cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 826cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 827cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8280b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8290b57cec5SDimitry Andric } 8300b57cec5SDimitry Andric#endif 8310b57cec5SDimitry Andric 832cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 833cb14a3feSDimitry Andric __table_.swap(__u.__table_); 834cb14a3feSDimitry Andric } 8350b57cec5SDimitry Andric 836cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 837cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 8380b57cec5SDimitry Andric 839cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 840cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 84106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 842cb14a3feSDimitry Andric template <class _K2, 843cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 844cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 845cb14a3feSDimitry Andric return __table_.find(__k); 846cb14a3feSDimitry Andric } 847cb14a3feSDimitry Andric template <class _K2, 848cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 849cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 850cb14a3feSDimitry Andric return __table_.find(__k); 851cb14a3feSDimitry Andric } 85206c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 853349cc55cSDimitry Andric 854cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 85506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 856cb14a3feSDimitry Andric template <class _K2, 857cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 858cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 859cb14a3feSDimitry Andric return __table_.__count_unique(__k); 860cb14a3feSDimitry Andric } 86106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 862349cc55cSDimitry Andric 86306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 864cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 865e8d8bef9SDimitry Andric 866cb14a3feSDimitry Andric template <class _K2, 867cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 868cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 869cb14a3feSDimitry Andric return find(__k) != end(); 870cb14a3feSDimitry Andric } 87106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 872349cc55cSDimitry Andric 873cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 874cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 875cb14a3feSDimitry Andric } 876cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 877cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 878cb14a3feSDimitry Andric } 87906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 880cb14a3feSDimitry Andric template <class _K2, 881cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 882cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 883cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 884cb14a3feSDimitry Andric } 885cb14a3feSDimitry Andric template <class _K2, 886cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 887cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 888cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 889cb14a3feSDimitry Andric } 89006c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 8910b57cec5SDimitry Andric 892cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 893cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 8940b57cec5SDimitry Andric 895cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 896cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 8970b57cec5SDimitry Andric 898cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 899cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 900cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 901cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 902cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 903cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 9040b57cec5SDimitry Andric 905cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 906cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 907cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 908cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 909cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 9100b57cec5SDimitry Andric}; 9110b57cec5SDimitry Andric 912349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 9130b57cec5SDimitry Andrictemplate <class _InputIterator, 9140b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 9150b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 9160b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 91706c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 918349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 919349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 920349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 921349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 922cb14a3feSDimitry Andricunordered_set(_InputIterator, 923cb14a3feSDimitry Andric _InputIterator, 924cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 925cb14a3feSDimitry Andric _Hash = _Hash(), 926cb14a3feSDimitry Andric _Pred = _Pred(), 927cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 9280b57cec5SDimitry Andric 92906c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 93006c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 93106c3fb27SDimitry Andric class _Hash = hash<ranges::range_value_t<_Range>>, 93206c3fb27SDimitry Andric class _Pred = equal_to<ranges::range_value_t<_Range>>, 93306c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 93406c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 93506c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 93606c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 93706c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 938cb14a3feSDimitry Andricunordered_set(from_range_t, 939cb14a3feSDimitry Andric _Range&&, 940cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 941cb14a3feSDimitry Andric _Hash = _Hash(), 942cb14a3feSDimitry Andric _Pred = _Pred(), 943cb14a3feSDimitry Andric _Allocator = _Allocator()) 94406c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 94506c3fb27SDimitry Andric# endif 94606c3fb27SDimitry Andric 947cb14a3feSDimitry Andrictemplate <class _Tp, 948cb14a3feSDimitry Andric class _Hash = hash<_Tp>, 9490b57cec5SDimitry Andric class _Pred = equal_to<_Tp>, 9500b57cec5SDimitry Andric class _Allocator = allocator<_Tp>, 951349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 952349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 953349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 954349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 955cb14a3feSDimitry Andricunordered_set(initializer_list<_Tp>, 956cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 957cb14a3feSDimitry Andric _Hash = _Hash(), 958cb14a3feSDimitry Andric _Pred = _Pred(), 959cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 9600b57cec5SDimitry Andric 961cb14a3feSDimitry Andrictemplate <class _InputIterator, 962cb14a3feSDimitry Andric class _Allocator, 96306c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 964349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 965cb14a3feSDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 9660b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, 9670b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 9680b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 9690b57cec5SDimitry Andric _Allocator>; 9700b57cec5SDimitry Andric 971cb14a3feSDimitry Andrictemplate <class _InputIterator, 972cb14a3feSDimitry Andric class _Hash, 973cb14a3feSDimitry Andric class _Allocator, 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<_Allocator>::value>> 978cb14a3feSDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 979cb14a3feSDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>; 9800b57cec5SDimitry Andric 98106c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 98206c3fb27SDimitry Andric 983cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 98406c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 985cb14a3feSDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, 986cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 987cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 988cb14a3feSDimitry Andric _Allocator>; 98906c3fb27SDimitry Andric 990cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 99106c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, _Allocator) 992cb14a3feSDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, 993cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 994cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 995cb14a3feSDimitry Andric _Allocator>; 99606c3fb27SDimitry Andric 997cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 998cb14a3feSDimitry Andric class _Hash, 999cb14a3feSDimitry Andric class _Allocator, 100006c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 100106c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 100206c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 100306c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 100406c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 100506c3fb27SDimitry Andric 100606c3fb27SDimitry Andric# endif 100706c3fb27SDimitry Andric 1008cb14a3feSDimitry Andrictemplate <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 10090b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 10100b57cec5SDimitry Andric -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 10110b57cec5SDimitry Andric 1012cb14a3feSDimitry Andrictemplate <class _Tp, 1013cb14a3feSDimitry Andric class _Hash, 1014cb14a3feSDimitry Andric class _Allocator, 1015349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1016349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1017349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10180b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 10190b57cec5SDimitry Andric -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 10200b57cec5SDimitry Andric#endif 10210b57cec5SDimitry Andric 10220b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1023cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql) 1024cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1025753f127fSDimitry Andric __table_.__rehash_unique(__n); 10260b57cec5SDimitry Andric} 10270b57cec5SDimitry Andric 10280b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1029cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1030cb14a3feSDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1031cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1032753f127fSDimitry Andric __table_.__rehash_unique(__n); 10330b57cec5SDimitry Andric} 10340b57cec5SDimitry Andric 10350b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10360b57cec5SDimitry Andrictemplate <class _InputIterator> 1037cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) { 10380b57cec5SDimitry Andric insert(__first, __last); 10390b57cec5SDimitry Andric} 10400b57cec5SDimitry Andric 10410b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10420b57cec5SDimitry Andrictemplate <class _InputIterator> 10430b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1044cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1045cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1046753f127fSDimitry Andric __table_.__rehash_unique(__n); 10470b57cec5SDimitry Andric insert(__first, __last); 10480b57cec5SDimitry Andric} 10490b57cec5SDimitry Andric 10500b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10510b57cec5SDimitry Andrictemplate <class _InputIterator> 10520b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1053cb14a3feSDimitry Andric _InputIterator __first, 1054cb14a3feSDimitry Andric _InputIterator __last, 1055cb14a3feSDimitry Andric size_type __n, 1056cb14a3feSDimitry Andric const hasher& __hf, 1057cb14a3feSDimitry Andric const key_equal& __eql, 10580b57cec5SDimitry Andric const allocator_type& __a) 1059cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1060cb14a3feSDimitry Andric __table_.__rehash_unique(__n); 1061cb14a3feSDimitry Andric insert(__first, __last); 10620b57cec5SDimitry Andric} 10630b57cec5SDimitry Andric 10640b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1065cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {} 1066cb14a3feSDimitry Andric 1067cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1068cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) { 1069753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 10700b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 10710b57cec5SDimitry Andric} 10720b57cec5SDimitry Andric 10730b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1074cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a) 1075cb14a3feSDimitry Andric : __table_(__u.__table_, __a) { 1076753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 10770b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 10780b57cec5SDimitry Andric} 10790b57cec5SDimitry Andric 10800b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 10810b57cec5SDimitry Andric 10820b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1083cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u) 10840b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1085cb14a3feSDimitry Andric : __table_(std::move(__u.__table_)) {} 10860b57cec5SDimitry Andric 10870b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1088cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a) 1089cb14a3feSDimitry Andric : __table_(std::move(__u.__table_), __a) { 1090cb14a3feSDimitry Andric if (__a != __u.get_allocator()) { 10910b57cec5SDimitry Andric iterator __i = __u.begin(); 10920b57cec5SDimitry Andric while (__u.size() != 0) 10935f757f3fSDimitry Andric __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value())); 10940b57cec5SDimitry Andric } 10950b57cec5SDimitry Andric} 10960b57cec5SDimitry Andric 10970b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1098cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) { 10990b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11000b57cec5SDimitry Andric} 11010b57cec5SDimitry Andric 11020b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11030b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1104cb14a3feSDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1105cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1106753f127fSDimitry Andric __table_.__rehash_unique(__n); 11070b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11080b57cec5SDimitry Andric} 11090b57cec5SDimitry Andric 11100b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11110b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1112cb14a3feSDimitry Andric initializer_list<value_type> __il, 1113cb14a3feSDimitry Andric size_type __n, 1114cb14a3feSDimitry Andric const hasher& __hf, 1115cb14a3feSDimitry Andric const key_equal& __eql, 1116cb14a3feSDimitry Andric const allocator_type& __a) 1117cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1118753f127fSDimitry Andric __table_.__rehash_unique(__n); 11190b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11200b57cec5SDimitry Andric} 11210b57cec5SDimitry Andric 11220b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1123cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>& 11240b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 1125cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 11265f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 11270b57cec5SDimitry Andric return *this; 11280b57cec5SDimitry Andric} 11290b57cec5SDimitry Andric 11300b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1131cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>& 1132cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 11330b57cec5SDimitry Andric __table_.__assign_unique(__il.begin(), __il.end()); 11340b57cec5SDimitry Andric return *this; 11350b57cec5SDimitry Andric} 11360b57cec5SDimitry Andric 11370b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 11380b57cec5SDimitry Andric 11390b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11400b57cec5SDimitry Andrictemplate <class _InputIterator> 1141cb14a3feSDimitry Andricinline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 11420b57cec5SDimitry Andric for (; __first != __last; ++__first) 11430b57cec5SDimitry Andric __table_.__insert_unique(*__first); 11440b57cec5SDimitry Andric} 11450b57cec5SDimitry Andric 11460b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1147cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 1148cb14a3feSDimitry Andricswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1149cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 11500b57cec5SDimitry Andric __x.swap(__y); 11510b57cec5SDimitry Andric} 11520b57cec5SDimitry Andric 115306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1154cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1155cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 1156cb14a3feSDimitry Andricerase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 11575f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 11585ffd83dbSDimitry Andric} 11590b57cec5SDimitry Andric#endif 11600b57cec5SDimitry Andric 11610b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1162cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1163cb14a3feSDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 11640b57cec5SDimitry Andric if (__x.size() != __y.size()) 11650b57cec5SDimitry Andric return false; 1166cb14a3feSDimitry Andric typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1167cb14a3feSDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 11680b57cec5SDimitry Andric const_iterator __j = __y.find(*__i); 11690b57cec5SDimitry Andric if (__j == __ey || !(*__i == *__j)) 11700b57cec5SDimitry Andric return false; 11710b57cec5SDimitry Andric } 11720b57cec5SDimitry Andric return true; 11730b57cec5SDimitry Andric} 11740b57cec5SDimitry Andric 117506c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 117606c3fb27SDimitry Andric 11770b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1178cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1179cb14a3feSDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 11800b57cec5SDimitry Andric return !(__x == __y); 11810b57cec5SDimitry Andric} 11820b57cec5SDimitry Andric 118306c3fb27SDimitry Andric#endif 118406c3fb27SDimitry Andric 1185cb14a3feSDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 1186cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multiset { 11870b57cec5SDimitry Andricpublic: 11880b57cec5SDimitry Andric // types 11890b57cec5SDimitry Andric typedef _Value key_type; 11900b57cec5SDimitry Andric typedef key_type value_type; 119181ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 119281ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 119381ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 11940b57cec5SDimitry Andric typedef value_type& reference; 11950b57cec5SDimitry Andric typedef const value_type& const_reference; 11960b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 119706c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 11980b57cec5SDimitry Andric 11990b57cec5SDimitry Andricprivate: 12000b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 12010b57cec5SDimitry Andric 12020b57cec5SDimitry Andric __table __table_; 12030b57cec5SDimitry Andric 12040b57cec5SDimitry Andricpublic: 12050b57cec5SDimitry Andric typedef typename __table::pointer pointer; 12060b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 12070b57cec5SDimitry Andric typedef typename __table::size_type size_type; 12080b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 12090b57cec5SDimitry Andric 12100b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 12110b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 12120b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 12130b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 12140b57cec5SDimitry Andric 121506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 12160b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 12170b57cec5SDimitry Andric#endif 12180b57cec5SDimitry Andric 12190b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 12200b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 12210b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 12220b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 12230b57cec5SDimitry Andric 1224cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1225cb14a3feSDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI 1226cb14a3feSDimitry Andric unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 12275f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1228cb14a3feSDimitry Andric unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 122906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 1230cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a) 12310b57cec5SDimitry Andric : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1232cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 12330b57cec5SDimitry Andric : unordered_multiset(__n, __hf, key_equal(), __a) {} 12340b57cec5SDimitry Andric#endif 12350b57cec5SDimitry Andric template <class _InputIterator> 123606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last); 12370b57cec5SDimitry Andric template <class _InputIterator> 1238cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1239cb14a3feSDimitry Andric _InputIterator __first, 1240cb14a3feSDimitry Andric _InputIterator __last, 1241cb14a3feSDimitry Andric size_type __n, 1242cb14a3feSDimitry Andric const hasher& __hf = hasher(), 12430b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 12440b57cec5SDimitry Andric template <class _InputIterator> 1245cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1246cb14a3feSDimitry Andric _InputIterator __first, 1247cb14a3feSDimitry Andric _InputIterator __last, 1248cb14a3feSDimitry Andric size_type __n, 1249cb14a3feSDimitry Andric const hasher& __hf, 1250cb14a3feSDimitry Andric const key_equal& __eql, 1251cb14a3feSDimitry Andric const allocator_type& __a); 125206c3fb27SDimitry Andric 125306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 125406c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1255cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1256cb14a3feSDimitry Andric from_range_t, 1257cb14a3feSDimitry Andric _Range&& __range, 1258cb14a3feSDimitry Andric size_type __n = /*implementation-defined*/ 0, 1259cb14a3feSDimitry Andric const hasher& __hf = hasher(), 1260cb14a3feSDimitry Andric const key_equal& __eql = key_equal(), 126106c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 126206c3fb27SDimitry Andric : __table_(__hf, __eql, __a) { 126306c3fb27SDimitry Andric if (__n > 0) { 126406c3fb27SDimitry Andric __table_.__rehash_multi(__n); 126506c3fb27SDimitry Andric } 126606c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 126706c3fb27SDimitry Andric } 126806c3fb27SDimitry Andric#endif 126906c3fb27SDimitry Andric 127006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 12710b57cec5SDimitry Andric template <class _InputIterator> 12725f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 1273cb14a3feSDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 12740b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 12750b57cec5SDimitry Andric template <class _InputIterator> 1276cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1277cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 12780b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 12790b57cec5SDimitry Andric#endif 128006c3fb27SDimitry Andric 128106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 128206c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1283cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 128406c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 128506c3fb27SDimitry Andric 128606c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 128706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 128806c3fb27SDimitry Andric unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 128906c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 129006c3fb27SDimitry Andric#endif 129106c3fb27SDimitry Andric 1292cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a); 129306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); 129406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 12950b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1296cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u) 12970b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 129806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 129906c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il); 1300cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1301cb14a3feSDimitry Andric initializer_list<value_type> __il, 1302cb14a3feSDimitry Andric size_type __n, 13030b57cec5SDimitry Andric const hasher& __hf = hasher(), 13040b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 1305cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1306cb14a3feSDimitry Andric initializer_list<value_type> __il, 1307cb14a3feSDimitry Andric size_type __n, 1308cb14a3feSDimitry Andric const hasher& __hf, 1309cb14a3feSDimitry Andric const key_equal& __eql, 13100b57cec5SDimitry Andric const allocator_type& __a); 131106c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 14 13125f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13130b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 13140b57cec5SDimitry Andric : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 13155f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13160b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 13170b57cec5SDimitry Andric : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 13180b57cec5SDimitry Andric# endif 13190b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 1320cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() { 1321bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 13220b57cec5SDimitry Andric } 13230b57cec5SDimitry Andric 1324cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) { 13250b57cec5SDimitry Andric __table_ = __u.__table_; 13260b57cec5SDimitry Andric return *this; 13270b57cec5SDimitry Andric } 13280b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1329cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u) 13300b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 133106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il); 13320b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 13330b57cec5SDimitry Andric 1334cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1335cb14a3feSDimitry Andric return allocator_type(__table_.__node_alloc()); 1336cb14a3feSDimitry Andric } 13370b57cec5SDimitry Andric 1338cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1339cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1340cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 13410b57cec5SDimitry Andric 1342cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1343cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1344cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1345cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1346cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1347cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 13480b57cec5SDimitry Andric 13490b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 13500b57cec5SDimitry Andric template <class... _Args> 1351cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1352cb14a3feSDimitry Andric return __table_.__emplace_multi(std::forward<_Args>(__args)...); 1353cb14a3feSDimitry Andric } 13540b57cec5SDimitry Andric template <class... _Args> 1355cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1356cb14a3feSDimitry Andric return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...); 1357cb14a3feSDimitry Andric } 13580b57cec5SDimitry Andric 1359cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); } 1360cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 1361cb14a3feSDimitry Andric return __table_.__insert_multi(__p, std::move(__x)); 1362cb14a3feSDimitry Andric } 1363cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 13640b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 13650b57cec5SDimitry Andric 1366cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 13670b57cec5SDimitry Andric 1368cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 1369cb14a3feSDimitry Andric return __table_.__insert_multi(__p, __x); 1370cb14a3feSDimitry Andric } 13710b57cec5SDimitry Andric 13720b57cec5SDimitry Andric template <class _InputIterator> 1373cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 13740b57cec5SDimitry Andric 137506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 137606c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1377cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 137806c3fb27SDimitry Andric for (auto&& __element : __range) { 137906c3fb27SDimitry Andric __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 138006c3fb27SDimitry Andric } 138106c3fb27SDimitry Andric } 138206c3fb27SDimitry Andric#endif 138306c3fb27SDimitry Andric 138406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1385cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 138606c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 13870b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1388cb14a3feSDimitry Andric return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 13890b57cec5SDimitry Andric } 1390cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 139106c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 13920b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1393cb14a3feSDimitry Andric return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh)); 13940b57cec5SDimitry Andric } 1395cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) { 1396cb14a3feSDimitry Andric return __table_.template __node_handle_extract<node_type>(__position); 13970b57cec5SDimitry Andric } 1398cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 13990b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 14000b57cec5SDimitry Andric } 14010b57cec5SDimitry Andric 14020b57cec5SDimitry Andric template <class _H2, class _P2> 1403cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 1404cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1405cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14060b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14070b57cec5SDimitry Andric } 14080b57cec5SDimitry Andric template <class _H2, class _P2> 1409cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 1410cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1411cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14120b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14130b57cec5SDimitry Andric } 14140b57cec5SDimitry Andric template <class _H2, class _P2> 1415cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 1416cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1417cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14180b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14190b57cec5SDimitry Andric } 14200b57cec5SDimitry Andric template <class _H2, class _P2> 1421cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 1422cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1423cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14240b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14250b57cec5SDimitry Andric } 14260b57cec5SDimitry Andric#endif 14270b57cec5SDimitry Andric 1428cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 1429cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 1430cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1431cb14a3feSDimitry Andric return __table_.erase(__first, __last); 1432cb14a3feSDimitry Andric } 1433cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 14340b57cec5SDimitry Andric 1435cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 1436cb14a3feSDimitry Andric __table_.swap(__u.__table_); 1437cb14a3feSDimitry Andric } 14380b57cec5SDimitry Andric 1439cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 1440cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 14410b57cec5SDimitry Andric 1442cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1443cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 144406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1445cb14a3feSDimitry Andric template <class _K2, 1446cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1447cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1448cb14a3feSDimitry Andric return __table_.find(__k); 1449cb14a3feSDimitry Andric } 1450cb14a3feSDimitry Andric template <class _K2, 1451cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1452cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1453cb14a3feSDimitry Andric return __table_.find(__k); 1454cb14a3feSDimitry Andric } 145506c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1456349cc55cSDimitry Andric 1457cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 145806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1459cb14a3feSDimitry Andric template <class _K2, 1460cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1461cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1462cb14a3feSDimitry Andric return __table_.__count_multi(__k); 1463cb14a3feSDimitry Andric } 146406c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1465349cc55cSDimitry Andric 146606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1467cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1468e8d8bef9SDimitry Andric 1469cb14a3feSDimitry Andric template <class _K2, 1470cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1471cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1472cb14a3feSDimitry Andric return find(__k) != end(); 1473cb14a3feSDimitry Andric } 147406c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1475349cc55cSDimitry Andric 1476cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1477cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1478cb14a3feSDimitry Andric } 1479cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1480cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1481cb14a3feSDimitry Andric } 148206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1483cb14a3feSDimitry Andric template <class _K2, 1484cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1485cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1486cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1487cb14a3feSDimitry Andric } 1488cb14a3feSDimitry Andric template <class _K2, 1489cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1490cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1491cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1492cb14a3feSDimitry Andric } 149306c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 14940b57cec5SDimitry Andric 1495cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1496cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 14970b57cec5SDimitry Andric 1498cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1499cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 15000b57cec5SDimitry Andric 1501cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1502cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1503cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1504cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1505cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1506cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 15070b57cec5SDimitry Andric 1508cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1509cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1510cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1511cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 1512cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 15130b57cec5SDimitry Andric}; 15140b57cec5SDimitry Andric 1515349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 15160b57cec5SDimitry Andrictemplate <class _InputIterator, 15170b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 15180b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 15190b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 152006c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1521349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1522349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1523349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1524349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1525cb14a3feSDimitry Andricunordered_multiset( 1526cb14a3feSDimitry Andric _InputIterator, 1527cb14a3feSDimitry Andric _InputIterator, 1528cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1529cb14a3feSDimitry Andric _Hash = _Hash(), 1530cb14a3feSDimitry Andric _Pred = _Pred(), 1531cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 15320b57cec5SDimitry Andric 153306c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 153406c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 153506c3fb27SDimitry Andric class _Hash = hash<ranges::range_value_t<_Range>>, 153606c3fb27SDimitry Andric class _Pred = equal_to<ranges::range_value_t<_Range>>, 153706c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 153806c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 153906c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 154006c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 154106c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1542cb14a3feSDimitry Andricunordered_multiset( 1543cb14a3feSDimitry Andric from_range_t, 1544cb14a3feSDimitry Andric _Range&&, 1545cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1546cb14a3feSDimitry Andric _Hash = _Hash(), 1547cb14a3feSDimitry Andric _Pred = _Pred(), 1548cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 154906c3fb27SDimitry Andric# endif 155006c3fb27SDimitry Andric 1551cb14a3feSDimitry Andrictemplate <class _Tp, 1552cb14a3feSDimitry Andric class _Hash = hash<_Tp>, 1553cb14a3feSDimitry Andric class _Pred = equal_to<_Tp>, 1554cb14a3feSDimitry Andric class _Allocator = allocator<_Tp>, 1555349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1556349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1557349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1558349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1559cb14a3feSDimitry Andricunordered_multiset(initializer_list<_Tp>, 1560cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1561cb14a3feSDimitry Andric _Hash = _Hash(), 1562cb14a3feSDimitry Andric _Pred = _Pred(), 1563cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 15640b57cec5SDimitry Andric 1565cb14a3feSDimitry Andrictemplate <class _InputIterator, 1566cb14a3feSDimitry Andric class _Allocator, 156706c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1568349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 15690b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 15700b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, 15710b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 15720b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 15730b57cec5SDimitry Andric _Allocator>; 15740b57cec5SDimitry Andric 1575cb14a3feSDimitry Andrictemplate <class _InputIterator, 1576cb14a3feSDimitry Andric class _Hash, 1577cb14a3feSDimitry Andric class _Allocator, 157806c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1579349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1580349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1581349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1582cb14a3feSDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1583cb14a3feSDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, 1584cb14a3feSDimitry Andric _Hash, 15850b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 15860b57cec5SDimitry Andric _Allocator>; 15870b57cec5SDimitry Andric 158806c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 158906c3fb27SDimitry Andric 1590cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 159106c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1592cb14a3feSDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, 1593cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 1594cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 1595cb14a3feSDimitry Andric _Allocator>; 159606c3fb27SDimitry Andric 1597cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 159806c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, _Allocator) 1599cb14a3feSDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, 1600cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 1601cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 1602cb14a3feSDimitry Andric _Allocator>; 160306c3fb27SDimitry Andric 1604cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 1605cb14a3feSDimitry Andric class _Hash, 1606cb14a3feSDimitry Andric class _Allocator, 160706c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 160806c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 160906c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 161006c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 161106c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 161206c3fb27SDimitry Andric 161306c3fb27SDimitry Andric# endif 161406c3fb27SDimitry Andric 1615cb14a3feSDimitry Andrictemplate <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 16160b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 16170b57cec5SDimitry Andric -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 16180b57cec5SDimitry Andric 1619cb14a3feSDimitry Andrictemplate <class _Tp, 1620cb14a3feSDimitry Andric class _Hash, 1621cb14a3feSDimitry Andric class _Allocator, 1622349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1623349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1624349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 16250b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 16260b57cec5SDimitry Andric -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 16270b57cec5SDimitry Andric#endif 16280b57cec5SDimitry Andric 16290b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16300b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16310b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql) 1632cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1633753f127fSDimitry Andric __table_.__rehash_multi(__n); 16340b57cec5SDimitry Andric} 16350b57cec5SDimitry Andric 16360b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16370b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1638cb14a3feSDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1639cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1640cb14a3feSDimitry Andric __table_.__rehash_multi(__n); 1641cb14a3feSDimitry Andric} 1642cb14a3feSDimitry Andric 1643cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1644cb14a3feSDimitry Andrictemplate <class _InputIterator> 1645cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) { 1646cb14a3feSDimitry Andric insert(__first, __last); 1647cb14a3feSDimitry Andric} 1648cb14a3feSDimitry Andric 1649cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1650cb14a3feSDimitry Andrictemplate <class _InputIterator> 1651cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1652cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1653cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1654cb14a3feSDimitry Andric __table_.__rehash_multi(__n); 1655cb14a3feSDimitry Andric insert(__first, __last); 1656cb14a3feSDimitry Andric} 1657cb14a3feSDimitry Andric 1658cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1659cb14a3feSDimitry Andrictemplate <class _InputIterator> 1660cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1661cb14a3feSDimitry Andric _InputIterator __first, 1662cb14a3feSDimitry Andric _InputIterator __last, 1663cb14a3feSDimitry Andric size_type __n, 1664cb14a3feSDimitry Andric const hasher& __hf, 1665cb14a3feSDimitry Andric const key_equal& __eql, 16660b57cec5SDimitry Andric const allocator_type& __a) 1667cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1668753f127fSDimitry Andric __table_.__rehash_multi(__n); 16690b57cec5SDimitry Andric insert(__first, __last); 16700b57cec5SDimitry Andric} 16710b57cec5SDimitry Andric 16720b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1673cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a) 1674cb14a3feSDimitry Andric : __table_(__a) {} 16750b57cec5SDimitry Andric 16760b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1677cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u) 1678cb14a3feSDimitry Andric : __table_(__u.__table_) { 1679753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 16800b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16810b57cec5SDimitry Andric} 16820b57cec5SDimitry Andric 16830b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16840b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16850b57cec5SDimitry Andric const unordered_multiset& __u, const allocator_type& __a) 1686cb14a3feSDimitry Andric : __table_(__u.__table_, __a) { 1687753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 16880b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16890b57cec5SDimitry Andric} 16900b57cec5SDimitry Andric 16910b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 16920b57cec5SDimitry Andric 16930b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1694cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u) 16950b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1696cb14a3feSDimitry Andric : __table_(std::move(__u.__table_)) {} 16970b57cec5SDimitry Andric 16980b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16990b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 17000b57cec5SDimitry Andric unordered_multiset&& __u, const allocator_type& __a) 1701cb14a3feSDimitry Andric : __table_(std::move(__u.__table_), __a) { 1702cb14a3feSDimitry Andric if (__a != __u.get_allocator()) { 17030b57cec5SDimitry Andric iterator __i = __u.begin(); 17040b57cec5SDimitry Andric while (__u.size() != 0) 17055f757f3fSDimitry Andric __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value())); 17060b57cec5SDimitry Andric } 17070b57cec5SDimitry Andric} 17080b57cec5SDimitry Andric 17090b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1710cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) { 17110b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17120b57cec5SDimitry Andric} 17130b57cec5SDimitry Andric 17140b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17150b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1716cb14a3feSDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1717cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1718753f127fSDimitry Andric __table_.__rehash_multi(__n); 17190b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17200b57cec5SDimitry Andric} 17210b57cec5SDimitry Andric 17220b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17230b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1724cb14a3feSDimitry Andric initializer_list<value_type> __il, 1725cb14a3feSDimitry Andric size_type __n, 1726cb14a3feSDimitry Andric const hasher& __hf, 1727cb14a3feSDimitry Andric const key_equal& __eql, 1728cb14a3feSDimitry Andric const allocator_type& __a) 1729cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1730753f127fSDimitry Andric __table_.__rehash_multi(__n); 17310b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17320b57cec5SDimitry Andric} 17330b57cec5SDimitry Andric 17340b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1735cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1736cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u) 1737cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 17385f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 17390b57cec5SDimitry Andric return *this; 17400b57cec5SDimitry Andric} 17410b57cec5SDimitry Andric 17420b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1743cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1744cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 17450b57cec5SDimitry Andric __table_.__assign_multi(__il.begin(), __il.end()); 17460b57cec5SDimitry Andric return *this; 17470b57cec5SDimitry Andric} 17480b57cec5SDimitry Andric 17490b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 17500b57cec5SDimitry Andric 17510b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17520b57cec5SDimitry Andrictemplate <class _InputIterator> 1753cb14a3feSDimitry Andricinline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 17540b57cec5SDimitry Andric for (; __first != __last; ++__first) 17550b57cec5SDimitry Andric __table_.__insert_multi(*__first); 17560b57cec5SDimitry Andric} 17570b57cec5SDimitry Andric 17580b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1759cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 1760cb14a3feSDimitry Andricswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1761cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 17620b57cec5SDimitry Andric __x.swap(__y); 17630b57cec5SDimitry Andric} 17640b57cec5SDimitry Andric 176506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1766cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1767cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 1768cb14a3feSDimitry Andricerase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 17695f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 17705ffd83dbSDimitry Andric} 17710b57cec5SDimitry Andric#endif 17720b57cec5SDimitry Andric 17730b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1774cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1775cb14a3feSDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 17760b57cec5SDimitry Andric if (__x.size() != __y.size()) 17770b57cec5SDimitry Andric return false; 1778cb14a3feSDimitry Andric typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 17790b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _EqRng; 1780cb14a3feSDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 17810b57cec5SDimitry Andric _EqRng __xeq = __x.equal_range(*__i); 17820b57cec5SDimitry Andric _EqRng __yeq = __y.equal_range(*__i); 1783cb14a3feSDimitry Andric if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 17845f757f3fSDimitry Andric !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 17850b57cec5SDimitry Andric return false; 17860b57cec5SDimitry Andric __i = __xeq.second; 17870b57cec5SDimitry Andric } 17880b57cec5SDimitry Andric return true; 17890b57cec5SDimitry Andric} 17900b57cec5SDimitry Andric 179106c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 179206c3fb27SDimitry Andric 17930b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1794cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1795cb14a3feSDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 17960b57cec5SDimitry Andric return !(__x == __y); 17970b57cec5SDimitry Andric} 17980b57cec5SDimitry Andric 179906c3fb27SDimitry Andric#endif 180006c3fb27SDimitry Andric 18010b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 18020b57cec5SDimitry Andric 180306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1804bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 1805bdd1243dSDimitry Andricnamespace pmr { 1806bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 180706c3fb27SDimitry Andricusing unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1808bdd1243dSDimitry Andric 1809bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1810cb14a3feSDimitry Andricusing unordered_multiset _LIBCPP_AVAILABILITY_PMR = 1811cb14a3feSDimitry Andric std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1812bdd1243dSDimitry Andric} // namespace pmr 1813bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD 1814bdd1243dSDimitry Andric#endif 1815bdd1243dSDimitry Andric 1816b3edf446SDimitry Andric_LIBCPP_POP_MACROS 1817b3edf446SDimitry Andric 1818bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1819bdd1243dSDimitry Andric# include <concepts> 182006c3fb27SDimitry Andric# include <cstdlib> 1821bdd1243dSDimitry Andric# include <functional> 1822bdd1243dSDimitry Andric# include <iterator> 18235f757f3fSDimitry Andric# include <stdexcept> 182406c3fb27SDimitry Andric# include <type_traits> 1825bdd1243dSDimitry Andric#endif 1826bdd1243dSDimitry Andric 18270b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_SET 1828