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,node_t & other,bool_<true>)390 BOOST_CONTAINER_FORCEINLINE static void do_assign(node_ptr_type &p, node_t &other, bool_<true>) 391 { p->do_move_assign(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 ()(typename dtl::if_c<DoMove,node_t &,const node_t &>::type other) const396 node_ptr_type operator() 397 (typename dtl::if_c<DoMove, node_t &, const node_t&>::type other) const 398 { 399 if(node_ptr_type p = m_icont.unlink_leftmost_without_rebalance()){ 400 //First recycle a node (this can't throw) 401 BOOST_TRY{ 402 //This can throw 403 this->do_assign(p, other, bool_<DoMove>()); 404 return p; 405 } 406 BOOST_CATCH(...){ 407 //If there is an exception destroy the whole source 408 m_holder.destroy_node(p); 409 while((p = m_icont.unlink_leftmost_without_rebalance())){ 410 m_holder.destroy_node(p); 411 } 412 BOOST_RETHROW 413 } 414 BOOST_CATCH_END 415 } 416 else{ 417 return m_holder.create_node(boost::move(other.get_real_data())); 418 } 419 } 420 421 AllocHolder &m_holder; 422 intrusive_container &m_icont; 423 }; 424 425 426 template<class KeyCompare, class KeyOfValue> 427 struct key_node_compare 428 : public boost::intrusive::detail::ebo_functor_holder<KeyCompare> 429 { key_node_compareboost::container::dtl::key_node_compare430 BOOST_CONTAINER_FORCEINLINE explicit key_node_compare(const KeyCompare &comp) 431 : base_t(comp) 432 {} 433 434 typedef boost::intrusive::detail::ebo_functor_holder<KeyCompare> base_t; 435 typedef KeyCompare key_compare; 436 typedef KeyOfValue key_of_value; 437 typedef typename KeyOfValue::type key_type; 438 439 440 template <class T, class VoidPointer, boost::container::tree_type_enum tree_type_value, bool OptimizeSize> 441 BOOST_CONTAINER_FORCEINLINE static const key_type & key_fromboost::container::dtl::key_node_compare442 key_from(const tree_node<T, VoidPointer, tree_type_value, OptimizeSize> &n) 443 { 444 return key_of_value()(n.get_data()); 445 } 446 447 template <class T> 448 BOOST_CONTAINER_FORCEINLINE static const T & key_fromboost::container::dtl::key_node_compare449 key_from(const T &t) 450 { 451 return t; 452 } 453 key_compboost::container::dtl::key_node_compare454 BOOST_CONTAINER_FORCEINLINE const key_compare &key_comp() const 455 { return static_cast<const key_compare &>(*this); } 456 key_compboost::container::dtl::key_node_compare457 BOOST_CONTAINER_FORCEINLINE key_compare &key_comp() 458 { return static_cast<key_compare &>(*this); } 459 operator ()boost::container::dtl::key_node_compare460 BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const key_type &key2) const 461 { return this->key_comp()(key1, key2); } 462 463 template<class U> operator ()boost::container::dtl::key_node_compare464 BOOST_CONTAINER_FORCEINLINE bool operator()(const key_type &key1, const U &nonkey2) const 465 { return this->key_comp()(key1, this->key_from(nonkey2)); } 466 467 template<class U> operator ()boost::container::dtl::key_node_compare468 BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const key_type &key2) const 469 { return this->key_comp()(this->key_from(nonkey1), key2); } 470 471 template<class U, class V> operator ()boost::container::dtl::key_node_compare472 BOOST_CONTAINER_FORCEINLINE bool operator()(const U &nonkey1, const V &nonkey2) const 473 { return this->key_comp()(this->key_from(nonkey1), this->key_from(nonkey2)); } 474 }; 475 476 template<class Options> 477 struct get_tree_opt 478 { 479 typedef Options type; 480 }; 481 482 template<> 483 struct get_tree_opt<void> 484 { 485 typedef tree_assoc_defaults type; 486 }; 487 488 template<class, class KeyOfValue> 489 struct real_key_of_value 490 { 491 typedef KeyOfValue type; 492 }; 493 494 template<class T> 495 struct real_key_of_value<T, void> 496 { 497 typedef dtl::identity<T> type; 498 }; 499 500 template<class T1, class T2> 501 struct real_key_of_value<std::pair<T1, T2>, int> 502 { 503 typedef dtl::select1st<T1> type; 504 }; 505 506 template<class T1, class T2> 507 struct real_key_of_value<boost::container::pair<T1, T2>, int> 508 { 509 typedef dtl::select1st<T1> type; 510 }; 511 512 template <class T, class KeyOfValue, class Compare, class Allocator, class Options> 513 class tree 514 : public dtl::node_alloc_holder 515 < typename real_allocator<T, Allocator>::type 516 , typename dtl::intrusive_tree_type 517 < typename real_allocator<T, Allocator>::type 518 , tree_value_compare 519 <typename allocator_traits<typename real_allocator<T, Allocator>::type>::pointer, Compare, typename real_key_of_value<T, KeyOfValue>::type> 520 , get_tree_opt<Options>::type::tree_type 521 , get_tree_opt<Options>::type::optimize_size 522 >::type 523 > 524 { 525 typedef tree < T, KeyOfValue 526 , Compare, Allocator, Options> ThisType; 527 public: 528 typedef typename real_allocator<T, Allocator>::type allocator_type; 529 530 private: 531 typedef allocator_traits<allocator_type> allocator_traits_t; 532 typedef typename real_key_of_value<T, KeyOfValue>::type key_of_value_t; 533 typedef tree_value_compare 534 < typename allocator_traits_t::pointer 535 , Compare 536 , key_of_value_t> ValComp; 537 typedef typename get_tree_opt<Options>::type options_type; 538 typedef typename dtl::intrusive_tree_type 539 < allocator_type, ValComp 540 , options_type::tree_type 541 , options_type::optimize_size 542 >::type Icont; 543 typedef dtl::node_alloc_holder 544 <allocator_type, Icont> AllocHolder; 545 typedef typename AllocHolder::NodePtr NodePtr; 546 547 typedef typename AllocHolder::NodeAlloc NodeAlloc; 548 typedef boost::container:: 549 allocator_traits<NodeAlloc> allocator_traits_type; 550 typedef typename AllocHolder::ValAlloc ValAlloc; 551 typedef typename AllocHolder::Node Node; 552 typedef typename Icont::iterator iiterator; 553 typedef typename Icont::const_iterator iconst_iterator; 554 typedef dtl::allocator_destroyer<NodeAlloc> Destroyer; 555 typedef typename AllocHolder::alloc_version alloc_version; 556 typedef intrusive_tree_proxy<options_type::tree_type> intrusive_tree_proxy_t; 557 558 BOOST_COPYABLE_AND_MOVABLE(tree) 559 560 public: 561 562 typedef typename key_of_value_t::type key_type; 563 typedef T value_type; 564 typedef Compare key_compare; 565 typedef ValComp value_compare; 566 typedef typename boost::container:: 567 allocator_traits<allocator_type>::pointer pointer; 568 typedef typename boost::container:: 569 allocator_traits<allocator_type>::const_pointer const_pointer; 570 typedef typename boost::container:: 571 allocator_traits<allocator_type>::reference reference; 572 typedef typename boost::container:: 573 allocator_traits<allocator_type>::const_reference const_reference; 574 typedef typename boost::container:: 575 allocator_traits<allocator_type>::size_type size_type; 576 typedef typename boost::container:: 577 allocator_traits<allocator_type>::difference_type difference_type; 578 typedef dtl::iterator_from_iiterator 579 <iiterator, false> iterator; 580 typedef dtl::iterator_from_iiterator 581 <iiterator, true > const_iterator; 582 typedef boost::container::reverse_iterator 583 <iterator> reverse_iterator; 584 typedef boost::container::reverse_iterator 585 <const_iterator> const_reverse_iterator; 586 typedef node_handle 587 < NodeAlloc, void> node_type; 588 typedef insert_return_type_base 589 <iterator, node_type> insert_return_type; 590 591 typedef NodeAlloc stored_allocator_type; 592 593 private: 594 595 typedef key_node_compare<key_compare, key_of_value_t> KeyNodeCompare; 596 597 public: 598 tree()599 BOOST_CONTAINER_FORCEINLINE tree() 600 : AllocHolder() 601 {} 602 tree(const key_compare & comp)603 BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp) 604 : AllocHolder(ValComp(comp)) 605 {} 606 tree(const key_compare & comp,const allocator_type & a)607 BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a) 608 : AllocHolder(ValComp(comp), a) 609 {} 610 tree(const allocator_type & a)611 BOOST_CONTAINER_FORCEINLINE explicit tree(const allocator_type& a) 612 : AllocHolder(a) 613 {} 614 615 template <class InputIterator> tree(bool unique_insertion,InputIterator first,InputIterator last)616 tree(bool unique_insertion, InputIterator first, InputIterator last) 617 : AllocHolder(value_compare(key_compare())) 618 { 619 this->tree_construct(unique_insertion, first, last); 620 //AllocHolder clears in case of exception 621 } 622 623 template <class InputIterator> tree(bool unique_insertion,InputIterator first,InputIterator last,const key_compare & comp)624 tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp) 625 : AllocHolder(value_compare(comp)) 626 { 627 this->tree_construct(unique_insertion, first, last); 628 //AllocHolder clears in case of exception 629 } 630 631 template <class InputIterator> tree(bool unique_insertion,InputIterator first,InputIterator last,const key_compare & comp,const allocator_type & a)632 tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a) 633 : AllocHolder(value_compare(comp), a) 634 { 635 this->tree_construct(unique_insertion, first, last); 636 //AllocHolder clears in case of exception 637 } 638 639 //construct with ordered range 640 template <class InputIterator> tree(ordered_range_t,InputIterator first,InputIterator last)641 tree( ordered_range_t, InputIterator first, InputIterator last) 642 : AllocHolder(value_compare(key_compare())) 643 { 644 this->tree_construct(ordered_range_t(), first, last); 645 } 646 647 template <class InputIterator> tree(ordered_range_t,InputIterator first,InputIterator last,const key_compare & comp)648 tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp) 649 : AllocHolder(value_compare(comp)) 650 { 651 this->tree_construct(ordered_range_t(), first, last); 652 } 653 654 template <class InputIterator> tree(ordered_range_t,InputIterator first,InputIterator last,const key_compare & comp,const allocator_type & a)655 tree( ordered_range_t, InputIterator first, InputIterator last 656 , const key_compare& comp, const allocator_type& a) 657 : AllocHolder(value_compare(comp), a) 658 { 659 this->tree_construct(ordered_range_t(), first, last); 660 } 661 662 private: 663 664 template <class InputIterator> tree_construct(bool unique_insertion,InputIterator first,InputIterator last)665 void tree_construct(bool unique_insertion, InputIterator first, InputIterator last) 666 { 667 //Use cend() as hint to achieve linear time for 668 //ordered ranges as required by the standard 669 //for the constructor 670 if(unique_insertion){ 671 const const_iterator end_it(this->cend()); 672 for ( ; first != last; ++first){ 673 this->insert_unique_hint_convertible(end_it, *first); 674 } 675 } 676 else{ 677 this->tree_construct_non_unique(first, last); 678 } 679 } 680 681 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)682 void tree_construct_non_unique(InputIterator first, InputIterator last 683 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 684 , typename dtl::enable_if_or 685 < void 686 , dtl::is_same<alloc_version, version_1> 687 , dtl::is_input_iterator<InputIterator> 688 >::type * = 0 689 #endif 690 ) 691 { 692 //Use cend() as hint to achieve linear time for 693 //ordered ranges as required by the standard 694 //for the constructor 695 const const_iterator end_it(this->cend()); 696 for ( ; first != last; ++first){ 697 this->insert_equal_hint_convertible(end_it, *first); 698 } 699 } 700 701 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)702 void tree_construct_non_unique(InputIterator first, InputIterator last 703 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 704 , typename dtl::disable_if_or 705 < void 706 , dtl::is_same<alloc_version, version_1> 707 , dtl::is_input_iterator<InputIterator> 708 >::type * = 0 709 #endif 710 ) 711 { 712 //Optimized allocation and construction 713 this->allocate_many_and_construct 714 ( first, boost::container::iterator_udistance(first, last) 715 , insert_equal_end_hint_functor<Node, Icont>(this->icont())); 716 } 717 718 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)719 void tree_construct( ordered_range_t, InputIterator first, InputIterator last 720 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 721 , typename dtl::disable_if_or 722 < void 723 , dtl::is_same<alloc_version, version_1> 724 , dtl::is_input_iterator<InputIterator> 725 >::type * = 0 726 #endif 727 ) 728 { 729 //Optimized allocation and construction 730 this->allocate_many_and_construct 731 ( first, boost::container::iterator_udistance(first, last) 732 , dtl::push_back_functor<Node, Icont>(this->icont())); 733 //AllocHolder clears in case of exception 734 } 735 736 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)737 void tree_construct( ordered_range_t, InputIterator first, InputIterator last 738 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 739 , typename dtl::enable_if_or 740 < void 741 , dtl::is_same<alloc_version, version_1> 742 , dtl::is_input_iterator<InputIterator> 743 >::type * = 0 744 #endif 745 ) 746 { 747 for ( ; first != last; ++first){ 748 this->push_back_impl(*first); 749 } 750 } 751 752 public: 753 tree(const tree & x)754 BOOST_CONTAINER_FORCEINLINE tree(const tree& x) 755 : AllocHolder(x, x.value_comp()) 756 { 757 this->icont().clone_from 758 (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); 759 } 760 tree(BOOST_RV_REF (tree)x)761 BOOST_CONTAINER_FORCEINLINE tree(BOOST_RV_REF(tree) x) 762 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value) 763 : AllocHolder(BOOST_MOVE_BASE(AllocHolder, x), x.value_comp()) 764 {} 765 tree(const tree & x,const allocator_type & a)766 BOOST_CONTAINER_FORCEINLINE tree(const tree& x, const allocator_type &a) 767 : AllocHolder(x.value_comp(), a) 768 { 769 this->icont().clone_from 770 (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); 771 //AllocHolder clears in case of exception 772 } 773 tree(BOOST_RV_REF (tree)x,const allocator_type & a)774 tree(BOOST_RV_REF(tree) x, const allocator_type &a) 775 : AllocHolder(x.value_comp(), a) 776 { 777 if(this->node_alloc() == x.node_alloc()){ 778 this->icont().swap(x.icont()); 779 } 780 else{ 781 this->icont().clone_from 782 (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc())); 783 } 784 //AllocHolder clears in case of exception 785 } 786 ~tree()787 BOOST_CONTAINER_FORCEINLINE ~tree() 788 {} //AllocHolder clears the tree 789 operator =(BOOST_COPY_ASSIGN_REF (tree)x)790 tree& operator=(BOOST_COPY_ASSIGN_REF(tree) x) 791 { 792 if (BOOST_LIKELY(this != &x)) { 793 NodeAlloc &this_alloc = this->get_stored_allocator(); 794 const NodeAlloc &x_alloc = x.get_stored_allocator(); 795 dtl::bool_<allocator_traits<NodeAlloc>:: 796 propagate_on_container_copy_assignment::value> flag; 797 if(flag && this_alloc != x_alloc){ 798 this->clear(); 799 } 800 this->AllocHolder::copy_assign_alloc(x); 801 //Transfer all the nodes to a temporary tree 802 //If anything goes wrong, all the nodes will be destroyed 803 //automatically 804 Icont other_tree(::boost::move(this->icont())); 805 806 //Now recreate the source tree reusing nodes stored by other_tree 807 this->icont().clone_from 808 (x.icont() 809 , RecyclingCloner<AllocHolder, false>(*this, other_tree) 810 , Destroyer(this->node_alloc())); 811 812 //If there are remaining nodes, destroy them 813 NodePtr p; 814 while((p = other_tree.unlink_leftmost_without_rebalance())){ 815 AllocHolder::destroy_node(p); 816 } 817 } 818 return *this; 819 } 820 operator =(BOOST_RV_REF (tree)x)821 tree& operator=(BOOST_RV_REF(tree) x) 822 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value || 823 allocator_traits_type::is_always_equal::value) && 824 boost::container::dtl::is_nothrow_move_assignable<Compare>::value) 825 { 826 if (BOOST_LIKELY(this != &x)) { 827 NodeAlloc &this_alloc = this->node_alloc(); 828 NodeAlloc &x_alloc = x.node_alloc(); 829 const bool propagate_alloc = allocator_traits<NodeAlloc>:: 830 propagate_on_container_move_assignment::value; 831 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; 832 //Resources can be transferred if both allocators are 833 //going to be equal after this function (either propagated or already equal) 834 if(propagate_alloc || allocators_equal){ 835 //Destroy 836 this->clear(); 837 //Move allocator if needed 838 this->AllocHolder::move_assign_alloc(x); 839 //Obtain resources 840 this->icont() = boost::move(x.icont()); 841 } 842 //Else do a one by one move 843 else{ 844 //Transfer all the nodes to a temporary tree 845 //If anything goes wrong, all the nodes will be destroyed 846 //automatically 847 Icont other_tree(::boost::move(this->icont())); 848 849 //Now recreate the source tree reusing nodes stored by other_tree 850 this->icont().clone_from 851 (::boost::move(x.icont()) 852 , RecyclingCloner<AllocHolder, true>(*this, other_tree) 853 , Destroyer(this->node_alloc())); 854 855 //If there are remaining nodes, destroy them 856 NodePtr p; 857 while((p = other_tree.unlink_leftmost_without_rebalance())){ 858 AllocHolder::destroy_node(p); 859 } 860 } 861 } 862 return *this; 863 } 864 865 public: 866 // accessors: 867 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE value_comp() const868 value_compare value_comp() const 869 { return this->icont().value_comp().predicate(); } 870 871 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE key_comp() const872 key_compare key_comp() const 873 { return this->icont().value_comp().predicate().key_comp(); } 874 875 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE get_allocator() const876 allocator_type get_allocator() const 877 { return allocator_type(this->node_alloc()); } 878 879 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE get_stored_allocator() const880 const stored_allocator_type &get_stored_allocator() const 881 { return this->node_alloc(); } 882 883 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE get_stored_allocator()884 stored_allocator_type &get_stored_allocator() 885 { return this->node_alloc(); } 886 887 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE begin()888 iterator begin() 889 { return iterator(this->icont().begin()); } 890 891 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE begin() const892 const_iterator begin() const 893 { return this->cbegin(); } 894 895 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE end()896 iterator end() 897 { return iterator(this->icont().end()); } 898 899 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE end() const900 const_iterator end() const 901 { return this->cend(); } 902 903 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rbegin()904 reverse_iterator rbegin() 905 { return reverse_iterator(end()); } 906 907 908 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rbegin() const909 const_reverse_iterator rbegin() const 910 { return this->crbegin(); } 911 912 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rend()913 reverse_iterator rend() 914 { return reverse_iterator(begin()); } 915 916 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE rend() const917 const_reverse_iterator rend() const 918 { return this->crend(); } 919 920 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. 921 //! 922 //! <b>Throws</b>: Nothing. 923 //! 924 //! <b>Complexity</b>: Constant. 925 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE cbegin() const926 const_iterator cbegin() const 927 { return const_iterator(this->non_const_icont().begin()); } 928 929 //! <b>Effects</b>: Returns a const_iterator to the end of the container. 930 //! 931 //! <b>Throws</b>: Nothing. 932 //! 933 //! <b>Complexity</b>: Constant. 934 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE cend() const935 const_iterator cend() const 936 { return const_iterator(this->non_const_icont().end()); } 937 938 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 939 //! of the reversed container. 940 //! 941 //! <b>Throws</b>: Nothing. 942 //! 943 //! <b>Complexity</b>: Constant. 944 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE crbegin() const945 const_reverse_iterator crbegin() const 946 { return const_reverse_iterator(cend()); } 947 948 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 949 //! of the reversed container. 950 //! 951 //! <b>Throws</b>: Nothing. 952 //! 953 //! <b>Complexity</b>: Constant. 954 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE crend() const955 const_reverse_iterator crend() const 956 { return const_reverse_iterator(cbegin()); } 957 958 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE empty() const959 bool empty() const 960 { return !this->size(); } 961 962 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE size() const963 size_type size() const 964 { return this->icont().size(); } 965 966 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE max_size() const967 size_type max_size() const 968 { return AllocHolder::max_size(); } 969 swap(ThisType & x)970 BOOST_CONTAINER_FORCEINLINE void swap(ThisType& x) 971 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 972 && boost::container::dtl::is_nothrow_swappable<Compare>::value ) 973 { AllocHolder::swap(x); } 974 975 public: 976 977 typedef typename Icont::insert_commit_data insert_commit_data; 978 979 // insert/erase insert_unique_check(const key_type & key,insert_commit_data & data)980 std::pair<iterator,bool> insert_unique_check 981 (const key_type& key, insert_commit_data &data) 982 { 983 std::pair<iiterator, bool> ret = 984 this->icont().insert_unique_check(key, KeyNodeCompare(key_comp()), data); 985 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 986 } 987 insert_unique_check(const_iterator hint,const key_type & key,insert_commit_data & data)988 std::pair<iterator,bool> insert_unique_check 989 (const_iterator hint, const key_type& key, insert_commit_data &data) 990 { 991 BOOST_ASSERT((priv_is_linked)(hint)); 992 std::pair<iiterator, bool> ret = 993 this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(key_comp()), data); 994 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 995 } 996 997 template<class MovableConvertible> insert_unique_commit(BOOST_FWD_REF (MovableConvertible)v,insert_commit_data & data)998 iterator insert_unique_commit 999 (BOOST_FWD_REF(MovableConvertible) v, insert_commit_data &data) 1000 { 1001 NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(v)); 1002 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1003 iterator ret(this->icont().insert_unique_commit(*tmp, data)); 1004 destroy_deallocator.release(); 1005 return ret; 1006 } 1007 1008 template<class MovableConvertible> insert_unique_convertible(BOOST_FWD_REF (MovableConvertible)v)1009 std::pair<iterator,bool> insert_unique_convertible(BOOST_FWD_REF(MovableConvertible) v) 1010 { 1011 insert_commit_data data; 1012 std::pair<iterator,bool> ret = 1013 this->insert_unique_check(key_of_value_t()(v), data); 1014 if(ret.second){ 1015 ret.first = this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); 1016 } 1017 return ret; 1018 } 1019 1020 template<class MovableConvertible> insert_unique_hint_convertible(const_iterator hint,BOOST_FWD_REF (MovableConvertible)v)1021 iterator insert_unique_hint_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) 1022 { 1023 BOOST_ASSERT((priv_is_linked)(hint)); 1024 insert_commit_data data; 1025 std::pair<iterator,bool> ret = 1026 this->insert_unique_check(hint, key_of_value_t()(v), data); 1027 if(!ret.second) 1028 return ret.first; 1029 return this->insert_unique_commit(boost::forward<MovableConvertible>(v), data); 1030 } 1031 1032 1033 private: 1034 1035 template<class KeyConvertible, class M> priv_insert_or_assign_commit(BOOST_FWD_REF (KeyConvertible)key,BOOST_FWD_REF (M)obj,insert_commit_data & data)1036 iiterator priv_insert_or_assign_commit 1037 (BOOST_FWD_REF(KeyConvertible) key, BOOST_FWD_REF(M) obj, insert_commit_data &data) 1038 { 1039 NodePtr tmp = AllocHolder::create_node(boost::forward<KeyConvertible>(key), boost::forward<M>(obj)); 1040 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1041 iiterator ret(this->icont().insert_unique_commit(*tmp, data)); 1042 destroy_deallocator.release(); 1043 return ret; 1044 } 1045 priv_is_linked(const_iterator const position) const1046 bool priv_is_linked(const_iterator const position) const 1047 { 1048 iiterator const cur(position.get()); 1049 return cur == this->icont().end() || 1050 cur == this->icont().root() || 1051 iiterator(cur).go_parent().go_left() == cur || 1052 iiterator(cur).go_parent().go_right() == cur; 1053 } 1054 1055 template<class MovableConvertible> push_back_impl(BOOST_FWD_REF (MovableConvertible)v)1056 void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) 1057 { 1058 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); 1059 //push_back has no-throw guarantee so avoid any deallocator/destroyer 1060 this->icont().push_back(*tmp); 1061 } 1062 emplace_unique_node(NodePtr p)1063 std::pair<iterator, bool> emplace_unique_node(NodePtr p) 1064 { 1065 value_type &v = p->get_data(); 1066 insert_commit_data data; 1067 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(p, this->node_alloc()); 1068 std::pair<iterator,bool> ret = 1069 this->insert_unique_check(key_of_value_t()(v), data); 1070 if(!ret.second){ 1071 return ret; 1072 } 1073 //No throw insertion part, release rollback 1074 destroy_deallocator.release(); 1075 return std::pair<iterator,bool> 1076 ( iterator(this->icont().insert_unique_commit(*p, data)) 1077 , true ); 1078 } 1079 emplace_hint_unique_node(const_iterator hint,NodePtr p)1080 iterator emplace_hint_unique_node(const_iterator hint, NodePtr p) 1081 { 1082 BOOST_ASSERT((priv_is_linked)(hint)); 1083 value_type &v = p->get_data(); 1084 insert_commit_data data; 1085 std::pair<iterator,bool> ret = 1086 this->insert_unique_check(hint, key_of_value_t()(v), data); 1087 if(!ret.second){ 1088 //Destroy unneeded node 1089 Destroyer(this->node_alloc())(p); 1090 return ret.first; 1091 } 1092 return iterator(this->icont().insert_unique_commit(*p, data)); 1093 } 1094 1095 public: 1096 1097 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1098 1099 template <class... Args> emplace_unique(BOOST_FWD_REF (Args)...args)1100 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> emplace_unique(BOOST_FWD_REF(Args)... args) 1101 { return this->emplace_unique_node(AllocHolder::create_node(boost::forward<Args>(args)...)); } 1102 1103 template <class... Args> emplace_hint_unique(const_iterator hint,BOOST_FWD_REF (Args)...args)1104 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) 1105 { return this->emplace_hint_unique_node(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } 1106 1107 template <class... Args> emplace_equal(BOOST_FWD_REF (Args)...args)1108 iterator emplace_equal(BOOST_FWD_REF(Args)... args) 1109 { 1110 NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); 1111 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1112 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); 1113 destroy_deallocator.release(); 1114 return ret; 1115 } 1116 1117 template <class... Args> emplace_hint_equal(const_iterator hint,BOOST_FWD_REF (Args)...args)1118 iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) 1119 { 1120 BOOST_ASSERT((priv_is_linked)(hint)); 1121 NodePtr tmp(AllocHolder::create_node(boost::forward<Args>(args)...)); 1122 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1123 iterator ret(this->icont().insert_equal(hint.get(), *tmp)); 1124 destroy_deallocator.release(); 1125 return ret; 1126 } 1127 1128 template <class KeyType, class... Args> try_emplace(const_iterator hint,BOOST_FWD_REF (KeyType)key,BOOST_FWD_REF (Args)...args)1129 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace 1130 (const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(Args)... args) 1131 { 1132 insert_commit_data data; 1133 const key_type & k = key; //Support emulated rvalue references 1134 std::pair<iiterator, bool> ret = 1135 hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data) 1136 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); 1137 if(ret.second){ 1138 ret.first = this->icont().insert_unique_commit 1139 (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key), boost::forward<Args>(args)...), data); 1140 } 1141 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 1142 } 1143 1144 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1145 1146 #define BOOST_CONTAINER_TREE_EMPLACE_CODE(N) \ 1147 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1148 std::pair<iterator, bool> emplace_unique(BOOST_MOVE_UREF##N)\ 1149 { return this->emplace_unique_node(AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ 1150 \ 1151 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1152 iterator emplace_hint_unique(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1153 { return this->emplace_hint_unique_node(hint, AllocHolder::create_node(BOOST_MOVE_FWD##N)); }\ 1154 \ 1155 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1156 iterator emplace_equal(BOOST_MOVE_UREF##N)\ 1157 {\ 1158 NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 1159 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ 1160 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp));\ 1161 destroy_deallocator.release();\ 1162 return ret;\ 1163 }\ 1164 \ 1165 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 1166 iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1167 {\ 1168 BOOST_ASSERT((priv_is_linked)(hint));\ 1169 NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ 1170 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc());\ 1171 iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ 1172 destroy_deallocator.release();\ 1173 return ret;\ 1174 }\ 1175 \ 1176 template <class KeyType BOOST_MOVE_I##N BOOST_MOVE_CLASS##N>\ 1177 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool>\ 1178 try_emplace(const_iterator hint, BOOST_FWD_REF(KeyType) key BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ 1179 {\ 1180 insert_commit_data data;\ 1181 const key_type & k = key;\ 1182 std::pair<iiterator, bool> ret =\ 1183 hint == const_iterator() ? this->icont().insert_unique_check( k, KeyNodeCompare(key_comp()), data)\ 1184 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data);\ 1185 if(ret.second){\ 1186 ret.first = this->icont().insert_unique_commit\ 1187 (*AllocHolder::create_node(try_emplace_t(), boost::forward<KeyType>(key) BOOST_MOVE_I##N BOOST_MOVE_FWD##N), data);\ 1188 }\ 1189 return std::pair<iterator, bool>(iterator(ret.first), ret.second);\ 1190 }\ 1191 // 1192 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_TREE_EMPLACE_CODE) 1193 #undef BOOST_CONTAINER_TREE_EMPLACE_CODE 1194 1195 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 1196 1197 //BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert_unique, value_type, iterator, this->insert_unique_hint_convertible, const_iterator, const_iterator) 1198 1199 template <class InputIterator> insert_unique_range(InputIterator first,InputIterator last)1200 void insert_unique_range(InputIterator first, InputIterator last) 1201 { 1202 for( ; first != last; ++first) 1203 this->insert_unique_convertible(*first); 1204 } 1205 1206 template<class MovableConvertible> insert_equal_convertible(BOOST_FWD_REF (MovableConvertible)v)1207 iterator insert_equal_convertible(BOOST_FWD_REF(MovableConvertible) v) 1208 { 1209 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); 1210 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1211 iterator ret(this->icont().insert_equal(this->icont().end(), *tmp)); 1212 destroy_deallocator.release(); 1213 return ret; 1214 } 1215 1216 template<class MovableConvertible> insert_equal_hint_convertible(const_iterator hint,BOOST_FWD_REF (MovableConvertible)v)1217 iterator insert_equal_hint_convertible(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) 1218 { 1219 BOOST_ASSERT((priv_is_linked)(hint)); 1220 NodePtr tmp(AllocHolder::create_node(boost::forward<MovableConvertible>(v))); 1221 scoped_destroy_deallocator<NodeAlloc> destroy_deallocator(tmp, this->node_alloc()); 1222 iterator ret(this->icont().insert_equal(hint.get(), *tmp)); 1223 destroy_deallocator.release(); 1224 return ret; 1225 } 1226 1227 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG 1228 (insert_equal, value_type, iterator, this->insert_equal_hint_convertible, const_iterator, const_iterator) 1229 1230 template <class InputIterator> insert_equal_range(InputIterator first,InputIterator last)1231 void insert_equal_range(InputIterator first, InputIterator last) 1232 { 1233 for( ; first != last; ++first) 1234 this->insert_equal_convertible(*first); 1235 } 1236 1237 template<class KeyType, class M> insert_or_assign(const_iterator hint,BOOST_FWD_REF (KeyType)key,BOOST_FWD_REF (M)obj)1238 std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_FWD_REF(KeyType) key, BOOST_FWD_REF(M) obj) 1239 { 1240 insert_commit_data data; 1241 const key_type & k = key; //Support emulated rvalue references 1242 std::pair<iiterator, bool> ret = 1243 hint == const_iterator() ? this->icont().insert_unique_check(k, KeyNodeCompare(key_comp()), data) 1244 : this->icont().insert_unique_check(hint.get(), k, KeyNodeCompare(key_comp()), data); 1245 if(ret.second){ 1246 ret.first = this->priv_insert_or_assign_commit(boost::forward<KeyType>(key), boost::forward<M>(obj), data); 1247 } 1248 else{ 1249 ret.first->get_data().second = boost::forward<M>(obj); 1250 } 1251 return std::pair<iterator, bool>(iterator(ret.first), ret.second); 1252 } 1253 erase(const_iterator position)1254 iterator erase(const_iterator position) 1255 { 1256 BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); 1257 return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); 1258 } 1259 erase(const key_type & k)1260 BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& k) 1261 { return AllocHolder::erase_key(k, KeyNodeCompare(key_comp()), alloc_version()); } 1262 erase_unique(const key_type & k)1263 size_type erase_unique(const key_type& k) 1264 { 1265 iterator i = this->find(k); 1266 size_type ret = static_cast<size_type>(i != this->end()); 1267 if (ret) 1268 this->erase(i); 1269 return ret; 1270 } 1271 erase(const_iterator first,const_iterator last)1272 iterator erase(const_iterator first, const_iterator last) 1273 { 1274 BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); 1275 BOOST_ASSERT(first == last || (priv_is_linked)(last)); 1276 return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); 1277 } 1278 extract(const key_type & k)1279 node_type extract(const key_type& k) 1280 { 1281 iterator const it = this->find(k); 1282 if(this->end() != it){ 1283 return this->extract(it); 1284 } 1285 return node_type(); 1286 } 1287 extract(const_iterator position)1288 node_type extract(const_iterator position) 1289 { 1290 BOOST_ASSERT(position != this->cend() && (priv_is_linked)(position)); 1291 iiterator const iit(position.get()); 1292 this->icont().erase(iit); 1293 return node_type(iit.operator->(), this->node_alloc()); 1294 } 1295 insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1296 insert_return_type insert_unique_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1297 { 1298 return this->insert_unique_node(this->end(), boost::move(nh)); 1299 } 1300 insert_unique_node(const_iterator hint,BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1301 insert_return_type insert_unique_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1302 { 1303 insert_return_type irt; //inserted == false, node.empty() 1304 if(!nh.empty()){ 1305 insert_commit_data data; 1306 std::pair<iterator,bool> ret = 1307 this->insert_unique_check(hint, key_of_value_t()(nh.value()), data); 1308 if(ret.second){ 1309 irt.inserted = true; 1310 irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data)); 1311 nh.release(); 1312 } 1313 else{ 1314 irt.position = ret.first; 1315 irt.node = boost::move(nh); 1316 } 1317 } 1318 else{ 1319 irt.position = this->end(); 1320 } 1321 return BOOST_MOVE_RET(insert_return_type, irt); 1322 } 1323 insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1324 iterator insert_equal_node(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1325 { 1326 if(nh.empty()){ 1327 return this->end(); 1328 } 1329 else{ 1330 NodePtr const p(nh.release()); 1331 return iterator(this->icont().insert_equal(*p)); 1332 } 1333 } 1334 insert_equal_node(const_iterator hint,BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)1335 iterator insert_equal_node(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh) 1336 { 1337 if(nh.empty()){ 1338 return this->end(); 1339 } 1340 else{ 1341 NodePtr const p(nh.release()); 1342 return iterator(this->icont().insert_equal(hint.get(), *p)); 1343 } 1344 } 1345 1346 template<class C2> merge_unique(tree<T,KeyOfValue,C2,Allocator,Options> & source)1347 BOOST_CONTAINER_FORCEINLINE void merge_unique(tree<T, KeyOfValue, C2, Allocator, Options>& source) 1348 { return this->icont().merge_unique(source.icont()); } 1349 1350 template<class C2> merge_equal(tree<T,KeyOfValue,C2,Allocator,Options> & source)1351 BOOST_CONTAINER_FORCEINLINE void merge_equal(tree<T, KeyOfValue, C2, Allocator, Options>& source) 1352 { return this->icont().merge_equal(source.icont()); } clear()1353 BOOST_CONTAINER_FORCEINLINE void clear() 1354 { AllocHolder::clear(alloc_version()); } 1355 1356 // search operations. Const and non-const overloads even if no iterator is returned 1357 // so splay implementations can to their rebalancing when searching in non-const versions 1358 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE find(const key_type & k)1359 iterator find(const key_type& k) 1360 { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } 1361 1362 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE find(const key_type & k) const1363 const_iterator find(const key_type& k) const 1364 { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } 1365 1366 template <class K> 1367 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1368 typename dtl::enable_if_transparent<key_compare, K, iterator>::type find(const K & k)1369 find(const K& k) 1370 { return iterator(this->icont().find(k, KeyNodeCompare(key_comp()))); } 1371 1372 template <class K> 1373 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1374 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type find(const K & k) const1375 find(const K& k) const 1376 { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(key_comp()))); } 1377 1378 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE count(const key_type & k) const1379 size_type count(const key_type& k) const 1380 { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } 1381 1382 template <class K> 1383 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1384 typename dtl::enable_if_transparent<key_compare, K, size_type>::type count(const K & k) const1385 count(const K& k) const 1386 { return size_type(this->icont().count(k, KeyNodeCompare(key_comp()))); } 1387 1388 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE contains(const key_type & x) const1389 bool contains(const key_type& x) const 1390 { return this->find(x) != this->cend(); } 1391 1392 template<typename K> 1393 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1394 typename dtl::enable_if_transparent<key_compare, K, bool>::type contains(const K & x) const1395 contains(const K& x) const 1396 { return this->find(x) != this->cend(); } 1397 1398 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE lower_bound(const key_type & k)1399 iterator lower_bound(const key_type& k) 1400 { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1401 1402 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE lower_bound(const key_type & k) const1403 const_iterator lower_bound(const key_type& k) const 1404 { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1405 1406 template <class K> 1407 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1408 typename dtl::enable_if_transparent<key_compare, K, iterator>::type lower_bound(const K & k)1409 lower_bound(const K& k) 1410 { return iterator(this->icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1411 1412 template <class K> 1413 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1414 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type lower_bound(const K & k) const1415 lower_bound(const K& k) const 1416 { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(key_comp()))); } 1417 1418 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE upper_bound(const key_type & k)1419 iterator upper_bound(const key_type& k) 1420 { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1421 1422 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE upper_bound(const key_type & k) const1423 const_iterator upper_bound(const key_type& k) const 1424 { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1425 1426 template <class K> 1427 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1428 typename dtl::enable_if_transparent<key_compare, K, iterator>::type upper_bound(const K & k)1429 upper_bound(const K& k) 1430 { return iterator(this->icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1431 1432 template <class K> 1433 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1434 typename dtl::enable_if_transparent<key_compare, K, const_iterator>::type upper_bound(const K & k) const1435 upper_bound(const K& k) const 1436 { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(key_comp()))); } 1437 1438 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE equal_range(const key_type & k)1439 std::pair<iterator,iterator> equal_range(const key_type& k) 1440 { 1441 std::pair<iiterator, iiterator> ret = 1442 this->icont().equal_range(k, KeyNodeCompare(key_comp())); 1443 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1444 } 1445 1446 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE equal_range(const key_type & k) const1447 std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const 1448 { 1449 std::pair<iiterator, iiterator> ret = 1450 this->non_const_icont().equal_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_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1457 typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type equal_range(const K & k)1458 equal_range(const K& k) 1459 { 1460 std::pair<iiterator, iiterator> ret = 1461 this->icont().equal_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_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1467 typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type equal_range(const K & k) const1468 equal_range(const K& k) const 1469 { 1470 std::pair<iiterator, iiterator> ret = 1471 this->non_const_icont().equal_range(k, KeyNodeCompare(key_comp())); 1472 return std::pair<const_iterator,const_iterator> 1473 (const_iterator(ret.first), const_iterator(ret.second)); 1474 } 1475 1476 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE lower_bound_range(const key_type & k)1477 std::pair<iterator,iterator> lower_bound_range(const key_type& k) 1478 { 1479 std::pair<iiterator, iiterator> ret = 1480 this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1481 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1482 } 1483 1484 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE lower_bound_range(const key_type & k) const1485 std::pair<const_iterator, const_iterator> lower_bound_range(const key_type& k) const 1486 { 1487 std::pair<iiterator, iiterator> ret = 1488 this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1489 return std::pair<const_iterator,const_iterator> 1490 (const_iterator(ret.first), const_iterator(ret.second)); 1491 } 1492 1493 template <class K> 1494 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1495 typename dtl::enable_if_transparent<key_compare, K, std::pair<iterator,iterator> >::type lower_bound_range(const K & k)1496 lower_bound_range(const K& k) 1497 { 1498 std::pair<iiterator, iiterator> ret = 1499 this->icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1500 return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); 1501 } 1502 1503 template <class K> 1504 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE 1505 typename dtl::enable_if_transparent<key_compare, K, std::pair<const_iterator, const_iterator> >::type lower_bound_range(const K & k) const1506 lower_bound_range(const K& k) const 1507 { 1508 std::pair<iiterator, iiterator> ret = 1509 this->non_const_icont().lower_bound_range(k, KeyNodeCompare(key_comp())); 1510 return std::pair<const_iterator,const_iterator> 1511 (const_iterator(ret.first), const_iterator(ret.second)); 1512 } 1513 rebalance()1514 BOOST_CONTAINER_FORCEINLINE void rebalance() 1515 { intrusive_tree_proxy_t::rebalance(this->icont()); } 1516 1517 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator ==(const tree & x,const tree & y)1518 friend bool operator==(const tree& x, const tree& y) 1519 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } 1520 1521 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator <(const tree & x,const tree & y)1522 friend bool operator<(const tree& x, const tree& y) 1523 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1524 1525 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator !=(const tree & x,const tree & y)1526 friend bool operator!=(const tree& x, const tree& y) 1527 { return !(x == y); } 1528 1529 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator >(const tree & x,const tree & y)1530 friend bool operator>(const tree& x, const tree& y) 1531 { return y < x; } 1532 1533 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator <=(const tree & x,const tree & y)1534 friend bool operator<=(const tree& x, const tree& y) 1535 { return !(y < x); } 1536 1537 BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE operator >=(const tree & x,const tree & y)1538 friend bool operator>=(const tree& x, const tree& y) 1539 { return !(x < y); } 1540 swap(tree & x,tree & y)1541 BOOST_CONTAINER_FORCEINLINE friend void swap(tree& x, tree& y) 1542 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value 1543 && boost::container::dtl::is_nothrow_swappable<Compare>::value ) 1544 { x.swap(y); } 1545 }; 1546 1547 } //namespace dtl { 1548 } //namespace container { 1549 1550 template <class T> 1551 struct has_trivial_destructor_after_move; 1552 1553 //!has_trivial_destructor_after_move<> == true_type 1554 //!specialization for optimizations 1555 template <class T, class KeyOfValue, class Compare, class Allocator, class Options> 1556 struct has_trivial_destructor_after_move 1557 < 1558 ::boost::container::dtl::tree 1559 <T, KeyOfValue, Compare, Allocator, Options> 1560 > 1561 { 1562 typedef typename ::boost::container::dtl::tree<T, KeyOfValue, Compare, Allocator, Options>::allocator_type allocator_type; 1563 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer; 1564 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value && 1565 ::boost::has_trivial_destructor_after_move<pointer>::value && 1566 ::boost::has_trivial_destructor_after_move<Compare>::value; 1567 }; 1568 1569 } //namespace boost { 1570 1571 #include <boost/container/detail/config_end.hpp> 1572 1573 #endif //BOOST_CONTAINER_TREE_HPP 1574