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_LIST_HPP 15 #define BOOST_INTRUSIVE_LIST_HPP 16 17 #include <boost/intrusive/detail/config_begin.hpp> 18 #include <boost/intrusive/intrusive_fwd.hpp> 19 #include <boost/intrusive/detail/assert.hpp> 20 #include <boost/intrusive/list_hook.hpp> 21 #include <boost/intrusive/circular_list_algorithms.hpp> 22 #include <boost/intrusive/pointer_traits.hpp> 23 #include <boost/intrusive/detail/mpl.hpp> 24 #include <boost/intrusive/link_mode.hpp> 25 #include <boost/intrusive/detail/get_value_traits.hpp> 26 #include <boost/intrusive/detail/is_stateful_value_traits.hpp> 27 #include <boost/intrusive/detail/default_header_holder.hpp> 28 #include <boost/intrusive/detail/reverse_iterator.hpp> 29 #include <boost/intrusive/detail/uncast.hpp> 30 #include <boost/intrusive/detail/list_iterator.hpp> 31 #include <boost/intrusive/detail/array_initializer.hpp> 32 #include <boost/intrusive/detail/exception_disposer.hpp> 33 #include <boost/intrusive/detail/equal_to_value.hpp> 34 #include <boost/intrusive/detail/key_nodeptr_comp.hpp> 35 #include <boost/intrusive/detail/simple_disposers.hpp> 36 #include <boost/intrusive/detail/size_holder.hpp> 37 #include <boost/intrusive/detail/algorithm.hpp> 38 39 #include <boost/move/utility_core.hpp> 40 #include <boost/static_assert.hpp> 41 42 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//std::less 43 #include <cstddef> //std::size_t, etc. 44 45 #if defined(BOOST_HAS_PRAGMA_ONCE) 46 # pragma once 47 #endif 48 49 namespace boost { 50 namespace intrusive { 51 52 /// @cond 53 54 struct default_list_hook_applier 55 { template <class T> struct apply{ typedef typename T::default_list_hook type; }; }; 56 57 template<> 58 struct is_default_hook_tag<default_list_hook_applier> 59 { static const bool value = true; }; 60 61 struct list_defaults 62 { 63 typedef default_list_hook_applier proto_value_traits; 64 static const bool constant_time_size = true; 65 typedef std::size_t size_type; 66 typedef void header_holder_type; 67 }; 68 69 /// @endcond 70 71 //! The class template list is an intrusive container that mimics most of the 72 //! interface of std::list as described in the C++ standard. 73 //! 74 //! The template parameter \c T is the type to be managed by the container. 75 //! The user can specify additional options and if no options are provided 76 //! default options are used. 77 //! 78 //! The container supports the following options: 79 //! \c base_hook<>/member_hook<>/value_traits<>, 80 //! \c constant_time_size<> and \c size_type<>. 81 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 82 template<class T, class ...Options> 83 #else 84 template <class ValueTraits, class SizeType, bool ConstantTimeSize, typename HeaderHolder> 85 #endif 86 class list_impl 87 { 88 //Public typedefs 89 public: 90 typedef ValueTraits value_traits; 91 typedef typename value_traits::pointer pointer; 92 typedef typename value_traits::const_pointer const_pointer; 93 typedef typename pointer_traits<pointer>::element_type value_type; 94 typedef typename pointer_traits<pointer>::reference reference; 95 typedef typename pointer_traits<const_pointer>::reference const_reference; 96 typedef typename pointer_traits<pointer>::difference_type difference_type; 97 typedef SizeType size_type; 98 typedef list_iterator<value_traits, false> iterator; 99 typedef list_iterator<value_traits, true> const_iterator; 100 typedef boost::intrusive::reverse_iterator<iterator> reverse_iterator; 101 typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_iterator; 102 typedef typename value_traits::node_traits node_traits; 103 typedef typename node_traits::node node; 104 typedef typename node_traits::node_ptr node_ptr; 105 typedef typename node_traits::const_node_ptr const_node_ptr; 106 typedef circular_list_algorithms<node_traits> node_algorithms; 107 typedef typename detail::get_header_holder_type 108 < value_traits, HeaderHolder >::type header_holder_type; 109 110 static const bool constant_time_size = ConstantTimeSize; 111 static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; 112 static const bool has_container_from_iterator = 113 detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; 114 115 /// @cond 116 117 private: 118 typedef detail::size_holder<constant_time_size, size_type> size_traits; 119 120 //noncopyable 121 BOOST_MOVABLE_BUT_NOT_COPYABLE(list_impl) 122 123 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; 124 125 //Constant-time size is incompatible with auto-unlink hooks! 126 BOOST_STATIC_ASSERT(!(constant_time_size && 127 ((int)value_traits::link_mode == (int)auto_unlink) 128 )); 129 get_root_node()130 node_ptr get_root_node() 131 { return data_.root_plus_size_.m_header.get_node(); } 132 get_root_node() const133 const_node_ptr get_root_node() const 134 { return data_.root_plus_size_.m_header.get_node(); } 135 136 struct root_plus_size : public size_traits 137 { 138 header_holder_type m_header; 139 }; 140 141 struct data_t : public value_traits 142 { 143 typedef typename list_impl::value_traits value_traits; data_tboost::intrusive::list_impl::data_t144 explicit data_t(const value_traits &val_traits) 145 : value_traits(val_traits) 146 {} 147 148 root_plus_size root_plus_size_; 149 } data_; 150 priv_size_traits()151 size_traits &priv_size_traits() 152 { return data_.root_plus_size_; } 153 priv_size_traits() const154 const size_traits &priv_size_traits() const 155 { return data_.root_plus_size_; } 156 priv_value_traits() const157 const value_traits &priv_value_traits() const 158 { return data_; } 159 priv_value_traits()160 value_traits &priv_value_traits() 161 { return data_; } 162 163 typedef typename boost::intrusive::value_traits_pointers 164 <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; 165 priv_value_traits_ptr() const166 const_value_traits_ptr priv_value_traits_ptr() const 167 { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } 168 169 /// @endcond 170 171 public: 172 173 //! <b>Effects</b>: constructs an empty list. 174 //! 175 //! <b>Complexity</b>: Constant 176 //! 177 //! <b>Throws</b>: If value_traits::node_traits::node 178 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). list_impl()179 list_impl() 180 : data_(value_traits()) 181 { 182 this->priv_size_traits().set_size(size_type(0)); 183 node_algorithms::init_header(this->get_root_node()); 184 } 185 186 //! <b>Effects</b>: constructs an empty list. 187 //! 188 //! <b>Complexity</b>: Constant 189 //! 190 //! <b>Throws</b>: If value_traits::node_traits::node 191 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). list_impl(const value_traits & v_traits)192 explicit list_impl(const value_traits &v_traits) 193 : data_(v_traits) 194 { 195 this->priv_size_traits().set_size(size_type(0)); 196 node_algorithms::init_header(this->get_root_node()); 197 } 198 199 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. 200 //! 201 //! <b>Effects</b>: Constructs a list equal to the range [first,last). 202 //! 203 //! <b>Complexity</b>: Linear in distance(b, e). No copy constructors are called. 204 //! 205 //! <b>Throws</b>: If value_traits::node_traits::node 206 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). 207 template<class Iterator> list_impl(Iterator b,Iterator e,const value_traits & v_traits=value_traits ())208 list_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) 209 : data_(v_traits) 210 { 211 //nothrow, no need to rollback to release elements on exception 212 this->priv_size_traits().set_size(size_type(0)); 213 node_algorithms::init_header(this->get_root_node()); 214 //nothrow, no need to rollback to release elements on exception 215 this->insert(this->cend(), b, e); 216 } 217 218 //! <b>Effects</b>: Constructs a container moving resources from another container. 219 //! Internal value traits are move constructed and 220 //! nodes belonging to x (except the node representing the "end") are linked to *this. 221 //! 222 //! <b>Complexity</b>: Constant. 223 //! 224 //! <b>Throws</b>: If value_traits::node_traits::node's 225 //! move constructor throws (this does not happen with predefined Boost.Intrusive hooks) 226 //! or the move constructor of value traits throws. list_impl(BOOST_RV_REF (list_impl)x)227 list_impl(BOOST_RV_REF(list_impl) x) 228 : data_(::boost::move(x.priv_value_traits())) 229 { 230 this->priv_size_traits().set_size(size_type(0)); 231 node_algorithms::init_header(this->get_root_node()); 232 //nothrow, no need to rollback to release elements on exception 233 this->swap(x); 234 } 235 236 //! <b>Effects</b>: Equivalent to swap 237 //! operator =(BOOST_RV_REF (list_impl)x)238 list_impl& operator=(BOOST_RV_REF(list_impl) x) 239 { this->swap(x); return *this; } 240 241 //! <b>Effects</b>: If it's not a safe-mode or an auto-unlink value_type 242 //! the destructor does nothing 243 //! (ie. no code is generated). Otherwise it detaches all elements from this. 244 //! In this case the objects in the list are not deleted (i.e. no destructors 245 //! are called), but the hooks according to the ValueTraits template parameter 246 //! are set to their default value. 247 //! 248 //! <b>Complexity</b>: Linear to the number of elements in the list, if 249 //! it's a safe-mode or auto-unlink value . Otherwise constant. ~list_impl()250 ~list_impl() 251 { 252 if(is_safe_autounlink<ValueTraits::link_mode>::value){ 253 this->clear(); 254 node_algorithms::init(this->get_root_node()); 255 } 256 } 257 258 //! <b>Requires</b>: value must be an lvalue. 259 //! 260 //! <b>Effects</b>: Inserts the value in the back of the list. 261 //! No copy constructors are called. 262 //! 263 //! <b>Throws</b>: Nothing. 264 //! 265 //! <b>Complexity</b>: Constant. 266 //! 267 //! <b>Note</b>: Does not affect the validity of iterators and references. push_back(reference value)268 void push_back(reference value) 269 { 270 node_ptr to_insert = priv_value_traits().to_node_ptr(value); 271 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); 272 node_algorithms::link_before(this->get_root_node(), to_insert); 273 this->priv_size_traits().increment(); 274 } 275 276 //! <b>Requires</b>: value must be an lvalue. 277 //! 278 //! <b>Effects</b>: Inserts the value in the front of the list. 279 //! No copy constructors are called. 280 //! 281 //! <b>Throws</b>: Nothing. 282 //! 283 //! <b>Complexity</b>: Constant. 284 //! 285 //! <b>Note</b>: Does not affect the validity of iterators and references. push_front(reference value)286 void push_front(reference value) 287 { 288 node_ptr to_insert = priv_value_traits().to_node_ptr(value); 289 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); 290 node_algorithms::link_before(node_traits::get_next(this->get_root_node()), to_insert); 291 this->priv_size_traits().increment(); 292 } 293 294 //! <b>Effects</b>: Erases the last element of the list. 295 //! No destructors are called. 296 //! 297 //! <b>Throws</b>: Nothing. 298 //! 299 //! <b>Complexity</b>: Constant. 300 //! 301 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. pop_back()302 void pop_back() 303 { return this->pop_back_and_dispose(detail::null_disposer()); } 304 305 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 306 //! 307 //! <b>Effects</b>: Erases the last element of the list. 308 //! No destructors are called. 309 //! Disposer::operator()(pointer) is called for the removed element. 310 //! 311 //! <b>Throws</b>: Nothing. 312 //! 313 //! <b>Complexity</b>: Constant. 314 //! 315 //! <b>Note</b>: Invalidates the iterators to the erased element. 316 template<class Disposer> pop_back_and_dispose(Disposer disposer)317 void pop_back_and_dispose(Disposer disposer) 318 { 319 node_ptr to_erase = node_traits::get_previous(this->get_root_node()); 320 node_algorithms::unlink(to_erase); 321 this->priv_size_traits().decrement(); 322 if(safemode_or_autounlink) 323 node_algorithms::init(to_erase); 324 disposer(priv_value_traits().to_value_ptr(to_erase)); 325 } 326 327 //! <b>Effects</b>: Erases the first element of the list. 328 //! No destructors are called. 329 //! 330 //! <b>Throws</b>: Nothing. 331 //! 332 //! <b>Complexity</b>: Constant. 333 //! 334 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. pop_front()335 void pop_front() 336 { return this->pop_front_and_dispose(detail::null_disposer()); } 337 338 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 339 //! 340 //! <b>Effects</b>: Erases the first element of the list. 341 //! No destructors are called. 342 //! Disposer::operator()(pointer) is called for the removed element. 343 //! 344 //! <b>Throws</b>: Nothing. 345 //! 346 //! <b>Complexity</b>: Constant. 347 //! 348 //! <b>Note</b>: Invalidates the iterators to the erased element. 349 template<class Disposer> pop_front_and_dispose(Disposer disposer)350 void pop_front_and_dispose(Disposer disposer) 351 { 352 node_ptr to_erase = node_traits::get_next(this->get_root_node()); 353 node_algorithms::unlink(to_erase); 354 this->priv_size_traits().decrement(); 355 if(safemode_or_autounlink) 356 node_algorithms::init(to_erase); 357 disposer(priv_value_traits().to_value_ptr(to_erase)); 358 } 359 360 //! <b>Effects</b>: Returns a reference to the first element of the list. 361 //! 362 //! <b>Throws</b>: Nothing. 363 //! 364 //! <b>Complexity</b>: Constant. front()365 reference front() 366 { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } 367 368 //! <b>Effects</b>: Returns a const_reference to the first element of the list. 369 //! 370 //! <b>Throws</b>: Nothing. 371 //! 372 //! <b>Complexity</b>: Constant. front() const373 const_reference front() const 374 { return *priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } 375 376 //! <b>Effects</b>: Returns a reference to the last element of the list. 377 //! 378 //! <b>Throws</b>: Nothing. 379 //! 380 //! <b>Complexity</b>: Constant. back()381 reference back() 382 { return *priv_value_traits().to_value_ptr(node_traits::get_previous(this->get_root_node())); } 383 384 //! <b>Effects</b>: Returns a const_reference to the last element of the list. 385 //! 386 //! <b>Throws</b>: Nothing. 387 //! 388 //! <b>Complexity</b>: Constant. back() const389 const_reference back() const 390 { return *priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_previous(this->get_root_node()))); } 391 392 //! <b>Effects</b>: Returns an iterator to the first element contained in the list. 393 //! 394 //! <b>Throws</b>: Nothing. 395 //! 396 //! <b>Complexity</b>: Constant. begin()397 iterator begin() 398 { return iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } 399 400 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 401 //! 402 //! <b>Throws</b>: Nothing. 403 //! 404 //! <b>Complexity</b>: Constant. begin() const405 const_iterator begin() const 406 { return this->cbegin(); } 407 408 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. 409 //! 410 //! <b>Throws</b>: Nothing. 411 //! 412 //! <b>Complexity</b>: Constant. cbegin() const413 const_iterator cbegin() const 414 { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } 415 416 //! <b>Effects</b>: Returns an iterator to the end of the list. 417 //! 418 //! <b>Throws</b>: Nothing. 419 //! 420 //! <b>Complexity</b>: Constant. end()421 iterator end() 422 { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); } 423 424 //! <b>Effects</b>: Returns a const_iterator to the end of the list. 425 //! 426 //! <b>Throws</b>: Nothing. 427 //! 428 //! <b>Complexity</b>: Constant. end() const429 const_iterator end() const 430 { return this->cend(); } 431 432 //! <b>Effects</b>: Returns a constant iterator to the end of the list. 433 //! 434 //! <b>Throws</b>: Nothing. 435 //! 436 //! <b>Complexity</b>: Constant. cend() const437 const_iterator cend() const 438 { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); } 439 440 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 441 //! of the reversed list. 442 //! 443 //! <b>Throws</b>: Nothing. 444 //! 445 //! <b>Complexity</b>: Constant. rbegin()446 reverse_iterator rbegin() 447 { return reverse_iterator(this->end()); } 448 449 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 450 //! of the reversed list. 451 //! 452 //! <b>Throws</b>: Nothing. 453 //! 454 //! <b>Complexity</b>: Constant. rbegin() const455 const_reverse_iterator rbegin() const 456 { return this->crbegin(); } 457 458 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 459 //! of the reversed list. 460 //! 461 //! <b>Throws</b>: Nothing. 462 //! 463 //! <b>Complexity</b>: Constant. crbegin() const464 const_reverse_iterator crbegin() const 465 { return const_reverse_iterator(end()); } 466 467 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 468 //! of the reversed list. 469 //! 470 //! <b>Throws</b>: Nothing. 471 //! 472 //! <b>Complexity</b>: Constant. rend()473 reverse_iterator rend() 474 { return reverse_iterator(begin()); } 475 476 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 477 //! of the reversed list. 478 //! 479 //! <b>Throws</b>: Nothing. 480 //! 481 //! <b>Complexity</b>: Constant. rend() const482 const_reverse_iterator rend() const 483 { return this->crend(); } 484 485 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 486 //! of the reversed list. 487 //! 488 //! <b>Throws</b>: Nothing. 489 //! 490 //! <b>Complexity</b>: Constant. crend() const491 const_reverse_iterator crend() const 492 { return const_reverse_iterator(this->begin()); } 493 494 //! <b>Precondition</b>: end_iterator must be a valid end iterator 495 //! of list. 496 //! 497 //! <b>Effects</b>: Returns a const reference to the list associated to the end iterator 498 //! 499 //! <b>Throws</b>: Nothing. 500 //! 501 //! <b>Complexity</b>: Constant. container_from_end_iterator(iterator end_iterator)502 static list_impl &container_from_end_iterator(iterator end_iterator) 503 { return list_impl::priv_container_from_end_iterator(end_iterator); } 504 505 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator 506 //! of list. 507 //! 508 //! <b>Effects</b>: Returns a const reference to the list associated to the end iterator 509 //! 510 //! <b>Throws</b>: Nothing. 511 //! 512 //! <b>Complexity</b>: Constant. container_from_end_iterator(const_iterator end_iterator)513 static const list_impl &container_from_end_iterator(const_iterator end_iterator) 514 { return list_impl::priv_container_from_end_iterator(end_iterator); } 515 516 //! <b>Effects</b>: Returns the number of the elements contained in the list. 517 //! 518 //! <b>Throws</b>: Nothing. 519 //! 520 //! <b>Complexity</b>: Linear to the number of elements contained in the list. 521 //! if constant-time size option is disabled. Constant time otherwise. 522 //! 523 //! <b>Note</b>: Does not affect the validity of iterators and references. size() const524 size_type size() const 525 { 526 if(constant_time_size) 527 return this->priv_size_traits().get_size(); 528 else 529 return node_algorithms::count(this->get_root_node()) - 1; 530 } 531 532 //! <b>Effects</b>: Returns true if the list contains no elements. 533 //! 534 //! <b>Throws</b>: Nothing. 535 //! 536 //! <b>Complexity</b>: Constant. 537 //! 538 //! <b>Note</b>: Does not affect the validity of iterators and references. empty() const539 bool empty() const 540 { return node_algorithms::unique(this->get_root_node()); } 541 542 //! <b>Effects</b>: Swaps the elements of x and *this. 543 //! 544 //! <b>Throws</b>: Nothing. 545 //! 546 //! <b>Complexity</b>: Constant. 547 //! 548 //! <b>Note</b>: Does not affect the validity of iterators and references. swap(list_impl & other)549 void swap(list_impl& other) 550 { 551 node_algorithms::swap_nodes(this->get_root_node(), other.get_root_node()); 552 this->priv_size_traits().swap(other.priv_size_traits()); 553 } 554 555 //! <b>Effects</b>: Moves backwards all the elements, so that the first 556 //! element becomes the second, the second becomes the third... 557 //! the last element becomes the first one. 558 //! 559 //! <b>Throws</b>: Nothing. 560 //! 561 //! <b>Complexity</b>: Linear to the number of shifts. 562 //! 563 //! <b>Note</b>: Does not affect the validity of iterators and references. shift_backwards(size_type n=1)564 void shift_backwards(size_type n = 1) 565 { node_algorithms::move_forward(this->get_root_node(), n); } 566 567 //! <b>Effects</b>: Moves forward all the elements, so that the second 568 //! element becomes the first, the third becomes the second... 569 //! the first element becomes the last one. 570 //! 571 //! <b>Throws</b>: Nothing. 572 //! 573 //! <b>Complexity</b>: Linear to the number of shifts. 574 //! 575 //! <b>Note</b>: Does not affect the validity of iterators and references. shift_forward(size_type n=1)576 void shift_forward(size_type n = 1) 577 { node_algorithms::move_backwards(this->get_root_node(), n); } 578 579 //! <b>Effects</b>: Erases the element pointed by i of the list. 580 //! No destructors are called. 581 //! 582 //! <b>Returns</b>: the first element remaining beyond the removed element, 583 //! or end() if no such element exists. 584 //! 585 //! <b>Throws</b>: Nothing. 586 //! 587 //! <b>Complexity</b>: Constant. 588 //! 589 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 590 //! erased element. erase(const_iterator i)591 iterator erase(const_iterator i) 592 { return this->erase_and_dispose(i, detail::null_disposer()); } 593 594 //! <b>Requires</b>: b and e must be valid iterators to elements in *this. 595 //! 596 //! <b>Effects</b>: Erases the element range pointed by b and e 597 //! No destructors are called. 598 //! 599 //! <b>Returns</b>: the first element remaining beyond the removed elements, 600 //! or end() if no such element exists. 601 //! 602 //! <b>Throws</b>: Nothing. 603 //! 604 //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode 605 //! or auto-unlink value, or constant-time size is enabled. Constant-time otherwise. 606 //! 607 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 608 //! erased elements. erase(const_iterator b,const_iterator e)609 iterator erase(const_iterator b, const_iterator e) 610 { 611 if(safemode_or_autounlink || constant_time_size){ 612 return this->erase_and_dispose(b, e, detail::null_disposer()); 613 } 614 else{ 615 node_algorithms::unlink(b.pointed_node(), e.pointed_node()); 616 return e.unconst(); 617 } 618 } 619 620 //! <b>Requires</b>: b and e must be valid iterators to elements in *this. 621 //! n must be distance(b, e). 622 //! 623 //! <b>Effects</b>: Erases the element range pointed by b and e 624 //! No destructors are called. 625 //! 626 //! <b>Returns</b>: the first element remaining beyond the removed elements, 627 //! or end() if no such element exists. 628 //! 629 //! <b>Throws</b>: Nothing. 630 //! 631 //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode 632 //! or auto-unlink value is enabled. Constant-time otherwise. 633 //! 634 //! <b>Note</b>: Invalidates the iterators (but not the references) to the 635 //! erased elements. erase(const_iterator b,const_iterator e,size_type n)636 iterator erase(const_iterator b, const_iterator e, size_type n) 637 { 638 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_algorithms::distance(b.pointed_node(), e.pointed_node()) == n); 639 if(safemode_or_autounlink || constant_time_size){ 640 return this->erase_and_dispose(b, e, detail::null_disposer()); 641 } 642 else{ 643 if(constant_time_size){ 644 this->priv_size_traits().decrease(n); 645 } 646 node_algorithms::unlink(b.pointed_node(), e.pointed_node()); 647 return e.unconst(); 648 } 649 } 650 651 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 652 //! 653 //! <b>Effects</b>: Erases the element pointed by i of the list. 654 //! No destructors are called. 655 //! Disposer::operator()(pointer) is called for the removed element. 656 //! 657 //! <b>Returns</b>: the first element remaining beyond the removed element, 658 //! or end() if no such element exists. 659 //! 660 //! <b>Throws</b>: Nothing. 661 //! 662 //! <b>Complexity</b>: Constant. 663 //! 664 //! <b>Note</b>: Invalidates the iterators to the erased element. 665 template <class Disposer> erase_and_dispose(const_iterator i,Disposer disposer)666 iterator erase_and_dispose(const_iterator i, Disposer disposer) 667 { 668 node_ptr to_erase(i.pointed_node()); 669 ++i; 670 node_algorithms::unlink(to_erase); 671 this->priv_size_traits().decrement(); 672 if(safemode_or_autounlink) 673 node_algorithms::init(to_erase); 674 disposer(this->priv_value_traits().to_value_ptr(to_erase)); 675 return i.unconst(); 676 } 677 678 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) 679 template<class Disposer> erase_and_dispose(iterator i,Disposer disposer)680 iterator erase_and_dispose(iterator i, Disposer disposer) 681 { return this->erase_and_dispose(const_iterator(i), disposer); } 682 #endif 683 684 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 685 //! 686 //! <b>Effects</b>: Erases the element range pointed by b and e 687 //! No destructors are called. 688 //! Disposer::operator()(pointer) is called for the removed elements. 689 //! 690 //! <b>Returns</b>: the first element remaining beyond the removed elements, 691 //! or end() if no such element exists. 692 //! 693 //! <b>Throws</b>: Nothing. 694 //! 695 //! <b>Complexity</b>: Linear to the number of elements erased. 696 //! 697 //! <b>Note</b>: Invalidates the iterators to the erased elements. 698 template <class Disposer> erase_and_dispose(const_iterator b,const_iterator e,Disposer disposer)699 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) 700 { 701 node_ptr bp(b.pointed_node()), ep(e.pointed_node()); 702 node_algorithms::unlink(bp, ep); 703 while(bp != ep){ 704 node_ptr to_erase(bp); 705 bp = node_traits::get_next(bp); 706 if(safemode_or_autounlink) 707 node_algorithms::init(to_erase); 708 disposer(priv_value_traits().to_value_ptr(to_erase)); 709 this->priv_size_traits().decrement(); 710 } 711 return e.unconst(); 712 } 713 714 //! <b>Effects</b>: Erases all the elements of the container. 715 //! No destructors are called. 716 //! 717 //! <b>Throws</b>: Nothing. 718 //! 719 //! <b>Complexity</b>: Linear to the number of elements of the list. 720 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. 721 //! 722 //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements. clear()723 void clear() 724 { 725 if(safemode_or_autounlink){ 726 this->clear_and_dispose(detail::null_disposer()); 727 } 728 else{ 729 node_algorithms::init_header(this->get_root_node()); 730 this->priv_size_traits().set_size(size_type(0)); 731 } 732 } 733 734 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 735 //! 736 //! <b>Effects</b>: Erases all the elements of the container. 737 //! No destructors are called. 738 //! Disposer::operator()(pointer) is called for the removed elements. 739 //! 740 //! <b>Throws</b>: Nothing. 741 //! 742 //! <b>Complexity</b>: Linear to the number of elements of the list. 743 //! 744 //! <b>Note</b>: Invalidates the iterators to the erased elements. 745 template <class Disposer> clear_and_dispose(Disposer disposer)746 void clear_and_dispose(Disposer disposer) 747 { 748 const_iterator it(this->begin()), itend(this->end()); 749 while(it != itend){ 750 node_ptr to_erase(it.pointed_node()); 751 ++it; 752 if(safemode_or_autounlink) 753 node_algorithms::init(to_erase); 754 disposer(priv_value_traits().to_value_ptr(to_erase)); 755 } 756 node_algorithms::init_header(this->get_root_node()); 757 this->priv_size_traits().set_size(0); 758 } 759 760 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 761 //! Cloner should yield to nodes equivalent to the original nodes. 762 //! 763 //! <b>Effects</b>: Erases all the elements from *this 764 //! calling Disposer::operator()(pointer), clones all the 765 //! elements from src calling Cloner::operator()(const_reference ) 766 //! and inserts them on *this. 767 //! 768 //! If cloner throws, all cloned elements are unlinked and disposed 769 //! calling Disposer::operator()(pointer). 770 //! 771 //! <b>Complexity</b>: Linear to erased plus inserted elements. 772 //! 773 //! <b>Throws</b>: If cloner throws. Basic guarantee. 774 template <class Cloner, class Disposer> clone_from(const list_impl & src,Cloner cloner,Disposer disposer)775 void clone_from(const list_impl &src, Cloner cloner, Disposer disposer) 776 { 777 this->clear_and_dispose(disposer); 778 detail::exception_disposer<list_impl, Disposer> 779 rollback(*this, disposer); 780 const_iterator b(src.begin()), e(src.end()); 781 for(; b != e; ++b){ 782 this->push_back(*cloner(*b)); 783 } 784 rollback.release(); 785 } 786 787 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 788 //! Cloner should yield to nodes equivalent to the original nodes. 789 //! 790 //! <b>Effects</b>: Erases all the elements from *this 791 //! calling Disposer::operator()(pointer), clones all the 792 //! elements from src calling Cloner::operator()(reference) 793 //! and inserts them on *this. 794 //! 795 //! If cloner throws, all cloned elements are unlinked and disposed 796 //! calling Disposer::operator()(pointer). 797 //! 798 //! <b>Complexity</b>: Linear to erased plus inserted elements. 799 //! 800 //! <b>Throws</b>: If cloner throws. Basic guarantee. 801 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (list_impl)src,Cloner cloner,Disposer disposer)802 void clone_from(BOOST_RV_REF(list_impl) src, Cloner cloner, Disposer disposer) 803 { 804 this->clear_and_dispose(disposer); 805 detail::exception_disposer<list_impl, Disposer> 806 rollback(*this, disposer); 807 iterator b(src.begin()), e(src.end()); 808 for(; b != e; ++b){ 809 this->push_back(*cloner(*b)); 810 } 811 rollback.release(); 812 } 813 814 //! <b>Requires</b>: value must be an lvalue and p must be a valid iterator of *this. 815 //! 816 //! <b>Effects</b>: Inserts the value before the position pointed by p. 817 //! 818 //! <b>Returns</b>: An iterator to the inserted element. 819 //! 820 //! <b>Throws</b>: Nothing. 821 //! 822 //! <b>Complexity</b>: Constant time. No copy constructors are called. 823 //! 824 //! <b>Note</b>: Does not affect the validity of iterators and references. insert(const_iterator p,reference value)825 iterator insert(const_iterator p, reference value) 826 { 827 node_ptr to_insert = this->priv_value_traits().to_node_ptr(value); 828 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::inited(to_insert)); 829 node_algorithms::link_before(p.pointed_node(), to_insert); 830 this->priv_size_traits().increment(); 831 return iterator(to_insert, this->priv_value_traits_ptr()); 832 } 833 834 //! <b>Requires</b>: Dereferencing iterator must yield 835 //! an lvalue of type value_type and p must be a valid iterator of *this. 836 //! 837 //! <b>Effects</b>: Inserts the range pointed by b and e before the position p. 838 //! No copy constructors are called. 839 //! 840 //! <b>Throws</b>: Nothing. 841 //! 842 //! <b>Complexity</b>: Linear to the number of elements inserted. 843 //! 844 //! <b>Note</b>: Does not affect the validity of iterators and references. 845 template<class Iterator> insert(const_iterator p,Iterator b,Iterator e)846 void insert(const_iterator p, Iterator b, Iterator e) 847 { 848 for (; b != e; ++b) 849 this->insert(p, *b); 850 } 851 852 //! <b>Requires</b>: Dereferencing iterator must yield 853 //! an lvalue of type value_type. 854 //! 855 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. 856 //! No destructors or copy constructors are called. 857 //! 858 //! <b>Throws</b>: Nothing. 859 //! 860 //! <b>Complexity</b>: Linear to the number of elements inserted plus 861 //! linear to the elements contained in the list if it's a safe-mode 862 //! or auto-unlink value. 863 //! Linear to the number of elements inserted in the list otherwise. 864 //! 865 //! <b>Note</b>: Invalidates the iterators (but not the references) 866 //! to the erased elements. 867 template<class Iterator> assign(Iterator b,Iterator e)868 void assign(Iterator b, Iterator e) 869 { 870 this->clear(); 871 this->insert(this->cend(), b, e); 872 } 873 874 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 875 //! 876 //! <b>Requires</b>: Dereferencing iterator must yield 877 //! an lvalue of type value_type. 878 //! 879 //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. 880 //! No destructors or copy constructors are called. 881 //! Disposer::operator()(pointer) is called for the removed elements. 882 //! 883 //! <b>Throws</b>: Nothing. 884 //! 885 //! <b>Complexity</b>: Linear to the number of elements inserted plus 886 //! linear to the elements contained in the list. 887 //! 888 //! <b>Note</b>: Invalidates the iterators (but not the references) 889 //! to the erased elements. 890 template<class Iterator, class Disposer> dispose_and_assign(Disposer disposer,Iterator b,Iterator e)891 void dispose_and_assign(Disposer disposer, Iterator b, Iterator e) 892 { 893 this->clear_and_dispose(disposer); 894 this->insert(this->cend(), b, e); 895 } 896 897 //! <b>Requires</b>: p must be a valid iterator of *this. 898 //! 899 //! <b>Effects</b>: Transfers all the elements of list x to this list, before the 900 //! the element pointed by p. No destructors or copy constructors are called. 901 //! 902 //! <b>Throws</b>: Nothing. 903 //! 904 //! <b>Complexity</b>: Constant. 905 //! 906 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of 907 //! this list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list_impl & x)908 void splice(const_iterator p, list_impl& x) 909 { 910 if(!x.empty()){ 911 node_algorithms::transfer 912 (p.pointed_node(), x.begin().pointed_node(), x.end().pointed_node()); 913 size_traits &thist = this->priv_size_traits(); 914 size_traits &xt = x.priv_size_traits(); 915 thist.increase(xt.get_size()); 916 xt.set_size(size_type(0)); 917 } 918 } 919 920 //! <b>Requires</b>: p must be a valid iterator of *this. 921 //! new_ele must point to an element contained in list x. 922 //! 923 //! <b>Effects</b>: Transfers the value pointed by new_ele, from list x to this list, 924 //! before the element pointed by p. No destructors or copy constructors are called. 925 //! If p == new_ele or p == ++new_ele, this function is a null operation. 926 //! 927 //! <b>Throws</b>: Nothing. 928 //! 929 //! <b>Complexity</b>: Constant. 930 //! 931 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 932 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list_impl & x,const_iterator new_ele)933 void splice(const_iterator p, list_impl&x, const_iterator new_ele) 934 { 935 node_algorithms::transfer(p.pointed_node(), new_ele.pointed_node()); 936 x.priv_size_traits().decrement(); 937 this->priv_size_traits().increment(); 938 } 939 940 //! <b>Requires</b>: p must be a valid iterator of *this. 941 //! f and e must point to elements contained in list x. 942 //! 943 //! <b>Effects</b>: Transfers the range pointed by f and e from list x to this list, 944 //! before the element pointed by p. No destructors or copy constructors are called. 945 //! 946 //! <b>Throws</b>: Nothing. 947 //! 948 //! <b>Complexity</b>: Linear to the number of elements transferred 949 //! if constant-time size option is enabled. Constant-time otherwise. 950 //! 951 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 952 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list_impl & x,const_iterator f,const_iterator e)953 void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e) 954 { 955 if(constant_time_size) 956 this->splice(p, x, f, e, node_algorithms::distance(f.pointed_node(), e.pointed_node())); 957 else 958 this->splice(p, x, f, e, 1);//intrusive::iterator_distance is a dummy value 959 } 960 961 //! <b>Requires</b>: p must be a valid iterator of *this. 962 //! f and e must point to elements contained in list x. 963 //! n == distance(f, e) 964 //! 965 //! <b>Effects</b>: Transfers the range pointed by f and e from list x to this list, 966 //! before the element pointed by p. No destructors or copy constructors are called. 967 //! 968 //! <b>Throws</b>: Nothing. 969 //! 970 //! <b>Complexity</b>: Constant. 971 //! 972 //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this 973 //! list. Iterators of this list and all the references are not invalidated. splice(const_iterator p,list_impl & x,const_iterator f,const_iterator e,size_type n)974 void splice(const_iterator p, list_impl&x, const_iterator f, const_iterator e, size_type n) 975 { 976 if(n){ 977 if(constant_time_size){ 978 BOOST_INTRUSIVE_INVARIANT_ASSERT(n == node_algorithms::distance(f.pointed_node(), e.pointed_node())); 979 node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node()); 980 size_traits &thist = this->priv_size_traits(); 981 size_traits &xt = x.priv_size_traits(); 982 thist.increase(n); 983 xt.decrease(n); 984 } 985 else{ 986 node_algorithms::transfer(p.pointed_node(), f.pointed_node(), e.pointed_node()); 987 } 988 } 989 } 990 991 //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. 992 //! The sort is stable, that is, the relative order of equivalent elements is preserved. 993 //! 994 //! <b>Throws</b>: If value_traits::node_traits::node 995 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 996 //! or std::less<value_type> throws. Basic guarantee. 997 //! 998 //! <b>Notes</b>: Iterators and references are not invalidated. 999 //! 1000 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1001 //! is the list's size. sort()1002 void sort() 1003 { this->sort(std::less<value_type>()); } 1004 1005 //! <b>Requires</b>: p must be a comparison function that induces a strict weak ordering 1006 //! 1007 //! <b>Effects</b>: This function sorts the list *this according to p. The sort is 1008 //! stable, that is, the relative order of equivalent elements is preserved. 1009 //! 1010 //! <b>Throws</b>: If value_traits::node_traits::node 1011 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) 1012 //! or the predicate throws. Basic guarantee. 1013 //! 1014 //! <b>Notes</b>: This won't throw if list_base_hook<> or 1015 //! list_member_hook are used. 1016 //! Iterators and references are not invalidated. 1017 //! 1018 //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N 1019 //! is the list's size. 1020 template<class Predicate> sort(Predicate p)1021 void sort(Predicate p) 1022 { 1023 if(node_traits::get_next(this->get_root_node()) 1024 != node_traits::get_previous(this->get_root_node())){ 1025 list_impl carry(this->priv_value_traits()); 1026 detail::array_initializer<list_impl, 64> counter(this->priv_value_traits()); 1027 int fill = 0; 1028 while(!this->empty()){ 1029 carry.splice(carry.cbegin(), *this, this->cbegin()); 1030 int i = 0; 1031 while(i < fill && !counter[i].empty()) { 1032 counter[i].merge(carry, p); 1033 carry.swap(counter[i++]); 1034 } 1035 carry.swap(counter[i]); 1036 if(i == fill) 1037 ++fill; 1038 } 1039 for (int i = 1; i < fill; ++i) 1040 counter[i].merge(counter[i-1], p); 1041 this->swap(counter[fill-1]); 1042 } 1043 } 1044 1045 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1046 //! in order into *this according to std::less<value_type>. The merge is stable; 1047 //! that is, if an element from *this is equivalent to one from x, then the element 1048 //! from *this will precede the one from x. 1049 //! 1050 //! <b>Throws</b>: If std::less<value_type> throws. Basic guarantee. 1051 //! 1052 //! <b>Complexity</b>: This function is linear time: it performs at most 1053 //! size() + x.size() - 1 comparisons. 1054 //! 1055 //! <b>Note</b>: Iterators and references are not invalidated merge(list_impl & x)1056 void merge(list_impl& x) 1057 { this->merge(x, std::less<value_type>()); } 1058 1059 //! <b>Requires</b>: p must be a comparison function that induces a strict weak 1060 //! ordering and both *this and x must be sorted according to that ordering 1061 //! The lists x and *this must be distinct. 1062 //! 1063 //! <b>Effects</b>: This function removes all of x's elements and inserts them 1064 //! in order into *this. The merge is stable; that is, if an element from *this is 1065 //! equivalent to one from x, then the element from *this will precede the one from x. 1066 //! 1067 //! <b>Throws</b>: If the predicate throws. Basic guarantee. 1068 //! 1069 //! <b>Complexity</b>: This function is linear time: it performs at most 1070 //! size() + x.size() - 1 comparisons. 1071 //! 1072 //! <b>Note</b>: Iterators and references are not invalidated. 1073 template<class Predicate> merge(list_impl & x,Predicate p)1074 void merge(list_impl& x, Predicate p) 1075 { 1076 const_iterator e(this->cend()), ex(x.cend()); 1077 const_iterator b(this->cbegin()); 1078 while(!x.empty()){ 1079 const_iterator ix(x.cbegin()); 1080 while (b != e && !p(*ix, *b)){ 1081 ++b; 1082 } 1083 if(b == e){ 1084 //Now transfer the rest to the end of the container 1085 this->splice(e, x); 1086 break; 1087 } 1088 else{ 1089 size_type n(0); 1090 do{ 1091 ++ix; ++n; 1092 } while(ix != ex && p(*ix, *b)); 1093 this->splice(b, x, x.begin(), ix, n); 1094 } 1095 } 1096 } 1097 1098 //! <b>Effects</b>: Reverses the order of elements in the list. 1099 //! 1100 //! <b>Throws</b>: Nothing. 1101 //! 1102 //! <b>Complexity</b>: This function is linear time. 1103 //! 1104 //! <b>Note</b>: Iterators and references are not invalidated reverse()1105 void reverse() 1106 { node_algorithms::reverse(this->get_root_node()); } 1107 1108 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1109 //! No destructors are called. 1110 //! 1111 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. 1112 //! 1113 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1114 //! 1115 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1116 //! and iterators to elements that are not removed remain valid. remove(const_reference value)1117 void remove(const_reference value) 1118 { this->remove_if(detail::equal_to_value<const_reference>(value)); } 1119 1120 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1121 //! 1122 //! <b>Effects</b>: Removes all the elements that compare equal to value. 1123 //! Disposer::operator()(pointer) is called for every removed element. 1124 //! 1125 //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. 1126 //! 1127 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1128 //! 1129 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1130 //! and iterators to elements that are not removed remain valid. 1131 template<class Disposer> remove_and_dispose(const_reference value,Disposer disposer)1132 void remove_and_dispose(const_reference value, Disposer disposer) 1133 { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); } 1134 1135 //! <b>Effects</b>: Removes all the elements for which a specified 1136 //! predicate is satisfied. No destructors are called. 1137 //! 1138 //! <b>Throws</b>: If pred throws. Basic guarantee. 1139 //! 1140 //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. 1141 //! 1142 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1143 //! and iterators to elements that are not removed remain valid. 1144 template<class Pred> remove_if(Pred pred)1145 void remove_if(Pred pred) 1146 { 1147 const node_ptr root_node = this->get_root_node(); 1148 typename node_algorithms::stable_partition_info info; 1149 node_algorithms::stable_partition 1150 (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); 1151 //Invariants preserved by stable_partition so erase can be safely called 1152 //The first element might have changed so calculate it again 1153 this->erase( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr()) 1154 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) 1155 , info.num_1st_partition); 1156 } 1157 1158 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1159 //! 1160 //! <b>Effects</b>: Removes all the elements for which a specified 1161 //! predicate is satisfied. 1162 //! Disposer::operator()(pointer) is called for every removed element. 1163 //! 1164 //! <b>Throws</b>: If pred throws. Basic guarantee. 1165 //! 1166 //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. 1167 //! 1168 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1169 //! and iterators to elements that are not removed remain valid. 1170 template<class Pred, class Disposer> remove_and_dispose_if(Pred pred,Disposer disposer)1171 void remove_and_dispose_if(Pred pred, Disposer disposer) 1172 { 1173 const node_ptr root_node = this->get_root_node(); 1174 typename node_algorithms::stable_partition_info info; 1175 node_algorithms::stable_partition 1176 (node_traits::get_next(root_node), root_node, detail::key_nodeptr_comp<Pred, value_traits>(pred, &this->priv_value_traits()), info); 1177 //Invariants preserved by stable_partition so erase can be safely called 1178 //The first element might have changed so calculate it again 1179 this->erase_and_dispose( const_iterator(node_traits::get_next(root_node), this->priv_value_traits_ptr()) 1180 , const_iterator(info.beg_2st_partition, this->priv_value_traits_ptr()) 1181 , disposer); 1182 } 1183 1184 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1185 //! elements that are equal from the list. No destructors are called. 1186 //! 1187 //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee. 1188 //! 1189 //! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()). 1190 //! 1191 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1192 //! and iterators to elements that are not removed remain valid. unique()1193 void unique() 1194 { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); } 1195 1196 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1197 //! elements that satisfy some binary predicate from the list. 1198 //! No destructors are called. 1199 //! 1200 //! <b>Throws</b>: If pred throws. Basic guarantee. 1201 //! 1202 //! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons). 1203 //! 1204 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1205 //! and iterators to elements that are not removed remain valid. 1206 template<class BinaryPredicate> unique(BinaryPredicate pred)1207 void unique(BinaryPredicate pred) 1208 { this->unique_and_dispose(pred, detail::null_disposer()); } 1209 1210 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1211 //! 1212 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1213 //! elements that are equal from the list. 1214 //! Disposer::operator()(pointer) is called for every removed element. 1215 //! 1216 //! <b>Throws</b>: If std::equal_to<value_type throws. Basic guarantee. 1217 //! 1218 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. 1219 //! 1220 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1221 //! and iterators to elements that are not removed remain valid. 1222 template<class Disposer> unique_and_dispose(Disposer disposer)1223 void unique_and_dispose(Disposer disposer) 1224 { this->unique_and_dispose(std::equal_to<value_type>(), disposer); } 1225 1226 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. 1227 //! 1228 //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent 1229 //! elements that satisfy some binary predicate from the list. 1230 //! Disposer::operator()(pointer) is called for every removed element. 1231 //! 1232 //! <b>Throws</b>: If pred throws. Basic guarantee. 1233 //! 1234 //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. 1235 //! 1236 //! <b>Note</b>: The relative order of elements that are not removed is unchanged, 1237 //! and iterators to elements that are not removed remain valid. 1238 template<class BinaryPredicate, class Disposer> unique_and_dispose(BinaryPredicate pred,Disposer disposer)1239 void unique_and_dispose(BinaryPredicate pred, Disposer disposer) 1240 { 1241 const_iterator itend(this->cend()); 1242 const_iterator cur(this->cbegin()); 1243 1244 if(cur != itend){ 1245 const_iterator after(cur); 1246 ++after; 1247 while(after != itend){ 1248 if(pred(*cur, *after)){ 1249 after = this->erase_and_dispose(after, disposer); 1250 } 1251 else{ 1252 cur = after; 1253 ++after; 1254 } 1255 } 1256 } 1257 } 1258 1259 //! <b>Requires</b>: value must be a reference to a value inserted in a list. 1260 //! 1261 //! <b>Effects</b>: This function returns a const_iterator pointing to the element 1262 //! 1263 //! <b>Throws</b>: Nothing. 1264 //! 1265 //! <b>Complexity</b>: Constant time. 1266 //! 1267 //! <b>Note</b>: Iterators and references are not invalidated. 1268 //! This static function is available only if the <i>value traits</i> 1269 //! is stateless. s_iterator_to(reference value)1270 static iterator s_iterator_to(reference value) 1271 { 1272 BOOST_STATIC_ASSERT((!stateful_value_traits)); 1273 BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(value))); 1274 return iterator(value_traits::to_node_ptr(value), const_value_traits_ptr()); 1275 } 1276 1277 //! <b>Requires</b>: value must be a const reference to a value inserted in a list. 1278 //! 1279 //! <b>Effects</b>: This function returns an iterator pointing to the element. 1280 //! 1281 //! <b>Throws</b>: Nothing. 1282 //! 1283 //! <b>Complexity</b>: Constant time. 1284 //! 1285 //! <b>Note</b>: Iterators and references are not invalidated. 1286 //! This static function is available only if the <i>value traits</i> 1287 //! is stateless. s_iterator_to(const_reference value)1288 static const_iterator s_iterator_to(const_reference value) 1289 { 1290 BOOST_STATIC_ASSERT((!stateful_value_traits)); 1291 reference r =*detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); 1292 BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(value_traits::to_node_ptr(r))); 1293 return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr()); 1294 } 1295 1296 //! <b>Requires</b>: value must be a reference to a value inserted in a list. 1297 //! 1298 //! <b>Effects</b>: This function returns a const_iterator pointing to the element 1299 //! 1300 //! <b>Throws</b>: Nothing. 1301 //! 1302 //! <b>Complexity</b>: Constant time. 1303 //! 1304 //! <b>Note</b>: Iterators and references are not invalidated. iterator_to(reference value)1305 iterator iterator_to(reference value) 1306 { 1307 BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(value))); 1308 return iterator(this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); 1309 } 1310 1311 //! <b>Requires</b>: value must be a const reference to a value inserted in a list. 1312 //! 1313 //! <b>Effects</b>: This function returns an iterator pointing to the element. 1314 //! 1315 //! <b>Throws</b>: Nothing. 1316 //! 1317 //! <b>Complexity</b>: Constant time. 1318 //! 1319 //! <b>Note</b>: Iterators and references are not invalidated. iterator_to(const_reference value) const1320 const_iterator iterator_to(const_reference value) const 1321 { 1322 reference r = *detail::uncast(pointer_traits<const_pointer>::pointer_to(value)); 1323 BOOST_INTRUSIVE_INVARIANT_ASSERT(!node_algorithms::inited(this->priv_value_traits().to_node_ptr(r))); 1324 return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr()); 1325 } 1326 1327 //! <b>Effects</b>: Asserts the integrity of the container. 1328 //! 1329 //! <b>Complexity</b>: Linear time. 1330 //! 1331 //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). 1332 //! Experimental function, interface might change in future versions. check() const1333 void check() const 1334 { 1335 const_node_ptr header_ptr = get_root_node(); 1336 // header's next and prev are never null 1337 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_next(header_ptr)); 1338 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(header_ptr)); 1339 // header's next and prev either both point to header (empty list) or neither does 1340 BOOST_INTRUSIVE_INVARIANT_ASSERT((node_traits::get_next(header_ptr) == header_ptr) 1341 == (node_traits::get_previous(header_ptr) == header_ptr)); 1342 if (node_traits::get_next(header_ptr) == header_ptr) 1343 { 1344 if (constant_time_size) 1345 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == 0); 1346 return; 1347 } 1348 size_t node_count = 0; 1349 const_node_ptr p = header_ptr; 1350 while (true) 1351 { 1352 const_node_ptr next_p = node_traits::get_next(p); 1353 BOOST_INTRUSIVE_INVARIANT_ASSERT(next_p); 1354 BOOST_INTRUSIVE_INVARIANT_ASSERT(node_traits::get_previous(next_p) == p); 1355 p = next_p; 1356 if (p == header_ptr) break; 1357 ++node_count; 1358 } 1359 if (constant_time_size) 1360 BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_size_traits().get_size() == node_count); 1361 } 1362 operator ==(const list_impl & x,const list_impl & y)1363 friend bool operator==(const list_impl &x, const list_impl &y) 1364 { 1365 if(constant_time_size && x.size() != y.size()){ 1366 return false; 1367 } 1368 return ::boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); 1369 } 1370 operator !=(const list_impl & x,const list_impl & y)1371 friend bool operator!=(const list_impl &x, const list_impl &y) 1372 { return !(x == y); } 1373 operator <(const list_impl & x,const list_impl & y)1374 friend bool operator<(const list_impl &x, const list_impl &y) 1375 { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } 1376 operator >(const list_impl & x,const list_impl & y)1377 friend bool operator>(const list_impl &x, const list_impl &y) 1378 { return y < x; } 1379 operator <=(const list_impl & x,const list_impl & y)1380 friend bool operator<=(const list_impl &x, const list_impl &y) 1381 { return !(y < x); } 1382 operator >=(const list_impl & x,const list_impl & y)1383 friend bool operator>=(const list_impl &x, const list_impl &y) 1384 { return !(x < y); } 1385 swap(list_impl & x,list_impl & y)1386 friend void swap(list_impl &x, list_impl &y) 1387 { x.swap(y); } 1388 1389 /// @cond 1390 1391 private: priv_container_from_end_iterator(const const_iterator & end_iterator)1392 static list_impl &priv_container_from_end_iterator(const const_iterator &end_iterator) 1393 { 1394 BOOST_STATIC_ASSERT((has_container_from_iterator)); 1395 node_ptr p = end_iterator.pointed_node(); 1396 header_holder_type* h = header_holder_type::get_holder(p); 1397 root_plus_size* r = detail::parent_from_member 1398 < root_plus_size, header_holder_type>(h, &root_plus_size::m_header); 1399 data_t *d = detail::parent_from_member<data_t, root_plus_size> 1400 ( r, &data_t::root_plus_size_); 1401 list_impl *s = detail::parent_from_member<list_impl, data_t>(d, &list_impl::data_); 1402 return *s; 1403 } 1404 /// @endcond 1405 }; 1406 1407 1408 //! Helper metafunction to define a \c list that yields to the same type when the 1409 //! same options (either explicitly or implicitly) are used. 1410 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1411 template<class T, class ...Options> 1412 #else 1413 template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void> 1414 #endif 1415 struct make_list 1416 { 1417 /// @cond 1418 typedef typename pack_options 1419 < list_defaults, 1420 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1421 O1, O2, O3, O4 1422 #else 1423 Options... 1424 #endif 1425 >::type packed_options; 1426 1427 typedef typename detail::get_value_traits 1428 <T, typename packed_options::proto_value_traits>::type value_traits; 1429 typedef list_impl 1430 < 1431 value_traits, 1432 typename packed_options::size_type, 1433 packed_options::constant_time_size, 1434 typename packed_options::header_holder_type 1435 > implementation_defined; 1436 /// @endcond 1437 typedef implementation_defined type; 1438 }; 1439 1440 1441 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED 1442 1443 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1444 template<class T, class O1, class O2, class O3, class O4> 1445 #else 1446 template<class T, class ...Options> 1447 #endif 1448 class list 1449 : public make_list<T, 1450 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1451 O1, O2, O3, O4 1452 #else 1453 Options... 1454 #endif 1455 >::type 1456 { 1457 typedef typename make_list 1458 <T, 1459 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) 1460 O1, O2, O3, O4 1461 #else 1462 Options... 1463 #endif 1464 >::type Base; 1465 //Assert if passed value traits are compatible with the type 1466 BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value)); 1467 BOOST_MOVABLE_BUT_NOT_COPYABLE(list) 1468 1469 public: 1470 typedef typename Base::value_traits value_traits; 1471 typedef typename Base::iterator iterator; 1472 typedef typename Base::const_iterator const_iterator; 1473 list()1474 BOOST_INTRUSIVE_FORCEINLINE list() 1475 : Base() 1476 {} 1477 list(const value_traits & v_traits)1478 BOOST_INTRUSIVE_FORCEINLINE explicit list(const value_traits &v_traits) 1479 : Base(v_traits) 1480 {} 1481 1482 template<class Iterator> list(Iterator b,Iterator e,const value_traits & v_traits=value_traits ())1483 BOOST_INTRUSIVE_FORCEINLINE list(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) 1484 : Base(b, e, v_traits) 1485 {} 1486 list(BOOST_RV_REF (list)x)1487 BOOST_INTRUSIVE_FORCEINLINE list(BOOST_RV_REF(list) x) 1488 : Base(BOOST_MOVE_BASE(Base, x)) 1489 {} 1490 operator =(BOOST_RV_REF (list)x)1491 BOOST_INTRUSIVE_FORCEINLINE list& operator=(BOOST_RV_REF(list) x) 1492 { return static_cast<list &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } 1493 1494 template <class Cloner, class Disposer> clone_from(const list & src,Cloner cloner,Disposer disposer)1495 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const list &src, Cloner cloner, Disposer disposer) 1496 { Base::clone_from(src, cloner, disposer); } 1497 1498 template <class Cloner, class Disposer> clone_from(BOOST_RV_REF (list)src,Cloner cloner,Disposer disposer)1499 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(list) src, Cloner cloner, Disposer disposer) 1500 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } 1501 container_from_end_iterator(iterator end_iterator)1502 BOOST_INTRUSIVE_FORCEINLINE static list &container_from_end_iterator(iterator end_iterator) 1503 { return static_cast<list &>(Base::container_from_end_iterator(end_iterator)); } 1504 container_from_end_iterator(const_iterator end_iterator)1505 BOOST_INTRUSIVE_FORCEINLINE static const list &container_from_end_iterator(const_iterator end_iterator) 1506 { return static_cast<const list &>(Base::container_from_end_iterator(end_iterator)); } 1507 }; 1508 1509 #endif 1510 1511 } //namespace intrusive 1512 } //namespace boost 1513 1514 #include <boost/intrusive/detail/config_end.hpp> 1515 1516 #endif //BOOST_INTRUSIVE_LIST_HPP 1517