1 ///////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Olaf Krzikalla 2004-2006. 4 // (C) Copyright Ion Gaztanaga 2006-2014 5 // 6 // Distributed under the Boost Software License, Version 1.0. 7 // (See accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 // 10 // See http://www.boost.org/libs/intrusive for documentation. 11 // 12 ///////////////////////////////////////////////////////////////////////////// 13 14 #ifndef BOOST_INTRUSIVE_SLIST_HPP 15 #define BOOST_INTRUSIVE_SLIST_HPP 16 17 #include <boost/intrusive/detail/config_begin.hpp> 18 #include <boost/intrusive/intrusive_fwd.hpp> 19 20 #include <boost/intrusive/detail/assert.hpp> 21 #include <boost/intrusive/slist_hook.hpp> 22 #include <boost/intrusive/circular_slist_algorithms.hpp> 23 #include <boost/intrusive/linear_slist_algorithms.hpp> 24 #include <boost/intrusive/pointer_traits.hpp> 25 #include <boost/intrusive/link_mode.hpp> 26 #include <boost/intrusive/detail/get_value_traits.hpp> 27 #include <boost/intrusive/detail/is_stateful_value_traits.hpp> 28 #include <boost/intrusive/detail/default_header_holder.hpp> 29 #include <boost/intrusive/detail/uncast.hpp> 30 #include <boost/intrusive/detail/mpl.hpp> 31 #include <boost/intrusive/detail/iterator.hpp> 32 #include <boost/intrusive/detail/slist_iterator.hpp> 33 #include <boost/intrusive/detail/array_initializer.hpp> 34 #include <boost/intrusive/detail/exception_disposer.hpp> 35 #include <boost/intrusive/detail/equal_to_value.hpp> 36 #include <boost/intrusive/detail/key_nodeptr_comp.hpp> 37 #include <boost/intrusive/detail/simple_disposers.hpp> 38 #include <boost/intrusive/detail/size_holder.hpp> 39 #include <boost/intrusive/detail/algorithm.hpp> 40 41 #include <boost/move/utility_core.hpp> 42 #include <boost/static_assert.hpp> 43 44 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less 45 #include <cstddef> //std::size_t 46 #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair 47 48 #if defined(BOOST_HAS_PRAGMA_ONCE) 49 # pragma once 50 #endif 51 52 namespace boost { 53 namespace intrusive { 54 55 /// @cond 56 57 template<class HeaderHolder, class NodePtr, bool> 58 struct header_holder_plus_last 59 { 60 HeaderHolder header_holder_; 61 NodePtr last_; 62 }; 63 64 template<class HeaderHolder, class NodePtr> 65 struct header_holder_plus_last<HeaderHolder, NodePtr, false> 66 { 67 HeaderHolder header_holder_; 68 }; 69 70 struct default_slist_hook_applier 71 { template <class T> struct apply{ typedef typename T::default_slist_hook type; }; }; 72 73 template<> 74 struct is_default_hook_tag<default_slist_hook_applier> 75 { static const bool value = true; }; 76 77 struct slist_defaults 78 { 79 typedef default_slist_hook_applier proto_value_traits; 80 static const bool constant_time_size = true; 81 static const bool linear = false; 82 typedef std::size_t size_type; 83 static const bool cache_last = false; 84 typedef void header_holder_type; 85 }; 86 87 struct slist_bool_flags 88 { 89 static const std::size_t linear_pos = 1u; 90 static const std::size_t constant_time_size_pos = 2u; 91 static const std::size_t cache_last_pos = 4u; 92 }; 93 94 95 /// @endcond 96 97 //! The class template slist is an intrusive container, that encapsulates 98 //! a singly-linked list. You can use such a list to squeeze the last bit 99 //! of performance from your application. Unfortunately, the little gains 100 //! come with some huge drawbacks. A lot of member functions can't be 101 //! implemented as efficiently as for standard containers. To overcome 102 //! this limitation some other member functions with rather unusual semantics 103 //! have to be introduced. 104 //! 105 //! The template parameter \c T is the type to be managed by the container. 106 //! The user can specify additional options and if no options are provided 107 //! default options are used. 108 //! 109 //! The container supports the following options: 110 //! \c base_hook<>/member_hook<>/value_traits<>, 111 //! \c constant_time_size<>, \c size_type<>, 112 //! \c linear<> and \c cache_last<>. 113 //! 114 //! The iterators of slist are forward iterators. slist provides a static 115 //! function called "previous" to compute the previous iterator of a given iterator. 116 //! This function has linear complexity. To improve the usability esp. with 117 //! the '*_after' functions, ++end() == begin() and previous(begin()) == end() 118 //! are defined. An new special function "before_begin()" is defined, which returns 119 //! an iterator that points one less the beginning of the list: ++before_begin() == begin() 120 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 121 template<class T, class ...Options> 122 #else 123 template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> 124 #endif 125 class slist_impl 126 { 127 //Public typedefs 128 public: 129 typedef ValueTraits value_traits; 130 typedef typename value_traits::pointer pointer; 131 typedef typename value_traits::const_pointer const_pointer; 132 typedef typename pointer_traits<pointer>::element_type value_type; 133 typedef typename pointer_traits<pointer>::reference reference; 134 typedef typename pointer_traits<const_pointer>::reference const_reference; 135 typedef typename pointer_traits<pointer>::difference_type difference_type; 136 typedef SizeType size_type; 137 typedef slist_iterator<value_traits, false> iterator; 138 typedef slist_iterator<value_traits, true> const_iterator; 139 typedef typename value_traits::node_traits node_traits; 140 typedef typename node_traits::node node; 141 typedef typename node_traits::node_ptr node_ptr; 142 typedef typename node_traits::const_node_ptr const_node_ptr; 143 typedef typename detail::get_header_holder_type 144 < value_traits, HeaderHolder >::type header_holder_type; 145 146 static const bool constant_time_size = 0 != (BoolFlags & slist_bool_flags::constant_time_size_pos); 147 static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; 148 static const bool linear = 0 != (BoolFlags & slist_bool_flags::linear_pos); 149 static const bool cache_last = 0 != (BoolFlags & slist_bool_flags::cache_last_pos); 150 static const bool has_container_from_iterator = 151 detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; 152 153 typedef typename detail::if_c 154 < linear 155 , linear_slist_algorithms<node_traits> 156 , circular_slist_algorithms<node_traits> 157 >::type node_algorithms; 158 159 /// @cond 160 private: 161 typedef detail::size_holder<constant_time_size, size_type> size_traits; 162 163 //noncopyable 164 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist_impl) 165 166 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; 167 168 //Constant-time size is incompatible with auto-unlink hooks! 169 BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); 170 //Linear singly linked lists are incompatible with auto-unlink hooks! 171 BOOST_STATIC_ASSERT(!(linear && ((int)value_traits::link_mode == (int)auto_unlink))); 172 //A list with cached last node is incompatible with auto-unlink hooks! 173 BOOST_STATIC_ASSERT(!(cache_last && ((int)value_traits::link_mode == (int)auto_unlink))); 174 get_end_node()175 node_ptr get_end_node() 176 { return node_ptr(linear ? node_ptr() : this->get_root_node()); } 177 get_end_node() const178 const_node_ptr get_end_node() const 179 { 180 return const_node_ptr 181 (linear ? const_node_ptr() : this->get_root_node()); } 182 get_root_node()183 node_ptr get_root_node() 184 { return data_.root_plus_size_.header_holder_.get_node(); } 185 get_root_node() const186 const_node_ptr get_root_node() const 187 { return data_.root_plus_size_.header_holder_.get_node(); } 188 get_last_node()189 node_ptr get_last_node() 190 { return this->get_last_node(detail::bool_<cache_last>()); } 191 get_last_node() const192 const_node_ptr get_last_node() const 193 { return this->get_last_node(detail::bool_<cache_last>()); } 194 set_last_node(const node_ptr & n)195 void set_last_node(const node_ptr &n) 196 { return this->set_last_node(n, detail::bool_<cache_last>()); } 197 get_last_node(detail::bool_<false>)198 static node_ptr get_last_node(detail::bool_<false>) 199 { 200 //This function shall not be used if cache_last is not true 201 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); 202 return node_ptr(); 203 } 204 set_last_node(const node_ptr &,detail::bool_<false>)205 static void set_last_node(const node_ptr &, detail::bool_<false>) 206 { 207 //This function shall not be used if cache_last is not true 208 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); 209 } 210 get_last_node(detail::bool_<true>)211 node_ptr get_last_node(detail::bool_<true>) 212 { return node_ptr(data_.root_plus_size_.last_); } 213 get_last_node(detail::bool_<true>) const214 const_node_ptr get_last_node(detail::bool_<true>) const 215 { return const_node_ptr(data_.root_plus_size_.last_); } 216 set_last_node(const node_ptr & n,detail::bool_<true>)217 void set_last_node(const node_ptr & n, detail::bool_<true>) 218 { data_.root_plus_size_.last_ = n; } 219 set_default_constructed_state()220 void set_default_constructed_state() 221 { 222 node_algorithms::init_header(this->get_root_node()); 223 this->priv_size_traits().set_size(size_type(0)); 224 if(cache_last){ 225 this->set_last_node(this->get_root_node()); 226 } 227 } 228 229 typedef header_holder_plus_last<header_holder_type, node_ptr, cache_last> header_holder_plus_last_t; 230 struct root_plus_size 231 : public size_traits 232 , public header_holder_plus_last_t 233 {}; 234 235 struct data_t 236 : public slist_impl::value_traits 237 { 238 typedef typename slist_impl::value_traits value_traits; data_tboost::intrusive::slist_impl::data_t239 explicit data_t(const value_traits &val_traits) 240 : value_traits(val_traits) 241 {} 242 243 root_plus_size root_plus_size_; 244 } data_; 245 priv_size_traits()246 size_traits &priv_size_traits() 247 { return data_.root_plus_size_; } 248 priv_size_traits() const249 const size_traits &priv_size_traits() const 250 { return data_.root_plus_size_; } 251 priv_value_traits() const252 const value_traits &priv_value_traits() const 253 { return data_; } 254 priv_value_traits()255 value_traits &priv_value_traits() 256 { return data_; } 257 258 typedef typename boost::intrusive::value_traits_pointers 259 <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; 260 priv_value_traits_ptr() const261 const_value_traits_ptr priv_value_traits_ptr() const 262 { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } 263 264 /// @endcond 265 266 public: 267 268 ///@cond 269 270 //! <b>Requires</b>: f and before_l belong to another slist. 271 //! 272 //! <b>Effects</b>: Transfers the range [f, before_l] to this 273 //! list, after the element pointed by prev_pos. 274 //! No destructors or copy constructors are called. 275 //! 276 //! <b>Throws</b>: Nothing. 277 //! 278 //! <b>Complexity</b>: Linear to the number of elements transferred 279 //! if constant_time_size is true. Constant-time otherwise. 280 //! 281 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 282 //! list. Iterators of this list and all the references are not invalidated. 283 //! 284 //! <b>Warning</b>: Experimental function, don't use it! slist_impl(const node_ptr & f,const node_ptr & before_l,size_type n,const value_traits & v_traits=value_traits ())285 slist_impl( const node_ptr & f, const node_ptr & before_l 286 , size_type n, const value_traits &v_traits = value_traits()) 287 : data_(v_traits) 288 { 289 if(n){ 290 this->priv_size_traits().set_size(n); 291 if(cache_last){ 292 this->set_last_node(before_l); 293 } 294 node_traits::set_next(this->get_root_node(), f); 295 node_traits::set_next(before_l, this->get_end_node()); 296 } 297 else{ 298 this->set_default_constructed_state(); 299 } 300 } 301 302 ///@endcond 303 304 //! <b>Effects</b>: constructs an empty list. 305 //! 306 //! <b>Complexity</b>: Constant 307 //! 308 //! <b>Throws</b>: If value_traits::node_traits::node 309 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). slist_impl(const value_traits & v_traits=value_traits ())310 explicit slist_impl(const value_traits &v_traits = value_traits()) 311 : data_(v_traits) 312 { this->set_default_constructed_state(); } 313 314 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. 315 //! 316 //! <b>Effects</b>: Constructs a list equal to [b ,e). 317 //! 318 //! <b>Complexity</b>: Linear in distance(b, e). No copy constructors are called. 319 //! 320 //! <b>Throws</b>: If value_traits::node_traits::node 321 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). 322 template<class Iterator> slist_impl(Iterator b,Iterator e,const value_traits & v_traits=value_traits ())323 slist_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) 324 : data_(v_traits) 325 { 326 this->set_default_constructed_state(); 327 //nothrow, no need to rollback to release elements on exception 328 this->insert_after(this->cbefore_begin(), b, e); 329 } 330 331 //! <b>Effects</b>: to-do 332 //! slist_impl(BOOST_RV_REF (slist_impl)x)333 slist_impl(BOOST_RV_REF(slist_impl) x) 334 : data_(::boost::move(x.priv_value_traits())) 335 { 336 this->priv_size_traits().set_size(size_type(0)); 337 node_algorithms::init_header(this->get_root_node()); 338 //nothrow, no need to rollback to release elements on exception 339 this->swap(x); 340 } 341 342 //! <b>Effects</b>: to-do 343 //! operator =(BOOST_RV_REF (slist_impl)x)344 slist_impl& operator=(BOOST_RV_REF(slist_impl) x) 345 { this->swap(x); return *this; } 346 347 //! <b>Effects</b>: If it's a safe-mode 348 //! or auto-unlink value, the destructor does nothing 349 //! (ie. no code is generated). Otherwise it detaches all elements from this. 350 //! In this case the objects in the list are not deleted (i.e. no destructors 351 //! are called), but the hooks according to the value_traits template parameter 352 //! are set to their default value. 353 //! 354 //! <b>Complexity</b>: Linear to the number of elements in the list, if 355 //! it's a safe-mode or auto-unlink value. Otherwise constant. ~slist_impl()356 ~slist_impl() 357 { 358 if(is_safe_autounlink<ValueTraits::link_mode>::value){ 359 this->clear(); 360 node_algorithms::init(this->get_root_node()); 361 } 362 } 363 364 //! <b>Effects</b>: Erases all the elements of the container. 365 //! 366 //! <b>Throws</b>: Nothing. 367 //! 368 //! <b>Complexity</b>: Linear to the number of elements of the list. 369 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. 370 //! 371 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements. clear()372 void clear() 373 { 374 if(safemode_or_autounlink){ 375 this->clear_and_dispose(detail::null_disposer()); 376 } 377 else{ 378 this->set_default_constructed_state(); 379 } 380 } 381 382 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 383 //! 384 //! <b>Effects</b>: Erases all the elements of the container 385 //! Disposer::operator()(pointer) is called for the removed elements. 386 //! 387 //! <b>Throws</b>: Nothing. 388 //! 389 //! <b>Complexity</b>: Linear to the number of elements of the list. 390 //! 391 //! <b>Note</b>: Invalidates the iterators to the erased elements. 392 template <class Disposer> clear_and_dispose(Disposer disposer)393 void clear_and_dispose(Disposer disposer) 394 { 395 const_iterator it(this->begin()), itend(this->end()); 396 while(it != itend){ 397 node_ptr to_erase(it.pointed_node()); 398 ++it; 399 if(safemode_or_autounlink) 400 node_algorithms::init(to_erase); 401 disposer(priv_value_traits().to_value_ptr(to_erase)); 402 } 403 this->set_default_constructed_state(); 404 } 405 406 //! <b>Requires</b>: value must be an lvalue. 407 //! 408 //! <b>Effects</b>: Inserts the value in the front of the list. 409 //! No copy constructors are called. 410 //! 411 //! <b>Throws</b>: Nothing. 412 //! 413 //! <b>Complexity</b>: Constant. 414 //! 415 //! <b>Note</b>: Does not affect the validity of iterators and references. push_front(reference value)416 void push_front(reference value) 417 { 418 node_ptr to_insert = priv_value_traits().to_node_ptr(value); 419 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); 420 if(cache_last){ 421 if(this->empty()){ 422 this->set_last_node(to_insert); 423 } 424 } 425 node_algorithms::link_after(this->get_root_node(), to_insert); 426 this->priv_size_traits().increment(); 427 } 428 429 //! <b>Requires</b>: value must be an lvalue. 430 //! 431 //! <b>Effects</b>: Inserts the value in the back of the list. 432 //! No copy constructors are called. 433 //! 434 //! <b>Throws</b>: Nothing. 435 //! 436 //! <b>Complexity</b>: Constant. 437 //! 438 //! <b>Note</b>: Does not affect the validity of iterators and references. 439 //! This function is only available is cache_last<> is true. push_back(reference value)440 void push_back(reference value) 441 { 442 BOOST_STATIC_ASSERT((cache_last)); 443 node_ptr n = priv_value_traits().to_node_ptr(value); 444 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n)); 445 node_algorithms::link_after(this->get_last_node(), n); 446 if(cache_last){ 447 this->set_last_node(n); 448 } 449 this->priv_size_traits().increment(); 450 } 451 452 //! <b>Effects</b>: Erases the first element of the list. 453 //! No destructors are called. 454 //! 455 //! <b>Throws</b>: Nothing. 456 //! 457 //! <b>Complexity</b>: Constant. 458 //! 459 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. pop_front()460 void pop_front() 461 { return this->pop_front_and_dispose(detail::null_disposer()); } 462 463 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 464 //! 465 //! <b>Effects</b>: Erases the first element of the list. 466 //! Disposer::operator()(pointer) is called for the removed element. 467 //! 468 //! <b>Throws</b>: Nothing. 469 //! 470 //! <b>Complexity</b>: Constant. 471 //! 472 //! <b>Note</b>: Invalidates the iterators to the erased element. 473 template<class Disposer> pop_front_and_dispose(Disposer disposer)474 void pop_front_and_dispose(Disposer disposer) 475 { 476 node_ptr to_erase = node_traits::get_next(this->get_root_node()); 477 node_algorithms::unlink_after(this->get_root_node()); 478 this->priv_size_traits().decrement(); 479 if(safemode_or_autounlink) 480 node_algorithms::init(to_erase); 481 disposer(priv_value_traits().to_value_ptr(to_erase)); 482 if(cache_last){ 483 if(this->empty()){ 484 this->set_last_node(this->get_root_node()); 485 } 486 } 487 } 488 489 //! <b>Effects</b>: Returns a reference to the first element of the list. 490 //! 491 //! <b>Throws</b>: Nothing. 492 //! 493 //! <b>Complexity</b>: Constant. front()494 reference front() 495 { return *this->priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } 496 497 //! <b>Effects</b>: Returns a const_reference to the first element of the list. 498 //! 499 //! <b>Throws</b>: Nothing. 500 //! 501 //! <b>Complexity</b>: Constant. front() const502 const_reference front() const 503 { return *this->priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_next(this->get_root_node()))); } 504 505 //! <b>Effects</b>: Returns a reference to the last element of the list. 506 //! 507 //! <b>Throws</b>: Nothing. 508 //! 509 //! <b>Complexity</b>: Constant. 510 //! 511 //! <b>Note</b>: Does not affect the validity of iterators and references. 512 //! This function is only available is cache_last<> is true. back()513 reference back() 514 { 515 BOOST_STATIC_ASSERT((cache_last)); 516 return *this->priv_value_traits().to_value_ptr(this->get_last_node()); 517 } 518 519 //! <b>Effects</b>: Returns a const_reference to the last element of the list. 520 //! 521 //! <b>Throws</b>: Nothing. 522 //! 523 //! <b>Complexity</b>: Constant. 524 //! 525 //! <b>Note</b>: Does not affect the validity of iterators and references. 526 //! This function is only available is cache_last<> is true. back() const527 const_reference back() const 528 { 529 BOOST_STATIC_ASSERT((cache_last)); 530 return *this->priv_value_traits().to_value_ptr(this->get_last_node()); 531 } 532 533 //! <b>Effects</b>: Returns an iterator to the first element contained in the list. 534 //! 535 //! <b>Throws</b>: Nothing. 536 //! 537 //! <b>Complexity</b>: Constant. begin()538 iterator begin() 539 { return iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } 540 541 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 542 //! 543 //! <b>Throws</b>: Nothing. 544 //! 545 //! <b>Complexity</b>: Constant. begin() const546 const_iterator begin() const 547 { return const_iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } 548 549 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 550 //! 551 //! <b>Throws</b>: Nothing. 552 //! 553 //! <b>Complexity</b>: Constant. cbegin() const554 const_iterator cbegin() const 555 { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } 556 557 //! <b>Effects</b>: Returns an iterator to the end of the list. 558 //! 559 //! <b>Throws</b>: Nothing. 560 //! 561 //! <b>Complexity</b>: Constant. end()562 iterator end() 563 { return iterator(this->get_end_node(), this->priv_value_traits_ptr()); } 564 565 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 566 //! 567 //! <b>Throws</b>: Nothing. 568 //! 569 //! <b>Complexity</b>: Constant. end() const570 const_iterator end() const 571 { return const_iterator(detail::uncast(this->get_end_node()), this->priv_value_traits_ptr()); } 572 573 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 574 //! 575 //! <b>Throws</b>: Nothing. 576 //! 577 //! <b>Complexity</b>: Constant. cend() const578 const_iterator cend() const 579 { return this->end(); } 580 581 //! <b>Effects</b>: Returns an iterator that points to a position 582 //! before the first element. Equivalent to "end()" 583 //! 584 //! <b>Throws</b>: Nothing. 585 //! 586 //! <b>Complexity</b>: Constant. before_begin()587 iterator before_begin() 588 { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); } 589 590 //! <b>Effects</b>: Returns an iterator that points to a position 591 //! before the first element. Equivalent to "end()" 592 //! 593 //! <b>Throws</b>: Nothing. 594 //! 595 //! <b>Complexity</b>: Constant. before_begin() const596 const_iterator before_begin() const 597 { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); } 598 599 //! <b>Effects</b>: Returns an iterator that points to a position 600 //! before the first element. Equivalent to "end()" 601 //! 602 //! <b>Throws</b>: Nothing. 603 //! 604 //! <b>Complexity</b>: Constant. cbefore_begin() const605 const_iterator cbefore_begin() const 606 { return this->before_begin(); } 607 608 //! <b>Effects</b>: Returns an iterator to the last element contained in the list. 609 //! 610 //! <b>Throws</b>: Nothing. 611 //! 612 //! <b>Complexity</b>: Constant. 613 //! 614 //! <b>Note</b>: This function is present only if cached_last<> option is true. last()615 iterator last() 616 { 617 //This function shall not be used if cache_last is not true 618 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); 619 return iterator (this->get_last_node(), this->priv_value_traits_ptr()); 620 } 621 622 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list. 623 //! 624 //! <b>Throws</b>: Nothing. 625 //! 626 //! <b>Complexity</b>: Constant. 627 //! 628 //! <b>Note</b>: This function is present only if cached_last<> option is true. last() const629 const_iterator last() const 630 { 631 //This function shall not be used if cache_last is not true 632 BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); 633 return const_iterator (this->get_last_node(), this->priv_value_traits_ptr()); 634 } 635 636 //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list. 637 //! 638 //! <b>Throws</b>: Nothing. 639 //! 640 //! <b>Complexity</b>: Constant. 641 //! 642 //! <b>Note</b>: This function is present only if cached_last<> option is true. clast() const643 const_iterator clast() const 644 { return const_iterator(this->get_last_node(), this->priv_value_traits_ptr()); } 645 646 //! <b>Precondition</b>: end_iterator must be a valid end iterator 647 //! of slist. 648 //! 649 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator 650 //! 651 //! <b>Throws</b>: Nothing. 652 //! 653 //! <b>Complexity</b>: Constant. container_from_end_iterator(iterator end_iterator)654 static slist_impl &container_from_end_iterator(iterator end_iterator) 655 { return slist_impl::priv_container_from_end_iterator(end_iterator); } 656 657 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator 658 //! of slist. 659 //! 660 //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator 661 //! 662 //! <b>Throws</b>: Nothing. 663 //! 664 //! <b>Complexity</b>: Constant. container_from_end_iterator(const_iterator end_iterator)665 static const slist_impl &container_from_end_iterator(const_iterator end_iterator) 666 { return slist_impl::priv_container_from_end_iterator(end_iterator); } 667 668 //! <b>Effects</b>: Returns the number of the elements contained in the list. 669 //! 670 //! <b>Throws</b>: Nothing. 671 //! 672 //! <b>Complexity</b>: Linear to the number of elements contained in the list. 673 //! if constant_time_size is false. Constant time otherwise. 674 //! 675 //! <b>Note</b>: Does not affect the validity of iterators and references. size() const676 size_type size() const 677 { 678 if(constant_time_size) 679 return this->priv_size_traits().get_size(); 680 else 681 return node_algorithms::count(this->get_root_node()) - 1; 682 } 683 684 //! <b>Effects</b>: Returns true if the list contains no elements. 685 //! 686 //! <b>Throws</b>: Nothing. 687 //! 688 //! <b>Complexity</b>: Constant. 689 //! 690 //! <b>Note</b>: Does not affect the validity of iterators and references. empty() const691 bool empty() const 692 { return node_algorithms::unique(this->get_root_node()); } 693 694 //! <b>Effects</b>: Swaps the elements of x and *this. 695 //! 696 //! <b>Throws</b>: Nothing. 697 //! 698 //! <b>Complexity</b>: Linear to the number of elements of both lists. 699 //! Constant-time if linear<> and/or cache_last<> options are used. 700 //! 701 //! <b>Note</b>: Does not affect the validity of iterators and references. swap(slist_impl & other)702 void swap(slist_impl& other) 703 { 704 if(cache_last){ 705 priv_swap_cache_last(this, &other); 706 } 707 else{ 708 this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>()); 709 } 710 if(constant_time_size){ 711 size_type backup = this->priv_size_traits().get_size(); 712 this->priv_size_traits().set_size(other.priv_size_traits().get_size()); 713 other.priv_size_traits().set_size(backup); 714 } 715 } 716 717 //! <b>Effects</b>: Moves backwards all the elements, so that the first 718 //! element becomes the second, the second becomes the third... 719 //! the last element becomes the first one. 720 //! 721 //! <b>Throws</b>: Nothing. 722 //! 723 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts. 724 //! 725 //! <b>Note</b>: Iterators Does not affect the validity of iterators and references. shift_backwards(size_type n=1)726 void shift_backwards(size_type n = 1) 727 { this->priv_shift_backwards(n, detail::bool_<linear>()); } 728 729 //! <b>Effects</b>: Moves forward all the elements, so that the second 730 //! element becomes the first, the third becomes the second... 731 //! the first element becomes the last one. 732 //! 733 //! <b>Throws</b>: Nothing. 734 //! 735 //! <b>Complexity</b>: Linear to the number of elements plus the number shifts. 736 //! 737 //! <b>Note</b>: Does not affect the validity of iterators and references. shift_forward(size_type n=1)738 void shift_forward(size_type n = 1) 739 { this->priv_shift_forward(n, detail::bool_<linear>()); } 740 741 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 742 //! Cloner should yield to nodes equivalent to the original nodes. 743 //! 744 //! <b>Effects</b>: Erases all the elements from *this 745 //! calling Disposer::operator()(pointer), clones all the 746 //! elements from src calling Cloner::operator()(const_reference ) 747 //! and inserts them on *this. 748 //! 749 //! If cloner throws, all cloned elements are unlinked and disposed 750 //! calling Disposer::operator()(pointer). 751 //! 752 //! <b>Complexity</b>: Linear to erased plus inserted elements. 753 //! 754 //! <b>Throws</b>: If cloner throws. 755 template <class Cloner, class Disposer> clone_from(const slist_impl & src,Cloner cloner,Disposer disposer)756 void clone_from(const slist_impl &src, Cloner cloner, Disposer disposer) 757 { 758 this->clear_and_dispose(disposer); 759 detail::exception_disposer<slist_impl, Disposer> 760 rollback(*this, disposer); 761 const_iterator prev(this->cbefore_begin()); 762 const_iterator b(src.begin()), e(src.end()); 763 for(; b != e; ++b){ 764 prev = this->insert_after(prev, *cloner(*b)); 765 } 766 rollback.release(); 767 } 768 769 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 770 //! Cloner should yield to nodes equivalent to the original nodes. 771 //! 772 //! <b>Effects</b>: Erases all the elements from *this 773 //! calling Disposer::operator()(pointer), clones all the 774 //! elements from src calling Cloner::operator()(reference) 775 //! and inserts them on *this. 776 //! 777 //! If cloner throws, all cloned elements are unlinked and disposed 778 //! calling Disposer::operator()(pointer). 779 //! 780 //! <b>Complexity</b>: Linear to erased plus inserted elements. 781 //! 782 //! <b>Throws</b>: If cloner throws. 783 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (slist_impl)src,Cloner cloner,Disposer disposer)784 void clone_from(BOOST_RV_REF(slist_impl) src, Cloner cloner, Disposer disposer) 785 { 786 this->clear_and_dispose(disposer); 787 detail::exception_disposer<slist_impl, Disposer> 788 rollback(*this, disposer); 789 iterator prev(this->cbefore_begin()); 790 iterator b(src.begin()), e(src.end()); 791 for(; b != e; ++b){ 792 prev = this->insert_after(prev, *cloner(*b)); 793 } 794 rollback.release(); 795 } 796 797 //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element 798 //! contained by the list or to end(). 799 //! 800 //! <b>Effects</b>: Inserts the value after the position pointed by prev_p. 801 //! No copy constructor is called. 802 //! 803 //! <b>Returns</b>: An iterator to the inserted element. 804 //! 805 //! <b>Throws</b>: Nothing. 806 //! 807 //! <b>Complexity</b>: Constant. 808 //! 809 //! <b>Note</b>: Does not affect the validity of iterators and references. insert_after(const_iterator prev_p,reference value)810 iterator insert_after(const_iterator prev_p, reference value) 811 { 812 node_ptr n = priv_value_traits().to_node_ptr(value); 813 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n)); 814 node_ptr prev_n(prev_p.pointed_node()); 815 node_algorithms::link_after(prev_n, n); 816 if(cache_last && (this->get_last_node() == prev_n)){ 817 this->set_last_node(n); 818 } 819 this->priv_size_traits().increment(); 820 return iterator (n, this->priv_value_traits_ptr()); 821 } 822 823 //! <b>Requires</b>: Dereferencing iterator must yield 824 //! an lvalue of type value_type and prev_p must point to an element 825 //! contained by the list or to the end node. 826 //! 827 //! <b>Effects</b>: Inserts the [f, l) 828 //! after the position prev_p. 829 //! 830 //! <b>Throws</b>: Nothing. 831 //! 832 //! <b>Complexity</b>: Linear to the number of elements inserted. 833 //! 834 //! <b>Note</b>: Does not affect the validity of iterators and references. 835 template<class Iterator> insert_after(const_iterator prev_p,Iterator f,Iterator l)836 void insert_after(const_iterator prev_p, Iterator f, Iterator l) 837 { 838 //Insert first nodes avoiding cache and size checks 839 size_type count = 0; 840 node_ptr prev_n(prev_p.pointed_node()); 841 for (; f != l; ++f, ++count){ 842 const node_ptr n = priv_value_traits().to_node_ptr(*f); 843 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n)); 844 node_algorithms::link_after(prev_n, n); 845 prev_n = n; 846 } 847 //Now fix special cases if needed 848 if(cache_last && (this->get_last_node() == prev_p.pointed_node())){ 849 this->set_last_node(prev_n); 850 } 851 if(constant_time_size){ 852 this->priv_size_traits().increase(count); 853 } 854 } 855 856 //! <b>Requires</b>: value must be an lvalue and p must point to an element 857 //! contained by the list or to end(). 858 //! 859 //! <b>Effects</b>: Inserts the value before the position pointed by p. 860 //! No copy constructor is called. 861 //! 862 //! <b>Throws</b>: Nothing. 863 //! 864 //! <b>Complexity</b>: Linear to the number of elements before p. 865 //! Constant-time if cache_last<> is true and p == end(). 866 //! 867 //! <b>Note</b>: Does not affect the validity of iterators and references. insert(const_iterator p,reference value)868 iterator insert(const_iterator p, reference value) 869 { return this->insert_after(this->previous(p), value); } 870 871 //! <b>Requires</b>: Dereferencing iterator must yield 872 //! an lvalue of type value_type and p must point to an element 873 //! contained by the list or to the end node. 874 //! 875 //! <b>Effects</b>: Inserts the pointed by b and e 876 //! before the position p. No copy constructors are called. 877 //! 878 //! <b>Throws</b>: Nothing. 879 //! 880 //! <b>Complexity</b>: Linear to the number of elements inserted plus linear 881 //! to the elements before b. 882 //! Linear to the number of elements to insert if cache_last<> option is true and p == end(). 883 //! 884 //! <b>Note</b>: Does not affect the validity of iterators and references. 885 template<class Iterator> insert(const_iterator p,Iterator b,Iterator e)886 void insert(const_iterator p, Iterator b, Iterator e) 887 { return this->insert_after(this->previous(p), b, e); } 888 889 //! <b>Effects</b>: Erases the element after the element pointed by prev of 890 //! the list. No destructors are called. 891 //! 892 //! <b>Returns</b>: the first element remaining beyond the removed elements, 893 //! or end() if no such element exists. 894 //! 895 //! <b>Throws</b>: Nothing. 896 //! 897 //! <b>Complexity</b>: Constant. 898 //! 899 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 900 //! erased element. erase_after(const_iterator prev)901 iterator erase_after(const_iterator prev) 902 { return this->erase_after_and_dispose(prev, detail::null_disposer()); } 903 904 //! <b>Effects</b>: Erases the range (before_f, l) from 905 //! the list. No destructors are called. 906 //! 907 //! <b>Returns</b>: the first element remaining beyond the removed elements, 908 //! or end() if no such element exists. 909 //! 910 //! <b>Throws</b>: Nothing. 911 //! 912 //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode 913 //! , auto-unlink value or constant-time size is activated. Constant time otherwise. 914 //! 915 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 916 //! erased element. erase_after(const_iterator before_f,const_iterator l)917 iterator erase_after(const_iterator before_f, const_iterator l) 918 { 919 if(safemode_or_autounlink || constant_time_size){ 920 return this->erase_after_and_dispose(before_f, l, detail::null_disposer()); 921 } 922 else{ 923 const node_ptr bfp = before_f.pointed_node(); 924 const node_ptr lp = l.pointed_node(); 925 if(cache_last){ 926 if(lp == this->get_end_node()){ 927 this->set_last_node(bfp); 928 } 929 } 930 node_algorithms::unlink_after(bfp, lp); 931 return l.unconst(); 932 } 933 } 934 935 //! <b>Effects</b>: Erases the range (before_f, l) from 936 //! the list. n must be distance(before_f, l) - 1. 937 //! No destructors are called. 938 //! 939 //! <b>Returns</b>: the first element remaining beyond the removed elements, 940 //! or end() if no such element exists. 941 //! 942 //! <b>Throws</b>: Nothing. 943 //! 944 //! <b>Complexity</b>: constant-time if link_mode is normal_link. 945 //! Linear to the elements (l - before_f) otherwise. 946 //! 947 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 948 //! erased element. erase_after(const_iterator before_f,const_iterator l,size_type n)949 iterator erase_after(const_iterator before_f, const_iterator l, size_type n) 950 { 951 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance((++const_iterator(before_f)).pointed_node(), l.pointed_node()) == n); 952 if(safemode_or_autounlink){ 953 return this->erase_after(before_f, l); 954 } 955 else{ 956 const node_ptr bfp = before_f.pointed_node(); 957 const node_ptr lp = l.pointed_node(); 958 if(cache_last){ 959 if((lp == this->get_end_node())){ 960 this->set_last_node(bfp); 961 } 962 } 963 node_algorithms::unlink_after(bfp, lp); 964 if(constant_time_size){ 965 this->priv_size_traits().decrease(n); 966 } 967 return l.unconst(); 968 } 969 } 970 971 //! <b>Effects</b>: Erases the element pointed by i of the list. 972 //! No destructors are called. 973 //! 974 //! <b>Returns</b>: the first element remaining beyond the removed element, 975 //! or end() if no such element exists. 976 //! 977 //! <b>Throws</b>: Nothing. 978 //! 979 //! <b>Complexity</b>: Linear to the elements before i. 980 //! 981 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 982 //! erased element. erase(const_iterator i)983 iterator erase(const_iterator i) 984 { return this->erase_after(this->previous(i)); } 985 986 //! <b>Requires</b>: f and l must be valid iterator to elements in *this. 987 //! 988 //! <b>Effects</b>: Erases the range pointed by b and e. 989 //! No destructors are called. 990 //! 991 //! <b>Returns</b>: the first element remaining beyond the removed elements, 992 //! or end() if no such element exists. 993 //! 994 //! <b>Throws</b>: Nothing. 995 //! 996 //! <b>Complexity</b>: Linear to the elements before l. 997 //! 998 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 999 //! erased elements. erase(const_iterator f,const_iterator l)1000 iterator erase(const_iterator f, const_iterator l) 1001 { return this->erase_after(this->previous(f), l); } 1002 1003 //! <b>Effects</b>: Erases the range [f, l) from 1004 //! the list. n must be distance(f, l). 1005 //! No destructors are called. 1006 //! 1007 //! <b>Returns</b>: the first element remaining beyond the removed elements, 1008 //! or end() if no such element exists. 1009 //! 1010 //! <b>Throws</b>: Nothing. 1011 //! 1012 //! <b>Complexity</b>: linear to the elements before f if link_mode is normal_link 1013 //! and constant_time_size is activated. Linear to the elements before l otherwise. 1014 //! 1015 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 1016 //! erased element. erase(const_iterator f,const_iterator l,size_type n)1017 iterator erase(const_iterator f, const_iterator l, size_type n) 1018 { return this->erase_after(this->previous(f), l, n); } 1019 1020 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1021 //! 1022 //! <b>Effects</b>: Erases the element after the element pointed by prev of 1023 //! the list. 1024 //! Disposer::operator()(pointer) is called for the removed element. 1025 //! 1026 //! <b>Returns</b>: the first element remaining beyond the removed elements, 1027 //! or end() if no such element exists. 1028 //! 1029 //! <b>Throws</b>: Nothing. 1030 //! 1031 //! <b>Complexity</b>: Constant. 1032 //! 1033 //! <b>Note</b>: Invalidates the iterators to the erased element. 1034 template<class Disposer> erase_after_and_dispose(const_iterator prev,Disposer disposer)1035 iterator erase_after_and_dispose(const_iterator prev, Disposer disposer) 1036 { 1037 const_iterator it(prev); 1038 ++it; 1039 node_ptr to_erase(it.pointed_node()); 1040 ++it; 1041 node_ptr prev_n(prev.pointed_node()); 1042 node_algorithms::unlink_after(prev_n); 1043 if(cache_last && (to_erase == this->get_last_node())){ 1044 this->set_last_node(prev_n); 1045 } 1046 if(safemode_or_autounlink) 1047 node_algorithms::init(to_erase); 1048 disposer(priv_value_traits().to_value_ptr(to_erase)); 1049 this->priv_size_traits().decrement(); 1050 return it.unconst(); 1051 } 1052 1053 /// @cond 1054 s_insert_after(const_iterator const prev_p,reference value)1055 static iterator s_insert_after(const_iterator const prev_p, reference value) 1056 { 1057 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits))); 1058 node_ptr const n = value_traits::to_node_ptr(value); 1059 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(n)); 1060 node_algorithms::link_after(prev_p.pointed_node(), n); 1061 return iterator (n, const_value_traits_ptr()); 1062 } 1063 1064 template<class Disposer> s_erase_after_and_dispose(const_iterator prev,Disposer disposer)1065 static iterator s_erase_after_and_dispose(const_iterator prev, Disposer disposer) 1066 { 1067 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits))); 1068 const_iterator it(prev); 1069 ++it; 1070 node_ptr to_erase(it.pointed_node()); 1071 ++it; 1072 node_ptr prev_n(prev.pointed_node()); 1073 node_algorithms::unlink_after(prev_n); 1074 if(safemode_or_autounlink) 1075 node_algorithms::init(to_erase); 1076 disposer(value_traits::to_value_ptr(to_erase)); 1077 return it.unconst(); 1078 } 1079 1080 template<class Disposer> s_erase_after_and_dispose(const_iterator before_f,const_iterator l,Disposer disposer)1081 static iterator s_erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer) 1082 { 1083 BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits))); 1084 node_ptr bfp(before_f.pointed_node()), lp(l.pointed_node()); 1085 node_ptr fp(node_traits::get_next(bfp)); 1086 node_algorithms::unlink_after(bfp, lp); 1087 while(fp != lp){ 1088 node_ptr to_erase(fp); 1089 fp = node_traits::get_next(fp); 1090 if(safemode_or_autounlink) 1091 node_algorithms::init(to_erase); 1092 disposer(value_traits::to_value_ptr(to_erase)); 1093 } 1094 return l.unconst(); 1095 } 1096 s_erase_after(const_iterator prev)1097 static iterator s_erase_after(const_iterator prev) 1098 { return s_erase_after_and_dispose(prev, detail::null_disposer()); } 1099 1100 /// @endcond 1101 1102 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1103 //! 1104 //! <b>Effects</b>: Erases the range (before_f, l) from 1105 //! the list. 1106 //! Disposer::operator()(pointer) is called for the removed elements. 1107 //! 1108 //! <b>Returns</b>: the first element remaining beyond the removed elements, 1109 //! or end() if no such element exists. 1110 //! 1111 //! <b>Throws</b>: Nothing. 1112 //! 1113 //! <b>Complexity</b>: Lineal to the elements (l - before_f + 1). 1114 //! 1115 //! <b>Note</b>: Invalidates the iterators to the erased element. 1116 template<class Disposer> erase_after_and_dispose(const_iterator before_f,const_iterator l,Disposer disposer)1117 iterator erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer) 1118 { 1119 node_ptr bfp(before_f.pointed_node()), lp(l.pointed_node()); 1120 node_ptr fp(node_traits::get_next(bfp)); 1121 node_algorithms::unlink_after(bfp, lp); 1122 while(fp != lp){ 1123 node_ptr to_erase(fp); 1124 fp = node_traits::get_next(fp); 1125 if(safemode_or_autounlink) 1126 node_algorithms::init(to_erase); 1127 disposer(priv_value_traits().to_value_ptr(to_erase)); 1128 this->priv_size_traits().decrement(); 1129 } 1130 if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){ 1131 this->set_last_node(bfp); 1132 } 1133 return l.unconst(); 1134 } 1135 1136 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1137 //! 1138 //! <b>Effects</b>: Erases the element pointed by i of the list. 1139 //! No destructors are called. 1140 //! Disposer::operator()(pointer) is called for the removed element. 1141 //! 1142 //! <b>Returns</b>: the first element remaining beyond the removed element, 1143 //! or end() if no such element exists. 1144 //! 1145 //! <b>Throws</b>: Nothing. 1146 //! 1147 //! <b>Complexity</b>: Linear to the elements before i. 1148 //! 1149 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 1150 //! erased element. 1151 template<class Disposer> erase_and_dispose(const_iterator i,Disposer disposer)1152 iterator erase_and_dispose(const_iterator i, Disposer disposer) 1153 { return this->erase_after_and_dispose(this->previous(i), disposer); } 1154 1155 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 1156 template<class Disposer> erase_and_dispose(iterator i,Disposer disposer)1157 iterator erase_and_dispose(iterator i, Disposer disposer) 1158 { return this->erase_and_dispose(const_iterator(i), disposer); } 1159 #endif 1160 1161 //! <b>Requires</b>: f and l must be valid iterator to elements in *this. 1162 //! Disposer::operator()(pointer) shouldn't throw. 1163 //! 1164 //! <b>Effects</b>: Erases the range pointed by b and e. 1165 //! No destructors are called. 1166 //! Disposer::operator()(pointer) is called for the removed elements. 1167 //! 1168 //! <b>Returns</b>: the first element remaining beyond the removed elements, 1169 //! or end() if no such element exists. 1170 //! 1171 //! <b>Throws</b>: Nothing. 1172 //! 1173 //! <b>Complexity</b>: Linear to the number of erased elements plus linear 1174 //! to the elements before f. 1175 //! 1176 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 1177 //! erased elements. 1178 template<class Disposer> erase_and_dispose(const_iterator f,const_iterator l,Disposer disposer)1179 iterator erase_and_dispose(const_iterator f, const_iterator l, Disposer disposer) 1180 { return this->erase_after_and_dispose(this->previous(f), l, disposer); } 1181 1182 //! <b>Requires</b>: Dereferencing iterator must yield 1183 //! an lvalue of type value_type. 1184 //! 1185 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. 1186 //! No destructors or copy constructors are called. 1187 //! 1188 //! <b>Throws</b>: Nothing. 1189 //! 1190 //! <b>Complexity</b>: Linear to the number of elements inserted plus 1191 //! linear to the elements contained in the list if it's a safe-mode 1192 //! or auto-unlink value. 1193 //! Linear to the number of elements inserted in the list otherwise. 1194 //! 1195 //! <b>Note</b>: Invalidates the iterators (but not the references) 1196 //! to the erased elements. 1197 template<class Iterator> assign(Iterator b,Iterator e)1198 void assign(Iterator b, Iterator e) 1199 { 1200 this->clear(); 1201 this->insert_after(this->cbefore_begin(), b, e); 1202 } 1203 1204 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1205 //! 1206 //! <b>Requires</b>: Dereferencing iterator must yield 1207 //! an lvalue of type value_type. 1208 //! 1209 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. 1210 //! No destructors or copy constructors are called. 1211 //! Disposer::operator()(pointer) is called for the removed elements. 1212 //! 1213 //! <b>Throws</b>: Nothing. 1214 //! 1215 //! <b>Complexity</b>: Linear to the number of elements inserted plus 1216 //! linear to the elements contained in the list. 1217 //! 1218 //! <b>Note</b>: Invalidates the iterators (but not the references) 1219 //! to the erased elements. 1220 template<class Iterator, class Disposer> dispose_and_assign(Disposer disposer,Iterator b,Iterator e)1221 void dispose_and_assign(Disposer disposer, Iterator b, Iterator e) 1222 { 1223 this->clear_and_dispose(disposer); 1224 this->insert_after(this->cbefore_begin(), b, e, disposer); 1225 } 1226 1227 //! <b>Requires</b>: prev must point to an element contained by this list or 1228 //! to the before_begin() element 1229 //! 1230 //! <b>Effects</b>: Transfers all the elements of list x to this list, after the 1231 //! the element pointed by prev. No destructors or copy constructors are called. 1232 //! 1233 //! <b>Returns</b>: Nothing. 1234 //! 1235 //! <b>Throws</b>: Nothing. 1236 //! 1237 //! <b>Complexity</b>: In general, linear to the elements contained in x. 1238 //! Constant-time if cache_last<> option is true and also constant-time if 1239 //! linear<> option is true "this" is empty and "l" is not used. 1240 //! 1241 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1242 //! list. Iterators of this list and all the references are not invalidated. 1243 //! 1244 //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be 1245 //! assigned to the last spliced element or prev if x is empty. 1246 //! This iterator can be used as new "prev" iterator for a new splice_after call. 1247 //! that will splice new values after the previously spliced values. splice_after(const_iterator prev,slist_impl & x,const_iterator * l=0)1248 void splice_after(const_iterator prev, slist_impl &x, const_iterator *l = 0) 1249 { 1250 if(x.empty()){ 1251 if(l) *l = prev; 1252 } 1253 else if(linear && this->empty()){ 1254 this->swap(x); 1255 if(l) *l = this->previous(this->cend()); 1256 } 1257 else{ 1258 const_iterator last_x(x.previous(x.end())); //<- constant time if cache_last is active 1259 node_ptr prev_n(prev.pointed_node()); 1260 node_ptr last_x_n(last_x.pointed_node()); 1261 if(cache_last){ 1262 x.set_last_node(x.get_root_node()); 1263 if(node_traits::get_next(prev_n) == this->get_end_node()){ 1264 this->set_last_node(last_x_n); 1265 } 1266 } 1267 node_algorithms::transfer_after( prev_n, x.before_begin().pointed_node(), last_x_n); 1268 this->priv_size_traits().increase(x.priv_size_traits().get_size()); 1269 x.priv_size_traits().set_size(size_type(0)); 1270 if(l) *l = last_x; 1271 } 1272 } 1273 1274 //! <b>Requires</b>: prev must point to an element contained by this list or 1275 //! to the before_begin() element. prev_ele must point to an element contained in list 1276 //! x or must be x.before_begin(). 1277 //! 1278 //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list, 1279 //! after the element pointed by prev. No destructors or copy constructors are called. 1280 //! 1281 //! <b>Throws</b>: Nothing. 1282 //! 1283 //! <b>Complexity</b>: Constant. 1284 //! 1285 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1286 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_pos,slist_impl & x,const_iterator prev_ele)1287 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator prev_ele) 1288 { 1289 const_iterator elem = prev_ele; 1290 this->splice_after(prev_pos, x, prev_ele, ++elem, 1); 1291 } 1292 1293 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be 1294 //! before_begin(), and before_f and before_l belong to x and 1295 //! ++before_f != x.end() && before_l != x.end(). 1296 //! 1297 //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this 1298 //! list, after the element pointed by prev_pos. 1299 //! No destructors or copy constructors are called. 1300 //! 1301 //! <b>Throws</b>: Nothing. 1302 //! 1303 //! <b>Complexity</b>: Linear to the number of elements transferred 1304 //! if constant_time_size is true. Constant-time otherwise. 1305 //! 1306 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1307 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_pos,slist_impl & x,const_iterator before_f,const_iterator before_l)1308 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l) 1309 { 1310 if(constant_time_size) 1311 this->splice_after(prev_pos, x, before_f, before_l, node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node())); 1312 else 1313 this->priv_splice_after 1314 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node()); 1315 } 1316 1317 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be 1318 //! before_begin(), and before_f and before_l belong to x and 1319 //! ++before_f != x.end() && before_l != x.end() and 1320 //! n == distance(before_f, before_l). 1321 //! 1322 //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this 1323 //! list, after the element pointed by p. No destructors or copy constructors are called. 1324 //! 1325 //! <b>Throws</b>: Nothing. 1326 //! 1327 //! <b>Complexity</b>: Constant time. 1328 //! 1329 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1330 //! list. Iterators of this list and all the references are not invalidated. splice_after(const_iterator prev_pos,slist_impl & x,const_iterator before_f,const_iterator before_l,size_type n)1331 void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l, size_type n) 1332 { 1333 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(before_f.pointed_node(), before_l.pointed_node()) == n); 1334 this->priv_splice_after 1335 (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node()); 1336 if(constant_time_size){ 1337 this->priv_size_traits().increase(n); 1338 x.priv_size_traits().decrease(n); 1339 } 1340 } 1341 1342 //! <b>Requires</b>: it is an iterator to an element in *this. 1343 //! 1344 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 1345 //! the element pointed by it. No destructors or copy constructors are called. 1346 //! 1347 //! <b>Returns</b>: Nothing. 1348 //! 1349 //! <b>Throws</b>: Nothing. 1350 //! 1351 //! <b>Complexity</b>: Linear to the elements contained in x plus linear to 1352 //! the elements before it. 1353 //! Linear to the elements before it if cache_last<> option is true. 1354 //! Constant-time if cache_last<> option is true and it == end(). 1355 //! 1356 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1357 //! list. Iterators of this list and all the references are not invalidated. 1358 //! 1359 //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be 1360 //! assigned to the last spliced element or prev if x is empty. 1361 //! This iterator can be used as new "prev" iterator for a new splice_after call. 1362 //! that will splice new values after the previously spliced values. splice(const_iterator it,slist_impl & x,const_iterator * l=0)1363 void splice(const_iterator it, slist_impl &x, const_iterator *l = 0) 1364 { this->splice_after(this->previous(it), x, l); } 1365 1366 //! <b>Requires</b>: it p must be a valid iterator of *this. 1367 //! elem must point to an element contained in list 1368 //! x. 1369 //! 1370 //! <b>Effects</b>: Transfers the element elem, from list x to this list, 1371 //! before the element pointed by pos. No destructors or copy constructors are called. 1372 //! 1373 //! <b>Throws</b>: Nothing. 1374 //! 1375 //! <b>Complexity</b>: Linear to the elements before pos and before elem. 1376 //! Linear to the elements before elem if cache_last<> option is true and pos == end(). 1377 //! 1378 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1379 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator pos,slist_impl & x,const_iterator elem)1380 void splice(const_iterator pos, slist_impl &x, const_iterator elem) 1381 { return this->splice_after(this->previous(pos), x, x.previous(elem)); } 1382 1383 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this 1384 //! and f and f belong to x and f and f a valid range on x. 1385 //! 1386 //! <b>Effects</b>: Transfers the range [f, l) from list x to this 1387 //! list, before the element pointed by pos. 1388 //! No destructors or copy constructors are called. 1389 //! 1390 //! <b>Throws</b>: Nothing. 1391 //! 1392 //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l 1393 //! plus linear to the number of elements transferred if constant_time_size is true. 1394 //! Linear to the sum of elements before f, and l 1395 //! plus linear to the number of elements transferred if constant_time_size is true 1396 //! if cache_last<> is true and pos == end() 1397 //! 1398 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1399 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator pos,slist_impl & x,const_iterator f,const_iterator l)1400 void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l) 1401 { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l)); } 1402 1403 //! <b>Requires</b>: pos must be a dereferenceable iterator in *this 1404 //! and f and l belong to x and f and l a valid range on x. 1405 //! n == distance(f, l). 1406 //! 1407 //! <b>Effects</b>: Transfers the range [f, l) from list x to this 1408 //! list, before the element pointed by pos. 1409 //! No destructors or copy constructors are called. 1410 //! 1411 //! <b>Throws</b>: Nothing. 1412 //! 1413 //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l. 1414 //! Linear to the sum of elements before f and l 1415 //! if cache_last<> is true and pos == end(). 1416 //! 1417 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 1418 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator pos,slist_impl & x,const_iterator f,const_iterator l,size_type n)1419 void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l, size_type n) 1420 { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l), n); } 1421 1422 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 1423 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 1424 //! 1425 //! <b>Throws</b>: If value_traits::node_traits::node 1426 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 1427 //! or the predicate throws. Basic guarantee. 1428 //! 1429 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1430 //! is the list's size. 1431 //! 1432 //! <b>Note</b>: Iterators and references are not invalidated 1433 template<class Predicate> sort(Predicate p)1434 void sort(Predicate p) 1435 { 1436 if (node_traits::get_next(node_traits::get_next(this->get_root_node())) 1437 != this->get_root_node()) { 1438 1439 slist_impl carry(this->priv_value_traits()); 1440 detail::array_initializer<slist_impl, 64> counter(this->priv_value_traits()); 1441 int fill = 0; 1442 const_iterator last_inserted; 1443 while(!this->empty()){ 1444 last_inserted = this->cbegin(); 1445 carry.splice_after(carry.cbefore_begin(), *this, this->cbefore_begin()); 1446 int i = 0; 1447 while(i < fill && !counter[i].empty()) { 1448 carry.swap(counter[i]); 1449 carry.merge(counter[i++], p, &last_inserted); 1450 } 1451 BOOST_INTRUSIVE_INVARIANT_ASSERT(counter[i].empty()); 1452 const_iterator last_element(carry.previous(last_inserted, carry.end())); 1453 1454 if(constant_time_size){ 1455 counter[i].splice_after( counter[i].cbefore_begin(), carry 1456 , carry.cbefore_begin(), last_element 1457 , carry.size()); 1458 } 1459 else{ 1460 counter[i].splice_after( counter[i].cbefore_begin(), carry 1461 , carry.cbefore_begin(), last_element); 1462 } 1463 if(i == fill) 1464 ++fill; 1465 } 1466 1467 for (int i = 1; i < fill; ++i) 1468 counter[i].merge(counter[i-1], p, &last_inserted); 1469 --fill; 1470 const_iterator last_element(counter[fill].previous(last_inserted, counter[fill].end())); 1471 if(constant_time_size){ 1472 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin() 1473 , last_element, counter[fill].size()); 1474 } 1475 else{ 1476 this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin() 1477 , last_element); 1478 } 1479 } 1480 } 1481 1482 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1483 //! ordering and both *this and x must be sorted according to that ordering 1484 //! The lists x and *this must be distinct. 1485 //! 1486 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1487 //! in order into *this. The merge is stable; that is, if an element from *this is 1488 //! equivalent to one from x, then the element from *this will precede the one from x. 1489 //! 1490 //! <b>Throws</b>: If value_traits::node_traits::node 1491 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 1492 //! or std::less<value_type> throws. Basic guarantee. 1493 //! 1494 //! <b>Complexity</b>: This function is linear time: it performs at most 1495 //! size() + x.size() - 1 comparisons. 1496 //! 1497 //! <b>Note</b>: Iterators and references are not invalidated. sort()1498 void sort() 1499 { this->sort(std::less<value_type>()); } 1500 1501 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1502 //! ordering and both *this and x must be sorted according to that ordering 1503 //! The lists x and *this must be distinct. 1504 //! 1505 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1506 //! in order into *this. The merge is stable; that is, if an element from *this is 1507 //! equivalent to one from x, then the element from *this will precede the one from x. 1508 //! 1509 //! <b>Returns</b>: Nothing. 1510 //! 1511 //! <b>Throws</b>: If the predicate throws. Basic guarantee. 1512 //! 1513 //! <b>Complexity</b>: This function is linear time: it performs at most 1514 //! size() + x.size() - 1 comparisons. 1515 //! 1516 //! <b>Note</b>: Iterators and references are not invalidated. 1517 //! 1518 //! <b>Additional note</b>: If optional "l" argument is passed, it is assigned 1519 //! to an iterator to the last transferred value or end() is x is empty. 1520 template<class Predicate> merge(slist_impl & x,Predicate p,const_iterator * l=0)1521 void merge(slist_impl& x, Predicate p, const_iterator *l = 0) 1522 { 1523 const_iterator e(this->cend()), ex(x.cend()), bb(this->cbefore_begin()), 1524 bb_next; 1525 if(l) *l = e.unconst(); 1526 while(!x.empty()){ 1527 const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++); 1528 while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){ 1529 bb = bb_next; 1530 } 1531 if(bb_next == e){ 1532 //Now transfer the rest to the end of the container 1533 this->splice_after(bb, x, l); 1534 break; 1535 } 1536 else{ 1537 size_type n(0); 1538 do{ 1539 ibx = ibx_next; ++n; 1540 } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next)); 1541 this->splice_after(bb, x, x.before_begin(), ibx, n); 1542 if(l) *l = ibx; 1543 } 1544 } 1545 } 1546 1547 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1548 //! in order into *this according to std::less<value_type>. The merge is stable; 1549 //! that is, if an element from *this is equivalent to one from x, then the element 1550 //! from *this will precede the one from x. 1551 //! 1552 //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee. 1553 //! 1554 //! <b>Complexity</b>: This function is linear time: it performs at most 1555 //! size() + x.size() - 1 comparisons. 1556 //! 1557 //! <b>Note</b>: Iterators and references are not invalidated merge(slist_impl & x)1558 void merge(slist_impl& x) 1559 { this->merge(x, std::less<value_type>()); } 1560 1561 //! <b>Effects</b>: Reverses the order of elements in the list. 1562 //! 1563 //! <b>Throws</b>: Nothing. 1564 //! 1565 //! <b>Complexity</b>: This function is linear to the contained elements. 1566 //! 1567 //! <b>Note</b>: Iterators and references are not invalidated reverse()1568 void reverse() 1569 { 1570 if(cache_last && !this->empty()){ 1571 this->set_last_node(node_traits::get_next(this->get_root_node())); 1572 } 1573 this->priv_reverse(detail::bool_<linear>()); 1574 } 1575 1576 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1577 //! No destructors are called. 1578 //! 1579 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. 1580 //! 1581 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1582 //! 1583 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1584 //! and iterators to elements that are not removed remain valid. This function is 1585 //! linear time: it performs exactly size() comparisons for equality. remove(const_reference value)1586 void remove(const_reference value) 1587 { this->remove_if(detail::equal_to_value<const_reference>(value)); } 1588 1589 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1590 //! 1591 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1592 //! Disposer::operator()(pointer) is called for every removed element. 1593 //! 1594 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. 1595 //! 1596 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1597 //! 1598 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1599 //! and iterators to elements that are not removed remain valid. 1600 template<class Disposer> remove_and_dispose(const_reference value,Disposer disposer)1601 void remove_and_dispose(const_reference value, Disposer disposer) 1602 { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); } 1603 1604 //! <b>Effects</b>: Removes all the elements for which a specified 1605 //! predicate is satisfied. No destructors are called. 1606 //! 1607 //! <b>Throws</b>: If pred throws. Basic guarantee. 1608 //! 1609 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. 1610 //! 1611 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1612 //! and iterators to elements that are not removed remain valid. 1613 template<class Pred> remove_if(Pred pred)1614 void remove_if(Pred pred) 1615 { 1616 const node_ptr bbeg = this->get_root_node(); 1617 typename node_algorithms::stable_partition_info info; 1618 node_algorithms::stable_partition 1619 (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); 1620 //After cache last is set, slist invariants are preserved... 1621 if(cache_last){ 1622 this->set_last_node(info.new_last_node); 1623 } 1624 //...so erase can be safely called 1625 this->erase_after( const_iterator(bbeg, this->priv_value_traits_ptr()) 1626 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) 1627 , info.num_1st_partition); 1628 } 1629 1630 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1631 //! 1632 //! <b>Effects</b>: Removes all the elements for which a specified 1633 //! predicate is satisfied. 1634 //! Disposer::operator()(pointer) is called for every removed element. 1635 //! 1636 //! <b>Throws</b>: If pred throws. Basic guarantee. 1637 //! 1638 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1639 //! 1640 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1641 //! and iterators to elements that are not removed remain valid. 1642 template<class Pred, class Disposer> remove_and_dispose_if(Pred pred,Disposer disposer)1643 void remove_and_dispose_if(Pred pred, Disposer disposer) 1644 { 1645 const node_ptr bbeg = this->get_root_node(); 1646 typename node_algorithms::stable_partition_info info; 1647 node_algorithms::stable_partition 1648 (bbeg, this->get_end_node(), detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); 1649 //After cache last is set, slist invariants are preserved... 1650 if(cache_last){ 1651 this->set_last_node(info.new_last_node); 1652 } 1653 //...so erase can be safely called 1654 this->erase_after_and_dispose( const_iterator(bbeg, this->priv_value_traits_ptr()) 1655 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) 1656 , disposer); 1657 } 1658 1659 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1660 //! elements that are equal from the list. No destructors are called. 1661 //! 1662 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. 1663 //! 1664 //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()). 1665 //! 1666 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1667 //! and iterators to elements that are not removed remain valid. unique()1668 void unique() 1669 { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); } 1670 1671 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1672 //! elements that satisfy some binary predicate from the list. 1673 //! No destructors are called. 1674 //! 1675 //! <b>Throws</b>: If the predicate throws. Basic guarantee. 1676 //! 1677 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. 1678 //! 1679 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1680 //! and iterators to elements that are not removed remain valid. 1681 template<class BinaryPredicate> unique(BinaryPredicate pred)1682 void unique(BinaryPredicate pred) 1683 { this->unique_and_dispose(pred, detail::null_disposer()); } 1684 1685 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1686 //! 1687 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1688 //! elements that satisfy some binary predicate from the list. 1689 //! Disposer::operator()(pointer) is called for every removed element. 1690 //! 1691 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. 1692 //! 1693 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. 1694 //! 1695 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1696 //! and iterators to elements that are not removed remain valid. 1697 template<class Disposer> unique_and_dispose(Disposer disposer)1698 void unique_and_dispose(Disposer disposer) 1699 { this->unique(std::equal_to<value_type>(), disposer); } 1700 1701 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1702 //! 1703 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1704 //! elements that satisfy some binary predicate from the list. 1705 //! Disposer::operator()(pointer) is called for every removed element. 1706 //! 1707 //! <b>Throws</b>: If the predicate throws. Basic guarantee. 1708 //! 1709 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. 1710 //! 1711 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1712 //! and iterators to elements that are not removed remain valid. 1713 template<class BinaryPredicate, class Disposer> unique_and_dispose(BinaryPredicate pred,Disposer disposer)1714 void unique_and_dispose(BinaryPredicate pred, Disposer disposer) 1715 { 1716 const_iterator end_n(this->cend()); 1717 const_iterator bcur(this->cbegin()); 1718 if(bcur != end_n){ 1719 const_iterator cur(bcur); 1720 ++cur; 1721 while(cur != end_n) { 1722 if (pred(*bcur, *cur)){ 1723 cur = this->erase_after_and_dispose(bcur, disposer); 1724 } 1725 else{ 1726 bcur = cur; 1727 ++cur; 1728 } 1729 } 1730 if(cache_last){ 1731 this->set_last_node(bcur.pointed_node()); 1732 } 1733 } 1734 } 1735 1736 //! <b>Requires</b>: value must be a reference to a value inserted in a list. 1737 //! 1738 //! <b>Effects</b>: This function returns a const_iterator pointing to the element 1739 //! 1740 //! <b>Throws</b>: Nothing. 1741 //! 1742 //! <b>Complexity</b>: Constant time. 1743 //! 1744 //! <b>Note</b>: Iterators and references are not invalidated. 1745 //! This static function is available only if the <i>value traits</i> 1746 //! is stateless. s_iterator_to(reference value)1747 static iterator s_iterator_to(reference value) 1748 { 1749 BOOST_STATIC_ASSERT((!stateful_value_traits)); 1750 return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr()); 1751 } 1752 1753 //! <b>Requires</b>: value must be a const reference to a value inserted in a list. 1754 //! 1755 //! <b>Effects</b>: This function returns an iterator pointing to the element. 1756 //! 1757 //! <b>Throws</b>: Nothing. 1758 //! 1759 //! <b>Complexity</b>: Constant time. 1760 //! 1761 //! <b>Note</b>: Iterators and references are not invalidated. 1762 //! This static function is available only if the <i>value traits</i> 1763 //! is stateless. s_iterator_to(const_reference value)1764 static const_iterator s_iterator_to(const_reference value) 1765 { 1766 BOOST_STATIC_ASSERT((!stateful_value_traits)); 1767 reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); 1768 return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr()); 1769 } 1770 1771 //! <b>Requires</b>: value must be a reference to a value inserted in a list. 1772 //! 1773 //! <b>Effects</b>: This function returns a const_iterator pointing to the element 1774 //! 1775 //! <b>Throws</b>: Nothing. 1776 //! 1777 //! <b>Complexity</b>: Constant time. 1778 //! 1779 //! <b>Note</b>: Iterators and references are not invalidated. iterator_to(reference value)1780 iterator iterator_to(reference value) 1781 { 1782 BOOST_INTRUSIVE_INVARIANT_ASSERT(linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(value))); 1783 return iterator (this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); 1784 } 1785 1786 //! <b>Requires</b>: value must be a const reference to a value inserted in a list. 1787 //! 1788 //! <b>Effects</b>: This function returns an iterator pointing to the element. 1789 //! 1790 //! <b>Throws</b>: Nothing. 1791 //! 1792 //! <b>Complexity</b>: Constant time. 1793 //! 1794 //! <b>Note</b>: Iterators and references are not invalidated. iterator_to(const_reference value) const1795 const_iterator iterator_to(const_reference value) const 1796 { 1797 reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); 1798 BOOST_INTRUSIVE_INVARIANT_ASSERT (linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(r))); 1799 return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr()); 1800 } 1801 1802 //! <b>Returns</b>: The iterator to the element before i in the list. 1803 //! Returns the end-iterator, if either i is the begin-iterator or the 1804 //! list is empty. 1805 //! 1806 //! <b>Throws</b>: Nothing. 1807 //! 1808 //! <b>Complexity</b>: Linear to the number of elements before i. 1809 //! Constant if cache_last<> is true and i == end(). previous(iterator i)1810 iterator previous(iterator i) 1811 { return this->previous(this->cbefore_begin(), i); } 1812 1813 //! <b>Returns</b>: The const_iterator to the element before i in the list. 1814 //! Returns the end-const_iterator, if either i is the begin-const_iterator or 1815 //! the list is empty. 1816 //! 1817 //! <b>Throws</b>: Nothing. 1818 //! 1819 //! <b>Complexity</b>: Linear to the number of elements before i. 1820 //! Constant if cache_last<> is true and i == end(). previous(const_iterator i) const1821 const_iterator previous(const_iterator i) const 1822 { return this->previous(this->cbefore_begin(), i); } 1823 1824 //! <b>Returns</b>: The iterator to the element before i in the list, 1825 //! starting the search on element after prev_from. 1826 //! Returns the end-iterator, if either i is the begin-iterator or the 1827 //! list is empty. 1828 //! 1829 //! <b>Throws</b>: Nothing. 1830 //! 1831 //! <b>Complexity</b>: Linear to the number of elements before i. 1832 //! Constant if cache_last<> is true and i == end(). previous(const_iterator prev_from,iterator i)1833 iterator previous(const_iterator prev_from, iterator i) 1834 { return this->previous(prev_from, const_iterator(i)).unconst(); } 1835 1836 //! <b>Returns</b>: The const_iterator to the element before i in the list, 1837 //! starting the search on element after prev_from. 1838 //! Returns the end-const_iterator, if either i is the begin-const_iterator or 1839 //! the list is empty. 1840 //! 1841 //! <b>Throws</b>: Nothing. 1842 //! 1843 //! <b>Complexity</b>: Linear to the number of elements before i. 1844 //! Constant if cache_last<> is true and i == end(). previous(const_iterator prev_from,const_iterator i) const1845 const_iterator previous(const_iterator prev_from, const_iterator i) const 1846 { 1847 if(cache_last && (i.pointed_node() == this->get_end_node())){ 1848 return const_iterator(detail::uncast(this->get_last_node()), this->priv_value_traits_ptr()); 1849 } 1850 return const_iterator 1851 (node_algorithms::get_previous_node 1852 (prev_from.pointed_node(), i.pointed_node()), this->priv_value_traits_ptr()); 1853 } 1854 1855 ///@cond 1856 1857 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be 1858 //! before_begin(), and f and before_l belong to another slist. 1859 //! 1860 //! <b>Effects</b>: Transfers the range [f, before_l] to this 1861 //! list, after the element pointed by prev_pos. 1862 //! No destructors or copy constructors are called. 1863 //! 1864 //! <b>Throws</b>: Nothing. 1865 //! 1866 //! <b>Complexity</b>: Linear to the number of elements transferred 1867 //! if constant_time_size is true. Constant-time otherwise. 1868 //! 1869 //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now 1870 //! point to elements of this list. Iterators of this list and all the references are not invalidated. 1871 //! 1872 //! <b>Warning</b>: Experimental function, don't use it! incorporate_after(const_iterator prev_pos,const node_ptr & f,const node_ptr & before_l)1873 void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l) 1874 { 1875 if(constant_time_size) 1876 this->incorporate_after(prev_pos, f, before_l, node_algorithms::distance(f.pointed_node(), before_l.pointed_node())+1); 1877 else 1878 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l); 1879 } 1880 1881 //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be 1882 //! before_begin(), and f and before_l belong to another slist. 1883 //! n == distance(f, before_l) + 1. 1884 //! 1885 //! <b>Effects</b>: Transfers the range [f, before_l] to this 1886 //! list, after the element pointed by prev_pos. 1887 //! No destructors or copy constructors are called. 1888 //! 1889 //! <b>Throws</b>: Nothing. 1890 //! 1891 //! <b>Complexity</b>: Constant time. 1892 //! 1893 //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now 1894 //! point to elements of this list. Iterators of this list and all the references are not invalidated. 1895 //! 1896 //! <b>Warning</b>: Experimental function, don't use it! incorporate_after(const_iterator prev_pos,const node_ptr & f,const node_ptr & before_l,size_type n)1897 void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l, size_type n) 1898 { 1899 if(n){ 1900 BOOST_INTRUSIVE_INVARIANT_ASSERT(n > 0); 1901 BOOST_INTRUSIVE_INVARIANT_ASSERT 1902 (size_type(boost::intrusive::iterator_distance 1903 ( iterator(f, this->priv_value_traits_ptr()) 1904 , iterator(before_l, this->priv_value_traits_ptr()))) 1905 +1 == n); 1906 this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l); 1907 if(constant_time_size){ 1908 this->priv_size_traits().increase(n); 1909 } 1910 } 1911 } 1912 1913 ///@endcond 1914 1915 //! <b>Effects</b>: Asserts the integrity of the container. 1916 //! 1917 //! <b>Complexity</b>: Linear time. 1918 //! 1919 //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). 1920 //! Experimental function, interface might change in future versions. check() const1921 void check() const 1922 { 1923 const_node_ptr header_ptr = get_root_node(); 1924 // header's next is never null 1925 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr)); 1926 if (node_traits::get_next(header_ptr) == header_ptr) 1927 { 1928 if (constant_time_size) 1929 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0); 1930 return; 1931 } 1932 size_t node_count = 0; 1933 const_node_ptr p = header_ptr; 1934 while (true) 1935 { 1936 const_node_ptr next_p = node_traits::get_next(p); 1937 if (!linear) 1938 { 1939 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p); 1940 } 1941 else 1942 { 1943 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p != header_ptr); 1944 } 1945 if ((!linear && next_p == header_ptr) || (linear && !next_p)) 1946 { 1947 if (cache_last) 1948 BOOST_INTRUSIVE_INVARIANT_ASSERT(get_last_node() == p); 1949 break; 1950 } 1951 p = next_p; 1952 ++node_count; 1953 } 1954 if (constant_time_size) 1955 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count); 1956 } 1957 1958 operator ==(const slist_impl & x,const slist_impl & y)1959 friend bool operator==(const slist_impl &x, const slist_impl &y) 1960 { 1961 if(constant_time_size && x.size() != y.size()){ 1962 return false; 1963 } 1964 return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); 1965 } 1966 operator !=(const slist_impl & x,const slist_impl & y)1967 friend bool operator!=(const slist_impl &x, const slist_impl &y) 1968 { return !(x == y); } 1969 operator <(const slist_impl & x,const slist_impl & y)1970 friend bool operator<(const slist_impl &x, const slist_impl &y) 1971 { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1972 operator >(const slist_impl & x,const slist_impl & y)1973 friend bool operator>(const slist_impl &x, const slist_impl &y) 1974 { return y < x; } 1975 operator <=(const slist_impl & x,const slist_impl & y)1976 friend bool operator<=(const slist_impl &x, const slist_impl &y) 1977 { return !(y < x); } 1978 operator >=(const slist_impl & x,const slist_impl & y)1979 friend bool operator>=(const slist_impl &x, const slist_impl &y) 1980 { return !(x < y); } 1981 swap(slist_impl & x,slist_impl & y)1982 friend void swap(slist_impl &x, slist_impl &y) 1983 { x.swap(y); } 1984 1985 private: priv_splice_after(const node_ptr & prev_pos_n,slist_impl & x,const node_ptr & before_f_n,const node_ptr & before_l_n)1986 void priv_splice_after(const node_ptr & prev_pos_n, slist_impl &x, const node_ptr & before_f_n, const node_ptr & before_l_n) 1987 { 1988 if (cache_last && (before_f_n != before_l_n)){ 1989 if(prev_pos_n == this->get_last_node()){ 1990 this->set_last_node(before_l_n); 1991 } 1992 if(&x != this && node_traits::get_next(before_l_n) == x.get_end_node()){ 1993 x.set_last_node(before_f_n); 1994 } 1995 } 1996 node_algorithms::transfer_after(prev_pos_n, before_f_n, before_l_n); 1997 } 1998 priv_incorporate_after(const node_ptr & prev_pos_n,const node_ptr & first_n,const node_ptr & before_l_n)1999 void priv_incorporate_after(const node_ptr & prev_pos_n, const node_ptr & first_n, const node_ptr & before_l_n) 2000 { 2001 if(cache_last){ 2002 if(prev_pos_n == this->get_last_node()){ 2003 this->set_last_node(before_l_n); 2004 } 2005 } 2006 node_algorithms::incorporate_after(prev_pos_n, first_n, before_l_n); 2007 } 2008 priv_reverse(detail::bool_<false>)2009 void priv_reverse(detail::bool_<false>) 2010 { node_algorithms::reverse(this->get_root_node()); } 2011 priv_reverse(detail::bool_<true>)2012 void priv_reverse(detail::bool_<true>) 2013 { 2014 node_ptr new_first = node_algorithms::reverse 2015 (node_traits::get_next(this->get_root_node())); 2016 node_traits::set_next(this->get_root_node(), new_first); 2017 } 2018 priv_shift_backwards(size_type n,detail::bool_<false>)2019 void priv_shift_backwards(size_type n, detail::bool_<false>) 2020 { 2021 node_ptr l = node_algorithms::move_forward(this->get_root_node(), (std::size_t)n); 2022 if(cache_last && l){ 2023 this->set_last_node(l); 2024 } 2025 } 2026 priv_shift_backwards(size_type n,detail::bool_<true>)2027 void priv_shift_backwards(size_type n, detail::bool_<true>) 2028 { 2029 std::pair<node_ptr, node_ptr> ret( 2030 node_algorithms::move_first_n_forward 2031 (node_traits::get_next(this->get_root_node()), (std::size_t)n)); 2032 if(ret.first){ 2033 node_traits::set_next(this->get_root_node(), ret.first); 2034 if(cache_last){ 2035 this->set_last_node(ret.second); 2036 } 2037 } 2038 } 2039 priv_shift_forward(size_type n,detail::bool_<false>)2040 void priv_shift_forward(size_type n, detail::bool_<false>) 2041 { 2042 node_ptr l = node_algorithms::move_backwards(this->get_root_node(), (std::size_t)n); 2043 if(cache_last && l){ 2044 this->set_last_node(l); 2045 } 2046 } 2047 priv_shift_forward(size_type n,detail::bool_<true>)2048 void priv_shift_forward(size_type n, detail::bool_<true>) 2049 { 2050 std::pair<node_ptr, node_ptr> ret( 2051 node_algorithms::move_first_n_backwards 2052 (node_traits::get_next(this->get_root_node()), (std::size_t)n)); 2053 if(ret.first){ 2054 node_traits::set_next(this->get_root_node(), ret.first); 2055 if(cache_last){ 2056 this->set_last_node(ret.second); 2057 } 2058 } 2059 } 2060 priv_swap_cache_last(slist_impl * this_impl,slist_impl * other_impl)2061 static void priv_swap_cache_last(slist_impl *this_impl, slist_impl *other_impl) 2062 { 2063 bool other_was_empty = false; 2064 if(this_impl->empty()){ 2065 //Check if both are empty or 2066 if(other_impl->empty()) 2067 return; 2068 //If this is empty swap pointers 2069 slist_impl *tmp = this_impl; 2070 this_impl = other_impl; 2071 other_impl = tmp; 2072 other_was_empty = true; 2073 } 2074 else{ 2075 other_was_empty = other_impl->empty(); 2076 } 2077 2078 //Precondition: this is not empty 2079 node_ptr other_old_last(other_impl->get_last_node()); 2080 node_ptr other_bfirst(other_impl->get_root_node()); 2081 node_ptr this_bfirst(this_impl->get_root_node()); 2082 node_ptr this_old_last(this_impl->get_last_node()); 2083 2084 //Move all nodes from this to other's beginning 2085 node_algorithms::transfer_after(other_bfirst, this_bfirst, this_old_last); 2086 other_impl->set_last_node(this_old_last); 2087 2088 if(other_was_empty){ 2089 this_impl->set_last_node(this_bfirst); 2090 } 2091 else{ 2092 //Move trailing nodes from other to this 2093 node_algorithms::transfer_after(this_bfirst, this_old_last, other_old_last); 2094 this_impl->set_last_node(other_old_last); 2095 } 2096 } 2097 2098 //circular version priv_swap_lists(const node_ptr & this_node,const node_ptr & other_node,detail::bool_<false>)2099 static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<false>) 2100 { node_algorithms::swap_nodes(this_node, other_node); } 2101 2102 //linear version priv_swap_lists(const node_ptr & this_node,const node_ptr & other_node,detail::bool_<true>)2103 static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<true>) 2104 { node_algorithms::swap_trailing_nodes(this_node, other_node); } 2105 priv_container_from_end_iterator(const const_iterator & end_iterator)2106 static slist_impl &priv_container_from_end_iterator(const const_iterator &end_iterator) 2107 { 2108 //Obtaining the container from the end iterator is not possible with linear 2109 //singly linked lists (because "end" is represented by the null pointer) 2110 BOOST_STATIC_ASSERT(!linear); 2111 BOOST_STATIC_ASSERT((has_container_from_iterator)); 2112 node_ptr p = end_iterator.pointed_node(); 2113 header_holder_type* h = header_holder_type::get_holder(p); 2114 header_holder_plus_last_t* hpl = detail::parent_from_member< header_holder_plus_last_t, header_holder_type> 2115 (h, &header_holder_plus_last_t::header_holder_); 2116 root_plus_size* r = static_cast< root_plus_size* >(hpl); 2117 data_t *d = detail::parent_from_member<data_t, root_plus_size> 2118 ( r, &data_t::root_plus_size_); 2119 slist_impl *s = detail::parent_from_member<slist_impl, data_t>(d, &slist_impl::data_); 2120 return *s; 2121 } 2122 }; 2123 2124 //! Helper metafunction to define a \c slist that yields to the same type when the 2125 //! same options (either explicitly or implicitly) are used. 2126 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2127 template<class T, class ...Options> 2128 #else 2129 template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void, class O6 = void> 2130 #endif 2131 struct make_slist 2132 { 2133 /// @cond 2134 typedef typename pack_options 2135 < slist_defaults, 2136 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2137 O1, O2, O3, O4, O5, O6 2138 #else 2139 Options... 2140 #endif 2141 >::type packed_options; 2142 2143 typedef typename detail::get_value_traits 2144 <T, typename packed_options::proto_value_traits>::type value_traits; 2145 typedef slist_impl 2146 < value_traits 2147 , typename packed_options::size_type 2148 , (std::size_t(packed_options::linear)*slist_bool_flags::linear_pos) 2149 |(std::size_t(packed_options::constant_time_size)*slist_bool_flags::constant_time_size_pos) 2150 |(std::size_t(packed_options::cache_last)*slist_bool_flags::cache_last_pos) 2151 , typename packed_options::header_holder_type 2152 > implementation_defined; 2153 /// @endcond 2154 typedef implementation_defined type; 2155 }; 2156 2157 2158 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 2159 2160 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2161 template<class T, class O1, class O2, class O3, class O4, class O5, class O6> 2162 #else 2163 template<class T, class ...Options> 2164 #endif 2165 class slist 2166 : public make_slist<T, 2167 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2168 O1, O2, O3, O4, O5, O6 2169 #else 2170 Options... 2171 #endif 2172 >::type 2173 { 2174 typedef typename make_slist 2175 <T, 2176 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 2177 O1, O2, O3, O4, O5, O6 2178 #else 2179 Options... 2180 #endif 2181 >::type Base; 2182 //Assert if passed value traits are compatible with the type 2183 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value)); 2184 BOOST_MOVABLE_BUT_NOT_COPYABLE(slist) 2185 2186 public: 2187 typedef typename Base::value_traits value_traits; 2188 typedef typename Base::iterator iterator; 2189 typedef typename Base::const_iterator const_iterator; 2190 typedef typename Base::size_type size_type; 2191 typedef typename Base::node_ptr node_ptr; 2192 slist(const value_traits & v_traits=value_traits ())2193 explicit slist(const value_traits &v_traits = value_traits()) 2194 : Base(v_traits) 2195 {} 2196 2197 struct incorporate_t{}; 2198 slist(const node_ptr & f,const node_ptr & before_l,size_type n,const value_traits & v_traits=value_traits ())2199 slist( const node_ptr & f, const node_ptr & before_l 2200 , size_type n, const value_traits &v_traits = value_traits()) 2201 : Base(f, before_l, n, v_traits) 2202 {} 2203 2204 template<class Iterator> slist(Iterator b,Iterator e,const value_traits & v_traits=value_traits ())2205 slist(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) 2206 : Base(b, e, v_traits) 2207 {} 2208 slist(BOOST_RV_REF (slist)x)2209 slist(BOOST_RV_REF(slist) x) 2210 : Base(BOOST_MOVE_BASE(Base, x)) 2211 {} 2212 operator =(BOOST_RV_REF (slist)x)2213 slist& operator=(BOOST_RV_REF(slist) x) 2214 { return static_cast<slist &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 2215 2216 template <class Cloner, class Disposer> clone_from(const slist & src,Cloner cloner,Disposer disposer)2217 void clone_from(const slist &src, Cloner cloner, Disposer disposer) 2218 { Base::clone_from(src, cloner, disposer); } 2219 2220 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (slist)src,Cloner cloner,Disposer disposer)2221 void clone_from(BOOST_RV_REF(slist) src, Cloner cloner, Disposer disposer) 2222 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 2223 container_from_end_iterator(iterator end_iterator)2224 static slist &container_from_end_iterator(iterator end_iterator) 2225 { return static_cast<slist &>(Base::container_from_end_iterator(end_iterator)); } 2226 container_from_end_iterator(const_iterator end_iterator)2227 static const slist &container_from_end_iterator(const_iterator end_iterator) 2228 { return static_cast<const slist &>(Base::container_from_end_iterator(end_iterator)); } 2229 }; 2230 2231 #endif 2232 2233 } //namespace intrusive 2234 } //namespace boost 2235 2236 #include <boost/intrusive/detail/config_end.hpp> 2237 2238 #endif //BOOST_INTRUSIVE_SLIST_HPP 2239