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 5730b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 5740b57cec5SDimitry Andric 5750b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 5760b57cec5SDimitry Andricclass unordered_multiset; 5770b57cec5SDimitry Andric 578*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 579*cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_set { 5800b57cec5SDimitry Andricpublic: 5810b57cec5SDimitry Andric // types 5820b57cec5SDimitry Andric typedef _Value key_type; 5830b57cec5SDimitry Andric typedef key_type value_type; 58481ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 58581ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 58681ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 5870b57cec5SDimitry Andric typedef value_type& reference; 5880b57cec5SDimitry Andric typedef const value_type& const_reference; 5890b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 59006c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 5910b57cec5SDimitry Andric 592bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value, 593bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 594bdd1243dSDimitry Andric "original allocator"); 595bdd1243dSDimitry Andric 5960b57cec5SDimitry Andricprivate: 5970b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 5980b57cec5SDimitry Andric 5990b57cec5SDimitry Andric __table __table_; 6000b57cec5SDimitry Andric 6010b57cec5SDimitry Andricpublic: 6020b57cec5SDimitry Andric typedef typename __table::pointer pointer; 6030b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 6040b57cec5SDimitry Andric typedef typename __table::size_type size_type; 6050b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 6060b57cec5SDimitry Andric 6070b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 6080b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 6090b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 6100b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 6110b57cec5SDimitry Andric 61206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 6130b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 6140b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 6150b57cec5SDimitry Andric#endif 6160b57cec5SDimitry Andric 6170b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 6180b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 6190b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 6200b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 6210b57cec5SDimitry Andric 622*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 623*cb14a3feSDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI 624*cb14a3feSDimitry Andric unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 62506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 626*cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a) 6270b57cec5SDimitry Andric : unordered_set(__n, hasher(), key_equal(), __a) {} 628*cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 6290b57cec5SDimitry Andric : unordered_set(__n, __hf, key_equal(), __a) {} 6300b57cec5SDimitry Andric#endif 631*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 632*cb14a3feSDimitry Andric unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 6330b57cec5SDimitry Andric template <class _InputIterator> 63406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last); 6350b57cec5SDimitry Andric template <class _InputIterator> 636*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 637*cb14a3feSDimitry Andric unordered_set(_InputIterator __first, 638*cb14a3feSDimitry Andric _InputIterator __last, 639*cb14a3feSDimitry Andric size_type __n, 640*cb14a3feSDimitry Andric const hasher& __hf = hasher(), 6410b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 6420b57cec5SDimitry Andric template <class _InputIterator> 643*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 644*cb14a3feSDimitry Andric _InputIterator __first, 645*cb14a3feSDimitry Andric _InputIterator __last, 646*cb14a3feSDimitry Andric size_type __n, 647*cb14a3feSDimitry Andric const hasher& __hf, 648*cb14a3feSDimitry Andric const key_equal& __eql, 6490b57cec5SDimitry Andric const allocator_type& __a); 65006c3fb27SDimitry Andric 65106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 65206c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 653*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 654*cb14a3feSDimitry Andric from_range_t, 655*cb14a3feSDimitry Andric _Range&& __range, 656*cb14a3feSDimitry Andric size_type __n = /*implementation-defined*/ 0, 657*cb14a3feSDimitry Andric const hasher& __hf = hasher(), 658*cb14a3feSDimitry Andric const key_equal& __eql = key_equal(), 65906c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 66006c3fb27SDimitry Andric : __table_(__hf, __eql, __a) { 66106c3fb27SDimitry Andric if (__n > 0) { 66206c3fb27SDimitry Andric __table_.__rehash_unique(__n); 66306c3fb27SDimitry Andric } 66406c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 66506c3fb27SDimitry Andric } 66606c3fb27SDimitry Andric#endif 66706c3fb27SDimitry Andric 66806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 6690b57cec5SDimitry Andric template <class _InputIterator> 6705f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 671*cb14a3feSDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 6720b57cec5SDimitry Andric : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 6730b57cec5SDimitry Andric template <class _InputIterator> 674*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 675*cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 6760b57cec5SDimitry Andric : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 6770b57cec5SDimitry Andric#endif 67806c3fb27SDimitry Andric 67906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 68006c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 681*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 68206c3fb27SDimitry Andric : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 68306c3fb27SDimitry Andric 68406c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 68506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 68606c3fb27SDimitry Andric unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 68706c3fb27SDimitry Andric : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 68806c3fb27SDimitry Andric#endif 68906c3fb27SDimitry Andric 690*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a); 69106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u); 69206c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a); 6930b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 694*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 69506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a); 69606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il); 697*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI 698*cb14a3feSDimitry Andric unordered_set(initializer_list<value_type> __il, 699*cb14a3feSDimitry Andric size_type __n, 7000b57cec5SDimitry Andric const hasher& __hf = hasher(), 7010b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 702*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set( 703*cb14a3feSDimitry Andric initializer_list<value_type> __il, 704*cb14a3feSDimitry Andric size_type __n, 705*cb14a3feSDimitry Andric const hasher& __hf, 706*cb14a3feSDimitry Andric const key_equal& __eql, 7070b57cec5SDimitry Andric const allocator_type& __a); 70806c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 14 7095f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 710*cb14a3feSDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 7110b57cec5SDimitry Andric : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 7125f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 713*cb14a3feSDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 7140b57cec5SDimitry Andric : unordered_set(__il, __n, __hf, key_equal(), __a) {} 7150b57cec5SDimitry Andric# endif 7160b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 717*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~unordered_set() { 718bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 7190b57cec5SDimitry Andric } 7200b57cec5SDimitry Andric 721*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) { 7220b57cec5SDimitry Andric __table_ = __u.__table_; 7230b57cec5SDimitry Andric return *this; 7240b57cec5SDimitry Andric } 7250b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 726*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u) 7270b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 728*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il); 7290b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7300b57cec5SDimitry Andric 731*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 732*cb14a3feSDimitry Andric return allocator_type(__table_.__node_alloc()); 733*cb14a3feSDimitry Andric } 7340b57cec5SDimitry Andric 735*cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 736*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 737*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 7380b57cec5SDimitry Andric 739*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 740*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 741*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 742*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 743*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 744*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 7450b57cec5SDimitry Andric 7460b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 7470b57cec5SDimitry Andric template <class... _Args> 748*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 749*cb14a3feSDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...); 750*cb14a3feSDimitry Andric } 7510b57cec5SDimitry Andric template <class... _Args> 752*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) { 75381ad6265SDimitry Andric return __table_.__emplace_unique(std::forward<_Args>(__args)...).first; 7540b57cec5SDimitry Andric } 7550b57cec5SDimitry Andric 756*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) { 757*cb14a3feSDimitry Andric return __table_.__insert_unique(std::move(__x)); 7580b57cec5SDimitry Andric } 759*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; } 76081ad6265SDimitry Andric 761*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 7620b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 763*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); } 7640b57cec5SDimitry Andric 765*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 7660b57cec5SDimitry Andric template <class _InputIterator> 767*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 7680b57cec5SDimitry Andric 76906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 77006c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 771*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 77206c3fb27SDimitry Andric for (auto&& __element : __range) { 77306c3fb27SDimitry Andric __table_.__insert_unique(std::forward<decltype(__element)>(__element)); 77406c3fb27SDimitry Andric } 77506c3fb27SDimitry Andric } 77606c3fb27SDimitry Andric#endif 77706c3fb27SDimitry Andric 778*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 779*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 780*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 781*cb14a3feSDimitry Andric return __table_.erase(__first, __last); 782*cb14a3feSDimitry Andric } 783*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 7840b57cec5SDimitry Andric 78506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 786*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 78706c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 7880b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 789*cb14a3feSDimitry Andric return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 7900b57cec5SDimitry Andric } 791*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) { 79206c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 7930b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 794*cb14a3feSDimitry Andric return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh)); 7950b57cec5SDimitry Andric } 796*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 7970b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 7980b57cec5SDimitry Andric } 799*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 8000b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__it); 8010b57cec5SDimitry Andric } 8020b57cec5SDimitry Andric 8030b57cec5SDimitry Andric template <class _H2, class _P2> 804*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 805*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 806*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8070b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8080b57cec5SDimitry Andric } 8090b57cec5SDimitry Andric template <class _H2, class _P2> 810*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 811*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 812*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8130b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8140b57cec5SDimitry Andric } 8150b57cec5SDimitry Andric template <class _H2, class _P2> 816*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 817*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 818*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8190b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8200b57cec5SDimitry Andric } 8210b57cec5SDimitry Andric template <class _H2, class _P2> 822*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 823*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 824*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8250b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 8260b57cec5SDimitry Andric } 8270b57cec5SDimitry Andric#endif 8280b57cec5SDimitry Andric 829*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 830*cb14a3feSDimitry Andric __table_.swap(__u.__table_); 831*cb14a3feSDimitry Andric } 8320b57cec5SDimitry Andric 833*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 834*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 8350b57cec5SDimitry Andric 836*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 837*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 83806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 839*cb14a3feSDimitry Andric template <class _K2, 840*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 841*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 842*cb14a3feSDimitry Andric return __table_.find(__k); 843*cb14a3feSDimitry Andric } 844*cb14a3feSDimitry Andric template <class _K2, 845*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 846*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 847*cb14a3feSDimitry Andric return __table_.find(__k); 848*cb14a3feSDimitry Andric } 84906c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 850349cc55cSDimitry Andric 851*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 85206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 853*cb14a3feSDimitry Andric template <class _K2, 854*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 855*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 856*cb14a3feSDimitry Andric return __table_.__count_unique(__k); 857*cb14a3feSDimitry Andric } 85806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 859349cc55cSDimitry Andric 86006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 861*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 862e8d8bef9SDimitry Andric 863*cb14a3feSDimitry Andric template <class _K2, 864*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 865*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 866*cb14a3feSDimitry Andric return find(__k) != end(); 867*cb14a3feSDimitry Andric } 86806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 869349cc55cSDimitry Andric 870*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 871*cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 872*cb14a3feSDimitry Andric } 873*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 874*cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 875*cb14a3feSDimitry Andric } 87606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 877*cb14a3feSDimitry Andric template <class _K2, 878*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 879*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 880*cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 881*cb14a3feSDimitry Andric } 882*cb14a3feSDimitry Andric template <class _K2, 883*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 884*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 885*cb14a3feSDimitry Andric return __table_.__equal_range_unique(__k); 886*cb14a3feSDimitry Andric } 88706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 8880b57cec5SDimitry Andric 889*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 890*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 8910b57cec5SDimitry Andric 892*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 893*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 8940b57cec5SDimitry Andric 895*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 896*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 897*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 898*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 899*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 900*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 9010b57cec5SDimitry Andric 902*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 903*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 904*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 905*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); } 906*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); } 9070b57cec5SDimitry Andric}; 9080b57cec5SDimitry Andric 909349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 9100b57cec5SDimitry Andrictemplate <class _InputIterator, 9110b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 9120b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 9130b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 91406c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 915349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 916349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 917349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 918349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 919*cb14a3feSDimitry Andricunordered_set(_InputIterator, 920*cb14a3feSDimitry Andric _InputIterator, 921*cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 922*cb14a3feSDimitry Andric _Hash = _Hash(), 923*cb14a3feSDimitry Andric _Pred = _Pred(), 924*cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 9250b57cec5SDimitry Andric 92606c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 92706c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 92806c3fb27SDimitry Andric class _Hash = hash<ranges::range_value_t<_Range>>, 92906c3fb27SDimitry Andric class _Pred = equal_to<ranges::range_value_t<_Range>>, 93006c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 93106c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 93206c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 93306c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 93406c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 935*cb14a3feSDimitry Andricunordered_set(from_range_t, 936*cb14a3feSDimitry Andric _Range&&, 937*cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 938*cb14a3feSDimitry Andric _Hash = _Hash(), 939*cb14a3feSDimitry Andric _Pred = _Pred(), 940*cb14a3feSDimitry Andric _Allocator = _Allocator()) 94106c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 94206c3fb27SDimitry Andric# endif 94306c3fb27SDimitry Andric 944*cb14a3feSDimitry Andrictemplate <class _Tp, 945*cb14a3feSDimitry Andric class _Hash = hash<_Tp>, 9460b57cec5SDimitry Andric class _Pred = equal_to<_Tp>, 9470b57cec5SDimitry Andric class _Allocator = allocator<_Tp>, 948349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 949349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 950349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 951349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 952*cb14a3feSDimitry Andricunordered_set(initializer_list<_Tp>, 953*cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 954*cb14a3feSDimitry Andric _Hash = _Hash(), 955*cb14a3feSDimitry Andric _Pred = _Pred(), 956*cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 9570b57cec5SDimitry Andric 958*cb14a3feSDimitry Andrictemplate <class _InputIterator, 959*cb14a3feSDimitry Andric class _Allocator, 96006c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 961349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 962*cb14a3feSDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 9630b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, 9640b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 9650b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 9660b57cec5SDimitry Andric _Allocator>; 9670b57cec5SDimitry Andric 968*cb14a3feSDimitry Andrictemplate <class _InputIterator, 969*cb14a3feSDimitry Andric class _Hash, 970*cb14a3feSDimitry Andric class _Allocator, 97106c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 972349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 973349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 974349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 975*cb14a3feSDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 976*cb14a3feSDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>; 9770b57cec5SDimitry Andric 97806c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 97906c3fb27SDimitry Andric 980*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 98106c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 982*cb14a3feSDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, 983*cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 984*cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 985*cb14a3feSDimitry Andric _Allocator>; 98606c3fb27SDimitry Andric 987*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 98806c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, _Allocator) 989*cb14a3feSDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, 990*cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 991*cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 992*cb14a3feSDimitry Andric _Allocator>; 99306c3fb27SDimitry Andric 994*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 995*cb14a3feSDimitry Andric class _Hash, 996*cb14a3feSDimitry Andric class _Allocator, 99706c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 99806c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 99906c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 100006c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 100106c3fb27SDimitry Andric -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 100206c3fb27SDimitry Andric 100306c3fb27SDimitry Andric# endif 100406c3fb27SDimitry Andric 1005*cb14a3feSDimitry Andrictemplate <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 10060b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 10070b57cec5SDimitry Andric -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 10080b57cec5SDimitry Andric 1009*cb14a3feSDimitry Andrictemplate <class _Tp, 1010*cb14a3feSDimitry Andric class _Hash, 1011*cb14a3feSDimitry Andric class _Allocator, 1012349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1013349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1014349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 10150b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 10160b57cec5SDimitry Andric -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 10170b57cec5SDimitry Andric#endif 10180b57cec5SDimitry Andric 10190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1020*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql) 1021*cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1022753f127fSDimitry Andric __table_.__rehash_unique(__n); 10230b57cec5SDimitry Andric} 10240b57cec5SDimitry Andric 10250b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1026*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1027*cb14a3feSDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1028*cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1029753f127fSDimitry Andric __table_.__rehash_unique(__n); 10300b57cec5SDimitry Andric} 10310b57cec5SDimitry Andric 10320b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10330b57cec5SDimitry Andrictemplate <class _InputIterator> 1034*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) { 10350b57cec5SDimitry Andric insert(__first, __last); 10360b57cec5SDimitry Andric} 10370b57cec5SDimitry Andric 10380b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10390b57cec5SDimitry Andrictemplate <class _InputIterator> 10400b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1041*cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1042*cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1043753f127fSDimitry Andric __table_.__rehash_unique(__n); 10440b57cec5SDimitry Andric insert(__first, __last); 10450b57cec5SDimitry Andric} 10460b57cec5SDimitry Andric 10470b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10480b57cec5SDimitry Andrictemplate <class _InputIterator> 10490b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1050*cb14a3feSDimitry Andric _InputIterator __first, 1051*cb14a3feSDimitry Andric _InputIterator __last, 1052*cb14a3feSDimitry Andric size_type __n, 1053*cb14a3feSDimitry Andric const hasher& __hf, 1054*cb14a3feSDimitry Andric const key_equal& __eql, 10550b57cec5SDimitry Andric const allocator_type& __a) 1056*cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1057*cb14a3feSDimitry Andric __table_.__rehash_unique(__n); 1058*cb14a3feSDimitry Andric insert(__first, __last); 10590b57cec5SDimitry Andric} 10600b57cec5SDimitry Andric 10610b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1062*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {} 1063*cb14a3feSDimitry Andric 1064*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1065*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) { 1066753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 10670b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 10680b57cec5SDimitry Andric} 10690b57cec5SDimitry Andric 10700b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1071*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a) 1072*cb14a3feSDimitry Andric : __table_(__u.__table_, __a) { 1073753f127fSDimitry Andric __table_.__rehash_unique(__u.bucket_count()); 10740b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 10750b57cec5SDimitry Andric} 10760b57cec5SDimitry Andric 10770b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 10780b57cec5SDimitry Andric 10790b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1080*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u) 10810b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1082*cb14a3feSDimitry Andric : __table_(std::move(__u.__table_)) {} 10830b57cec5SDimitry Andric 10840b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1085*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a) 1086*cb14a3feSDimitry Andric : __table_(std::move(__u.__table_), __a) { 1087*cb14a3feSDimitry Andric if (__a != __u.get_allocator()) { 10880b57cec5SDimitry Andric iterator __i = __u.begin(); 10890b57cec5SDimitry Andric while (__u.size() != 0) 10905f757f3fSDimitry Andric __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value())); 10910b57cec5SDimitry Andric } 10920b57cec5SDimitry Andric} 10930b57cec5SDimitry Andric 10940b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1095*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) { 10960b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 10970b57cec5SDimitry Andric} 10980b57cec5SDimitry Andric 10990b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11000b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1101*cb14a3feSDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1102*cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1103753f127fSDimitry Andric __table_.__rehash_unique(__n); 11040b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11050b57cec5SDimitry Andric} 11060b57cec5SDimitry Andric 11070b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11080b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 1109*cb14a3feSDimitry Andric initializer_list<value_type> __il, 1110*cb14a3feSDimitry Andric size_type __n, 1111*cb14a3feSDimitry Andric const hasher& __hf, 1112*cb14a3feSDimitry Andric const key_equal& __eql, 1113*cb14a3feSDimitry Andric const allocator_type& __a) 1114*cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1115753f127fSDimitry Andric __table_.__rehash_unique(__n); 11160b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11170b57cec5SDimitry Andric} 11180b57cec5SDimitry Andric 11190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1120*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>& 11210b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 1122*cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 11235f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 11240b57cec5SDimitry Andric return *this; 11250b57cec5SDimitry Andric} 11260b57cec5SDimitry Andric 11270b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1128*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>& 1129*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 11300b57cec5SDimitry Andric __table_.__assign_unique(__il.begin(), __il.end()); 11310b57cec5SDimitry Andric return *this; 11320b57cec5SDimitry Andric} 11330b57cec5SDimitry Andric 11340b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 11350b57cec5SDimitry Andric 11360b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 11370b57cec5SDimitry Andrictemplate <class _InputIterator> 1138*cb14a3feSDimitry Andricinline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 11390b57cec5SDimitry Andric for (; __first != __last; ++__first) 11400b57cec5SDimitry Andric __table_.__insert_unique(*__first); 11410b57cec5SDimitry Andric} 11420b57cec5SDimitry Andric 11430b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1144*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 1145*cb14a3feSDimitry Andricswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1146*cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 11470b57cec5SDimitry Andric __x.swap(__y); 11480b57cec5SDimitry Andric} 11490b57cec5SDimitry Andric 115006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1151*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1152*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 1153*cb14a3feSDimitry Andricerase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 11545f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 11555ffd83dbSDimitry Andric} 11560b57cec5SDimitry Andric#endif 11570b57cec5SDimitry Andric 11580b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1159*cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1160*cb14a3feSDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 11610b57cec5SDimitry Andric if (__x.size() != __y.size()) 11620b57cec5SDimitry Andric return false; 1163*cb14a3feSDimitry Andric typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 1164*cb14a3feSDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 11650b57cec5SDimitry Andric const_iterator __j = __y.find(*__i); 11660b57cec5SDimitry Andric if (__j == __ey || !(*__i == *__j)) 11670b57cec5SDimitry Andric return false; 11680b57cec5SDimitry Andric } 11690b57cec5SDimitry Andric return true; 11700b57cec5SDimitry Andric} 11710b57cec5SDimitry Andric 117206c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 117306c3fb27SDimitry Andric 11740b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1175*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1176*cb14a3feSDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) { 11770b57cec5SDimitry Andric return !(__x == __y); 11780b57cec5SDimitry Andric} 11790b57cec5SDimitry Andric 118006c3fb27SDimitry Andric#endif 118106c3fb27SDimitry Andric 1182*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> > 1183*cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multiset { 11840b57cec5SDimitry Andricpublic: 11850b57cec5SDimitry Andric // types 11860b57cec5SDimitry Andric typedef _Value key_type; 11870b57cec5SDimitry Andric typedef key_type value_type; 118881ad6265SDimitry Andric typedef __type_identity_t<_Hash> hasher; 118981ad6265SDimitry Andric typedef __type_identity_t<_Pred> key_equal; 119081ad6265SDimitry Andric typedef __type_identity_t<_Alloc> allocator_type; 11910b57cec5SDimitry Andric typedef value_type& reference; 11920b57cec5SDimitry Andric typedef const value_type& const_reference; 11930b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 119406c3fb27SDimitry Andric "Allocator::value_type must be same type as value_type"); 11950b57cec5SDimitry Andric 11960b57cec5SDimitry Andricprivate: 11970b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 11980b57cec5SDimitry Andric 11990b57cec5SDimitry Andric __table __table_; 12000b57cec5SDimitry Andric 12010b57cec5SDimitry Andricpublic: 12020b57cec5SDimitry Andric typedef typename __table::pointer pointer; 12030b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 12040b57cec5SDimitry Andric typedef typename __table::size_type size_type; 12050b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 12060b57cec5SDimitry Andric 12070b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 12080b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 12090b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 12100b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 12110b57cec5SDimitry Andric 121206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 12130b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 12140b57cec5SDimitry Andric#endif 12150b57cec5SDimitry Andric 12160b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 12170b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 12180b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 12190b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 12200b57cec5SDimitry Andric 1221*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {} 1222*cb14a3feSDimitry Andric explicit _LIBCPP_HIDE_FROM_ABI 1223*cb14a3feSDimitry Andric unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 12245f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1225*cb14a3feSDimitry Andric unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 122606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 1227*cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a) 12280b57cec5SDimitry Andric : unordered_multiset(__n, hasher(), key_equal(), __a) {} 1229*cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 12300b57cec5SDimitry Andric : unordered_multiset(__n, __hf, key_equal(), __a) {} 12310b57cec5SDimitry Andric#endif 12320b57cec5SDimitry Andric template <class _InputIterator> 123306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last); 12340b57cec5SDimitry Andric template <class _InputIterator> 1235*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1236*cb14a3feSDimitry Andric _InputIterator __first, 1237*cb14a3feSDimitry Andric _InputIterator __last, 1238*cb14a3feSDimitry Andric size_type __n, 1239*cb14a3feSDimitry Andric const hasher& __hf = hasher(), 12400b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 12410b57cec5SDimitry Andric template <class _InputIterator> 1242*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1243*cb14a3feSDimitry Andric _InputIterator __first, 1244*cb14a3feSDimitry Andric _InputIterator __last, 1245*cb14a3feSDimitry Andric size_type __n, 1246*cb14a3feSDimitry Andric const hasher& __hf, 1247*cb14a3feSDimitry Andric const key_equal& __eql, 1248*cb14a3feSDimitry Andric const allocator_type& __a); 124906c3fb27SDimitry Andric 125006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 125106c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1252*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1253*cb14a3feSDimitry Andric from_range_t, 1254*cb14a3feSDimitry Andric _Range&& __range, 1255*cb14a3feSDimitry Andric size_type __n = /*implementation-defined*/ 0, 1256*cb14a3feSDimitry Andric const hasher& __hf = hasher(), 1257*cb14a3feSDimitry Andric const key_equal& __eql = key_equal(), 125806c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 125906c3fb27SDimitry Andric : __table_(__hf, __eql, __a) { 126006c3fb27SDimitry Andric if (__n > 0) { 126106c3fb27SDimitry Andric __table_.__rehash_multi(__n); 126206c3fb27SDimitry Andric } 126306c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 126406c3fb27SDimitry Andric } 126506c3fb27SDimitry Andric#endif 126606c3fb27SDimitry Andric 126706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 12680b57cec5SDimitry Andric template <class _InputIterator> 12695f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 1270*cb14a3feSDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 12710b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 12720b57cec5SDimitry Andric template <class _InputIterator> 1273*cb14a3feSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1274*cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a) 12750b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 12760b57cec5SDimitry Andric#endif 127706c3fb27SDimitry Andric 127806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 127906c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1280*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a) 128106c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {} 128206c3fb27SDimitry Andric 128306c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 128406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 128506c3fb27SDimitry Andric unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a) 128606c3fb27SDimitry Andric : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {} 128706c3fb27SDimitry Andric#endif 128806c3fb27SDimitry Andric 1289*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a); 129006c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u); 129106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 12920b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1293*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u) 12940b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 129506c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 129606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il); 1297*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1298*cb14a3feSDimitry Andric initializer_list<value_type> __il, 1299*cb14a3feSDimitry Andric size_type __n, 13000b57cec5SDimitry Andric const hasher& __hf = hasher(), 13010b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 1302*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset( 1303*cb14a3feSDimitry Andric initializer_list<value_type> __il, 1304*cb14a3feSDimitry Andric size_type __n, 1305*cb14a3feSDimitry Andric const hasher& __hf, 1306*cb14a3feSDimitry Andric const key_equal& __eql, 13070b57cec5SDimitry Andric const allocator_type& __a); 130806c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 14 13095f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13100b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 13110b57cec5SDimitry Andric : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 13125f757f3fSDimitry Andric inline _LIBCPP_HIDE_FROM_ABI 13130b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 13140b57cec5SDimitry Andric : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 13150b57cec5SDimitry Andric# endif 13160b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 1317*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() { 1318bdd1243dSDimitry Andric static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 13190b57cec5SDimitry Andric } 13200b57cec5SDimitry Andric 1321*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) { 13220b57cec5SDimitry Andric __table_ = __u.__table_; 13230b57cec5SDimitry Andric return *this; 13240b57cec5SDimitry Andric } 13250b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1326*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u) 13270b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 132806c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il); 13290b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 13300b57cec5SDimitry Andric 1331*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { 1332*cb14a3feSDimitry Andric return allocator_type(__table_.__node_alloc()); 1333*cb14a3feSDimitry Andric } 13340b57cec5SDimitry Andric 1335*cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; } 1336*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); } 1337*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); } 13380b57cec5SDimitry Andric 1339*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); } 1340*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); } 1341*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); } 1342*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); } 1343*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); } 1344*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); } 13450b57cec5SDimitry Andric 13460b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 13470b57cec5SDimitry Andric template <class... _Args> 1348*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1349*cb14a3feSDimitry Andric return __table_.__emplace_multi(std::forward<_Args>(__args)...); 1350*cb14a3feSDimitry Andric } 13510b57cec5SDimitry Andric template <class... _Args> 1352*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1353*cb14a3feSDimitry Andric return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...); 1354*cb14a3feSDimitry Andric } 13550b57cec5SDimitry Andric 1356*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); } 1357*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) { 1358*cb14a3feSDimitry Andric return __table_.__insert_multi(__p, std::move(__x)); 1359*cb14a3feSDimitry Andric } 1360*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 13610b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 13620b57cec5SDimitry Andric 1363*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 13640b57cec5SDimitry Andric 1365*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) { 1366*cb14a3feSDimitry Andric return __table_.__insert_multi(__p, __x); 1367*cb14a3feSDimitry Andric } 13680b57cec5SDimitry Andric 13690b57cec5SDimitry Andric template <class _InputIterator> 1370*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 13710b57cec5SDimitry Andric 137206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 137306c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1374*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 137506c3fb27SDimitry Andric for (auto&& __element : __range) { 137606c3fb27SDimitry Andric __table_.__insert_multi(std::forward<decltype(__element)>(__element)); 137706c3fb27SDimitry Andric } 137806c3fb27SDimitry Andric } 137906c3fb27SDimitry Andric#endif 138006c3fb27SDimitry Andric 138106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1382*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 138306c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 13840b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1385*cb14a3feSDimitry Andric return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 13860b57cec5SDimitry Andric } 1387*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 138806c3fb27SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 13890b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 1390*cb14a3feSDimitry Andric return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh)); 13910b57cec5SDimitry Andric } 1392*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) { 1393*cb14a3feSDimitry Andric return __table_.template __node_handle_extract<node_type>(__position); 13940b57cec5SDimitry Andric } 1395*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 13960b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 13970b57cec5SDimitry Andric } 13980b57cec5SDimitry Andric 13990b57cec5SDimitry Andric template <class _H2, class _P2> 1400*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) { 1401*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1402*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14030b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14040b57cec5SDimitry Andric } 14050b57cec5SDimitry Andric template <class _H2, class _P2> 1406*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) { 1407*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1408*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14090b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14100b57cec5SDimitry Andric } 14110b57cec5SDimitry Andric template <class _H2, class _P2> 1412*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) { 1413*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1414*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14150b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14160b57cec5SDimitry Andric } 14170b57cec5SDimitry Andric template <class _H2, class _P2> 1418*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) { 1419*cb14a3feSDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1420*cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 14210b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 14220b57cec5SDimitry Andric } 14230b57cec5SDimitry Andric#endif 14240b57cec5SDimitry Andric 1425*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); } 1426*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 1427*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) { 1428*cb14a3feSDimitry Andric return __table_.erase(__first, __last); 1429*cb14a3feSDimitry Andric } 1430*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); } 14310b57cec5SDimitry Andric 1432*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) { 1433*cb14a3feSDimitry Andric __table_.swap(__u.__table_); 1434*cb14a3feSDimitry Andric } 14350b57cec5SDimitry Andric 1436*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); } 1437*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } 14380b57cec5SDimitry Andric 1439*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 1440*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 144106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1442*cb14a3feSDimitry Andric template <class _K2, 1443*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1444*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1445*cb14a3feSDimitry Andric return __table_.find(__k); 1446*cb14a3feSDimitry Andric } 1447*cb14a3feSDimitry Andric template <class _K2, 1448*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1449*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1450*cb14a3feSDimitry Andric return __table_.find(__k); 1451*cb14a3feSDimitry Andric } 145206c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1453349cc55cSDimitry Andric 1454*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 145506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1456*cb14a3feSDimitry Andric template <class _K2, 1457*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1458*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1459*cb14a3feSDimitry Andric return __table_.__count_multi(__k); 1460*cb14a3feSDimitry Andric } 146106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1462349cc55cSDimitry Andric 146306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1464*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 1465e8d8bef9SDimitry Andric 1466*cb14a3feSDimitry Andric template <class _K2, 1467*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1468*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1469*cb14a3feSDimitry Andric return find(__k) != end(); 1470*cb14a3feSDimitry Andric } 147106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 1472349cc55cSDimitry Andric 1473*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1474*cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1475*cb14a3feSDimitry Andric } 1476*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1477*cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1478*cb14a3feSDimitry Andric } 147906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1480*cb14a3feSDimitry Andric template <class _K2, 1481*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1482*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1483*cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1484*cb14a3feSDimitry Andric } 1485*cb14a3feSDimitry Andric template <class _K2, 1486*cb14a3feSDimitry Andric enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr> 1487*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1488*cb14a3feSDimitry Andric return __table_.__equal_range_multi(__k); 1489*cb14a3feSDimitry Andric } 149006c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 14910b57cec5SDimitry Andric 1492*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); } 1493*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); } 14940b57cec5SDimitry Andric 1495*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); } 1496*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); } 14970b57cec5SDimitry Andric 1498*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); } 1499*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); } 1500*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); } 1501*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); } 1502*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); } 1503*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); } 15040b57cec5SDimitry Andric 1505*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); } 1506*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); } 1507*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); } 1508*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); } 1509*cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); } 15100b57cec5SDimitry Andric}; 15110b57cec5SDimitry Andric 1512349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 15130b57cec5SDimitry Andrictemplate <class _InputIterator, 15140b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 15150b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 15160b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 151706c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1518349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1519349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1520349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1521349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1522*cb14a3feSDimitry Andricunordered_multiset( 1523*cb14a3feSDimitry Andric _InputIterator, 1524*cb14a3feSDimitry Andric _InputIterator, 1525*cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1526*cb14a3feSDimitry Andric _Hash = _Hash(), 1527*cb14a3feSDimitry Andric _Pred = _Pred(), 1528*cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 15290b57cec5SDimitry Andric 153006c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 153106c3fb27SDimitry Andrictemplate <ranges::input_range _Range, 153206c3fb27SDimitry Andric class _Hash = hash<ranges::range_value_t<_Range>>, 153306c3fb27SDimitry Andric class _Pred = equal_to<ranges::range_value_t<_Range>>, 153406c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 153506c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 153606c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 153706c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 153806c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1539*cb14a3feSDimitry Andricunordered_multiset( 1540*cb14a3feSDimitry Andric from_range_t, 1541*cb14a3feSDimitry Andric _Range&&, 1542*cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1543*cb14a3feSDimitry Andric _Hash = _Hash(), 1544*cb14a3feSDimitry Andric _Pred = _Pred(), 1545*cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23 154606c3fb27SDimitry Andric# endif 154706c3fb27SDimitry Andric 1548*cb14a3feSDimitry Andrictemplate <class _Tp, 1549*cb14a3feSDimitry Andric class _Hash = hash<_Tp>, 1550*cb14a3feSDimitry Andric class _Pred = equal_to<_Tp>, 1551*cb14a3feSDimitry Andric class _Allocator = allocator<_Tp>, 1552349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1553349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1554349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Pred>::value>, 1555349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1556*cb14a3feSDimitry Andricunordered_multiset(initializer_list<_Tp>, 1557*cb14a3feSDimitry Andric typename allocator_traits<_Allocator>::size_type = 0, 1558*cb14a3feSDimitry Andric _Hash = _Hash(), 1559*cb14a3feSDimitry Andric _Pred = _Pred(), 1560*cb14a3feSDimitry Andric _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 15610b57cec5SDimitry Andric 1562*cb14a3feSDimitry Andrictemplate <class _InputIterator, 1563*cb14a3feSDimitry Andric class _Allocator, 156406c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1565349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 15660b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 15670b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, 15680b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 15690b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 15700b57cec5SDimitry Andric _Allocator>; 15710b57cec5SDimitry Andric 1572*cb14a3feSDimitry Andrictemplate <class _InputIterator, 1573*cb14a3feSDimitry Andric class _Hash, 1574*cb14a3feSDimitry Andric class _Allocator, 157506c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>, 1576349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1577349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1578349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 1579*cb14a3feSDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 1580*cb14a3feSDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, 1581*cb14a3feSDimitry Andric _Hash, 15820b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 15830b57cec5SDimitry Andric _Allocator>; 15840b57cec5SDimitry Andric 158506c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 158606c3fb27SDimitry Andric 1587*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 158806c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator) 1589*cb14a3feSDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, 1590*cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 1591*cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 1592*cb14a3feSDimitry Andric _Allocator>; 159306c3fb27SDimitry Andric 1594*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 159506c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, _Allocator) 1596*cb14a3feSDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, 1597*cb14a3feSDimitry Andric hash<ranges::range_value_t<_Range>>, 1598*cb14a3feSDimitry Andric equal_to<ranges::range_value_t<_Range>>, 1599*cb14a3feSDimitry Andric _Allocator>; 160006c3fb27SDimitry Andric 1601*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 1602*cb14a3feSDimitry Andric class _Hash, 1603*cb14a3feSDimitry Andric class _Allocator, 160406c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 160506c3fb27SDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 160606c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 160706c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 160806c3fb27SDimitry Andric -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>; 160906c3fb27SDimitry Andric 161006c3fb27SDimitry Andric# endif 161106c3fb27SDimitry Andric 1612*cb14a3feSDimitry Andrictemplate <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>> 16130b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 16140b57cec5SDimitry Andric -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 16150b57cec5SDimitry Andric 1616*cb14a3feSDimitry Andrictemplate <class _Tp, 1617*cb14a3feSDimitry Andric class _Hash, 1618*cb14a3feSDimitry Andric class _Allocator, 1619349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Hash>::value>, 1620349cc55cSDimitry Andric class = enable_if_t<!is_integral<_Hash>::value>, 1621349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value>> 16220b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 16230b57cec5SDimitry Andric -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 16240b57cec5SDimitry Andric#endif 16250b57cec5SDimitry Andric 16260b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16270b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16280b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql) 1629*cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1630753f127fSDimitry Andric __table_.__rehash_multi(__n); 16310b57cec5SDimitry Andric} 16320b57cec5SDimitry Andric 16330b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16340b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1635*cb14a3feSDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1636*cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1637*cb14a3feSDimitry Andric __table_.__rehash_multi(__n); 1638*cb14a3feSDimitry Andric} 1639*cb14a3feSDimitry Andric 1640*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1641*cb14a3feSDimitry Andrictemplate <class _InputIterator> 1642*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) { 1643*cb14a3feSDimitry Andric insert(__first, __last); 1644*cb14a3feSDimitry Andric} 1645*cb14a3feSDimitry Andric 1646*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1647*cb14a3feSDimitry Andrictemplate <class _InputIterator> 1648*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1649*cb14a3feSDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 1650*cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1651*cb14a3feSDimitry Andric __table_.__rehash_multi(__n); 1652*cb14a3feSDimitry Andric insert(__first, __last); 1653*cb14a3feSDimitry Andric} 1654*cb14a3feSDimitry Andric 1655*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1656*cb14a3feSDimitry Andrictemplate <class _InputIterator> 1657*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1658*cb14a3feSDimitry Andric _InputIterator __first, 1659*cb14a3feSDimitry Andric _InputIterator __last, 1660*cb14a3feSDimitry Andric size_type __n, 1661*cb14a3feSDimitry Andric const hasher& __hf, 1662*cb14a3feSDimitry Andric const key_equal& __eql, 16630b57cec5SDimitry Andric const allocator_type& __a) 1664*cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1665753f127fSDimitry Andric __table_.__rehash_multi(__n); 16660b57cec5SDimitry Andric insert(__first, __last); 16670b57cec5SDimitry Andric} 16680b57cec5SDimitry Andric 16690b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1670*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a) 1671*cb14a3feSDimitry Andric : __table_(__a) {} 16720b57cec5SDimitry Andric 16730b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1674*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u) 1675*cb14a3feSDimitry Andric : __table_(__u.__table_) { 1676753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 16770b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16780b57cec5SDimitry Andric} 16790b57cec5SDimitry Andric 16800b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16810b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16820b57cec5SDimitry Andric const unordered_multiset& __u, const allocator_type& __a) 1683*cb14a3feSDimitry Andric : __table_(__u.__table_, __a) { 1684753f127fSDimitry Andric __table_.__rehash_multi(__u.bucket_count()); 16850b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16860b57cec5SDimitry Andric} 16870b57cec5SDimitry Andric 16880b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 16890b57cec5SDimitry Andric 16900b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1691*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u) 16920b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1693*cb14a3feSDimitry Andric : __table_(std::move(__u.__table_)) {} 16940b57cec5SDimitry Andric 16950b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16960b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16970b57cec5SDimitry Andric unordered_multiset&& __u, const allocator_type& __a) 1698*cb14a3feSDimitry Andric : __table_(std::move(__u.__table_), __a) { 1699*cb14a3feSDimitry Andric if (__a != __u.get_allocator()) { 17000b57cec5SDimitry Andric iterator __i = __u.begin(); 17010b57cec5SDimitry Andric while (__u.size() != 0) 17025f757f3fSDimitry Andric __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value())); 17030b57cec5SDimitry Andric } 17040b57cec5SDimitry Andric} 17050b57cec5SDimitry Andric 17060b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1707*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) { 17080b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17090b57cec5SDimitry Andric} 17100b57cec5SDimitry Andric 17110b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17120b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1713*cb14a3feSDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql) 1714*cb14a3feSDimitry Andric : __table_(__hf, __eql) { 1715753f127fSDimitry Andric __table_.__rehash_multi(__n); 17160b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17170b57cec5SDimitry Andric} 17180b57cec5SDimitry Andric 17190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17200b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 1721*cb14a3feSDimitry Andric initializer_list<value_type> __il, 1722*cb14a3feSDimitry Andric size_type __n, 1723*cb14a3feSDimitry Andric const hasher& __hf, 1724*cb14a3feSDimitry Andric const key_equal& __eql, 1725*cb14a3feSDimitry Andric const allocator_type& __a) 1726*cb14a3feSDimitry Andric : __table_(__hf, __eql, __a) { 1727753f127fSDimitry Andric __table_.__rehash_multi(__n); 17280b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 17290b57cec5SDimitry Andric} 17300b57cec5SDimitry Andric 17310b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1732*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1733*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u) 1734*cb14a3feSDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) { 17355f757f3fSDimitry Andric __table_ = std::move(__u.__table_); 17360b57cec5SDimitry Andric return *this; 17370b57cec5SDimitry Andric} 17380b57cec5SDimitry Andric 17390b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1740*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>& 1741*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) { 17420b57cec5SDimitry Andric __table_.__assign_multi(__il.begin(), __il.end()); 17430b57cec5SDimitry Andric return *this; 17440b57cec5SDimitry Andric} 17450b57cec5SDimitry Andric 17460b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 17470b57cec5SDimitry Andric 17480b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17490b57cec5SDimitry Andrictemplate <class _InputIterator> 1750*cb14a3feSDimitry Andricinline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 17510b57cec5SDimitry Andric for (; __first != __last; ++__first) 17520b57cec5SDimitry Andric __table_.__insert_multi(*__first); 17530b57cec5SDimitry Andric} 17540b57cec5SDimitry Andric 17550b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1756*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 1757*cb14a3feSDimitry Andricswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1758*cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 17590b57cec5SDimitry Andric __x.swap(__y); 17600b57cec5SDimitry Andric} 17610b57cec5SDimitry Andric 176206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1763*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> 1764*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 1765*cb14a3feSDimitry Andricerase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) { 17665f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 17675ffd83dbSDimitry Andric} 17680b57cec5SDimitry Andric#endif 17690b57cec5SDimitry Andric 17700b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1771*cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1772*cb14a3feSDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 17730b57cec5SDimitry Andric if (__x.size() != __y.size()) 17740b57cec5SDimitry Andric return false; 1775*cb14a3feSDimitry Andric typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 17760b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _EqRng; 1777*cb14a3feSDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 17780b57cec5SDimitry Andric _EqRng __xeq = __x.equal_range(*__i); 17790b57cec5SDimitry Andric _EqRng __yeq = __y.equal_range(*__i); 1780*cb14a3feSDimitry Andric if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 17815f757f3fSDimitry Andric !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 17820b57cec5SDimitry Andric return false; 17830b57cec5SDimitry Andric __i = __xeq.second; 17840b57cec5SDimitry Andric } 17850b57cec5SDimitry Andric return true; 17860b57cec5SDimitry Andric} 17870b57cec5SDimitry Andric 178806c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 178906c3fb27SDimitry Andric 17900b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 1791*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1792*cb14a3feSDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { 17930b57cec5SDimitry Andric return !(__x == __y); 17940b57cec5SDimitry Andric} 17950b57cec5SDimitry Andric 179606c3fb27SDimitry Andric#endif 179706c3fb27SDimitry Andric 17980b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 17990b57cec5SDimitry Andric 180006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1801bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 1802bdd1243dSDimitry Andricnamespace pmr { 1803bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 180406c3fb27SDimitry Andricusing unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1805bdd1243dSDimitry Andric 1806bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>> 1807*cb14a3feSDimitry Andricusing unordered_multiset _LIBCPP_AVAILABILITY_PMR = 1808*cb14a3feSDimitry Andric std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>; 1809bdd1243dSDimitry Andric} // namespace pmr 1810bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD 1811bdd1243dSDimitry Andric#endif 1812bdd1243dSDimitry Andric 1813bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1814bdd1243dSDimitry Andric# include <concepts> 181506c3fb27SDimitry Andric# include <cstdlib> 1816bdd1243dSDimitry Andric# include <functional> 1817bdd1243dSDimitry Andric# include <iterator> 18185f757f3fSDimitry Andric# include <stdexcept> 181906c3fb27SDimitry Andric# include <type_traits> 1820bdd1243dSDimitry Andric#endif 1821bdd1243dSDimitry Andric 18220b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_SET 1823