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