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