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 if(safemode_or_autounlink) 1066 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert)); 1067 iterator ret(node_algorithms::insert_equal_upper_bound 1068 (this->header_ptr(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr()); 1069 this->sz_traits().increment(); 1070 return ret; 1071 } 1072 1073 //! <b>Requires</b>: value must be an lvalue, and "hint" must be 1074 //! a valid iterator. 1075 //! 1076 //! <b>Effects</b>: Inserts x into the container, using "hint" as a hint to 1077 //! where it will be inserted. If "hint" is the upper_bound 1078 //! the insertion takes constant time (two comparisons in the worst case) 1079 //! 1080 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 1081 //! constant time if t is inserted immediately before hint. 1082 //! 1083 //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee. 1084 //! 1085 //! <b>Note</b>: Does not affect the validity of iterators and references. 1086 //! No copy-constructors are called. insert_equal(const_iterator hint,reference value)1087 iterator insert_equal(const_iterator hint, reference value) 1088 { 1089 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1090 if(safemode_or_autounlink) 1091 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert)); 1092 iterator ret(node_algorithms::insert_equal 1093 (this->header_ptr(), hint.pointed_node(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr()); 1094 this->sz_traits().increment(); 1095 return ret; 1096 } 1097 1098 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 1099 //! of type value_type. 1100 //! 1101 //! <b>Effects</b>: Inserts a each element of a range into the container 1102 //! before the upper bound of the key of each element. 1103 //! 1104 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the 1105 //! size of the range. However, it is linear in N if the range is already sorted 1106 //! by value_comp(). 1107 //! 1108 //! <b>Throws</b>: Nothing. 1109 //! 1110 //! <b>Note</b>: Does not affect the validity of iterators and references. 1111 //! No copy-constructors are called. 1112 template<class Iterator> insert_equal(Iterator b,Iterator e)1113 void insert_equal(Iterator b, Iterator e) 1114 { 1115 iterator iend(this->end()); 1116 for (; b != e; ++b) 1117 this->insert_equal(iend, *b); 1118 } 1119 1120 //! <b>Requires</b>: value must be an lvalue 1121 //! 1122 //! <b>Effects</b>: Inserts value into the container if the value 1123 //! is not already present. 1124 //! 1125 //! <b>Complexity</b>: Average complexity for insert element is at 1126 //! most logarithmic. 1127 //! 1128 //! <b>Throws</b>: Nothing. 1129 //! 1130 //! <b>Note</b>: Does not affect the validity of iterators and references. 1131 //! No copy-constructors are called. insert_unique(reference value)1132 std::pair<iterator, bool> insert_unique(reference value) 1133 { 1134 insert_commit_data commit_data; 1135 std::pair<node_ptr, bool> ret = 1136 (node_algorithms::insert_unique_check 1137 (this->header_ptr(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data)); 1138 return std::pair<iterator, bool> 1139 ( ret.second ? this->insert_unique_commit(value, commit_data) 1140 : iterator(ret.first, this->priv_value_traits_ptr()) 1141 , ret.second); 1142 } 1143 1144 //! <b>Requires</b>: value must be an lvalue, and "hint" must be 1145 //! a valid iterator 1146 //! 1147 //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint 1148 //! to where it will be inserted. 1149 //! 1150 //! <b>Complexity</b>: Logarithmic in general, but it is amortized 1151 //! constant time (two comparisons in the worst case) 1152 //! if t is inserted immediately before hint. 1153 //! 1154 //! <b>Throws</b>: Nothing. 1155 //! 1156 //! <b>Note</b>: Does not affect the validity of iterators and references. 1157 //! No copy-constructors are called. insert_unique(const_iterator hint,reference value)1158 iterator insert_unique(const_iterator hint, reference value) 1159 { 1160 insert_commit_data commit_data; 1161 std::pair<node_ptr, bool> ret = 1162 (node_algorithms::insert_unique_check 1163 (this->header_ptr(), hint.pointed_node(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data)); 1164 return ret.second ? this->insert_unique_commit(value, commit_data) 1165 : iterator(ret.first, this->priv_value_traits_ptr()); 1166 } 1167 1168 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue 1169 //! of type value_type. 1170 //! 1171 //! <b>Effects</b>: Tries to insert each element of a range into the container. 1172 //! 1173 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the 1174 //! size of the range. However, it is linear in N if the range is already sorted 1175 //! by value_comp(). 1176 //! 1177 //! <b>Throws</b>: Nothing. 1178 //! 1179 //! <b>Note</b>: Does not affect the validity of iterators and references. 1180 //! No copy-constructors are called. 1181 template<class Iterator> insert_unique(Iterator b,Iterator e)1182 void insert_unique(Iterator b, Iterator e) 1183 { 1184 if(this->empty()){ 1185 iterator iend(this->end()); 1186 for (; b != e; ++b) 1187 this->insert_unique(iend, *b); 1188 } 1189 else{ 1190 for (; b != e; ++b) 1191 this->insert_unique(*b); 1192 } 1193 } 1194 1195 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1196 1197 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1198 //! a user provided key instead of the value itself. 1199 //! 1200 //! <b>Returns</b>: If there is an equivalent value 1201 //! returns a pair containing an iterator to the already present value 1202 //! and false. If the value can be inserted returns true in the returned 1203 //! pair boolean and fills "commit_data" that is meant to be used with 1204 //! the "insert_commit" function. 1205 //! 1206 //! <b>Complexity</b>: Average complexity is at most logarithmic. 1207 //! 1208 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1209 std::pair<iterator, bool> insert_unique_check(const key_type &key, insert_commit_data &commit_data); 1210 1211 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1212 //! a user provided key instead of the value itself, using "hint" 1213 //! as a hint to where it will be inserted. 1214 //! 1215 //! <b>Returns</b>: If there is an equivalent value 1216 //! returns a pair containing an iterator to the already present value 1217 //! and false. If the value can be inserted returns true in the returned 1218 //! pair boolean and fills "commit_data" that is meant to be used with 1219 //! the "insert_commit" function. 1220 //! 1221 //! <b>Complexity</b>: Logarithmic in general, but it's amortized 1222 //! constant time if t is inserted immediately before hint. 1223 //! 1224 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1225 std::pair<iterator, bool> insert_unique_check(const_iterator hint, const key_type &key, insert_commit_data &commit_data); 1226 1227 //! <b>Requires</b>: comp must be a comparison function that induces 1228 //! the same strict weak ordering as key_compare. The difference is that 1229 //! comp compares an arbitrary key with the contained values. 1230 //! 1231 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1232 //! a user provided key instead of the value itself. 1233 //! 1234 //! <b>Returns</b>: If there is an equivalent value 1235 //! returns a pair containing an iterator to the already present value 1236 //! and false. If the value can be inserted returns true in the returned 1237 //! pair boolean and fills "commit_data" that is meant to be used with 1238 //! the "insert_commit" function. 1239 //! 1240 //! <b>Complexity</b>: Average complexity is at most logarithmic. 1241 //! 1242 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1243 //! 1244 //! <b>Notes</b>: This function is used to improve performance when constructing 1245 //! a value_type is expensive: if there is an equivalent value 1246 //! the constructed object must be discarded. Many times, the part of the 1247 //! node that is used to impose the order is much cheaper to construct 1248 //! than the value_type and this function offers the possibility to use that 1249 //! part to check if the insertion will be successful. 1250 //! 1251 //! If the check is successful, the user can construct the value_type and use 1252 //! "insert_commit" to insert the object in constant-time. This gives a total 1253 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). 1254 //! 1255 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 1256 //! objects are inserted or erased from the container. 1257 template<class KeyType, class KeyTypeKeyCompare> 1258 std::pair<iterator, bool> insert_unique_check 1259 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); 1260 1261 //! <b>Requires</b>: comp must be a comparison function that induces 1262 //! the same strict weak ordering as key_compare. The difference is that 1263 //! comp compares an arbitrary key with the contained values. 1264 //! 1265 //! <b>Effects</b>: Checks if a value can be inserted in the container, using 1266 //! a user provided key instead of the value itself, using "hint" 1267 //! as a hint to where it will be inserted. 1268 //! 1269 //! <b>Returns</b>: If there is an equivalent value 1270 //! returns a pair containing an iterator to the already present value 1271 //! and false. If the value can be inserted returns true in the returned 1272 //! pair boolean and fills "commit_data" that is meant to be used with 1273 //! the "insert_commit" function. 1274 //! 1275 //! <b>Complexity</b>: Logarithmic in general, but it's amortized 1276 //! constant time if t is inserted immediately before hint. 1277 //! 1278 //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. 1279 //! 1280 //! <b>Notes</b>: This function is used to improve performance when constructing 1281 //! a value_type is expensive: if there is an equivalent value 1282 //! the constructed object must be discarded. Many times, the part of the 1283 //! constructing that is used to impose the order is much cheaper to construct 1284 //! than the value_type and this function offers the possibility to use that key 1285 //! to check if the insertion will be successful. 1286 //! 1287 //! If the check is successful, the user can construct the value_type and use 1288 //! "insert_commit" to insert the object in constant-time. This can give a total 1289 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)). 1290 //! 1291 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more 1292 //! objects are inserted or erased from the container. 1293 template<class KeyType, class KeyTypeKeyCompare> 1294 std::pair<iterator, bool> insert_unique_check 1295 (const_iterator hint, const KeyType &key 1296 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); 1297 1298 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1299 1300 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data 1301 //! must have been obtained from a previous call to "insert_check". 1302 //! No objects should have been inserted or erased from the container between 1303 //! the "insert_check" that filled "commit_data" and the call to "insert_commit". 1304 //! 1305 //! <b>Effects</b>: Inserts the value in the container using the information obtained 1306 //! from the "commit_data" that a previous "insert_check" filled. 1307 //! 1308 //! <b>Returns</b>: An iterator to the newly inserted object. 1309 //! 1310 //! <b>Complexity</b>: Constant time. 1311 //! 1312 //! <b>Throws</b>: Nothing. 1313 //! 1314 //! <b>Notes</b>: This function has only sense if a "insert_check" has been 1315 //! previously executed to fill "commit_data". No value should be inserted or 1316 //! erased between the "insert_check" and "insert_commit" calls. insert_unique_commit(reference value,const insert_commit_data & commit_data)1317 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) 1318 { 1319 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1320 if(safemode_or_autounlink) 1321 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert)); 1322 1323 #if !(defined(BOOST_DISABLE_ASSERTS) || ( defined(BOOST_ENABLE_ASSERT_DEBUG_HANDLER) && defined(NDEBUG) )) 1324 //Test insertion position is correct 1325 iterator p(commit_data.node, this->priv_value_traits_ptr()); 1326 if(!commit_data.link_left){ 1327 ++p; 1328 } 1329 //Check if the insertion point is correct to detect wrong 1330 //uses insert_unique_check 1331 BOOST_ASSERT(( p == this->end() || !this->comp()(*p, value) )); 1332 BOOST_ASSERT(( p == this->begin() || !this->comp()(value, *--p) )); 1333 #endif 1334 1335 node_algorithms::insert_unique_commit 1336 (this->header_ptr(), to_insert, commit_data); 1337 this->sz_traits().increment(); 1338 return iterator(to_insert, this->priv_value_traits_ptr()); 1339 } 1340 1341 //! <b>Requires</b>: value must be an lvalue, "pos" must be 1342 //! a valid iterator (or end) and must be the succesor of value 1343 //! once inserted according to the predicate 1344 //! 1345 //! <b>Effects</b>: Inserts x into the container before "pos". 1346 //! 1347 //! <b>Complexity</b>: Constant time. 1348 //! 1349 //! <b>Throws</b>: Nothing. 1350 //! 1351 //! <b>Note</b>: This function does not check preconditions so if "pos" is not 1352 //! the successor of "value" container ordering invariant will be broken. 1353 //! This is a low-level function to be used only for performance reasons 1354 //! by advanced users. insert_before(const_iterator pos,reference value)1355 iterator insert_before(const_iterator pos, reference value) 1356 { 1357 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1358 if(safemode_or_autounlink) 1359 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert)); 1360 this->sz_traits().increment(); 1361 return iterator(node_algorithms::insert_before 1362 (this->header_ptr(), pos.pointed_node(), to_insert), this->priv_value_traits_ptr()); 1363 } 1364 1365 //! <b>Requires</b>: value must be an lvalue, and it must be no less 1366 //! than the greatest inserted key 1367 //! 1368 //! <b>Effects</b>: Inserts x into the container in the last position. 1369 //! 1370 //! <b>Complexity</b>: Constant time. 1371 //! 1372 //! <b>Throws</b>: Nothing. 1373 //! 1374 //! <b>Note</b>: This function does not check preconditions so if value is 1375 //! less than the greatest inserted key container ordering invariant will be broken. 1376 //! This function is slightly more efficient than using "insert_before". 1377 //! This is a low-level function to be used only for performance reasons 1378 //! by advanced users. push_back(reference value)1379 void push_back(reference value) 1380 { 1381 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1382 if(safemode_or_autounlink) 1383 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert)); 1384 this->sz_traits().increment(); 1385 node_algorithms::push_back(this->header_ptr(), to_insert); 1386 } 1387 1388 //! <b>Requires</b>: value must be an lvalue, and it must be no greater 1389 //! than the minimum inserted key 1390 //! 1391 //! <b>Effects</b>: Inserts x into the container in the first position. 1392 //! 1393 //! <b>Complexity</b>: Constant time. 1394 //! 1395 //! <b>Throws</b>: Nothing. 1396 //! 1397 //! <b>Note</b>: This function does not check preconditions so if value is 1398 //! greater than the minimum inserted key container ordering invariant will be broken. 1399 //! This function is slightly more efficient than using "insert_before". 1400 //! This is a low-level function to be used only for performance reasons 1401 //! by advanced users. push_front(reference value)1402 void push_front(reference value) 1403 { 1404 node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); 1405 if(safemode_or_autounlink) 1406 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(to_insert)); 1407 this->sz_traits().increment(); 1408 node_algorithms::push_front(this->header_ptr(), to_insert); 1409 } 1410 1411 //! <b>Effects</b>: Erases the element pointed to by i. 1412 //! 1413 //! <b>Complexity</b>: Average complexity for erase element is constant time. 1414 //! 1415 //! <b>Throws</b>: Nothing. 1416 //! 1417 //! <b>Note</b>: Invalidates the iterators (but not the references) 1418 //! to the erased elements. No destructors are called. erase(const_iterator i)1419 iterator erase(const_iterator i) 1420 { 1421 const_iterator ret(i); 1422 ++ret; 1423 node_ptr to_erase(i.pointed_node()); 1424 if(safemode_or_autounlink) 1425 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!node_algorithms::unique(to_erase)); 1426 node_algorithms::erase(this->header_ptr(), to_erase); 1427 this->sz_traits().decrement(); 1428 if(safemode_or_autounlink) 1429 node_algorithms::init(to_erase); 1430 return ret.unconst(); 1431 } 1432 1433 //! <b>Effects</b>: Erases the range pointed to by b end e. 1434 //! 1435 //! <b>Complexity</b>: Average complexity for erase range is at most 1436 //! O(log(size() + N)), where N is the number of elements in the range. 1437 //! 1438 //! <b>Throws</b>: Nothing. 1439 //! 1440 //! <b>Note</b>: Invalidates the iterators (but not the references) 1441 //! to the erased elements. No destructors are called. erase(const_iterator b,const_iterator e)1442 iterator erase(const_iterator b, const_iterator e) 1443 { size_type n; return this->private_erase(b, e, n); } 1444 1445 //! <b>Effects</b>: Erases all the elements with the given value. 1446 //! 1447 //! <b>Returns</b>: The number of erased elements. 1448 //! 1449 //! <b>Complexity</b>: O(log(size() + N). 1450 //! 1451 //! <b>Throws</b>: Nothing. 1452 //! 1453 //! <b>Note</b>: Invalidates the iterators (but not the references) 1454 //! to the erased elements. No destructors are called. erase(const key_type & key)1455 size_type erase(const key_type &key) 1456 { return this->erase(key, this->key_comp()); } 1457 1458 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1459 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1460 //! with nk the key_type of a value_type inserted into `*this`. 1461 //! 1462 //! <b>Effects</b>: Erases all the elements with the given key. 1463 //! according to the comparison functor "comp". 1464 //! 1465 //! <b>Returns</b>: The number of erased elements. 1466 //! 1467 //! <b>Complexity</b>: O(log(size() + N). 1468 //! 1469 //! <b>Throws</b>: Nothing. 1470 //! 1471 //! <b>Note</b>: Invalidates the iterators (but not the references) 1472 //! to the erased elements. No destructors are called. 1473 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)1474 BOOST_INTRUSIVE_DOC1ST(size_type 1475 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) 1476 erase(const KeyType& key, KeyTypeKeyCompare comp) 1477 { 1478 std::pair<iterator,iterator> p = this->equal_range(key, comp); 1479 size_type n; 1480 this->private_erase(p.first, p.second, n); 1481 return n; 1482 } 1483 1484 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1485 //! 1486 //! <b>Effects</b>: Erases the element pointed to by i. 1487 //! Disposer::operator()(pointer) is called for the removed element. 1488 //! 1489 //! <b>Complexity</b>: Average complexity for erase element is constant time. 1490 //! 1491 //! <b>Throws</b>: Nothing. 1492 //! 1493 //! <b>Note</b>: Invalidates the iterators 1494 //! to the erased elements. 1495 template<class Disposer> erase_and_dispose(const_iterator i,Disposer disposer)1496 iterator erase_and_dispose(const_iterator i, Disposer disposer) 1497 { 1498 node_ptr to_erase(i.pointed_node()); 1499 iterator ret(this->erase(i)); 1500 disposer(this->get_value_traits().to_value_ptr(to_erase)); 1501 return ret; 1502 } 1503 1504 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1505 //! 1506 //! <b>Effects</b>: Erases all the elements with the given value. 1507 //! Disposer::operator()(pointer) is called for the removed elements. 1508 //! 1509 //! <b>Returns</b>: The number of erased elements. 1510 //! 1511 //! <b>Complexity</b>: O(log(size() + N). 1512 //! 1513 //! <b>Throws</b>: Nothing. 1514 //! 1515 //! <b>Note</b>: Invalidates the iterators (but not the references) 1516 //! to the erased elements. No destructors are called. 1517 template<class Disposer> erase_and_dispose(const key_type & key,Disposer disposer)1518 size_type erase_and_dispose(const key_type &key, Disposer disposer) 1519 { 1520 std::pair<iterator,iterator> p = this->equal_range(key); 1521 size_type n; 1522 this->private_erase(p.first, p.second, n, disposer); 1523 return n; 1524 } 1525 1526 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1527 //! 1528 //! <b>Effects</b>: Erases the range pointed to by b end e. 1529 //! Disposer::operator()(pointer) is called for the removed elements. 1530 //! 1531 //! <b>Complexity</b>: Average complexity for erase range is at most 1532 //! O(log(size() + N)), where N is the number of elements in the range. 1533 //! 1534 //! <b>Throws</b>: Nothing. 1535 //! 1536 //! <b>Note</b>: Invalidates the iterators 1537 //! to the erased elements. 1538 template<class Disposer> erase_and_dispose(const_iterator b,const_iterator e,Disposer disposer)1539 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) 1540 { size_type n; return this->private_erase(b, e, n, disposer); } 1541 1542 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1543 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk) 1544 //! and nk the key_type of a value_type inserted into `*this`. 1545 //! 1546 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1547 //! 1548 //! <b>Effects</b>: Erases all the elements with the given key. 1549 //! according to the comparison functor "comp". 1550 //! Disposer::operator()(pointer) is called for the removed elements. 1551 //! 1552 //! <b>Returns</b>: The number of erased elements. 1553 //! 1554 //! <b>Complexity</b>: O(log(size() + N). 1555 //! 1556 //! <b>Throws</b>: Nothing. 1557 //! 1558 //! <b>Note</b>: Invalidates the iterators 1559 //! to the erased elements. 1560 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)1561 BOOST_INTRUSIVE_DOC1ST(size_type 1562 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) 1563 erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer) 1564 { 1565 std::pair<iterator,iterator> p = this->equal_range(key, comp); 1566 size_type n; 1567 this->private_erase(p.first, p.second, n, disposer); 1568 return n; 1569 } 1570 1571 //! <b>Effects</b>: Erases all of the elements. 1572 //! 1573 //! <b>Complexity</b>: Linear to the number of elements on the container. 1574 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. 1575 //! 1576 //! <b>Throws</b>: Nothing. 1577 //! 1578 //! <b>Note</b>: Invalidates the iterators (but not the references) 1579 //! to the erased elements. No destructors are called. clear()1580 void clear() 1581 { 1582 if(safemode_or_autounlink){ 1583 this->clear_and_dispose(detail::null_disposer()); 1584 } 1585 else{ 1586 node_algorithms::init_header(this->header_ptr()); 1587 this->sz_traits().set_size(0); 1588 } 1589 } 1590 1591 //! <b>Effects</b>: Erases all of the elements calling disposer(p) for 1592 //! each node to be erased. 1593 //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)), 1594 //! where N is the number of elements in the container. 1595 //! 1596 //! <b>Throws</b>: Nothing. 1597 //! 1598 //! <b>Note</b>: Invalidates the iterators (but not the references) 1599 //! to the erased elements. Calls N times to disposer functor. 1600 template<class Disposer> clear_and_dispose(Disposer disposer)1601 void clear_and_dispose(Disposer disposer) 1602 { 1603 node_algorithms::clear_and_dispose(this->header_ptr() 1604 , detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); 1605 node_algorithms::init_header(this->header_ptr()); 1606 this->sz_traits().set_size(0); 1607 } 1608 1609 //! <b>Effects</b>: Returns the number of contained elements with the given value 1610 //! 1611 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal 1612 //! to number of objects with the given value. 1613 //! 1614 //! <b>Throws</b>: If `key_compare` throws. count(const key_type & key) const1615 size_type count(const key_type &key) const 1616 { return size_type(this->count(key, this->key_comp())); } 1617 1618 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1619 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1620 //! and nk the key_type of a value_type inserted into `*this`. 1621 //! 1622 //! <b>Effects</b>: Returns the number of contained elements with the given key 1623 //! 1624 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal 1625 //! to number of objects with the given key. 1626 //! 1627 //! <b>Throws</b>: If `comp` throws. 1628 template<class KeyType, class KeyTypeKeyCompare> count(const KeyType & key,KeyTypeKeyCompare comp) const1629 size_type count(const KeyType &key, KeyTypeKeyCompare comp) const 1630 { 1631 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp); 1632 size_type n = 0; 1633 for(; ret.first != ret.second; ++ret.first){ ++n; } 1634 return n; 1635 } 1636 1637 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1638 1639 //Add non-const overloads to theoretically const members 1640 //as some algorithms have different behavior when non-const versions are used (like splay trees). count(const key_type & key)1641 size_type count(const key_type &key) 1642 { return size_type(this->count(key, this->key_comp())); } 1643 1644 template<class KeyType, class KeyTypeKeyCompare> count(const KeyType & key,KeyTypeKeyCompare comp)1645 size_type count(const KeyType &key, KeyTypeKeyCompare comp) 1646 { 1647 std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp); 1648 size_type n = 0; 1649 for(; ret.first != ret.second; ++ret.first){ ++n; } 1650 return n; 1651 } 1652 1653 #else //defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1654 1655 //! <b>Effects</b>: Returns an iterator to the first element whose 1656 //! key is not less than k or end() if that element does not exist. 1657 //! 1658 //! <b>Complexity</b>: Logarithmic. 1659 //! 1660 //! <b>Throws</b>: If `key_compare` throws. 1661 iterator lower_bound(const key_type &key); 1662 1663 //! <b>Effects</b>: Returns an iterator to the first element whose 1664 //! key is not less than k or end() if that element does not exist. 1665 //! 1666 //! <b>Complexity</b>: Logarithmic. 1667 //! 1668 //! <b>Throws</b>: If `key_compare` throws. 1669 const_iterator lower_bound(const key_type &key) const; 1670 1671 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) 1672 template<class KeyType, class KeyTypeKeyCompare> 1673 iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp); 1674 1675 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) 1676 template<class KeyType, class KeyTypeKeyCompare> 1677 const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const; 1678 1679 //! <b>Effects</b>: Returns an iterator to the first element whose 1680 //! key is greater than k or end() if that element does not exist. 1681 //! 1682 //! <b>Complexity</b>: Logarithmic. 1683 //! 1684 //! <b>Throws</b>: If `key_compare` throws. 1685 iterator upper_bound(const key_type &key); 1686 1687 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1688 //! !comp(key, nk), with nk the key_type of a value_type inserted into `*this`. 1689 //! 1690 //! <b>Effects</b>: Returns an iterator to the first element whose 1691 //! key is greater than k according to comp or end() if that element 1692 //! does not exist. 1693 //! 1694 //! <b>Complexity</b>: Logarithmic. 1695 //! 1696 //! <b>Throws</b>: If `comp` throws. 1697 template<class KeyType, class KeyTypeKeyCompare> 1698 iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp); 1699 1700 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) 1701 const_iterator upper_bound(const key_type &key) const; 1702 1703 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) 1704 template<class KeyType, class KeyTypeKeyCompare> 1705 const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const; 1706 1707 //! <b>Effects</b>: Finds an iterator to the first element whose key is 1708 //! k or end() if that element does not exist. 1709 //! 1710 //! <b>Complexity</b>: Logarithmic. 1711 //! 1712 //! <b>Throws</b>: If `key_compare` throws. 1713 iterator find(const key_type &key); 1714 1715 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1716 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1717 //! and nk the key_type of a value_type inserted into `*this`. 1718 //! 1719 //! <b>Effects</b>: Finds an iterator to the first element whose key is 1720 //! k or end() if that element does not exist. 1721 //! 1722 //! <b>Complexity</b>: Logarithmic. 1723 //! 1724 //! <b>Throws</b>: If `comp` throws. 1725 template<class KeyType, class KeyTypeKeyCompare> 1726 iterator find(const KeyType &key, KeyTypeKeyCompare comp); 1727 1728 //! @copydoc ::boost::intrusive::bstree::find(const key_type &) 1729 const_iterator find(const key_type &key) const; 1730 1731 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) 1732 template<class KeyType, class KeyTypeKeyCompare> 1733 const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const; 1734 1735 //! <b>Effects</b>: Finds a range containing all elements whose key is k or 1736 //! an empty range that indicates the position where those elements would be 1737 //! if they there is no elements with key k. 1738 //! 1739 //! <b>Complexity</b>: Logarithmic. 1740 //! 1741 //! <b>Throws</b>: If `key_compare` throws. 1742 std::pair<iterator,iterator> equal_range(const key_type &key); 1743 1744 //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to 1745 //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), 1746 //! with nk the key_type of a value_type inserted into `*this`. 1747 //! 1748 //! <b>Effects</b>: Finds a range containing all elements whose key is k or 1749 //! an empty range that indicates the position where those elements would be 1750 //! if they there is no elements with key k. 1751 //! 1752 //! <b>Complexity</b>: Logarithmic. 1753 //! 1754 //! <b>Throws</b>: If `comp` throws. 1755 template<class KeyType, class KeyTypeKeyCompare> 1756 std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp); 1757 1758 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) 1759 std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const; 1760 1761 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) 1762 template<class KeyType, class KeyTypeKeyCompare> 1763 std::pair<const_iterator, const_iterator> 1764 equal_range(const KeyType &key, KeyTypeKeyCompare comp) const; 1765 1766 //! <b>Requires</b>: 1767 //! `upper_key` shall not precede `lower_key` according to key_compare. 1768 //! [key_comp()(upper_key, lower_key) shall be false] 1769 //! 1770 //! If `lower_key` is equivalent to `upper_key` 1771 //! [!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)] then 1772 //! ('left_closed' || 'right_closed') must be false. 1773 //! 1774 //! <b>Effects</b>: Returns an a pair with the following criteria: 1775 //! 1776 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise 1777 //! 1778 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise 1779 //! 1780 //! <b>Complexity</b>: Logarithmic. 1781 //! 1782 //! <b>Throws</b>: If `key_compare` throws. 1783 //! 1784 //! <b>Note</b>: This function can be more efficient than calling upper_bound 1785 //! and lower_bound for lower_value and upper_value. 1786 //! 1787 //! <b>Note</b>: Experimental function, the interface might change in future releases. 1788 std::pair<iterator,iterator> bounded_range 1789 (const key_type &lower_key, const key_type &upper_value, bool left_closed, bool right_closed); 1790 1791 //! <b>Requires</b>: 1792 //! `lower_key` is a value such that `*this` is partitioned with respect to 1793 //! comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise. 1794 //! 1795 //! `upper_key` is a value such that `*this` is partitioned with respect to 1796 //! !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise. 1797 //! 1798 //! `upper_key` shall not precede `lower_key` according to comp 1799 //! [comp(upper_key, lower_key) shall be false] 1800 //! 1801 //! If `lower_key` is equivalent to `upper_key` 1802 //! [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then 1803 //! ('left_closed' || 'right_closed') must be false. 1804 //! 1805 //! <b>Effects</b>: Returns an a pair with the following criteria: 1806 //! 1807 //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise 1808 //! 1809 //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise 1810 //! 1811 //! <b>Complexity</b>: Logarithmic. 1812 //! 1813 //! <b>Throws</b>: If `comp` throws. 1814 //! 1815 //! <b>Note</b>: This function can be more efficient than calling upper_bound 1816 //! and lower_bound for lower_key and upper_key. 1817 //! 1818 //! <b>Note</b>: Experimental function, the interface might change in future releases. 1819 template<class KeyType, class KeyTypeKeyCompare> 1820 std::pair<iterator,iterator> bounded_range 1821 (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 1822 1823 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) 1824 std::pair<const_iterator,const_iterator> bounded_range 1825 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 1826 1827 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 1828 template<class KeyType, class KeyTypeKeyCompare> 1829 std::pair<const_iterator,const_iterator> bounded_range 1830 (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 1831 1832 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1833 //! appropriate type. Otherwise the behavior is undefined. 1834 //! 1835 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set 1836 //! that points to the value 1837 //! 1838 //! <b>Complexity</b>: Constant. 1839 //! 1840 //! <b>Throws</b>: Nothing. 1841 //! 1842 //! <b>Note</b>: This static function is available only if the <i>value traits</i> 1843 //! is stateless. 1844 static iterator s_iterator_to(reference value); 1845 1846 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1847 //! appropriate type. Otherwise the behavior is undefined. 1848 //! 1849 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the 1850 //! set that points to the value 1851 //! 1852 //! <b>Complexity</b>: Constant. 1853 //! 1854 //! <b>Throws</b>: Nothing. 1855 //! 1856 //! <b>Note</b>: This static function is available only if the <i>value traits</i> 1857 //! is stateless. 1858 static const_iterator s_iterator_to(const_reference value); 1859 1860 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1861 //! appropriate type. Otherwise the behavior is undefined. 1862 //! 1863 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set 1864 //! that points to the value 1865 //! 1866 //! <b>Complexity</b>: Constant. 1867 //! 1868 //! <b>Throws</b>: Nothing. 1869 iterator iterator_to(reference value); 1870 1871 //! <b>Requires</b>: value must be an lvalue and shall be in a set of 1872 //! appropriate type. Otherwise the behavior is undefined. 1873 //! 1874 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the 1875 //! set that points to the value 1876 //! 1877 //! <b>Complexity</b>: Constant. 1878 //! 1879 //! <b>Throws</b>: Nothing. 1880 const_iterator iterator_to(const_reference value) const; 1881 1882 //! <b>Requires</b>: value shall not be in a container. 1883 //! 1884 //! <b>Effects</b>: init_node puts the hook of a value in a well-known default 1885 //! state. 1886 //! 1887 //! <b>Throws</b>: Nothing. 1888 //! 1889 //! <b>Complexity</b>: Constant time. 1890 //! 1891 //! <b>Note</b>: This function puts the hook in the well-known default state 1892 //! used by auto_unlink and safe hooks. 1893 static void init_node(reference value); 1894 1895 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1896 1897 //! <b>Effects</b>: Unlinks the leftmost node from the container. 1898 //! 1899 //! <b>Complexity</b>: Average complexity is constant time. 1900 //! 1901 //! <b>Throws</b>: Nothing. 1902 //! 1903 //! <b>Notes</b>: This function breaks the container and the container can 1904 //! only be used for more unlink_leftmost_without_rebalance calls. 1905 //! This function is normally used to achieve a step by step 1906 //! controlled destruction of the container. unlink_leftmost_without_rebalance()1907 pointer unlink_leftmost_without_rebalance() 1908 { 1909 node_ptr to_be_disposed(node_algorithms::unlink_leftmost_without_rebalance 1910 (this->header_ptr())); 1911 if(!to_be_disposed) 1912 return 0; 1913 this->sz_traits().decrement(); 1914 if(safemode_or_autounlink)//If this is commented does not work with normal_link 1915 node_algorithms::init(to_be_disposed); 1916 return this->get_value_traits().to_value_ptr(to_be_disposed); 1917 } 1918 1919 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1920 1921 //! <b>Requires</b>: replace_this must be a valid iterator of *this 1922 //! and with_this must not be inserted in any container. 1923 //! 1924 //! <b>Effects</b>: Replaces replace_this in its position in the 1925 //! container with with_this. The container does not need to be rebalanced. 1926 //! 1927 //! <b>Complexity</b>: Constant. 1928 //! 1929 //! <b>Throws</b>: Nothing. 1930 //! 1931 //! <b>Note</b>: This function will break container ordering invariants if 1932 //! with_this is not equivalent to *replace_this according to the 1933 //! ordering rules. This function is faster than erasing and inserting 1934 //! the node, since no rebalancing or comparison is needed. 1935 void replace_node(iterator replace_this, reference with_this); 1936 1937 //! <b>Effects</b>: Rebalances the tree. 1938 //! 1939 //! <b>Throws</b>: Nothing. 1940 //! 1941 //! <b>Complexity</b>: Linear. 1942 void rebalance(); 1943 1944 //! <b>Requires</b>: old_root is a node of a tree. 1945 //! 1946 //! <b>Effects</b>: Rebalances the subtree rooted at old_root. 1947 //! 1948 //! <b>Returns</b>: The new root of the subtree. 1949 //! 1950 //! <b>Throws</b>: Nothing. 1951 //! 1952 //! <b>Complexity</b>: Linear to the elements in the subtree. 1953 iterator rebalance_subtree(iterator root); 1954 1955 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1956 1957 //! <b>Effects</b>: removes "value" from the container. 1958 //! 1959 //! <b>Throws</b>: Nothing. 1960 //! 1961 //! <b>Complexity</b>: Logarithmic time. 1962 //! 1963 //! <b>Note</b>: This static function is only usable with non-constant 1964 //! time size containers that have stateless comparison functors. 1965 //! 1966 //! If the user calls 1967 //! this function with a constant time size container or stateful comparison 1968 //! functor a compilation error will be issued. remove_node(reference value)1969 static void remove_node(reference value) 1970 { 1971 BOOST_STATIC_ASSERT((!constant_time_size)); 1972 node_ptr to_remove(value_traits::to_node_ptr(value)); 1973 node_algorithms::unlink(to_remove); 1974 if(safemode_or_autounlink) 1975 node_algorithms::init(to_remove); 1976 } 1977 1978 //! <b>Requires</b>: "source" container's Options can only can differ in the comparison 1979 //! function from *this. 1980 //! 1981 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using 1982 //! the comparison object of *this. If there is an element in a with key equivalent to the 1983 //! key of an element from source, then that element is not extracted from source. 1984 //! 1985 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 1986 //! to those same elements but as members of *this. Iterators referring to the transferred 1987 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 1988 //! not into source. 1989 //! 1990 //! <b>Throws</b>: Nothing unless the comparison object throws. 1991 //! 1992 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) 1993 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1994 template<class T, class ...Options2> void merge_unique(bstree<T, Options2...> &); 1995 #else 1996 template<class Compare2> merge_unique(bstree_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,ConstantTimeSize,AlgoType,HeaderHolder> & source)1997 void merge_unique(bstree_impl 1998 <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source) 1999 #endif 2000 { 2001 node_ptr it (node_algorithms::begin_node(source.header_ptr())) 2002 , itend(node_algorithms::end_node (source.header_ptr())); 2003 2004 while(it != itend){ 2005 node_ptr const p(it); 2006 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); 2007 it = node_algorithms::next_node(it); 2008 if( node_algorithms::transfer_unique(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p) ){ 2009 source.sz_traits().decrement(); 2010 this->sz_traits().increment(); 2011 } 2012 } 2013 } 2014 2015 //! <b>Requires</b>: "source" container's Options can only can differ in the comparison 2016 //! function from *this. 2017 //! 2018 //! <b>Effects</b>: Extracts each element in source and insert it into a using 2019 //! the comparison object of *this. 2020 //! 2021 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer 2022 //! to those same elements but as members of *this. Iterators referring to the transferred 2023 //! elements will continue to refer to their elements, but they now behave as iterators into *this, 2024 //! not into source. 2025 //! 2026 //! <b>Throws</b>: Nothing unless the comparison object throws. 2027 //! 2028 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) 2029 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 2030 template<class T, class ...Options2> void merge_equal(bstree<T, Options2...> &); 2031 #else 2032 template<class Compare2> merge_equal(bstree_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,ConstantTimeSize,AlgoType,HeaderHolder> & source)2033 void merge_equal(bstree_impl 2034 <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source) 2035 #endif 2036 { 2037 node_ptr it (node_algorithms::begin_node(source.header_ptr())) 2038 , itend(node_algorithms::end_node (source.header_ptr())); 2039 2040 while(it != itend){ 2041 node_ptr const p(it); 2042 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); 2043 it = node_algorithms::next_node(it); 2044 node_algorithms::transfer_equal(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p); 2045 source.sz_traits().decrement(); 2046 this->sz_traits().increment(); 2047 } 2048 } 2049 2050 //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user. 2051 //! 2052 //! <b>Complexity</b>: Linear time. 2053 //! 2054 //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG). 2055 //! Experimental function, interface might change in future versions. 2056 template <class ExtraChecker> check(ExtraChecker extra_checker) const2057 void check(ExtraChecker extra_checker) const 2058 { 2059 typedef detail::key_nodeptr_comp<key_compare, value_traits, key_of_value> nodeptr_comp_t; 2060 nodeptr_comp_t nodeptr_comp(this->key_comp(), &this->get_value_traits()); 2061 typedef typename get_node_checker<AlgoType, ValueTraits, nodeptr_comp_t, ExtraChecker>::type node_checker_t; 2062 typename node_checker_t::return_type checker_return; 2063 node_algorithms::check(this->header_ptr(), node_checker_t(nodeptr_comp, extra_checker), checker_return); 2064 if (constant_time_size) 2065 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->sz_traits().get_size() == checker_return.node_count); 2066 } 2067 2068 //! <b>Effects</b>: Asserts the integrity of the container. 2069 //! 2070 //! <b>Complexity</b>: Linear time. 2071 //! 2072 //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). 2073 //! Experimental function, interface might change in future versions. check() const2074 void check() const 2075 { 2076 check(detail::empty_node_checker<ValueTraits>()); 2077 } 2078 operator ==(const bstree_impl & x,const bstree_impl & y)2079 friend bool operator==(const bstree_impl &x, const bstree_impl &y) 2080 { 2081 if(constant_time_size && x.size() != y.size()){ 2082 return false; 2083 } 2084 return boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); 2085 } 2086 operator !=(const bstree_impl & x,const bstree_impl & y)2087 friend bool operator!=(const bstree_impl &x, const bstree_impl &y) 2088 { return !(x == y); } 2089 operator <(const bstree_impl & x,const bstree_impl & y)2090 friend bool operator<(const bstree_impl &x, const bstree_impl &y) 2091 { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 2092 operator >(const bstree_impl & x,const bstree_impl & y)2093 friend bool operator>(const bstree_impl &x, const bstree_impl &y) 2094 { return y < x; } 2095 operator <=(const bstree_impl & x,const bstree_impl & y)2096 friend bool operator<=(const bstree_impl &x, const bstree_impl &y) 2097 { return !(x > y); } 2098 operator >=(const bstree_impl & x,const bstree_impl & y)2099 friend bool operator>=(const bstree_impl &x, const bstree_impl &y) 2100 { return !(x < y); } 2101 swap(bstree_impl & x,bstree_impl & y)2102 friend void swap(bstree_impl &x, bstree_impl &y) 2103 { x.swap(y); } 2104 2105 /// @cond 2106 private: 2107 template<class Disposer> private_erase(const_iterator b,const_iterator e,size_type & n,Disposer disposer)2108 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer) 2109 { 2110 for(n = 0; b != e; ++n) 2111 this->erase_and_dispose(b++, disposer); 2112 return b.unconst(); 2113 } 2114 private_erase(const_iterator b,const_iterator e,size_type & n)2115 iterator private_erase(const_iterator b, const_iterator e, size_type &n) 2116 { 2117 for(n = 0; b != e; ++n) 2118 this->erase(b++); 2119 return b.unconst(); 2120 } 2121 /// @endcond 2122 }; 2123 2124 //! Helper metafunction to define a \c bstree that yields to the same type when the 2125 //! same options (either explicitly or implicitly) are used. 2126 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2127 template<class T, class ...Options> 2128 #else 2129 template<class T, class O1 = void, class O2 = void 2130 , class O3 = void, class O4 = void 2131 , class O5 = void, class O6 = void> 2132 #endif 2133 struct make_bstree 2134 { 2135 /// @cond 2136 typedef typename pack_options 2137 < bstree_defaults, 2138 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2139 O1, O2, O3, O4, O5, O6 2140 #else 2141 Options... 2142 #endif 2143 >::type packed_options; 2144 2145 typedef typename detail::get_value_traits 2146 <T, typename packed_options::proto_value_traits>::type value_traits; 2147 2148 typedef bstree_impl 2149 < value_traits 2150 , typename packed_options::key_of_value 2151 , typename packed_options::compare 2152 , typename packed_options::size_type 2153 , packed_options::constant_time_size 2154 , BsTreeAlgorithms 2155 , typename packed_options::header_holder_type 2156 > implementation_defined; 2157 /// @endcond 2158 typedef implementation_defined type; 2159 }; 2160 2161 2162 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 2163 2164 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2165 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 2166 #else 2167 template<class T, class ...Options> 2168 #endif 2169 class bstree 2170 : public make_bstree<T, 2171 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2172 O1, O2, O3, O4, O5, O6 2173 #else 2174 Options... 2175 #endif 2176 >::type 2177 { 2178 typedef typename make_bstree 2179 <T, 2180 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2181 O1, O2, O3, O4, O5, O6 2182 #else 2183 Options... 2184 #endif 2185 >::type Base; 2186 BOOST_MOVABLE_BUT_NOT_COPYABLE(bstree) 2187 2188 public: 2189 typedef typename Base::key_compare key_compare; 2190 typedef typename Base::value_traits value_traits; 2191 typedef typename Base::iterator iterator; 2192 typedef typename Base::const_iterator const_iterator; 2193 2194 //Assert if passed value traits are compatible with the type 2195 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 2196 bstree()2197 bstree() 2198 : Base() 2199 {} 2200 bstree(const key_compare & cmp,const value_traits & v_traits=value_traits ())2201 explicit bstree( const key_compare &cmp, const value_traits &v_traits = value_traits()) 2202 : Base(cmp, v_traits) 2203 {} 2204 2205 template<class Iterator> bstree(bool unique,Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())2206 bstree( bool unique, Iterator b, Iterator e 2207 , const key_compare &cmp = key_compare() 2208 , const value_traits &v_traits = value_traits()) 2209 : Base(unique, b, e, cmp, v_traits) 2210 {} 2211 bstree(BOOST_RV_REF (bstree)x)2212 bstree(BOOST_RV_REF(bstree) x) 2213 : Base(BOOST_MOVE_BASE(Base, x)) 2214 {} 2215 operator =(BOOST_RV_REF (bstree)x)2216 bstree& operator=(BOOST_RV_REF(bstree) x) 2217 { return static_cast<bstree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 2218 2219 template <class Cloner, class Disposer> clone_from(const bstree & src,Cloner cloner,Disposer disposer)2220 void clone_from(const bstree &src, Cloner cloner, Disposer disposer) 2221 { Base::clone_from(src, cloner, disposer); } 2222 2223 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (bstree)src,Cloner cloner,Disposer disposer)2224 void clone_from(BOOST_RV_REF(bstree) src, Cloner cloner, Disposer disposer) 2225 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 2226 container_from_end_iterator(iterator end_iterator)2227 static bstree &container_from_end_iterator(iterator end_iterator) 2228 { return static_cast<bstree &>(Base::container_from_end_iterator(end_iterator)); } 2229 container_from_end_iterator(const_iterator end_iterator)2230 static const bstree &container_from_end_iterator(const_iterator end_iterator) 2231 { return static_cast<const bstree &>(Base::container_from_end_iterator(end_iterator)); } 2232 container_from_iterator(iterator it)2233 static bstree &container_from_iterator(iterator it) 2234 { return static_cast<bstree &>(Base::container_from_iterator(it)); } 2235 container_from_iterator(const_iterator it)2236 static const bstree &container_from_iterator(const_iterator it) 2237 { return static_cast<const bstree &>(Base::container_from_iterator(it)); } 2238 }; 2239 2240 #endif 2241 } //namespace intrusive 2242 } //namespace boost 2243 2244 #include <boost/intrusive/detail/config_end.hpp> 2245 2246 #endif //BOOST_INTRUSIVE_BSTREE_HPP 2247