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