// -*- C++ -*- //===----------------------------------------------------------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #ifndef _LIBCPP___TREE #define _LIBCPP___TREE #include <__algorithm/min.h> #include <__assert> #include <__config> #include <__functional/invoke.h> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> #include <__memory/addressof.h> #include <__memory/allocator_traits.h> #include <__memory/compressed_pair.h> #include <__memory/pointer_traits.h> #include <__memory/swap_allocator.h> #include <__memory/unique_ptr.h> #include <__type_traits/can_extract_key.h> #include <__type_traits/conditional.h> #include <__type_traits/is_const.h> #include <__type_traits/is_constructible.h> #include <__type_traits/is_nothrow_assignable.h> #include <__type_traits/is_nothrow_constructible.h> #include <__type_traits/is_pointer.h> #include <__type_traits/is_same.h> #include <__type_traits/is_swappable.h> #include <__type_traits/remove_const_ref.h> #include <__type_traits/remove_cvref.h> #include <__utility/forward.h> #include <__utility/move.h> #include <__utility/pair.h> #include <__utility/swap.h> #include <limits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif _LIBCPP_PUSH_MACROS #include <__undef_macros> _LIBCPP_BEGIN_NAMESPACE_STD template <class, class, class, class> class _LIBCPP_TEMPLATE_VIS map; template <class, class, class, class> class _LIBCPP_TEMPLATE_VIS multimap; template <class, class, class> class _LIBCPP_TEMPLATE_VIS set; template <class, class, class> class _LIBCPP_TEMPLATE_VIS multiset; template <class _Tp, class _Compare, class _Allocator> class __tree; template <class _Tp, class _NodePtr, class _DiffType> class _LIBCPP_TEMPLATE_VIS __tree_iterator; template <class _Tp, class _ConstNodePtr, class _DiffType> class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; template <class _Pointer> class __tree_end_node; template <class _VoidPtr> class __tree_node_base; template <class _Tp, class _VoidPtr> class __tree_node; template <class _Key, class _Value> struct __value_type; template <class _Allocator> class __map_node_destructor; template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator; template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator; /* _NodePtr algorithms The algorithms taking _NodePtr are red black tree algorithms. Those algorithms taking a parameter named __root should assume that __root points to a proper red black tree (unless otherwise specified). Each algorithm herein assumes that __root->__parent_ points to a non-null structure which has a member __left_ which points back to __root. No other member is read or written to at __root->__parent_. __root->__parent_ will be referred to below (in comments only) as end_node. end_node->__left_ is an externably accessible lvalue for __root, and can be changed by node insertion and removal (without explicit reference to end_node). All nodes (with the exception of end_node), even the node referred to as __root, have a non-null __parent_ field. */ // Returns: true if __x is a left child of its parent, else false // Precondition: __x != nullptr. template <class _NodePtr> inline _LIBCPP_HIDE_FROM_ABI bool __tree_is_left_child(_NodePtr __x) _NOEXCEPT { … } // Determines if the subtree rooted at __x is a proper red black subtree. If // __x is a proper subtree, returns the black height (null counts as 1). If // __x is an improper subtree, returns 0. template <class _NodePtr> unsigned __tree_sub_invariant(_NodePtr __x) { … } // Determines if the red black tree rooted at __root is a proper red black tree. // __root == nullptr is a proper tree. Returns true is __root is a proper // red black tree, else returns false. template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI bool __tree_invariant(_NodePtr __root) { … } // Returns: pointer to the left-most node under __x. template <class _NodePtr> inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_min(_NodePtr __x) _NOEXCEPT { … } // Returns: pointer to the right-most node under __x. template <class _NodePtr> inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_max(_NodePtr __x) _NOEXCEPT { … } // Returns: pointer to the next in-order node after __x. template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_next(_NodePtr __x) _NOEXCEPT { … } template <class _EndNodePtr, class _NodePtr> inline _LIBCPP_HIDE_FROM_ABI _EndNodePtr __tree_next_iter(_NodePtr __x) _NOEXCEPT { … } // Returns: pointer to the previous in-order node before __x. // Note: __x may be the end node. template <class _NodePtr, class _EndNodePtr> inline _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT { … } // Returns: pointer to a node which has no children template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI _NodePtr __tree_leaf(_NodePtr __x) _NOEXCEPT { … } // Effects: Makes __x->__right_ the subtree root with __x as its left child // while preserving in-order order. template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI void __tree_left_rotate(_NodePtr __x) _NOEXCEPT { … } // Effects: Makes __x->__left_ the subtree root with __x as its right child // while preserving in-order order. template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI void __tree_right_rotate(_NodePtr __x) _NOEXCEPT { … } // Effects: Rebalances __root after attaching __x to a leaf. // Precondition: __x has no children. // __x == __root or == a direct or indirect child of __root. // If __x were to be unlinked from __root (setting __root to // nullptr if __root == __x), __tree_invariant(__root) == true. // Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_ // may be different than the value passed in as __root. template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI void __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT { … } // Precondition: __z == __root or == a direct or indirect child of __root. // Effects: unlinks __z from the tree rooted at __root, rebalancing as needed. // Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_ // nor any of its children refer to __z. end_node->__left_ // may be different than the value passed in as __root. template <class _NodePtr> _LIBCPP_HIDE_FROM_ABI void __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT { … } // node traits template <class _Tp> struct __is_tree_value_type_imp : false_type { … }; __is_tree_value_type_imp<__value_type<_Key, _Value>>; template <class... _Args> struct __is_tree_value_type : false_type { … }; __is_tree_value_type<_One>; template <class _Tp> struct __tree_key_value_types { … }; __tree_key_value_types<__value_type<_Key, _Tp>>; template <class _VoidPtr> struct __tree_node_base_types { … }; template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>, bool = _KVTypes::__is_map> struct __tree_map_pointer_types { … }; __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true>; template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type> struct __tree_node_types; __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr>>; template <class _ValueTp, class _VoidPtr> struct __make_tree_node_types { … }; // node template <class _Pointer> class __tree_end_node { … }; template <class _VoidPtr> class _LIBCPP_STANDALONE_DEBUG __tree_node_base : public __tree_node_base_types<_VoidPtr>::__end_node_type { … }; template <class _Tp, class _VoidPtr> class _LIBCPP_STANDALONE_DEBUG __tree_node : public __tree_node_base<_VoidPtr> { … }; template <class _Allocator> class __tree_node_destructor { … }; #if _LIBCPP_STD_VER >= 17 template <class _NodeType, class _Alloc> struct __generic_container_node_destructor; __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>; #endif template <class _Tp, class _NodePtr, class _DiffType> class _LIBCPP_TEMPLATE_VIS __tree_iterator { … }; template <class _Tp, class _NodePtr, class _DiffType> class _LIBCPP_TEMPLATE_VIS __tree_const_iterator { … }; template <class _Tp, class _Compare> #ifndef _LIBCPP_CXX03_LANG _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, "the specified comparator type does not provide a viable const call operator") #endif int __diagnose_non_const_comparator(); template <class _Tp, class _Compare, class _Allocator> class __tree { … }; template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) _NOEXCEPT_( is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_copy_constructible<value_compare>::value) : … { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) : … { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a) : … { … } // Precondition: size() != 0 template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_pointer __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_from_tree(__tree* __t) _NOEXCEPT { … } // Precondition: __cache != nullptr // __cache->left_ == nullptr // __cache->right_ == nullptr // This is no longer a red-black tree template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_pointer __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t) { … } template <class _Tp, class _Compare, class _Allocator> template <class _ForwardIterator> void __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last) { … } template <class _Tp, class _Compare, class _Allocator> template <class _InputIterator> void __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last) { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) : … { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_( is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<value_compare>::value) : … { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) : … { … } template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value) { … } template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type) { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>& __tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) _NOEXCEPT_( __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<value_compare>::value&& is_nothrow_move_assignable<__node_allocator>::value) { … } template <class _Tp, class _Compare, class _Allocator> __tree<_Tp, _Compare, _Allocator>::~__tree() { … } template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT { … } template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::swap(__tree& __t) #if _LIBCPP_STD_VER <= 11 _NOEXCEPT_(__is_nothrow_swappable_v<value_compare> && (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>)) #else _NOEXCEPT_(__is_nothrow_swappable_v<value_compare>) #endif { … } template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT { … } // Find lower_bound place to insert // Set __parent to parent of null leaf // Return reference to null leaf template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent, const key_type& __v) { … } // Find upper_bound place to insert // Set __parent to parent of null leaf // Return reference to null leaf template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent, const key_type& __v) { … } // Find leaf place to insert closest to __hint // First check prior to __hint. // Next check after __hint. // Next do O(log N) search. // Set __parent to parent of null leaf // Return reference to null leaf template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v) { … } // Find place to insert if __v doesn't exist // Set __parent to parent of null leaf // Return reference to null leaf // If __v exists, set parent to node of __v and return reference to node of __v template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent, const _Key& __v) { … } // Find place to insert if __v doesn't exist // First check prior to __hint. // Next check after __hint. // Next do O(log N) search. // Set __parent to parent of null leaf // Return reference to null leaf // If __v exists, set parent to node of __v and return reference to node of __v template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer& __tree<_Tp, _Compare, _Allocator>::__find_equal( const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v) { … } template <class _Tp, class _Compare, class _Allocator> void __tree<_Tp, _Compare, _Allocator>::__insert_node_at( __parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node) _NOEXCEPT { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key, class... _Args> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key, class... _Args> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( const_iterator __p, _Key const& __k, _Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::__node_holder __tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> template <class... _Args> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> template <class... _Args> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) { … } template <class _Tp, class _Compare, class _Allocator> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool> __tree<_Tp, _Compare, _Allocator>::__node_assign_unique(const __container_value_type& __v, __node_pointer __nd) { … } template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd) { … } template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd) { … } template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT { … } #if _LIBCPP_STD_VER >= 17 template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle, class _InsertReturnType> _LIBCPP_HIDE_FROM_ABI _InsertReturnType __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(_NodeHandle&& __nh) { … } template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh) { … } template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(key_type const& __key) { … } template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI _NodeHandle __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Tree> _LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source) { … } template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh) { … } template <class _Tp, class _Compare, class _Allocator> template <class _NodeHandle> _LIBCPP_HIDE_FROM_ABI typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Tree> _LIBCPP_HIDE_FROM_ABI void __tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source) { … } #endif // _LIBCPP_STD_VER >= 17 template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p) { … } template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::size_type __tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__lower_bound( const _Key& __v, __node_pointer __root, __iter_pointer __result) const { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> typename __tree<_Tp, _Compare, _Allocator>::const_iterator __tree<_Tp, _Compare, _Allocator>::__upper_bound( const _Key& __v, __node_pointer __root, __iter_pointer __result) const { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, typename __tree<_Tp, _Compare, _Allocator>::const_iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) { … } template <class _Tp, class _Compare, class _Allocator> template <class _Key> pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, typename __tree<_Tp, _Compare, _Allocator>::const_iterator> __tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const { … } template <class _Tp, class _Compare, class _Allocator> typename __tree<_Tp, _Compare, _Allocator>::__node_holder __tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT { … } template <class _Tp, class _Compare, class _Allocator> inline _LIBCPP_HIDE_FROM_ABI void swap(__tree<_Tp, _Compare, _Allocator>& __x, __tree<_Tp, _Compare, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { … } _LIBCPP_END_NAMESPACE_STD _LIBCPP_POP_MACROS #endif // _LIBCPP___TREE
Codebase Browser
chromium