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