1
//////////////////////////////////////////////////////////////////////////////
3
// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
4
// Software License, Version 1.0. (See accompanying file
5
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7
// See http://www.boost.org/libs/container for documentation.
10
#ifndef BOOST_CONTAINER_LIST_HPP
11
#define BOOST_CONTAINER_LIST_HPP
17
#include <boost/container/detail/config_begin.hpp>
18
#include <boost/container/detail/workaround.hpp>
19
#include <boost/container/container_fwd.hpp>
20
#include <boost/container/detail/version_type.hpp>
21
#include <boost/container/detail/iterators.hpp>
22
#include <boost/container/detail/mpl.hpp>
23
#include <boost/container/throw_exception.hpp>
24
#include <boost/move/utility.hpp>
25
#include <boost/move/iterator.hpp>
26
#include <boost/move/detail/move_helpers.hpp>
27
#include <boost/intrusive/pointer_traits.hpp>
28
#include <boost/container/detail/utilities.hpp>
29
#include <boost/container/detail/algorithms.hpp>
30
#include <boost/type_traits/has_trivial_destructor.hpp>
31
#include <boost/intrusive/list.hpp>
32
#include <boost/assert.hpp>
33
#include <boost/container/detail/node_alloc_holder.hpp>
35
#if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
37
//Preprocessor library to emulate perfect forwarding
38
#include <boost/container/detail/preprocessor.hpp>
51
namespace container_detail {
53
template<class VoidPointer>
56
typedef typename container_detail::bi::make_list_base_hook
57
<container_detail::bi::void_pointer<VoidPointer>, container_detail::bi::link_mode<container_detail::bi::normal_link> >::type type;
60
template <class T, class VoidPointer>
62
: public list_hook<VoidPointer>::type
69
typedef typename list_hook<VoidPointer>::type hook_type;
74
{ return this->m_data; }
76
const T &get_data() const
77
{ return this->m_data; }
80
template<class Allocator>
81
struct intrusive_list_type
83
typedef boost::container::allocator_traits<Allocator> allocator_traits_type;
84
typedef typename allocator_traits_type::value_type value_type;
85
typedef typename boost::intrusive::pointer_traits
86
<typename allocator_traits_type::pointer>::template
87
rebind_pointer<void>::type
89
typedef typename container_detail::list_node
90
<value_type, void_pointer> node_type;
91
typedef typename container_detail::bi::make_list
93
, container_detail::bi::base_hook<typename list_hook<void_pointer>::type>
94
, container_detail::bi::constant_time_size<true>
95
, container_detail::bi::size_type
96
<typename allocator_traits_type::size_type>
97
>::type container_type;
98
typedef container_type type ;
101
} //namespace container_detail {
104
//! A list is a doubly linked list. That is, it is a Sequence that supports both
105
//! forward and backward traversal, and (amortized) constant time insertion and
106
//! removal of elements at the beginning or the end, or in the middle. Lists have
107
//! the important property that insertion and splicing do not invalidate iterators
108
//! to list elements, and that even removal invalidates only the iterators that point
109
//! to the elements that are removed. The ordering of iterators may be changed
110
//! (that is, list<T>::iterator might have a different predecessor or successor
111
//! after a list operation than it did before), but the iterators themselves will
112
//! not be invalidated or made to point to different elements unless that invalidation
113
//! or mutation is explicit.
114
#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
115
template <class T, class Allocator = std::allocator<T> >
117
template <class T, class Allocator>
120
: protected container_detail::node_alloc_holder
121
<Allocator, typename container_detail::intrusive_list_type<Allocator>::type>
125
container_detail::intrusive_list_type<Allocator>::type Icont;
126
typedef container_detail::node_alloc_holder<Allocator, Icont> AllocHolder;
127
typedef typename AllocHolder::NodePtr NodePtr;
128
typedef typename AllocHolder::NodeAlloc NodeAlloc;
129
typedef typename AllocHolder::ValAlloc ValAlloc;
130
typedef typename AllocHolder::Node Node;
131
typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer;
132
typedef typename AllocHolder::allocator_v1 allocator_v1;
133
typedef typename AllocHolder::allocator_v2 allocator_v2;
134
typedef typename AllocHolder::alloc_version alloc_version;
135
typedef boost::container::allocator_traits<Allocator> allocator_traits_type;
139
typedef typename AllocHolder::value_type value_type;
140
const value_type &t_;
143
equal_to_value(const value_type &t)
147
bool operator()(const value_type &t)const
152
struct ValueCompareToNodeCompare
155
ValueCompareToNodeCompare(Pred pred)
159
bool operator()(const Node &a, const Node &b) const
160
{ return static_cast<const Pred&>(*this)(a.m_data, b.m_data); }
162
bool operator()(const Node &a) const
163
{ return static_cast<const Pred&>(*this)(a.m_data); }
166
BOOST_COPYABLE_AND_MOVABLE(list)
168
typedef container_detail::iterator<typename Icont::iterator, false> iterator_impl;
169
typedef container_detail::iterator<typename Icont::iterator, true> const_iterator_impl;
173
//////////////////////////////////////////////
177
//////////////////////////////////////////////
179
typedef T value_type;
180
typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
181
typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
182
typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
183
typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
184
typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
185
typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
186
typedef Allocator allocator_type;
187
typedef BOOST_CONTAINER_IMPDEF(NodeAlloc) stored_allocator_type;
188
typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
189
typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
190
typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<iterator>) reverse_iterator;
191
typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<const_iterator>) const_reverse_iterator;
193
//////////////////////////////////////////////
195
// construct/copy/destroy
197
//////////////////////////////////////////////
199
//! <b>Effects</b>: Default constructs a list.
201
//! <b>Throws</b>: If allocator_type's default constructor throws.
203
//! <b>Complexity</b>: Constant.
208
//! <b>Effects</b>: Constructs a list taking the allocator as parameter.
210
//! <b>Throws</b>: Nothing
212
//! <b>Complexity</b>: Constant.
213
explicit list(const allocator_type &a) BOOST_CONTAINER_NOEXCEPT
217
//! <b>Effects</b>: Constructs a list that will use a copy of allocator a
218
//! and inserts n copies of value.
220
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor
221
//! throws or T's default or copy constructor throws.
223
//! <b>Complexity</b>: Linear to n.
224
explicit list(size_type n)
225
: AllocHolder(Allocator())
228
//! <b>Effects</b>: Constructs a list that will use a copy of allocator a
229
//! and inserts n copies of value.
231
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor
232
//! throws or T's default or copy constructor throws.
234
//! <b>Complexity</b>: Linear to n.
235
list(size_type n, const T& value, const Allocator& a = Allocator())
237
{ this->insert(this->cbegin(), n, value); }
239
//! <b>Effects</b>: Copy constructs a list.
241
//! <b>Postcondition</b>: x == *this.
243
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws.
245
//! <b>Complexity</b>: Linear to the elements x contains.
248
{ this->insert(this->cbegin(), x.begin(), x.end()); }
250
//! <b>Effects</b>: Move constructor. Moves mx's resources to *this.
252
//! <b>Throws</b>: If allocator_type's copy constructor throws.
254
//! <b>Complexity</b>: Constant.
255
list(BOOST_RV_REF(list) x)
256
: AllocHolder(boost::move(static_cast<AllocHolder&>(x)))
259
//! <b>Effects</b>: Copy constructs a list using the specified allocator.
261
//! <b>Postcondition</b>: x == *this.
263
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws.
265
//! <b>Complexity</b>: Linear to the elements x contains.
266
list(const list& x, const allocator_type &a)
268
{ this->insert(this->cbegin(), x.begin(), x.end()); }
270
//! <b>Effects</b>: Move constructor sing the specified allocator.
271
//! Moves mx's resources to *this.
273
//! <b>Throws</b>: If allocation or value_type's copy constructor throws.
275
//! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
276
list(BOOST_RV_REF(list) x, const allocator_type &a)
279
if(this->node_alloc() == x.node_alloc()){
280
this->icont().swap(x.icont());
283
this->insert(this->cbegin(), x.begin(), x.end());
287
//! <b>Effects</b>: Constructs a list that will use a copy of allocator a
288
//! and inserts a copy of the range [first, last) in the list.
290
//! <b>Throws</b>: If allocator_type's default constructor or copy constructor
291
//! throws or T's constructor taking an dereferenced InIt throws.
293
//! <b>Complexity</b>: Linear to the range [first, last).
294
template <class InpIt>
295
list(InpIt first, InpIt last, const Allocator &a = Allocator())
297
{ this->insert(this->cbegin(), first, last); }
299
//! <b>Effects</b>: Destroys the list. All stored values are destroyed
300
//! and used memory is deallocated.
302
//! <b>Throws</b>: Nothing.
304
//! <b>Complexity</b>: Linear to the number of elements.
305
~list() BOOST_CONTAINER_NOEXCEPT
306
{} //AllocHolder clears the list
308
//! <b>Effects</b>: Makes *this contain the same elements as x.
310
//! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
311
//! of each of x's elements.
313
//! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
315
//! <b>Complexity</b>: Linear to the number of elements in x.
316
list& operator=(BOOST_COPY_ASSIGN_REF(list) x)
319
NodeAlloc &this_alloc = this->node_alloc();
320
const NodeAlloc &x_alloc = x.node_alloc();
321
container_detail::bool_<allocator_traits_type::
322
propagate_on_container_copy_assignment::value> flag;
323
if(flag && this_alloc != x_alloc){
326
this->AllocHolder::copy_assign_alloc(x);
327
this->assign(x.begin(), x.end());
332
//! <b>Effects</b>: Move assignment. All mx's values are transferred to *this.
334
//! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
335
//! before the function.
337
//! <b>Throws</b>: If allocator_type's copy constructor throws.
339
//! <b>Complexity</b>: Constant.
340
list& operator=(BOOST_RV_REF(list) x)
343
NodeAlloc &this_alloc = this->node_alloc();
344
NodeAlloc &x_alloc = x.node_alloc();
345
//If allocators are equal we can just swap pointers
346
if(this_alloc == x_alloc){
347
//Destroy and swap pointers
349
this->icont() = boost::move(x.icont());
350
//Move allocator if needed
351
this->AllocHolder::move_assign_alloc(x);
353
//If unequal allocators, then do a one by one move
355
this->assign( boost::make_move_iterator(x.begin())
356
, boost::make_move_iterator(x.end()));
362
//! <b>Effects</b>: Assigns the n copies of val to *this.
364
//! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
366
//! <b>Complexity</b>: Linear to n.
367
void assign(size_type n, const T& val)
369
typedef constant_iterator<value_type, difference_type> cvalue_iterator;
370
return this->assign(cvalue_iterator(val, n), cvalue_iterator());
373
//! <b>Effects</b>: Assigns the the range [first, last) to *this.
375
//! <b>Throws</b>: If memory allocation throws or
376
//! T's constructor from dereferencing InpIt throws.
378
//! <b>Complexity</b>: Linear to n.
379
template <class InpIt>
380
void assign(InpIt first, InpIt last
381
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
382
, typename container_detail::enable_if_c
383
< !container_detail::is_convertible<InpIt, size_type>::value
388
iterator first1 = this->begin();
389
const iterator last1 = this->end();
390
for ( ; first1 != last1 && first != last; ++first1, ++first)
393
this->erase(first1, last1);
395
this->insert(last1, first, last);
399
//! <b>Effects</b>: Returns a copy of the internal allocator.
401
//! <b>Throws</b>: If allocator's copy constructor throws.
403
//! <b>Complexity</b>: Constant.
404
allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
405
{ return allocator_type(this->node_alloc()); }
407
//! <b>Effects</b>: Returns a reference to the internal allocator.
409
//! <b>Throws</b>: Nothing
411
//! <b>Complexity</b>: Constant.
413
//! <b>Note</b>: Non-standard extension.
414
stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
415
{ return this->node_alloc(); }
417
//! <b>Effects</b>: Returns a reference to the internal allocator.
419
//! <b>Throws</b>: Nothing
421
//! <b>Complexity</b>: Constant.
423
//! <b>Note</b>: Non-standard extension.
424
const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
425
{ return this->node_alloc(); }
427
//////////////////////////////////////////////
431
//////////////////////////////////////////////
433
//! <b>Effects</b>: Returns an iterator to the first element contained in the list.
435
//! <b>Throws</b>: Nothing.
437
//! <b>Complexity</b>: Constant.
438
iterator begin() BOOST_CONTAINER_NOEXCEPT
439
{ return iterator(this->icont().begin()); }
441
//! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
443
//! <b>Throws</b>: Nothing.
445
//! <b>Complexity</b>: Constant.
446
const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
447
{ return this->cbegin(); }
449
//! <b>Effects</b>: Returns an iterator to the end of the list.
451
//! <b>Throws</b>: Nothing.
453
//! <b>Complexity</b>: Constant.
454
iterator end() BOOST_CONTAINER_NOEXCEPT
455
{ return iterator(this->icont().end()); }
457
//! <b>Effects</b>: Returns a const_iterator to the end of the list.
459
//! <b>Throws</b>: Nothing.
461
//! <b>Complexity</b>: Constant.
462
const_iterator end() const BOOST_CONTAINER_NOEXCEPT
463
{ return this->cend(); }
465
//! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
466
//! of the reversed list.
468
//! <b>Throws</b>: Nothing.
470
//! <b>Complexity</b>: Constant.
471
reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
472
{ return reverse_iterator(end()); }
474
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
475
//! of the reversed list.
477
//! <b>Throws</b>: Nothing.
479
//! <b>Complexity</b>: Constant.
480
const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
481
{ return this->crbegin(); }
483
//! <b>Effects</b>: Returns a reverse_iterator pointing to the end
484
//! of the reversed list.
486
//! <b>Throws</b>: Nothing.
488
//! <b>Complexity</b>: Constant.
489
reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
490
{ return reverse_iterator(begin()); }
492
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
493
//! of the reversed list.
495
//! <b>Throws</b>: Nothing.
497
//! <b>Complexity</b>: Constant.
498
const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
499
{ return this->crend(); }
501
//! <b>Effects</b>: Returns a const_iterator to the first element contained in the list.
503
//! <b>Throws</b>: Nothing.
505
//! <b>Complexity</b>: Constant.
506
const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
507
{ return const_iterator(this->non_const_icont().begin()); }
509
//! <b>Effects</b>: Returns a const_iterator to the end of the list.
511
//! <b>Throws</b>: Nothing.
513
//! <b>Complexity</b>: Constant.
514
const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
515
{ return const_iterator(this->non_const_icont().end()); }
517
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
518
//! of the reversed list.
520
//! <b>Throws</b>: Nothing.
522
//! <b>Complexity</b>: Constant.
523
const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
524
{ return const_reverse_iterator(this->cend()); }
526
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
527
//! of the reversed list.
529
//! <b>Throws</b>: Nothing.
531
//! <b>Complexity</b>: Constant.
532
const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
533
{ return const_reverse_iterator(this->cbegin()); }
535
//////////////////////////////////////////////
539
//////////////////////////////////////////////
541
//! <b>Effects</b>: Returns true if the list contains no elements.
543
//! <b>Throws</b>: Nothing.
545
//! <b>Complexity</b>: Constant.
546
bool empty() const BOOST_CONTAINER_NOEXCEPT
547
{ return !this->size(); }
549
//! <b>Effects</b>: Returns the number of the elements contained in the list.
551
//! <b>Throws</b>: Nothing.
553
//! <b>Complexity</b>: Constant.
554
size_type size() const BOOST_CONTAINER_NOEXCEPT
555
{ return this->icont().size(); }
557
//! <b>Effects</b>: Returns the largest possible size of the list.
559
//! <b>Throws</b>: Nothing.
561
//! <b>Complexity</b>: Constant.
562
size_type max_size() const BOOST_CONTAINER_NOEXCEPT
563
{ return AllocHolder::max_size(); }
565
//! <b>Effects</b>: Inserts or erases elements at the end such that
566
//! the size becomes n. New elements are value initialized.
568
//! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
570
//! <b>Complexity</b>: Linear to the difference between size() and new_size.
571
void resize(size_type new_size)
573
if(!priv_try_shrink(new_size)){
574
typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
575
this->insert(this->cend(), value_init_iterator(new_size - this->size()), value_init_iterator());
579
//! <b>Effects</b>: Inserts or erases elements at the end such that
580
//! the size becomes n. New elements are copy constructed from x.
582
//! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
584
//! <b>Complexity</b>: Linear to the difference between size() and new_size.
585
void resize(size_type new_size, const T& x)
587
if(!priv_try_shrink(new_size)){
588
this->insert(this->cend(), new_size - this->size(), x);
592
//////////////////////////////////////////////
596
//////////////////////////////////////////////
598
//! <b>Requires</b>: !empty()
600
//! <b>Effects</b>: Returns a reference to the first element
601
//! from the beginning of the container.
603
//! <b>Throws</b>: Nothing.
605
//! <b>Complexity</b>: Constant.
606
reference front() BOOST_CONTAINER_NOEXCEPT
607
{ return *this->begin(); }
609
//! <b>Requires</b>: !empty()
611
//! <b>Effects</b>: Returns a const reference to the first element
612
//! from the beginning of the container.
614
//! <b>Throws</b>: Nothing.
616
//! <b>Complexity</b>: Constant.
617
const_reference front() const BOOST_CONTAINER_NOEXCEPT
618
{ return *this->begin(); }
620
//! <b>Requires</b>: !empty()
622
//! <b>Effects</b>: Returns a reference to the first element
623
//! from the beginning of the container.
625
//! <b>Throws</b>: Nothing.
627
//! <b>Complexity</b>: Constant.
628
reference back() BOOST_CONTAINER_NOEXCEPT
629
{ return *(--this->end()); }
631
//! <b>Requires</b>: !empty()
633
//! <b>Effects</b>: Returns a const reference to the first element
634
//! from the beginning of the container.
636
//! <b>Throws</b>: Nothing.
638
//! <b>Complexity</b>: Constant.
639
const_reference back() const BOOST_CONTAINER_NOEXCEPT
640
{ return *(--this->end()); }
642
//////////////////////////////////////////////
646
//////////////////////////////////////////////
648
#if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
650
//! <b>Effects</b>: Inserts an object of type T constructed with
651
//! std::forward<Args>(args)... in the end of the list.
653
//! <b>Throws</b>: If memory allocation throws or
654
//! T's in-place constructor throws.
656
//! <b>Complexity</b>: Constant
657
template <class... Args>
658
void emplace_back(Args&&... args)
659
{ this->emplace(this->cend(), boost::forward<Args>(args)...); }
661
//! <b>Effects</b>: Inserts an object of type T constructed with
662
//! std::forward<Args>(args)... in the beginning of the list.
664
//! <b>Throws</b>: If memory allocation throws or
665
//! T's in-place constructor throws.
667
//! <b>Complexity</b>: Constant
668
template <class... Args>
669
void emplace_front(Args&&... args)
670
{ this->emplace(this->cbegin(), boost::forward<Args>(args)...); }
672
//! <b>Effects</b>: Inserts an object of type T constructed with
673
//! std::forward<Args>(args)... before p.
675
//! <b>Throws</b>: If memory allocation throws or
676
//! T's in-place constructor throws.
678
//! <b>Complexity</b>: Constant
679
template <class... Args>
680
iterator emplace(const_iterator p, Args&&... args)
682
NodePtr pnode(AllocHolder::create_node(boost::forward<Args>(args)...));
683
return iterator(this->icont().insert(p.get(), *pnode));
686
#else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
688
#define BOOST_PP_LOCAL_MACRO(n) \
689
BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
690
void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
692
this->emplace(this->cend() \
693
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
696
BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
697
void emplace_front(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
699
this->emplace(this->cbegin() \
700
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \
703
BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
704
iterator emplace(const_iterator p \
705
BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
707
NodePtr pnode (AllocHolder::create_node \
708
(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \
709
return iterator(this->icont().insert(p.get(), *pnode)); \
712
#define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
713
#include BOOST_PP_LOCAL_ITERATE()
715
#endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
717
#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
718
//! <b>Effects</b>: Inserts a copy of x at the beginning of the list.
720
//! <b>Throws</b>: If memory allocation throws or
721
//! T's copy constructor throws.
723
//! <b>Complexity</b>: Amortized constant time.
724
void push_front(const T &x);
726
//! <b>Effects</b>: Constructs a new element in the beginning of the list
727
//! and moves the resources of mx to this new element.
729
//! <b>Throws</b>: If memory allocation throws.
731
//! <b>Complexity</b>: Amortized constant time.
732
void push_front(T &&x);
734
BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
737
#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
738
//! <b>Effects</b>: Inserts a copy of x at the end of the list.
740
//! <b>Throws</b>: If memory allocation throws or
741
//! T's copy constructor throws.
743
//! <b>Complexity</b>: Amortized constant time.
744
void push_back(const T &x);
746
//! <b>Effects</b>: Constructs a new element in the end of the list
747
//! and moves the resources of mx to this new element.
749
//! <b>Throws</b>: If memory allocation throws.
751
//! <b>Complexity</b>: Amortized constant time.
752
void push_back(T &&x);
754
BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
757
#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
758
//! <b>Requires</b>: position must be a valid iterator of *this.
760
//! <b>Effects</b>: Insert a copy of x before position.
762
//! <b>Returns</b>: an iterator to the inserted element.
764
//! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
766
//! <b>Complexity</b>: Amortized constant time.
767
iterator insert(const_iterator position, const T &x);
769
//! <b>Requires</b>: position must be a valid iterator of *this.
771
//! <b>Effects</b>: Insert a new element before position with mx's resources.
773
//! <b>Returns</b>: an iterator to the inserted element.
775
//! <b>Throws</b>: If memory allocation throws.
777
//! <b>Complexity</b>: Amortized constant time.
778
iterator insert(const_iterator position, T &&x);
780
BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
783
//! <b>Requires</b>: p must be a valid iterator of *this.
785
//! <b>Effects</b>: Inserts n copies of x before p.
787
//! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
789
//! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
791
//! <b>Complexity</b>: Linear to n.
792
iterator insert(const_iterator p, size_type n, const T& x)
794
typedef constant_iterator<value_type, difference_type> cvalue_iterator;
795
return this->insert(p, cvalue_iterator(x, n), cvalue_iterator());
798
//! <b>Requires</b>: p must be a valid iterator of *this.
800
//! <b>Effects</b>: Insert a copy of the [first, last) range before p.
802
//! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
804
//! <b>Throws</b>: If memory allocation throws, T's constructor from a
805
//! dereferenced InpIt throws.
807
//! <b>Complexity</b>: Linear to std::distance [first, last).
808
template <class InpIt>
809
iterator insert(const_iterator p, InpIt first, InpIt last
810
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
811
, typename container_detail::enable_if_c
812
< !container_detail::is_convertible<InpIt, size_type>::value
813
&& (container_detail::is_input_iterator<InpIt>::value
814
|| container_detail::is_same<alloc_version, allocator_v1>::value
820
const typename Icont::iterator ipos(p.get());
821
iterator ret_it(ipos);
823
ret_it = iterator(this->icont().insert(ipos, *this->create_node_from_it(first)));
826
for (; first != last; ++first){
827
this->icont().insert(ipos, *this->create_node_from_it(first));
832
#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
833
template <class FwdIt>
834
iterator insert(const_iterator p, FwdIt first, FwdIt last
835
, typename container_detail::enable_if_c
836
< !container_detail::is_convertible<FwdIt, size_type>::value
837
&& !(container_detail::is_input_iterator<FwdIt>::value
838
|| container_detail::is_same<alloc_version, allocator_v1>::value
843
//Optimized allocation and construction
844
insertion_functor func(this->icont(), p.get());
845
iterator before_p(p.get());
847
this->allocate_many_and_construct(first, std::distance(first, last), func);
852
//! <b>Effects</b>: Removes the first element from the list.
854
//! <b>Throws</b>: Nothing.
856
//! <b>Complexity</b>: Amortized constant time.
857
void pop_front() BOOST_CONTAINER_NOEXCEPT
858
{ this->erase(this->cbegin()); }
860
//! <b>Effects</b>: Removes the last element from the list.
862
//! <b>Throws</b>: Nothing.
864
//! <b>Complexity</b>: Amortized constant time.
865
void pop_back() BOOST_CONTAINER_NOEXCEPT
866
{ const_iterator tmp = this->cend(); this->erase(--tmp); }
868
//! <b>Requires</b>: p must be a valid iterator of *this.
870
//! <b>Effects</b>: Erases the element at p p.
872
//! <b>Throws</b>: Nothing.
874
//! <b>Complexity</b>: Amortized constant time.
875
iterator erase(const_iterator p) BOOST_CONTAINER_NOEXCEPT
876
{ return iterator(this->icont().erase_and_dispose(p.get(), Destroyer(this->node_alloc()))); }
878
//! <b>Requires</b>: first and last must be valid iterator to elements in *this.
880
//! <b>Effects</b>: Erases the elements pointed by [first, last).
882
//! <b>Throws</b>: Nothing.
884
//! <b>Complexity</b>: Linear to the distance between first and last.
885
iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
886
{ return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); }
888
//! <b>Effects</b>: Swaps the contents of *this and x.
890
//! <b>Throws</b>: Nothing.
892
//! <b>Complexity</b>: Constant.
894
{ AllocHolder::swap(x); }
896
//! <b>Effects</b>: Erases all the elements of the list.
898
//! <b>Throws</b>: Nothing.
900
//! <b>Complexity</b>: Linear to the number of elements in the list.
901
void clear() BOOST_CONTAINER_NOEXCEPT
902
{ AllocHolder::clear(alloc_version()); }
904
//////////////////////////////////////////////
908
//////////////////////////////////////////////
910
//! <b>Requires</b>: p must point to an element contained
911
//! by the list. x != *this. this' allocator and x's allocator shall compare equal
913
//! <b>Effects</b>: Transfers all the elements of list x to this list, before the
914
//! the element pointed by p. No destructors or copy constructors are called.
916
//! <b>Throws</b>: Nothing
918
//! <b>Complexity</b>: Constant.
920
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of
921
//! this list. Iterators of this list and all the references are not invalidated.
922
void splice(const_iterator p, list& x) BOOST_CONTAINER_NOEXCEPT
924
BOOST_ASSERT(this != &x);
925
BOOST_ASSERT(this->node_alloc() == x.node_alloc());
926
this->icont().splice(p.get(), x.icont());
929
//! <b>Requires</b>: p must point to an element contained
930
//! by the list. x != *this. this' allocator and x's allocator shall compare equal
932
//! <b>Effects</b>: Transfers all the elements of list x to this list, before the
933
//! the element pointed by p. No destructors or copy constructors are called.
935
//! <b>Throws</b>: Nothing
937
//! <b>Complexity</b>: Constant.
939
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of
940
//! this list. Iterators of this list and all the references are not invalidated.
941
void splice(const_iterator p, BOOST_RV_REF(list) x) BOOST_CONTAINER_NOEXCEPT
942
{ this->splice(p, static_cast<list&>(x)); }
944
//! <b>Requires</b>: p must point to an element contained
945
//! by this list. i must point to an element contained in list x.
946
//! this' allocator and x's allocator shall compare equal
948
//! <b>Effects</b>: Transfers the value pointed by i, from list x to this list,
949
//! before the the element pointed by p. No destructors or copy constructors are called.
950
//! If p == i or p == ++i, this function is a null operation.
952
//! <b>Throws</b>: Nothing
954
//! <b>Complexity</b>: Constant.
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.
958
void splice(const_iterator p, list &x, const_iterator i) BOOST_CONTAINER_NOEXCEPT
960
//BOOST_ASSERT(this != &x);
961
BOOST_ASSERT(this->node_alloc() == x.node_alloc());
962
this->icont().splice(p.get(), x.icont(), i.get());
965
//! <b>Requires</b>: p must point to an element contained
966
//! by this list. i must point to an element contained in list x.
967
//! this' allocator and x's allocator shall compare equal.
969
//! <b>Effects</b>: Transfers the value pointed by i, from list x to this list,
970
//! before the the element pointed by p. No destructors or copy constructors are called.
971
//! If p == i or p == ++i, this function is a null operation.
973
//! <b>Throws</b>: Nothing
975
//! <b>Complexity</b>: Constant.
977
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
978
//! list. Iterators of this list and all the references are not invalidated.
979
void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator i) BOOST_CONTAINER_NOEXCEPT
980
{ this->splice(p, static_cast<list&>(x), i); }
982
//! <b>Requires</b>: p must point to an element contained
983
//! by this list. first and last must point to elements contained in list x.
984
//! this' allocator and x's allocator shall compare equal
986
//! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
987
//! before the the element pointed by p. No destructors or copy constructors are called.
989
//! <b>Throws</b>: Nothing
991
//! <b>Complexity</b>: Linear to the number of elements transferred.
993
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
994
//! list. Iterators of this list and all the references are not invalidated.
995
void splice(const_iterator p, list &x, const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
997
BOOST_ASSERT(this->node_alloc() == x.node_alloc());
998
this->icont().splice(p.get(), x.icont(), first.get(), last.get());
1001
//! <b>Requires</b>: p must point to an element contained
1002
//! by this list. first and last must point to elements contained in list x.
1003
//! this' allocator and x's allocator shall compare equal.
1005
//! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1006
//! before the the element pointed by p. No destructors or copy constructors are called.
1008
//! <b>Throws</b>: Nothing
1010
//! <b>Complexity</b>: Linear to the number of elements transferred.
1012
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1013
//! list. Iterators of this list and all the references are not invalidated.
1014
void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
1015
{ this->splice(p, static_cast<list&>(x), first, last); }
1017
//! <b>Requires</b>: p must point to an element contained
1018
//! by this list. first and last must point to elements contained in list x.
1019
//! n == std::distance(first, last). this' allocator and x's allocator shall compare equal
1021
//! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1022
//! before the the element pointed by p. No destructors or copy constructors are called.
1024
//! <b>Throws</b>: Nothing
1026
//! <b>Complexity</b>: Constant.
1028
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1029
//! list. Iterators of this list and all the references are not invalidated.
1031
//! <b>Note</b>: Non-standard extension
1032
void splice(const_iterator p, list &x, const_iterator first, const_iterator last, size_type n) BOOST_CONTAINER_NOEXCEPT
1034
BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1035
this->icont().splice(p.get(), x.icont(), first.get(), last.get(), n);
1038
//! <b>Requires</b>: p must point to an element contained
1039
//! by this list. first and last must point to elements contained in list x.
1040
//! n == std::distance(first, last). this' allocator and x's allocator shall compare equal
1042
//! <b>Effects</b>: Transfers the range pointed by first and last from list x to this list,
1043
//! before the the element pointed by p. No destructors or copy constructors are called.
1045
//! <b>Throws</b>: Nothing
1047
//! <b>Complexity</b>: Constant.
1049
//! <b>Note</b>: Iterators of values obtained from list x now point to elements of this
1050
//! list. Iterators of this list and all the references are not invalidated.
1052
//! <b>Note</b>: Non-standard extension
1053
void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last, size_type n) BOOST_CONTAINER_NOEXCEPT
1054
{ this->splice(p, static_cast<list&>(x), first, last, n); }
1056
//! <b>Effects</b>: Removes all the elements that compare equal to value.
1058
//! <b>Throws</b>: If comparison throws.
1060
//! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality.
1062
//! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1063
//! and iterators to elements that are not removed remain valid.
1064
void remove(const T& value)
1065
{ this->remove_if(equal_to_value(value)); }
1067
//! <b>Effects</b>: Removes all the elements for which a specified
1068
//! predicate is satisfied.
1070
//! <b>Throws</b>: If pred throws.
1072
//! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate.
1074
//! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1075
//! and iterators to elements that are not removed remain valid.
1076
template <class Pred>
1077
void remove_if(Pred pred)
1079
typedef ValueCompareToNodeCompare<Pred> Predicate;
1080
this->icont().remove_and_dispose_if(Predicate(pred), Destroyer(this->node_alloc()));
1083
//! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1084
//! elements that are equal from the list.
1086
//! <b>Throws</b>: If comparison throws.
1088
//! <b>Complexity</b>: Linear time (size()-1 comparisons equality comparisons).
1090
//! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1091
//! and iterators to elements that are not removed remain valid.
1093
{ this->unique(value_equal()); }
1095
//! <b>Effects</b>: Removes adjacent duplicate elements or adjacent
1096
//! elements that satisfy some binary predicate from the list.
1098
//! <b>Throws</b>: If pred throws.
1100
//! <b>Complexity</b>: Linear time (size()-1 comparisons calls to pred()).
1102
//! <b>Note</b>: The relative order of elements that are not removed is unchanged,
1103
//! and iterators to elements that are not removed remain valid.
1104
template <class BinaryPredicate>
1105
void unique(BinaryPredicate binary_pred)
1107
typedef ValueCompareToNodeCompare<BinaryPredicate> Predicate;
1108
this->icont().unique_and_dispose(Predicate(binary_pred), Destroyer(this->node_alloc()));
1111
//! <b>Requires</b>: The lists x and *this must be distinct.
1113
//! <b>Effects</b>: This function removes all of x's elements and inserts them
1114
//! in order into *this according to std::less<value_type>. The merge is stable;
1115
//! that is, if an element from *this is equivalent to one from x, then the element
1116
//! from *this will precede the one from x.
1118
//! <b>Throws</b>: If comparison throws.
1120
//! <b>Complexity</b>: This function is linear time: it performs at most
1121
//! size() + x.size() - 1 comparisons.
1123
{ this->merge(x, value_less()); }
1125
//! <b>Requires</b>: The lists x and *this must be distinct.
1127
//! <b>Effects</b>: This function removes all of x's elements and inserts them
1128
//! in order into *this according to std::less<value_type>. The merge is stable;
1129
//! that is, if an element from *this is equivalent to one from x, then the element
1130
//! from *this will precede the one from x.
1132
//! <b>Throws</b>: If comparison throws.
1134
//! <b>Complexity</b>: This function is linear time: it performs at most
1135
//! size() + x.size() - 1 comparisons.
1136
void merge(BOOST_RV_REF(list) x)
1137
{ this->merge(static_cast<list&>(x)); }
1139
//! <b>Requires</b>: p must be a comparison function that induces a strict weak
1140
//! ordering and both *this and x must be sorted according to that ordering
1141
//! The lists x and *this must be distinct.
1143
//! <b>Effects</b>: This function removes all of x's elements and inserts them
1144
//! in order into *this. The merge is stable; that is, if an element from *this is
1145
//! equivalent to one from x, then the element from *this will precede the one from x.
1147
//! <b>Throws</b>: If comp throws.
1149
//! <b>Complexity</b>: This function is linear time: it performs at most
1150
//! size() + x.size() - 1 comparisons.
1152
//! <b>Note</b>: Iterators and references to *this are not invalidated.
1153
template <class StrictWeakOrdering>
1154
void merge(list &x, const StrictWeakOrdering &comp)
1156
BOOST_ASSERT(this->node_alloc() == x.node_alloc());
1157
this->icont().merge(x.icont(),
1158
ValueCompareToNodeCompare<StrictWeakOrdering>(comp));
1161
//! <b>Requires</b>: p must be a comparison function that induces a strict weak
1162
//! ordering and both *this and x must be sorted according to that ordering
1163
//! The lists x and *this must be distinct.
1165
//! <b>Effects</b>: This function removes all of x's elements and inserts them
1166
//! in order into *this. The merge is stable; that is, if an element from *this is
1167
//! equivalent to one from x, then the element from *this will precede the one from x.
1169
//! <b>Throws</b>: If comp throws.
1171
//! <b>Complexity</b>: This function is linear time: it performs at most
1172
//! size() + x.size() - 1 comparisons.
1174
//! <b>Note</b>: Iterators and references to *this are not invalidated.
1175
template <class StrictWeakOrdering>
1176
void merge(BOOST_RV_REF(list) x, StrictWeakOrdering comp)
1177
{ this->merge(static_cast<list&>(x), comp); }
1179
//! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1180
//! The sort is stable, that is, the relative order of equivalent elements is preserved.
1182
//! <b>Throws</b>: If comparison throws.
1184
//! <b>Notes</b>: Iterators and references are not invalidated.
1186
//! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1187
//! is the list's size.
1189
{ this->sort(value_less()); }
1191
//! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>.
1192
//! The sort is stable, that is, the relative order of equivalent elements is preserved.
1194
//! <b>Throws</b>: If comp throws.
1196
//! <b>Notes</b>: Iterators and references are not invalidated.
1198
//! <b>Complexity</b>: The number of comparisons is approximately N log N, where N
1199
//! is the list's size.
1200
template <class StrictWeakOrdering>
1201
void sort(StrictWeakOrdering comp)
1203
// nothing if the list has length 0 or 1.
1204
if (this->size() < 2)
1206
this->icont().sort(ValueCompareToNodeCompare<StrictWeakOrdering>(comp));
1209
//! <b>Effects</b>: Reverses the order of elements in the list.
1211
//! <b>Throws</b>: Nothing.
1213
//! <b>Complexity</b>: This function is linear time.
1215
//! <b>Note</b>: Iterators and references are not invalidated
1216
void reverse() BOOST_CONTAINER_NOEXCEPT
1217
{ this->icont().reverse(); }
1222
bool priv_try_shrink(size_type new_size)
1224
const size_type len = this->size();
1226
const const_iterator iend = this->cend();
1227
size_type to_erase = len - new_size;
1228
const_iterator ifirst;
1229
if(to_erase < len/2u){
1236
ifirst = this->cbegin();
1237
size_type to_skip = len - to_erase;
1242
this->erase(ifirst, iend);
1250
iterator priv_insert(const_iterator p, const T &x)
1252
NodePtr tmp = AllocHolder::create_node(x);
1253
return iterator(this->icont().insert(p.get(), *tmp));
1256
iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x)
1258
NodePtr tmp = AllocHolder::create_node(boost::move(x));
1259
return iterator(this->icont().insert(p.get(), *tmp));
1262
void priv_push_back (const T &x)
1263
{ this->insert(this->cend(), x); }
1265
void priv_push_back (BOOST_RV_REF(T) x)
1266
{ this->insert(this->cend(), boost::move(x)); }
1268
void priv_push_front (const T &x)
1269
{ this->insert(this->cbegin(), x); }
1271
void priv_push_front (BOOST_RV_REF(T) x)
1272
{ this->insert(this->cbegin(), boost::move(x)); }
1274
class insertion_functor;
1275
friend class insertion_functor;
1277
class insertion_functor
1280
typedef typename Icont::const_iterator iconst_iterator;
1281
const iconst_iterator pos_;
1284
insertion_functor(Icont &icont, typename Icont::const_iterator pos)
1285
: icont_(icont), pos_(pos)
1288
void operator()(Node &n)
1290
this->icont_.insert(pos_, n);
1294
//Functors for member algorithm defaults
1297
bool operator()(const value_type &a, const value_type &b) const
1303
bool operator()(const value_type &a, const value_type &b) const
1310
template <class T, class Allocator>
1311
inline bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y)
1313
if(x.size() != y.size()){
1316
typedef typename list<T,Allocator>::const_iterator const_iterator;
1317
const_iterator end1 = x.end();
1319
const_iterator i1 = x.begin();
1320
const_iterator i2 = y.begin();
1321
while (i1 != end1 && *i1 == *i2) {
1328
template <class T, class Allocator>
1329
inline bool operator<(const list<T,Allocator>& x,
1330
const list<T,Allocator>& y)
1332
return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
1335
template <class T, class Allocator>
1336
inline bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y)
1341
template <class T, class Allocator>
1342
inline bool operator>(const list<T,Allocator>& x, const list<T,Allocator>& y)
1347
template <class T, class Allocator>
1348
inline bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y)
1353
template <class T, class Allocator>
1354
inline bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y)
1359
template <class T, class Allocator>
1360
inline void swap(list<T, Allocator>& x, list<T, Allocator>& y)
1367
} //namespace container {
1369
//!has_trivial_destructor_after_move<> == true_type
1370
//!specialization for optimizations
1371
template <class T, class Allocator>
1372
struct has_trivial_destructor_after_move<boost::container::list<T, Allocator> >
1373
: public ::boost::has_trivial_destructor_after_move<Allocator>
1376
namespace container {
1382
#include <boost/container/detail/config_end.hpp>
1384
#endif // BOOST_CONTAINER_LIST_HPP
added
removed
deps/boost_intern/boost/container/list.hpp
