1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2007-2014 4 // 5 // Distributed under the Boost Software License, Version 1.0. 6 // (See accompanying file LICENSE_1_0.txt or copy at 7 // http://www.boost.org/LICENSE_1_0.txt) 8 // 9 // See http://www.boost.org/libs/intrusive for documentation. 10 // 11 ///////////////////////////////////////////////////////////////////////////// 12 #ifndef BOOST_INTRUSIVE_SG_SET_HPP 13 #define BOOST_INTRUSIVE_SG_SET_HPP 14 15 #include <boost/intrusive/detail/config_begin.hpp> 16 #include <boost/intrusive/intrusive_fwd.hpp> 17 #include <boost/intrusive/detail/mpl.hpp> 18 #include <boost/intrusive/sgtree.hpp> 19 #include <boost/static_assert.hpp> 20 #include <boost/move/utility_core.hpp> 21 22 #if defined(BOOST_HAS_PRAGMA_ONCE) 23 # pragma once 24 #endif 25 26 namespace boost { 27 namespace intrusive { 28 29 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 30 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool ConstantTimeSize, typename HeaderHolder> 31 class sg_multiset_impl; 32 #endif 33 34 //! The class template sg_set is an intrusive container, that mimics most of 35 //! the interface of std::sg_set as described in the C++ standard. 36 //! 37 //! The template parameter \c T is the type to be managed by the container. 38 //! The user can specify additional options and if no options are provided 39 //! default options are used. 40 //! 41 //! The container supports the following options: 42 //! \c base_hook<>/member_hook<>/value_traits<>, 43 //! \c floating_point<>, \c size_type<> and 44 //! \c compare<>. 45 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 46 template<class T, class ...Options> 47 #else 48 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool FloatingPoint, typename HeaderHolder> 49 #endif 50 class sg_set_impl 51 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 52 : public sgtree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, FloatingPoint, HeaderHolder> 53 #endif 54 { 55 /// @cond 56 typedef sgtree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, FloatingPoint, HeaderHolder> tree_type; 57 BOOST_MOVABLE_BUT_NOT_COPYABLE(sg_set_impl) 58 59 typedef tree_type implementation_defined; 60 /// @endcond 61 62 public: 63 typedef typename implementation_defined::value_type value_type; 64 typedef typename implementation_defined::key_type key_type; 65 typedef typename implementation_defined::key_of_value key_of_value; 66 typedef typename implementation_defined::value_traits value_traits; 67 typedef typename implementation_defined::pointer pointer; 68 typedef typename implementation_defined::const_pointer const_pointer; 69 typedef typename implementation_defined::reference reference; 70 typedef typename implementation_defined::const_reference const_reference; 71 typedef typename implementation_defined::difference_type difference_type; 72 typedef typename implementation_defined::size_type size_type; 73 typedef typename implementation_defined::value_compare value_compare; 74 typedef typename implementation_defined::key_compare key_compare; 75 typedef typename implementation_defined::iterator iterator; 76 typedef typename implementation_defined::const_iterator const_iterator; 77 typedef typename implementation_defined::reverse_iterator reverse_iterator; 78 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; 79 typedef typename implementation_defined::insert_commit_data insert_commit_data; 80 typedef typename implementation_defined::node_traits node_traits; 81 typedef typename implementation_defined::node node; 82 typedef typename implementation_defined::node_ptr node_ptr; 83 typedef typename implementation_defined::const_node_ptr const_node_ptr; 84 typedef typename implementation_defined::node_algorithms node_algorithms; 85 86 static const bool constant_time_size = tree_type::constant_time_size; 87 88 public: 89 //! @copydoc ::boost::intrusive::sgtree::sgtree() sg_set_impl()90 sg_set_impl() 91 : tree_type() 92 {} 93 94 //! @copydoc ::boost::intrusive::sgtree::sgtree(const key_compare &,const value_traits &) sg_set_impl(const key_compare & cmp,const value_traits & v_traits=value_traits ())95 explicit sg_set_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) 96 : tree_type(cmp, v_traits) 97 {} 98 99 //! @copydoc ::boost::intrusive::sgtree::sgtree(bool,Iterator,Iterator,const key_compare &,const value_traits &) 100 template<class Iterator> sg_set_impl(Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())101 sg_set_impl( Iterator b, Iterator e 102 , const key_compare &cmp = key_compare() 103 , const value_traits &v_traits = value_traits()) 104 : tree_type(true, b, e, cmp, v_traits) 105 {} 106 107 //! @copydoc ::boost::intrusive::sgtree::sgtree(sgtree &&) sg_set_impl(BOOST_RV_REF (sg_set_impl)x)108 sg_set_impl(BOOST_RV_REF(sg_set_impl) x) 109 : tree_type(BOOST_MOVE_BASE(tree_type, x)) 110 {} 111 112 //! @copydoc ::boost::intrusive::sgtree::operator=(sgtree &&) operator =(BOOST_RV_REF (sg_set_impl)x)113 sg_set_impl& operator=(BOOST_RV_REF(sg_set_impl) x) 114 { return static_cast<sg_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } 115 116 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 117 //! @copydoc ::boost::intrusive::sgtree::~sgtree() 118 ~sg_set_impl(); 119 120 //! @copydoc ::boost::intrusive::sgtree::begin() 121 iterator begin(); 122 123 //! @copydoc ::boost::intrusive::sgtree::begin()const 124 const_iterator begin() const; 125 126 //! @copydoc ::boost::intrusive::sgtree::cbegin()const 127 const_iterator cbegin() const; 128 129 //! @copydoc ::boost::intrusive::sgtree::end() 130 iterator end(); 131 132 //! @copydoc ::boost::intrusive::sgtree::end()const 133 const_iterator end() const; 134 135 //! @copydoc ::boost::intrusive::sgtree::cend()const 136 const_iterator cend() const; 137 138 //! @copydoc ::boost::intrusive::sgtree::rbegin() 139 reverse_iterator rbegin(); 140 141 //! @copydoc ::boost::intrusive::sgtree::rbegin()const 142 const_reverse_iterator rbegin() const; 143 144 //! @copydoc ::boost::intrusive::sgtree::crbegin()const 145 const_reverse_iterator crbegin() const; 146 147 //! @copydoc ::boost::intrusive::sgtree::rend() 148 reverse_iterator rend(); 149 150 //! @copydoc ::boost::intrusive::sgtree::rend()const 151 const_reverse_iterator rend() const; 152 153 //! @copydoc ::boost::intrusive::sgtree::crend()const 154 const_reverse_iterator crend() const; 155 156 //! @copydoc ::boost::intrusive::sgtree::root() 157 iterator root(); 158 159 //! @copydoc ::boost::intrusive::sgtree::root()const 160 const_iterator root() const; 161 162 //! @copydoc ::boost::intrusive::sgtree::croot()const 163 const_iterator croot() const; 164 165 //! @copydoc ::boost::intrusive::sgtree::container_from_end_iterator(iterator) 166 static sg_set_impl &container_from_end_iterator(iterator end_iterator); 167 168 //! @copydoc ::boost::intrusive::sgtree::container_from_end_iterator(const_iterator) 169 static const sg_set_impl &container_from_end_iterator(const_iterator end_iterator); 170 171 //! @copydoc ::boost::intrusive::sgtree::container_from_iterator(iterator) 172 static sg_set_impl &container_from_iterator(iterator it); 173 174 //! @copydoc ::boost::intrusive::sgtree::container_from_iterator(const_iterator) 175 static const sg_set_impl &container_from_iterator(const_iterator it); 176 177 //! @copydoc ::boost::intrusive::sgtree::key_comp()const 178 key_compare key_comp() const; 179 180 //! @copydoc ::boost::intrusive::sgtree::value_comp()const 181 value_compare value_comp() const; 182 183 //! @copydoc ::boost::intrusive::sgtree::empty()const 184 bool empty() const; 185 186 //! @copydoc ::boost::intrusive::sgtree::size()const 187 size_type size() const; 188 189 //! @copydoc ::boost::intrusive::sgtree::swap 190 void swap(sg_set_impl& other); 191 192 //! @copydoc ::boost::intrusive::sgtree::clone_from(const sgtree&,Cloner,Disposer) 193 template <class Cloner, class Disposer> 194 void clone_from(const sg_set_impl &src, Cloner cloner, Disposer disposer); 195 196 #else 197 198 using tree_type::clone_from; 199 200 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 201 202 //! @copydoc ::boost::intrusive::sgtree::clone_from(sgtree&&,Cloner,Disposer) 203 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (sg_set_impl)src,Cloner cloner,Disposer disposer)204 void clone_from(BOOST_RV_REF(sg_set_impl) src, Cloner cloner, Disposer disposer) 205 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } 206 207 //! @copydoc ::boost::intrusive::sgtree::insert_unique(reference) insert(reference value)208 std::pair<iterator, bool> insert(reference value) 209 { return tree_type::insert_unique(value); } 210 211 //! @copydoc ::boost::intrusive::sgtree::insert_unique(const_iterator,reference) insert(const_iterator hint,reference value)212 iterator insert(const_iterator hint, reference value) 213 { return tree_type::insert_unique(hint, value); } 214 215 //! @copydoc ::boost::intrusive::sgtree::insert_unique_check(const key_type&,insert_commit_data&) insert_check(const key_type & key,insert_commit_data & commit_data)216 std::pair<iterator, bool> insert_check 217 (const key_type &key, insert_commit_data &commit_data) 218 { return tree_type::insert_unique_check(key, commit_data); } 219 220 //! @copydoc ::boost::intrusive::sgtree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&) insert_check(const_iterator hint,const key_type & key,insert_commit_data & commit_data)221 std::pair<iterator, bool> insert_check 222 (const_iterator hint, const key_type &key 223 ,insert_commit_data &commit_data) 224 { return tree_type::insert_unique_check(hint, key, commit_data); } 225 226 //! @copydoc ::boost::intrusive::sgtree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 227 template<class KeyType, class KeyTypeKeyCompare> insert_check(const KeyType & key,KeyTypeKeyCompare comp,insert_commit_data & commit_data)228 std::pair<iterator, bool> insert_check 229 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data) 230 { return tree_type::insert_unique_check(key, comp, commit_data); } 231 232 //! @copydoc ::boost::intrusive::sgtree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&) 233 template<class KeyType, class KeyTypeKeyCompare> insert_check(const_iterator hint,const KeyType & key,KeyTypeKeyCompare comp,insert_commit_data & commit_data)234 std::pair<iterator, bool> insert_check 235 (const_iterator hint, const KeyType &key 236 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data) 237 { return tree_type::insert_unique_check(hint, key, comp, commit_data); } 238 239 //! @copydoc ::boost::intrusive::sgtree::insert_unique(Iterator,Iterator) 240 template<class Iterator> insert(Iterator b,Iterator e)241 void insert(Iterator b, Iterator e) 242 { tree_type::insert_unique(b, e); } 243 244 //! @copydoc ::boost::intrusive::sgtree::insert_unique_commit insert_commit(reference value,const insert_commit_data & commit_data)245 iterator insert_commit(reference value, const insert_commit_data &commit_data) 246 { return tree_type::insert_unique_commit(value, commit_data); } 247 248 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 249 //! @copydoc ::boost::intrusive::sgtree::insert_before 250 iterator insert_before(const_iterator pos, reference value); 251 252 //! @copydoc ::boost::intrusive::sgtree::push_back 253 void push_back(reference value); 254 255 //! @copydoc ::boost::intrusive::sgtree::push_front 256 void push_front(reference value); 257 258 //! @copydoc ::boost::intrusive::sgtree::erase(const_iterator) 259 iterator erase(const_iterator i); 260 261 //! @copydoc ::boost::intrusive::sgtree::erase(const_iterator,const_iterator) 262 iterator erase(const_iterator b, const_iterator e); 263 264 //! @copydoc ::boost::intrusive::sgtree::erase(const key_type &) 265 size_type erase(const key_type &key); 266 267 //! @copydoc ::boost::intrusive::sgtree::erase(const KeyType&,KeyTypeKeyCompare) 268 template<class KeyType, class KeyTypeKeyCompare> 269 size_type erase(const KeyType& key, KeyTypeKeyCompare comp); 270 271 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const_iterator,Disposer) 272 template<class Disposer> 273 iterator erase_and_dispose(const_iterator i, Disposer disposer); 274 275 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const_iterator,const_iterator,Disposer) 276 template<class Disposer> 277 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); 278 279 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const key_type &, Disposer) 280 template<class Disposer> 281 size_type erase_and_dispose(const key_type &key, Disposer disposer); 282 283 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) 284 template<class KeyType, class KeyTypeKeyCompare, class Disposer> 285 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); 286 287 //! @copydoc ::boost::intrusive::sgtree::clear 288 void clear(); 289 290 //! @copydoc ::boost::intrusive::sgtree::clear_and_dispose 291 template<class Disposer> 292 void clear_and_dispose(Disposer disposer); 293 294 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 295 296 //! @copydoc ::boost::intrusive::sgtree::count(const key_type &)const count(const key_type & key) const297 size_type count(const key_type &key) const 298 { return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); } 299 300 //! @copydoc ::boost::intrusive::sgtree::count(const KeyType&,KeyTypeKeyCompare)const 301 template<class KeyType, class KeyTypeKeyCompare> count(const KeyType & key,KeyTypeKeyCompare comp) const302 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const 303 { return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); } 304 305 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 306 307 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const key_type &) 308 iterator lower_bound(const key_type &key); 309 310 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const KeyType&,KeyTypeKeyCompare) 311 template<class KeyType, class KeyTypeKeyCompare> 312 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); 313 314 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const key_type &)const 315 const_iterator lower_bound(const key_type &key) const; 316 317 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const KeyType&,KeyTypeKeyCompare)const 318 template<class KeyType, class KeyTypeKeyCompare> 319 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 320 321 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const key_type &) 322 iterator upper_bound(const key_type &key); 323 324 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const KeyType&,KeyTypeKeyCompare) 325 template<class KeyType, class KeyTypeKeyCompare> 326 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); 327 328 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const key_type &)const 329 const_iterator upper_bound(const key_type &key) const; 330 331 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const KeyType&,KeyTypeKeyCompare)const 332 template<class KeyType, class KeyTypeKeyCompare> 333 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 334 335 //! @copydoc ::boost::intrusive::sgtree::find(const key_type &) 336 iterator find(const key_type &key); 337 338 //! @copydoc ::boost::intrusive::sgtree::find(const KeyType&,KeyTypeKeyCompare) 339 template<class KeyType, class KeyTypeKeyCompare> 340 iterator find(const KeyType& key, KeyTypeKeyCompare comp); 341 342 //! @copydoc ::boost::intrusive::sgtree::find(const key_type &)const 343 const_iterator find(const key_type &key) const; 344 345 //! @copydoc ::boost::intrusive::sgtree::find(const KeyType&,KeyTypeKeyCompare)const 346 template<class KeyType, class KeyTypeKeyCompare> 347 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; 348 349 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 350 351 //! @copydoc ::boost::intrusive::sgtree::equal_range(const key_type &) equal_range(const key_type & key)352 std::pair<iterator,iterator> equal_range(const key_type &key) 353 { return this->tree_type::lower_bound_range(key); } 354 355 //! @copydoc ::boost::intrusive::sgtree::equal_range(const KeyType&,KeyTypeKeyCompare) 356 template<class KeyType, class KeyTypeKeyCompare> equal_range(const KeyType & key,KeyTypeKeyCompare comp)357 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp) 358 { return this->tree_type::equal_range(key, comp); } 359 360 //! @copydoc ::boost::intrusive::sgtree::equal_range(const key_type &)const 361 std::pair<const_iterator, const_iterator> equal_range(const key_type & key) const362 equal_range(const key_type &key) const 363 { return this->tree_type::lower_bound_range(key); } 364 365 //! @copydoc ::boost::intrusive::sgtree::equal_range(const KeyType&,KeyTypeKeyCompare)const 366 template<class KeyType, class KeyTypeKeyCompare> 367 std::pair<const_iterator, const_iterator> equal_range(const KeyType & key,KeyTypeKeyCompare comp) const368 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const 369 { return this->tree_type::equal_range(key, comp); } 370 371 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 372 373 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const key_type &,const key_type &,bool,bool) 374 std::pair<iterator,iterator> bounded_range 375 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); 376 377 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 378 template<class KeyType, class KeyTypeKeyCompare> 379 std::pair<iterator,iterator> bounded_range 380 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 381 382 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const key_type &,const key_type &,bool,bool)const 383 std::pair<const_iterator, const_iterator> 384 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 385 386 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const 387 template<class KeyType, class KeyTypeKeyCompare> 388 std::pair<const_iterator, const_iterator> bounded_range 389 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 390 391 //! @copydoc ::boost::intrusive::sgtree::s_iterator_to(reference) 392 static iterator s_iterator_to(reference value); 393 394 //! @copydoc ::boost::intrusive::sgtree::s_iterator_to(const_reference) 395 static const_iterator s_iterator_to(const_reference value); 396 397 //! @copydoc ::boost::intrusive::sgtree::iterator_to(reference) 398 iterator iterator_to(reference value); 399 400 //! @copydoc ::boost::intrusive::sgtree::iterator_to(const_reference)const 401 const_iterator iterator_to(const_reference value) const; 402 403 //! @copydoc ::boost::intrusive::sgtree::init_node(reference) 404 static void init_node(reference value); 405 406 //! @copydoc ::boost::intrusive::sgtree::unlink_leftmost_without_rebalance 407 pointer unlink_leftmost_without_rebalance(); 408 409 //! @copydoc ::boost::intrusive::sgtree::replace_node 410 void replace_node(iterator replace_this, reference with_this); 411 412 //! @copydoc ::boost::intrusive::sgtree::remove_node 413 void remove_node(reference value); 414 415 //! @copydoc ::boost::intrusive::sgtree::rebalance 416 void rebalance(); 417 418 //! @copydoc ::boost::intrusive::sgtree::rebalance_subtree 419 iterator rebalance_subtree(iterator root); 420 421 //! @copydoc ::boost::intrusive::sgtree::balance_factor() 422 float balance_factor() const; 423 424 //! @copydoc ::boost::intrusive::sgtree::balance_factor(float) 425 void balance_factor(float new_alpha); 426 427 //! @copydoc ::boost::intrusive::rbtree::merge_unique 428 template<class ...Options2> 429 void merge(sg_set<T, Options2...> &source); 430 431 //! @copydoc ::boost::intrusive::rbtree::merge_unique 432 template<class ...Options2> 433 void merge(sg_multiset<T, Options2...> &source); 434 435 #else 436 437 template<class Compare2> merge(sg_set_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,FloatingPoint,HeaderHolder> & source)438 void merge(sg_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source) 439 { return tree_type::merge_unique(source); } 440 441 template<class Compare2> merge(sg_multiset_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,FloatingPoint,HeaderHolder> & source)442 void merge(sg_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source) 443 { return tree_type::merge_unique(source); } 444 445 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 446 }; 447 448 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 449 450 template<class T, class ...Options> 451 bool operator!= (const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y); 452 453 template<class T, class ...Options> 454 bool operator>(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y); 455 456 template<class T, class ...Options> 457 bool operator<=(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y); 458 459 template<class T, class ...Options> 460 bool operator>=(const sg_set_impl<T, Options...> &x, const sg_set_impl<T, Options...> &y); 461 462 template<class T, class ...Options> 463 void swap(sg_set_impl<T, Options...> &x, sg_set_impl<T, Options...> &y); 464 465 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 466 467 //! Helper metafunction to define a \c sg_set that yields to the same type when the 468 //! same options (either explicitly or implicitly) are used. 469 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 470 template<class T, class ...Options> 471 #else 472 template<class T, class O1 = void, class O2 = void 473 , class O3 = void, class O4 = void 474 , class O5 = void, class O6 = void> 475 #endif 476 struct make_sg_set 477 { 478 /// @cond 479 typedef typename pack_options 480 < sgtree_defaults, 481 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 482 O1, O2, O3, O4, O5, O6 483 #else 484 Options... 485 #endif 486 >::type packed_options; 487 488 typedef typename detail::get_value_traits 489 <T, typename packed_options::proto_value_traits>::type value_traits; 490 491 typedef sg_set_impl 492 < value_traits 493 , typename packed_options::key_of_value 494 , typename packed_options::compare 495 , typename packed_options::size_type 496 , packed_options::floating_point 497 , typename packed_options::header_holder_type 498 > implementation_defined; 499 /// @endcond 500 typedef implementation_defined type; 501 }; 502 503 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 504 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 505 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 506 #else 507 template<class T, class ...Options> 508 #endif 509 class sg_set 510 : public make_sg_set<T, 511 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 512 O1, O2, O3, O4, O5, O6 513 #else 514 Options... 515 #endif 516 >::type 517 { 518 typedef typename make_sg_set 519 <T, 520 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 521 O1, O2, O3, O4, O5, O6 522 #else 523 Options... 524 #endif 525 >::type Base; 526 527 BOOST_MOVABLE_BUT_NOT_COPYABLE(sg_set) 528 public: 529 typedef typename Base::key_compare key_compare; 530 typedef typename Base::value_traits value_traits; 531 typedef typename Base::iterator iterator; 532 typedef typename Base::const_iterator const_iterator; 533 534 //Assert if passed value traits are compatible with the type 535 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 536 sg_set()537 BOOST_INTRUSIVE_FORCEINLINE sg_set() 538 : Base() 539 {} 540 sg_set(const key_compare & cmp,const value_traits & v_traits=value_traits ())541 BOOST_INTRUSIVE_FORCEINLINE explicit sg_set( const key_compare &cmp, const value_traits &v_traits = value_traits()) 542 : Base(cmp, v_traits) 543 {} 544 545 template<class Iterator> sg_set(Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())546 BOOST_INTRUSIVE_FORCEINLINE sg_set( Iterator b, Iterator e 547 , const key_compare &cmp = key_compare() 548 , const value_traits &v_traits = value_traits()) 549 : Base(b, e, cmp, v_traits) 550 {} 551 sg_set(BOOST_RV_REF (sg_set)x)552 BOOST_INTRUSIVE_FORCEINLINE sg_set(BOOST_RV_REF(sg_set) x) 553 : Base(BOOST_MOVE_BASE(Base, x)) 554 {} 555 operator =(BOOST_RV_REF (sg_set)x)556 BOOST_INTRUSIVE_FORCEINLINE sg_set& operator=(BOOST_RV_REF(sg_set) x) 557 { return static_cast<sg_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 558 559 template <class Cloner, class Disposer> clone_from(const sg_set & src,Cloner cloner,Disposer disposer)560 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const sg_set &src, Cloner cloner, Disposer disposer) 561 { Base::clone_from(src, cloner, disposer); } 562 563 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (sg_set)src,Cloner cloner,Disposer disposer)564 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(sg_set) src, Cloner cloner, Disposer disposer) 565 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 566 container_from_end_iterator(iterator end_iterator)567 BOOST_INTRUSIVE_FORCEINLINE static sg_set &container_from_end_iterator(iterator end_iterator) 568 { return static_cast<sg_set &>(Base::container_from_end_iterator(end_iterator)); } 569 container_from_end_iterator(const_iterator end_iterator)570 BOOST_INTRUSIVE_FORCEINLINE static const sg_set &container_from_end_iterator(const_iterator end_iterator) 571 { return static_cast<const sg_set &>(Base::container_from_end_iterator(end_iterator)); } 572 container_from_iterator(iterator it)573 BOOST_INTRUSIVE_FORCEINLINE static sg_set &container_from_iterator(iterator it) 574 { return static_cast<sg_set &>(Base::container_from_iterator(it)); } 575 container_from_iterator(const_iterator it)576 BOOST_INTRUSIVE_FORCEINLINE static const sg_set &container_from_iterator(const_iterator it) 577 { return static_cast<const sg_set &>(Base::container_from_iterator(it)); } 578 }; 579 580 #endif 581 582 //! The class template sg_multiset is an intrusive container, that mimics most of 583 //! the interface of std::sg_multiset as described in the C++ standard. 584 //! 585 //! The template parameter \c T is the type to be managed by the container. 586 //! The user can specify additional options and if no options are provided 587 //! default options are used. 588 //! 589 //! The container supports the following options: 590 //! \c base_hook<>/member_hook<>/value_traits<>, 591 //! \c floating_point<>, \c size_type<> and 592 //! \c compare<>. 593 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 594 template<class T, class ...Options> 595 #else 596 template<class ValueTraits, class VoidOrKeyOfValue, class Compare, class SizeType, bool FloatingPoint, typename HeaderHolder> 597 #endif 598 class sg_multiset_impl 599 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 600 : public sgtree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, FloatingPoint, HeaderHolder> 601 #endif 602 { 603 /// @cond 604 typedef sgtree_impl<ValueTraits, VoidOrKeyOfValue, Compare, SizeType, FloatingPoint, HeaderHolder> tree_type; 605 606 BOOST_MOVABLE_BUT_NOT_COPYABLE(sg_multiset_impl) 607 typedef tree_type implementation_defined; 608 /// @endcond 609 610 public: 611 typedef typename implementation_defined::value_type value_type; 612 typedef typename implementation_defined::key_type key_type; 613 typedef typename implementation_defined::key_of_value key_of_value; 614 typedef typename implementation_defined::value_traits value_traits; 615 typedef typename implementation_defined::pointer pointer; 616 typedef typename implementation_defined::const_pointer const_pointer; 617 typedef typename implementation_defined::reference reference; 618 typedef typename implementation_defined::const_reference const_reference; 619 typedef typename implementation_defined::difference_type difference_type; 620 typedef typename implementation_defined::size_type size_type; 621 typedef typename implementation_defined::value_compare value_compare; 622 typedef typename implementation_defined::key_compare key_compare; 623 typedef typename implementation_defined::iterator iterator; 624 typedef typename implementation_defined::const_iterator const_iterator; 625 typedef typename implementation_defined::reverse_iterator reverse_iterator; 626 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator; 627 typedef typename implementation_defined::insert_commit_data insert_commit_data; 628 typedef typename implementation_defined::node_traits node_traits; 629 typedef typename implementation_defined::node node; 630 typedef typename implementation_defined::node_ptr node_ptr; 631 typedef typename implementation_defined::const_node_ptr const_node_ptr; 632 typedef typename implementation_defined::node_algorithms node_algorithms; 633 634 static const bool constant_time_size = tree_type::constant_time_size; 635 636 public: 637 //! @copydoc ::boost::intrusive::sgtree::sgtree() sg_multiset_impl()638 sg_multiset_impl() 639 : tree_type() 640 {} 641 642 //! @copydoc ::boost::intrusive::sgtree::sgtree(const key_compare &,const value_traits &) sg_multiset_impl(const key_compare & cmp,const value_traits & v_traits=value_traits ())643 explicit sg_multiset_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) 644 : tree_type(cmp, v_traits) 645 {} 646 647 //! @copydoc ::boost::intrusive::sgtree::sgtree(bool,Iterator,Iterator,const key_compare &,const value_traits &) 648 template<class Iterator> sg_multiset_impl(Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())649 sg_multiset_impl( Iterator b, Iterator e 650 , const key_compare &cmp = key_compare() 651 , const value_traits &v_traits = value_traits()) 652 : tree_type(false, b, e, cmp, v_traits) 653 {} 654 655 //! @copydoc ::boost::intrusive::sgtree::sgtree(sgtree &&) sg_multiset_impl(BOOST_RV_REF (sg_multiset_impl)x)656 sg_multiset_impl(BOOST_RV_REF(sg_multiset_impl) x) 657 : tree_type(BOOST_MOVE_BASE(tree_type, x)) 658 {} 659 660 //! @copydoc ::boost::intrusive::sgtree::operator=(sgtree &&) operator =(BOOST_RV_REF (sg_multiset_impl)x)661 sg_multiset_impl& operator=(BOOST_RV_REF(sg_multiset_impl) x) 662 { return static_cast<sg_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); } 663 664 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 665 //! @copydoc ::boost::intrusive::sgtree::~sgtree() 666 ~sg_multiset_impl(); 667 668 //! @copydoc ::boost::intrusive::sgtree::begin() 669 iterator begin(); 670 671 //! @copydoc ::boost::intrusive::sgtree::begin()const 672 const_iterator begin() const; 673 674 //! @copydoc ::boost::intrusive::sgtree::cbegin()const 675 const_iterator cbegin() const; 676 677 //! @copydoc ::boost::intrusive::sgtree::end() 678 iterator end(); 679 680 //! @copydoc ::boost::intrusive::sgtree::end()const 681 const_iterator end() const; 682 683 //! @copydoc ::boost::intrusive::sgtree::cend()const 684 const_iterator cend() const; 685 686 //! @copydoc ::boost::intrusive::sgtree::rbegin() 687 reverse_iterator rbegin(); 688 689 //! @copydoc ::boost::intrusive::sgtree::rbegin()const 690 const_reverse_iterator rbegin() const; 691 692 //! @copydoc ::boost::intrusive::sgtree::crbegin()const 693 const_reverse_iterator crbegin() const; 694 695 //! @copydoc ::boost::intrusive::sgtree::rend() 696 reverse_iterator rend(); 697 698 //! @copydoc ::boost::intrusive::sgtree::rend()const 699 const_reverse_iterator rend() const; 700 701 //! @copydoc ::boost::intrusive::sgtree::crend()const 702 const_reverse_iterator crend() const; 703 704 //! @copydoc ::boost::intrusive::sgtree::root() 705 iterator root(); 706 707 //! @copydoc ::boost::intrusive::sgtree::root()const 708 const_iterator root() const; 709 710 //! @copydoc ::boost::intrusive::sgtree::croot()const 711 const_iterator croot() const; 712 713 //! @copydoc ::boost::intrusive::sgtree::container_from_end_iterator(iterator) 714 static sg_multiset_impl &container_from_end_iterator(iterator end_iterator); 715 716 //! @copydoc ::boost::intrusive::sgtree::container_from_end_iterator(const_iterator) 717 static const sg_multiset_impl &container_from_end_iterator(const_iterator end_iterator); 718 719 //! @copydoc ::boost::intrusive::sgtree::container_from_iterator(iterator) 720 static sg_multiset_impl &container_from_iterator(iterator it); 721 722 //! @copydoc ::boost::intrusive::sgtree::container_from_iterator(const_iterator) 723 static const sg_multiset_impl &container_from_iterator(const_iterator it); 724 725 //! @copydoc ::boost::intrusive::sgtree::key_comp()const 726 key_compare key_comp() const; 727 728 //! @copydoc ::boost::intrusive::sgtree::value_comp()const 729 value_compare value_comp() const; 730 731 //! @copydoc ::boost::intrusive::sgtree::empty()const 732 bool empty() const; 733 734 //! @copydoc ::boost::intrusive::sgtree::size()const 735 size_type size() const; 736 737 //! @copydoc ::boost::intrusive::sgtree::swap 738 void swap(sg_multiset_impl& other); 739 740 //! @copydoc ::boost::intrusive::sgtree::clone_from(const sgtree&,Cloner,Disposer) 741 template <class Cloner, class Disposer> 742 void clone_from(const sg_multiset_impl &src, Cloner cloner, Disposer disposer); 743 744 #else 745 746 using tree_type::clone_from; 747 748 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 749 750 //! @copydoc ::boost::intrusive::sgtree::clone_from(sgtree&&,Cloner,Disposer) 751 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (sg_multiset_impl)src,Cloner cloner,Disposer disposer)752 void clone_from(BOOST_RV_REF(sg_multiset_impl) src, Cloner cloner, Disposer disposer) 753 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); } 754 755 //! @copydoc ::boost::intrusive::sgtree::insert_equal(reference) insert(reference value)756 iterator insert(reference value) 757 { return tree_type::insert_equal(value); } 758 759 //! @copydoc ::boost::intrusive::sgtree::insert_equal(const_iterator,reference) insert(const_iterator hint,reference value)760 iterator insert(const_iterator hint, reference value) 761 { return tree_type::insert_equal(hint, value); } 762 763 //! @copydoc ::boost::intrusive::sgtree::insert_equal(Iterator,Iterator) 764 template<class Iterator> insert(Iterator b,Iterator e)765 void insert(Iterator b, Iterator e) 766 { tree_type::insert_equal(b, e); } 767 768 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 769 //! @copydoc ::boost::intrusive::sgtree::insert_before 770 iterator insert_before(const_iterator pos, reference value); 771 772 //! @copydoc ::boost::intrusive::sgtree::push_back 773 void push_back(reference value); 774 775 //! @copydoc ::boost::intrusive::sgtree::push_front 776 void push_front(reference value); 777 778 //! @copydoc ::boost::intrusive::sgtree::erase(const_iterator) 779 iterator erase(const_iterator i); 780 781 //! @copydoc ::boost::intrusive::sgtree::erase(const_iterator,const_iterator) 782 iterator erase(const_iterator b, const_iterator e); 783 784 //! @copydoc ::boost::intrusive::sgtree::erase(const key_type &) 785 size_type erase(const key_type &key); 786 787 //! @copydoc ::boost::intrusive::sgtree::erase(const KeyType&,KeyTypeKeyCompare) 788 template<class KeyType, class KeyTypeKeyCompare> 789 size_type erase(const KeyType& key, KeyTypeKeyCompare comp); 790 791 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const_iterator,Disposer) 792 template<class Disposer> 793 iterator erase_and_dispose(const_iterator i, Disposer disposer); 794 795 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const_iterator,const_iterator,Disposer) 796 template<class Disposer> 797 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer); 798 799 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const key_type &, Disposer) 800 template<class Disposer> 801 size_type erase_and_dispose(const key_type &key, Disposer disposer); 802 803 //! @copydoc ::boost::intrusive::sgtree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer) 804 template<class KeyType, class KeyTypeKeyCompare, class Disposer> 805 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer); 806 807 //! @copydoc ::boost::intrusive::sgtree::clear 808 void clear(); 809 810 //! @copydoc ::boost::intrusive::sgtree::clear_and_dispose 811 template<class Disposer> 812 void clear_and_dispose(Disposer disposer); 813 814 //! @copydoc ::boost::intrusive::sgtree::count(const key_type &)const 815 size_type count(const key_type &key) const; 816 817 //! @copydoc ::boost::intrusive::sgtree::count(const KeyType&,KeyTypeKeyCompare)const 818 template<class KeyType, class KeyTypeKeyCompare> 819 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const; 820 821 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const key_type &) 822 iterator lower_bound(const key_type &key); 823 824 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const KeyType&,KeyTypeKeyCompare) 825 template<class KeyType, class KeyTypeKeyCompare> 826 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp); 827 828 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const key_type &)const 829 const_iterator lower_bound(const key_type &key) const; 830 831 //! @copydoc ::boost::intrusive::sgtree::lower_bound(const KeyType&,KeyTypeKeyCompare)const 832 template<class KeyType, class KeyTypeKeyCompare> 833 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 834 835 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const key_type &) 836 iterator upper_bound(const key_type &key); 837 838 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const KeyType&,KeyTypeKeyCompare) 839 template<class KeyType, class KeyTypeKeyCompare> 840 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp); 841 842 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const key_type &)const 843 const_iterator upper_bound(const key_type &key) const; 844 845 //! @copydoc ::boost::intrusive::sgtree::upper_bound(const KeyType&,KeyTypeKeyCompare)const 846 template<class KeyType, class KeyTypeKeyCompare> 847 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const; 848 849 //! @copydoc ::boost::intrusive::sgtree::find(const key_type &) 850 iterator find(const key_type &key); 851 852 //! @copydoc ::boost::intrusive::sgtree::find(const KeyType&,KeyTypeKeyCompare) 853 template<class KeyType, class KeyTypeKeyCompare> 854 iterator find(const KeyType& key, KeyTypeKeyCompare comp); 855 856 //! @copydoc ::boost::intrusive::sgtree::find(const key_type &)const 857 const_iterator find(const key_type &key) const; 858 859 //! @copydoc ::boost::intrusive::sgtree::find(const KeyType&,KeyTypeKeyCompare)const 860 template<class KeyType, class KeyTypeKeyCompare> 861 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const; 862 863 //! @copydoc ::boost::intrusive::sgtree::equal_range(const key_type &) 864 std::pair<iterator,iterator> equal_range(const key_type &key); 865 866 //! @copydoc ::boost::intrusive::sgtree::equal_range(const KeyType&,KeyTypeKeyCompare) 867 template<class KeyType, class KeyTypeKeyCompare> 868 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp); 869 870 //! @copydoc ::boost::intrusive::sgtree::equal_range(const key_type &)const 871 std::pair<const_iterator, const_iterator> 872 equal_range(const key_type &key) const; 873 874 //! @copydoc ::boost::intrusive::sgtree::equal_range(const KeyType&,KeyTypeKeyCompare)const 875 template<class KeyType, class KeyTypeKeyCompare> 876 std::pair<const_iterator, const_iterator> 877 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const; 878 879 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const key_type &,const key_type &,bool,bool) 880 std::pair<iterator,iterator> bounded_range 881 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed); 882 883 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) 884 template<class KeyType, class KeyTypeKeyCompare> 885 std::pair<iterator,iterator> bounded_range 886 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); 887 888 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const key_type &,const key_type &,bool,bool)const 889 std::pair<const_iterator, const_iterator> 890 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; 891 892 //! @copydoc ::boost::intrusive::sgtree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const 893 template<class KeyType, class KeyTypeKeyCompare> 894 std::pair<const_iterator, const_iterator> bounded_range 895 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; 896 897 //! @copydoc ::boost::intrusive::sgtree::s_iterator_to(reference) 898 static iterator s_iterator_to(reference value); 899 900 //! @copydoc ::boost::intrusive::sgtree::s_iterator_to(const_reference) 901 static const_iterator s_iterator_to(const_reference value); 902 903 //! @copydoc ::boost::intrusive::sgtree::iterator_to(reference) 904 iterator iterator_to(reference value); 905 906 //! @copydoc ::boost::intrusive::sgtree::iterator_to(const_reference)const 907 const_iterator iterator_to(const_reference value) const; 908 909 //! @copydoc ::boost::intrusive::sgtree::init_node(reference) 910 static void init_node(reference value); 911 912 //! @copydoc ::boost::intrusive::sgtree::unlink_leftmost_without_rebalance 913 pointer unlink_leftmost_without_rebalance(); 914 915 //! @copydoc ::boost::intrusive::sgtree::replace_node 916 void replace_node(iterator replace_this, reference with_this); 917 918 //! @copydoc ::boost::intrusive::sgtree::remove_node 919 void remove_node(reference value); 920 921 //! @copydoc ::boost::intrusive::sgtree::rebalance 922 void rebalance(); 923 924 //! @copydoc ::boost::intrusive::sgtree::rebalance_subtree 925 iterator rebalance_subtree(iterator root); 926 927 //! @copydoc ::boost::intrusive::sgtree::balance_factor() 928 float balance_factor() const; 929 930 //! @copydoc ::boost::intrusive::sgtree::balance_factor(float) 931 void balance_factor(float new_alpha); 932 933 //! @copydoc ::boost::intrusive::treap::merge_unique 934 template<class ...Options2> 935 void merge(sg_multiset<T, Options2...> &source); 936 937 //! @copydoc ::boost::intrusive::treap::merge_unique 938 template<class ...Options2> 939 void merge(sg_set<T, Options2...> &source); 940 941 #else 942 943 template<class Compare2> merge(sg_multiset_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,FloatingPoint,HeaderHolder> & source)944 void merge(sg_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source) 945 { return tree_type::merge_equal(source); } 946 947 template<class Compare2> merge(sg_set_impl<ValueTraits,VoidOrKeyOfValue,Compare2,SizeType,FloatingPoint,HeaderHolder> & source)948 void merge(sg_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, FloatingPoint, HeaderHolder> &source) 949 { return tree_type::merge_equal(source); } 950 951 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED 952 }; 953 954 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 955 956 template<class T, class ...Options> 957 bool operator!= (const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y); 958 959 template<class T, class ...Options> 960 bool operator>(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y); 961 962 template<class T, class ...Options> 963 bool operator<=(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y); 964 965 template<class T, class ...Options> 966 bool operator>=(const sg_multiset_impl<T, Options...> &x, const sg_multiset_impl<T, Options...> &y); 967 968 template<class T, class ...Options> 969 void swap(sg_multiset_impl<T, Options...> &x, sg_multiset_impl<T, Options...> &y); 970 971 #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 972 973 //! Helper metafunction to define a \c sg_multiset that yields to the same type when the 974 //! same options (either explicitly or implicitly) are used. 975 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 976 template<class T, class ...Options> 977 #else 978 template<class T, class O1 = void, class O2 = void 979 , class O3 = void, class O4 = void 980 , class O5 = void, class O6 = void> 981 #endif 982 struct make_sg_multiset 983 { 984 /// @cond 985 typedef typename pack_options 986 < sgtree_defaults, 987 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 988 O1, O2, O3, O4, O5, O6 989 #else 990 Options... 991 #endif 992 >::type packed_options; 993 994 typedef typename detail::get_value_traits 995 <T, typename packed_options::proto_value_traits>::type value_traits; 996 997 typedef sg_multiset_impl 998 < value_traits 999 , typename packed_options::key_of_value 1000 , typename packed_options::compare 1001 , typename packed_options::size_type 1002 , packed_options::floating_point 1003 , typename packed_options::header_holder_type 1004 > implementation_defined; 1005 /// @endcond 1006 typedef implementation_defined type; 1007 }; 1008 1009 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1010 1011 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1012 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 1013 #else 1014 template<class T, class ...Options> 1015 #endif 1016 class sg_multiset 1017 : public make_sg_multiset<T, 1018 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1019 O1, O2, O3, O4, O5, O6 1020 #else 1021 Options... 1022 #endif 1023 >::type 1024 { 1025 typedef typename make_sg_multiset<T, 1026 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1027 O1, O2, O3, O4, O5, O6 1028 #else 1029 Options... 1030 #endif 1031 >::type Base; 1032 1033 BOOST_MOVABLE_BUT_NOT_COPYABLE(sg_multiset) 1034 1035 public: 1036 typedef typename Base::key_compare key_compare; 1037 typedef typename Base::value_traits value_traits; 1038 typedef typename Base::iterator iterator; 1039 typedef typename Base::const_iterator const_iterator; 1040 1041 //Assert if passed value traits are compatible with the type 1042 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); 1043 sg_multiset()1044 BOOST_INTRUSIVE_FORCEINLINE sg_multiset() 1045 : Base() 1046 {} 1047 sg_multiset(const key_compare & cmp,const value_traits & v_traits=value_traits ())1048 BOOST_INTRUSIVE_FORCEINLINE explicit sg_multiset( const key_compare &cmp, const value_traits &v_traits = value_traits()) 1049 : Base(cmp, v_traits) 1050 {} 1051 1052 template<class Iterator> sg_multiset(Iterator b,Iterator e,const key_compare & cmp=key_compare (),const value_traits & v_traits=value_traits ())1053 BOOST_INTRUSIVE_FORCEINLINE sg_multiset( Iterator b, Iterator e 1054 , const key_compare &cmp = key_compare() 1055 , const value_traits &v_traits = value_traits()) 1056 : Base(b, e, cmp, v_traits) 1057 {} 1058 sg_multiset(BOOST_RV_REF (sg_multiset)x)1059 BOOST_INTRUSIVE_FORCEINLINE sg_multiset(BOOST_RV_REF(sg_multiset) x) 1060 : Base(BOOST_MOVE_BASE(Base, x)) 1061 {} 1062 operator =(BOOST_RV_REF (sg_multiset)x)1063 BOOST_INTRUSIVE_FORCEINLINE sg_multiset& operator=(BOOST_RV_REF(sg_multiset) x) 1064 { return static_cast<sg_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 1065 1066 template <class Cloner, class Disposer> clone_from(const sg_multiset & src,Cloner cloner,Disposer disposer)1067 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const sg_multiset &src, Cloner cloner, Disposer disposer) 1068 { Base::clone_from(src, cloner, disposer); } 1069 1070 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (sg_multiset)src,Cloner cloner,Disposer disposer)1071 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(sg_multiset) src, Cloner cloner, Disposer disposer) 1072 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 1073 container_from_end_iterator(iterator end_iterator)1074 BOOST_INTRUSIVE_FORCEINLINE static sg_multiset &container_from_end_iterator(iterator end_iterator) 1075 { return static_cast<sg_multiset &>(Base::container_from_end_iterator(end_iterator)); } 1076 container_from_end_iterator(const_iterator end_iterator)1077 BOOST_INTRUSIVE_FORCEINLINE static const sg_multiset &container_from_end_iterator(const_iterator end_iterator) 1078 { return static_cast<const sg_multiset &>(Base::container_from_end_iterator(end_iterator)); } 1079 container_from_iterator(iterator it)1080 BOOST_INTRUSIVE_FORCEINLINE static sg_multiset &container_from_iterator(iterator it) 1081 { return static_cast<sg_multiset &>(Base::container_from_iterator(it)); } 1082 container_from_iterator(const_iterator it)1083 BOOST_INTRUSIVE_FORCEINLINE static const sg_multiset &container_from_iterator(const_iterator it) 1084 { return static_cast<const sg_multiset &>(Base::container_from_iterator(it)); } 1085 }; 1086 1087 #endif 1088 1089 } //namespace intrusive 1090 } //namespace boost 1091 1092 #include <boost/intrusive/detail/config_end.hpp> 1093 1094 #endif //BOOST_INTRUSIVE_SG_SET_HPP 1095