10b57cec5SDimitry Andric// -*- C++ -*- 20b57cec5SDimitry Andric//===-------------------------- unordered_set -----------------------------===// 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 130b57cec5SDimitry Andric/* 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric unordered_set synopsis 160b57cec5SDimitry Andric 170b57cec5SDimitry Andric#include <initializer_list> 180b57cec5SDimitry Andric 190b57cec5SDimitry Andricnamespace std 200b57cec5SDimitry Andric{ 210b57cec5SDimitry Andric 220b57cec5SDimitry Andrictemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 230b57cec5SDimitry Andric class Alloc = allocator<Value>> 240b57cec5SDimitry Andricclass unordered_set 250b57cec5SDimitry Andric{ 260b57cec5SDimitry Andricpublic: 270b57cec5SDimitry Andric // types 280b57cec5SDimitry Andric typedef Value key_type; 290b57cec5SDimitry Andric typedef key_type value_type; 300b57cec5SDimitry Andric typedef Hash hasher; 310b57cec5SDimitry Andric typedef Pred key_equal; 320b57cec5SDimitry Andric typedef Alloc allocator_type; 330b57cec5SDimitry Andric typedef value_type& reference; 340b57cec5SDimitry Andric typedef const value_type& const_reference; 350b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::pointer pointer; 360b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 370b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::size_type size_type; 380b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::difference_type difference_type; 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric typedef /unspecified/ iterator; 410b57cec5SDimitry Andric typedef /unspecified/ const_iterator; 420b57cec5SDimitry Andric typedef /unspecified/ local_iterator; 430b57cec5SDimitry Andric typedef /unspecified/ const_local_iterator; 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric typedef unspecified node_type unspecified; // C++17 460b57cec5SDimitry Andric typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 470b57cec5SDimitry Andric 480b57cec5SDimitry Andric unordered_set() 490b57cec5SDimitry Andric noexcept( 500b57cec5SDimitry Andric is_nothrow_default_constructible<hasher>::value && 510b57cec5SDimitry Andric is_nothrow_default_constructible<key_equal>::value && 520b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value); 530b57cec5SDimitry Andric explicit unordered_set(size_type n, const hasher& hf = hasher(), 540b57cec5SDimitry Andric const key_equal& eql = key_equal(), 550b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 560b57cec5SDimitry Andric template <class InputIterator> 570b57cec5SDimitry Andric unordered_set(InputIterator f, InputIterator l, 580b57cec5SDimitry Andric size_type n = 0, const hasher& hf = hasher(), 590b57cec5SDimitry Andric const key_equal& eql = key_equal(), 600b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 610b57cec5SDimitry Andric explicit unordered_set(const allocator_type&); 620b57cec5SDimitry Andric unordered_set(const unordered_set&); 630b57cec5SDimitry Andric unordered_set(const unordered_set&, const Allocator&); 640b57cec5SDimitry Andric unordered_set(unordered_set&&) 650b57cec5SDimitry Andric noexcept( 660b57cec5SDimitry Andric is_nothrow_move_constructible<hasher>::value && 670b57cec5SDimitry Andric is_nothrow_move_constructible<key_equal>::value && 680b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value); 690b57cec5SDimitry Andric unordered_set(unordered_set&&, const Allocator&); 700b57cec5SDimitry Andric unordered_set(initializer_list<value_type>, size_type n = 0, 710b57cec5SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 720b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 730b57cec5SDimitry Andric unordered_set(size_type n, const allocator_type& a); // C++14 740b57cec5SDimitry Andric unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 750b57cec5SDimitry Andric template <class InputIterator> 760b57cec5SDimitry Andric unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 770b57cec5SDimitry Andric template <class InputIterator> 780b57cec5SDimitry Andric unordered_set(InputIterator f, InputIterator l, size_type n, 790b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 800b57cec5SDimitry Andric unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 810b57cec5SDimitry Andric unordered_set(initializer_list<value_type> il, size_type n, 820b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 830b57cec5SDimitry Andric ~unordered_set(); 840b57cec5SDimitry Andric unordered_set& operator=(const unordered_set&); 850b57cec5SDimitry Andric unordered_set& operator=(unordered_set&&) 860b57cec5SDimitry Andric noexcept( 870b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 880b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 890b57cec5SDimitry Andric is_nothrow_move_assignable<hasher>::value && 900b57cec5SDimitry Andric is_nothrow_move_assignable<key_equal>::value); 910b57cec5SDimitry Andric unordered_set& operator=(initializer_list<value_type>); 920b57cec5SDimitry Andric 930b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 940b57cec5SDimitry Andric 950b57cec5SDimitry Andric bool empty() const noexcept; 960b57cec5SDimitry Andric size_type size() const noexcept; 970b57cec5SDimitry Andric size_type max_size() const noexcept; 980b57cec5SDimitry Andric 990b57cec5SDimitry Andric iterator begin() noexcept; 1000b57cec5SDimitry Andric iterator end() noexcept; 1010b57cec5SDimitry Andric const_iterator begin() const noexcept; 1020b57cec5SDimitry Andric const_iterator end() const noexcept; 1030b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 1040b57cec5SDimitry Andric const_iterator cend() const noexcept; 1050b57cec5SDimitry Andric 1060b57cec5SDimitry Andric template <class... Args> 1070b57cec5SDimitry Andric pair<iterator, bool> emplace(Args&&... args); 1080b57cec5SDimitry Andric template <class... Args> 1090b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 1100b57cec5SDimitry Andric pair<iterator, bool> insert(const value_type& obj); 1110b57cec5SDimitry Andric pair<iterator, bool> insert(value_type&& obj); 1120b57cec5SDimitry Andric iterator insert(const_iterator hint, const value_type& obj); 1130b57cec5SDimitry Andric iterator insert(const_iterator hint, value_type&& obj); 1140b57cec5SDimitry Andric template <class InputIterator> 1150b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 1160b57cec5SDimitry Andric void insert(initializer_list<value_type>); 1170b57cec5SDimitry Andric 1180b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 1190b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 1200b57cec5SDimitry Andric insert_return_type insert(node_type&& nh); // C++17 1210b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 1220b57cec5SDimitry Andric 1230b57cec5SDimitry Andric iterator erase(const_iterator position); 1240b57cec5SDimitry Andric iterator erase(iterator position); // C++14 1250b57cec5SDimitry Andric size_type erase(const key_type& k); 1260b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 1270b57cec5SDimitry Andric void clear() noexcept; 1280b57cec5SDimitry Andric 1290b57cec5SDimitry Andric template<class H2, class P2> 1300b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 1310b57cec5SDimitry Andric template<class H2, class P2> 1320b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 1330b57cec5SDimitry Andric template<class H2, class P2> 1340b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 1350b57cec5SDimitry Andric template<class H2, class P2> 1360b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 1370b57cec5SDimitry Andric 1380b57cec5SDimitry Andric void swap(unordered_set&) 1390b57cec5SDimitry Andric noexcept(allocator_traits<Allocator>::is_always_equal::value && 1400b57cec5SDimitry Andric noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 1410b57cec5SDimitry Andric noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 1420b57cec5SDimitry Andric 1430b57cec5SDimitry Andric hasher hash_function() const; 1440b57cec5SDimitry Andric key_equal key_eq() const; 1450b57cec5SDimitry Andric 1460b57cec5SDimitry Andric iterator find(const key_type& k); 1470b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 148*e8d8bef9SDimitry Andric template<typename K> 149*e8d8bef9SDimitry Andric iterator find(const K& x); // C++20 150*e8d8bef9SDimitry Andric template<typename K> 151*e8d8bef9SDimitry Andric const_iterator find(const K& x) const; // C++20 1520b57cec5SDimitry Andric size_type count(const key_type& k) const; 153*e8d8bef9SDimitry Andric template<typename K> 154*e8d8bef9SDimitry Andric size_type count(const K& k) const; // C++20 1550b57cec5SDimitry Andric bool contains(const key_type& k) const; // C++20 156*e8d8bef9SDimitry Andric template<typename K> 157*e8d8bef9SDimitry Andric bool contains(const K& k) const; // C++20 1580b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& k); 1590b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 160*e8d8bef9SDimitry Andric template<typename K> 161*e8d8bef9SDimitry Andric pair<iterator, iterator> equal_range(const K& k); // C++20 162*e8d8bef9SDimitry Andric template<typename K> 163*e8d8bef9SDimitry Andric pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 1640b57cec5SDimitry Andric 1650b57cec5SDimitry Andric size_type bucket_count() const noexcept; 1660b57cec5SDimitry Andric size_type max_bucket_count() const noexcept; 1670b57cec5SDimitry Andric 1680b57cec5SDimitry Andric size_type bucket_size(size_type n) const; 1690b57cec5SDimitry Andric size_type bucket(const key_type& k) const; 1700b57cec5SDimitry Andric 1710b57cec5SDimitry Andric local_iterator begin(size_type n); 1720b57cec5SDimitry Andric local_iterator end(size_type n); 1730b57cec5SDimitry Andric const_local_iterator begin(size_type n) const; 1740b57cec5SDimitry Andric const_local_iterator end(size_type n) const; 1750b57cec5SDimitry Andric const_local_iterator cbegin(size_type n) const; 1760b57cec5SDimitry Andric const_local_iterator cend(size_type n) const; 1770b57cec5SDimitry Andric 1780b57cec5SDimitry Andric float load_factor() const noexcept; 1790b57cec5SDimitry Andric float max_load_factor() const noexcept; 1800b57cec5SDimitry Andric void max_load_factor(float z); 1810b57cec5SDimitry Andric void rehash(size_type n); 1820b57cec5SDimitry Andric void reserve(size_type n); 1830b57cec5SDimitry Andric}; 1840b57cec5SDimitry Andric 1850b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 1860b57cec5SDimitry Andric void swap(unordered_set<Value, Hash, Pred, Alloc>& x, 1870b57cec5SDimitry Andric unordered_set<Value, Hash, Pred, Alloc>& y) 1880b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 1890b57cec5SDimitry Andric 1900b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 1910b57cec5SDimitry Andric bool 1920b57cec5SDimitry Andric operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, 1930b57cec5SDimitry Andric const unordered_set<Value, Hash, Pred, Alloc>& y); 1940b57cec5SDimitry Andric 1950b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 1960b57cec5SDimitry Andric bool 1970b57cec5SDimitry Andric operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, 1980b57cec5SDimitry Andric const unordered_set<Value, Hash, Pred, Alloc>& y); 1990b57cec5SDimitry Andric 2000b57cec5SDimitry Andrictemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, 2010b57cec5SDimitry Andric class Alloc = allocator<Value>> 2020b57cec5SDimitry Andricclass unordered_multiset 2030b57cec5SDimitry Andric{ 2040b57cec5SDimitry Andricpublic: 2050b57cec5SDimitry Andric // types 2060b57cec5SDimitry Andric typedef Value key_type; 2070b57cec5SDimitry Andric typedef key_type value_type; 2080b57cec5SDimitry Andric typedef Hash hasher; 2090b57cec5SDimitry Andric typedef Pred key_equal; 2100b57cec5SDimitry Andric typedef Alloc allocator_type; 2110b57cec5SDimitry Andric typedef value_type& reference; 2120b57cec5SDimitry Andric typedef const value_type& const_reference; 2130b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::pointer pointer; 2140b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 2150b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::size_type size_type; 2160b57cec5SDimitry Andric typedef typename allocator_traits<allocator_type>::difference_type difference_type; 2170b57cec5SDimitry Andric 2180b57cec5SDimitry Andric typedef /unspecified/ iterator; 2190b57cec5SDimitry Andric typedef /unspecified/ const_iterator; 2200b57cec5SDimitry Andric typedef /unspecified/ local_iterator; 2210b57cec5SDimitry Andric typedef /unspecified/ const_local_iterator; 2220b57cec5SDimitry Andric 2230b57cec5SDimitry Andric typedef unspecified node_type unspecified; // C++17 2240b57cec5SDimitry Andric 2250b57cec5SDimitry Andric unordered_multiset() 2260b57cec5SDimitry Andric noexcept( 2270b57cec5SDimitry Andric is_nothrow_default_constructible<hasher>::value && 2280b57cec5SDimitry Andric is_nothrow_default_constructible<key_equal>::value && 2290b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value); 2300b57cec5SDimitry Andric explicit unordered_multiset(size_type n, const hasher& hf = hasher(), 2310b57cec5SDimitry Andric const key_equal& eql = key_equal(), 2320b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 2330b57cec5SDimitry Andric template <class InputIterator> 2340b57cec5SDimitry Andric unordered_multiset(InputIterator f, InputIterator l, 2350b57cec5SDimitry Andric size_type n = 0, const hasher& hf = hasher(), 2360b57cec5SDimitry Andric const key_equal& eql = key_equal(), 2370b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 2380b57cec5SDimitry Andric explicit unordered_multiset(const allocator_type&); 2390b57cec5SDimitry Andric unordered_multiset(const unordered_multiset&); 2400b57cec5SDimitry Andric unordered_multiset(const unordered_multiset&, const Allocator&); 2410b57cec5SDimitry Andric unordered_multiset(unordered_multiset&&) 2420b57cec5SDimitry Andric noexcept( 2430b57cec5SDimitry Andric is_nothrow_move_constructible<hasher>::value && 2440b57cec5SDimitry Andric is_nothrow_move_constructible<key_equal>::value && 2450b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value); 2460b57cec5SDimitry Andric unordered_multiset(unordered_multiset&&, const Allocator&); 2470b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type>, size_type n = /see below/, 2480b57cec5SDimitry Andric const hasher& hf = hasher(), const key_equal& eql = key_equal(), 2490b57cec5SDimitry Andric const allocator_type& a = allocator_type()); 2500b57cec5SDimitry Andric unordered_multiset(size_type n, const allocator_type& a); // C++14 2510b57cec5SDimitry Andric unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 2520b57cec5SDimitry Andric template <class InputIterator> 2530b57cec5SDimitry Andric unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 2540b57cec5SDimitry Andric template <class InputIterator> 2550b57cec5SDimitry Andric unordered_multiset(InputIterator f, InputIterator l, size_type n, 2560b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 2570b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 2580b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> il, size_type n, 2590b57cec5SDimitry Andric const hasher& hf, const allocator_type& a); // C++14 2600b57cec5SDimitry Andric ~unordered_multiset(); 2610b57cec5SDimitry Andric unordered_multiset& operator=(const unordered_multiset&); 2620b57cec5SDimitry Andric unordered_multiset& operator=(unordered_multiset&&) 2630b57cec5SDimitry Andric noexcept( 2640b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 2650b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 2660b57cec5SDimitry Andric is_nothrow_move_assignable<hasher>::value && 2670b57cec5SDimitry Andric is_nothrow_move_assignable<key_equal>::value); 2680b57cec5SDimitry Andric unordered_multiset& operator=(initializer_list<value_type>); 2690b57cec5SDimitry Andric 2700b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 2710b57cec5SDimitry Andric 2720b57cec5SDimitry Andric bool empty() const noexcept; 2730b57cec5SDimitry Andric size_type size() const noexcept; 2740b57cec5SDimitry Andric size_type max_size() const noexcept; 2750b57cec5SDimitry Andric 2760b57cec5SDimitry Andric iterator begin() noexcept; 2770b57cec5SDimitry Andric iterator end() noexcept; 2780b57cec5SDimitry Andric const_iterator begin() const noexcept; 2790b57cec5SDimitry Andric const_iterator end() const noexcept; 2800b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 2810b57cec5SDimitry Andric const_iterator cend() const noexcept; 2820b57cec5SDimitry Andric 2830b57cec5SDimitry Andric template <class... Args> 2840b57cec5SDimitry Andric iterator emplace(Args&&... args); 2850b57cec5SDimitry Andric template <class... Args> 2860b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 2870b57cec5SDimitry Andric iterator insert(const value_type& obj); 2880b57cec5SDimitry Andric iterator insert(value_type&& obj); 2890b57cec5SDimitry Andric iterator insert(const_iterator hint, const value_type& obj); 2900b57cec5SDimitry Andric iterator insert(const_iterator hint, value_type&& obj); 2910b57cec5SDimitry Andric template <class InputIterator> 2920b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 2930b57cec5SDimitry Andric void insert(initializer_list<value_type>); 2940b57cec5SDimitry Andric 2950b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 2960b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 2970b57cec5SDimitry Andric iterator insert(node_type&& nh); // C++17 2980b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 2990b57cec5SDimitry Andric 3000b57cec5SDimitry Andric iterator erase(const_iterator position); 3010b57cec5SDimitry Andric iterator erase(iterator position); // C++14 3020b57cec5SDimitry Andric size_type erase(const key_type& k); 3030b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 3040b57cec5SDimitry Andric void clear() noexcept; 3050b57cec5SDimitry Andric 3060b57cec5SDimitry Andric template<class H2, class P2> 3070b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 3080b57cec5SDimitry Andric template<class H2, class P2> 3090b57cec5SDimitry Andric void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 3100b57cec5SDimitry Andric template<class H2, class P2> 3110b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 3120b57cec5SDimitry Andric template<class H2, class P2> 3130b57cec5SDimitry Andric void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 3140b57cec5SDimitry Andric 3150b57cec5SDimitry Andric void swap(unordered_multiset&) 3160b57cec5SDimitry Andric noexcept(allocator_traits<Allocator>::is_always_equal::value && 3170b57cec5SDimitry Andric noexcept(swap(declval<hasher&>(), declval<hasher&>())) && 3180b57cec5SDimitry Andric noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 3190b57cec5SDimitry Andric 3200b57cec5SDimitry Andric hasher hash_function() const; 3210b57cec5SDimitry Andric key_equal key_eq() const; 3220b57cec5SDimitry Andric 3230b57cec5SDimitry Andric iterator find(const key_type& k); 3240b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 325*e8d8bef9SDimitry Andric template<typename K> 326*e8d8bef9SDimitry Andric iterator find(const K& x); // C++20 327*e8d8bef9SDimitry Andric template<typename K> 328*e8d8bef9SDimitry Andric const_iterator find(const K& x) const; // C++20 3290b57cec5SDimitry Andric size_type count(const key_type& k) const; 330*e8d8bef9SDimitry Andric template<typename K> 331*e8d8bef9SDimitry Andric size_type count(const K& k) const; // C++20 3320b57cec5SDimitry Andric bool contains(const key_type& k) const; // C++20 333*e8d8bef9SDimitry Andric template<typename K> 334*e8d8bef9SDimitry Andric bool contains(const K& k) const; // C++20 3350b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& k); 3360b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 337*e8d8bef9SDimitry Andric template<typename K> 338*e8d8bef9SDimitry Andric pair<iterator, iterator> equal_range(const K& k); // C++20 339*e8d8bef9SDimitry Andric template<typename K> 340*e8d8bef9SDimitry Andric pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20 3410b57cec5SDimitry Andric 3420b57cec5SDimitry Andric size_type bucket_count() const noexcept; 3430b57cec5SDimitry Andric size_type max_bucket_count() const noexcept; 3440b57cec5SDimitry Andric 3450b57cec5SDimitry Andric size_type bucket_size(size_type n) const; 3460b57cec5SDimitry Andric size_type bucket(const key_type& k) const; 3470b57cec5SDimitry Andric 3480b57cec5SDimitry Andric local_iterator begin(size_type n); 3490b57cec5SDimitry Andric local_iterator end(size_type n); 3500b57cec5SDimitry Andric const_local_iterator begin(size_type n) const; 3510b57cec5SDimitry Andric const_local_iterator end(size_type n) const; 3520b57cec5SDimitry Andric const_local_iterator cbegin(size_type n) const; 3530b57cec5SDimitry Andric const_local_iterator cend(size_type n) const; 3540b57cec5SDimitry Andric 3550b57cec5SDimitry Andric float load_factor() const noexcept; 3560b57cec5SDimitry Andric float max_load_factor() const noexcept; 3570b57cec5SDimitry Andric void max_load_factor(float z); 3580b57cec5SDimitry Andric void rehash(size_type n); 3590b57cec5SDimitry Andric void reserve(size_type n); 3600b57cec5SDimitry Andric}; 3610b57cec5SDimitry Andric 3620b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 3630b57cec5SDimitry Andric void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, 3640b57cec5SDimitry Andric unordered_multiset<Value, Hash, Pred, Alloc>& y) 3650b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 3660b57cec5SDimitry Andric 3670b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate> 3685ffd83dbSDimitry Andric typename unordered_set<K, T, H, P, A>::size_type 3695ffd83dbSDimitry Andric erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20 3700b57cec5SDimitry Andric 3710b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate> 3725ffd83dbSDimitry Andric typename unordered_multiset<K, T, H, P, A>::size_type 3735ffd83dbSDimitry Andric erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20 3740b57cec5SDimitry Andric 3750b57cec5SDimitry Andric 3760b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 3770b57cec5SDimitry Andric bool 3780b57cec5SDimitry Andric operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 3790b57cec5SDimitry Andric const unordered_multiset<Value, Hash, Pred, Alloc>& y); 3800b57cec5SDimitry Andric 3810b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc> 3820b57cec5SDimitry Andric bool 3830b57cec5SDimitry Andric operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, 3840b57cec5SDimitry Andric const unordered_multiset<Value, Hash, Pred, Alloc>& y); 3850b57cec5SDimitry Andric} // std 3860b57cec5SDimitry Andric 3870b57cec5SDimitry Andric*/ 3880b57cec5SDimitry Andric 3890b57cec5SDimitry Andric#include <__config> 3900b57cec5SDimitry Andric#include <__hash_table> 3910b57cec5SDimitry Andric#include <__node_handle> 3920b57cec5SDimitry Andric#include <functional> 3930b57cec5SDimitry Andric#include <version> 3940b57cec5SDimitry Andric 3950b57cec5SDimitry Andric#include <__debug> 3960b57cec5SDimitry Andric 3970b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 3980b57cec5SDimitry Andric#pragma GCC system_header 3990b57cec5SDimitry Andric#endif 4000b57cec5SDimitry Andric 4010b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 4020b57cec5SDimitry Andric 4030b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 4040b57cec5SDimitry Andricclass unordered_multiset; 4050b57cec5SDimitry Andric 4060b57cec5SDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 4070b57cec5SDimitry Andric class _Alloc = allocator<_Value> > 4080b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_set 4090b57cec5SDimitry Andric{ 4100b57cec5SDimitry Andricpublic: 4110b57cec5SDimitry Andric // types 4120b57cec5SDimitry Andric typedef _Value key_type; 4130b57cec5SDimitry Andric typedef key_type value_type; 4140b57cec5SDimitry Andric typedef typename __identity<_Hash>::type hasher; 4150b57cec5SDimitry Andric typedef typename __identity<_Pred>::type key_equal; 4160b57cec5SDimitry Andric typedef typename __identity<_Alloc>::type allocator_type; 4170b57cec5SDimitry Andric typedef value_type& reference; 4180b57cec5SDimitry Andric typedef const value_type& const_reference; 4190b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 4200b57cec5SDimitry Andric "Invalid allocator::value_type"); 4210b57cec5SDimitry Andric 4220b57cec5SDimitry Andricprivate: 4230b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 4240b57cec5SDimitry Andric 4250b57cec5SDimitry Andric __table __table_; 4260b57cec5SDimitry Andric 4270b57cec5SDimitry Andricpublic: 4280b57cec5SDimitry Andric typedef typename __table::pointer pointer; 4290b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 4300b57cec5SDimitry Andric typedef typename __table::size_type size_type; 4310b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 4320b57cec5SDimitry Andric 4330b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 4340b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 4350b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 4360b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 4370b57cec5SDimitry Andric 4380b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 4390b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 4400b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 4410b57cec5SDimitry Andric#endif 4420b57cec5SDimitry Andric 4430b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 4440b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 4450b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 4460b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 4470b57cec5SDimitry Andric 4480b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 4490b57cec5SDimitry Andric unordered_set() 4500b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 4510b57cec5SDimitry Andric { 452*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 4530b57cec5SDimitry Andric __get_db()->__insert_c(this); 4540b57cec5SDimitry Andric#endif 4550b57cec5SDimitry Andric } 4560b57cec5SDimitry Andric explicit unordered_set(size_type __n, const hasher& __hf = hasher(), 4570b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 4580b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 4590b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 4600b57cec5SDimitry Andric unordered_set(size_type __n, const allocator_type& __a) 4610b57cec5SDimitry Andric : unordered_set(__n, hasher(), key_equal(), __a) {} 4620b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 4630b57cec5SDimitry Andric unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) 4640b57cec5SDimitry Andric : unordered_set(__n, __hf, key_equal(), __a) {} 4650b57cec5SDimitry Andric#endif 4660b57cec5SDimitry Andric unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, 4670b57cec5SDimitry Andric const allocator_type& __a); 4680b57cec5SDimitry Andric template <class _InputIterator> 4690b57cec5SDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last); 4700b57cec5SDimitry Andric template <class _InputIterator> 4710b57cec5SDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, 4720b57cec5SDimitry Andric size_type __n, const hasher& __hf = hasher(), 4730b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 4740b57cec5SDimitry Andric template <class _InputIterator> 4750b57cec5SDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, 4760b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, 4770b57cec5SDimitry Andric const allocator_type& __a); 4780b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 4790b57cec5SDimitry Andric template <class _InputIterator> 4800b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 4810b57cec5SDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, 4820b57cec5SDimitry Andric size_type __n, const allocator_type& __a) 4830b57cec5SDimitry Andric : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} 4840b57cec5SDimitry Andric template <class _InputIterator> 4850b57cec5SDimitry Andric unordered_set(_InputIterator __first, _InputIterator __last, 4860b57cec5SDimitry Andric size_type __n, const hasher& __hf, const allocator_type& __a) 4870b57cec5SDimitry Andric : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} 4880b57cec5SDimitry Andric#endif 4890b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 4900b57cec5SDimitry Andric explicit unordered_set(const allocator_type& __a); 4910b57cec5SDimitry Andric unordered_set(const unordered_set& __u); 4920b57cec5SDimitry Andric unordered_set(const unordered_set& __u, const allocator_type& __a); 4930b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 4940b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 4950b57cec5SDimitry Andric unordered_set(unordered_set&& __u) 4960b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 4970b57cec5SDimitry Andric unordered_set(unordered_set&& __u, const allocator_type& __a); 4980b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il); 4990b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, 5000b57cec5SDimitry Andric const hasher& __hf = hasher(), 5010b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 5020b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, 5030b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, 5040b57cec5SDimitry Andric const allocator_type& __a); 5050b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 5060b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 5070b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, 5080b57cec5SDimitry Andric const allocator_type& __a) 5090b57cec5SDimitry Andric : unordered_set(__il, __n, hasher(), key_equal(), __a) {} 5100b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 5110b57cec5SDimitry Andric unordered_set(initializer_list<value_type> __il, size_type __n, 5120b57cec5SDimitry Andric const hasher& __hf, const allocator_type& __a) 5130b57cec5SDimitry Andric : unordered_set(__il, __n, __hf, key_equal(), __a) {} 5140b57cec5SDimitry Andric#endif 5150b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 5160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5170b57cec5SDimitry Andric ~unordered_set() { 5180b57cec5SDimitry Andric static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 5190b57cec5SDimitry Andric } 5200b57cec5SDimitry Andric 5210b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5220b57cec5SDimitry Andric unordered_set& operator=(const unordered_set& __u) 5230b57cec5SDimitry Andric { 5240b57cec5SDimitry Andric __table_ = __u.__table_; 5250b57cec5SDimitry Andric return *this; 5260b57cec5SDimitry Andric } 5270b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 5280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5290b57cec5SDimitry Andric unordered_set& operator=(unordered_set&& __u) 5300b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 5310b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5320b57cec5SDimitry Andric unordered_set& operator=(initializer_list<value_type> __il); 5330b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 5340b57cec5SDimitry Andric 5350b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5360b57cec5SDimitry Andric allocator_type get_allocator() const _NOEXCEPT 5370b57cec5SDimitry Andric {return allocator_type(__table_.__node_alloc());} 5380b57cec5SDimitry Andric 5390b57cec5SDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 5400b57cec5SDimitry Andric bool empty() const _NOEXCEPT {return __table_.size() == 0;} 5410b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5420b57cec5SDimitry Andric size_type size() const _NOEXCEPT {return __table_.size();} 5430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5440b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT {return __table_.max_size();} 5450b57cec5SDimitry Andric 5460b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5470b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return __table_.begin();} 5480b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5490b57cec5SDimitry Andric iterator end() _NOEXCEPT {return __table_.end();} 5500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5510b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return __table_.begin();} 5520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5530b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return __table_.end();} 5540b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5550b57cec5SDimitry Andric const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 5560b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5570b57cec5SDimitry Andric const_iterator cend() const _NOEXCEPT {return __table_.end();} 5580b57cec5SDimitry Andric 5590b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 5600b57cec5SDimitry Andric template <class... _Args> 5610b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5620b57cec5SDimitry Andric pair<iterator, bool> emplace(_Args&&... __args) 5630b57cec5SDimitry Andric {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 5640b57cec5SDimitry Andric template <class... _Args> 5650b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 566*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 5670b57cec5SDimitry Andric iterator emplace_hint(const_iterator __p, _Args&&... __args) 5680b57cec5SDimitry Andric { 5690b57cec5SDimitry Andric _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 5700b57cec5SDimitry Andric "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" 5710b57cec5SDimitry Andric " referring to this unordered_set"); 5720b57cec5SDimitry Andric return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 5730b57cec5SDimitry Andric } 5740b57cec5SDimitry Andric#else 5750b57cec5SDimitry Andric iterator emplace_hint(const_iterator, _Args&&... __args) 5760b57cec5SDimitry Andric {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} 5770b57cec5SDimitry Andric#endif 5780b57cec5SDimitry Andric 5790b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5800b57cec5SDimitry Andric pair<iterator, bool> insert(value_type&& __x) 5810b57cec5SDimitry Andric {return __table_.__insert_unique(_VSTD::move(__x));} 5820b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 583*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 5840b57cec5SDimitry Andric iterator insert(const_iterator __p, value_type&& __x) 5850b57cec5SDimitry Andric { 5860b57cec5SDimitry Andric _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 5870b57cec5SDimitry Andric "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" 5880b57cec5SDimitry Andric " referring to this unordered_set"); 5890b57cec5SDimitry Andric return insert(_VSTD::move(__x)).first; 5900b57cec5SDimitry Andric } 5910b57cec5SDimitry Andric#else 5920b57cec5SDimitry Andric iterator insert(const_iterator, value_type&& __x) 5930b57cec5SDimitry Andric {return insert(_VSTD::move(__x)).first;} 5940b57cec5SDimitry Andric#endif 5950b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5960b57cec5SDimitry Andric void insert(initializer_list<value_type> __il) 5970b57cec5SDimitry Andric {insert(__il.begin(), __il.end());} 5980b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 5990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6000b57cec5SDimitry Andric pair<iterator, bool> insert(const value_type& __x) 6010b57cec5SDimitry Andric {return __table_.__insert_unique(__x);} 6020b57cec5SDimitry Andric 6030b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 604*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 6050b57cec5SDimitry Andric iterator insert(const_iterator __p, const value_type& __x) 6060b57cec5SDimitry Andric { 6070b57cec5SDimitry Andric _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 6080b57cec5SDimitry Andric "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" 6090b57cec5SDimitry Andric " referring to this unordered_set"); 6100b57cec5SDimitry Andric return insert(__x).first; 6110b57cec5SDimitry Andric } 6120b57cec5SDimitry Andric#else 6130b57cec5SDimitry Andric iterator insert(const_iterator, const value_type& __x) 6140b57cec5SDimitry Andric {return insert(__x).first;} 6150b57cec5SDimitry Andric#endif 6160b57cec5SDimitry Andric template <class _InputIterator> 6170b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6180b57cec5SDimitry Andric void insert(_InputIterator __first, _InputIterator __last); 6190b57cec5SDimitry Andric 6200b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6210b57cec5SDimitry Andric iterator erase(const_iterator __p) {return __table_.erase(__p);} 6220b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6230b57cec5SDimitry Andric size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 6240b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6250b57cec5SDimitry Andric iterator erase(const_iterator __first, const_iterator __last) 6260b57cec5SDimitry Andric {return __table_.erase(__first, __last);} 6270b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6280b57cec5SDimitry Andric void clear() _NOEXCEPT {__table_.clear();} 6290b57cec5SDimitry Andric 6300b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 6310b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6320b57cec5SDimitry Andric insert_return_type insert(node_type&& __nh) 6330b57cec5SDimitry Andric { 6340b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 6350b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 6360b57cec5SDimitry Andric return __table_.template __node_handle_insert_unique< 6370b57cec5SDimitry Andric node_type, insert_return_type>(_VSTD::move(__nh)); 6380b57cec5SDimitry Andric } 6390b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6400b57cec5SDimitry Andric iterator insert(const_iterator __h, node_type&& __nh) 6410b57cec5SDimitry Andric { 6420b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 6430b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_set::insert()"); 6440b57cec5SDimitry Andric return __table_.template __node_handle_insert_unique<node_type>( 6450b57cec5SDimitry Andric __h, _VSTD::move(__nh)); 6460b57cec5SDimitry Andric } 6470b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6480b57cec5SDimitry Andric node_type extract(key_type const& __key) 6490b57cec5SDimitry Andric { 6500b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 6510b57cec5SDimitry Andric } 6520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6530b57cec5SDimitry Andric node_type extract(const_iterator __it) 6540b57cec5SDimitry Andric { 6550b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__it); 6560b57cec5SDimitry Andric } 6570b57cec5SDimitry Andric 6580b57cec5SDimitry Andric template<class _H2, class _P2> 6590b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6600b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 6610b57cec5SDimitry Andric { 6620b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 6630b57cec5SDimitry Andric "merging container with incompatible allocator"); 6640b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 6650b57cec5SDimitry Andric } 6660b57cec5SDimitry Andric template<class _H2, class _P2> 6670b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6680b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) 6690b57cec5SDimitry Andric { 6700b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 6710b57cec5SDimitry Andric "merging container with incompatible allocator"); 6720b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 6730b57cec5SDimitry Andric } 6740b57cec5SDimitry Andric template<class _H2, class _P2> 6750b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6760b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 6770b57cec5SDimitry Andric { 6780b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 6790b57cec5SDimitry Andric "merging container with incompatible allocator"); 6800b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 6810b57cec5SDimitry Andric } 6820b57cec5SDimitry Andric template<class _H2, class _P2> 6830b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6840b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 6850b57cec5SDimitry Andric { 6860b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 6870b57cec5SDimitry Andric "merging container with incompatible allocator"); 6880b57cec5SDimitry Andric __table_.__node_handle_merge_unique(__source.__table_); 6890b57cec5SDimitry Andric } 6900b57cec5SDimitry Andric#endif 6910b57cec5SDimitry Andric 6920b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6930b57cec5SDimitry Andric void swap(unordered_set& __u) 6940b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 6950b57cec5SDimitry Andric {__table_.swap(__u.__table_);} 6960b57cec5SDimitry Andric 6970b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6980b57cec5SDimitry Andric hasher hash_function() const {return __table_.hash_function();} 6990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7000b57cec5SDimitry Andric key_equal key_eq() const {return __table_.key_eq();} 7010b57cec5SDimitry Andric 7020b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7030b57cec5SDimitry Andric iterator find(const key_type& __k) {return __table_.find(__k);} 7040b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7050b57cec5SDimitry Andric const_iterator find(const key_type& __k) const {return __table_.find(__k);} 706*e8d8bef9SDimitry Andric #if _LIBCPP_STD_VER > 17 707*e8d8bef9SDimitry Andric template <typename _K2> 708*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 709*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, iterator> 710*e8d8bef9SDimitry Andric find(const _K2& __k) {return __table_.find(__k);} 711*e8d8bef9SDimitry Andric template <typename _K2> 712*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 713*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, const_iterator> 714*e8d8bef9SDimitry Andric find(const _K2& __k) const {return __table_.find(__k);} 715*e8d8bef9SDimitry Andric #endif // _LIBCPP_STD_VER > 17 7160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7170b57cec5SDimitry Andric size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 7180b57cec5SDimitry Andric #if _LIBCPP_STD_VER > 17 719*e8d8bef9SDimitry Andric template <typename _K2> 720*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 721*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, size_type> 722*e8d8bef9SDimitry Andric count(const _K2& __k) const {return __table_.__count_unique(__k);} 723*e8d8bef9SDimitry Andric #endif // _LIBCPP_STD_VER > 17 724*e8d8bef9SDimitry Andric #if _LIBCPP_STD_VER > 17 7250b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7260b57cec5SDimitry Andric bool contains(const key_type& __k) const {return find(__k) != end();} 727*e8d8bef9SDimitry Andric 728*e8d8bef9SDimitry Andric template <typename _K2> 729*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 730*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, bool> 731*e8d8bef9SDimitry Andric contains(const _K2& __k) const {return find(__k) != end();} 7320b57cec5SDimitry Andric #endif // _LIBCPP_STD_VER > 17 7330b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7340b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& __k) 7350b57cec5SDimitry Andric {return __table_.__equal_range_unique(__k);} 7360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7370b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 7380b57cec5SDimitry Andric {return __table_.__equal_range_unique(__k);} 739*e8d8bef9SDimitry Andric #if _LIBCPP_STD_VER > 17 740*e8d8bef9SDimitry Andric template <typename _K2> 741*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 742*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, pair<iterator, iterator>> 743*e8d8bef9SDimitry Andric equal_range(const _K2& __k) {return __table_.__equal_range_unique(__k);} 744*e8d8bef9SDimitry Andric template <typename _K2> 745*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 746*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, pair<const_iterator, const_iterator>> 747*e8d8bef9SDimitry Andric equal_range(const _K2& __k) const {return __table_.__equal_range_unique(__k);} 748*e8d8bef9SDimitry Andric #endif // _LIBCPP_STD_VER > 17 7490b57cec5SDimitry Andric 7500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7510b57cec5SDimitry Andric size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 7520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7530b57cec5SDimitry Andric size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 7540b57cec5SDimitry Andric 7550b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7560b57cec5SDimitry Andric size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 7570b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7580b57cec5SDimitry Andric size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 7590b57cec5SDimitry Andric 7600b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7610b57cec5SDimitry Andric local_iterator begin(size_type __n) {return __table_.begin(__n);} 7620b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7630b57cec5SDimitry Andric local_iterator end(size_type __n) {return __table_.end(__n);} 7640b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7650b57cec5SDimitry Andric const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 7660b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7670b57cec5SDimitry Andric const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 7680b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7690b57cec5SDimitry Andric const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 7700b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7710b57cec5SDimitry Andric const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 7720b57cec5SDimitry Andric 7730b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7740b57cec5SDimitry Andric float load_factor() const _NOEXCEPT {return __table_.load_factor();} 7750b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7760b57cec5SDimitry Andric float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 7770b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7780b57cec5SDimitry Andric void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 7790b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7800b57cec5SDimitry Andric void rehash(size_type __n) {__table_.rehash(__n);} 7810b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7820b57cec5SDimitry Andric void reserve(size_type __n) {__table_.reserve(__n);} 7830b57cec5SDimitry Andric 784*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 7850b57cec5SDimitry Andric 7860b57cec5SDimitry Andric bool __dereferenceable(const const_iterator* __i) const 7870b57cec5SDimitry Andric {return __table_.__dereferenceable(__i);} 7880b57cec5SDimitry Andric bool __decrementable(const const_iterator* __i) const 7890b57cec5SDimitry Andric {return __table_.__decrementable(__i);} 7900b57cec5SDimitry Andric bool __addable(const const_iterator* __i, ptrdiff_t __n) const 7910b57cec5SDimitry Andric {return __table_.__addable(__i, __n);} 7920b57cec5SDimitry Andric bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 7930b57cec5SDimitry Andric {return __table_.__addable(__i, __n);} 7940b57cec5SDimitry Andric 795*e8d8bef9SDimitry Andric#endif // _LIBCPP_DEBUG_LEVEL == 2 7960b57cec5SDimitry Andric 7970b57cec5SDimitry Andric}; 7980b57cec5SDimitry Andric 7990b57cec5SDimitry Andric#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 8000b57cec5SDimitry Andrictemplate<class _InputIterator, 8010b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 8020b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 8030b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 8040b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 8050b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 8060b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Pred>::value>, 8070b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 8080b57cec5SDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 8090b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 8100b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 8110b57cec5SDimitry Andric 8120b57cec5SDimitry Andrictemplate<class _Tp, class _Hash = hash<_Tp>, 8130b57cec5SDimitry Andric class _Pred = equal_to<_Tp>, 8140b57cec5SDimitry Andric class _Allocator = allocator<_Tp>, 8150b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 8160b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 8170b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Pred>::value>, 8180b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 8190b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, 8200b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 8210b57cec5SDimitry Andric -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 8220b57cec5SDimitry Andric 8230b57cec5SDimitry Andrictemplate<class _InputIterator, class _Allocator, 8240b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 8250b57cec5SDimitry Andricunordered_set(_InputIterator, _InputIterator, 8260b57cec5SDimitry Andric typename allocator_traits<_Allocator>::size_type, _Allocator) 8270b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, 8280b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 8290b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 8300b57cec5SDimitry Andric _Allocator>; 8310b57cec5SDimitry Andric 8320b57cec5SDimitry Andrictemplate<class _InputIterator, class _Hash, class _Allocator, 8330b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 8340b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 8350b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 8360b57cec5SDimitry Andricunordered_set(_InputIterator, _InputIterator, 8370b57cec5SDimitry Andric typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 8380b57cec5SDimitry Andric -> unordered_set<__iter_value_type<_InputIterator>, _Hash, 8390b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 8400b57cec5SDimitry Andric _Allocator>; 8410b57cec5SDimitry Andric 8420b57cec5SDimitry Andrictemplate<class _Tp, class _Allocator, 8430b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 8440b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 8450b57cec5SDimitry Andric -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 8460b57cec5SDimitry Andric 8470b57cec5SDimitry Andrictemplate<class _Tp, class _Hash, class _Allocator, 8480b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 8490b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 8500b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 8510b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 8520b57cec5SDimitry Andric -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 8530b57cec5SDimitry Andric#endif 8540b57cec5SDimitry Andric 8550b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 8560b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 8570b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql) 8580b57cec5SDimitry Andric : __table_(__hf, __eql) 8590b57cec5SDimitry Andric{ 860*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 8610b57cec5SDimitry Andric __get_db()->__insert_c(this); 8620b57cec5SDimitry Andric#endif 8630b57cec5SDimitry Andric __table_.rehash(__n); 8640b57cec5SDimitry Andric} 8650b57cec5SDimitry Andric 8660b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 8670b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, 8680b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 8690b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 8700b57cec5SDimitry Andric{ 871*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 8720b57cec5SDimitry Andric __get_db()->__insert_c(this); 8730b57cec5SDimitry Andric#endif 8740b57cec5SDimitry Andric __table_.rehash(__n); 8750b57cec5SDimitry Andric} 8760b57cec5SDimitry Andric 8770b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 8780b57cec5SDimitry Andrictemplate <class _InputIterator> 8790b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 8800b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last) 8810b57cec5SDimitry Andric{ 882*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 8830b57cec5SDimitry Andric __get_db()->__insert_c(this); 8840b57cec5SDimitry Andric#endif 8850b57cec5SDimitry Andric insert(__first, __last); 8860b57cec5SDimitry Andric} 8870b57cec5SDimitry Andric 8880b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 8890b57cec5SDimitry Andrictemplate <class _InputIterator> 8900b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 8910b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 8920b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql) 8930b57cec5SDimitry Andric : __table_(__hf, __eql) 8940b57cec5SDimitry Andric{ 895*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 8960b57cec5SDimitry Andric __get_db()->__insert_c(this); 8970b57cec5SDimitry Andric#endif 8980b57cec5SDimitry Andric __table_.rehash(__n); 8990b57cec5SDimitry Andric insert(__first, __last); 9000b57cec5SDimitry Andric} 9010b57cec5SDimitry Andric 9020b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9030b57cec5SDimitry Andrictemplate <class _InputIterator> 9040b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9050b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 9060b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 9070b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 9080b57cec5SDimitry Andric{ 909*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9100b57cec5SDimitry Andric __get_db()->__insert_c(this); 9110b57cec5SDimitry Andric#endif 9120b57cec5SDimitry Andric __table_.rehash(__n); 9130b57cec5SDimitry Andric insert(__first, __last); 9140b57cec5SDimitry Andric} 9150b57cec5SDimitry Andric 9160b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9170b57cec5SDimitry Andricinline 9180b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9190b57cec5SDimitry Andric const allocator_type& __a) 9200b57cec5SDimitry Andric : __table_(__a) 9210b57cec5SDimitry Andric{ 922*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9230b57cec5SDimitry Andric __get_db()->__insert_c(this); 9240b57cec5SDimitry Andric#endif 9250b57cec5SDimitry Andric} 9260b57cec5SDimitry Andric 9270b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9280b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9290b57cec5SDimitry Andric const unordered_set& __u) 9300b57cec5SDimitry Andric : __table_(__u.__table_) 9310b57cec5SDimitry Andric{ 932*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9330b57cec5SDimitry Andric __get_db()->__insert_c(this); 9340b57cec5SDimitry Andric#endif 9350b57cec5SDimitry Andric __table_.rehash(__u.bucket_count()); 9360b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 9370b57cec5SDimitry Andric} 9380b57cec5SDimitry Andric 9390b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9400b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9410b57cec5SDimitry Andric const unordered_set& __u, const allocator_type& __a) 9420b57cec5SDimitry Andric : __table_(__u.__table_, __a) 9430b57cec5SDimitry Andric{ 944*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9450b57cec5SDimitry Andric __get_db()->__insert_c(this); 9460b57cec5SDimitry Andric#endif 9470b57cec5SDimitry Andric __table_.rehash(__u.bucket_count()); 9480b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 9490b57cec5SDimitry Andric} 9500b57cec5SDimitry Andric 9510b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 9520b57cec5SDimitry Andric 9530b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9540b57cec5SDimitry Andricinline 9550b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9560b57cec5SDimitry Andric unordered_set&& __u) 9570b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 9580b57cec5SDimitry Andric : __table_(_VSTD::move(__u.__table_)) 9590b57cec5SDimitry Andric{ 960*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9610b57cec5SDimitry Andric __get_db()->__insert_c(this); 9620b57cec5SDimitry Andric __get_db()->swap(this, &__u); 9630b57cec5SDimitry Andric#endif 9640b57cec5SDimitry Andric} 9650b57cec5SDimitry Andric 9660b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9670b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9680b57cec5SDimitry Andric unordered_set&& __u, const allocator_type& __a) 9690b57cec5SDimitry Andric : __table_(_VSTD::move(__u.__table_), __a) 9700b57cec5SDimitry Andric{ 971*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9720b57cec5SDimitry Andric __get_db()->__insert_c(this); 9730b57cec5SDimitry Andric#endif 9740b57cec5SDimitry Andric if (__a != __u.get_allocator()) 9750b57cec5SDimitry Andric { 9760b57cec5SDimitry Andric iterator __i = __u.begin(); 9770b57cec5SDimitry Andric while (__u.size() != 0) 9780b57cec5SDimitry Andric __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 9790b57cec5SDimitry Andric } 980*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9810b57cec5SDimitry Andric else 9820b57cec5SDimitry Andric __get_db()->swap(this, &__u); 9830b57cec5SDimitry Andric#endif 9840b57cec5SDimitry Andric} 9850b57cec5SDimitry Andric 9860b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9870b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9880b57cec5SDimitry Andric initializer_list<value_type> __il) 9890b57cec5SDimitry Andric{ 990*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 9910b57cec5SDimitry Andric __get_db()->__insert_c(this); 9920b57cec5SDimitry Andric#endif 9930b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 9940b57cec5SDimitry Andric} 9950b57cec5SDimitry Andric 9960b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 9970b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 9980b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 9990b57cec5SDimitry Andric const key_equal& __eql) 10000b57cec5SDimitry Andric : __table_(__hf, __eql) 10010b57cec5SDimitry Andric{ 1002*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 10030b57cec5SDimitry Andric __get_db()->__insert_c(this); 10040b57cec5SDimitry Andric#endif 10050b57cec5SDimitry Andric __table_.rehash(__n); 10060b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 10070b57cec5SDimitry Andric} 10080b57cec5SDimitry Andric 10090b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10100b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( 10110b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 10120b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a) 10130b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 10140b57cec5SDimitry Andric{ 1015*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 10160b57cec5SDimitry Andric __get_db()->__insert_c(this); 10170b57cec5SDimitry Andric#endif 10180b57cec5SDimitry Andric __table_.rehash(__n); 10190b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 10200b57cec5SDimitry Andric} 10210b57cec5SDimitry Andric 10220b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10230b57cec5SDimitry Andricinline 10240b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>& 10250b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) 10260b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 10270b57cec5SDimitry Andric{ 10280b57cec5SDimitry Andric __table_ = _VSTD::move(__u.__table_); 10290b57cec5SDimitry Andric return *this; 10300b57cec5SDimitry Andric} 10310b57cec5SDimitry Andric 10320b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10330b57cec5SDimitry Andricinline 10340b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>& 10350b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( 10360b57cec5SDimitry Andric initializer_list<value_type> __il) 10370b57cec5SDimitry Andric{ 10380b57cec5SDimitry Andric __table_.__assign_unique(__il.begin(), __il.end()); 10390b57cec5SDimitry Andric return *this; 10400b57cec5SDimitry Andric} 10410b57cec5SDimitry Andric 10420b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 10430b57cec5SDimitry Andric 10440b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10450b57cec5SDimitry Andrictemplate <class _InputIterator> 10460b57cec5SDimitry Andricinline 10470b57cec5SDimitry Andricvoid 10480b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 10490b57cec5SDimitry Andric _InputIterator __last) 10500b57cec5SDimitry Andric{ 10510b57cec5SDimitry Andric for (; __first != __last; ++__first) 10520b57cec5SDimitry Andric __table_.__insert_unique(*__first); 10530b57cec5SDimitry Andric} 10540b57cec5SDimitry Andric 10550b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10560b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10570b57cec5SDimitry Andricvoid 10580b57cec5SDimitry Andricswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 10590b57cec5SDimitry Andric unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 10600b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 10610b57cec5SDimitry Andric{ 10620b57cec5SDimitry Andric __x.swap(__y); 10630b57cec5SDimitry Andric} 10640b57cec5SDimitry Andric 10650b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 10665ffd83dbSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, 10675ffd83dbSDimitry Andric class _Predicate> 10680b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10695ffd83dbSDimitry Andric typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type 10705ffd83dbSDimitry Andric erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, 10715ffd83dbSDimitry Andric _Predicate __pred) { 10725ffd83dbSDimitry Andric return __libcpp_erase_if_container(__c, __pred); 10735ffd83dbSDimitry Andric} 10740b57cec5SDimitry Andric#endif 10750b57cec5SDimitry Andric 10760b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10770b57cec5SDimitry Andricbool 10780b57cec5SDimitry Andricoperator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 10790b57cec5SDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 10800b57cec5SDimitry Andric{ 10810b57cec5SDimitry Andric if (__x.size() != __y.size()) 10820b57cec5SDimitry Andric return false; 10830b57cec5SDimitry Andric typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator 10840b57cec5SDimitry Andric const_iterator; 10850b57cec5SDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 10860b57cec5SDimitry Andric __i != __ex; ++__i) 10870b57cec5SDimitry Andric { 10880b57cec5SDimitry Andric const_iterator __j = __y.find(*__i); 10890b57cec5SDimitry Andric if (__j == __ey || !(*__i == *__j)) 10900b57cec5SDimitry Andric return false; 10910b57cec5SDimitry Andric } 10920b57cec5SDimitry Andric return true; 10930b57cec5SDimitry Andric} 10940b57cec5SDimitry Andric 10950b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 10960b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10970b57cec5SDimitry Andricbool 10980b57cec5SDimitry Andricoperator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 10990b57cec5SDimitry Andric const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 11000b57cec5SDimitry Andric{ 11010b57cec5SDimitry Andric return !(__x == __y); 11020b57cec5SDimitry Andric} 11030b57cec5SDimitry Andric 11040b57cec5SDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, 11050b57cec5SDimitry Andric class _Alloc = allocator<_Value> > 11060b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multiset 11070b57cec5SDimitry Andric{ 11080b57cec5SDimitry Andricpublic: 11090b57cec5SDimitry Andric // types 11100b57cec5SDimitry Andric typedef _Value key_type; 11110b57cec5SDimitry Andric typedef key_type value_type; 11120b57cec5SDimitry Andric typedef typename __identity<_Hash>::type hasher; 11130b57cec5SDimitry Andric typedef typename __identity<_Pred>::type key_equal; 11140b57cec5SDimitry Andric typedef typename __identity<_Alloc>::type allocator_type; 11150b57cec5SDimitry Andric typedef value_type& reference; 11160b57cec5SDimitry Andric typedef const value_type& const_reference; 11170b57cec5SDimitry Andric static_assert((is_same<value_type, typename allocator_type::value_type>::value), 11180b57cec5SDimitry Andric "Invalid allocator::value_type"); 11190b57cec5SDimitry Andric 11200b57cec5SDimitry Andricprivate: 11210b57cec5SDimitry Andric typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; 11220b57cec5SDimitry Andric 11230b57cec5SDimitry Andric __table __table_; 11240b57cec5SDimitry Andric 11250b57cec5SDimitry Andricpublic: 11260b57cec5SDimitry Andric typedef typename __table::pointer pointer; 11270b57cec5SDimitry Andric typedef typename __table::const_pointer const_pointer; 11280b57cec5SDimitry Andric typedef typename __table::size_type size_type; 11290b57cec5SDimitry Andric typedef typename __table::difference_type difference_type; 11300b57cec5SDimitry Andric 11310b57cec5SDimitry Andric typedef typename __table::const_iterator iterator; 11320b57cec5SDimitry Andric typedef typename __table::const_iterator const_iterator; 11330b57cec5SDimitry Andric typedef typename __table::const_local_iterator local_iterator; 11340b57cec5SDimitry Andric typedef typename __table::const_local_iterator const_local_iterator; 11350b57cec5SDimitry Andric 11360b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 11370b57cec5SDimitry Andric typedef __set_node_handle<typename __table::__node, allocator_type> node_type; 11380b57cec5SDimitry Andric#endif 11390b57cec5SDimitry Andric 11400b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 11410b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_set; 11420b57cec5SDimitry Andric template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> 11430b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; 11440b57cec5SDimitry Andric 11450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11460b57cec5SDimitry Andric unordered_multiset() 11470b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 11480b57cec5SDimitry Andric { 1149*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 11500b57cec5SDimitry Andric __get_db()->__insert_c(this); 11510b57cec5SDimitry Andric#endif 11520b57cec5SDimitry Andric } 11530b57cec5SDimitry Andric explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), 11540b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 11550b57cec5SDimitry Andric unordered_multiset(size_type __n, const hasher& __hf, 11560b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a); 11570b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 11580b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 11590b57cec5SDimitry Andric unordered_multiset(size_type __n, const allocator_type& __a) 11600b57cec5SDimitry Andric : unordered_multiset(__n, hasher(), key_equal(), __a) {} 11610b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 11620b57cec5SDimitry Andric unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) 11630b57cec5SDimitry Andric : unordered_multiset(__n, __hf, key_equal(), __a) {} 11640b57cec5SDimitry Andric#endif 11650b57cec5SDimitry Andric template <class _InputIterator> 11660b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last); 11670b57cec5SDimitry Andric template <class _InputIterator> 11680b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, 11690b57cec5SDimitry Andric size_type __n, const hasher& __hf = hasher(), 11700b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 11710b57cec5SDimitry Andric template <class _InputIterator> 11720b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, 11730b57cec5SDimitry Andric size_type __n , const hasher& __hf, 11740b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a); 11750b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 11760b57cec5SDimitry Andric template <class _InputIterator> 11770b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 11780b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, 11790b57cec5SDimitry Andric size_type __n, const allocator_type& __a) 11800b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} 11810b57cec5SDimitry Andric template <class _InputIterator> 11820b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 11830b57cec5SDimitry Andric unordered_multiset(_InputIterator __first, _InputIterator __last, 11840b57cec5SDimitry Andric size_type __n, const hasher& __hf, const allocator_type& __a) 11850b57cec5SDimitry Andric : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} 11860b57cec5SDimitry Andric#endif 11870b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11880b57cec5SDimitry Andric explicit unordered_multiset(const allocator_type& __a); 11890b57cec5SDimitry Andric unordered_multiset(const unordered_multiset& __u); 11900b57cec5SDimitry Andric unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); 11910b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 11920b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11930b57cec5SDimitry Andric unordered_multiset(unordered_multiset&& __u) 11940b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 11950b57cec5SDimitry Andric unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); 11960b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il); 11970b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, 11980b57cec5SDimitry Andric const hasher& __hf = hasher(), 11990b57cec5SDimitry Andric const key_equal& __eql = key_equal()); 12000b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, 12010b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, 12020b57cec5SDimitry Andric const allocator_type& __a); 12030b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 12040b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 12050b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 12060b57cec5SDimitry Andric : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} 12070b57cec5SDimitry Andric inline _LIBCPP_INLINE_VISIBILITY 12080b57cec5SDimitry Andric unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) 12090b57cec5SDimitry Andric : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} 12100b57cec5SDimitry Andric#endif 12110b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12120b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12130b57cec5SDimitry Andric ~unordered_multiset() { 12140b57cec5SDimitry Andric static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), ""); 12150b57cec5SDimitry Andric } 12160b57cec5SDimitry Andric 12170b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12180b57cec5SDimitry Andric unordered_multiset& operator=(const unordered_multiset& __u) 12190b57cec5SDimitry Andric { 12200b57cec5SDimitry Andric __table_ = __u.__table_; 12210b57cec5SDimitry Andric return *this; 12220b57cec5SDimitry Andric } 12230b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 12240b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12250b57cec5SDimitry Andric unordered_multiset& operator=(unordered_multiset&& __u) 12260b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 12270b57cec5SDimitry Andric unordered_multiset& operator=(initializer_list<value_type> __il); 12280b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12290b57cec5SDimitry Andric 12300b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12310b57cec5SDimitry Andric allocator_type get_allocator() const _NOEXCEPT 12320b57cec5SDimitry Andric {return allocator_type(__table_.__node_alloc());} 12330b57cec5SDimitry Andric 12340b57cec5SDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 12350b57cec5SDimitry Andric bool empty() const _NOEXCEPT {return __table_.size() == 0;} 12360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12370b57cec5SDimitry Andric size_type size() const _NOEXCEPT {return __table_.size();} 12380b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12390b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT {return __table_.max_size();} 12400b57cec5SDimitry Andric 12410b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12420b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return __table_.begin();} 12430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12440b57cec5SDimitry Andric iterator end() _NOEXCEPT {return __table_.end();} 12450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12460b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return __table_.begin();} 12470b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12480b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return __table_.end();} 12490b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12500b57cec5SDimitry Andric const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 12510b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12520b57cec5SDimitry Andric const_iterator cend() const _NOEXCEPT {return __table_.end();} 12530b57cec5SDimitry Andric 12540b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 12550b57cec5SDimitry Andric template <class... _Args> 12560b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12570b57cec5SDimitry Andric iterator emplace(_Args&&... __args) 12580b57cec5SDimitry Andric {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 12590b57cec5SDimitry Andric template <class... _Args> 12600b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12610b57cec5SDimitry Andric iterator emplace_hint(const_iterator __p, _Args&&... __args) 12620b57cec5SDimitry Andric {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 12630b57cec5SDimitry Andric 12640b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12650b57cec5SDimitry Andric iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 12660b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12670b57cec5SDimitry Andric iterator insert(const_iterator __p, value_type&& __x) 12680b57cec5SDimitry Andric {return __table_.__insert_multi(__p, _VSTD::move(__x));} 12690b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12700b57cec5SDimitry Andric void insert(initializer_list<value_type> __il) 12710b57cec5SDimitry Andric {insert(__il.begin(), __il.end());} 12720b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12730b57cec5SDimitry Andric 12740b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12750b57cec5SDimitry Andric iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 12760b57cec5SDimitry Andric 12770b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12780b57cec5SDimitry Andric iterator insert(const_iterator __p, const value_type& __x) 12790b57cec5SDimitry Andric {return __table_.__insert_multi(__p, __x);} 12800b57cec5SDimitry Andric 12810b57cec5SDimitry Andric template <class _InputIterator> 12820b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12830b57cec5SDimitry Andric void insert(_InputIterator __first, _InputIterator __last); 12840b57cec5SDimitry Andric 12850b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 12860b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12870b57cec5SDimitry Andric iterator insert(node_type&& __nh) 12880b57cec5SDimitry Andric { 12890b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 12900b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 12910b57cec5SDimitry Andric return __table_.template __node_handle_insert_multi<node_type>( 12920b57cec5SDimitry Andric _VSTD::move(__nh)); 12930b57cec5SDimitry Andric } 12940b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12950b57cec5SDimitry Andric iterator insert(const_iterator __hint, node_type&& __nh) 12960b57cec5SDimitry Andric { 12970b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 12980b57cec5SDimitry Andric "node_type with incompatible allocator passed to unordered_multiset::insert()"); 12990b57cec5SDimitry Andric return __table_.template __node_handle_insert_multi<node_type>( 13000b57cec5SDimitry Andric __hint, _VSTD::move(__nh)); 13010b57cec5SDimitry Andric } 13020b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13030b57cec5SDimitry Andric node_type extract(const_iterator __position) 13040b57cec5SDimitry Andric { 13050b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>( 13060b57cec5SDimitry Andric __position); 13070b57cec5SDimitry Andric } 13080b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13090b57cec5SDimitry Andric node_type extract(key_type const& __key) 13100b57cec5SDimitry Andric { 13110b57cec5SDimitry Andric return __table_.template __node_handle_extract<node_type>(__key); 13120b57cec5SDimitry Andric } 13130b57cec5SDimitry Andric 13140b57cec5SDimitry Andric template <class _H2, class _P2> 13150b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13160b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) 13170b57cec5SDimitry Andric { 13180b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13190b57cec5SDimitry Andric "merging container with incompatible allocator"); 13200b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 13210b57cec5SDimitry Andric } 13220b57cec5SDimitry Andric template <class _H2, class _P2> 13230b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13240b57cec5SDimitry Andric void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) 13250b57cec5SDimitry Andric { 13260b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13270b57cec5SDimitry Andric "merging container with incompatible allocator"); 13280b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 13290b57cec5SDimitry Andric } 13300b57cec5SDimitry Andric template <class _H2, class _P2> 13310b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13320b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) 13330b57cec5SDimitry Andric { 13340b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13350b57cec5SDimitry Andric "merging container with incompatible allocator"); 13360b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 13370b57cec5SDimitry Andric } 13380b57cec5SDimitry Andric template <class _H2, class _P2> 13390b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13400b57cec5SDimitry Andric void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) 13410b57cec5SDimitry Andric { 13420b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13430b57cec5SDimitry Andric "merging container with incompatible allocator"); 13440b57cec5SDimitry Andric return __table_.__node_handle_merge_multi(__source.__table_); 13450b57cec5SDimitry Andric } 13460b57cec5SDimitry Andric#endif 13470b57cec5SDimitry Andric 13480b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13490b57cec5SDimitry Andric iterator erase(const_iterator __p) {return __table_.erase(__p);} 13500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13510b57cec5SDimitry Andric size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 13520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13530b57cec5SDimitry Andric iterator erase(const_iterator __first, const_iterator __last) 13540b57cec5SDimitry Andric {return __table_.erase(__first, __last);} 13550b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13560b57cec5SDimitry Andric void clear() _NOEXCEPT {__table_.clear();} 13570b57cec5SDimitry Andric 13580b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13590b57cec5SDimitry Andric void swap(unordered_multiset& __u) 13600b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 13610b57cec5SDimitry Andric {__table_.swap(__u.__table_);} 13620b57cec5SDimitry Andric 13630b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13640b57cec5SDimitry Andric hasher hash_function() const {return __table_.hash_function();} 13650b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13660b57cec5SDimitry Andric key_equal key_eq() const {return __table_.key_eq();} 13670b57cec5SDimitry Andric 13680b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13690b57cec5SDimitry Andric iterator find(const key_type& __k) {return __table_.find(__k);} 13700b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13710b57cec5SDimitry Andric const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1372*e8d8bef9SDimitry Andric #if _LIBCPP_STD_VER > 17 1373*e8d8bef9SDimitry Andric template <typename _K2> 1374*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1375*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, iterator> 1376*e8d8bef9SDimitry Andric find(const _K2& __k) {return __table_.find(__k);} 1377*e8d8bef9SDimitry Andric template <typename _K2> 1378*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1379*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, const_iterator> 1380*e8d8bef9SDimitry Andric find(const _K2& __k) const {return __table_.find(__k);} 1381*e8d8bef9SDimitry Andric #endif // _LIBCPP_STD_VER > 17 13820b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13830b57cec5SDimitry Andric size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 13840b57cec5SDimitry Andric #if _LIBCPP_STD_VER > 17 1385*e8d8bef9SDimitry Andric template <typename _K2> 1386*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1387*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, size_type> 1388*e8d8bef9SDimitry Andric count(const _K2& __k) const {return __table_.__count_multi(__k);} 1389*e8d8bef9SDimitry Andric #endif // _LIBCPP_STD_VER > 17 1390*e8d8bef9SDimitry Andric #if _LIBCPP_STD_VER > 17 13910b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13920b57cec5SDimitry Andric bool contains(const key_type& __k) const {return find(__k) != end();} 1393*e8d8bef9SDimitry Andric 1394*e8d8bef9SDimitry Andric template <typename _K2> 1395*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1396*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, bool> 1397*e8d8bef9SDimitry Andric contains(const _K2& __k) const {return find(__k) != end();} 13980b57cec5SDimitry Andric #endif // _LIBCPP_STD_VER > 17 13990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14000b57cec5SDimitry Andric pair<iterator, iterator> equal_range(const key_type& __k) 14010b57cec5SDimitry Andric {return __table_.__equal_range_multi(__k);} 14020b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14030b57cec5SDimitry Andric pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 14040b57cec5SDimitry Andric {return __table_.__equal_range_multi(__k);} 1405*e8d8bef9SDimitry Andric #if _LIBCPP_STD_VER > 17 1406*e8d8bef9SDimitry Andric template <typename _K2> 1407*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1408*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, pair<iterator, iterator>> 1409*e8d8bef9SDimitry Andric equal_range(const _K2& __k) {return __table_.__equal_range_multi(__k);} 1410*e8d8bef9SDimitry Andric template <typename _K2> 1411*e8d8bef9SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1412*e8d8bef9SDimitry Andric _EnableIf<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value, pair<const_iterator, const_iterator>> 1413*e8d8bef9SDimitry Andric equal_range(const _K2& __k) const {return __table_.__equal_range_multi(__k);} 1414*e8d8bef9SDimitry Andric #endif // _LIBCPP_STD_VER > 17 14150b57cec5SDimitry Andric 14160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14170b57cec5SDimitry Andric size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 14180b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14190b57cec5SDimitry Andric size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 14200b57cec5SDimitry Andric 14210b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14220b57cec5SDimitry Andric size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} 14230b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14240b57cec5SDimitry Andric size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 14250b57cec5SDimitry Andric 14260b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14270b57cec5SDimitry Andric local_iterator begin(size_type __n) {return __table_.begin(__n);} 14280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14290b57cec5SDimitry Andric local_iterator end(size_type __n) {return __table_.end(__n);} 14300b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14310b57cec5SDimitry Andric const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 14320b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14330b57cec5SDimitry Andric const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 14340b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14350b57cec5SDimitry Andric const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 14360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14370b57cec5SDimitry Andric const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 14380b57cec5SDimitry Andric 14390b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14400b57cec5SDimitry Andric float load_factor() const _NOEXCEPT {return __table_.load_factor();} 14410b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14420b57cec5SDimitry Andric float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 14430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14440b57cec5SDimitry Andric void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 14450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14460b57cec5SDimitry Andric void rehash(size_type __n) {__table_.rehash(__n);} 14470b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14480b57cec5SDimitry Andric void reserve(size_type __n) {__table_.reserve(__n);} 14490b57cec5SDimitry Andric 1450*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 14510b57cec5SDimitry Andric 14520b57cec5SDimitry Andric bool __dereferenceable(const const_iterator* __i) const 14530b57cec5SDimitry Andric {return __table_.__dereferenceable(__i);} 14540b57cec5SDimitry Andric bool __decrementable(const const_iterator* __i) const 14550b57cec5SDimitry Andric {return __table_.__decrementable(__i);} 14560b57cec5SDimitry Andric bool __addable(const const_iterator* __i, ptrdiff_t __n) const 14570b57cec5SDimitry Andric {return __table_.__addable(__i, __n);} 14580b57cec5SDimitry Andric bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 14590b57cec5SDimitry Andric {return __table_.__addable(__i, __n);} 14600b57cec5SDimitry Andric 1461*e8d8bef9SDimitry Andric#endif // _LIBCPP_DEBUG_LEVEL == 2 14620b57cec5SDimitry Andric 14630b57cec5SDimitry Andric}; 14640b57cec5SDimitry Andric 14650b57cec5SDimitry Andric#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 14660b57cec5SDimitry Andrictemplate<class _InputIterator, 14670b57cec5SDimitry Andric class _Hash = hash<__iter_value_type<_InputIterator>>, 14680b57cec5SDimitry Andric class _Pred = equal_to<__iter_value_type<_InputIterator>>, 14690b57cec5SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 14700b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 14710b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 14720b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Pred>::value>, 14730b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 14740b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, 14750b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 14760b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; 14770b57cec5SDimitry Andric 14780b57cec5SDimitry Andrictemplate<class _Tp, class _Hash = hash<_Tp>, 14790b57cec5SDimitry Andric class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>, 14800b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 14810b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 14820b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Pred>::value>, 14830b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 14840b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, 14850b57cec5SDimitry Andric _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 14860b57cec5SDimitry Andric -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 14870b57cec5SDimitry Andric 14880b57cec5SDimitry Andrictemplate<class _InputIterator, class _Allocator, 14890b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 14900b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) 14910b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, 14920b57cec5SDimitry Andric hash<__iter_value_type<_InputIterator>>, 14930b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 14940b57cec5SDimitry Andric _Allocator>; 14950b57cec5SDimitry Andric 14960b57cec5SDimitry Andrictemplate<class _InputIterator, class _Hash, class _Allocator, 14970b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 14980b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 14990b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 15000b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, 15010b57cec5SDimitry Andric _Hash, _Allocator) 15020b57cec5SDimitry Andric -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, 15030b57cec5SDimitry Andric equal_to<__iter_value_type<_InputIterator>>, 15040b57cec5SDimitry Andric _Allocator>; 15050b57cec5SDimitry Andric 15060b57cec5SDimitry Andrictemplate<class _Tp, class _Allocator, 15070b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 15080b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) 15090b57cec5SDimitry Andric -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 15100b57cec5SDimitry Andric 15110b57cec5SDimitry Andrictemplate<class _Tp, class _Hash, class _Allocator, 15120b57cec5SDimitry Andric class = _EnableIf<!__is_allocator<_Hash>::value>, 15130b57cec5SDimitry Andric class = _EnableIf<!is_integral<_Hash>::value>, 15140b57cec5SDimitry Andric class = _EnableIf<__is_allocator<_Allocator>::value>> 15150b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) 15160b57cec5SDimitry Andric -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 15170b57cec5SDimitry Andric#endif 15180b57cec5SDimitry Andric 15190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15200b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15210b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql) 15220b57cec5SDimitry Andric : __table_(__hf, __eql) 15230b57cec5SDimitry Andric{ 1524*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15250b57cec5SDimitry Andric __get_db()->__insert_c(this); 15260b57cec5SDimitry Andric#endif 15270b57cec5SDimitry Andric __table_.rehash(__n); 15280b57cec5SDimitry Andric} 15290b57cec5SDimitry Andric 15300b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15310b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15320b57cec5SDimitry Andric size_type __n, const hasher& __hf, const key_equal& __eql, 15330b57cec5SDimitry Andric const allocator_type& __a) 15340b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 15350b57cec5SDimitry Andric{ 1536*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15370b57cec5SDimitry Andric __get_db()->__insert_c(this); 15380b57cec5SDimitry Andric#endif 15390b57cec5SDimitry Andric __table_.rehash(__n); 15400b57cec5SDimitry Andric} 15410b57cec5SDimitry Andric 15420b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15430b57cec5SDimitry Andrictemplate <class _InputIterator> 15440b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15450b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last) 15460b57cec5SDimitry Andric{ 1547*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15480b57cec5SDimitry Andric __get_db()->__insert_c(this); 15490b57cec5SDimitry Andric#endif 15500b57cec5SDimitry Andric insert(__first, __last); 15510b57cec5SDimitry Andric} 15520b57cec5SDimitry Andric 15530b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15540b57cec5SDimitry Andrictemplate <class _InputIterator> 15550b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15560b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 15570b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql) 15580b57cec5SDimitry Andric : __table_(__hf, __eql) 15590b57cec5SDimitry Andric{ 1560*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15610b57cec5SDimitry Andric __get_db()->__insert_c(this); 15620b57cec5SDimitry Andric#endif 15630b57cec5SDimitry Andric __table_.rehash(__n); 15640b57cec5SDimitry Andric insert(__first, __last); 15650b57cec5SDimitry Andric} 15660b57cec5SDimitry Andric 15670b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15680b57cec5SDimitry Andrictemplate <class _InputIterator> 15690b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15700b57cec5SDimitry Andric _InputIterator __first, _InputIterator __last, size_type __n, 15710b57cec5SDimitry Andric const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 15720b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 15730b57cec5SDimitry Andric{ 1574*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15750b57cec5SDimitry Andric __get_db()->__insert_c(this); 15760b57cec5SDimitry Andric#endif 15770b57cec5SDimitry Andric __table_.rehash(__n); 15780b57cec5SDimitry Andric insert(__first, __last); 15790b57cec5SDimitry Andric} 15800b57cec5SDimitry Andric 15810b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15820b57cec5SDimitry Andricinline 15830b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15840b57cec5SDimitry Andric const allocator_type& __a) 15850b57cec5SDimitry Andric : __table_(__a) 15860b57cec5SDimitry Andric{ 1587*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15880b57cec5SDimitry Andric __get_db()->__insert_c(this); 15890b57cec5SDimitry Andric#endif 15900b57cec5SDimitry Andric} 15910b57cec5SDimitry Andric 15920b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 15930b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 15940b57cec5SDimitry Andric const unordered_multiset& __u) 15950b57cec5SDimitry Andric : __table_(__u.__table_) 15960b57cec5SDimitry Andric{ 1597*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 15980b57cec5SDimitry Andric __get_db()->__insert_c(this); 15990b57cec5SDimitry Andric#endif 16000b57cec5SDimitry Andric __table_.rehash(__u.bucket_count()); 16010b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16020b57cec5SDimitry Andric} 16030b57cec5SDimitry Andric 16040b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16050b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16060b57cec5SDimitry Andric const unordered_multiset& __u, const allocator_type& __a) 16070b57cec5SDimitry Andric : __table_(__u.__table_, __a) 16080b57cec5SDimitry Andric{ 1609*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16100b57cec5SDimitry Andric __get_db()->__insert_c(this); 16110b57cec5SDimitry Andric#endif 16120b57cec5SDimitry Andric __table_.rehash(__u.bucket_count()); 16130b57cec5SDimitry Andric insert(__u.begin(), __u.end()); 16140b57cec5SDimitry Andric} 16150b57cec5SDimitry Andric 16160b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 16170b57cec5SDimitry Andric 16180b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16190b57cec5SDimitry Andricinline 16200b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16210b57cec5SDimitry Andric unordered_multiset&& __u) 16220b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 16230b57cec5SDimitry Andric : __table_(_VSTD::move(__u.__table_)) 16240b57cec5SDimitry Andric{ 1625*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16260b57cec5SDimitry Andric __get_db()->__insert_c(this); 16270b57cec5SDimitry Andric __get_db()->swap(this, &__u); 16280b57cec5SDimitry Andric#endif 16290b57cec5SDimitry Andric} 16300b57cec5SDimitry Andric 16310b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16320b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16330b57cec5SDimitry Andric unordered_multiset&& __u, const allocator_type& __a) 16340b57cec5SDimitry Andric : __table_(_VSTD::move(__u.__table_), __a) 16350b57cec5SDimitry Andric{ 1636*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16370b57cec5SDimitry Andric __get_db()->__insert_c(this); 16380b57cec5SDimitry Andric#endif 16390b57cec5SDimitry Andric if (__a != __u.get_allocator()) 16400b57cec5SDimitry Andric { 16410b57cec5SDimitry Andric iterator __i = __u.begin(); 16420b57cec5SDimitry Andric while (__u.size() != 0) 16430b57cec5SDimitry Andric __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); 16440b57cec5SDimitry Andric } 1645*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16460b57cec5SDimitry Andric else 16470b57cec5SDimitry Andric __get_db()->swap(this, &__u); 16480b57cec5SDimitry Andric#endif 16490b57cec5SDimitry Andric} 16500b57cec5SDimitry Andric 16510b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16520b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16530b57cec5SDimitry Andric initializer_list<value_type> __il) 16540b57cec5SDimitry Andric{ 1655*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16560b57cec5SDimitry Andric __get_db()->__insert_c(this); 16570b57cec5SDimitry Andric#endif 16580b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 16590b57cec5SDimitry Andric} 16600b57cec5SDimitry Andric 16610b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16620b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16630b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 16640b57cec5SDimitry Andric const key_equal& __eql) 16650b57cec5SDimitry Andric : __table_(__hf, __eql) 16660b57cec5SDimitry Andric{ 1667*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16680b57cec5SDimitry Andric __get_db()->__insert_c(this); 16690b57cec5SDimitry Andric#endif 16700b57cec5SDimitry Andric __table_.rehash(__n); 16710b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 16720b57cec5SDimitry Andric} 16730b57cec5SDimitry Andric 16740b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16750b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( 16760b57cec5SDimitry Andric initializer_list<value_type> __il, size_type __n, const hasher& __hf, 16770b57cec5SDimitry Andric const key_equal& __eql, const allocator_type& __a) 16780b57cec5SDimitry Andric : __table_(__hf, __eql, __a) 16790b57cec5SDimitry Andric{ 1680*e8d8bef9SDimitry Andric#if _LIBCPP_DEBUG_LEVEL == 2 16810b57cec5SDimitry Andric __get_db()->__insert_c(this); 16820b57cec5SDimitry Andric#endif 16830b57cec5SDimitry Andric __table_.rehash(__n); 16840b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 16850b57cec5SDimitry Andric} 16860b57cec5SDimitry Andric 16870b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16880b57cec5SDimitry Andricinline 16890b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 16900b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 16910b57cec5SDimitry Andric unordered_multiset&& __u) 16920b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 16930b57cec5SDimitry Andric{ 16940b57cec5SDimitry Andric __table_ = _VSTD::move(__u.__table_); 16950b57cec5SDimitry Andric return *this; 16960b57cec5SDimitry Andric} 16970b57cec5SDimitry Andric 16980b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 16990b57cec5SDimitry Andricinline 17000b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>& 17010b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( 17020b57cec5SDimitry Andric initializer_list<value_type> __il) 17030b57cec5SDimitry Andric{ 17040b57cec5SDimitry Andric __table_.__assign_multi(__il.begin(), __il.end()); 17050b57cec5SDimitry Andric return *this; 17060b57cec5SDimitry Andric} 17070b57cec5SDimitry Andric 17080b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 17090b57cec5SDimitry Andric 17100b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17110b57cec5SDimitry Andrictemplate <class _InputIterator> 17120b57cec5SDimitry Andricinline 17130b57cec5SDimitry Andricvoid 17140b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 17150b57cec5SDimitry Andric _InputIterator __last) 17160b57cec5SDimitry Andric{ 17170b57cec5SDimitry Andric for (; __first != __last; ++__first) 17180b57cec5SDimitry Andric __table_.__insert_multi(*__first); 17190b57cec5SDimitry Andric} 17200b57cec5SDimitry Andric 17210b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17220b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 17230b57cec5SDimitry Andricvoid 17240b57cec5SDimitry Andricswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 17250b57cec5SDimitry Andric unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 17260b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 17270b57cec5SDimitry Andric{ 17280b57cec5SDimitry Andric __x.swap(__y); 17290b57cec5SDimitry Andric} 17300b57cec5SDimitry Andric 17310b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 17325ffd83dbSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, 17335ffd83dbSDimitry Andric class _Predicate> 17340b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 17355ffd83dbSDimitry Andric typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type 17365ffd83dbSDimitry Andric erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, 17375ffd83dbSDimitry Andric _Predicate __pred) { 17385ffd83dbSDimitry Andric return __libcpp_erase_if_container(__c, __pred); 17395ffd83dbSDimitry Andric} 17400b57cec5SDimitry Andric#endif 17410b57cec5SDimitry Andric 17420b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17430b57cec5SDimitry Andricbool 17440b57cec5SDimitry Andricoperator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 17450b57cec5SDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 17460b57cec5SDimitry Andric{ 17470b57cec5SDimitry Andric if (__x.size() != __y.size()) 17480b57cec5SDimitry Andric return false; 17490b57cec5SDimitry Andric typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator 17500b57cec5SDimitry Andric const_iterator; 17510b57cec5SDimitry Andric typedef pair<const_iterator, const_iterator> _EqRng; 17520b57cec5SDimitry Andric for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 17530b57cec5SDimitry Andric { 17540b57cec5SDimitry Andric _EqRng __xeq = __x.equal_range(*__i); 17550b57cec5SDimitry Andric _EqRng __yeq = __y.equal_range(*__i); 17560b57cec5SDimitry Andric if (_VSTD::distance(__xeq.first, __xeq.second) != 17570b57cec5SDimitry Andric _VSTD::distance(__yeq.first, __yeq.second) || 17580b57cec5SDimitry Andric !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 17590b57cec5SDimitry Andric return false; 17600b57cec5SDimitry Andric __i = __xeq.second; 17610b57cec5SDimitry Andric } 17620b57cec5SDimitry Andric return true; 17630b57cec5SDimitry Andric} 17640b57cec5SDimitry Andric 17650b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc> 17660b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 17670b57cec5SDimitry Andricbool 17680b57cec5SDimitry Andricoperator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 17690b57cec5SDimitry Andric const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 17700b57cec5SDimitry Andric{ 17710b57cec5SDimitry Andric return !(__x == __y); 17720b57cec5SDimitry Andric} 17730b57cec5SDimitry Andric 17740b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 17750b57cec5SDimitry Andric 17760b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_SET 1777