1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2013-2014 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 #ifndef BOOST_INTRUSIVE_BSTREE_HPP 13 #define BOOST_INTRUSIVE_BSTREE_HPP 14 15 #include <boost/intrusive/detail/config_begin.hpp> 16 #include <boost/intrusive/intrusive_fwd.hpp> 17 18 #include <boost/intrusive/detail/assert.hpp> 19 #include <boost/static_assert.hpp> 20 #include <boost/intrusive/intrusive_fwd.hpp> 21 #include <boost/intrusive/bs_set_hook.hpp> 22 #include <boost/intrusive/detail/tree_node.hpp> 23 #include <boost/intrusive/detail/tree_iterator.hpp> 24 #include <boost/intrusive/detail/ebo_functor_holder.hpp> 25 #include <boost/intrusive/detail/mpl.hpp> 26 #include <boost/intrusive/pointer_traits.hpp> 27 #include <boost/intrusive/detail/is_stateful_value_traits.hpp> 28 #include <boost/intrusive/detail/empty_node_checker.hpp> 29 #include <boost/intrusive/detail/default_header_holder.hpp> 30 #include <boost/intrusive/detail/reverse_iterator.hpp> 31 #include <boost/intrusive/detail/exception_disposer.hpp> 32 #include <boost/intrusive/detail/node_cloner_disposer.hpp> 33 #include <boost/intrusive/detail/key_nodeptr_comp.hpp> 34 #include <boost/intrusive/detail/simple_disposers.hpp> 35 #include <boost/intrusive/detail/size_holder.hpp> 36 #include <boost/intrusive/detail/algo_type.hpp> 37 #include <boost/intrusive/detail/algorithm.hpp> 38 #include <boost/intrusive/detail/tree_value_compare.hpp> 39 40 #include <boost/intrusive/detail/get_value_traits.hpp> 41 #include <boost/intrusive/bstree_algorithms.hpp> 42 #include <boost/intrusive/link_mode.hpp> 43 #include <boost/intrusive/parent_from_member.hpp> 44 #include <boost/move/utility_core.hpp> 45 #include <boost/move/adl_move_swap.hpp> 46 47 #include <boost/intrusive/detail/minimal_pair_header.hpp> 48 #include <cstddef> //size_t... 49 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal_to 50 51 #if defined(BOOST_HAS_PRAGMA_ONCE) 52 # pragma once 53 #endif 54 55 namespace boost { 56 namespace intrusive { 57 58 /// @cond 59 60 struct default_bstree_hook_applier 61 { template <class T> struct apply{ typedef typename T::default_bstree_hook type; }; }; 62 63 template<> 64 struct is_default_hook_tag<default_bstree_hook_applier> 65 { static const bool value = true; }; 66 67 struct bstree_defaults 68 { 69 typedef default_bstree_hook_applier proto_value_traits; 70 static const bool constant_time_size = true; 71 typedef std::size_t size_type; 72 typedef void compare; 73 typedef void key_of_value; 74 static const bool floating_point = true; //For sgtree 75 typedef void priority; //For treap 76 typedef void header_holder_type; 77 }; 78 79 template<class ValueTraits, algo_types AlgoType, typename HeaderHolder> 80 struct bstbase3 81 { 82 typedef ValueTraits value_traits; 83 typedef typename value_traits::node_traits node_traits; 84 typedef typename node_traits::node node_type; 85 typedef typename get_algo<AlgoType, node_traits>::type node_algorithms; 86 typedef typename node_traits::node_ptr node_ptr; 87 typedef typename node_traits::const_node_ptr const_node_ptr; 88 typedef tree_iterator<value_traits, false> iterator; 89 typedef tree_iterator<value_traits, true> const_iterator; 90 typedef boost::intrusive::reverse_iterator<iterator> reverse_iterator; 91 typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_iterator; 92 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; 93 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; 94 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type; 95 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; 96 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; 97 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; 98 typedef typename detail::get_header_holder_type 99 < value_traits,HeaderHolder >::type header_holder_type; 100 101 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; 102 static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; 103 static const bool has_container_from_iterator = 104 detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; 105 106 struct holder_t : public ValueTraits 107 { holder_tboost::intrusive::bstbase3::holder_t108 BOOST_INTRUSIVE_FORCEINLINE explicit holder_t(const ValueTraits &vtraits) 109 : ValueTraits(vtraits) 110 {} 111 header_holder_type root; 112 } holder; 113 get_tree_base_from_end_iteratorboost::intrusive::bstbase3114 static bstbase3 &get_tree_base_from_end_iterator(const const_iterator &end_iterator) 115 { 116 BOOST_STATIC_ASSERT(has_container_from_iterator); 117 node_ptr p = end_iterator.pointed_node(); 118 header_holder_type* h = header_holder_type::get_holder(p); 119 holder_t *holder = get_parent_from_member<holder_t, header_holder_type>(h, &holder_t::root); 120 bstbase3 *base = get_parent_from_member<bstbase3, holder_t> (holder, &bstbase3::holder); 121 return *base; 122 } 123 bstbase3boost::intrusive::bstbase3124 BOOST_INTRUSIVE_FORCEINLINE bstbase3(const ValueTraits &vtraits) 125 : holder(vtraits) 126 { 127 node_algorithms::init_header(this->header_ptr()); 128 } 129 header_ptrboost::intrusive::bstbase3130 BOOST_INTRUSIVE_FORCEINLINE node_ptr header_ptr() 131 { return holder.root.get_node(); } 132 header_ptrboost::intrusive::bstbase3133 BOOST_INTRUSIVE_FORCEINLINE const_node_ptr header_ptr() const 134 { return holder.root.get_node(); } 135 get_value_traitsboost::intrusive::bstbase3136 BOOST_INTRUSIVE_FORCEINLINE const value_traits &get_value_traits() const 137 { return this->holder; } 138 get_value_traitsboost::intrusive::bstbase3139 BOOST_INTRUSIVE_FORCEINLINE value_traits &get_value_traits() 140 { return this->holder; } 141 142 typedef typename boost::intrusive::value_traits_pointers 143 <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; 144 priv_value_traits_ptrboost::intrusive::bstbase3145 BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr priv_value_traits_ptr() const 146 { return pointer_traits<const_value_traits_ptr>::pointer_to(this->get_value_traits()); } 147 beginboost::intrusive::bstbase3148 iterator begin() 149 { return iterator(node_algorithms::begin_node(this->header_ptr()), this->priv_value_traits_ptr()); } 150 beginboost::intrusive::bstbase3151 BOOST_INTRUSIVE_FORCEINLINE const_iterator begin() const 152 { return cbegin(); } 153 cbeginboost::intrusive::bstbase3154 const_iterator cbegin() const 155 { return const_iterator(node_algorithms::begin_node(this->header_ptr()), this->priv_value_traits_ptr()); } 156 endboost::intrusive::bstbase3157 iterator end() 158 { return iterator(node_algorithms::end_node(this->header_ptr()), this->priv_value_traits_ptr()); } 159 endboost::intrusive::bstbase3160 BOOST_INTRUSIVE_FORCEINLINE const_iterator end() const 161 { return cend(); } 162 cendboost::intrusive::bstbase3163 BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const 164 { return const_iterator(node_algorithms::end_node(this->header_ptr()), this->priv_value_traits_ptr()); } 165 rootboost::intrusive::bstbase3166 BOOST_INTRUSIVE_FORCEINLINE iterator root() 167 { return iterator(node_algorithms::root_node(this->header_ptr()), this->priv_value_traits_ptr()); } 168 rootboost::intrusive::bstbase3169 BOOST_INTRUSIVE_FORCEINLINE const_iterator root() const 170 { return croot(); } 171 crootboost::intrusive::bstbase3172 BOOST_INTRUSIVE_FORCEINLINE const_iterator croot() const 173 { return const_iterator(node_algorithms::root_node(this->header_ptr()), this->priv_value_traits_ptr()); } 174 rbeginboost::intrusive::bstbase3175 BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rbegin() 176 { return reverse_iterator(end()); } 177 rbeginboost::intrusive::bstbase3178 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rbegin() const 179 { return const_reverse_iterator(end()); } 180 crbeginboost::intrusive::bstbase3181 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crbegin() const 182 { return const_reverse_iterator(end()); } 183 rendboost::intrusive::bstbase3184 BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rend() 185 { return reverse_iterator(begin()); } 186 rendboost::intrusive::bstbase3187 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rend() const 188 { return const_reverse_iterator(begin()); } 189 crendboost::intrusive::bstbase3190 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crend() const 191 { return const_reverse_iterator(begin()); } 192 replace_nodeboost::intrusive::bstbase3193 void replace_node(iterator replace_this, reference with_this) 194 { 195 node_algorithms::replace_node( get_value_traits().to_node_ptr(*replace_this) 196 , this->header_ptr() 197 , get_value_traits().to_node_ptr(with_this)); 198 if(safemode_or_autounlink) 199 node_algorithms::init(replace_this.pointed_node()); 200 } 201 rebalanceboost::intrusive::bstbase3202 BOOST_INTRUSIVE_FORCEINLINE void rebalance() 203 { node_algorithms::rebalance(this->header_ptr()); } 204 rebalance_subtreeboost::intrusive::bstbase3205 iterator rebalance_subtree(iterator root) 206 { return iterator(node_algorithms::rebalance_subtree(root.pointed_node()), this->priv_value_traits_ptr()); } 207 s_iterator_toboost::intrusive::bstbase3208 static iterator s_iterator_to(reference value) 209 { 210 BOOST_STATIC_ASSERT((!stateful_value_traits)); 211 return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr()); 212 } 213 s_iterator_toboost::intrusive::bstbase3214 static const_iterator s_iterator_to(const_reference value) 215 { 216 BOOST_STATIC_ASSERT((!stateful_value_traits)); 217 return const_iterator (value_traits::to_node_ptr(*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value))), const_value_traits_ptr()); 218 } 219 iterator_toboost::intrusive::bstbase3220 iterator iterator_to(reference value) 221 { return iterator (this->get_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); } 222 iterator_toboost::intrusive::bstbase3223 const_iterator iterator_to(const_reference value) const 224 { return const_iterator (this->get_value_traits().to_node_ptr(*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value))), this->priv_value_traits_ptr()); } 225 init_nodeboost::intrusive::bstbase3226 BOOST_INTRUSIVE_FORCEINLINE static void init_node(reference value) 227 { node_algorithms::init(value_traits::to_node_ptr(value)); } 228 229 }; 230 231 template<class Less, class T> 232 struct get_compare 233 { 234 typedef Less type; 235 }; 236 237 template<class T> 238 struct get_compare<void, T> 239 { 240 typedef ::std::less<T> type; 241 }; 242 243 template<class KeyOfValue, class T> 244 struct get_key_of_value 245 { 246 typedef KeyOfValue type; 247 }; 248 249 template<class T> 250 struct get_key_of_value<void, T> 251 { 252 typedef ::boost::intrusive::detail::identity<T> type; 253 }; 254 255 template<class ValuePtr, class VoidOrKeyOfValue, class VoidOrKeyComp> 256 struct bst_key_types 257 { 258 typedef typename 259 boost::movelib::pointer_element<ValuePtr>::type value_type; 260 typedef typename get_key_of_value 261 < VoidOrKeyOfValue, value_type>::type key_of_value; 262 typedef typename key_of_value::type key_type; 263 typedef typename get_compare< VoidOrKeyComp 264 , key_type 265 >::type key_compare; 266 typedef tree_value_compare 267 <ValuePtr, key_compare, key_of_value> value_compare; 268 }; 269 270 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, algo_types AlgoType, typename HeaderHolder> 271 struct bstbase2 272 //Put the (possibly empty) functor in the first position to get EBO in MSVC 273 //Use public inheritance to avoid MSVC bugs with closures 274 : public detail::ebo_functor_holder 275 < typename bst_key_types 276 < typename ValueTraits::pointer 277 , VoidOrKeyOfValue 278 , VoidOrKeyComp 279 280 >::value_compare 281 > 282 , public bstbase3<ValueTraits, AlgoType, HeaderHolder> 283 { 284 typedef bstbase3<ValueTraits, AlgoType, HeaderHolder> treeheader_t; 285 typedef bst_key_types< typename ValueTraits::pointer 286 , VoidOrKeyOfValue 287 , VoidOrKeyComp> key_types; 288 typedef typename treeheader_t::value_traits value_traits; 289 typedef typename treeheader_t::node_algorithms node_algorithms; 290 typedef typename ValueTraits::value_type value_type; 291 typedef typename key_types::key_type key_type; 292 typedef typename key_types::key_of_value key_of_value; 293 typedef typename key_types::key_compare key_compare; 294 typedef typename key_types::value_compare value_compare; 295 typedef typename treeheader_t::iterator iterator; 296 typedef typename treeheader_t::const_iterator const_iterator; 297 typedef typename treeheader_t::node_ptr node_ptr; 298 typedef typename treeheader_t::const_node_ptr const_node_ptr; 299 bstbase2boost::intrusive::bstbase2300 bstbase2(const key_compare &comp, const ValueTraits &vtraits) 301 : detail::ebo_functor_holder<value_compare>(value_compare(comp)), treeheader_t(vtraits) 302 {} 303 compboost::intrusive::bstbase2304 const value_compare &comp() const 305 { return this->get(); } 306 compboost::intrusive::bstbase2307 value_compare &comp() 308 { return this->get(); } 309 310 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; 311 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; 312 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; 313 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; 314 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; 315 typedef typename node_algorithms::insert_commit_data insert_commit_data; 316 value_compboost::intrusive::bstbase2317 BOOST_INTRUSIVE_FORCEINLINE value_compare value_comp() const 318 { return this->comp(); } 319 key_compboost::intrusive::bstbase2320 BOOST_INTRUSIVE_FORCEINLINE key_compare key_comp() const 321 { return this->comp().key_comp(); } 322 323 //lower_bound lower_boundboost::intrusive::bstbase2324 BOOST_INTRUSIVE_FORCEINLINE iterator lower_bound(const key_type &key) 325 { return this->lower_bound(key, this->key_comp()); } 326 lower_boundboost::intrusive::bstbase2327 BOOST_INTRUSIVE_FORCEINLINE const_iterator lower_bound(const key_type &key) const 328 { return this->lower_bound(key, this->key_comp()); } 329 330 template<class KeyType, class KeyTypeKeyCompare> lower_boundboost::intrusive::bstbase2331 iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) 332 { 333 return iterator(node_algorithms::lower_bound 334 (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); 335 } 336 337 template<class KeyType, class KeyTypeKeyCompare> lower_boundboost::intrusive::bstbase2338 const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const 339 { 340 return const_iterator(node_algorithms::lower_bound 341 (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); 342 } 343 344 //upper_bound upper_boundboost::intrusive::bstbase2345 BOOST_INTRUSIVE_FORCEINLINE iterator upper_bound(const key_type &key) 346 { return this->upper_bound(key, this->key_comp()); } 347 348 template<class KeyType, class KeyTypeKeyCompare> upper_boundboost::intrusive::bstbase2349 iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) 350 { 351 return iterator(node_algorithms::upper_bound 352 (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); 353 } 354 upper_boundboost::intrusive::bstbase2355 BOOST_INTRUSIVE_FORCEINLINE const_iterator upper_bound(const key_type &key) const 356 { return this->upper_bound(key, this->key_comp()); } 357 358 template<class KeyType, class KeyTypeKeyCompare> upper_boundboost::intrusive::bstbase2359 const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const 360 { 361 return const_iterator(node_algorithms::upper_bound 362 (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); 363 } 364 365 template<class KeyTypeKeyCompare> 366 struct key_node_comp_ret 367 { typedef detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value> type; }; 368 369 template<class KeyTypeKeyCompare> key_node_compboost::intrusive::bstbase2370 BOOST_INTRUSIVE_FORCEINLINE typename key_node_comp_ret<KeyTypeKeyCompare>::type key_node_comp(KeyTypeKeyCompare comp) const 371 { 372 return detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value>(comp, &this->get_value_traits()); 373 } 374 375 //find findboost::intrusive::bstbase2376 BOOST_INTRUSIVE_FORCEINLINE iterator find(const key_type &key) 377 { return this->find(key, this->key_comp()); } 378 379 template<class KeyType, class KeyTypeKeyCompare> findboost::intrusive::bstbase2380 iterator find(const KeyType &key, KeyTypeKeyCompare comp) 381 { 382 return iterator 383 (node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); 384 } 385 findboost::intrusive::bstbase2386 BOOST_INTRUSIVE_FORCEINLINE const_iterator find(const key_type &key) const 387 { return this->find(key, this->key_comp()); } 388 389 template<class KeyType, class KeyTypeKeyCompare> findboost::intrusive::bstbase2390 const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const 391 { 392 return const_iterator 393 (node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); 394 } 395 396 //equal_range equal_rangeboost::intrusive::bstbase2397 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type &key) 398 { return this->equal_range(key, this->key_comp()); } 399 400 template<class KeyType, class KeyTypeKeyCompare> equal_rangeboost::intrusive::bstbase2401 std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp) 402 { 403 std::pair<node_ptr, node_ptr> ret 404 (node_algorithms::equal_range(this->header_ptr(), key, this->key_node_comp(comp))); 405 return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr()) 406 , iterator(ret.second, this->priv_value_traits_ptr())); 407 } 408 409 BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator> equal_rangeboost::intrusive::bstbase2410 equal_range(const key_type &key) const 411 { return this->equal_range(key, this->key_comp()); } 412 413 template<class KeyType, class KeyTypeKeyCompare> 414 std::pair<const_iterator, const_iterator> equal_rangeboost::intrusive::bstbase2415 equal_range(const KeyType &key, KeyTypeKeyCompare comp) const 416 { 417 std::pair<node_ptr, node_ptr> ret 418 (node_algorithms::equal_range(this->header_ptr(), key, this->key_node_comp(comp))); 419 return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr()) 420 , const_iterator(ret.second, this->priv_value_traits_ptr())); 421 } 422 423 //lower_bound_range lower_bound_rangeboost::intrusive::bstbase2424 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> lower_bound_range(const key_type &key) 425 { return this->lower_bound_range(key, this->key_comp()); } 426 427 template<class KeyType, class KeyTypeKeyCompare> lower_bound_rangeboost::intrusive::bstbase2428 std::pair<iterator,iterator> lower_bound_range(const KeyType &key, KeyTypeKeyCompare comp) 429 { 430 std::pair<node_ptr, node_ptr> ret 431 (node_algorithms::lower_bound_range(this->header_ptr(), key, this->key_node_comp(comp))); 432 return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr()) 433 , iterator(ret.second, this->priv_value_traits_ptr())); 434 } 435 436 BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator> lower_bound_rangeboost::intrusive::bstbase2437 lower_bound_range(const key_type &key) const 438 { return this->lower_bound_range(key, this->key_comp()); } 439 440 template<class KeyType, class KeyTypeKeyCompare> 441 std::pair<const_iterator, const_iterator> lower_bound_rangeboost::intrusive::bstbase2442 lower_bound_range(const KeyType &key, KeyTypeKeyCompare comp) const 443 { 444 std::pair<node_ptr, node_ptr> ret 445 (node_algorithms::lower_bound_range(this->header_ptr(), key, this->key_node_comp(comp))); 446 return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr()) 447 , const_iterator(ret.second, this->priv_value_traits_ptr())); 448 } 449 450 //bounded_range bounded_rangeboost::intrusive::bstbase2451 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> bounded_range 452 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) 453 { return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); } 454 455 template<class KeyType, class KeyTypeKeyCompare> bounded_rangeboost::intrusive::bstbase2456 std::pair<iterator,iterator> bounded_range 457 (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) 458 { 459 std::pair<node_ptr, node_ptr> ret 460 (node_algorithms::bounded_range 461 (this->header_ptr(), lower_key, upper_key, this->key_node_comp(comp), left_closed, right_closed)); 462 return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr()) 463 , iterator(ret.second, this->priv_value_traits_ptr())); 464 } 465 bounded_rangeboost::intrusive::bstbase2466 BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator,const_iterator> bounded_range 467 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const 468 { return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); } 469 470 template<class KeyType, class KeyTypeKeyCompare> bounded_rangeboost::intrusive::bstbase2471 std::pair<const_iterator,const_iterator> bounded_range 472 (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const 473 { 474 std::pair<node_ptr, node_ptr> ret 475 (node_algorithms::bounded_range 476 (this->header_ptr(), lower_key, upper_key, this->key_node_comp(comp), left_closed, right_closed)); 477 return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr()) 478 , const_iterator(ret.second, this->priv_value_traits_ptr())); 479 } 480 481 //insert_unique_check insert_unique_checkboost::intrusive::bstbase2482 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check 483 (const key_type &key, insert_commit_data &commit_data) 484 { return this->insert_unique_check(key, this->key_comp(), commit_data); } 485 insert_unique_checkboost::intrusive::bstbase2486 BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check 487 (const_iterator hint, const key_type &key, insert_commit_data &commit_data) 488 { return this->insert_unique_check(hint, key, this->key_comp(), commit_data); } 489 490 template<class KeyType, class KeyTypeKeyCompare> BOOST_INTRUSIVE_DOC1STboost::intrusive::bstbase2491 BOOST_INTRUSIVE_DOC1ST(std::pair<iterator BOOST_INTRUSIVE_I bool> 492 , typename detail::disable_if_convertible 493 <KeyType BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I 494 std::pair<iterator BOOST_INTRUSIVE_I bool> >::type) 495 insert_unique_check 496 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data) 497 { 498 std::pair<node_ptr, bool> ret = 499 (node_algorithms::insert_unique_check 500 (this->header_ptr(), key, this->key_node_comp(comp), commit_data)); 501 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); 502 } 503 504 template<class KeyType, class KeyTypeKeyCompare> insert_unique_checkboost::intrusive::bstbase2505 std::pair<iterator, bool> insert_unique_check 506 (const_iterator hint, const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data) 507 { 508 std::pair<node_ptr, bool> ret = 509 (node_algorithms::insert_unique_check 510 (this->header_ptr(), hint.pointed_node(), key, this->key_node_comp(comp), commit_data)); 511 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); 512 } 513 }; 514 515 //Due to MSVC's EBO implementation, to save space and maintain the ABI, we must put the non-empty size member 516 //in the first position, but if size is not going to be stored then we'll use an specialization 517 //that doesn't inherit from size_holder 518 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder> 519 struct bstbase_hack 520 : public detail::size_holder<ConstantTimeSize, SizeType> 521 , public bstbase2 < ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> 522 { 523 typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type; 524 typedef typename base_type::key_compare key_compare; 525 typedef typename base_type::value_compare value_compare; 526 typedef SizeType size_type; 527 typedef typename base_type::node_traits node_traits; 528 typedef typename get_algo 529 <AlgoType, node_traits>::type algo_type; 530 bstbase_hackboost::intrusive::bstbase_hack531 BOOST_INTRUSIVE_FORCEINLINE bstbase_hack(const key_compare & comp, const ValueTraits &vtraits) 532 : base_type(comp, vtraits) 533 { 534 this->sz_traits().set_size(size_type(0)); 535 } 536 537 typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits; 538 sz_traitsboost::intrusive::bstbase_hack539 BOOST_INTRUSIVE_FORCEINLINE size_traits &sz_traits() 540 { return static_cast<size_traits &>(*this); } 541 sz_traitsboost::intrusive::bstbase_hack542 BOOST_INTRUSIVE_FORCEINLINE const size_traits &sz_traits() const 543 { return static_cast<const size_traits &>(*this); } 544 }; 545 546 //Specialization for ConstantTimeSize == false 547 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder> 548 struct bstbase_hack<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder> 549 : public bstbase2 < ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> 550 { 551 typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type; 552 typedef typename base_type::value_compare value_compare; 553 typedef typename base_type::key_compare key_compare; bstbase_hackboost::intrusive::bstbase_hack554 BOOST_INTRUSIVE_FORCEINLINE bstbase_hack(const key_compare & comp, const ValueTraits &vtraits) 555 : base_type(comp, vtraits) 556 {} 557 558 typedef detail::size_holder<false, SizeType> size_traits; 559 sz_traitsboost::intrusive::bstbase_hack560 BOOST_INTRUSIVE_FORCEINLINE size_traits sz_traits() const 561 { return size_traits(); } 562 }; 563 564 //This class will 565 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder> 566 struct bstbase 567 : public bstbase_hack< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> 568 { 569 typedef bstbase_hack< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> base_type; 570 typedef ValueTraits value_traits; 571 typedef typename base_type::value_compare value_compare; 572 typedef typename base_type::key_compare key_compare; 573 typedef typename base_type::const_reference const_reference; 574 typedef typename base_type::reference reference; 575 typedef typename base_type::iterator iterator; 576 typedef typename base_type::const_iterator const_iterator; 577 typedef typename base_type::node_traits node_traits; 578 typedef typename get_algo 579 <AlgoType, node_traits>::type node_algorithms; 580 typedef SizeType size_type; 581 bstbaseboost::intrusive::bstbase582 BOOST_INTRUSIVE_FORCEINLINE bstbase(const key_compare & comp, const ValueTraits &vtraits) 583 : base_type(comp, vtraits) 584 {} 585 586 //Detach all inserted nodes. This will add exception safety to bstree_impl 587 //constructors inserting elements. ~bstbaseboost::intrusive::bstbase588 ~bstbase() 589 { 590 if(is_safe_autounlink<value_traits::link_mode>::value){ 591 node_algorithms::clear_and_dispose 592 ( this->header_ptr() 593 , detail::node_disposer<detail::null_disposer, value_traits, AlgoType> 594 (detail::null_disposer(), &this->get_value_traits())); 595 node_algorithms::init(this->header_ptr()); 596 } 597 } 598 }; 599 600 601 /// @endcond 602 603 //! The class template bstree is an unbalanced intrusive binary search tree 604 //! container. The no-throw guarantee holds only, if the key_compare object 605 //! doesn't throw. 606 //! 607 //! The complexity guarantees only hold if the tree is balanced, logarithmic 608 //! complexity would increase to linear if the tree is totally unbalanced. 609 //! 610 //! The template parameter \c T is the type to be managed by the container. 611 //! The user can specify additional options and if no options are provided 612 //! default options are used. 613 //! 614 //! The container supports the following options: 615 //! \c base_hook<>/member_hook<>/value_traits<>, 616 //! \c constant_time_size<>, \c size_type<> and 617 //! \c compare<>. 618 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 619 template<class T, class ...Options> 620 #else 621 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder> 622 #endif 623 class bstree_impl 624 : public bstbase<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> 625 { 626 public: 627 /// @cond 628 typedef bstbase<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> data_type; 629 typedef tree_iterator<ValueTraits, false> iterator_type; 630 typedef tree_iterator<ValueTraits, true> const_iterator_type; 631 /// @endcond 632 633 typedef BOOST_INTRUSIVE_IMPDEF(ValueTraits) value_traits; 634 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; 635 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; 636 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type; 637 typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_type) key_type; 638 typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_of_value) key_of_value; 639 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; 640 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; 641 typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; 642 typedef BOOST_INTRUSIVE_IMPDEF(SizeType) size_type; 643 typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::value_compare) value_compare; 644 typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_compare) key_compare; 645 typedef BOOST_INTRUSIVE_IMPDEF(iterator_type) iterator; 646 typedef BOOST_INTRUSIVE_IMPDEF(const_iterator_type) const_iterator; 647 typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<iterator>) reverse_iterator; 648 typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<const_iterator>) const_reverse_iterator; 649 typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::node_traits) node_traits; 650 typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::node) node; 651 typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::node_ptr) node_ptr; 652 typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::const_node_ptr) const_node_ptr; 653 /// @cond 654 typedef typename get_algo<AlgoType, node_traits>::type algo_type; 655 /// @endcond 656 typedef BOOST_INTRUSIVE_IMPDEF(algo_type) node_algorithms; 657 658 static const bool constant_time_size = ConstantTimeSize; 659 static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; 660 /// @cond 661 private: 662 663 //noncopyable 664 BOOST_MOVABLE_BUT_NOT_COPYABLE(bstree_impl) 665 666 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; 667 668 //Constant-time size is incompatible with auto-unlink hooks! 669 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); 670 671 672 protected: 673 674 675 /// @endcond 676 677 public: 678 679 typedef typename node_algorithms::insert_commit_data insert_commit_data; 680 681 //! <b>Effects</b>: Constructs an empty container. 682 //! 683 //! <b>Complexity</b>: Constant. 684 //! 685 //! <b>Throws</b>: If value_traits::node_traits::node 686 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 687 //! or the copy constructor of the key_compare object throws. Basic guarantee. bstree_impl()688 bstree_impl() 689 : data_type(key_compare(), value_traits()) 690 {} 691 692 //! <b>Effects</b>: Constructs an empty container with given comparison and traits. 693 //! 694 //! <b>Complexity</b>: Constant. 695 //! 696 //! <b>Throws</b>: If value_traits::node_traits::node 697 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 698 //! or the copy constructor of the key_compare object throws. Basic guarantee. bstree_impl(const key_compare & cmp,const value_traits & v_traits=value_traits ())699 explicit bstree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) 700 : data_type(cmp, v_traits) 701 {} 702 703 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. 704 //! cmp must be a comparison function that induces a strict weak ordering. 705 //! 706 //! <b>Effects</b>: Constructs an empty container and inserts elements from 707 //! [b, e). 708 //! 709 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using 710 //! comp and otherwise N * log N, where N is the distance between first and last. 711 //! 712 //! <b>Throws</b>: If value_traits::node_traits::node 713 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 714 //! or the copy constructor/operator() of the key_compare object throws. Basic guarantee. 715 template<class Iterator> bstree_impl(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())716 bstree_impl( bool unique, Iterator b, Iterator e 717 , const key_compare &cmp = key_compare() 718 , const value_traits &v_traits = value_traits()) 719 : data_type(cmp, v_traits) 720 { 721 //bstbase releases elements in case of exceptions 722 if(unique) 723 this->insert_unique(b, e); 724 else 725 this->insert_equal(b, e); 726 } 727 728 //! <b>Effects</b>: Constructs a container moving resources from another container. 729 //! Internal comparison object and value traits are move constructed and 730 //! nodes belonging to x (except the node representing the "end") are linked to *this. 731 //! 732 //! <b>Complexity</b>: Constant. 733 //! 734 //! <b>Throws</b>: If value_traits::node_traits::node's 735 //! move constructor throws (this does not happen with predefined Boost.Intrusive hooks) 736 //! or the move constructor of the comparison objet throws. bstree_impl(BOOST_RV_REF (bstree_impl)x)737 bstree_impl(BOOST_RV_REF(bstree_impl) x) 738 : data_type(::boost::move(x.comp()), ::boost::move(x.get_value_traits())) 739 { 740 this->swap(x); 741 } 742 743 //! <b>Effects</b>: Equivalent to swap 744 //! operator =(BOOST_RV_REF (bstree_impl)x)745 BOOST_INTRUSIVE_FORCEINLINE bstree_impl& operator=(BOOST_RV_REF(bstree_impl) x) 746 { this->swap(x); return *this; } 747 748 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 749 //! <b>Effects</b>: Detaches all elements from this. The objects in the set 750 //! are not deleted (i.e. no destructors are called), but the nodes according to 751 //! the value_traits template parameter are reinitialized and thus can be reused. 752 //! 753 //! <b>Complexity</b>: Linear to elements contained in *this. 754 //! 755 //! <b>Throws</b>: Nothing. ~bstree_impl()756 ~bstree_impl() 757 {} 758 759 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the container. 760 //! 761 //! <b>Complexity</b>: Constant. 762 //! 763 //! <b>Throws</b>: Nothing. 764 iterator begin(); 765 766 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the container. 767 //! 768 //! <b>Complexity</b>: Constant. 769 //! 770 //! <b>Throws</b>: Nothing. 771 const_iterator begin() const; 772 773 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the container. 774 //! 775 //! <b>Complexity</b>: Constant. 776 //! 777 //! <b>Throws</b>: Nothing. 778 const_iterator cbegin() const; 779 780 //! <b>Effects</b>: Returns an iterator pointing to the end of the container. 781 //! 782 //! <b>Complexity</b>: Constant. 783 //! 784 //! <b>Throws</b>: Nothing. 785 iterator end(); 786 787 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the container. 788 //! 789 //! <b>Complexity</b>: Constant. 790 //! 791 //! <b>Throws</b>: Nothing. 792 const_iterator end() const; 793 794 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the container. 795 //! 796 //! <b>Complexity</b>: Constant. 797 //! 798 //! <b>Throws</b>: Nothing. 799 const_iterator cend() const; 800 801 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the 802 //! reversed container. 803 //! 804 //! <b>Complexity</b>: Constant. 805 //! 806 //! <b>Throws</b>: Nothing. 807 reverse_iterator rbegin(); 808 809 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 810 //! of the reversed container. 811 //! 812 //! <b>Complexity</b>: Constant. 813 //! 814 //! <b>Throws</b>: Nothing. 815 const_reverse_iterator rbegin() const; 816 817 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 818 //! of the reversed container. 819 //! 820 //! <b>Complexity</b>: Constant. 821 //! 822 //! <b>Throws</b>: Nothing. 823 const_reverse_iterator crbegin() const; 824 825 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 826 //! of the reversed container. 827 //! 828 //! <b>Complexity</b>: Constant. 829 //! 830 //! <b>Throws</b>: Nothing. 831 reverse_iterator rend(); 832 833 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 834 //! of the reversed container. 835 //! 836 //! <b>Complexity</b>: Constant. 837 //! 838 //! <b>Throws</b>: Nothing. 839 const_reverse_iterator rend() const; 840 841 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 842 //! of the reversed container. 843 //! 844 //! <b>Complexity</b>: Constant. 845 //! 846 //! <b>Throws</b>: Nothing. 847 const_reverse_iterator crend() const; 848 849 //! <b>Effects</b>: Returns a iterator pointing to the root node of the container or end() if not present. 850 //! 851 //! <b>Complexity</b>: Constant. 852 //! 853 //! <b>Throws</b>: Nothing. 854 iterator root(); 855 856 //! <b>Effects</b>: Returns a const_iterator pointing to the root node of the container or cend() if not present. 857 //! 858 //! <b>Complexity</b>: Constant. 859 //! 860 //! <b>Throws</b>: Nothing. 861 const_iterator root() const; 862 863 //! <b>Effects</b>: Returns a const_iterator pointing to the root node of the container or cend() if not present. 864 //! 865 //! <b>Complexity</b>: Constant. 866 //! 867 //! <b>Throws</b>: Nothing. 868 const_iterator croot() const; 869 870 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 871 872 //! <b>Precondition</b>: end_iterator must be a valid end iterator 873 //! of the container. 874 //! 875 //! <b>Effects</b>: Returns a const reference to the container associated to the end iterator 876 //! 877 //! <b>Throws</b>: Nothing. 878 //! 879 //! <b>Complexity</b>: Constant. container_from_end_iterator(iterator end_iterator)880 static bstree_impl &container_from_end_iterator(iterator end_iterator) 881 { 882 return static_cast<bstree_impl&> 883 (data_type::get_tree_base_from_end_iterator(end_iterator)); 884 } 885 886 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator 887 //! of the container. 888 //! 889 //! <b>Effects</b>: Returns a const reference to the container associated to the iterator 890 //! 891 //! <b>Throws</b>: Nothing. 892 //! 893 //! <b>Complexity</b>: Constant. container_from_end_iterator(const_iterator end_iterator)894 static const bstree_impl &container_from_end_iterator(const_iterator end_iterator) 895 { 896 return static_cast<bstree_impl&> 897 (data_type::get_tree_base_from_end_iterator(end_iterator)); 898 } 899 900 //! <b>Precondition</b>: it must be a valid iterator 901 //! of the container. 902 //! 903 //! <b>Effects</b>: Returns a const reference to the container associated to the iterator 904 //! 905 //! <b>Throws</b>: Nothing. 906 //! 907 //! <b>Complexity</b>: Logarithmic. container_from_iterator(iterator it)908 static bstree_impl &container_from_iterator(iterator it) 909 { return container_from_end_iterator(it.end_iterator_from_it()); } 910 911 //! <b>Precondition</b>: it must be a valid end const_iterator 912 //! of container. 913 //! 914 //! <b>Effects</b>: Returns a const reference to the container associated to the end iterator 915 //! 916 //! <b>Throws</b>: Nothing. 917 //! 918 //! <b>Complexity</b>: Logarithmic. container_from_iterator(const_iterator it)919 static const bstree_impl &container_from_iterator(const_iterator it) 920 { return container_from_end_iterator(it.end_iterator_from_it()); } 921 922 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 923 924 //! <b>Effects</b>: Returns the key_compare object used by the container. 925 //! 926 //! <b>Complexity</b>: Constant. 927 //! 928 //! <b>Throws</b>: If key_compare copy-constructor throws. 929 key_compare key_comp() const; 930 931 //! <b>Effects</b>: Returns the value_compare object used by the container. 932 //! 933 //! <b>Complexity</b>: Constant. 934 //! 935 //! <b>Throws</b>: If value_compare copy-constructor throws. 936 value_compare value_comp() const; 937 938 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 939 940 //! <b>Effects</b>: Returns true if the container is empty. 941 //! 942 //! <b>Complexity</b>: Constant. 943 //! 944 //! <b>Throws</b>: Nothing. empty() const945 bool empty() const 946 { 947 if(ConstantTimeSize){ 948 return !this->data_type::sz_traits().get_size(); 949 } 950 else{ 951 return algo_type::unique(this->header_ptr()); 952 } 953 } 954 955 //! <b>Effects</b>: Returns the number of elements stored in the container. 956 //! 957 //! <b>Complexity</b>: Linear to elements contained in *this 958 //! if constant-time size option is disabled. Constant time otherwise. 959 //! 960 //! <b>Throws</b>: Nothing. size() const961 size_type size() const 962 { 963 if(constant_time_size) 964 return this->sz_traits().get_size(); 965 else{ 966 return (size_type)node_algorithms::size(this->header_ptr()); 967 } 968 } 969 970 //! <b>Effects</b>: Swaps the contents of two containers. 971 //! 972 //! <b>Complexity</b>: Constant. 973 //! 974 //! <b>Throws</b>: If the comparison functor's swap call throws. swap(bstree_impl & other)975 void swap(bstree_impl& other) 976 { 977 //This can throw 978 ::boost::adl_move_swap(this->comp(), other.comp()); 979 //These can't throw 980 node_algorithms::swap_tree(this->header_ptr(), node_ptr(other.header_ptr())); 981 this->sz_traits().swap(other.sz_traits()); 982 } 983 984 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 985 //! Cloner should yield to nodes equivalent to the original nodes. 986 //! 987 //! <b>Effects</b>: Erases all the elements from *this 988 //! calling Disposer::operator()(pointer), clones all the 989 //! elements from src calling Cloner::operator()(const_reference ) 990 //! and inserts them on *this. Copies the predicate from the source container. 991 //! 992 //! If cloner throws, all cloned elements are unlinked and disposed 993 //! calling Disposer::operator()(pointer). 994 //! 995 //! <b>Complexity</b>: Linear to erased plus inserted elements. 996 //! 997 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. 998 template <class Cloner, class Disposer> clone_from(const bstree_impl & src,Cloner cloner,Disposer disposer)999 void clone_from(const bstree_impl &src, Cloner cloner, Disposer disposer) 1000 { 1001 this->clear_and_dispose(disposer); 1002 if(!src.empty()){ 1003 detail::exception_disposer<bstree_impl, Disposer> 1004 rollback(*this, disposer); 1005 node_algorithms::clone 1006 (src.header_ptr() 1007 ,this->header_ptr() 1008 ,detail::node_cloner <Cloner, value_traits, AlgoType>(cloner, &this->get_value_traits()) 1009 ,detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); 1010 this->sz_traits().set_size(src.sz_traits().get_size()); 1011 this->comp() = src.comp(); 1012 rollback.release(); 1013 } 1014 } 1015 1016 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1017 //! Cloner should yield to nodes equivalent to the original nodes. 1018 //! 1019 //! <b>Effects</b>: Erases all the elements from *this 1020 //! calling Disposer::operator()(pointer), clones all the 1021 //! elements from src calling Cloner::operator()(reference) 1022 //! and inserts them on *this. Copies the predicate from the source container. 1023 //! 1024 //! If cloner throws, all cloned elements are unlinked and disposed 1025 //! calling Disposer::operator()(pointer). 1026 //! 1027 //! <b>Complexity</b>: Linear to erased plus inserted elements. 1028 //! 1029 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. 1030 //! 1031 //! <b>Note</b>: This version can modify the source container, useful to implement 1032 //! move semantics. 1033 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (bstree_impl)src,Cloner cloner,Disposer disposer)1034 void clone_from(BOOST_RV_REF(bstree_impl) src, Cloner cloner, Disposer disposer) 1035 { 1036 this->clear_and_dispose(disposer); 1037 if(!src.empty()){ 1038 detail::exception_disposer<bstree_impl, Disposer> 1039 rollback(*this, disposer); 1040 node_algorithms::clone 1041 (src.header_ptr() 1042 ,this->header_ptr() 1043 ,detail::node_cloner <Cloner, value_traits, AlgoType, false>(cloner, &this->get_value_traits()) 1044 ,detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); 1045 this->sz_traits().set_size(src.sz_traits().get_size()); 1046 this->comp() = src.comp(); 1047 rollback.release(); 1048 } 1049 } 1050 1051 //! <b>Requires</b>: value must be an lvalue 1052 //! 1053 //! <b>Effects</b>: Inserts value into the container before the upper bound. 1054 //! 1055 //! <b>Complexity</b>: Average complexity for insert element is at 1056 //! most logarithmic. 1057 //! 1058 //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee. 1059 //! 1060 //! <b>Note</b>: Does not affect the validity of iterators and references. 1061 //! No copy-constructors are called. insert_equal(reference value)1062 iterator insert_equal(reference value) 1063 { 1064 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1065 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 1066 iterator ret(node_algorithms::insert_equal_upper_bound 1067 (this->header_ptr(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr()); 1068 this->sz_traits().increment(); 1069 return ret; 1070 } 1071 1072 //! <b>Requires</b>: value must be an lvalue, and "hint" must be 1073 //! a valid iterator. 1074 //! 1075 //! <b>Effects</b>: Inserts x into the container, using "hint" as a hint to 1076 //! where it will be inserted. If "hint" is the upper_bound 1077 //! the insertion takes constant time (two comparisons in the worst case) 1078 //! 1079 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 1080 //! constant time if t is inserted immediately before hint. 1081 //! 1082 //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee. 1083 //! 1084 //! <b>Note</b>: Does not affect the validity of iterators and references. 1085 //! No copy-constructors are called. insert_equal(const_iterator hint,reference value)1086 iterator insert_equal(const_iterator hint, reference value) 1087 { 1088 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1089 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 1090 iterator ret(node_algorithms::insert_equal 1091 (this->header_ptr(), hint.pointed_node(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr()); 1092 this->sz_traits().increment(); 1093 return ret; 1094 } 1095 1096 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 1097 //! of type value_type. 1098 //! 1099 //! <b>Effects</b>: Inserts a each element of a range into the container 1100 //! before the upper bound of the key of each element. 1101 //! 1102 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the 1103 //! size of the range. However, it is linear in N if the range is already sorted 1104 //! by value_comp(). 1105 //! 1106 //! <b>Throws</b>: Nothing. 1107 //! 1108 //! <b>Note</b>: Does not affect the validity of iterators and references. 1109 //! No copy-constructors are called. 1110 template<class Iterator> insert_equal(Iterator b,Iterator e)1111 void insert_equal(Iterator b, Iterator e) 1112 { 1113 iterator iend(this->end()); 1114 for (; b != e; ++b) 1115 this->insert_equal(iend, *b); 1116 } 1117 1118 //! <b>Requires</b>: value must be an lvalue 1119 //! 1120 //! <b>Effects</b>: Inserts value into the container if the value 1121 //! is not already present. 1122 //! 1123 //! <b>Complexity</b>: Average complexity for insert element is at 1124 //! most logarithmic. 1125 //! 1126 //! <b>Throws</b>: Nothing. 1127 //! 1128 //! <b>Note</b>: Does not affect the validity of iterators and references. 1129 //! No copy-constructors are called. insert_unique(reference value)1130 std::pair<iterator, bool> insert_unique(reference value) 1131 { 1132 insert_commit_data commit_data; 1133 std::pair<node_ptr, bool> ret = 1134 (node_algorithms::insert_unique_check 1135 (this->header_ptr(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data)); 1136 return std::pair<iterator, bool> 1137 ( ret.second ? this->insert_unique_commit(value, commit_data) 1138 : iterator(ret.first, this->priv_value_traits_ptr()) 1139 , ret.second); 1140 } 1141 1142 //! <b>Requires</b>: value must be an lvalue, and "hint" must be 1143 //! a valid iterator 1144 //! 1145 //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint 1146 //! to where it will be inserted. 1147 //! 1148 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 1149 //! constant time (two comparisons in the worst case) 1150 //! if t is inserted immediately before hint. 1151 //! 1152 //! <b>Throws</b>: Nothing. 1153 //! 1154 //! <b>Note</b>: Does not affect the validity of iterators and references. 1155 //! No copy-constructors are called. insert_unique(const_iterator hint,reference value)1156 iterator insert_unique(const_iterator hint, reference value) 1157 { 1158 insert_commit_data commit_data; 1159 std::pair<node_ptr, bool> ret = 1160 (node_algorithms::insert_unique_check 1161 (this->header_ptr(), hint.pointed_node(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data)); 1162 return ret.second ? this->insert_unique_commit(value, commit_data) 1163 : iterator(ret.first, this->priv_value_traits_ptr()); 1164 } 1165 1166 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 1167 //! of type value_type. 1168 //! 1169 //! <b>Effects</b>: Tries to insert each element of a range into the container. 1170 //! 1171 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the 1172 //! size of the range. However, it is linear in N if the range is already sorted 1173 //! by value_comp(). 1174 //! 1175 //! <b>Throws</b>: Nothing. 1176 //! 1177 //! <b>Note</b>: Does not affect the validity of iterators and references. 1178 //! No copy-constructors are called. 1179 template<class Iterator> insert_unique(Iterator b,Iterator e)1180 void insert_unique(Iterator b, Iterator e) 1181 { 1182 if(this->empty()){ 1183 iterator iend(this->end()); 1184 for (; b != e; ++b) 1185 this->insert_unique(iend, *b); 1186 } 1187 else{ 1188 for (; b != e; ++b) 1189 this->insert_unique(*b); 1190 } 1191 } 1192 1193 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1194 1195 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1196 //! a user provided key instead of the value itself. 1197 //! 1198 //! <b>Returns</b>: If there is an equivalent value 1199 //! returns a pair containing an iterator to the already present value 1200 //! and false. If the value can be inserted returns true in the returned 1201 //! pair boolean and fills "commit_data" that is meant to be used with 1202 //! the "insert_commit" function. 1203 //! 1204 //! <b>Complexity</b>: Average complexity is at most logarithmic. 1205 //! 1206 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1207 std::pair<iterator, bool> insert_unique_check(const key_type &key, insert_commit_data &commit_data); 1208 1209 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1210 //! a user provided key instead of the value itself, using "hint" 1211 //! as a hint to where it will be inserted. 1212 //! 1213 //! <b>Returns</b>: If there is an equivalent value 1214 //! returns a pair containing an iterator to the already present value 1215 //! and false. If the value can be inserted returns true in the returned 1216 //! pair boolean and fills "commit_data" that is meant to be used with 1217 //! the "insert_commit" function. 1218 //! 1219 //! <b>Complexity</b>: Logarithmic in general, but it's amortized 1220 //! constant time if t is inserted immediately before hint. 1221 //! 1222 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1223 std::pair<iterator, bool> insert_unique_check(const_iterator hint, const key_type &key, insert_commit_data &commit_data); 1224 1225 //! <b>Requires</b>: comp must be a comparison function that induces 1226 //! the same strict weak ordering as key_compare. The difference is that 1227 //! comp compares an arbitrary key with the contained values. 1228 //! 1229 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1230 //! a user provided key instead of the value itself. 1231 //! 1232 //! <b>Returns</b>: If there is an equivalent value 1233 //! returns a pair containing an iterator to the already present value 1234 //! and false. If the value can be inserted returns true in the returned 1235 //! pair boolean and fills "commit_data" that is meant to be used with 1236 //! the "insert_commit" function. 1237 //! 1238 //! <b>Complexity</b>: Average complexity is at most logarithmic. 1239 //! 1240 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1241 //! 1242 //! <b>Notes</b>: This function is used to improve performance when constructing 1243 //! a value_type is expensive: if there is an equivalent value 1244 //! the constructed object must be discarded. Many times, the part of the 1245 //! node that is used to impose the order is much cheaper to construct 1246 //! than the value_type and this function offers the possibility to use that 1247 //! part to check if the insertion will be successful. 1248 //! 1249 //! If the check is successful, the user can construct the value_type and use 1250 //! "insert_commit" to insert the object in constant-time. This gives a total 1251 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). 1252 //! 1253 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 1254 //! objects are inserted or erased from the container. 1255 template<class KeyType, class KeyTypeKeyCompare> 1256 std::pair<iterator, bool> insert_unique_check 1257 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); 1258 1259 //! <b>Requires</b>: comp must be a comparison function that induces 1260 //! the same strict weak ordering as key_compare. The difference is that 1261 //! comp compares an arbitrary key with the contained values. 1262 //! 1263 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1264 //! a user provided key instead of the value itself, using "hint" 1265 //! as a hint to where it will be inserted. 1266 //! 1267 //! <b>Returns</b>: If there is an equivalent value 1268 //! returns a pair containing an iterator to the already present value 1269 //! and false. If the value can be inserted returns true in the returned 1270 //! pair boolean and fills "commit_data" that is meant to be used with 1271 //! the "insert_commit" function. 1272 //! 1273 //! <b>Complexity</b>: Logarithmic in general, but it's amortized 1274 //! constant time if t is inserted immediately before hint. 1275 //! 1276 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1277 //! 1278 //! <b>Notes</b>: This function is used to improve performance when constructing 1279 //! a value_type is expensive: if there is an equivalent value 1280 //! the constructed object must be discarded. Many times, the part of the 1281 //! constructing that is used to impose the order is much cheaper to construct 1282 //! than the value_type and this function offers the possibility to use that key 1283 //! to check if the insertion will be successful. 1284 //! 1285 //! If the check is successful, the user can construct the value_type and use 1286 //! "insert_commit" to insert the object in constant-time. This can give a total 1287 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)). 1288 //! 1289 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 1290 //! objects are inserted or erased from the container. 1291 template<class KeyType, class KeyTypeKeyCompare> 1292 std::pair<iterator, bool> insert_unique_check 1293 (const_iterator hint, const KeyType &key 1294 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); 1295 1296 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1297 1298 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data 1299 //! must have been obtained from a previous call to "insert_check". 1300 //! No objects should have been inserted or erased from the container between 1301 //! the "insert_check" that filled "commit_data" and the call to "insert_commit". 1302 //! 1303 //! <b>Effects</b>: Inserts the value in the container using the information obtained 1304 //! from the "commit_data" that a previous "insert_check" filled. 1305 //! 1306 //! <b>Returns</b>: An iterator to the newly inserted object. 1307 //! 1308 //! <b>Complexity</b>: Constant time. 1309 //! 1310 //! <b>Throws</b>: Nothing. 1311 //! 1312 //! <b>Notes</b>: This function has only sense if a "insert_check" has been 1313 //! previously executed to fill "commit_data". No value should be inserted or 1314 //! erased between the "insert_check" and "insert_commit" calls. insert_unique_commit(reference value,const insert_commit_data & commit_data)1315 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) 1316 { 1317 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1318 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 1319 1320 #if !(defined(BOOST_DISABLE_ASSERTS) || ( defined(BOOST_ENABLE_ASSERT_DEBUG_HANDLER) && defined(NDEBUG) )) 1321 //Test insertion position is correct 1322 iterator p(commit_data.node, this->priv_value_traits_ptr()); 1323 if(!commit_data.link_left){ 1324 ++p; 1325 } 1326 //Check if the insertion point is correct to detect wrong 1327 //uses insert_unique_check 1328 BOOST_ASSERT(( p == this->end() || !this->comp()(*p, value) )); 1329 BOOST_ASSERT(( p == this->begin() || !this->comp()(value, *--p) )); 1330 #endif 1331 1332 node_algorithms::insert_unique_commit 1333 (this->header_ptr(), to_insert, commit_data); 1334 this->sz_traits().increment(); 1335 return iterator(to_insert, this->priv_value_traits_ptr()); 1336 } 1337 1338 //! <b>Requires</b>: value must be an lvalue, "pos" must be 1339 //! a valid iterator (or end) and must be the succesor of value 1340 //! once inserted according to the predicate 1341 //! 1342 //! <b>Effects</b>: Inserts x into the container before "pos". 1343 //! 1344 //! <b>Complexity</b>: Constant time. 1345 //! 1346 //! <b>Throws</b>: Nothing. 1347 //! 1348 //! <b>Note</b>: This function does not check preconditions so if "pos" is not 1349 //! the successor of "value" container ordering invariant will be broken. 1350 //! This is a low-level function to be used only for performance reasons 1351 //! by advanced users. insert_before(const_iterator pos,reference value)1352 iterator insert_before(const_iterator pos, reference value) 1353 { 1354 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1355 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 1356 this->sz_traits().increment(); 1357 return iterator(node_algorithms::insert_before 1358 (this->header_ptr(), pos.pointed_node(), to_insert), this->priv_value_traits_ptr()); 1359 } 1360 1361 //! <b>Requires</b>: value must be an lvalue, and it must be no less 1362 //! than the greatest inserted key 1363 //! 1364 //! <b>Effects</b>: Inserts x into the container in the last position. 1365 //! 1366 //! <b>Complexity</b>: Constant time. 1367 //! 1368 //! <b>Throws</b>: Nothing. 1369 //! 1370 //! <b>Note</b>: This function does not check preconditions so if value is 1371 //! less than the greatest inserted key container ordering invariant will be broken. 1372 //! This function is slightly more efficient than using "insert_before". 1373 //! This is a low-level function to be used only for performance reasons 1374 //! by advanced users. push_back(reference value)1375 void push_back(reference value) 1376 { 1377 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1378 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 1379 this->sz_traits().increment(); 1380 node_algorithms::push_back(this->header_ptr(), to_insert); 1381 } 1382 1383 //! <b>Requires</b>: value must be an lvalue, and it must be no greater 1384 //! than the minimum inserted key 1385 //! 1386 //! <b>Effects</b>: Inserts x into the container in the first position. 1387 //! 1388 //! <b>Complexity</b>: Constant time. 1389 //! 1390 //! <b>Throws</b>: Nothing. 1391 //! 1392 //! <b>Note</b>: This function does not check preconditions so if value is 1393 //! greater than the minimum inserted key container ordering invariant will be broken. 1394 //! This function is slightly more efficient than using "insert_before". 1395 //! This is a low-level function to be used only for performance reasons 1396 //! by advanced users. push_front(reference value)1397 void push_front(reference value) 1398 { 1399 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1400 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); 1401 this->sz_traits().increment(); 1402 node_algorithms::push_front(this->header_ptr(), to_insert); 1403 } 1404 1405 //! <b>Effects</b>: Erases the element pointed to by i. 1406 //! 1407 //! <b>Complexity</b>: Average complexity for erase element is constant time. 1408 //! 1409 //! <b>Throws</b>: Nothing. 1410 //! 1411 //! <b>Note</b>: Invalidates the iterators (but not the references) 1412 //! to the erased elements. No destructors are called. erase(const_iterator i)1413 iterator erase(const_iterator i) 1414 { 1415 const_iterator ret(i); 1416 ++ret; 1417 node_ptr to_erase(i.pointed_node()); 1418 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(to_erase)); 1419 node_algorithms::erase(this->header_ptr(), to_erase); 1420 this->sz_traits().decrement(); 1421 if(safemode_or_autounlink) 1422 node_algorithms::init(to_erase); 1423 return ret.unconst(); 1424 } 1425 1426 //! <b>Effects</b>: Erases the range pointed to by b end e. 1427 //! 1428 //! <b>Complexity</b>: Average complexity for erase range is at most 1429 //! O(log(size() + N)), where N is the number of elements in the range. 1430 //! 1431 //! <b>Throws</b>: Nothing. 1432 //! 1433 //! <b>Note</b>: Invalidates the iterators (but not the references) 1434 //! to the erased elements. No destructors are called. erase(const_iterator b,const_iterator e)1435 iterator erase(const_iterator b, const_iterator e) 1436 { size_type n; return this->private_erase(b, e, n); } 1437 1438 //! <b>Effects</b>: Erases all the elements with the given value. 1439 //! 1440 //! <b>Returns</b>: The number of erased elements. 1441 //! 1442 //! <b>Complexity</b>: O(log(size() + N). 1443 //! 1444 //! <b>Throws</b>: Nothing. 1445 //! 1446 //! <b>Note</b>: Invalidates the iterators (but not the references) 1447 //! to the erased elements. No destructors are called. erase(const key_type & key)1448 size_type erase(const key_type &key) 1449 { return this->erase(key, this->key_comp()); } 1450 1451 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1452 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1453 //! with nk the key_type of a value_type inserted into `*this`. 1454 //! 1455 //! <b>Effects</b>: Erases all the elements with the given key. 1456 //! according to the comparison functor "comp". 1457 //! 1458 //! <b>Returns</b>: The number of erased elements. 1459 //! 1460 //! <b>Complexity</b>: O(log(size() + N). 1461 //! 1462 //! <b>Throws</b>: Nothing. 1463 //! 1464 //! <b>Note</b>: Invalidates the iterators (but not the references) 1465 //! to the erased elements. No destructors are called. 1466 template<class KeyType, class KeyTypeKeyCompare> BOOST_INTRUSIVE_DOC1ST(size_type,typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)1467 BOOST_INTRUSIVE_DOC1ST(size_type 1468 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) 1469 erase(const KeyType& key, KeyTypeKeyCompare comp) 1470 { 1471 std::pair<iterator,iterator> p = this->equal_range(key, comp); 1472 size_type n; 1473 this->private_erase(p.first, p.second, n); 1474 return n; 1475 } 1476 1477 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1478 //! 1479 //! <b>Effects</b>: Erases the element pointed to by i. 1480 //! Disposer::operator()(pointer) is called for the removed element. 1481 //! 1482 //! <b>Complexity</b>: Average complexity for erase element is constant time. 1483 //! 1484 //! <b>Throws</b>: Nothing. 1485 //! 1486 //! <b>Note</b>: Invalidates the iterators 1487 //! to the erased elements. 1488 template<class Disposer> erase_and_dispose(const_iterator i,Disposer disposer)1489 iterator erase_and_dispose(const_iterator i, Disposer disposer) 1490 { 1491 node_ptr to_erase(i.pointed_node()); 1492 iterator ret(this->erase(i)); 1493 disposer(this->get_value_traits().to_value_ptr(to_erase)); 1494 return ret; 1495 } 1496 1497 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1498 //! 1499 //! <b>Effects</b>: Erases all the elements with the given value. 1500 //! Disposer::operator()(pointer) is called for the removed elements. 1501 //! 1502 //! <b>Returns</b>: The number of erased elements. 1503 //! 1504 //! <b>Complexity</b>: O(log(size() + N). 1505 //! 1506 //! <b>Throws</b>: Nothing. 1507 //! 1508 //! <b>Note</b>: Invalidates the iterators (but not the references) 1509 //! to the erased elements. No destructors are called. 1510 template<class Disposer> erase_and_dispose(const key_type & key,Disposer disposer)1511 size_type erase_and_dispose(const key_type &key, Disposer disposer) 1512 { 1513 std::pair<iterator,iterator> p = this->equal_range(key); 1514 size_type n; 1515 this->private_erase(p.first, p.second, n, disposer); 1516 return n; 1517 } 1518 1519 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1520 //! 1521 //! <b>Effects</b>: Erases the range pointed to by b end e. 1522 //! Disposer::operator()(pointer) is called for the removed elements. 1523 //! 1524 //! <b>Complexity</b>: Average complexity for erase range is at most 1525 //! O(log(size() + N)), where N is the number of elements in the range. 1526 //! 1527 //! <b>Throws</b>: Nothing. 1528 //! 1529 //! <b>Note</b>: Invalidates the iterators 1530 //! to the erased elements. 1531 template<class Disposer> erase_and_dispose(const_iterator b,const_iterator e,Disposer disposer)1532 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) 1533 { size_type n; return this->private_erase(b, e, n, disposer); } 1534 1535 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1536 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk) 1537 //! and nk the key_type of a value_type inserted into `*this`. 1538 //! 1539 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1540 //! 1541 //! <b>Effects</b>: Erases all the elements with the given key. 1542 //! according to the comparison functor "comp". 1543 //! Disposer::operator()(pointer) is called for the removed elements. 1544 //! 1545 //! <b>Returns</b>: The number of erased elements. 1546 //! 1547 //! <b>Complexity</b>: O(log(size() + N). 1548 //! 1549 //! <b>Throws</b>: Nothing. 1550 //! 1551 //! <b>Note</b>: Invalidates the iterators 1552 //! to the erased elements. 1553 template<class KeyType, class KeyTypeKeyCompare, class Disposer> BOOST_INTRUSIVE_DOC1ST(size_type,typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)1554 BOOST_INTRUSIVE_DOC1ST(size_type 1555 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) 1556 erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer) 1557 { 1558 std::pair<iterator,iterator> p = this->equal_range(key, comp); 1559 size_type n; 1560 this->private_erase(p.first, p.second, n, disposer); 1561 return n; 1562 } 1563 1564 //! <b>Effects</b>: Erases all of the elements. 1565 //! 1566 //! <b>Complexity</b>: Linear to the number of elements on the container. 1567 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. 1568 //! 1569 //! <b>Throws</b>: Nothing. 1570 //! 1571 //! <b>Note</b>: Invalidates the iterators (but not the references) 1572 //! to the erased elements. No destructors are called. clear()1573 void clear() 1574 { 1575 if(safemode_or_autounlink){ 1576 this->clear_and_dispose(detail::null_disposer()); 1577 } 1578 else{ 1579 node_algorithms::init_header(this->header_ptr()); 1580 this->sz_traits().set_size(0); 1581 } 1582 } 1583 1584 //! <b>Effects</b>: Erases all of the elements calling disposer(p) for 1585 //! each node to be erased. 1586 //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)), 1587 //! where N is the number of elements in the container. 1588 //! 1589 //! <b>Throws</b>: Nothing. 1590 //! 1591 //! <b>Note</b>: Invalidates the iterators (but not the references) 1592 //! to the erased elements. Calls N times to disposer functor. 1593 template<class Disposer> clear_and_dispose(Disposer disposer)1594 void clear_and_dispose(Disposer disposer) 1595 { 1596 node_algorithms::clear_and_dispose(this->header_ptr() 1597 , detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); 1598 node_algorithms::init_header(this->header_ptr()); 1599 this->sz_traits().set_size(0); 1600 } 1601 1602 //! <b>Effects</b>: Returns the number of contained elements with the given value 1603 //! 1604 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal 1605 //! to number of objects with the given value. 1606 //! 1607 //! <b>Throws</b>: If `key_compare` throws. count(const key_type & key) const1608 size_type count(const key_type &key) const 1609 { return size_type(this->count(key, this->key_comp())); } 1610 1611 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1612 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1613 //! and nk the key_type of a value_type inserted into `*this`. 1614 //! 1615 //! <b>Effects</b>: Returns the number of contained elements with the given key 1616 //! 1617 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal 1618 //! to number of objects with the given key. 1619 //! 1620 //! <b>Throws</b>: If `comp` throws. 1621 template<class KeyType, class KeyTypeKeyCompare> count(const KeyType & key,KeyTypeKeyCompare comp) const1622 size_type count(const KeyType &key, KeyTypeKeyCompare comp) const 1623 { 1624 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp); 1625 size_type n = 0; 1626 for(; ret.first != ret.second; ++ret.first){ ++n; } 1627 return n; 1628 } 1629 1630 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1631 1632 //Add non-const overloads to theoretically const members 1633 //as some algorithms have different behavior when non-const versions are used (like splay trees). count(const key_type & key)1634 size_type count(const key_type &key) 1635 { return size_type(this->count(key, this->key_comp())); } 1636 1637 template<class KeyType, class KeyTypeKeyCompare> count(const KeyType & key,KeyTypeKeyCompare comp)1638 size_type count(const KeyType &key, KeyTypeKeyCompare comp) 1639 { 1640 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp); 1641 size_type n = 0; 1642 for(; ret.first != ret.second; ++ret.first){ ++n; } 1643 return n; 1644 } 1645 1646 #else //defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1647 1648 //! <b>Effects</b>: Returns an iterator to the first element whose 1649 //! key is not less than k or end() if that element does not exist. 1650 //! 1651 //! <b>Complexity</b>: Logarithmic. 1652 //! 1653 //! <b>Throws</b>: If `key_compare` throws. 1654 iterator lower_bound(const key_type &key); 1655 1656 //! <b>Effects</b>: Returns an iterator to the first element whose 1657 //! key is not less than k or end() if that element does not exist. 1658 //! 1659 //! <b>Complexity</b>: Logarithmic. 1660 //! 1661 //! <b>Throws</b>: If `key_compare` throws. 1662 const_iterator lower_bound(const key_type &key) const; 1663 1664 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) 1665 template<class KeyType, class KeyTypeKeyCompare> 1666 iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp); 1667 1668 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) 1669 template<class KeyType, class KeyTypeKeyCompare> 1670 const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const; 1671 1672 //! <b>Effects</b>: Returns an iterator to the first element whose 1673 //! key is greater than k or end() if that element does not exist. 1674 //! 1675 //! <b>Complexity</b>: Logarithmic. 1676 //! 1677 //! <b>Throws</b>: If `key_compare` throws. 1678 iterator upper_bound(const key_type &key); 1679 1680 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1681 //! !comp(key, nk), with nk the key_type of a value_type inserted into `*this`. 1682 //! 1683 //! <b>Effects</b>: Returns an iterator to the first element whose 1684 //! key is greater than k according to comp or end() if that element 1685 //! does not exist. 1686 //! 1687 //! <b>Complexity</b>: Logarithmic. 1688 //! 1689 //! <b>Throws</b>: If `comp` throws. 1690 template<class KeyType, class KeyTypeKeyCompare> 1691 iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp); 1692 1693 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) 1694 const_iterator upper_bound(const key_type &key) const; 1695 1696 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) 1697 template<class KeyType, class KeyTypeKeyCompare> 1698 const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const; 1699 1700 //! <b>Effects</b>: Finds an iterator to the first element whose key is 1701 //! k or end() if that element does not exist. 1702 //! 1703 //! <b>Complexity</b>: Logarithmic. 1704 //! 1705 //! <b>Throws</b>: If `key_compare` throws. 1706 iterator find(const key_type &key); 1707 1708 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1709 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1710 //! and nk the key_type of a value_type inserted into `*this`. 1711 //! 1712 //! <b>Effects</b>: Finds an iterator to the first element whose key is 1713 //! k or end() if that element does not exist. 1714 //! 1715 //! <b>Complexity</b>: Logarithmic. 1716 //! 1717 //! <b>Throws</b>: If `comp` throws. 1718 template<class KeyType, class KeyTypeKeyCompare> 1719 iterator find(const KeyType &key, KeyTypeKeyCompare comp); 1720 1721 //! @copydoc ::boost::intrusive::bstree::find(const key_type &) 1722 const_iterator find(const key_type &key) const; 1723 1724 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) 1725 template<class KeyType, class KeyTypeKeyCompare> 1726 const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const; 1727 1728 //! <b>Effects</b>: Finds a range containing all elements whose key is k or 1729 //! an empty range that indicates the position where those elements would be 1730 //! if they there is no elements with key k. 1731 //! 1732 //! <b>Complexity</b>: Logarithmic. 1733 //! 1734 //! <b>Throws</b>: If `key_compare` throws. 1735 std::pair<iterator,iterator> equal_range(const key_type &key); 1736 1737 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1738 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1739 //! with nk the key_type of a value_type inserted into `*this`. 1740 //! 1741 //! <b>Effects</b>: Finds a range containing all elements whose key is k or 1742 //! an empty range that indicates the position where those elements would be 1743 //! if they there is no elements with key k. 1744 //! 1745 //! <b>Complexity</b>: Logarithmic. 1746 //! 1747 //! <b>Throws</b>: If `comp` throws. 1748 template<class KeyType, class KeyTypeKeyCompare> 1749 std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp); 1750 1751 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) 1752 std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const; 1753 1754 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) 1755 template<class KeyType, class KeyTypeKeyCompare> 1756 std::pair<const_iterator, const_iterator> 1757 equal_range(const KeyType &key, KeyTypeKeyCompare comp) const; 1758 1759 //! <b>Requires</b>: 1760 //! `upper_key` shall not precede `lower_key` according to key_compare. 1761 //! [key_comp()(upper_key, lower_key) shall be false] 1762 //! 1763 //! If `lower_key` is equivalent to `upper_key` 1764 //! [!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)] then 1765 //! ('left_closed' || 'right_closed') must be false. 1766 //! 1767 //! <b>Effects</b>: Returns an a pair with the following criteria: 1768 //! 1769 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise 1770 //! 1771 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise 1772 //! 1773 //! <b>Complexity</b>: Logarithmic. 1774 //! 1775 //! <b>Throws</b>: If `key_compare` throws. 1776 //! 1777 //! <b>Note</b>: This function can be more efficient than calling upper_bound 1778 //! and lower_bound for lower_value and upper_value. 1779 //! 1780 //! <b>Note</b>: Experimental function, the interface might change in future releases. 1781 std::pair<iterator,iterator> bounded_range 1782 (const key_type &lower_key, const key_type &upper_value, bool left_closed, bool right_closed); 1783 1784 //! <b>Requires</b>: 1785 //! `lower_key` is a value such that `*this` is partitioned with respect to 1786 //! comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise. 1787 //! 1788 //! `upper_key` is a value such that `*this` is partitioned with respect to 1789 //! !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise. 1790 //! 1791 //! `upper_key` shall not precede `lower_key` according to comp 1792 //! [comp(upper_key, lower_key) shall be false] 1793 //! 1794 //! If `lower_key` is equivalent to `upper_key` 1795 //! [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then 1796 //! ('left_closed' || 'right_closed') must be false. 1797 //! 1798 //! <b>Effects</b>: Returns an a pair with the following criteria: 1799 //! 1800 //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise 1801 //! 1802 //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise 1803 //! 1804 //! <b>Complexity</b>: Logarithmic. 1805 //! 1806 //! <b>Throws</b>: If `comp` throws. 1807 //! 1808 //! <b>Note</b>: This function can be more efficient than calling upper_bound 1809 //! and lower_bound for lower_key and upper_key. 1810 //! 1811 //! <b>Note</b>: Experimental function, the interface might change in future releases. 1812 template<class KeyType, class KeyTypeKeyCompare> 1813 std::pair<iterator,iterator> bounded_range 1814 (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 1815 1816 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) 1817 std::pair<const_iterator,const_iterator> bounded_range 1818 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 1819 1820 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 1821 template<class KeyType, class KeyTypeKeyCompare> 1822 std::pair<const_iterator,const_iterator> bounded_range 1823 (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 1824 1825 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1826 //! appropriate type. Otherwise the behavior is undefined. 1827 //! 1828 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set 1829 //! that points to the value 1830 //! 1831 //! <b>Complexity</b>: Constant. 1832 //! 1833 //! <b>Throws</b>: Nothing. 1834 //! 1835 //! <b>Note</b>: This static function is available only if the <i>value traits</i> 1836 //! is stateless. 1837 static iterator s_iterator_to(reference value); 1838 1839 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1840 //! appropriate type. Otherwise the behavior is undefined. 1841 //! 1842 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the 1843 //! set that points to the value 1844 //! 1845 //! <b>Complexity</b>: Constant. 1846 //! 1847 //! <b>Throws</b>: Nothing. 1848 //! 1849 //! <b>Note</b>: This static function is available only if the <i>value traits</i> 1850 //! is stateless. 1851 static const_iterator s_iterator_to(const_reference value); 1852 1853 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1854 //! appropriate type. Otherwise the behavior is undefined. 1855 //! 1856 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set 1857 //! that points to the value 1858 //! 1859 //! <b>Complexity</b>: Constant. 1860 //! 1861 //! <b>Throws</b>: Nothing. 1862 iterator iterator_to(reference value); 1863 1864 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1865 //! appropriate type. Otherwise the behavior is undefined. 1866 //! 1867 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the 1868 //! set that points to the value 1869 //! 1870 //! <b>Complexity</b>: Constant. 1871 //! 1872 //! <b>Throws</b>: Nothing. 1873 const_iterator iterator_to(const_reference value) const; 1874 1875 //! <b>Requires</b>: value shall not be in a container. 1876 //! 1877 //! <b>Effects</b>: init_node puts the hook of a value in a well-known default 1878 //! state. 1879 //! 1880 //! <b>Throws</b>: Nothing. 1881 //! 1882 //! <b>Complexity</b>: Constant time. 1883 //! 1884 //! <b>Note</b>: This function puts the hook in the well-known default state 1885 //! used by auto_unlink and safe hooks. 1886 static void init_node(reference value); 1887 1888 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1889 1890 //! <b>Effects</b>: Unlinks the leftmost node from the container. 1891 //! 1892 //! <b>Complexity</b>: Average complexity is constant time. 1893 //! 1894 //! <b>Throws</b>: Nothing. 1895 //! 1896 //! <b>Notes</b>: This function breaks the container and the container can 1897 //! only be used for more unlink_leftmost_without_rebalance calls. 1898 //! This function is normally used to achieve a step by step 1899 //! controlled destruction of the container. unlink_leftmost_without_rebalance()1900 pointer unlink_leftmost_without_rebalance() 1901 { 1902 node_ptr to_be_disposed(node_algorithms::unlink_leftmost_without_rebalance 1903 (this->header_ptr())); 1904 if(!to_be_disposed) 1905 return 0; 1906 this->sz_traits().decrement(); 1907 if(safemode_or_autounlink)//If this is commented does not work with normal_link 1908 node_algorithms::init(to_be_disposed); 1909 return this->get_value_traits().to_value_ptr(to_be_disposed); 1910 } 1911 1912 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1913 1914 //! <b>Requires</b>: replace_this must be a valid iterator of *this 1915 //! and with_this must not be inserted in any container. 1916 //! 1917 //! <b>Effects</b>: Replaces replace_this in its position in the 1918 //! container with with_this. The container does not need to be rebalanced. 1919 //! 1920 //! <b>Complexity</b>: Constant. 1921 //! 1922 //! <b>Throws</b>: Nothing. 1923 //! 1924 //! <b>Note</b>: This function will break container ordering invariants if 1925 //! with_this is not equivalent to *replace_this according to the 1926 //! ordering rules. This function is faster than erasing and inserting 1927 //! the node, since no rebalancing or comparison is needed. 1928 void replace_node(iterator replace_this, reference with_this); 1929 1930 //! <b>Effects</b>: Rebalances the tree. 1931 //! 1932 //! <b>Throws</b>: Nothing. 1933 //! 1934 //! <b>Complexity</b>: Linear. 1935 void rebalance(); 1936 1937 //! <b>Requires</b>: old_root is a node of a tree. 1938 //! 1939 //! <b>Effects</b>: Rebalances the subtree rooted at old_root. 1940 //! 1941 //! <b>Returns</b>: The new root of the subtree. 1942 //! 1943 //! <b>Throws</b>: Nothing. 1944 //! 1945 //! <b>Complexity</b>: Linear to the elements in the subtree. 1946 iterator rebalance_subtree(iterator root); 1947 1948 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1949 1950 //! <b>Effects</b>: removes "value" from the container. 1951 //! 1952 //! <b>Throws</b>: Nothing. 1953 //! 1954 //! <b>Complexity</b>: Logarithmic time. 1955 //! 1956 //! <b>Note</b>: This static function is only usable with non-constant 1957 //! time size containers that have stateless comparison functors. 1958 //! 1959 //! If the user calls 1960 //! this function with a constant time size container or stateful comparison 1961 //! functor a compilation error will be issued. remove_node(reference value)1962 static void remove_node(reference value) 1963 { 1964 BOOST_STATIC_ASSERT((!constant_time_size)); 1965 node_ptr to_remove(value_traits::to_node_ptr(value)); 1966 node_algorithms::unlink(to_remove); 1967 if(safemode_or_autounlink) 1968 node_algorithms::init(to_remove); 1969 } 1970 1971 //! <b>Requires</b>: "source" container's Options can only can differ in the comparison 1972 //! function from *this. 1973 //! 1974 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using 1975 //! the comparison object of *this. If there is an element in a with key equivalent to the 1976 //! key of an element from source, then that element is not extracted from source. 1977 //! 1978 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 1979 //! to those same elements but as members of *this. Iterators referring to the transferred 1980 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 1981 //! not into source. 1982 //! 1983 //! <b>Throws</b>: Nothing unless the comparison object throws. 1984 //! 1985 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) 1986 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1987 template<class T, class ...Options2> void merge_unique(bstree<T, Options2...> &); 1988 #else 1989 template<class Compare2> merge_unique(bstree_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,ConstantTimeSize,AlgoType,HeaderHolder> & source)1990 void merge_unique(bstree_impl 1991 <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source) 1992 #endif 1993 { 1994 node_ptr it (node_algorithms::begin_node(source.header_ptr())) 1995 , itend(node_algorithms::end_node (source.header_ptr())); 1996 1997 while(it != itend){ 1998 node_ptr const p(it); 1999 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); 2000 it = node_algorithms::next_node(it); 2001 if( node_algorithms::transfer_unique(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p) ){ 2002 source.sz_traits().decrement(); 2003 this->sz_traits().increment(); 2004 } 2005 } 2006 } 2007 2008 //! <b>Requires</b>: "source" container's Options can only can differ in the comparison 2009 //! function from *this. 2010 //! 2011 //! <b>Effects</b>: Extracts each element in source and insert it into a using 2012 //! the comparison object of *this. 2013 //! 2014 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 2015 //! to those same elements but as members of *this. Iterators referring to the transferred 2016 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 2017 //! not into source. 2018 //! 2019 //! <b>Throws</b>: Nothing unless the comparison object throws. 2020 //! 2021 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) 2022 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 2023 template<class T, class ...Options2> void merge_equal(bstree<T, Options2...> &); 2024 #else 2025 template<class Compare2> merge_equal(bstree_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,ConstantTimeSize,AlgoType,HeaderHolder> & source)2026 void merge_equal(bstree_impl 2027 <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source) 2028 #endif 2029 { 2030 node_ptr it (node_algorithms::begin_node(source.header_ptr())) 2031 , itend(node_algorithms::end_node (source.header_ptr())); 2032 2033 while(it != itend){ 2034 node_ptr const p(it); 2035 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); 2036 it = node_algorithms::next_node(it); 2037 node_algorithms::transfer_equal(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p); 2038 source.sz_traits().decrement(); 2039 this->sz_traits().increment(); 2040 } 2041 } 2042 2043 //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user. 2044 //! 2045 //! <b>Complexity</b>: Linear time. 2046 //! 2047 //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG). 2048 //! Experimental function, interface might change in future versions. 2049 template <class ExtraChecker> check(ExtraChecker extra_checker) const2050 void check(ExtraChecker extra_checker) const 2051 { 2052 typedef detail::key_nodeptr_comp<key_compare, value_traits, key_of_value> nodeptr_comp_t; 2053 nodeptr_comp_t nodeptr_comp(this->key_comp(), &this->get_value_traits()); 2054 typedef typename get_node_checker<AlgoType, ValueTraits, nodeptr_comp_t, ExtraChecker>::type node_checker_t; 2055 typename node_checker_t::return_type checker_return; 2056 node_algorithms::check(this->header_ptr(), node_checker_t(nodeptr_comp, extra_checker), checker_return); 2057 BOOST_INTRUSIVE_INVARIANT_ASSERT(!constant_time_size || this->sz_traits().get_size() == checker_return.node_count); 2058 } 2059 2060 //! <b>Effects</b>: Asserts the integrity of the container. 2061 //! 2062 //! <b>Complexity</b>: Linear time. 2063 //! 2064 //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). 2065 //! Experimental function, interface might change in future versions. check() const2066 void check() const 2067 { 2068 check(detail::empty_node_checker<ValueTraits>()); 2069 } 2070 operator ==(const bstree_impl & x,const bstree_impl & y)2071 friend bool operator==(const bstree_impl &x, const bstree_impl &y) 2072 { 2073 if(constant_time_size && x.size() != y.size()){ 2074 return false; 2075 } 2076 return boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); 2077 } 2078 operator !=(const bstree_impl & x,const bstree_impl & y)2079 friend bool operator!=(const bstree_impl &x, const bstree_impl &y) 2080 { return !(x == y); } 2081 operator <(const bstree_impl & x,const bstree_impl & y)2082 friend bool operator<(const bstree_impl &x, const bstree_impl &y) 2083 { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 2084 operator >(const bstree_impl & x,const bstree_impl & y)2085 friend bool operator>(const bstree_impl &x, const bstree_impl &y) 2086 { return y < x; } 2087 operator <=(const bstree_impl & x,const bstree_impl & y)2088 friend bool operator<=(const bstree_impl &x, const bstree_impl &y) 2089 { return !(x > y); } 2090 operator >=(const bstree_impl & x,const bstree_impl & y)2091 friend bool operator>=(const bstree_impl &x, const bstree_impl &y) 2092 { return !(x < y); } 2093 swap(bstree_impl & x,bstree_impl & y)2094 friend void swap(bstree_impl &x, bstree_impl &y) 2095 { x.swap(y); } 2096 2097 /// @cond 2098 private: 2099 template<class Disposer> private_erase(const_iterator b,const_iterator e,size_type & n,Disposer disposer)2100 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer) 2101 { 2102 for(n = 0; b != e; ++n) 2103 this->erase_and_dispose(b++, disposer); 2104 return b.unconst(); 2105 } 2106 private_erase(const_iterator b,const_iterator e,size_type & n)2107 iterator private_erase(const_iterator b, const_iterator e, size_type &n) 2108 { 2109 for(n = 0; b != e; ++n) 2110 this->erase(b++); 2111 return b.unconst(); 2112 } 2113 /// @endcond 2114 }; 2115 2116 //! Helper metafunction to define a \c bstree that yields to the same type when the 2117 //! same options (either explicitly or implicitly) are used. 2118 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2119 template<class T, class ...Options> 2120 #else 2121 template<class T, class O1 = void, class O2 = void 2122 , class O3 = void, class O4 = void 2123 , class O5 = void, class O6 = void> 2124 #endif 2125 struct make_bstree 2126 { 2127 /// @cond 2128 typedef typename pack_options 2129 < bstree_defaults, 2130 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2131 O1, O2, O3, O4, O5, O6 2132 #else 2133 Options... 2134 #endif 2135 >::type packed_options; 2136 2137 typedef typename detail::get_value_traits 2138 <T, typename packed_options::proto_value_traits>::type value_traits; 2139 2140 typedef bstree_impl 2141 < value_traits 2142 , typename packed_options::key_of_value 2143 , typename packed_options::compare 2144 , typename packed_options::size_type 2145 , packed_options::constant_time_size 2146 , BsTreeAlgorithms 2147 , typename packed_options::header_holder_type 2148 > implementation_defined; 2149 /// @endcond 2150 typedef implementation_defined type; 2151 }; 2152 2153 2154 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 2155 2156 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2157 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 2158 #else 2159 template<class T, class ...Options> 2160 #endif 2161 class bstree 2162 : public make_bstree<T, 2163 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2164 O1, O2, O3, O4, O5, O6 2165 #else 2166 Options... 2167 #endif 2168 >::type 2169 { 2170 typedef typename make_bstree 2171 <T, 2172 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2173 O1, O2, O3, O4, O5, O6 2174 #else 2175 Options... 2176 #endif 2177 >::type Base; 2178 BOOST_MOVABLE_BUT_NOT_COPYABLE(bstree) 2179 2180 public: 2181 typedef typename Base::key_compare key_compare; 2182 typedef typename Base::value_traits value_traits; 2183 typedef typename Base::iterator iterator; 2184 typedef typename Base::const_iterator const_iterator; 2185 2186 //Assert if passed value traits are compatible with the type 2187 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 2188 bstree()2189 BOOST_INTRUSIVE_FORCEINLINE bstree() 2190 : Base() 2191 {} 2192 bstree(const key_compare & cmp,const value_traits & v_traits=value_traits ())2193 BOOST_INTRUSIVE_FORCEINLINE explicit bstree( const key_compare &cmp, const value_traits &v_traits = value_traits()) 2194 : Base(cmp, v_traits) 2195 {} 2196 2197 template<class Iterator> bstree(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())2198 BOOST_INTRUSIVE_FORCEINLINE bstree( bool unique, Iterator b, Iterator e 2199 , const key_compare &cmp = key_compare() 2200 , const value_traits &v_traits = value_traits()) 2201 : Base(unique, b, e, cmp, v_traits) 2202 {} 2203 bstree(BOOST_RV_REF (bstree)x)2204 BOOST_INTRUSIVE_FORCEINLINE bstree(BOOST_RV_REF(bstree) x) 2205 : Base(BOOST_MOVE_BASE(Base, x)) 2206 {} 2207 operator =(BOOST_RV_REF (bstree)x)2208 BOOST_INTRUSIVE_FORCEINLINE bstree& operator=(BOOST_RV_REF(bstree) x) 2209 { return static_cast<bstree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 2210 2211 template <class Cloner, class Disposer> clone_from(const bstree & src,Cloner cloner,Disposer disposer)2212 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const bstree &src, Cloner cloner, Disposer disposer) 2213 { Base::clone_from(src, cloner, disposer); } 2214 2215 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (bstree)src,Cloner cloner,Disposer disposer)2216 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(bstree) src, Cloner cloner, Disposer disposer) 2217 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 2218 container_from_end_iterator(iterator end_iterator)2219 BOOST_INTRUSIVE_FORCEINLINE static bstree &container_from_end_iterator(iterator end_iterator) 2220 { return static_cast<bstree &>(Base::container_from_end_iterator(end_iterator)); } 2221 container_from_end_iterator(const_iterator end_iterator)2222 BOOST_INTRUSIVE_FORCEINLINE static const bstree &container_from_end_iterator(const_iterator end_iterator) 2223 { return static_cast<const bstree &>(Base::container_from_end_iterator(end_iterator)); } 2224 container_from_iterator(iterator it)2225 BOOST_INTRUSIVE_FORCEINLINE static bstree &container_from_iterator(iterator it) 2226 { return static_cast<bstree &>(Base::container_from_iterator(it)); } 2227 container_from_iterator(const_iterator it)2228 BOOST_INTRUSIVE_FORCEINLINE static const bstree &container_from_iterator(const_iterator it) 2229 { return static_cast<const bstree &>(Base::container_from_iterator(it)); } 2230 }; 2231 2232 #endif 2233 } //namespace intrusive 2234 } //namespace boost 2235 2236 #include <boost/intrusive/detail/config_end.hpp> 2237 2238 #endif //BOOST_INTRUSIVE_BSTREE_HPP 2239