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