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