1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2005-2015. Distributed under the Boost 4 // Software License, Version 1.0. (See accompanying file 5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 // 7 // See http://www.boost.org/libs/container for documentation. 8 // 9 ////////////////////////////////////////////////////////////////////////////// 10 11 #ifndef BOOST_CONTAINER_TREE_HPP 12 #define BOOST_CONTAINER_TREE_HPP 13 14 #ifndef BOOST_CONFIG_HPP 15 # include <boost/config.hpp> 16 #endif 17 18 #if defined(BOOST_HAS_PRAGMA_ONCE) 19 # pragma once 20 #endif 21 22 #include <boost/container/detail/config_begin.hpp> 23 #include <boost/container/detail/workaround.hpp> 24 // container 25 #include <boost/container/allocator_traits.hpp> 26 #include <boost/container/container_fwd.hpp> 27 #include <boost/container/options.hpp> 28 #include <boost/container/node_handle.hpp> 29 30 // container/detail 31 #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare 32 #include <boost/container/detail/compare_functors.hpp> 33 #include <boost/container/detail/destroyers.hpp> 34 #include <boost/container/detail/iterator.hpp> 35 #include <boost/container/detail/iterators.hpp> 36 #include <boost/container/detail/node_alloc_holder.hpp> 37 #include <boost/container/detail/pair.hpp> 38 #include <boost/container/detail/type_traits.hpp> 39 // intrusive 40 #include <boost/intrusive/pointer_traits.hpp> 41 #include <boost/intrusive/rbtree.hpp> 42 #include <boost/intrusive/avltree.hpp> 43 #include <boost/intrusive/splaytree.hpp> 44 #include <boost/intrusive/sgtree.hpp> 45 // intrusive/detail 46 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair 47 #include <boost/intrusive/detail/tree_value_compare.hpp> //tree_value_compare 48 // move 49 #include <boost/move/utility_core.hpp> 50 // move/detail 51 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 52 #include <boost/move/detail/fwd_macros.hpp> 53 #endif 54 #include <boost/move/detail/move_helpers.hpp> 55 // other 56 #include <boost/core/no_exceptions_support.hpp> 57 58 59 60 #include <boost/container/detail/std_fwd.hpp> 61 62 namespace boost { 63 namespace container { 64 namespace dtl { 65 66 using boost::intrusive::tree_value_compare; 67 68 template<class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> 69 struct intrusive_tree_hook; 70 71 template<class VoidPointer, bool OptimizeSize> 72 struct intrusive_tree_hook<VoidPointer, boost::container::red_black_tree, OptimizeSize> 73 { 74 typedef typename dtl::bi::make_set_base_hook 75 < dtl::bi::void_pointer<VoidPointer> 76 , dtl::bi::link_mode<dtl::bi::normal_link> 77 , dtl::bi::optimize_size<OptimizeSize> 78 >::type type; 79 }; 80 81 template<class VoidPointer, bool OptimizeSize> 82 struct intrusive_tree_hook<VoidPointer, boost::container::avl_tree, OptimizeSize> 83 { 84 typedef typename dtl::bi::make_avl_set_base_hook 85 < dtl::bi::void_pointer<VoidPointer> 86 , dtl::bi::link_mode<dtl::bi::normal_link> 87 , dtl::bi::optimize_size<OptimizeSize> 88 >::type type; 89 }; 90 91 template<class VoidPointer, bool OptimizeSize> 92 struct intrusive_tree_hook<VoidPointer, boost::container::scapegoat_tree, OptimizeSize> 93 { 94 typedef typename dtl::bi::make_bs_set_base_hook 95 < dtl::bi::void_pointer<VoidPointer> 96 , dtl::bi::link_mode<dtl::bi::normal_link> 97 >::type type; 98 }; 99 100 template<class VoidPointer, bool OptimizeSize> 101 struct intrusive_tree_hook<VoidPointer, boost::container::splay_tree, OptimizeSize> 102 { 103 typedef typename dtl::bi::make_bs_set_base_hook 104 < dtl::bi::void_pointer<VoidPointer> 105 , dtl::bi::link_mode<dtl::bi::normal_link> 106 >::type type; 107 }; 108 109 //This trait is used to type-pun std::pair because in C++03 110 //compilers std::pair is useless for C++11 features 111 template<class T> 112 struct tree_internal_data_type 113 { 114 typedef T type; 115 }; 116 117 template<class T1, class T2> 118 struct tree_internal_data_type< std::pair<T1, T2> > 119 { 120 typedef pair<typename boost::move_detail::remove_const<T1>::type, T2> type; 121 }; 122 123 //The node to be store in the tree 124 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> 125 struct tree_node 126 : public intrusive_tree_hook<VoidPointer, tree_type_value, OptimizeSize>::type 127 { 128 public: 129 typedef typename intrusive_tree_hook 130 <VoidPointer, tree_type_value, OptimizeSize>::type hook_type; 131 typedef T value_type; 132 typedef typename tree_internal_data_type<T>::type internal_type; 133 134 typedef tree_node< T, VoidPointer 135 , tree_type_value, OptimizeSize> node_t; 136 137 typedef typename boost::container::dtl::aligned_storage 138 <sizeof(T), boost::container::dtl::alignment_of<T>::value>::type storage_t; 139 storage_t m_storage; 140 141 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000) 142 #pragma GCC diagnostic push 143 #pragma GCC diagnostic ignored "-Wstrict-aliasing" 144 #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING 145 # endif 146 get_databoost::container::dtl::tree_node147 BOOST_CONTAINER_FORCEINLINE T &get_data() 148 { return *reinterpret_cast<T*>(this->m_storage.data); } 149 get_databoost::container::dtl::tree_node150 BOOST_CONTAINER_FORCEINLINE const T &get_data() const 151 { return *reinterpret_cast<const T*>(this->m_storage.data); } 152 get_data_ptrboost::container::dtl::tree_node153 BOOST_CONTAINER_FORCEINLINE T *get_data_ptr() 154 { return reinterpret_cast<T*>(this->m_storage.data); } 155 get_data_ptrboost::container::dtl::tree_node156 BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const 157 { return reinterpret_cast<T*>(this->m_storage.data); } 158 get_real_databoost::container::dtl::tree_node159 BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data() 160 { return *reinterpret_cast<internal_type*>(this->m_storage.data); } 161 get_real_databoost::container::dtl::tree_node162 BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const 163 { return *reinterpret_cast<const internal_type*>(this->m_storage.data); } 164 get_real_data_ptrboost::container::dtl::tree_node165 BOOST_CONTAINER_FORCEINLINE internal_type *get_real_data_ptr() 166 { return reinterpret_cast<internal_type*>(this->m_storage.data); } 167 get_real_data_ptrboost::container::dtl::tree_node168 BOOST_CONTAINER_FORCEINLINE const internal_type *get_real_data_ptr() const 169 { return reinterpret_cast<internal_type*>(this->m_storage.data); } 170 ~tree_nodeboost::container::dtl::tree_node171 BOOST_CONTAINER_FORCEINLINE ~tree_node() 172 { reinterpret_cast<internal_type*>(this->m_storage.data)->~internal_type(); } 173 174 #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING) 175 #pragma GCC diagnostic pop 176 #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING 177 # endif 178 destroy_headerboost::container::dtl::tree_node179 BOOST_CONTAINER_FORCEINLINE void destroy_header() 180 { static_cast<hook_type*>(this)->~hook_type(); } 181 182 template<class T1, class T2> do_assignboost::container::dtl::tree_node183 BOOST_CONTAINER_FORCEINLINE void do_assign(const std::pair<const T1, T2> &p) 184 { 185 const_cast<T1&>(this->get_real_data().first) = p.first; 186 this->get_real_data().second = p.second; 187 } 188 189 template<class T1, class T2> do_assignboost::container::dtl::tree_node190 BOOST_CONTAINER_FORCEINLINE void do_assign(const pair<const T1, T2> &p) 191 { 192 const_cast<T1&>(this->get_real_data().first) = p.first; 193 this->get_real_data().second = p.second; 194 } 195 196 template<class V> do_assignboost::container::dtl::tree_node197 BOOST_CONTAINER_FORCEINLINE void do_assign(const V &v) 198 { this->get_real_data() = v; } 199 200 template<class T1, class T2> do_move_assignboost::container::dtl::tree_node201 BOOST_CONTAINER_FORCEINLINE void do_move_assign(std::pair<const T1, T2> &p) 202 { 203 const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first); 204 this->get_real_data().second = ::boost::move(p.second); 205 } 206 207 template<class T1, class T2> do_move_assignboost::container::dtl::tree_node208 BOOST_CONTAINER_FORCEINLINE void do_move_assign(pair<const T1, T2> &p) 209 { 210 const_cast<T1&>(this->get_real_data().first) = ::boost::move(p.first); 211 this->get_real_data().second = ::boost::move(p.second); 212 } 213 214 template<class V> do_move_assignboost::container::dtl::tree_node215 BOOST_CONTAINER_FORCEINLINE void do_move_assign(V &v) 216 { this->get_real_data() = ::boost::move(v); } 217 }; 218 219 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> 220 struct iiterator_node_value_type< tree_node<T, VoidPointer, tree_type_value, OptimizeSize> > { 221 typedef T type; 222 }; 223 224 template<class Node, class Icont> 225 class insert_equal_end_hint_functor 226 { 227 Icont &icont_; 228 229 public: insert_equal_end_hint_functor(Icont & icont)230 BOOST_CONTAINER_FORCEINLINE insert_equal_end_hint_functor(Icont &icont) 231 : icont_(icont) 232 {} 233 operator ()(Node & n)234 BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) 235 { this->icont_.insert_equal(this->icont_.cend(), n); } 236 }; 237 238 template<class Node, class Icont> 239 class push_back_functor 240 { 241 Icont &icont_; 242 243 public: push_back_functor(Icont & icont)244 BOOST_CONTAINER_FORCEINLINE push_back_functor(Icont &icont) 245 : icont_(icont) 246 {} 247 operator ()(Node & n)248 BOOST_CONTAINER_FORCEINLINE void operator()(Node &n) 249 { this->icont_.push_back(n); } 250 }; 251 252 }//namespace dtl { 253 254 namespace dtl { 255 256 template< class NodeType, class NodeCompareType 257 , class SizeType, class HookType 258 , boost::container::tree_type_enum tree_type_value> 259 struct intrusive_tree_dispatch; 260 261 template<class NodeType, class NodeCompareType, class SizeType, class HookType> 262 struct intrusive_tree_dispatch 263 <NodeType, NodeCompareType, SizeType, HookType, boost::container::red_black_tree> 264 { 265 typedef typename dtl::bi::make_rbtree 266 <NodeType 267 ,dtl::bi::compare<NodeCompareType> 268 ,dtl::bi::base_hook<HookType> 269 ,dtl::bi::constant_time_size<true> 270 ,dtl::bi::size_type<SizeType> 271 >::type type; 272 }; 273 274 template<class NodeType, class NodeCompareType, class SizeType, class HookType> 275 struct intrusive_tree_dispatch 276 <NodeType, NodeCompareType, SizeType, HookType, boost::container::avl_tree> 277 { 278 typedef typename dtl::bi::make_avltree 279 <NodeType 280 ,dtl::bi::compare<NodeCompareType> 281 ,dtl::bi::base_hook<HookType> 282 ,dtl::bi::constant_time_size<true> 283 ,dtl::bi::size_type<SizeType> 284 >::type type; 285 }; 286 287 template<class NodeType, class NodeCompareType, class SizeType, class HookType> 288 struct intrusive_tree_dispatch 289 <NodeType, NodeCompareType, SizeType, HookType, boost::container::scapegoat_tree> 290 { 291 typedef typename dtl::bi::make_sgtree 292 <NodeType 293 ,dtl::bi::compare<NodeCompareType> 294 ,dtl::bi::base_hook<HookType> 295 ,dtl::bi::floating_point<true> 296 ,dtl::bi::size_type<SizeType> 297 >::type type; 298 }; 299 300 template<class NodeType, class NodeCompareType, class SizeType, class HookType> 301 struct intrusive_tree_dispatch 302 <NodeType, NodeCompareType, SizeType, HookType, boost::container::splay_tree> 303 { 304 typedef typename dtl::bi::make_splaytree 305 <NodeType 306 ,dtl::bi::compare<NodeCompareType> 307 ,dtl::bi::base_hook<HookType> 308 ,dtl::bi::constant_time_size<true> 309 ,dtl::bi::size_type<SizeType> 310 >::type type; 311 }; 312 313 template<class Allocator, class ValueCompare, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> 314 struct intrusive_tree_type 315 { 316 private: 317 typedef typename boost::container:: 318 allocator_traits<Allocator>::value_type value_type; 319 typedef typename boost::container:: 320 allocator_traits<Allocator>::void_pointer void_pointer; 321 typedef typename boost::container:: 322 allocator_traits<Allocator>::size_type size_type; 323 typedef typename dtl::tree_node 324 < value_type, void_pointer 325 , tree_type_value, OptimizeSize> node_t; 326 typedef value_to_node_compare 327 <node_t, ValueCompare> node_compare_type; 328 //Deducing the hook type from node_t (e.g. node_t::hook_type) would 329 //provoke an early instantiation of node_t that could ruin recursive 330 //tree definitions, so retype the complete type to avoid any problem. 331 typedef typename intrusive_tree_hook 332 <void_pointer, tree_type_value 333 , OptimizeSize>::type hook_type; 334 public: 335 typedef typename intrusive_tree_dispatch 336 < node_t, node_compare_type 337 , size_type, hook_type 338 , tree_type_value>::type type; 339 }; 340 341 //Trait to detect manually rebalanceable tree types 342 template<boost::container::tree_type_enum tree_type_value> 343 struct is_manually_balanceable 344 { static const bool value = true; }; 345 346 template<> struct is_manually_balanceable<red_black_tree> 347 { static const bool value = false; }; 348 349 template<> struct is_manually_balanceable<avl_tree> 350 { static const bool value = false; }; 351 352 //Proxy traits to implement different operations depending on the 353 //is_manually_balanceable<>::value 354 template< boost::container::tree_type_enum tree_type_value 355 , bool IsManuallyRebalanceable = is_manually_balanceable<tree_type_value>::value> 356 struct intrusive_tree_proxy 357 { 358 template<class Icont> rebalanceboost::container::dtl::intrusive_tree_proxy359 BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &) {} 360 }; 361 362 template<boost::container::tree_type_enum tree_type_value> 363 struct intrusive_tree_proxy<tree_type_value, true> 364 { 365 template<class Icont> rebalanceboost::container::dtl::intrusive_tree_proxy366 BOOST_CONTAINER_FORCEINLINE static void rebalance(Icont &c) 367 { c.rebalance(); } 368 }; 369 370 } //namespace dtl { 371 372 namespace dtl { 373 374 //This functor will be used with Intrusive clone functions to obtain 375 //already allocated nodes from a intrusive container instead of 376 //allocating new ones. When the intrusive container runs out of nodes 377 //the node holder is used instead. 378 template<class AllocHolder, bool DoMove> 379 class RecyclingCloner 380 { 381 typedef typename AllocHolder::intrusive_container intrusive_container; 382 typedef typename AllocHolder::Node node_t; 383 typedef typename AllocHolder::NodePtr node_ptr_type; 384 385 public: RecyclingCloner(AllocHolder & holder,intrusive_container & itree)386 RecyclingCloner(AllocHolder &holder, intrusive_container &itree) 387 : m_holder(holder), m_icont(itree) 388 {} 389 do_assign(node_ptr_type & p,const node_t & other,bool_<true>)390 BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<true>) 391 { p->do_move_assign(const_cast<node_t &>(other).get_real_data()); } 392 do_assign(node_ptr_type & p,const node_t & other,bool_<false>)393 BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, const node_t &other, bool_<false>) 394 { p->do_assign(other.get_real_data()); } 395 operator ()(const node_t & other) const396 node_ptr_type operator()(const node_t &other) const 397 { 398 if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ 399 //First recycle a node (this can't throw) 400 BOOST_TRY{ 401 //This can throw 402 this->do_assign(p, other, bool_<DoMove>()); 403 return p; 404 } 405 BOOST_CATCH(...){ 406 //If there is an exception destroy the whole source 407 m_holder.destroy_node(p); 408 while((p = m_icont.unlink_leftmost_without_rebalance())){ 409 m_holder.destroy_node(p); 410 } 411 BOOST_RETHROW 412 } 413 BOOST_CATCH_END 414 } 415 else{ 416 return m_holder.create_node(other.get_real_data()); 417 } 418 } 419 420 AllocHolder &m_holder; 421 intrusive_container &m_icont; 422 }; 423 424 425 template<class KeyCompare, class KeyOfValue> 426 struct key_node_compare 427 : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> 428 { key_node_compareboost::container::dtl::key_node_compare429 BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp) 430 : base_t(comp) 431 {} 432 433 typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t; 434 typedef KeyCompare key_compare; 435 typedef KeyOfValue key_of_value; 436 typedef typename KeyOfValue::type key_type; 437 438 439 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> 440 BOOST_CONTAINER_FORCEINLINE static const key_type & key_fromboost::container::dtl::key_node_compare441 key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n) 442 { 443 return key_of_value()(n.get_data()); 444 } 445 446 template <class T> 447 BOOST_CONTAINER_FORCEINLINE static const T & key_fromboost::container::dtl::key_node_compare448 key_from(const T &t) 449 { 450 return t; 451 } 452 key_compboost::container::dtl::key_node_compare453 BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const 454 { return static_cast<const key_compare &>(*this); } 455 key_compboost::container::dtl::key_node_compare456 BOOST_CONTAINER_FORCEINLINE key_compare &key_comp() 457 { return static_cast<key_compare &>(*this); } 458 operator ()boost::container::dtl::key_node_compare459 BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const 460 { return this->key_comp()(key1, key2); } 461 462 template<class U> operator ()boost::container::dtl::key_node_compare463 BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const 464 { return this->key_comp()(key1, this->key_from(nonkey2)); } 465 466 template<class U> operator ()boost::container::dtl::key_node_compare467 BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const 468 { return this->key_comp()(this->key_from(nonkey1), key2); } 469 470 template<class U, class V> operator ()boost::container::dtl::key_node_compare471 BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const 472 { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); } 473 }; 474 475 template<class Options> 476 struct get_tree_opt 477 { 478 typedef Options type; 479 }; 480 481 template<> 482 struct get_tree_opt<void> 483 { 484 typedef tree_assoc_defaults type; 485 }; 486 487 template<class, class KeyOfValue> 488 struct real_key_of_value 489 { 490 typedef KeyOfValue type; 491 }; 492 493 template<class T> 494 struct real_key_of_value<T, void> 495 { 496 typedef dtl::identity<T> type; 497 }; 498 499 template<class T1, class T2> 500 struct real_key_of_value<std::pair<T1, T2>, int> 501 { 502 typedef dtl::select1st<T1> type; 503 }; 504 505 template<class T1, class T2> 506 struct real_key_of_value<boost::container::pair<T1, T2>, int> 507 { 508 typedef dtl::select1st<T1> type; 509 }; 510 511 template <class T, class KeyOfValue, class Compare, class Allocator, class Options> 512 class tree 513 : public dtl::node_alloc_holder 514 < typename real_allocator<T, Allocator>::type 515 , typename dtl::intrusive_tree_type 516 < typename real_allocator<T, Allocator>::type 517 , tree_value_compare 518 <typename allocator_traits<typename real_allocator<T, Allocator>::type>::pointer, Compare, typename real_key_of_value<T, KeyOfValue>::type> 519 , get_tree_opt<Options>::type::tree_type 520 , get_tree_opt<Options>::type::optimize_size 521 >::type 522 > 523 { 524 typedef tree < T, KeyOfValue 525 , Compare, Allocator, Options> ThisType; 526 public: 527 typedef typename real_allocator<T, Allocator>::type allocator_type; 528 529 private: 530 typedef allocator_traits<allocator_type> allocator_traits_t; 531 typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t; 532 typedef tree_value_compare 533 < typename allocator_traits_t::pointer 534 , Compare 535 , key_of_value_t> ValComp; 536 typedef typename get_tree_opt<Options>::type options_type; 537 typedef typename dtl::intrusive_tree_type 538 < allocator_type, ValComp 539 , options_type::tree_type 540 , options_type::optimize_size 541 >::type Icont; 542 typedef dtl::node_alloc_holder 543 <allocator_type, Icont> AllocHolder; 544 typedef typename AllocHolder::NodePtr NodePtr; 545 546 typedef typename AllocHolder::NodeAlloc NodeAlloc; 547 typedef boost::container:: 548 allocator_traits<NodeAlloc> allocator_traits_type; 549 typedef typename AllocHolder::ValAlloc ValAlloc; 550 typedef typename AllocHolder::Node Node; 551 typedef typename Icont::iterator iiterator; 552 typedef typename Icont::const_iterator iconst_iterator; 553 typedef dtl::allocator_destroyer<NodeAlloc> Destroyer; 554 typedef typename AllocHolder::alloc_version alloc_version; 555 typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t; 556 557 BOOST_COPYABLE_AND_MOVABLE(tree) 558 559 public: 560 561 typedef typename key_of_value_t::type key_type; 562 typedef T value_type; 563 typedef Compare key_compare; 564 typedef ValComp value_compare; 565 typedef typename boost::container:: 566 allocator_traits<allocator_type>::pointer pointer; 567 typedef typename boost::container:: 568 allocator_traits<allocator_type>::const_pointer const_pointer; 569 typedef typename boost::container:: 570 allocator_traits<allocator_type>::reference reference; 571 typedef typename boost::container:: 572 allocator_traits<allocator_type>::const_reference const_reference; 573 typedef typename boost::container:: 574 allocator_traits<allocator_type>::size_type size_type; 575 typedef typename boost::container:: 576 allocator_traits<allocator_type>::difference_type difference_type; 577 typedef dtl::iterator_from_iiterator 578 <iiterator, false> iterator; 579 typedef dtl::iterator_from_iiterator 580 <iiterator, true > const_iterator; 581 typedef boost::container::reverse_iterator 582 <iterator> reverse_iterator; 583 typedef boost::container::reverse_iterator 584 <const_iterator> const_reverse_iterator; 585 typedef node_handle 586 < NodeAlloc, void> node_type; 587 typedef insert_return_type_base 588 <iterator, node_type> insert_return_type; 589 590 typedef NodeAlloc stored_allocator_type; 591 592 private: 593 594 typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare; 595 596 public: 597 tree()598 BOOST_CONTAINER_FORCEINLINE tree() 599 : AllocHolder() 600 {} 601 tree(const key_compare & comp)602 BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp) 603 : AllocHolder(ValComp(comp)) 604 {} 605 tree(const key_compare & comp,const allocator_type & a)606 BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a) 607 : AllocHolder(ValComp(comp), a) 608 {} 609 tree(const allocator_type & a)610 BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a) 611 : AllocHolder(a) 612 {} 613 614 template <class InputIterator> tree(bool unique_insertion,InputIterator first,InputIterator last)615 tree(bool unique_insertion, InputIterator first, InputIterator last) 616 : AllocHolder(value_compare(key_compare())) 617 { 618 this->tree_construct(unique_insertion, first, last); 619 //AllocHolder clears in case of exception 620 } 621 622 template <class InputIterator> tree(bool unique_insertion,InputIterator first,InputIterator last,const key_compare & comp)623 tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp) 624 : AllocHolder(value_compare(comp)) 625 { 626 this->tree_construct(unique_insertion, first, last); 627 //AllocHolder clears in case of exception 628 } 629 630 template <class InputIterator> tree(bool unique_insertion,InputIterator first,InputIterator last,const key_compare & comp,const allocator_type & a)631 tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a) 632 : AllocHolder(value_compare(comp), a) 633 { 634 this->tree_construct(unique_insertion, first, last); 635 //AllocHolder clears in case of exception 636 } 637 638 //construct with ordered range 639 template <class InputIterator> tree(ordered_range_t,InputIterator first,InputIterator last)640 tree( ordered_range_t, InputIterator first, InputIterator last) 641 : AllocHolder(value_compare(key_compare())) 642 { 643 this->tree_construct(ordered_range_t(), first, last); 644 } 645 646 template <class InputIterator> tree(ordered_range_t,InputIterator first,InputIterator last,const key_compare & comp)647 tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp) 648 : AllocHolder(value_compare(comp)) 649 { 650 this->tree_construct(ordered_range_t(), first, last); 651 } 652 653 template <class InputIterator> tree(ordered_range_t,InputIterator first,InputIterator last,const key_compare & comp,const allocator_type & a)654 tree( ordered_range_t, InputIterator first, InputIterator last 655 , const key_compare& comp, const allocator_type& a) 656 : AllocHolder(value_compare(comp), a) 657 { 658 this->tree_construct(ordered_range_t(), first, last); 659 } 660 661 private: 662 663 template <class InputIterator> tree_construct(bool unique_insertion,InputIterator first,InputIterator last)664 void tree_construct(bool unique_insertion, InputIterator first, InputIterator last) 665 { 666 //Use cend() as hint to achieve linear time for 667 //ordered ranges as required by the standard 668 //for the constructor 669 if(unique_insertion){ 670 const const_iterator end_it(this->cend()); 671 for ( ; first != last; ++first){ 672 this->insert_unique_convertible(end_it, *first); 673 } 674 } 675 else{ 676 this->tree_construct_non_unique(first, last); 677 } 678 } 679 680 template <class InputIterator> tree_construct_non_unique(InputIterator first,InputIterator last,typename dtl::enable_if_or<void,dtl::is_same<alloc_version,version_1>,dtl::is_input_iterator<InputIterator>>::type * =0)681 void tree_construct_non_unique(InputIterator first, InputIterator last 682 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 683 , typename dtl::enable_if_or 684 < void 685 , dtl::is_same<alloc_version, version_1> 686 , dtl::is_input_iterator<InputIterator> 687 >::type * = 0 688 #endif 689 ) 690 { 691 //Use cend() as hint to achieve linear time for 692 //ordered ranges as required by the standard 693 //for the constructor 694 const const_iterator end_it(this->cend()); 695 for ( ; first != last; ++first){ 696 this->insert_equal_convertible(end_it, *first); 697 } 698 } 699 700 template <class InputIterator> tree_construct_non_unique(InputIterator first,InputIterator last,typename dtl::disable_if_or<void,dtl::is_same<alloc_version,version_1>,dtl::is_input_iterator<InputIterator>>::type * =0)701 void tree_construct_non_unique(InputIterator first, InputIterator last 702 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 703 , typename dtl::disable_if_or 704 < void 705 , dtl::is_same<alloc_version, version_1> 706 , dtl::is_input_iterator<InputIterator> 707 >::type * = 0 708 #endif 709 ) 710 { 711 //Optimized allocation and construction 712 this->allocate_many_and_construct 713 ( first, boost::container::iterator_distance(first, last) 714 , insert_equal_end_hint_functor<Node, Icont>(this->icont())); 715 } 716 717 template <class InputIterator> tree_construct(ordered_range_t,InputIterator first,InputIterator last,typename dtl::disable_if_or<void,dtl::is_same<alloc_version,version_1>,dtl::is_input_iterator<InputIterator>>::type * =0)718 void tree_construct( ordered_range_t, InputIterator first, InputIterator last 719 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 720 , typename dtl::disable_if_or 721 < void 722 , dtl::is_same<alloc_version, version_1> 723 , dtl::is_input_iterator<InputIterator> 724 >::type * = 0 725 #endif 726 ) 727 { 728 //Optimized allocation and construction 729 this->allocate_many_and_construct 730 ( first, boost::container::iterator_distance(first, last) 731 , dtl::push_back_functor<Node, Icont>(this->icont())); 732 //AllocHolder clears in case of exception 733 } 734 735 template <class InputIterator> tree_construct(ordered_range_t,InputIterator first,InputIterator last,typename dtl::enable_if_or<void,dtl::is_same<alloc_version,version_1>,dtl::is_input_iterator<InputIterator>>::type * =0)736 void tree_construct( ordered_range_t, InputIterator first, InputIterator last 737 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 738 , typename dtl::enable_if_or 739 < void 740 , dtl::is_same<alloc_version, version_1> 741 , dtl::is_input_iterator<InputIterator> 742 >::type * = 0 743 #endif 744 ) 745 { 746 for ( ; first != last; ++first){ 747 this->push_back_impl(*first); 748 } 749 } 750 751 public: 752 tree(const tree & x)753 BOOST_CONTAINER_FORCEINLINE tree(const tree& x) 754 : AllocHolder(x, x.value_comp()) 755 { 756 this->icont().clone_from 757 (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); 758 } 759 tree(BOOST_RV_REF (tree)x)760 BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x) 761 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) 762 : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) 763 {} 764 tree(const tree & x,const allocator_type & a)765 BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a) 766 : AllocHolder(x.value_comp(), a) 767 { 768 this->icont().clone_from 769 (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); 770 //AllocHolder clears in case of exception 771 } 772 tree(BOOST_RV_REF (tree)x,const allocator_type & a)773 tree(BOOST_RV_REF(tree) x, const allocator_type &a) 774 : AllocHolder(x.value_comp(), a) 775 { 776 if(this->node_alloc() == x.node_alloc()){ 777 this->icont().swap(x.icont()); 778 } 779 else{ 780 this->icont().clone_from 781 (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); 782 } 783 //AllocHolder clears in case of exception 784 } 785 ~tree()786 BOOST_CONTAINER_FORCEINLINE ~tree() 787 {} //AllocHolder clears the tree 788 operator =(BOOST_COPY_ASSIGN_REF (tree)x)789 tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) 790 { 791 if (&x != this){ 792 NodeAlloc &this_alloc = this->get_stored_allocator(); 793 const NodeAlloc &x_alloc = x.get_stored_allocator(); 794 dtl::bool_<allocator_traits<NodeAlloc>:: 795 propagate_on_container_copy_assignment::value> flag; 796 if(flag && this_alloc != x_alloc){ 797 this->clear(); 798 } 799 this->AllocHolder::copy_assign_alloc(x); 800 //Transfer all the nodes to a temporary tree 801 //If anything goes wrong, all the nodes will be destroyed 802 //automatically 803 Icont other_tree(::boost::move(this->icont())); 804 805 //Now recreate the source tree reusing nodes stored by other_tree 806 this->icont().clone_from 807 (x.icont() 808 , RecyclingCloner<AllocHolder, false>(*this, other_tree) 809 , Destroyer(this->node_alloc())); 810 811 //If there are remaining nodes, destroy them 812 NodePtr p; 813 while((p = other_tree.unlink_leftmost_without_rebalance())){ 814 AllocHolder::destroy_node(p); 815 } 816 } 817 return *this; 818 } 819 operator =(BOOST_RV_REF (tree)x)820 tree& operator=(BOOST_RV_REF(tree) x) 821 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || 822 allocator_traits_type::is_always_equal::value) && 823 boost::container::dtl::is_nothrow_move_assignable<Compare>::value) 824 { 825 BOOST_ASSERT(this != &x); 826 NodeAlloc &this_alloc = this->node_alloc(); 827 NodeAlloc &x_alloc = x.node_alloc(); 828 const bool propagate_alloc = allocator_traits<NodeAlloc>:: 829 propagate_on_container_move_assignment::value; 830 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; 831 //Resources can be transferred if both allocators are 832 //going to be equal after this function (either propagated or already equal) 833 if(propagate_alloc || allocators_equal){ 834 //Destroy 835 this->clear(); 836 //Move allocator if needed 837 this->AllocHolder::move_assign_alloc(x); 838 //Obtain resources 839 this->icont() = boost::move(x.icont()); 840 } 841 //Else do a one by one move 842 else{ 843 //Transfer all the nodes to a temporary tree 844 //If anything goes wrong, all the nodes will be destroyed 845 //automatically 846 Icont other_tree(::boost::move(this->icont())); 847 848 //Now recreate the source tree reusing nodes stored by other_tree 849 this->icont().clone_from 850 (::boost::move(x.icont()) 851 , RecyclingCloner<AllocHolder, true>(*this, other_tree) 852 , Destroyer(this->node_alloc())); 853 854 //If there are remaining nodes, destroy them 855 NodePtr p; 856 while((p = other_tree.unlink_leftmost_without_rebalance())){ 857 AllocHolder::destroy_node(p); 858 } 859 } 860 return *this; 861 } 862 863 public: 864 // accessors: value_comp() const865 BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const 866 { return this->icont().value_comp().predicate(); } 867 key_comp() const868 BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const 869 { return this->icont().value_comp().predicate().key_comp(); } 870 get_allocator() const871 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const 872 { return allocator_type(this->node_alloc()); } 873 get_stored_allocator() const874 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const 875 { return this->node_alloc(); } 876 get_stored_allocator()877 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() 878 { return this->node_alloc(); } 879 begin()880 BOOST_CONTAINER_FORCEINLINE iterator begin() 881 { return iterator(this->icont().begin()); } 882 begin() const883 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const 884 { return this->cbegin(); } 885 end()886 BOOST_CONTAINER_FORCEINLINE iterator end() 887 { return iterator(this->icont().end()); } 888 end() const889 BOOST_CONTAINER_FORCEINLINE const_iterator end() const 890 { return this->cend(); } 891 rbegin()892 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() 893 { return reverse_iterator(end()); } 894 rbegin() const895 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const 896 { return this->crbegin(); } 897 rend()898 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() 899 { return reverse_iterator(begin()); } 900 rend() const901 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const 902 { return this->crend(); } 903 904 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 905 //! 906 //! <b>Throws</b>: Nothing. 907 //! 908 //! <b>Complexity</b>: Constant. cbegin() const909 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const 910 { return const_iterator(this->non_const_icont().begin()); } 911 912 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 913 //! 914 //! <b>Throws</b>: Nothing. 915 //! 916 //! <b>Complexity</b>: Constant. cend() const917 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const 918 { return const_iterator(this->non_const_icont().end()); } 919 920 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 921 //! of the reversed container. 922 //! 923 //! <b>Throws</b>: Nothing. 924 //! 925 //! <b>Complexity</b>: Constant. crbegin() const926 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const 927 { return const_reverse_iterator(cend()); } 928 929 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 930 //! of the reversed container. 931 //! 932 //! <b>Throws</b>: Nothing. 933 //! 934 //! <b>Complexity</b>: Constant. crend() const935 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const 936 { return const_reverse_iterator(cbegin()); } 937 empty() const938 BOOST_CONTAINER_FORCEINLINE bool empty() const 939 { return !this->size(); } 940 size() const941 BOOST_CONTAINER_FORCEINLINE size_type size() const 942 { return this->icont().size(); } 943 max_size() const944 BOOST_CONTAINER_FORCEINLINE size_type max_size() const 945 { return AllocHolder::max_size(); } 946 swap(ThisType & x)947 BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x) 948 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 949 && boost::container::dtl::is_nothrow_swappable<Compare>::value ) 950 { AllocHolder::swap(x); } 951 952 public: 953 954 typedef typename Icont::insert_commit_data insert_commit_data; 955 956 // insert/erase insert_unique_check(const key_type & key,insert_commit_data & data)957 std::pair<iterator,bool> insert_unique_check 958 (const key_type& key, insert_commit_data &data) 959 { 960 std::pair<iiterator, bool> ret = 961 this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data); 962 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 963 } 964 insert_unique_check(const_iterator hint,const key_type & key,insert_commit_data & data)965 std::pair<iterator,bool> insert_unique_check 966 (const_iterator hint, const key_type& key, insert_commit_data &data) 967 { 968 BOOST_ASSERT((priv_is_linked)(hint)); 969 std::pair<iiterator, bool> ret = 970 this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data); 971 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 972 } 973 974 template<class MovableConvertible> insert_unique_commit(BOOST_FWD_REF (MovableConvertible)v,insert_commit_data & data)975 iterator insert_unique_commit 976 (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) 977 { 978 NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v)); 979 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 980 iterator ret(this->icont().insert_unique_commit(*tmp, data)); 981 destroy_deallocator.release(); 982 return ret; 983 } 984 985 template<class MovableConvertible> insert_unique(BOOST_FWD_REF (MovableConvertible)v)986 std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) v) 987 { 988 insert_commit_data data; 989 std::pair<iterator,bool> ret = 990 this->insert_unique_check(key_of_value_t()(v), data); 991 if(ret.second){ 992 ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); 993 } 994 return ret; 995 } 996 997 private: 998 999 template<class KeyConvertible, class M> priv_insert_or_assign_commit(BOOST_FWD_REF (KeyConvertible)key,BOOST_FWD_REF (M)obj,insert_commit_data & data)1000 iiterator priv_insert_or_assign_commit 1001 (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data) 1002 { 1003 NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj)); 1004 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1005 iiterator ret(this->icont().insert_unique_commit(*tmp, data)); 1006 destroy_deallocator.release(); 1007 return ret; 1008 } 1009 priv_is_linked(const_iterator const position) const1010 bool priv_is_linked(const_iterator const position) const 1011 { 1012 iiterator const cur(position.get()); 1013 return cur == this->icont().end() || 1014 cur == this->icont().root() || 1015 iiterator(cur).go_parent().go_left() == cur || 1016 iiterator(cur).go_parent().go_right() == cur; 1017 } 1018 1019 template<class MovableConvertible> push_back_impl(BOOST_FWD_REF (MovableConvertible)v)1020 void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) 1021 { 1022 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); 1023 //push_back has no-throw guarantee so avoid any deallocator/destroyer 1024 this->icont().push_back(*tmp); 1025 } 1026 emplace_unique_impl(NodePtr p)1027 std::pair<iterator, bool> emplace_unique_impl(NodePtr p) 1028 { 1029 value_type &v = p->get_data(); 1030 insert_commit_data data; 1031 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); 1032 std::pair<iterator,bool> ret = 1033 this->insert_unique_check(key_of_value_t()(v), data); 1034 if(!ret.second){ 1035 return ret; 1036 } 1037 //No throw insertion part, release rollback 1038 destroy_deallocator.release(); 1039 return std::pair<iterator,bool> 1040 ( iterator(this->icont().insert_unique_commit(*p, data)) 1041 , true ); 1042 } 1043 emplace_unique_hint_impl(const_iterator hint,NodePtr p)1044 iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p) 1045 { 1046 BOOST_ASSERT((priv_is_linked)(hint)); 1047 value_type &v = p->get_data(); 1048 insert_commit_data data; 1049 std::pair<iterator,bool> ret = 1050 this->insert_unique_check(hint, key_of_value_t()(v), data); 1051 if(!ret.second){ 1052 Destroyer(this->node_alloc())(p); 1053 return ret.first; 1054 } 1055 return iterator(this->icont().insert_unique_commit(*p, data)); 1056 } 1057 1058 public: 1059 1060 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1061 1062 template <class... Args> emplace_unique(BOOST_FWD_REF (Args)...args)1063 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) 1064 { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } 1065 1066 template <class... Args> emplace_hint_unique(const_iterator hint,BOOST_FWD_REF (Args)...args)1067 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) 1068 { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } 1069 1070 template <class... Args> emplace_equal(BOOST_FWD_REF (Args)...args)1071 iterator emplace_equal(BOOST_FWD_REF(Args)... args) 1072 { 1073 NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); 1074 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1075 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); 1076 destroy_deallocator.release(); 1077 return ret; 1078 } 1079 1080 template <class... Args> emplace_hint_equal(const_iterator hint,BOOST_FWD_REF (Args)...args)1081 iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) 1082 { 1083 BOOST_ASSERT((priv_is_linked)(hint)); 1084 NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); 1085 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1086 iterator ret(this->icont().insert_equal(hint.get(), *tmp)); 1087 destroy_deallocator.release(); 1088 return ret; 1089 } 1090 1091 template <class KeyType, class... Args> try_emplace(const_iterator hint,BOOST_FWD_REF (KeyType)key,BOOST_FWD_REF (Args)...args)1092 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace 1093 (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) 1094 { 1095 insert_commit_data data; 1096 const key_type & k = key; //Support emulated rvalue references 1097 std::pair<iiterator, bool> ret = 1098 hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data) 1099 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); 1100 if(ret.second){ 1101 ret.first = this->icont().insert_unique_commit 1102 (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data); 1103 } 1104 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 1105 } 1106 1107 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1108 1109 #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ 1110 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1111 std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ 1112 { return this->emplace_unique_impl(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ 1113 \ 1114 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1115 iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1116 { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ 1117 \ 1118 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1119 iterator emplace_equal(BOOST_MOVE_UREF##N)\ 1120 {\ 1121 NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 1122 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ 1123 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\ 1124 destroy_deallocator.release();\ 1125 return ret;\ 1126 }\ 1127 \ 1128 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1129 iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1130 {\ 1131 BOOST_ASSERT((priv_is_linked)(hint));\ 1132 NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 1133 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ 1134 iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ 1135 destroy_deallocator.release();\ 1136 return ret;\ 1137 }\ 1138 \ 1139 template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ 1140 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ 1141 try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1142 {\ 1143 insert_commit_data data;\ 1144 const key_type & k = key;\ 1145 std::pair<iiterator, bool> ret =\ 1146 hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\ 1147 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\ 1148 if(ret.second){\ 1149 ret.first = this->icont().insert_unique_commit\ 1150 (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\ 1151 }\ 1152 return std::pair<iterator, bool>(iterator(ret.first), ret.second);\ 1153 }\ 1154 // 1155 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) 1156 #undef BOOST_CONTAINER_TREE_EMPLACE_CODE 1157 1158 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1159 1160 template<class MovableConvertible> insert_unique_convertible(const_iterator hint,BOOST_FWD_REF (MovableConvertible)v)1161 iterator insert_unique_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) 1162 { 1163 BOOST_ASSERT((priv_is_linked)(hint)); 1164 insert_commit_data data; 1165 std::pair<iterator,bool> ret = 1166 this->insert_unique_check(hint, key_of_value_t()(v), data); 1167 if(!ret.second) 1168 return ret.first; 1169 return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); 1170 } 1171 1172 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_convertible, const_iterator, const_iterator) 1173 1174 template <class InputIterator> insert_unique(InputIterator first,InputIterator last)1175 void insert_unique(InputIterator first, InputIterator last) 1176 { 1177 for( ; first != last; ++first) 1178 this->insert_unique(*first); 1179 } 1180 insert_equal(const value_type & v)1181 iterator insert_equal(const value_type& v) 1182 { 1183 NodePtr tmp(AllocHolder::create_node(v)); 1184 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1185 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); 1186 destroy_deallocator.release(); 1187 return ret; 1188 } 1189 1190 template<class MovableConvertible> insert_equal(BOOST_FWD_REF (MovableConvertible)v)1191 iterator insert_equal(BOOST_FWD_REF(MovableConvertible) v) 1192 { 1193 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); 1194 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1195 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); 1196 destroy_deallocator.release(); 1197 return ret; 1198 } 1199 1200 template<class MovableConvertible> insert_equal_convertible(const_iterator hint,BOOST_FWD_REF (MovableConvertible)v)1201 iterator insert_equal_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) 1202 { 1203 BOOST_ASSERT((priv_is_linked)(hint)); 1204 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); 1205 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1206 iterator ret(this->icont().insert_equal(hint.get(), *tmp)); 1207 destroy_deallocator.release(); 1208 return ret; 1209 } 1210 1211 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_equal, value_type, iterator, this->insert_equal_convertible, const_iterator, const_iterator) 1212 1213 template <class InputIterator> insert_equal(InputIterator first,InputIterator last)1214 void insert_equal(InputIterator first, InputIterator last) 1215 { 1216 for( ; first != last; ++first) 1217 this->insert_equal(*first); 1218 } 1219 1220 template<class KeyType, class M> insert_or_assign(const_iterator hint,BOOST_FWD_REF (KeyType)key,BOOST_FWD_REF (M)obj)1221 std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) 1222 { 1223 insert_commit_data data; 1224 const key_type & k = key; //Support emulated rvalue references 1225 std::pair<iiterator, bool> ret = 1226 hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data) 1227 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); 1228 if(ret.second){ 1229 ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data); 1230 } 1231 else{ 1232 ret.first->get_data().second = boost::forward<M>(obj); 1233 } 1234 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 1235 } 1236 erase(const_iterator position)1237 iterator erase(const_iterator position) 1238 { 1239 BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); 1240 return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); 1241 } 1242 erase(const key_type & k)1243 BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k) 1244 { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); } 1245 erase(const_iterator first,const_iterator last)1246 iterator erase(const_iterator first, const_iterator last) 1247 { 1248 BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); 1249 BOOST_ASSERT(first == last || (priv_is_linked)(last)); 1250 return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); 1251 } 1252 extract(const key_type & k)1253 node_type extract(const key_type& k) 1254 { 1255 iterator const it = this->find(k); 1256 if(this->end() != it){ 1257 return this->extract(it); 1258 } 1259 return node_type(); 1260 } 1261 extract(const_iterator position)1262 node_type extract(const_iterator position) 1263 { 1264 BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); 1265 iiterator const iit(position.get()); 1266 this->icont().erase(iit); 1267 return node_type(iit.operator->(), this->node_alloc()); 1268 } 1269 insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1270 insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1271 { 1272 return this->insert_unique_node(this->end(), boost::move(nh)); 1273 } 1274 insert_unique_node(const_iterator hint,BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1275 insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1276 { 1277 insert_return_type irt; //inserted == false, node.empty() 1278 if(!nh.empty()){ 1279 insert_commit_data data; 1280 std::pair<iterator,bool> ret = 1281 this->insert_unique_check(hint, key_of_value_t()(nh.value()), data); 1282 if(ret.second){ 1283 irt.inserted = true; 1284 irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data)); 1285 nh.release(); 1286 } 1287 else{ 1288 irt.position = ret.first; 1289 irt.node = boost::move(nh); 1290 } 1291 } 1292 else{ 1293 irt.position = this->end(); 1294 } 1295 return BOOST_MOVE_RET(insert_return_type, irt); 1296 } 1297 insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1298 iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1299 { 1300 if(nh.empty()){ 1301 return this->end(); 1302 } 1303 else{ 1304 NodePtr const p(nh.release()); 1305 return iterator(this->icont().insert_equal(*p)); 1306 } 1307 } 1308 insert_equal_node(const_iterator hint,BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1309 iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1310 { 1311 if(nh.empty()){ 1312 return this->end(); 1313 } 1314 else{ 1315 NodePtr const p(nh.release()); 1316 return iterator(this->icont().insert_equal(hint.get(), *p)); 1317 } 1318 } 1319 1320 template<class C2> merge_unique(tree<T,KeyOfValue,C2,Allocator,Options> & source)1321 BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source) 1322 { return this->icont().merge_unique(source.icont()); } 1323 1324 template<class C2> merge_equal(tree<T,KeyOfValue,C2,Allocator,Options> & source)1325 BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source) 1326 { return this->icont().merge_equal(source.icont()); } clear()1327 BOOST_CONTAINER_FORCEINLINE void clear() 1328 { AllocHolder::clear(alloc_version()); } 1329 1330 // search operations. Const and non-const overloads even if no iterator is returned 1331 // so splay implementations can to their rebalancing when searching in non-const versions find(const key_type & k)1332 BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& k) 1333 { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } 1334 find(const key_type & k) const1335 BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& k) const 1336 { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } 1337 1338 template <class K> 1339 BOOST_CONTAINER_FORCEINLINE 1340 typename dtl::enable_if_transparent<key_compare, K, iterator>::type find(const K & k)1341 find(const K& k) 1342 { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } 1343 1344 template <class K> 1345 BOOST_CONTAINER_FORCEINLINE 1346 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type find(const K & k) const1347 find(const K& k) const 1348 { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } 1349 count(const key_type & k) const1350 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& k) const 1351 { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } 1352 1353 template <class K> 1354 BOOST_CONTAINER_FORCEINLINE 1355 typename dtl::enable_if_transparent<key_compare, K, size_type>::type count(const K & k) const1356 count(const K& k) const 1357 { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } 1358 contains(const key_type & x) const1359 BOOST_CONTAINER_FORCEINLINE bool contains(const key_type& x) const 1360 { return this->find(x) != this->cend(); } 1361 1362 template<typename K> 1363 BOOST_CONTAINER_FORCEINLINE 1364 typename dtl::enable_if_transparent<key_compare, K, bool>::type contains(const K & x) const1365 contains(const K& x) const 1366 { return this->find(x) != this->cend(); } 1367 lower_bound(const key_type & k)1368 BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& k) 1369 { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1370 lower_bound(const key_type & k) const1371 BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& k) const 1372 { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1373 1374 template <class K> 1375 BOOST_CONTAINER_FORCEINLINE 1376 typename dtl::enable_if_transparent<key_compare, K, iterator>::type lower_bound(const K & k)1377 lower_bound(const K& k) 1378 { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1379 1380 template <class K> 1381 BOOST_CONTAINER_FORCEINLINE 1382 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type lower_bound(const K & k) const1383 lower_bound(const K& k) const 1384 { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1385 upper_bound(const key_type & k)1386 BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& k) 1387 { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1388 upper_bound(const key_type & k) const1389 BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& k) const 1390 { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1391 1392 template <class K> 1393 BOOST_CONTAINER_FORCEINLINE 1394 typename dtl::enable_if_transparent<key_compare, K, iterator>::type upper_bound(const K & k)1395 upper_bound(const K& k) 1396 { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1397 1398 template <class K> 1399 BOOST_CONTAINER_FORCEINLINE 1400 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type upper_bound(const K & k) const1401 upper_bound(const K& k) const 1402 { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1403 equal_range(const key_type & k)1404 std::pair<iterator,iterator> equal_range(const key_type& k) 1405 { 1406 std::pair<iiterator, iiterator> ret = 1407 this->icont().equal_range(k, KeyNodeCompare(key_comp())); 1408 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1409 } 1410 equal_range(const key_type & k) const1411 std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const 1412 { 1413 std::pair<iiterator, iiterator> ret = 1414 this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); 1415 return std::pair<const_iterator,const_iterator> 1416 (const_iterator(ret.first), const_iterator(ret.second)); 1417 } 1418 1419 template <class K> 1420 BOOST_CONTAINER_FORCEINLINE 1421 typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type equal_range(const K & k)1422 equal_range(const K& k) 1423 { 1424 std::pair<iiterator, iiterator> ret = 1425 this->icont().equal_range(k, KeyNodeCompare(key_comp())); 1426 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1427 } 1428 1429 template <class K> 1430 BOOST_CONTAINER_FORCEINLINE 1431 typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type equal_range(const K & k) const1432 equal_range(const K& k) const 1433 { 1434 std::pair<iiterator, iiterator> ret = 1435 this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); 1436 return std::pair<const_iterator,const_iterator> 1437 (const_iterator(ret.first), const_iterator(ret.second)); 1438 } 1439 lower_bound_range(const key_type & k)1440 std::pair<iterator,iterator> lower_bound_range(const key_type& k) 1441 { 1442 std::pair<iiterator, iiterator> ret = 1443 this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1444 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1445 } 1446 lower_bound_range(const key_type & k) const1447 std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const 1448 { 1449 std::pair<iiterator, iiterator> ret = 1450 this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1451 return std::pair<const_iterator,const_iterator> 1452 (const_iterator(ret.first), const_iterator(ret.second)); 1453 } 1454 1455 template <class K> 1456 BOOST_CONTAINER_FORCEINLINE 1457 typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type lower_bound_range(const K & k)1458 lower_bound_range(const K& k) 1459 { 1460 std::pair<iiterator, iiterator> ret = 1461 this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1462 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1463 } 1464 1465 template <class K> 1466 BOOST_CONTAINER_FORCEINLINE 1467 typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type lower_bound_range(const K & k) const1468 lower_bound_range(const K& k) const 1469 { 1470 std::pair<iiterator, iiterator> ret = 1471 this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1472 return std::pair<const_iterator,const_iterator> 1473 (const_iterator(ret.first), const_iterator(ret.second)); 1474 } 1475 rebalance()1476 BOOST_CONTAINER_FORCEINLINE void rebalance() 1477 { intrusive_tree_proxy_t::rebalance(this->icont()); } 1478 operator ==(const tree & x,const tree & y)1479 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const tree& x, const tree& y) 1480 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1481 operator <(const tree & x,const tree & y)1482 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const tree& x, const tree& y) 1483 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1484 operator !=(const tree & x,const tree & y)1485 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const tree& x, const tree& y) 1486 { return !(x == y); } 1487 operator >(const tree & x,const tree & y)1488 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const tree& x, const tree& y) 1489 { return y < x; } 1490 operator <=(const tree & x,const tree & y)1491 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const tree& x, const tree& y) 1492 { return !(y < x); } 1493 operator >=(const tree & x,const tree & y)1494 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const tree& x, const tree& y) 1495 { return !(x < y); } 1496 swap(tree & x,tree & y)1497 BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y) 1498 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1499 && boost::container::dtl::is_nothrow_swappable<Compare>::value ) 1500 { x.swap(y); } 1501 }; 1502 1503 } //namespace dtl { 1504 } //namespace container { 1505 1506 template <class T> 1507 struct has_trivial_destructor_after_move; 1508 1509 //!has_trivial_destructor_after_move<> == true_type 1510 //!specialization for optimizations 1511 template <class T, class KeyOfValue, class Compare, class Allocator, class Options> 1512 struct has_trivial_destructor_after_move 1513 < 1514 ::boost::container::dtl::tree 1515 <T, KeyOfValue, Compare, Allocator, Options> 1516 > 1517 { 1518 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; 1519 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && 1520 ::boost::has_trivial_destructor_after_move<pointer>::value && 1521 ::boost::has_trivial_destructor_after_move<Compare>::value; 1522 }; 1523 1524 } //namespace boost { 1525 1526 #include <boost/container/detail/config_end.hpp> 1527 1528 #endif //BOOST_CONTAINER_TREE_HPP 1529