X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fbits%2Fstl_tree.h;h=cb5a8eff800e7ea414020deb5ba81b9b7bc15594;hb=4d8cd3a26294ce35abb17668eac2b6c38dd23bd0;hp=ee56bbc75256c94f825f3ca3070131b75d36011d;hpb=c944d49b3bd3667c65c299afd3b1d756084203f4;p=platform%2Fupstream%2Fgcc48.git diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h index ee56bbc..cb5a8ef 100644 --- a/libstdc++-v3/include/bits/stl_tree.h +++ b/libstdc++-v3/include/bits/stl_tree.h @@ -1,8 +1,6 @@ // RB tree implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, -// 2009, 2010, 2011 -// Free Software Foundation, Inc. +// Copyright (C) 2001-2013 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -54,7 +52,7 @@ /** @file bits/stl_tree.h * This is an internal header file, included by other library headers. - * Do not attempt to use it directly. @headername{map or set} + * Do not attempt to use it directly. @headername{map,set} */ #ifndef _STL_TREE_H @@ -64,6 +62,9 @@ #include #include #include +#if __cplusplus >= 201103L +#include +#endif namespace std _GLIBCXX_VISIBILITY(default) { @@ -132,7 +133,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef _Rb_tree_node<_Val>* _Link_type; _Val _M_value_field; -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template _Rb_tree_node(_Args&&... __args) : _Rb_tree_node_base(), @@ -372,7 +373,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_put_node(_Link_type __p) { _M_impl._Node_allocator::deallocate(__p, 1); } -#ifndef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus < 201103L _Link_type _M_create_node(const value_type& __x) { @@ -402,8 +403,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Link_type __tmp = _M_get_node(); __try { - _M_get_Node_allocator().construct(__tmp, - std::forward<_Args>(__args)...); + allocator_traits<_Node_allocator>:: + construct(_M_get_Node_allocator(), __tmp, + std::forward<_Args>(__args)...); } __catch(...) { @@ -450,7 +452,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_node_count(0) { _M_initialize(); } -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a) : _Node_allocator(std::move(__a)), _M_key_compare(__comp), _M_header(), _M_node_count(0) @@ -570,27 +572,50 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typedef std::reverse_iterator const_reverse_iterator; private: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ + pair<_Base_ptr, _Base_ptr> + _M_get_insert_unique_pos(const key_type& __k); + + pair<_Base_ptr, _Base_ptr> + _M_get_insert_equal_pos(const key_type& __k); + + pair<_Base_ptr, _Base_ptr> + _M_get_insert_hint_unique_pos(const_iterator __pos, + const key_type& __k); + + pair<_Base_ptr, _Base_ptr> + _M_get_insert_hint_equal_pos(const_iterator __pos, + const key_type& __k); + +#if __cplusplus >= 201103L template iterator - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v); + _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); + + iterator + _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z); template iterator - _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v); + _M_insert_lower(_Base_ptr __y, _Arg&& __v); template iterator _M_insert_equal_lower(_Arg&& __x); + + iterator + _M_insert_lower_node(_Base_ptr __p, _Link_type __z); + + iterator + _M_insert_equal_lower_node(_Link_type __z); #else iterator - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, + _M_insert_(_Base_ptr __x, _Base_ptr __y, const value_type& __v); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 233. Insertion hints in associative containers. iterator - _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); + _M_insert_lower(_Base_ptr __y, const value_type& __v); iterator _M_insert_equal_lower(const value_type& __x); @@ -638,7 +663,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L _Rb_tree(_Rb_tree&& __x); #endif @@ -710,7 +735,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION swap(_Rb_tree& __t); // Insert/erase. -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template pair _M_insert_unique(_Arg&& __x); @@ -726,6 +751,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template iterator _M_insert_equal_(const_iterator __position, _Arg&& __x); + + template + pair + _M_emplace_unique(_Args&&... __args); + + template + iterator + _M_emplace_equal(_Args&&... __args); + + template + iterator + _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args); + + template + iterator + _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args); #else pair _M_insert_unique(const value_type& __x); @@ -756,7 +797,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_erase_aux(const_iterator __first, const_iterator __last); public: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 130. Associative erase should return an iterator. iterator @@ -789,7 +830,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION size_type erase(const key_type& __x); -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 130. Associative erase should return an iterator. iterator @@ -912,7 +953,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) { __x.swap(__y); } -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: @@ -961,25 +1002,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template #endif typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v) +#if __cplusplus >= 201103L + _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) #else - _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) + _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v) #endif { bool __insert_left = (__x != 0 || __p == _M_end() - || _M_impl._M_key_compare(_KeyOfValue()(__v), + || _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__p))); _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); - _Rb_tree_insert_and_rebalance(__insert_left, __z, - const_cast<_Base_ptr>(__p), + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_impl._M_header); ++_M_impl._M_node_count; return iterator(__z); @@ -987,24 +1027,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template #endif typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v) +#if __cplusplus >= 201103L + _M_insert_lower(_Base_ptr __p, _Arg&& __v) #else - _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) + _M_insert_lower(_Base_ptr __p, const _Val& __v) #endif { - bool __insert_left = (__x != 0 || __p == _M_end() + bool __insert_left = (__p == _M_end() || !_M_impl._M_key_compare(_S_key(__p), _KeyOfValue()(__v))); _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v)); - _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, this->_M_impl._M_header); ++_M_impl._M_node_count; return iterator(__z); @@ -1012,12 +1052,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template #endif typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L _M_insert_equal_lower(_Arg&& __v) #else _M_insert_equal_lower(const _Val& __v) @@ -1031,7 +1071,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? _S_left(__x) : _S_right(__x); } - return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)); + return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v)); } template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - template -#endif pair::iterator, bool> + _Compare, _Alloc>::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_unique(_Arg&& __v) -#else - _M_insert_unique(const _Val& __v) -#endif + _M_get_insert_unique_pos(const key_type& __k) { + typedef pair<_Base_ptr, _Base_ptr> _Res; _Link_type __x = _M_begin(); _Link_type __y = _M_end(); bool __comp = true; while (__x != 0) { __y = __x; - __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); + __comp = _M_impl._M_key_compare(__k, _S_key(__x)); __x = __comp ? _S_left(__x) : _S_right(__x); } iterator __j = iterator(__y); if (__comp) { if (__j == begin()) - return pair - (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true); + return _Res(__x, __y); else --__j; } - if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) - return pair - (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true); - return pair(__j, false); + if (_M_impl._M_key_compare(_S_key(__j._M_node), __k)) + return _Res(__x, __y); + return _Res(__j._M_node, 0); } template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - template -#endif - typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + pair::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_equal(_Arg&& __v) -#else - _M_insert_equal(const _Val& __v) -#endif + _M_get_insert_equal_pos(const key_type& __k) { + typedef pair<_Base_ptr, _Base_ptr> _Res; _Link_type __x = _M_begin(); _Link_type __y = _M_end(); while (__x != 0) { __y = __x; - __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? + __x = _M_impl._M_key_compare(__k, _S_key(__x)) ? _S_left(__x) : _S_right(__x); } - return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__x, __y); } template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L + template +#endif + pair::iterator, bool> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: +#if __cplusplus >= 201103L + _M_insert_unique(_Arg&& __v) +#else + _M_insert_unique(const _Val& __v) +#endif + { + typedef pair _Res; + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_unique_pos(_KeyOfValue()(__v)); + + if (__res.second) + return _Res(_M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v)), + true); + + return _Res(iterator(static_cast<_Link_type>(__res.first)), false); + } + + template +#if __cplusplus >= 201103L template #endif typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_unique_(const_iterator __position, _Arg&& __v) +#if __cplusplus >= 201103L + _M_insert_equal(_Arg&& __v) #else - _M_insert_unique_(const_iterator __position, const _Val& __v) + _M_insert_equal(const _Val& __v) #endif { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_equal_pos(_KeyOfValue()(__v)); + return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v)); + } + + template + pair::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_get_insert_hint_unique_pos(const_iterator __position, + const key_type& __k) + { + iterator __pos = __position._M_const_cast(); + typedef pair<_Base_ptr, _Base_ptr> _Res; + // end() - if (__position._M_node == _M_end()) + if (__pos._M_node == _M_end()) { if (size() > 0 - && _M_impl._M_key_compare(_S_key(_M_rightmost()), - _KeyOfValue()(__v))) - return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v)); + && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) + return _Res(0, _M_rightmost()); else - return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; + return _M_get_insert_unique_pos(__k); } - else if (_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(__position._M_node))) + else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node))) { // First, try before... - const_iterator __before = __position; - if (__position._M_node == _M_leftmost()) // begin() - return _M_insert_(_M_leftmost(), _M_leftmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), - _KeyOfValue()(__v))) + iterator __before = __pos; + if (__pos._M_node == _M_leftmost()) // begin() + return _Res(_M_leftmost(), _M_leftmost()); + else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k)) { if (_S_right(__before._M_node) == 0) - return _M_insert_(0, __before._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(0, __before._M_node); else - return _M_insert_(__position._M_node, - __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__pos._M_node, __pos._M_node); } else - return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; + return _M_get_insert_unique_pos(__k); } - else if (_M_impl._M_key_compare(_S_key(__position._M_node), - _KeyOfValue()(__v))) + else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) { // ... then try after. - const_iterator __after = __position; - if (__position._M_node == _M_rightmost()) - return _M_insert_(0, _M_rightmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key((++__after)._M_node))) + iterator __after = __pos; + if (__pos._M_node == _M_rightmost()) + return _Res(0, _M_rightmost()); + else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node))) { - if (_S_right(__position._M_node) == 0) - return _M_insert_(0, __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + if (_S_right(__pos._M_node) == 0) + return _Res(0, __pos._M_node); else - return _M_insert_(__after._M_node, __after._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__after._M_node, __after._M_node); } else - return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first; + return _M_get_insert_unique_pos(__k); } else // Equivalent keys. - return __position._M_const_cast(); + return _Res(__pos._M_node, 0); } template -#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#if __cplusplus >= 201103L template #endif typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: -#ifdef __GXX_EXPERIMENTAL_CXX0X__ - _M_insert_equal_(const_iterator __position, _Arg&& __v) +#if __cplusplus >= 201103L + _M_insert_unique_(const_iterator __position, _Arg&& __v) #else - _M_insert_equal_(const_iterator __position, const _Val& __v) + _M_insert_unique_(const_iterator __position, const _Val& __v) #endif { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v)); + + if (__res.second) + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v)); + return iterator(static_cast<_Link_type>(__res.first)); + } + + template + pair::_Base_ptr, + typename _Rb_tree<_Key, _Val, _KeyOfValue, + _Compare, _Alloc>::_Base_ptr> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k) + { + iterator __pos = __position._M_const_cast(); + typedef pair<_Base_ptr, _Base_ptr> _Res; + // end() - if (__position._M_node == _M_end()) + if (__pos._M_node == _M_end()) { if (size() > 0 - && !_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key(_M_rightmost()))) - return _M_insert_(0, _M_rightmost(), - _GLIBCXX_FORWARD(_Arg, __v)); + && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost()))) + return _Res(0, _M_rightmost()); else - return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v)); + return _M_get_insert_equal_pos(__k); } - else if (!_M_impl._M_key_compare(_S_key(__position._M_node), - _KeyOfValue()(__v))) + else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k)) { // First, try before... - const_iterator __before = __position; - if (__position._M_node == _M_leftmost()) // begin() - return _M_insert_(_M_leftmost(), _M_leftmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), - _S_key((--__before)._M_node))) + iterator __before = __pos; + if (__pos._M_node == _M_leftmost()) // begin() + return _Res(_M_leftmost(), _M_leftmost()); + else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node))) { if (_S_right(__before._M_node) == 0) - return _M_insert_(0, __before._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(0, __before._M_node); else - return _M_insert_(__position._M_node, - __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__pos._M_node, __pos._M_node); } else - return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v)); + return _M_get_insert_equal_pos(__k); } else { // ... then try after. - const_iterator __after = __position; - if (__position._M_node == _M_rightmost()) - return _M_insert_(0, _M_rightmost(), - _GLIBCXX_FORWARD(_Arg, __v)); - else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), - _KeyOfValue()(__v))) + iterator __after = __pos; + if (__pos._M_node == _M_rightmost()) + return _Res(0, _M_rightmost()); + else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k)) { - if (_S_right(__position._M_node) == 0) - return _M_insert_(0, __position._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + if (_S_right(__pos._M_node) == 0) + return _Res(0, __pos._M_node); else - return _M_insert_(__after._M_node, __after._M_node, - _GLIBCXX_FORWARD(_Arg, __v)); + return _Res(__after._M_node, __after._M_node); } else - return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); + return _Res(0, 0); } } + template +#if __cplusplus >= 201103L + template +#endif + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: +#if __cplusplus >= 201103L + _M_insert_equal_(const_iterator __position, _Arg&& __v) +#else + _M_insert_equal_(const_iterator __position, const _Val& __v) +#endif + { + pair<_Base_ptr, _Base_ptr> __res + = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v)); + + if (__res.second) + return _M_insert_(__res.first, __res.second, + _GLIBCXX_FORWARD(_Arg, __v)); + + return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v)); + } + +#if __cplusplus >= 201103L + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z) + { + bool __insert_left = (__x != 0 || __p == _M_end() + || _M_impl._M_key_compare(_S_key(__z), + _S_key(__p))); + + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + this->_M_impl._M_header); + ++_M_impl._M_node_count; + return iterator(__z); + } + + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_lower_node(_Base_ptr __p, _Link_type __z) + { + bool __insert_left = (__p == _M_end() + || !_M_impl._M_key_compare(_S_key(__p), + _S_key(__z))); + + _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, + this->_M_impl._M_header); + ++_M_impl._M_node_count; + return iterator(__z); + } + + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_insert_equal_lower_node(_Link_type __z) + { + _Link_type __x = _M_begin(); + _Link_type __y = _M_end(); + while (__x != 0) + { + __y = __x; + __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ? + _S_left(__x) : _S_right(__x); + } + return _M_insert_lower_node(__y, __z); + } + + template + template + pair::iterator, bool> + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_unique(_Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + typedef pair _Res; + auto __res = _M_get_insert_unique_pos(_S_key(__z)); + if (__res.second) + return _Res(_M_insert_node(__res.first, __res.second, __z), true); + + _M_destroy_node(__z); + return _Res(iterator(static_cast<_Link_type>(__res.first)), false); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } + + template + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_equal(_Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + auto __res = _M_get_insert_equal_pos(_S_key(__z)); + return _M_insert_node(__res.first, __res.second, __z); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } + + template + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z)); + + if (__res.second) + return _M_insert_node(__res.first, __res.second, __z); + + _M_destroy_node(__z); + return iterator(static_cast<_Link_type>(__res.first)); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } + + template + template + typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator + _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: + _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args) + { + _Link_type __z = _M_create_node(std::forward<_Args>(__args)...); + + __try + { + auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z)); + + if (__res.second) + return _M_insert_node(__res.first, __res.second, __z); + + return _M_insert_equal_lower_node(__z); + } + __catch(...) + { + _M_destroy_node(__z); + __throw_exception_again; + } + } +#endif + template template