diff options
Diffstat (limited to 'contrib/llvm-project/libcxx/include/map')
| -rw-r--r-- | contrib/llvm-project/libcxx/include/map | 2618 |
1 files changed, 1137 insertions, 1481 deletions
diff --git a/contrib/llvm-project/libcxx/include/map b/contrib/llvm-project/libcxx/include/map index 82a296f9cb8d..f122f2ebb15b 100644 --- a/contrib/llvm-project/libcxx/include/map +++ b/contrib/llvm-project/libcxx/include/map @@ -619,266 +619,220 @@ erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20 _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Key, class _CP, class _Compare, +template <class _Key, + class _CP, + class _Compare, bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value> -class __map_value_compare - : private _Compare -{ +class __map_value_compare : private _Compare { public: - _LIBCPP_HIDE_FROM_ABI - __map_value_compare() - _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) - : _Compare() {} - _LIBCPP_HIDE_FROM_ABI - __map_value_compare(_Compare __c) - _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) - : _Compare(__c) {} - _LIBCPP_HIDE_FROM_ABI - const _Compare& key_comp() const _NOEXCEPT {return *this;} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _CP& __x, const _CP& __y) const - {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _CP& __x, const _Key& __y) const - {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _Key& __x, const _CP& __y) const - {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);} - _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) - _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) - { - using std::swap; - swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); - } + _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) + : _Compare() {} + _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) + : _Compare(__c) {} + _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { + return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { + return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { + return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first); + } + _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) { + using std::swap; + swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y)); + } #if _LIBCPP_STD_VER >= 14 - template <typename _K2> - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _K2& __x, const _CP& __y) const - {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);} - - template <typename _K2> - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _CP& __x, const _K2& __y) const - {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);} + template <typename _K2> + _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const { + return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first); + } + + template <typename _K2> + _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const { + return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y); + } #endif }; template <class _Key, class _CP, class _Compare> -class __map_value_compare<_Key, _CP, _Compare, false> -{ - _Compare __comp_; +class __map_value_compare<_Key, _CP, _Compare, false> { + _Compare __comp_; public: - _LIBCPP_HIDE_FROM_ABI - __map_value_compare() - _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) - : __comp_() {} - _LIBCPP_HIDE_FROM_ABI - __map_value_compare(_Compare __c) - _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) - : __comp_(__c) {} - _LIBCPP_HIDE_FROM_ABI - const _Compare& key_comp() const _NOEXCEPT {return __comp_;} - - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _CP& __x, const _CP& __y) const - {return __comp_(__x.__get_value().first, __y.__get_value().first);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _CP& __x, const _Key& __y) const - {return __comp_(__x.__get_value().first, __y);} - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _Key& __x, const _CP& __y) const - {return __comp_(__x, __y.__get_value().first);} - void swap(__map_value_compare& __y) - _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) - { - using std::swap; - swap(__comp_, __y.__comp_); - } + _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value) + : __comp_() {} + _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value) + : __comp_(__c) {} + _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; } + + _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { + return __comp_(__x.__get_value().first, __y.__get_value().first); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { + return __comp_(__x.__get_value().first, __y); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { + return __comp_(__x, __y.__get_value().first); + } + void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) { + using std::swap; + swap(__comp_, __y.__comp_); + } #if _LIBCPP_STD_VER >= 14 - template <typename _K2> - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _K2& __x, const _CP& __y) const - {return __comp_(__x, __y.__get_value().first);} - - template <typename _K2> - _LIBCPP_HIDE_FROM_ABI - bool operator()(const _CP& __x, const _K2& __y) const - {return __comp_(__x.__get_value().first, __y);} + template <typename _K2> + _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const { + return __comp_(__x, __y.__get_value().first); + } + + template <typename _K2> + _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const { + return __comp_(__x.__get_value().first, __y); + } #endif }; template <class _Key, class _CP, class _Compare, bool __b> -inline _LIBCPP_HIDE_FROM_ABI -void -swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, - __map_value_compare<_Key, _CP, _Compare, __b>& __y) - _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) -{ - __x.swap(__y); +inline _LIBCPP_HIDE_FROM_ABI void +swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y) + _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { + __x.swap(__y); } template <class _Allocator> -class __map_node_destructor -{ - typedef _Allocator allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; +class __map_node_destructor { + typedef _Allocator allocator_type; + typedef allocator_traits<allocator_type> __alloc_traits; public: - typedef typename __alloc_traits::pointer pointer; + typedef typename __alloc_traits::pointer pointer; private: - allocator_type& __na_; + allocator_type& __na_; - __map_node_destructor& operator=(const __map_node_destructor&); + __map_node_destructor& operator=(const __map_node_destructor&); public: - bool __first_constructed; - bool __second_constructed; + bool __first_constructed; + bool __second_constructed; - _LIBCPP_HIDE_FROM_ABI - explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT - : __na_(__na), - __first_constructed(false), - __second_constructed(false) - {} + _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT + : __na_(__na), + __first_constructed(false), + __second_constructed(false) {} #ifndef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT - : __na_(__x.__na_), - __first_constructed(__x.__value_constructed), - __second_constructed(__x.__value_constructed) - { - __x.__value_constructed = false; - } + _LIBCPP_HIDE_FROM_ABI __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT + : __na_(__x.__na_), + __first_constructed(__x.__value_constructed), + __second_constructed(__x.__value_constructed) { + __x.__value_constructed = false; + } #endif // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - void operator()(pointer __p) _NOEXCEPT - { - if (__second_constructed) - __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second)); - if (__first_constructed) - __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first)); - if (__p) - __alloc_traits::deallocate(__na_, __p, 1); - } + _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { + if (__second_constructed) + __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second)); + if (__first_constructed) + __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first)); + if (__p) + __alloc_traits::deallocate(__na_, __p, 1); + } }; template <class _Key, class _Tp, class _Compare, class _Allocator> - class map; +class map; template <class _Key, class _Tp, class _Compare, class _Allocator> - class multimap; -template <class _TreeIterator> class __map_const_iterator; +class multimap; +template <class _TreeIterator> +class __map_const_iterator; #ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp> -struct _LIBCPP_STANDALONE_DEBUG __value_type -{ - typedef _Key key_type; - typedef _Tp mapped_type; - typedef pair<const key_type, mapped_type> value_type; - typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; - typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; +struct _LIBCPP_STANDALONE_DEBUG __value_type { + typedef _Key key_type; + typedef _Tp mapped_type; + typedef pair<const key_type, mapped_type> value_type; + typedef pair<key_type&, mapped_type&> __nc_ref_pair_type; + typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type; private: - value_type __cc_; + value_type __cc_; public: - _LIBCPP_HIDE_FROM_ABI - value_type& __get_value() - { -#if _LIBCPP_STD_VER >= 17 - return *std::launder(std::addressof(__cc_)); -#else - return __cc_; -#endif - } - - _LIBCPP_HIDE_FROM_ABI - const value_type& __get_value() const - { -#if _LIBCPP_STD_VER >= 17 - return *std::launder(std::addressof(__cc_)); -#else - return __cc_; -#endif - } - - _LIBCPP_HIDE_FROM_ABI - __nc_ref_pair_type __ref() - { - value_type& __v = __get_value(); - return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); - } - - _LIBCPP_HIDE_FROM_ABI - __nc_rref_pair_type __move() - { - value_type& __v = __get_value(); - return __nc_rref_pair_type( - std::move(const_cast<key_type&>(__v.first)), - std::move(__v.second)); - } - - _LIBCPP_HIDE_FROM_ABI - __value_type& operator=(const __value_type& __v) - { - __ref() = __v.__get_value(); - return *this; - } - - _LIBCPP_HIDE_FROM_ABI - __value_type& operator=(__value_type&& __v) - { - __ref() = __v.__move(); - return *this; - } - - template <class _ValueTp, - class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value> - > - _LIBCPP_HIDE_FROM_ABI - __value_type& operator=(_ValueTp&& __v) - { - __ref() = std::forward<_ValueTp>(__v); - return *this; - } + _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { +# if _LIBCPP_STD_VER >= 17 + return *std::launder(std::addressof(__cc_)); +# else + return __cc_; +# endif + } + + _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { +# if _LIBCPP_STD_VER >= 17 + return *std::launder(std::addressof(__cc_)); +# else + return __cc_; +# endif + } + + _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() { + value_type& __v = __get_value(); + return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second); + } + + _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() { + value_type& __v = __get_value(); + return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second)); + } + + _LIBCPP_HIDE_FROM_ABI __value_type& operator=(const __value_type& __v) { + __ref() = __v.__get_value(); + return *this; + } + + _LIBCPP_HIDE_FROM_ABI __value_type& operator=(__value_type&& __v) { + __ref() = __v.__move(); + return *this; + } + + template <class _ValueTp, class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value> > + _LIBCPP_HIDE_FROM_ABI __value_type& operator=(_ValueTp&& __v) { + __ref() = std::forward<_ValueTp>(__v); + return *this; + } private: - __value_type() = delete; - ~__value_type() = delete; - __value_type(const __value_type&) = delete; - __value_type(__value_type&&) = delete; + __value_type() = delete; + ~__value_type() = delete; + __value_type(const __value_type&) = delete; + __value_type(__value_type&&) = delete; }; #else template <class _Key, class _Tp> -struct __value_type -{ - typedef _Key key_type; - typedef _Tp mapped_type; - typedef pair<const key_type, mapped_type> value_type; +struct __value_type { + typedef _Key key_type; + typedef _Tp mapped_type; + typedef pair<const key_type, mapped_type> value_type; private: - value_type __cc_; + value_type __cc_; public: - _LIBCPP_HIDE_FROM_ABI - value_type& __get_value() { return __cc_; } - _LIBCPP_HIDE_FROM_ABI - const value_type& __get_value() const { return __cc_; } + _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; } + _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; } private: - __value_type(); - __value_type(__value_type const&); - __value_type& operator=(__value_type const&); - ~__value_type(); + __value_type(); + __value_type(__value_type const&); + __value_type& operator=(__value_type const&); + ~__value_type(); }; #endif // _LIBCPP_CXX03_LANG @@ -887,937 +841,778 @@ template <class _Tp> struct __extract_key_value_types; template <class _Key, class _Tp> -struct __extract_key_value_types<__value_type<_Key, _Tp> > -{ +struct __extract_key_value_types<__value_type<_Key, _Tp> > { typedef _Key const __key_type; - typedef _Tp __mapped_type; + typedef _Tp __mapped_type; }; template <class _TreeIterator> -class _LIBCPP_TEMPLATE_VIS __map_iterator -{ - typedef typename _TreeIterator::_NodeTypes _NodeTypes; - typedef typename _TreeIterator::__pointer_traits __pointer_traits; +class _LIBCPP_TEMPLATE_VIS __map_iterator { + typedef typename _TreeIterator::_NodeTypes _NodeTypes; + typedef typename _TreeIterator::__pointer_traits __pointer_traits; - _TreeIterator __i_; + _TreeIterator __i_; public: - typedef bidirectional_iterator_tag iterator_category; - typedef typename _NodeTypes::__map_value_type value_type; - typedef typename _TreeIterator::difference_type difference_type; - typedef value_type& reference; - typedef typename _NodeTypes::__map_value_type_pointer pointer; - - _LIBCPP_HIDE_FROM_ABI - __map_iterator() _NOEXCEPT {} - - _LIBCPP_HIDE_FROM_ABI - __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} - - _LIBCPP_HIDE_FROM_ABI - reference operator*() const {return __i_->__get_value();} - _LIBCPP_HIDE_FROM_ABI - pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} - - _LIBCPP_HIDE_FROM_ABI - __map_iterator& operator++() {++__i_; return *this;} - _LIBCPP_HIDE_FROM_ABI - __map_iterator operator++(int) - { - __map_iterator __t(*this); - ++(*this); - return __t; - } - - _LIBCPP_HIDE_FROM_ABI - __map_iterator& operator--() {--__i_; return *this;} - _LIBCPP_HIDE_FROM_ABI - __map_iterator operator--(int) - { - __map_iterator __t(*this); - --(*this); - return __t; - } - - friend _LIBCPP_HIDE_FROM_ABI - bool operator==(const __map_iterator& __x, const __map_iterator& __y) - {return __x.__i_ == __y.__i_;} - friend - _LIBCPP_HIDE_FROM_ABI - bool operator!=(const __map_iterator& __x, const __map_iterator& __y) - {return __x.__i_ != __y.__i_;} - - template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; - template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; - template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; + typedef bidirectional_iterator_tag iterator_category; + typedef typename _NodeTypes::__map_value_type value_type; + typedef typename _TreeIterator::difference_type difference_type; + typedef value_type& reference; + typedef typename _NodeTypes::__map_value_type_pointer pointer; + + _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {} + + _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } + + _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() { + ++__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) { + __map_iterator __t(*this); + ++(*this); + return __t; + } + + _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() { + --__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) { + __map_iterator __t(*this); + --(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) { + return __x.__i_ == __y.__i_; + } + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) { + return __x.__i_ != __y.__i_; + } + + template <class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS multimap; + template <class> + friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator; }; template <class _TreeIterator> -class _LIBCPP_TEMPLATE_VIS __map_const_iterator -{ - typedef typename _TreeIterator::_NodeTypes _NodeTypes; - typedef typename _TreeIterator::__pointer_traits __pointer_traits; +class _LIBCPP_TEMPLATE_VIS __map_const_iterator { + typedef typename _TreeIterator::_NodeTypes _NodeTypes; + typedef typename _TreeIterator::__pointer_traits __pointer_traits; - _TreeIterator __i_; + _TreeIterator __i_; public: - typedef bidirectional_iterator_tag iterator_category; - typedef typename _NodeTypes::__map_value_type value_type; - typedef typename _TreeIterator::difference_type difference_type; - typedef const value_type& reference; - typedef typename _NodeTypes::__const_map_value_type_pointer pointer; - - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator() _NOEXCEPT {} - - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator(__map_iterator< - typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT - : __i_(__i.__i_) {} - - _LIBCPP_HIDE_FROM_ABI - reference operator*() const {return __i_->__get_value();} - _LIBCPP_HIDE_FROM_ABI - pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());} - - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator& operator++() {++__i_; return *this;} - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator operator++(int) - { - __map_const_iterator __t(*this); - ++(*this); - return __t; - } - - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator& operator--() {--__i_; return *this;} - _LIBCPP_HIDE_FROM_ABI - __map_const_iterator operator--(int) - { - __map_const_iterator __t(*this); - --(*this); - return __t; - } - - friend _LIBCPP_HIDE_FROM_ABI - bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) - {return __x.__i_ == __y.__i_;} - friend _LIBCPP_HIDE_FROM_ABI - bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) - {return __x.__i_ != __y.__i_;} - - template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; - template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; - template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; + typedef bidirectional_iterator_tag iterator_category; + typedef typename _NodeTypes::__map_value_type value_type; + typedef typename _TreeIterator::difference_type difference_type; + typedef const value_type& reference; + typedef typename _NodeTypes::__const_map_value_type_pointer pointer; + + _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {} + + _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {} + _LIBCPP_HIDE_FROM_ABI + __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); } + + _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() { + ++__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) { + __map_const_iterator __t(*this); + ++(*this); + return __t; + } + + _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() { + --__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) { + __map_const_iterator __t(*this); + --(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) { + return __x.__i_ == __y.__i_; + } + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) { + return __x.__i_ != __y.__i_; + } + + template <class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class, class, class, class> + friend class _LIBCPP_TEMPLATE_VIS multimap; + template <class, class, class> + friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; }; -template <class _Key, class _Tp, class _Compare = less<_Key>, - class _Allocator = allocator<pair<const _Key, _Tp> > > -class _LIBCPP_TEMPLATE_VIS map -{ +template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > > +class _LIBCPP_TEMPLATE_VIS map { public: - // types: - typedef _Key key_type; - typedef _Tp mapped_type; - typedef pair<const key_type, mapped_type> value_type; - typedef __type_identity_t<_Compare> key_compare; - typedef __type_identity_t<_Allocator> allocator_type; - typedef value_type& reference; - typedef const value_type& const_reference; + // types: + typedef _Key key_type; + typedef _Tp mapped_type; + typedef pair<const key_type, mapped_type> value_type; + typedef __type_identity_t<_Compare> key_compare; + typedef __type_identity_t<_Allocator> allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; - static_assert((is_same<typename allocator_type::value_type, value_type>::value), - "Allocator::value_type must be same type as value_type"); + static_assert((is_same<typename allocator_type::value_type, value_type>::value), + "Allocator::value_type must be same type as value_type"); - class _LIBCPP_TEMPLATE_VIS value_compare - : public __binary_function<value_type, value_type, bool> - { - friend class map; - protected: - key_compare comp; + class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> { + friend class map; - _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {} - public: - _LIBCPP_HIDE_FROM_ABI - bool operator()(const value_type& __x, const value_type& __y) const - {return comp(__x.first, __y.first);} - }; + protected: + key_compare comp; -private: + _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {} - typedef std::__value_type<key_type, mapped_type> __value_type; - typedef __map_value_compare<key_type, __value_type, key_compare> __vc; - typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; - typedef __tree<__value_type, __vc, __allocator_type> __base; - typedef typename __base::__node_traits __node_traits; - typedef allocator_traits<allocator_type> __alloc_traits; + public: + _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const { + return comp(__x.first, __y.first); + } + }; - static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, - "[allocator.requirements] states that rebinding an allocator to the same type should result in the " - "original allocator"); +private: + typedef std::__value_type<key_type, mapped_type> __value_type; + typedef __map_value_compare<key_type, __value_type, key_compare> __vc; + typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; + typedef __tree<__value_type, __vc, __allocator_type> __base; + typedef typename __base::__node_traits __node_traits; + typedef allocator_traits<allocator_type> __alloc_traits; - __base __tree_; + static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, + "[allocator.requirements] states that rebinding an allocator to the same type should result in the " + "original allocator"); + + __base __tree_; public: - typedef typename __alloc_traits::pointer pointer; - typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; - typedef __map_iterator<typename __base::iterator> iterator; - typedef __map_const_iterator<typename __base::const_iterator> const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef typename __alloc_traits::pointer pointer; + typedef typename __alloc_traits::const_pointer const_pointer; + typedef typename __alloc_traits::size_type size_type; + typedef typename __alloc_traits::difference_type difference_type; + typedef __map_iterator<typename __base::iterator> iterator; + typedef __map_const_iterator<typename __base::const_iterator> const_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; #if _LIBCPP_STD_VER >= 17 - typedef __map_node_handle<typename __base::__node, allocator_type> node_type; - typedef __insert_return_type<iterator, node_type> insert_return_type; + typedef __map_node_handle<typename __base::__node, allocator_type> node_type; + typedef __insert_return_type<iterator, node_type> insert_return_type; #endif - template <class _Key2, class _Value2, class _Comp2, class _Alloc2> - friend class _LIBCPP_TEMPLATE_VIS map; - template <class _Key2, class _Value2, class _Comp2, class _Alloc2> - friend class _LIBCPP_TEMPLATE_VIS multimap; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multimap; - _LIBCPP_HIDE_FROM_ABI - map() - _NOEXCEPT_( - is_nothrow_default_constructible<allocator_type>::value && - is_nothrow_default_constructible<key_compare>::value && - is_nothrow_copy_constructible<key_compare>::value) - : __tree_(__vc(key_compare())) {} + _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_( + is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&& + is_nothrow_copy_constructible<key_compare>::value) + : __tree_(__vc(key_compare())) {} - _LIBCPP_HIDE_FROM_ABI - explicit map(const key_compare& __comp) - _NOEXCEPT_( - is_nothrow_default_constructible<allocator_type>::value && - is_nothrow_copy_constructible<key_compare>::value) - : __tree_(__vc(__comp)) {} - - _LIBCPP_HIDE_FROM_ABI - explicit map(const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} - - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - map(_InputIterator __f, _InputIterator __l, - const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) - { - insert(__f, __l); - } - - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - map(_InputIterator __f, _InputIterator __l, - const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), typename __base::allocator_type(__a)) - { - insert(__f, __l); - } + _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_( + is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value) + : __tree_(__vc(__comp)) {} + + _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} + + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare()) + : __tree_(__vc(__comp)) { + insert(__f, __l); + } + + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI + map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { + insert(__f, __l); + } #if _LIBCPP_STD_VER >= 23 - template <_ContainerCompatibleRange<value_type> _Range> - _LIBCPP_HIDE_FROM_ABI - map(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(), - const allocator_type& __a = allocator_type()) + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI + map(from_range_t, + _Range&& __range, + const key_compare& __comp = key_compare(), + const allocator_type& __a = allocator_type()) : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { - insert_range(std::forward<_Range>(__range)); - } + insert_range(std::forward<_Range>(__range)); + } #endif #if _LIBCPP_STD_VER >= 14 - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) - : map(__f, __l, key_compare(), __a) {} + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a) + : map(__f, __l, key_compare(), __a) {} #endif #if _LIBCPP_STD_VER >= 23 - template <_ContainerCompatibleRange<value_type> _Range> - _LIBCPP_HIDE_FROM_ABI - map(from_range_t, _Range&& __range, const allocator_type& __a) + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a) : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {} #endif - _LIBCPP_HIDE_FROM_ABI - map(const map& __m) - : __tree_(__m.__tree_) - { - insert(__m.begin(), __m.end()); - } + _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); } - _LIBCPP_HIDE_FROM_ABI - map& operator=(const map& __m) - { + _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) { #ifndef _LIBCPP_CXX03_LANG - __tree_ = __m.__tree_; + __tree_ = __m.__tree_; #else - if (this != std::addressof(__m)) { - __tree_.clear(); - __tree_.value_comp() = __m.__tree_.value_comp(); - __tree_.__copy_assign_alloc(__m.__tree_); - insert(__m.begin(), __m.end()); - } + if (this != std::addressof(__m)) { + __tree_.clear(); + __tree_.value_comp() = __m.__tree_.value_comp(); + __tree_.__copy_assign_alloc(__m.__tree_); + insert(__m.begin(), __m.end()); + } #endif - return *this; - } + return *this; + } #ifndef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - map(map&& __m) - _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) - : __tree_(std::move(__m.__tree_)) - { - } - - _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a); - - _LIBCPP_HIDE_FROM_ABI - map& operator=(map&& __m) - _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) - { - __tree_ = std::move(__m.__tree_); - return *this; - } - - _LIBCPP_HIDE_FROM_ABI - map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) - { - insert(__il.begin(), __il.end()); - } - - _LIBCPP_HIDE_FROM_ABI - map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), typename __base::allocator_type(__a)) - { - insert(__il.begin(), __il.end()); - } + _LIBCPP_HIDE_FROM_ABI map(map&& __m) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) + : __tree_(std::move(__m.__tree_)) {} -#if _LIBCPP_STD_VER >= 14 - _LIBCPP_HIDE_FROM_ABI - map(initializer_list<value_type> __il, const allocator_type& __a) - : map(__il, key_compare(), __a) {} -#endif + _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a); + + _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) { + __tree_ = std::move(__m.__tree_); + return *this; + } + + _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) + : __tree_(__vc(__comp)) { + insert(__il.begin(), __il.end()); + } + + _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { + insert(__il.begin(), __il.end()); + } + +# if _LIBCPP_STD_VER >= 14 + _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a) + : map(__il, key_compare(), __a) {} +# endif - _LIBCPP_HIDE_FROM_ABI - map& operator=(initializer_list<value_type> __il) - { - __tree_.__assign_unique(__il.begin(), __il.end()); - return *this; - } + _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) { + __tree_.__assign_unique(__il.begin(), __il.end()); + return *this; + } #endif // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - explicit map(const allocator_type& __a) - : __tree_(typename __base::allocator_type(__a)) - { - } - - _LIBCPP_HIDE_FROM_ABI - map(const map& __m, const allocator_type& __a) - : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) - { - insert(__m.begin(), __m.end()); - } - - _LIBCPP_HIDE_FROM_ABI - ~map() { - static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); - } + _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {} - _LIBCPP_HIDE_FROM_ABI - iterator begin() _NOEXCEPT {return __tree_.begin();} - _LIBCPP_HIDE_FROM_ABI - const_iterator begin() const _NOEXCEPT {return __tree_.begin();} - _LIBCPP_HIDE_FROM_ABI - iterator end() _NOEXCEPT {return __tree_.end();} - _LIBCPP_HIDE_FROM_ABI - const_iterator end() const _NOEXCEPT {return __tree_.end();} - - _LIBCPP_HIDE_FROM_ABI - reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator rbegin() const _NOEXCEPT - {return const_reverse_iterator(end());} - _LIBCPP_HIDE_FROM_ABI - reverse_iterator rend() _NOEXCEPT - {return reverse_iterator(begin());} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator rend() const _NOEXCEPT - {return const_reverse_iterator(begin());} - - _LIBCPP_HIDE_FROM_ABI - const_iterator cbegin() const _NOEXCEPT {return begin();} - _LIBCPP_HIDE_FROM_ABI - const_iterator cend() const _NOEXCEPT {return end();} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator crend() const _NOEXCEPT {return rend();} - - _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI - bool empty() const _NOEXCEPT {return __tree_.size() == 0;} - _LIBCPP_HIDE_FROM_ABI - size_type size() const _NOEXCEPT {return __tree_.size();} - _LIBCPP_HIDE_FROM_ABI - size_type max_size() const _NOEXCEPT {return __tree_.max_size();} - - _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); -#ifndef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k); -#endif + _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a) + : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) { + insert(__m.begin(), __m.end()); + } + + _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } + + _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } + _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } - _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); - _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; + _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } - _LIBCPP_HIDE_FROM_ABI - allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} - _LIBCPP_HIDE_FROM_ABI - key_compare key_comp() const {return __tree_.value_comp().key_comp();} - _LIBCPP_HIDE_FROM_ABI - value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} + _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } + _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); #ifndef _LIBCPP_CXX03_LANG - template <class ..._Args> - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> emplace(_Args&& ...__args) { - return __tree_.__emplace_unique(std::forward<_Args>(__args)...); - } + _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k); +#endif - template <class ..._Args> - _LIBCPP_HIDE_FROM_ABI - iterator emplace_hint(const_iterator __p, _Args&& ...__args) { - return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...); - } + _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k); + _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const; - template <class _Pp, - class = __enable_if_t<is_constructible<value_type, _Pp>::value> > - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> insert(_Pp&& __p) - {return __tree_.__insert_unique(std::forward<_Pp>(__p));} + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); } + _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); } + _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); } - template <class _Pp, - class = __enable_if_t<is_constructible<value_type, _Pp>::value> > - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __pos, _Pp&& __p) - {return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));} +#ifndef _LIBCPP_CXX03_LANG + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { + return __tree_.__emplace_unique(std::forward<_Args>(__args)...); + } + + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { + return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...); + } + + template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) { + return __tree_.__insert_unique(std::forward<_Pp>(__p)); + } + + template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> > + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) { + return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p)); + } #endif // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> - insert(const value_type& __v) {return __tree_.__insert_unique(__v);} + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); } - _LIBCPP_HIDE_FROM_ABI - iterator - insert(const_iterator __p, const value_type& __v) - {return __tree_.__insert_unique(__p.__i_, __v);} + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { + return __tree_.__insert_unique(__p.__i_, __v); + } #ifndef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> - insert(value_type&& __v) {return __tree_.__insert_unique(std::move(__v));} + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) { + return __tree_.__insert_unique(std::move(__v)); + } - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_unique(__p.__i_, std::move(__v));} + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { + return __tree_.__insert_unique(__p.__i_, std::move(__v)); + } - _LIBCPP_HIDE_FROM_ABI - void insert(initializer_list<value_type> __il) - {insert(__il.begin(), __il.end());} + _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } #endif - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - void insert(_InputIterator __f, _InputIterator __l) - { - for (const_iterator __e = cend(); __f != __l; ++__f) - insert(__e.__i_, *__f); - } + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { + for (const_iterator __e = cend(); __f != __l; ++__f) + insert(__e.__i_, *__f); + } #if _LIBCPP_STD_VER >= 23 - template <_ContainerCompatibleRange<value_type> _Range> - _LIBCPP_HIDE_FROM_ABI - void insert_range(_Range&& __range) { - const_iterator __end = cend(); - for (auto&& __element : __range) { - insert(__end.__i_, std::forward<decltype(__element)>(__element)); - } + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { + const_iterator __end = cend(); + for (auto&& __element : __range) { + insert(__end.__i_, std::forward<decltype(__element)>(__element)); } + } #endif #if _LIBCPP_STD_VER >= 17 - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) - { - return __tree_.__emplace_unique_key_args(__k, - std::piecewise_construct, - std::forward_as_tuple(__k), - std::forward_as_tuple(std::forward<_Args>(__args)...)); - } - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) - { - return __tree_.__emplace_unique_key_args(__k, - std::piecewise_construct, - std::forward_as_tuple(std::move(__k)), - std::forward_as_tuple(std::forward<_Args>(__args)...)); - } + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) { + return __tree_.__emplace_unique_key_args( + __k, + std::piecewise_construct, + std::forward_as_tuple(__k), + std::forward_as_tuple(std::forward<_Args>(__args)...)); + } - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI - iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) - { - return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) { + return __tree_.__emplace_unique_key_args( + __k, + std::piecewise_construct, + std::forward_as_tuple(std::move(__k)), + std::forward_as_tuple(std::forward<_Args>(__args)...)); + } + + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) { + return __tree_ + .__emplace_hint_unique_key_args( + __h.__i_, + __k, std::piecewise_construct, std::forward_as_tuple(__k), - std::forward_as_tuple(std::forward<_Args>(__args)...)).first; - } - - template <class... _Args> - _LIBCPP_HIDE_FROM_ABI - iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) - { - return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, + std::forward_as_tuple(std::forward<_Args>(__args)...)) + .first; + } + + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) { + return __tree_ + .__emplace_hint_unique_key_args( + __h.__i_, + __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), - std::forward_as_tuple(std::forward<_Args>(__args)...)).first; - } - - template <class _Vp> - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) - { - iterator __p = lower_bound(__k); - if ( __p != end() && !key_comp()(__k, __p->first)) - { - __p->second = std::forward<_Vp>(__v); - return std::make_pair(__p, false); - } - return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true); + std::forward_as_tuple(std::forward<_Args>(__args)...)) + .first; + } + + template <class _Vp> + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) { + iterator __p = lower_bound(__k); + if (__p != end() && !key_comp()(__k, __p->first)) { + __p->second = std::forward<_Vp>(__v); + return std::make_pair(__p, false); } - - template <class _Vp> - _LIBCPP_HIDE_FROM_ABI - pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) - { - iterator __p = lower_bound(__k); - if ( __p != end() && !key_comp()(__k, __p->first)) - { - __p->second = std::forward<_Vp>(__v); - return std::make_pair(__p, false); - } - return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true); + return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true); + } + + template <class _Vp> + _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) { + iterator __p = lower_bound(__k); + if (__p != end() && !key_comp()(__k, __p->first)) { + __p->second = std::forward<_Vp>(__v); + return std::make_pair(__p, false); } + return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true); + } - template <class _Vp> - _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, - const key_type& __k, - _Vp&& __v) { - auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args( - __h.__i_, __k, __k, std::forward<_Vp>(__v)); + template <class _Vp> + _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) { + auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v)); - if (!__inserted) - __r->__get_value().second = std::forward<_Vp>(__v); + if (!__inserted) + __r->__get_value().second = std::forward<_Vp>(__v); - return __r; - } + return __r; + } - template <class _Vp> - _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, - key_type&& __k, - _Vp&& __v) { - auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args( - __h.__i_, __k, std::move(__k), std::forward<_Vp>(__v)); + template <class _Vp> + _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) { + auto [__r, __inserted] = + __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v)); - if (!__inserted) - __r->__get_value().second = std::forward<_Vp>(__v); + if (!__inserted) + __r->__get_value().second = std::forward<_Vp>(__v); - return __r; - } + return __r; + } #endif // _LIBCPP_STD_VER >= 17 - _LIBCPP_HIDE_FROM_ABI - iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} - _LIBCPP_HIDE_FROM_ABI - iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} - _LIBCPP_HIDE_FROM_ABI - size_type erase(const key_type& __k) - {return __tree_.__erase_unique(__k);} - _LIBCPP_HIDE_FROM_ABI - iterator erase(const_iterator __f, const_iterator __l) - {return __tree_.erase(__f.__i_, __l.__i_);} - _LIBCPP_HIDE_FROM_ABI - void clear() _NOEXCEPT {__tree_.clear();} + _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); } + _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { + return __tree_.erase(__f.__i_, __l.__i_); + } + _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } #if _LIBCPP_STD_VER >= 17 - _LIBCPP_HIDE_FROM_ABI - insert_return_type insert(node_type&& __nh) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), - "node_type with incompatible allocator passed to map::insert()"); - return __tree_.template __node_handle_insert_unique< - node_type, insert_return_type>(std::move(__nh)); - } - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __hint, node_type&& __nh) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), - "node_type with incompatible allocator passed to map::insert()"); - return __tree_.template __node_handle_insert_unique<node_type>( - __hint.__i_, std::move(__nh)); - } - _LIBCPP_HIDE_FROM_ABI - node_type extract(key_type const& __key) - { - return __tree_.template __node_handle_extract<node_type>(__key); - } - _LIBCPP_HIDE_FROM_ABI - node_type extract(const_iterator __it) - { - return __tree_.template __node_handle_extract<node_type>(__it.__i_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - __tree_.__node_handle_merge_unique(__source.__tree_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - __tree_.__node_handle_merge_unique(__source.__tree_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - __tree_.__node_handle_merge_unique(__source.__tree_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - __tree_.__node_handle_merge_unique(__source.__tree_); - } + _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to map::insert()"); + return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); + } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to map::insert()"); + return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh)); + } + _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { + return __tree_.template __node_handle_extract<node_type>(__key); + } + _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { + return __tree_.template __node_handle_extract<node_type>(__it.__i_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + __tree_.__node_handle_merge_unique(__source.__tree_); + } #endif - _LIBCPP_HIDE_FROM_ABI - void swap(map& __m) - _NOEXCEPT_(__is_nothrow_swappable<__base>::value) - {__tree_.swap(__m.__tree_);} + _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) { + __tree_.swap(__m.__tree_); + } - _LIBCPP_HIDE_FROM_ABI - iterator find(const key_type& __k) {return __tree_.find(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator find(const key_type& __k) const {return __tree_.find(__k);} + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - iterator - find(const _K2& __k) {return __tree_.find(__k);} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - const_iterator - find(const _K2& __k) const {return __tree_.find(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { + return __tree_.find(__k); + } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { + return __tree_.find(__k); + } #endif - _LIBCPP_HIDE_FROM_ABI - size_type count(const key_type& __k) const - {return __tree_.__count_unique(__k);} + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - size_type - count(const _K2& __k) const {return __tree_.__count_multi(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { + return __tree_.__count_multi(__k); + } #endif #if _LIBCPP_STD_VER >= 20 - _LIBCPP_HIDE_FROM_ABI - bool contains(const key_type& __k) const {return find(__k) != end();} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - bool - contains(const _K2& __k) const { return find(__k) != end(); } + _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { + return find(__k) != end(); + } #endif // _LIBCPP_STD_VER >= 20 - _LIBCPP_HIDE_FROM_ABI - iterator lower_bound(const key_type& __k) - {return __tree_.lower_bound(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator lower_bound(const key_type& __k) const - {return __tree_.lower_bound(__k);} + _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - iterator - lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} - - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - const_iterator - lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) { + return __tree_.lower_bound(__k); + } + + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const { + return __tree_.lower_bound(__k); + } #endif - _LIBCPP_HIDE_FROM_ABI - iterator upper_bound(const key_type& __k) - {return __tree_.upper_bound(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator upper_bound(const key_type& __k) const - {return __tree_.upper_bound(__k);} + _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - iterator - upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - const_iterator - upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) { + return __tree_.upper_bound(__k); + } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const { + return __tree_.upper_bound(__k); + } #endif - _LIBCPP_HIDE_FROM_ABI - pair<iterator,iterator> equal_range(const key_type& __k) - {return __tree_.__equal_range_unique(__k);} - _LIBCPP_HIDE_FROM_ABI - pair<const_iterator,const_iterator> equal_range(const key_type& __k) const - {return __tree_.__equal_range_unique(__k);} + _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { + return __tree_.__equal_range_unique(__k); + } + _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { + return __tree_.__equal_range_unique(__k); + } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - pair<iterator,iterator> - equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - pair<const_iterator,const_iterator> - equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { + return __tree_.__equal_range_multi(__k); + } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { + return __tree_.__equal_range_multi(__k); + } #endif private: - typedef typename __base::__node __node; - typedef typename __base::__node_allocator __node_allocator; - typedef typename __base::__node_pointer __node_pointer; - typedef typename __base::__node_base_pointer __node_base_pointer; - typedef typename __base::__parent_pointer __parent_pointer; + typedef typename __base::__node __node; + typedef typename __base::__node_allocator __node_allocator; + typedef typename __base::__node_pointer __node_pointer; + typedef typename __base::__node_base_pointer __node_base_pointer; + typedef typename __base::__parent_pointer __parent_pointer; - typedef __map_node_destructor<__node_allocator> _Dp; - typedef unique_ptr<__node, _Dp> __node_holder; + typedef __map_node_destructor<__node_allocator> _Dp; + typedef unique_ptr<__node, _Dp> __node_holder; #ifdef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); + _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k); #endif }; #if _LIBCPP_STD_VER >= 17 -template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, - class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, - class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, - class = enable_if_t<!__is_allocator<_Compare>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +template <class _InputIterator, + class _Compare = less<__iter_key_type<_InputIterator>>, + class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, + class = enable_if_t<!__is_allocator<_Compare>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) - -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; + -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; -#if _LIBCPP_STD_VER >= 23 -template <ranges::input_range _Range, class _Compare = less<__range_key_type<_Range>>, +# if _LIBCPP_STD_VER >= 23 +template <ranges::input_range _Range, + class _Compare = less<__range_key_type<_Range>>, class _Allocator = allocator<__range_to_alloc_type<_Range>>, - class = enable_if_t<!__is_allocator<_Compare>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> + class = enable_if_t<!__is_allocator<_Compare>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) - -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; -#endif - -template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, - class _Allocator = allocator<pair<const _Key, _Tp>>, - class = enable_if_t<!__is_allocator<_Compare>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> + -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; +# endif + +template <class _Key, + class _Tp, + class _Compare = less<remove_const_t<_Key>>, + class _Allocator = allocator<pair<const _Key, _Tp>>, + class = enable_if_t<!__is_allocator<_Compare>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) - -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; + -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; -template<class _InputIterator, class _Allocator, - class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +template <class _InputIterator, + class _Allocator, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> map(_InputIterator, _InputIterator, _Allocator) - -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, - less<__iter_key_type<_InputIterator>>, _Allocator>; + -> map<__iter_key_type<_InputIterator>, + __iter_mapped_type<_InputIterator>, + less<__iter_key_type<_InputIterator>>, + _Allocator>; -#if _LIBCPP_STD_VER >= 23 -template <ranges::input_range _Range, class _Allocator, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +# if _LIBCPP_STD_VER >= 23 +template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> map(from_range_t, _Range&&, _Allocator) - -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; -#endif + -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; +# endif -template<class _Key, class _Tp, class _Allocator, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> map(initializer_list<pair<_Key, _Tp>>, _Allocator) - -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; + -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; #endif #ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a) - : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) -{ - if (__a != __m.get_allocator()) - { - const_iterator __e = cend(); - while (!__m.empty()) - __tree_.__insert_unique(__e.__i_, - __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); - } + : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) { + if (__a != __m.get_allocator()) { + const_iterator __e = cend(); + while (!__m.empty()) + __tree_.__insert_unique(__e.__i_, __m.__tree_.remove(__m.begin().__i_)->__value_.__move()); + } } template <class _Key, class _Tp, class _Compare, class _Allocator> -_Tp& -map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) -{ - return __tree_.__emplace_unique_key_args(__k, - std::piecewise_construct, - std::forward_as_tuple(__k), - std::forward_as_tuple()).first->__get_value().second; +_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { + return __tree_ + .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple()) + .first->__get_value() + .second; } template <class _Key, class _Tp, class _Compare, class _Allocator> -_Tp& -map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) -{ - // TODO investigate this clang-tidy warning. - // NOLINTNEXTLINE(bugprone-use-after-move) - return __tree_.__emplace_unique_key_args(__k, - std::piecewise_construct, - std::forward_as_tuple(std::move(__k)), - std::forward_as_tuple()).first->__get_value().second; +_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) { + // TODO investigate this clang-tidy warning. + // NOLINTBEGIN(bugprone-use-after-move) + return __tree_ + .__emplace_unique_key_args( + __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple()) + .first->__get_value() + .second; + // NOLINTEND(bugprone-use-after-move) } #else // _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder -map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) -{ - __node_allocator& __na = __tree_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second)); - __h.get_deleter().__second_constructed = true; - return __h; +map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) { + __node_allocator& __na = __tree_.__node_alloc(); + __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); + __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k); + __h.get_deleter().__first_constructed = true; + __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second)); + __h.get_deleter().__second_constructed = true; + return __h; } template <class _Key, class _Tp, class _Compare, class _Allocator> -_Tp& -map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) -{ - __parent_pointer __parent; - __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); - __node_pointer __r = static_cast<__node_pointer>(__child); - if (__child == nullptr) - { - __node_holder __h = __construct_node_with_key(__k); - __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); - __r = __h.release(); - } - return __r->__value_.__get_value().second; +_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) { + __parent_pointer __parent; + __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); + __node_pointer __r = static_cast<__node_pointer>(__child); + if (__child == nullptr) { + __node_holder __h = __construct_node_with_key(__k); + __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); + __r = __h.release(); + } + return __r->__value_.__get_value().second; } #endif // _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> -_Tp& -map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) -{ - __parent_pointer __parent; - __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); - if (__child == nullptr) - __throw_out_of_range("map::at: key not found"); - return static_cast<__node_pointer>(__child)->__value_.__get_value().second; +_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) { + __parent_pointer __parent; + __node_base_pointer& __child = __tree_.__find_equal(__parent, __k); + if (__child == nullptr) + __throw_out_of_range("map::at: key not found"); + return static_cast<__node_pointer>(__child)->__value_.__get_value().second; } template <class _Key, class _Tp, class _Compare, class _Allocator> -const _Tp& -map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const -{ - __parent_pointer __parent; - __node_base_pointer __child = __tree_.__find_equal(__parent, __k); - if (__child == nullptr) - __throw_out_of_range("map::at: key not found"); - return static_cast<__node_pointer>(__child)->__value_.__get_value().second; +const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const { + __parent_pointer __parent; + __node_base_pointer __child = __tree_.__find_equal(__parent, __k); + if (__child == nullptr) + __throw_out_of_range("map::at: key not found"); + return static_cast<__node_pointer>(__child)->__value_.__get_value().second; } - template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, - const map<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); +inline _LIBCPP_HIDE_FROM_ABI bool +operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { + return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); } #if _LIBCPP_STD_VER <= 17 template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x, - const map<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); +inline _LIBCPP_HIDE_FROM_ABI bool +operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { + return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, - const map<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return !(__x == __y); +inline _LIBCPP_HIDE_FROM_ABI bool +operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { + return !(__x == __y); } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x, - const map<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return __y < __x; +inline _LIBCPP_HIDE_FROM_ABI bool +operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { + return __y < __x; } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, - const map<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return !(__x < __y); +inline _LIBCPP_HIDE_FROM_ABI bool +operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { + return !(__x < __y); } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, - const map<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return !(__y < __x); +inline _LIBCPP_HIDE_FROM_ABI bool +operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { + return !(__y < __x); } #else // #if _LIBCPP_STD_VER <= 17 @@ -1825,654 +1620,519 @@ operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, template <class _Key, class _Tp, class _Compare, class _Allocator> _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>> operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) { - return std::lexicographical_compare_three_way( - __x.begin(), - __x.end(), - __y.begin(), - __y.end(), - std::__synth_three_way<pair<const _Key, _Tp>, pair<const _Key, _Tp>>); + return std::lexicographical_compare_three_way( + __x.begin(), + __x.end(), + __y.begin(), + __y.end(), + std::__synth_three_way<pair<const _Key, _Tp>, pair<const _Key, _Tp>>); } #endif // #if _LIBCPP_STD_VER <= 17 template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -void -swap(map<_Key, _Tp, _Compare, _Allocator>& __x, - map<_Key, _Tp, _Compare, _Allocator>& __y) - _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) -{ - __x.swap(__y); +inline _LIBCPP_HIDE_FROM_ABI void +swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y) + _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { + __x.swap(__y); } #if _LIBCPP_STD_VER >= 20 -template <class _Key, class _Tp, class _Compare, class _Allocator, - class _Predicate> -inline _LIBCPP_HIDE_FROM_ABI - typename map<_Key, _Tp, _Compare, _Allocator>::size_type - erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { +template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> +inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type +erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { return std::__libcpp_erase_if_container(__c, __pred); } #endif - -template <class _Key, class _Tp, class _Compare = less<_Key>, - class _Allocator = allocator<pair<const _Key, _Tp> > > -class _LIBCPP_TEMPLATE_VIS multimap -{ +template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > > +class _LIBCPP_TEMPLATE_VIS multimap { public: - // types: - typedef _Key key_type; - typedef _Tp mapped_type; - typedef pair<const key_type, mapped_type> value_type; - typedef __type_identity_t<_Compare> key_compare; - typedef __type_identity_t<_Allocator> allocator_type; - typedef value_type& reference; - typedef const value_type& const_reference; + // types: + typedef _Key key_type; + typedef _Tp mapped_type; + typedef pair<const key_type, mapped_type> value_type; + typedef __type_identity_t<_Compare> key_compare; + typedef __type_identity_t<_Allocator> allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; - static_assert((is_same<typename allocator_type::value_type, value_type>::value), - "Allocator::value_type must be same type as value_type"); + static_assert((is_same<typename allocator_type::value_type, value_type>::value), + "Allocator::value_type must be same type as value_type"); - class _LIBCPP_TEMPLATE_VIS value_compare - : public __binary_function<value_type, value_type, bool> - { - friend class multimap; - protected: - key_compare comp; + class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> { + friend class multimap; - _LIBCPP_HIDE_FROM_ABI - value_compare(key_compare __c) : comp(__c) {} - public: - _LIBCPP_HIDE_FROM_ABI - bool operator()(const value_type& __x, const value_type& __y) const - {return comp(__x.first, __y.first);} - }; + protected: + key_compare comp; -private: + _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {} - typedef std::__value_type<key_type, mapped_type> __value_type; - typedef __map_value_compare<key_type, __value_type, key_compare> __vc; - typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; - typedef __tree<__value_type, __vc, __allocator_type> __base; - typedef typename __base::__node_traits __node_traits; - typedef allocator_traits<allocator_type> __alloc_traits; + public: + _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const { + return comp(__x.first, __y.first); + } + }; + +private: + typedef std::__value_type<key_type, mapped_type> __value_type; + typedef __map_value_compare<key_type, __value_type, key_compare> __vc; + typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type; + typedef __tree<__value_type, __vc, __allocator_type> __base; + typedef typename __base::__node_traits __node_traits; + typedef allocator_traits<allocator_type> __alloc_traits; - static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, - "[allocator.requirements] states that rebinding an allocator to the same type should result in the " - "original allocator"); + static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, + "[allocator.requirements] states that rebinding an allocator to the same type should result in the " + "original allocator"); - __base __tree_; + __base __tree_; public: - typedef typename __alloc_traits::pointer pointer; - typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; - typedef __map_iterator<typename __base::iterator> iterator; - typedef __map_const_iterator<typename __base::const_iterator> const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef typename __alloc_traits::pointer pointer; + typedef typename __alloc_traits::const_pointer const_pointer; + typedef typename __alloc_traits::size_type size_type; + typedef typename __alloc_traits::difference_type difference_type; + typedef __map_iterator<typename __base::iterator> iterator; + typedef __map_const_iterator<typename __base::const_iterator> const_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; #if _LIBCPP_STD_VER >= 17 - typedef __map_node_handle<typename __base::__node, allocator_type> node_type; + typedef __map_node_handle<typename __base::__node, allocator_type> node_type; #endif - template <class _Key2, class _Value2, class _Comp2, class _Alloc2> - friend class _LIBCPP_TEMPLATE_VIS map; - template <class _Key2, class _Value2, class _Comp2, class _Alloc2> - friend class _LIBCPP_TEMPLATE_VIS multimap; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS map; + template <class _Key2, class _Value2, class _Comp2, class _Alloc2> + friend class _LIBCPP_TEMPLATE_VIS multimap; - _LIBCPP_HIDE_FROM_ABI - multimap() - _NOEXCEPT_( - is_nothrow_default_constructible<allocator_type>::value && - is_nothrow_default_constructible<key_compare>::value && - is_nothrow_copy_constructible<key_compare>::value) - : __tree_(__vc(key_compare())) {} + _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_( + is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&& + is_nothrow_copy_constructible<key_compare>::value) + : __tree_(__vc(key_compare())) {} - _LIBCPP_HIDE_FROM_ABI - explicit multimap(const key_compare& __comp) - _NOEXCEPT_( - is_nothrow_default_constructible<allocator_type>::value && - is_nothrow_copy_constructible<key_compare>::value) - : __tree_(__vc(__comp)) {} - - _LIBCPP_HIDE_FROM_ABI - explicit multimap(const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} - - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - multimap(_InputIterator __f, _InputIterator __l, - const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) - { - insert(__f, __l); - } - - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - multimap(_InputIterator __f, _InputIterator __l, - const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), typename __base::allocator_type(__a)) - { - insert(__f, __l); - } + _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_( + is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value) + : __tree_(__vc(__comp)) {} + + _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {} + + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare()) + : __tree_(__vc(__comp)) { + insert(__f, __l); + } + + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI + multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { + insert(__f, __l); + } #if _LIBCPP_STD_VER >= 23 - template <_ContainerCompatibleRange<value_type> _Range> - _LIBCPP_HIDE_FROM_ABI - multimap(from_range_t, _Range&& __range, const key_compare& __comp = key_compare(), - const allocator_type& __a = allocator_type()) + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI + multimap(from_range_t, + _Range&& __range, + const key_compare& __comp = key_compare(), + const allocator_type& __a = allocator_type()) : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { - insert_range(std::forward<_Range>(__range)); - } + insert_range(std::forward<_Range>(__range)); + } #endif #if _LIBCPP_STD_VER >= 14 - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) - : multimap(__f, __l, key_compare(), __a) {} + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a) + : multimap(__f, __l, key_compare(), __a) {} #endif #if _LIBCPP_STD_VER >= 23 - template <_ContainerCompatibleRange<value_type> _Range> - _LIBCPP_HIDE_FROM_ABI - multimap(from_range_t, _Range&& __range, const allocator_type& __a) + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a) : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {} #endif - _LIBCPP_HIDE_FROM_ABI - multimap(const multimap& __m) - : __tree_(__m.__tree_.value_comp(), - __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) - { - insert(__m.begin(), __m.end()); - } - - _LIBCPP_HIDE_FROM_ABI - multimap& operator=(const multimap& __m) - { + _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m) + : __tree_(__m.__tree_.value_comp(), + __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) { + insert(__m.begin(), __m.end()); + } + + _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) { #ifndef _LIBCPP_CXX03_LANG - __tree_ = __m.__tree_; + __tree_ = __m.__tree_; #else - if (this != std::addressof(__m)) { - __tree_.clear(); - __tree_.value_comp() = __m.__tree_.value_comp(); - __tree_.__copy_assign_alloc(__m.__tree_); - insert(__m.begin(), __m.end()); - } + if (this != std::addressof(__m)) { + __tree_.clear(); + __tree_.value_comp() = __m.__tree_.value_comp(); + __tree_.__copy_assign_alloc(__m.__tree_); + insert(__m.begin(), __m.end()); + } #endif - return *this; - } + return *this; + } #ifndef _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - multimap(multimap&& __m) - _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) - : __tree_(std::move(__m.__tree_)) - { - } - - _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a); - - _LIBCPP_HIDE_FROM_ABI - multimap& operator=(multimap&& __m) - _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) - { - __tree_ = std::move(__m.__tree_); - return *this; - } - - _LIBCPP_HIDE_FROM_ABI - multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) - { - insert(__il.begin(), __il.end()); - } - - _LIBCPP_HIDE_FROM_ABI - multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), typename __base::allocator_type(__a)) - { - insert(__il.begin(), __il.end()); - } + _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) + : __tree_(std::move(__m.__tree_)) {} -#if _LIBCPP_STD_VER >= 14 - _LIBCPP_HIDE_FROM_ABI - multimap(initializer_list<value_type> __il, const allocator_type& __a) - : multimap(__il, key_compare(), __a) {} -#endif + _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a); - _LIBCPP_HIDE_FROM_ABI - multimap& operator=(initializer_list<value_type> __il) - { - __tree_.__assign_multi(__il.begin(), __il.end()); - return *this; - } + _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) { + __tree_ = std::move(__m.__tree_); + return *this; + } + + _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) + : __tree_(__vc(__comp)) { + insert(__il.begin(), __il.end()); + } + + _LIBCPP_HIDE_FROM_ABI + multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) + : __tree_(__vc(__comp), typename __base::allocator_type(__a)) { + insert(__il.begin(), __il.end()); + } + +# if _LIBCPP_STD_VER >= 14 + _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a) + : multimap(__il, key_compare(), __a) {} +# endif + + _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) { + __tree_.__assign_multi(__il.begin(), __il.end()); + return *this; + } #endif // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - explicit multimap(const allocator_type& __a) - : __tree_(typename __base::allocator_type(__a)) - { - } - - _LIBCPP_HIDE_FROM_ABI - multimap(const multimap& __m, const allocator_type& __a) - : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) - { - insert(__m.begin(), __m.end()); - } - - _LIBCPP_HIDE_FROM_ABI - ~multimap() { - static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); - } + _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {} - _LIBCPP_HIDE_FROM_ABI - iterator begin() _NOEXCEPT {return __tree_.begin();} - _LIBCPP_HIDE_FROM_ABI - const_iterator begin() const _NOEXCEPT {return __tree_.begin();} - _LIBCPP_HIDE_FROM_ABI - iterator end() _NOEXCEPT {return __tree_.end();} - _LIBCPP_HIDE_FROM_ABI - const_iterator end() const _NOEXCEPT {return __tree_.end();} - - _LIBCPP_HIDE_FROM_ABI - reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator rbegin() const _NOEXCEPT - {return const_reverse_iterator(end());} - _LIBCPP_HIDE_FROM_ABI - reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator rend() const _NOEXCEPT - {return const_reverse_iterator(begin());} - - _LIBCPP_HIDE_FROM_ABI - const_iterator cbegin() const _NOEXCEPT {return begin();} - _LIBCPP_HIDE_FROM_ABI - const_iterator cend() const _NOEXCEPT {return end();} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} - _LIBCPP_HIDE_FROM_ABI - const_reverse_iterator crend() const _NOEXCEPT {return rend();} - - _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI - bool empty() const _NOEXCEPT {return __tree_.size() == 0;} - _LIBCPP_HIDE_FROM_ABI - size_type size() const _NOEXCEPT {return __tree_.size();} - _LIBCPP_HIDE_FROM_ABI - size_type max_size() const _NOEXCEPT {return __tree_.max_size();} - - _LIBCPP_HIDE_FROM_ABI - allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());} - _LIBCPP_HIDE_FROM_ABI - key_compare key_comp() const {return __tree_.value_comp().key_comp();} - _LIBCPP_HIDE_FROM_ABI - value_compare value_comp() const - {return value_compare(__tree_.value_comp().key_comp());} + _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a) + : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) { + insert(__m.begin(), __m.end()); + } -#ifndef _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } - template <class ..._Args> - _LIBCPP_HIDE_FROM_ABI - iterator emplace(_Args&& ...__args) { - return __tree_.__emplace_multi(std::forward<_Args>(__args)...); - } + _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } - template <class ..._Args> - _LIBCPP_HIDE_FROM_ABI - iterator emplace_hint(const_iterator __p, _Args&& ...__args) { - return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...); - } + _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } + _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } + + _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } + _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } + + _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); } + _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); } + _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); } - template <class _Pp, - class = __enable_if_t<is_constructible<value_type, _Pp>::value>> - _LIBCPP_HIDE_FROM_ABI - iterator insert(_Pp&& __p) - {return __tree_.__insert_multi(std::forward<_Pp>(__p));} +#ifndef _LIBCPP_CXX03_LANG + + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { + return __tree_.__emplace_multi(std::forward<_Args>(__args)...); + } - template <class _Pp, - class = __enable_if_t<is_constructible<value_type, _Pp>::value>> - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __pos, _Pp&& __p) - {return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p));} + template <class... _Args> + _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { + return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...); + } - _LIBCPP_HIDE_FROM_ABI - iterator insert(value_type&& __v) - {return __tree_.__insert_multi(std::move(__v));} + template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value>> + _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) { + return __tree_.__insert_multi(std::forward<_Pp>(__p)); + } - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __p, value_type&& __v) - {return __tree_.__insert_multi(__p.__i_, std::move(__v));} + template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value>> + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) { + return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p)); + } + _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); } - _LIBCPP_HIDE_FROM_ABI - void insert(initializer_list<value_type> __il) - {insert(__il.begin(), __il.end());} + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { + return __tree_.__insert_multi(__p.__i_, std::move(__v)); + } + + _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } #endif // _LIBCPP_CXX03_LANG - _LIBCPP_HIDE_FROM_ABI - iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} + _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); } - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __p, const value_type& __v) - {return __tree_.__insert_multi(__p.__i_, __v);} + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { + return __tree_.__insert_multi(__p.__i_, __v); + } - template <class _InputIterator> - _LIBCPP_HIDE_FROM_ABI - void insert(_InputIterator __f, _InputIterator __l) - { - for (const_iterator __e = cend(); __f != __l; ++__f) - __tree_.__insert_multi(__e.__i_, *__f); - } + template <class _InputIterator> + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { + for (const_iterator __e = cend(); __f != __l; ++__f) + __tree_.__insert_multi(__e.__i_, *__f); + } #if _LIBCPP_STD_VER >= 23 - template <_ContainerCompatibleRange<value_type> _Range> - _LIBCPP_HIDE_FROM_ABI - void insert_range(_Range&& __range) { - const_iterator __end = cend(); - for (auto&& __element : __range) { - __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element)); - } + template <_ContainerCompatibleRange<value_type> _Range> + _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { + const_iterator __end = cend(); + for (auto&& __element : __range) { + __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element)); } + } #endif - _LIBCPP_HIDE_FROM_ABI - iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} - _LIBCPP_HIDE_FROM_ABI - iterator erase(iterator __p) {return __tree_.erase(__p.__i_);} - _LIBCPP_HIDE_FROM_ABI - size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} - _LIBCPP_HIDE_FROM_ABI - iterator erase(const_iterator __f, const_iterator __l) - {return __tree_.erase(__f.__i_, __l.__i_);} + _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); } + _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { + return __tree_.erase(__f.__i_, __l.__i_); + } #if _LIBCPP_STD_VER >= 17 - _LIBCPP_HIDE_FROM_ABI - iterator insert(node_type&& __nh) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), - "node_type with incompatible allocator passed to multimap::insert()"); - return __tree_.template __node_handle_insert_multi<node_type>( - std::move(__nh)); - } - _LIBCPP_HIDE_FROM_ABI - iterator insert(const_iterator __hint, node_type&& __nh) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), - "node_type with incompatible allocator passed to multimap::insert()"); - return __tree_.template __node_handle_insert_multi<node_type>( - __hint.__i_, std::move(__nh)); - } - _LIBCPP_HIDE_FROM_ABI - node_type extract(key_type const& __key) - { - return __tree_.template __node_handle_extract<node_type>(__key); - } - _LIBCPP_HIDE_FROM_ABI - node_type extract(const_iterator __it) - { - return __tree_.template __node_handle_extract<node_type>( - __it.__i_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - return __tree_.__node_handle_merge_multi(__source.__tree_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - return __tree_.__node_handle_merge_multi(__source.__tree_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - return __tree_.__node_handle_merge_multi(__source.__tree_); - } - template <class _Compare2> - _LIBCPP_HIDE_FROM_ABI - void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) - { - _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__source.get_allocator() == get_allocator(), - "merging container with incompatible allocator"); - return __tree_.__node_handle_merge_multi(__source.__tree_); - } + _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to multimap::insert()"); + return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh)); + } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), + "node_type with incompatible allocator passed to multimap::insert()"); + return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh)); + } + _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { + return __tree_.template __node_handle_extract<node_type>(__key); + } + _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { + return __tree_.template __node_handle_extract<node_type>(__it.__i_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } + template <class _Compare2> + _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) { + _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( + __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); + return __tree_.__node_handle_merge_multi(__source.__tree_); + } #endif - _LIBCPP_HIDE_FROM_ABI - void clear() _NOEXCEPT {__tree_.clear();} + _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } - _LIBCPP_HIDE_FROM_ABI - void swap(multimap& __m) - _NOEXCEPT_(__is_nothrow_swappable<__base>::value) - {__tree_.swap(__m.__tree_);} + _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) { + __tree_.swap(__m.__tree_); + } - _LIBCPP_HIDE_FROM_ABI - iterator find(const key_type& __k) {return __tree_.find(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator find(const key_type& __k) const {return __tree_.find(__k);} + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - iterator - find(const _K2& __k) {return __tree_.find(__k);} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - const_iterator - find(const _K2& __k) const {return __tree_.find(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { + return __tree_.find(__k); + } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { + return __tree_.find(__k); + } #endif - _LIBCPP_HIDE_FROM_ABI - size_type count(const key_type& __k) const - {return __tree_.__count_multi(__k);} + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - size_type - count(const _K2& __k) const {return __tree_.__count_multi(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { + return __tree_.__count_multi(__k); + } #endif #if _LIBCPP_STD_VER >= 20 - _LIBCPP_HIDE_FROM_ABI - bool contains(const key_type& __k) const {return find(__k) != end();} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - bool - contains(const _K2& __k) const { return find(__k) != end(); } + _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { + return find(__k) != end(); + } #endif // _LIBCPP_STD_VER >= 20 - _LIBCPP_HIDE_FROM_ABI - iterator lower_bound(const key_type& __k) - {return __tree_.lower_bound(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator lower_bound(const key_type& __k) const - {return __tree_.lower_bound(__k);} + _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - iterator - lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} - - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - const_iterator - lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) { + return __tree_.lower_bound(__k); + } + + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const { + return __tree_.lower_bound(__k); + } #endif - _LIBCPP_HIDE_FROM_ABI - iterator upper_bound(const key_type& __k) - {return __tree_.upper_bound(__k);} - _LIBCPP_HIDE_FROM_ABI - const_iterator upper_bound(const key_type& __k) const - {return __tree_.upper_bound(__k);} + _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - iterator - upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - const_iterator - upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) { + return __tree_.upper_bound(__k); + } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const { + return __tree_.upper_bound(__k); + } #endif - _LIBCPP_HIDE_FROM_ABI - pair<iterator,iterator> equal_range(const key_type& __k) - {return __tree_.__equal_range_multi(__k);} - _LIBCPP_HIDE_FROM_ABI - pair<const_iterator,const_iterator> equal_range(const key_type& __k) const - {return __tree_.__equal_range_multi(__k);} + _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { + return __tree_.__equal_range_multi(__k); + } + _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { + return __tree_.__equal_range_multi(__k); + } #if _LIBCPP_STD_VER >= 14 - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - pair<iterator,iterator> - equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} - template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> - _LIBCPP_HIDE_FROM_ABI - pair<const_iterator,const_iterator> - equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { + return __tree_.__equal_range_multi(__k); + } + template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { + return __tree_.__equal_range_multi(__k); + } #endif private: - typedef typename __base::__node __node; - typedef typename __base::__node_allocator __node_allocator; - typedef typename __base::__node_pointer __node_pointer; + typedef typename __base::__node __node; + typedef typename __base::__node_allocator __node_allocator; + typedef typename __base::__node_pointer __node_pointer; - typedef __map_node_destructor<__node_allocator> _Dp; - typedef unique_ptr<__node, _Dp> __node_holder; + typedef __map_node_destructor<__node_allocator> _Dp; + typedef unique_ptr<__node, _Dp> __node_holder; }; #if _LIBCPP_STD_VER >= 17 -template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>, - class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, - class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, - class = enable_if_t<!__is_allocator<_Compare>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +template <class _InputIterator, + class _Compare = less<__iter_key_type<_InputIterator>>, + class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, + class = enable_if_t<!__is_allocator<_Compare>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) - -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; + -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>; -#if _LIBCPP_STD_VER >= 23 -template <ranges::input_range _Range, class _Compare = less<__range_key_type<_Range>>, +# if _LIBCPP_STD_VER >= 23 +template <ranges::input_range _Range, + class _Compare = less<__range_key_type<_Range>>, class _Allocator = allocator<__range_to_alloc_type<_Range>>, - class = enable_if_t<!__is_allocator<_Compare>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> + class = enable_if_t<!__is_allocator<_Compare>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) - -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; -#endif - -template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>, - class _Allocator = allocator<pair<const _Key, _Tp>>, - class = enable_if_t<!__is_allocator<_Compare>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> + -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>; +# endif + +template <class _Key, + class _Tp, + class _Compare = less<remove_const_t<_Key>>, + class _Allocator = allocator<pair<const _Key, _Tp>>, + class = enable_if_t<!__is_allocator<_Compare>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator()) - -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; + -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>; -template<class _InputIterator, class _Allocator, - class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +template <class _InputIterator, + class _Allocator, + class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, + class = enable_if_t<__is_allocator<_Allocator>::value, void>> multimap(_InputIterator, _InputIterator, _Allocator) - -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, - less<__iter_key_type<_InputIterator>>, _Allocator>; + -> multimap<__iter_key_type<_InputIterator>, + __iter_mapped_type<_InputIterator>, + less<__iter_key_type<_InputIterator>>, + _Allocator>; -#if _LIBCPP_STD_VER >= 23 -template <ranges::input_range _Range, class _Allocator, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +# if _LIBCPP_STD_VER >= 23 +template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> multimap(from_range_t, _Range&&, _Allocator) - -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; -#endif + -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>; +# endif -template<class _Key, class _Tp, class _Allocator, - class = enable_if_t<__is_allocator<_Allocator>::value, void>> +template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) - -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; + -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>; #endif #ifndef _LIBCPP_CXX03_LANG template <class _Key, class _Tp, class _Compare, class _Allocator> multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a) - : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) -{ - if (__a != __m.get_allocator()) - { - const_iterator __e = cend(); - while (!__m.empty()) - __tree_.__insert_multi(__e.__i_, - std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); - } + : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) { + if (__a != __m.get_allocator()) { + const_iterator __e = cend(); + while (!__m.empty()) + __tree_.__insert_multi(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move())); + } } #endif template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, - const multimap<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); +inline _LIBCPP_HIDE_FROM_ABI bool +operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { + return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); } #if _LIBCPP_STD_VER <= 17 template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, - const multimap<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); +inline _LIBCPP_HIDE_FROM_ABI bool +operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { + return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, - const multimap<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return !(__x == __y); +inline _LIBCPP_HIDE_FROM_ABI bool +operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { + return !(__x == __y); } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x, - const multimap<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return __y < __x; +inline _LIBCPP_HIDE_FROM_ABI bool +operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { + return __y < __x; } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, - const multimap<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return !(__x < __y); +inline _LIBCPP_HIDE_FROM_ABI bool +operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { + return !(__x < __y); } template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -bool -operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, - const multimap<_Key, _Tp, _Compare, _Allocator>& __y) -{ - return !(__y < __x); +inline _LIBCPP_HIDE_FROM_ABI bool +operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { + return !(__y < __x); } #else // #if _LIBCPP_STD_VER <= 17 @@ -2481,33 +2141,27 @@ template <class _Key, class _Tp, class _Compare, class _Allocator> _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>> operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) { - return std::lexicographical_compare_three_way( - __x.begin(), - __x.end(), - __y.begin(), - __y.end(), - std::__synth_three_way<pair<const _Key, _Tp>, pair<const _Key, _Tp>>); + return std::lexicographical_compare_three_way( + __x.begin(), + __x.end(), + __y.begin(), + __y.end(), + std::__synth_three_way<pair<const _Key, _Tp>, pair<const _Key, _Tp>>); } #endif // #if _LIBCPP_STD_VER <= 17 template <class _Key, class _Tp, class _Compare, class _Allocator> -inline _LIBCPP_HIDE_FROM_ABI -void -swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, - multimap<_Key, _Tp, _Compare, _Allocator>& __y) - _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) -{ - __x.swap(__y); +inline _LIBCPP_HIDE_FROM_ABI void +swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y) + _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { + __x.swap(__y); } #if _LIBCPP_STD_VER >= 20 -template <class _Key, class _Tp, class _Compare, class _Allocator, - class _Predicate> -inline _LIBCPP_HIDE_FROM_ABI - typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type - erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, - _Predicate __pred) { +template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate> +inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type +erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) { return std::__libcpp_erase_if_container(__c, __pred); } #endif @@ -2518,10 +2172,12 @@ _LIBCPP_END_NAMESPACE_STD _LIBCPP_BEGIN_NAMESPACE_STD namespace pmr { template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>> -using map _LIBCPP_AVAILABILITY_PMR = std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; +using map _LIBCPP_AVAILABILITY_PMR = + std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>> -using multimap _LIBCPP_AVAILABILITY_PMR = std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; +using multimap _LIBCPP_AVAILABILITY_PMR = + std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>; } // namespace pmr _LIBCPP_END_NAMESPACE_STD #endif |