1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2008-2015. 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)
6//
7// See http://www.boost.org/libs/container for documentation.
8//
9//////////////////////////////////////////////////////////////////////////////
10// Stable vector.
11//
12// Copyright 2008 Joaquin M Lopez Munoz.
13// Distributed under the Boost Software License, Version 1.0.
14// (See accompanying file LICENSE_1_0.txt or copy at
15// http://www.boost.org/LICENSE_1_0.txt)
16//
17//////////////////////////////////////////////////////////////////////////////
18
19#ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP
20#define BOOST_CONTAINER_STABLE_VECTOR_HPP
21
22#ifndef BOOST_CONFIG_HPP
23# include <boost/config.hpp>
24#endif
25
26#if defined(BOOST_HAS_PRAGMA_ONCE)
27# pragma once
28#endif
29
30#include <boost/container/detail/config_begin.hpp>
31#include <boost/container/detail/workaround.hpp>
32
33// container
34#include <boost/container/allocator_traits.hpp>
35#include <boost/container/container_fwd.hpp>
36#include <boost/container/new_allocator.hpp> //new_allocator
37#include <boost/container/throw_exception.hpp>
38// container/detail
39#include <boost/container/detail/addressof.hpp>
40#include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare
41#include <boost/container/detail/alloc_helpers.hpp>
42#include <boost/container/detail/allocator_version_traits.hpp>
43#include <boost/container/detail/construct_in_place.hpp>
44#include <boost/container/detail/iterator.hpp>
45#include <boost/container/detail/iterators.hpp>
46#include <boost/container/detail/placement_new.hpp>
47#include <boost/container/detail/to_raw_pointer.hpp>
48#include <boost/container/detail/type_traits.hpp>
49// intrusive
50#include <boost/intrusive/pointer_traits.hpp>
51// intrusive/detail
52#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
53// move
54#include <boost/move/utility_core.hpp>
55#include <boost/move/iterator.hpp>
56#include <boost/move/adl_move_swap.hpp>
57// move/detail
58#include <boost/move/detail/move_helpers.hpp>
59// other
60#include <boost/assert.hpp>
61#include <boost/core/no_exceptions_support.hpp>
62// std
63#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
64#include <initializer_list>
65#endif
66
67#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
68 #include <boost/container/vector.hpp>
69 //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
70#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
71
72namespace boost {
73namespace container {
74
75#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
76
77namespace stable_vector_detail{
78
79template <class C>
80class clear_on_destroy
81{
82 public:
83 clear_on_destroy(C &c)
84 : c_(c), do_clear_(true)
85 {}
86
87 void release()
88 { do_clear_ = false; }
89
90 ~clear_on_destroy()
91 {
92 if(do_clear_){
93 c_.clear();
94 c_.priv_clear_pool();
95 }
96 }
97
98 private:
99 clear_on_destroy(const clear_on_destroy &);
100 clear_on_destroy &operator=(const clear_on_destroy &);
101 C &c_;
102 bool do_clear_;
103};
104
105template<typename Pointer>
106struct node;
107
108template<class VoidPtr>
109struct node_base
110{
111 private:
112 typedef typename boost::intrusive::
113 pointer_traits<VoidPtr> void_ptr_traits;
114 typedef typename void_ptr_traits::
115 template rebind_pointer
116 <node_base>::type node_base_ptr;
117 typedef typename void_ptr_traits::
118 template rebind_pointer
119 <node_base_ptr>::type node_base_ptr_ptr;
120
121 public:
122 node_base(const node_base_ptr_ptr &n)
123 : up(n)
124 {}
125
126 node_base()
127 : up()
128 {}
129
130 node_base_ptr_ptr up;
131};
132
133template<typename Pointer>
134struct node
135 : public node_base
136 <typename ::boost::intrusive::pointer_traits<Pointer>::template
137 rebind_pointer<void>::type
138 >
139{
140 private:
141 node();
142
143 public:
144 typename ::boost::intrusive::pointer_traits<Pointer>::element_type value;
145};
146
147template<class VoidPtr, class VoidAllocator>
148struct index_traits
149{
150 typedef boost::intrusive::
151 pointer_traits
152 <VoidPtr> void_ptr_traits;
153 typedef stable_vector_detail::
154 node_base<VoidPtr> node_base_type;
155 typedef typename void_ptr_traits::template
156 rebind_pointer<node_base_type>::type node_base_ptr;
157 typedef typename void_ptr_traits::template
158 rebind_pointer<node_base_ptr>::type node_base_ptr_ptr;
159 typedef boost::intrusive::
160 pointer_traits<node_base_ptr> node_base_ptr_traits;
161 typedef boost::intrusive::
162 pointer_traits<node_base_ptr_ptr> node_base_ptr_ptr_traits;
163 typedef typename allocator_traits<VoidAllocator>::
164 template portable_rebind_alloc
165 <node_base_ptr>::type node_base_ptr_allocator;
166 typedef ::boost::container::vector
167 <node_base_ptr, node_base_ptr_allocator> index_type;
168 typedef typename index_type::iterator index_iterator;
169 typedef typename index_type::const_iterator const_index_iterator;
170 typedef typename index_type::size_type size_type;
171
172 static const size_type ExtraPointers = 3;
173 //Stable vector stores metadata at the end of the index (node_base_ptr vector) with additional 3 pointers:
174 // back() is this->index.back() - ExtraPointers;
175 // end node index is *(this->index.end() - 3)
176 // Node cache first is *(this->index.end() - 2);
177 // Node cache last is this->index.back();
178
179 static node_base_ptr_ptr ptr_to_node_base_ptr(node_base_ptr &n)
180 { return node_base_ptr_ptr_traits::pointer_to(n); }
181
182 static void fix_up_pointers(index_iterator first, index_iterator last)
183 {
184 while(first != last){
185 typedef typename index_type::reference node_base_ptr_ref;
186 node_base_ptr_ref nbp = *first;
187 nbp->up = index_traits::ptr_to_node_base_ptr(n&: nbp);
188 ++first;
189 }
190 }
191
192 static index_iterator get_fix_up_end(index_type &index)
193 { return index.end() - (ExtraPointers - 1); }
194
195 static void fix_up_pointers_from(index_type & index, index_iterator first)
196 { index_traits::fix_up_pointers(first, last: index_traits::get_fix_up_end(index)); }
197
198 static void readjust_end_node(index_type &index, node_base_type &end_node)
199 {
200 if(!index.empty()){
201 index_iterator end_node_it(index_traits::get_fix_up_end(index));
202 node_base_ptr &end_node_idx_ref = *(--end_node_it);
203 end_node_idx_ref = node_base_ptr_traits::pointer_to(end_node);
204 end_node.up = node_base_ptr_ptr_traits::pointer_to(end_node_idx_ref);
205 }
206 else{
207 end_node.up = node_base_ptr_ptr();
208 }
209 }
210
211 static void initialize_end_node(index_type &index, node_base_type &end_node, const size_type index_capacity_if_empty)
212 {
213 if(index.empty()){
214 index.reserve(index_capacity_if_empty + ExtraPointers);
215 index.resize(ExtraPointers);
216 node_base_ptr &end_node_ref = *index.data();
217 end_node_ref = node_base_ptr_traits::pointer_to(end_node);
218 end_node.up = index_traits::ptr_to_node_base_ptr(n&: end_node_ref);
219 }
220 }
221
222 #ifdef STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
223 static bool invariants(index_type &index)
224 {
225 for( index_iterator it = index.begin()
226 , it_end = index_traits::get_fix_up_end(index)
227 ; it != it_end
228 ; ++it){
229 if((*it)->up != index_traits::ptr_to_node_base_ptr(*it)){
230 return false;
231 }
232 }
233 return true;
234 }
235 #endif //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
236};
237
238} //namespace stable_vector_detail
239
240template<typename Pointer, bool IsConst>
241class stable_vector_iterator
242{
243 typedef boost::intrusive::pointer_traits<Pointer> non_const_ptr_traits;
244 public:
245 typedef std::random_access_iterator_tag iterator_category;
246 typedef typename non_const_ptr_traits::element_type value_type;
247 typedef typename non_const_ptr_traits::difference_type difference_type;
248 typedef typename ::boost::container::container_detail::if_c
249 < IsConst
250 , typename non_const_ptr_traits::template
251 rebind_pointer<const value_type>::type
252 , Pointer
253 >::type pointer;
254 typedef boost::intrusive::pointer_traits<pointer> ptr_traits;
255 typedef typename ptr_traits::reference reference;
256
257 private:
258 typedef typename non_const_ptr_traits::template
259 rebind_pointer<void>::type void_ptr;
260 typedef stable_vector_detail::node<Pointer> node_type;
261 typedef stable_vector_detail::node_base<void_ptr> node_base_type;
262 typedef typename non_const_ptr_traits::template
263 rebind_pointer<node_type>::type node_ptr;
264 typedef boost::intrusive::
265 pointer_traits<node_ptr> node_ptr_traits;
266 typedef typename non_const_ptr_traits::template
267 rebind_pointer<node_base_type>::type node_base_ptr;
268 typedef typename non_const_ptr_traits::template
269 rebind_pointer<node_base_ptr>::type node_base_ptr_ptr;
270
271 node_base_ptr m_pn;
272
273 public:
274
275 explicit stable_vector_iterator(node_base_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
276 : m_pn(p)
277 {}
278
279 stable_vector_iterator() BOOST_NOEXCEPT_OR_NOTHROW
280 : m_pn() //Value initialization to achieve "null iterators" (N3644)
281 {}
282
283 stable_vector_iterator(stable_vector_iterator<Pointer, false> const& other) BOOST_NOEXCEPT_OR_NOTHROW
284 : m_pn(other.node_pointer())
285 {}
286
287 node_ptr node_pointer() const BOOST_NOEXCEPT_OR_NOTHROW
288 { return node_ptr_traits::static_cast_from(m_pn); }
289
290 public:
291 //Pointer like operators
292 reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW
293 { return node_pointer()->value; }
294
295 pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
296 { return ptr_traits::pointer_to(this->operator*()); }
297
298 //Increment / Decrement
299 stable_vector_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
300 {
301 node_base_ptr_ptr p(this->m_pn->up);
302 this->m_pn = *(++p);
303 return *this;
304 }
305
306 stable_vector_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
307 { stable_vector_iterator tmp(*this); ++*this; return stable_vector_iterator(tmp); }
308
309 stable_vector_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
310 {
311 node_base_ptr_ptr p(this->m_pn->up);
312 this->m_pn = *(--p);
313 return *this;
314 }
315
316 stable_vector_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
317 { stable_vector_iterator tmp(*this); --*this; return stable_vector_iterator(tmp); }
318
319 reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW
320 { return node_ptr_traits::static_cast_from(this->m_pn->up[off])->value; }
321
322 stable_vector_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
323 {
324 if(off) this->m_pn = this->m_pn->up[off];
325 return *this;
326 }
327
328 friend stable_vector_iterator operator+(const stable_vector_iterator &left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
329 {
330 stable_vector_iterator tmp(left);
331 tmp += off;
332 return tmp;
333 }
334
335 friend stable_vector_iterator operator+(difference_type off, const stable_vector_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW
336 {
337 stable_vector_iterator tmp(right);
338 tmp += off;
339 return tmp;
340 }
341
342 stable_vector_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
343 { *this += -off; return *this; }
344
345 friend stable_vector_iterator operator-(const stable_vector_iterator &left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
346 {
347 stable_vector_iterator tmp(left);
348 tmp -= off;
349 return tmp;
350 }
351
352 friend difference_type operator-(const stable_vector_iterator &left, const stable_vector_iterator &right) BOOST_NOEXCEPT_OR_NOTHROW
353 { return left.m_pn->up - right.m_pn->up; }
354
355 //Comparison operators
356 friend bool operator== (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
357 { return l.m_pn == r.m_pn; }
358
359 friend bool operator!= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
360 { return l.m_pn != r.m_pn; }
361
362 friend bool operator< (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
363 { return l.m_pn->up < r.m_pn->up; }
364
365 friend bool operator<= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
366 { return l.m_pn->up <= r.m_pn->up; }
367
368 friend bool operator> (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
369 { return l.m_pn->up > r.m_pn->up; }
370
371 friend bool operator>= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
372 { return l.m_pn->up >= r.m_pn->up; }
373};
374
375 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
376
377 #define STABLE_VECTOR_CHECK_INVARIANT \
378 invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \
379 BOOST_JOIN(check_invariant_,__LINE__).touch();
380
381 #else //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
382
383 #define STABLE_VECTOR_CHECK_INVARIANT
384
385 #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
386
387#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
388
389//! Originally developed by Joaquin M. Lopez Munoz, stable_vector is a std::vector
390//! drop-in replacement implemented as a node container, offering iterator and reference
391//! stability.
392//!
393//! Here are the details taken from the author's blog
394//! (<a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" >
395//! Introducing stable_vector</a>):
396//!
397//! We present stable_vector, a fully STL-compliant stable container that provides
398//! most of the features of std::vector except element contiguity.
399//!
400//! General properties: stable_vector satisfies all the requirements of a container,
401//! a reversible container and a sequence and provides all the optional operations
402//! present in std::vector. Like std::vector, iterators are random access.
403//! stable_vector does not provide element contiguity; in exchange for this absence,
404//! the container is stable, i.e. references and iterators to an element of a stable_vector
405//! remain valid as long as the element is not erased, and an iterator that has been
406//! assigned the return value of end() always remain valid until the destruction of
407//! the associated stable_vector.
408//!
409//! Operation complexity: The big-O complexities of stable_vector operations match
410//! exactly those of std::vector. In general, insertion/deletion is constant time at
411//! the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector
412//! does not internally perform any value_type destruction, copy or assignment
413//! operations other than those exactly corresponding to the insertion of new
414//! elements or deletion of stored elements, which can sometimes compensate in terms
415//! of performance for the extra burden of doing more pointer manipulation and an
416//! additional allocation per element.
417//!
418//! Exception safety: As stable_vector does not internally copy elements around, some
419//! operations provide stronger exception safety guarantees than in std::vector.
420//!
421//! \tparam T The type of object that is stored in the stable_vector
422//! \tparam Allocator The allocator used for all internal memory management
423#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
424template <class T, class Allocator = new_allocator<T> >
425#else
426template <class T, class Allocator>
427#endif
428class stable_vector
429{
430 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
431 typedef allocator_traits<Allocator> allocator_traits_type;
432 typedef boost::intrusive::
433 pointer_traits
434 <typename allocator_traits_type::pointer> ptr_traits;
435 typedef typename ptr_traits::
436 template rebind_pointer<void>::type void_ptr;
437 typedef typename allocator_traits_type::
438 template portable_rebind_alloc
439 <void>::type void_allocator_type;
440 typedef stable_vector_detail::index_traits
441 <void_ptr, void_allocator_type> index_traits_type;
442 typedef typename index_traits_type::node_base_type node_base_type;
443 typedef typename index_traits_type::node_base_ptr node_base_ptr;
444 typedef typename index_traits_type::
445 node_base_ptr_ptr node_base_ptr_ptr;
446 typedef typename index_traits_type::
447 node_base_ptr_traits node_base_ptr_traits;
448 typedef typename index_traits_type::
449 node_base_ptr_ptr_traits node_base_ptr_ptr_traits;
450 typedef typename index_traits_type::index_type index_type;
451 typedef typename index_traits_type::index_iterator index_iterator;
452 typedef typename index_traits_type::
453 const_index_iterator const_index_iterator;
454 typedef stable_vector_detail::node
455 <typename ptr_traits::pointer> node_type;
456 typedef typename ptr_traits::template
457 rebind_pointer<node_type>::type node_ptr;
458 typedef boost::intrusive::
459 pointer_traits<node_ptr> node_ptr_traits;
460 typedef typename ptr_traits::template
461 rebind_pointer<const node_type>::type const_node_ptr;
462 typedef boost::intrusive::
463 pointer_traits<const_node_ptr> const_node_ptr_traits;
464 typedef typename node_ptr_traits::reference node_reference;
465 typedef typename const_node_ptr_traits::reference const_node_reference;
466
467 typedef ::boost::container::container_detail::integral_constant
468 <unsigned, boost::container::container_detail::
469 version<Allocator>::value> alloc_version;
470 typedef typename allocator_traits_type::
471 template portable_rebind_alloc
472 <node_type>::type node_allocator_type;
473
474 typedef ::boost::container::container_detail::
475 allocator_version_traits<node_allocator_type> allocator_version_traits_t;
476 typedef typename allocator_version_traits_t::multiallocation_chain multiallocation_chain;
477
478 node_ptr allocate_one()
479 { return allocator_version_traits_t::allocate_one(this->priv_node_alloc()); }
480
481 void deallocate_one(const node_ptr &p)
482 { allocator_version_traits_t::deallocate_one(this->priv_node_alloc(), p); }
483
484 void allocate_individual(typename allocator_traits_type::size_type n, multiallocation_chain &m)
485 { allocator_version_traits_t::allocate_individual(this->priv_node_alloc(), n, m); }
486
487 void deallocate_individual(multiallocation_chain &holder)
488 { allocator_version_traits_t::deallocate_individual(this->priv_node_alloc(), holder); }
489
490 friend class stable_vector_detail::clear_on_destroy<stable_vector>;
491 typedef stable_vector_iterator
492 < typename allocator_traits<Allocator>::pointer
493 , false> iterator_impl;
494 typedef stable_vector_iterator
495 < typename allocator_traits<Allocator>::pointer
496 , true> const_iterator_impl;
497 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
498 public:
499
500 //////////////////////////////////////////////
501 //
502 // types
503 //
504 //////////////////////////////////////////////
505 typedef T value_type;
506 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
507 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
508 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
509 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
510 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
511 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
512 typedef Allocator allocator_type;
513 typedef node_allocator_type stored_allocator_type;
514 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
515 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
516 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
517 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
518
519 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
520 private:
521 BOOST_COPYABLE_AND_MOVABLE(stable_vector)
522 static const size_type ExtraPointers = index_traits_type::ExtraPointers;
523
524 class insert_rollback;
525 friend class insert_rollback;
526
527 class push_back_rollback;
528 friend class push_back_rollback;
529 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
530
531 public:
532 //////////////////////////////////////////////
533 //
534 // construct/copy/destroy
535 //
536 //////////////////////////////////////////////
537
538 //! <b>Effects</b>: Default constructs a stable_vector.
539 //!
540 //! <b>Throws</b>: If allocator_type's default constructor throws.
541 //!
542 //! <b>Complexity</b>: Constant.
543 stable_vector()
544 : internal_data(), index()
545 {
546 STABLE_VECTOR_CHECK_INVARIANT;
547 }
548
549 //! <b>Effects</b>: Constructs a stable_vector taking the allocator as parameter.
550 //!
551 //! <b>Throws</b>: Nothing
552 //!
553 //! <b>Complexity</b>: Constant.
554 explicit stable_vector(const allocator_type& al) BOOST_NOEXCEPT_OR_NOTHROW
555 : internal_data(al), index(al)
556 {
557 STABLE_VECTOR_CHECK_INVARIANT;
558 }
559
560 //! <b>Effects</b>: Constructs a stable_vector
561 //! and inserts n value initialized values.
562 //!
563 //! <b>Throws</b>: If allocator_type's default constructor
564 //! throws or T's default or copy constructor throws.
565 //!
566 //! <b>Complexity</b>: Linear to n.
567 explicit stable_vector(size_type n)
568 : internal_data(), index()
569 {
570 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
571 this->resize(n);
572 STABLE_VECTOR_CHECK_INVARIANT;
573 cod.release();
574 }
575
576 //! <b>Effects</b>: Constructs a stable_vector
577 //! and inserts n default initialized values.
578 //!
579 //! <b>Throws</b>: If allocator_type's default constructor
580 //! throws or T's default or copy constructor throws.
581 //!
582 //! <b>Complexity</b>: Linear to n.
583 //!
584 //! <b>Note</b>: Non-standard extension
585 stable_vector(size_type n, default_init_t)
586 : internal_data(), index()
587 {
588 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
589 this->resize(n, default_init);
590 STABLE_VECTOR_CHECK_INVARIANT;
591 cod.release();
592 }
593
594 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
595 //! and inserts n value initialized values.
596 //!
597 //! <b>Throws</b>: If allocator_type's default constructor
598 //! throws or T's default or copy constructor throws.
599 //!
600 //! <b>Complexity</b>: Linear to n.
601 explicit stable_vector(size_type n, const allocator_type &a)
602 : internal_data(), index(a)
603 {
604 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
605 this->resize(n);
606 STABLE_VECTOR_CHECK_INVARIANT;
607 cod.release();
608 }
609
610 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
611 //! and inserts n default initialized values.
612 //!
613 //! <b>Throws</b>: If allocator_type's default constructor
614 //! throws or T's default or copy constructor throws.
615 //!
616 //! <b>Complexity</b>: Linear to n.
617 //!
618 //! <b>Note</b>: Non-standard extension
619 stable_vector(size_type n, default_init_t, const allocator_type &a)
620 : internal_data(), index(a)
621 {
622 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
623 this->resize(n, default_init);
624 STABLE_VECTOR_CHECK_INVARIANT;
625 cod.release();
626 }
627
628 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
629 //! and inserts n copies of value.
630 //!
631 //! <b>Throws</b>: If allocator_type's default constructor
632 //! throws or T's default or copy constructor throws.
633 //!
634 //! <b>Complexity</b>: Linear to n.
635 stable_vector(size_type n, const T& t, const allocator_type& al = allocator_type())
636 : internal_data(al), index(al)
637 {
638 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
639 this->insert(this->cend(), n, t);
640 STABLE_VECTOR_CHECK_INVARIANT;
641 cod.release();
642 }
643
644 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
645 //! and inserts a copy of the range [first, last) in the stable_vector.
646 //!
647 //! <b>Throws</b>: If allocator_type's default constructor
648 //! throws or T's constructor taking a dereferenced InIt throws.
649 //!
650 //! <b>Complexity</b>: Linear to the range [first, last).
651 template <class InputIterator>
652 stable_vector(InputIterator first,InputIterator last, const allocator_type& al = allocator_type())
653 : internal_data(al), index(al)
654 {
655 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
656 this->insert(this->cend(), first, last);
657 STABLE_VECTOR_CHECK_INVARIANT;
658 cod.release();
659 }
660
661 //! <b>Effects</b>: Copy constructs a stable_vector.
662 //!
663 //! <b>Postcondition</b>: x == *this.
664 //!
665 //! <b>Complexity</b>: Linear to the elements x contains.
666 stable_vector(const stable_vector& x)
667 : internal_data(allocator_traits<node_allocator_type>::
668 select_on_container_copy_construction(x.priv_node_alloc()))
669 , index(allocator_traits<allocator_type>::
670 select_on_container_copy_construction(x.index.get_stored_allocator()))
671 {
672 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
673 this->insert(this->cend(), x.begin(), x.end());
674 STABLE_VECTOR_CHECK_INVARIANT;
675 cod.release();
676 }
677
678#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
679 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
680 //! and inserts a copy of the range [il.begin(), il.last()) in the stable_vector
681 //!
682 //! <b>Throws</b>: If allocator_type's default constructor
683 //! throws or T's constructor taking a dereferenced initializer_list iterator throws.
684 //!
685 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
686 stable_vector(std::initializer_list<value_type> il, const allocator_type& l = allocator_type())
687 : internal_data(l), index(l)
688 {
689 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
690 insert(cend(), il.begin(), il.end());
691 STABLE_VECTOR_CHECK_INVARIANT;
692 cod.release();
693 }
694#endif
695
696 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
697 //!
698 //! <b>Throws</b>: If allocator_type's copy constructor throws.
699 //!
700 //! <b>Complexity</b>: Constant.
701 stable_vector(BOOST_RV_REF(stable_vector) x)
702 : internal_data(boost::move(x.priv_node_alloc())), index(boost::move(x.index))
703 {
704 this->priv_swap_members(x);
705 }
706
707 //! <b>Effects</b>: Copy constructs a stable_vector using the specified allocator.
708 //!
709 //! <b>Postcondition</b>: x == *this.
710 //!
711 //! <b>Complexity</b>: Linear to the elements x contains.
712 stable_vector(const stable_vector& x, const allocator_type &a)
713 : internal_data(a), index(a)
714 {
715 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
716 this->insert(this->cend(), x.begin(), x.end());
717 STABLE_VECTOR_CHECK_INVARIANT;
718 cod.release();
719 }
720
721 //! <b>Effects</b>: Move constructor using the specified allocator.
722 //! Moves x's resources to *this.
723 //!
724 //! <b>Throws</b>: If allocator_type's copy constructor throws.
725 //!
726 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
727 stable_vector(BOOST_RV_REF(stable_vector) x, const allocator_type &a)
728 : internal_data(a), index(a)
729 {
730 if(this->priv_node_alloc() == x.priv_node_alloc()){
731 this->index.swap(x.index);
732 this->priv_swap_members(x);
733 }
734 else{
735 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
736 this->insert(this->cend(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end()));
737 STABLE_VECTOR_CHECK_INVARIANT;
738 cod.release();
739 }
740 }
741
742 //! <b>Effects</b>: Destroys the stable_vector. All stored values are destroyed
743 //! and used memory is deallocated.
744 //!
745 //! <b>Throws</b>: Nothing.
746 //!
747 //! <b>Complexity</b>: Linear to the number of elements.
748 ~stable_vector()
749 {
750 this->clear();
751 this->priv_clear_pool();
752 }
753
754 //! <b>Effects</b>: Makes *this contain the same elements as x.
755 //!
756 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
757 //! of each of x's elements.
758 //!
759 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
760 //!
761 //! <b>Complexity</b>: Linear to the number of elements in x.
762 stable_vector& operator=(BOOST_COPY_ASSIGN_REF(stable_vector) x)
763 {
764 STABLE_VECTOR_CHECK_INVARIANT;
765 if (&x != this){
766 node_allocator_type &this_alloc = this->priv_node_alloc();
767 const node_allocator_type &x_alloc = x.priv_node_alloc();
768 container_detail::bool_<allocator_traits_type::
769 propagate_on_container_copy_assignment::value> flag;
770 if(flag && this_alloc != x_alloc){
771 this->clear();
772 this->shrink_to_fit();
773 }
774 container_detail::assign_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
775 container_detail::assign_alloc(this->index.get_stored_allocator(), x.index.get_stored_allocator(), flag);
776 this->assign(x.begin(), x.end());
777 }
778 return *this;
779 }
780
781 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
782 //!
783 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
784 //! before the function.
785 //!
786 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
787 //! is false and (allocation throws or T's move constructor throws)
788 //!
789 //! <b>Complexity</b>: Constant if allocator_traits_type::
790 //! propagate_on_container_move_assignment is true or
791 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
792 stable_vector& operator=(BOOST_RV_REF(stable_vector) x)
793 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
794 || allocator_traits_type::is_always_equal::value)
795 {
796 //for move constructor, no aliasing (&x != this) is assummed.
797 BOOST_ASSERT(this != &x);
798 node_allocator_type &this_alloc = this->priv_node_alloc();
799 node_allocator_type &x_alloc = x.priv_node_alloc();
800 const bool propagate_alloc = allocator_traits_type::
801 propagate_on_container_move_assignment::value;
802 container_detail::bool_<propagate_alloc> flag;
803 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
804 //Resources can be transferred if both allocators are
805 //going to be equal after this function (either propagated or already equal)
806 if(propagate_alloc || allocators_equal){
807 STABLE_VECTOR_CHECK_INVARIANT
808 //Destroy objects but retain memory in case x reuses it in the future
809 this->clear();
810 //Move allocator if needed
811 container_detail::move_alloc(this_alloc, x_alloc, flag);
812 //Take resources
813 this->index.swap(x.index);
814 this->priv_swap_members(x);
815 }
816 //Else do a one by one move
817 else{
818 this->assign( boost::make_move_iterator(x.begin())
819 , boost::make_move_iterator(x.end()));
820 }
821 return *this;
822 }
823
824#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
825 //! <b>Effects</b>: Make *this container contains elements from il.
826 //!
827 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
828 stable_vector& operator=(std::initializer_list<value_type> il)
829 {
830 STABLE_VECTOR_CHECK_INVARIANT;
831 assign(il.begin(), il.end());
832 return *this;
833 }
834#endif
835
836 //! <b>Effects</b>: Assigns the n copies of val to *this.
837 //!
838 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
839 //!
840 //! <b>Complexity</b>: Linear to n.
841 void assign(size_type n, const T& t)
842 {
843 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
844 this->assign(cvalue_iterator(t, n), cvalue_iterator());
845 }
846
847 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
848 //!
849 //! <b>Throws</b>: If memory allocation throws or
850 //! T's constructor from dereferencing InpIt throws.
851 //!
852 //! <b>Complexity</b>: Linear to n.
853 template<typename InputIterator>
854 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
855 typename container_detail::disable_if_convertible<InputIterator, size_type>::type
856 #else
857 void
858 #endif
859 assign(InputIterator first,InputIterator last)
860 {
861 STABLE_VECTOR_CHECK_INVARIANT;
862 iterator first1 = this->begin();
863 iterator last1 = this->end();
864 for ( ; first1 != last1 && first != last; ++first1, ++first)
865 *first1 = *first;
866 if (first == last){
867 this->erase(first1, last1);
868 }
869 else{
870 this->insert(last1, first, last);
871 }
872 }
873
874#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
875 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
876 //!
877 //! <b>Throws</b>: If memory allocation throws or
878 //! T's constructor from dereferencing initializer_list iterator throws.
879 //!
880 void assign(std::initializer_list<value_type> il)
881 {
882 STABLE_VECTOR_CHECK_INVARIANT;
883 assign(il.begin(), il.end());
884 }
885#endif
886
887 //! <b>Effects</b>: Returns a copy of the internal allocator.
888 //!
889 //! <b>Throws</b>: If allocator's copy constructor throws.
890 //!
891 //! <b>Complexity</b>: Constant.
892 allocator_type get_allocator() const
893 { return this->priv_node_alloc(); }
894
895 //! <b>Effects</b>: Returns a reference to the internal allocator.
896 //!
897 //! <b>Throws</b>: Nothing
898 //!
899 //! <b>Complexity</b>: Constant.
900 //!
901 //! <b>Note</b>: Non-standard extension.
902 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
903 { return this->priv_node_alloc(); }
904
905 //! <b>Effects</b>: Returns a reference to the internal allocator.
906 //!
907 //! <b>Throws</b>: Nothing
908 //!
909 //! <b>Complexity</b>: Constant.
910 //!
911 //! <b>Note</b>: Non-standard extension.
912 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
913 { return this->priv_node_alloc(); }
914
915 //////////////////////////////////////////////
916 //
917 // iterators
918 //
919 //////////////////////////////////////////////
920
921 //! <b>Effects</b>: Returns an iterator to the first element contained in the stable_vector.
922 //!
923 //! <b>Throws</b>: Nothing.
924 //!
925 //! <b>Complexity</b>: Constant.
926 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
927 { return (this->index.empty()) ? this->end(): iterator(node_ptr_traits::static_cast_from(this->index.front())); }
928
929 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
930 //!
931 //! <b>Throws</b>: Nothing.
932 //!
933 //! <b>Complexity</b>: Constant.
934 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
935 { return (this->index.empty()) ? this->cend() : const_iterator(node_ptr_traits::static_cast_from(this->index.front())) ; }
936
937 //! <b>Effects</b>: Returns an iterator to the end of the stable_vector.
938 //!
939 //! <b>Throws</b>: Nothing.
940 //!
941 //! <b>Complexity</b>: Constant.
942 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
943 { return iterator(this->priv_get_end_node()); }
944
945 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
946 //!
947 //! <b>Throws</b>: Nothing.
948 //!
949 //! <b>Complexity</b>: Constant.
950 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
951 { return const_iterator(this->priv_get_end_node()); }
952
953 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
954 //! of the reversed stable_vector.
955 //!
956 //! <b>Throws</b>: Nothing.
957 //!
958 //! <b>Complexity</b>: Constant.
959 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
960 { return reverse_iterator(this->end()); }
961
962 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
963 //! of the reversed stable_vector.
964 //!
965 //! <b>Throws</b>: Nothing.
966 //!
967 //! <b>Complexity</b>: Constant.
968 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
969 { return const_reverse_iterator(this->end()); }
970
971 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
972 //! of the reversed stable_vector.
973 //!
974 //! <b>Throws</b>: Nothing.
975 //!
976 //! <b>Complexity</b>: Constant.
977 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
978 { return reverse_iterator(this->begin()); }
979
980 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
981 //! of the reversed stable_vector.
982 //!
983 //! <b>Throws</b>: Nothing.
984 //!
985 //! <b>Complexity</b>: Constant.
986 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
987 { return const_reverse_iterator(this->begin()); }
988
989 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
990 //!
991 //! <b>Throws</b>: Nothing.
992 //!
993 //! <b>Complexity</b>: Constant.
994 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
995 { return this->begin(); }
996
997 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
998 //!
999 //! <b>Throws</b>: Nothing.
1000 //!
1001 //! <b>Complexity</b>: Constant.
1002 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1003 { return this->end(); }
1004
1005 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1006 //! of the reversed stable_vector.
1007 //!
1008 //! <b>Throws</b>: Nothing.
1009 //!
1010 //! <b>Complexity</b>: Constant.
1011 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1012 { return this->rbegin(); }
1013
1014 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1015 //! of the reversed stable_vector.
1016 //!
1017 //! <b>Throws</b>: Nothing.
1018 //!
1019 //! <b>Complexity</b>: Constant.
1020 const_reverse_iterator crend()const BOOST_NOEXCEPT_OR_NOTHROW
1021 { return this->rend(); }
1022
1023 //////////////////////////////////////////////
1024 //
1025 // capacity
1026 //
1027 //////////////////////////////////////////////
1028
1029 //! <b>Effects</b>: Returns true if the stable_vector contains no elements.
1030 //!
1031 //! <b>Throws</b>: Nothing.
1032 //!
1033 //! <b>Complexity</b>: Constant.
1034 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1035 { return this->index.size() <= ExtraPointers; }
1036
1037 //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector.
1038 //!
1039 //! <b>Throws</b>: Nothing.
1040 //!
1041 //! <b>Complexity</b>: Constant.
1042 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1043 {
1044 const size_type index_size = this->index.size();
1045 return (index_size - ExtraPointers) & (size_type(0u) -size_type(index_size != 0));
1046 }
1047
1048 //! <b>Effects</b>: Returns the largest possible size of the stable_vector.
1049 //!
1050 //! <b>Throws</b>: Nothing.
1051 //!
1052 //! <b>Complexity</b>: Constant.
1053 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1054 { return this->index.max_size() - ExtraPointers; }
1055
1056 //! <b>Effects</b>: Inserts or erases elements at the end such that
1057 //! the size becomes n. New elements are value initialized.
1058 //!
1059 //! <b>Throws</b>: If memory allocation throws, or T's value initialization throws.
1060 //!
1061 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1062 void resize(size_type n)
1063 {
1064 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
1065 STABLE_VECTOR_CHECK_INVARIANT;
1066 if(n > this->size())
1067 this->insert(this->cend(), value_init_iterator(n - this->size()), value_init_iterator());
1068 else if(n < this->size())
1069 this->erase(this->cbegin() + n, this->cend());
1070 }
1071
1072 //! <b>Effects</b>: Inserts or erases elements at the end such that
1073 //! the size becomes n. New elements are default initialized.
1074 //!
1075 //! <b>Throws</b>: If memory allocation throws, or T's default initialization throws.
1076 //!
1077 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1078 //!
1079 //! <b>Note</b>: Non-standard extension
1080 void resize(size_type n, default_init_t)
1081 {
1082 typedef default_init_construct_iterator<value_type, difference_type> default_init_iterator;
1083 STABLE_VECTOR_CHECK_INVARIANT;
1084 if(n > this->size())
1085 this->insert(this->cend(), default_init_iterator(n - this->size()), default_init_iterator());
1086 else if(n < this->size())
1087 this->erase(this->cbegin() + n, this->cend());
1088 }
1089
1090 //! <b>Effects</b>: Inserts or erases elements at the end such that
1091 //! the size becomes n. New elements are copy constructed from x.
1092 //!
1093 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1094 //!
1095 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1096 void resize(size_type n, const T& t)
1097 {
1098 STABLE_VECTOR_CHECK_INVARIANT;
1099 if(n > this->size())
1100 this->insert(this->cend(), n - this->size(), t);
1101 else if(n < this->size())
1102 this->erase(this->cbegin() + n, this->cend());
1103 }
1104
1105 //! <b>Effects</b>: Number of elements for which memory has been allocated.
1106 //! capacity() is always greater than or equal to size().
1107 //!
1108 //! <b>Throws</b>: Nothing.
1109 //!
1110 //! <b>Complexity</b>: Constant.
1111 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
1112 {
1113 const size_type index_size = this->index.size();
1114 BOOST_ASSERT(!index_size || index_size >= ExtraPointers);
1115 const size_type node_extra_capacity = this->internal_data.pool_size;
1116 //Pool count must be less than index capacity, as index is a vector
1117 BOOST_ASSERT(node_extra_capacity <= (this->index.capacity()- index_size));
1118 const size_type index_offset =
1119 (node_extra_capacity - ExtraPointers) & (size_type(0u) - size_type(index_size != 0));
1120 return index_size + index_offset;
1121 }
1122
1123 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
1124 //! effect. Otherwise, it is a request for allocation of additional memory.
1125 //! If the request is successful, then capacity() is greater than or equal to
1126 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
1127 //!
1128 //! <b>Throws</b>: If memory allocation allocation throws.
1129 void reserve(size_type n)
1130 {
1131 STABLE_VECTOR_CHECK_INVARIANT;
1132 if(n > this->max_size()){
1133 throw_length_error(str: "stable_vector::reserve max_size() exceeded");
1134 }
1135
1136 size_type sz = this->size();
1137 size_type old_capacity = this->capacity();
1138 if(n > old_capacity){
1139 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, n);
1140 const void * old_ptr = &index[0];
1141 this->index.reserve(n + ExtraPointers);
1142 bool realloced = &index[0] != old_ptr;
1143 //Fix the pointers for the newly allocated buffer
1144 if(realloced){
1145 index_traits_type::fix_up_pointers_from(this->index, this->index.begin());
1146 }
1147 //Now fill pool if data is not enough
1148 if((n - sz) > this->internal_data.pool_size){
1149 this->priv_increase_pool((n - sz) - this->internal_data.pool_size);
1150 }
1151 }
1152 }
1153
1154 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1155 //! with previous allocations. The size of the stable_vector is unchanged
1156 //!
1157 //! <b>Throws</b>: If memory allocation throws.
1158 //!
1159 //! <b>Complexity</b>: Linear to size().
1160 void shrink_to_fit()
1161 {
1162 if(this->capacity()){
1163 //First empty allocated node pool
1164 this->priv_clear_pool();
1165 //If empty completely destroy the index, let's recover default-constructed state
1166 if(this->empty()){
1167 this->index.clear();
1168 this->index.shrink_to_fit();
1169 this->internal_data.end_node.up = node_base_ptr_ptr();
1170 }
1171 //Otherwise, try to shrink-to-fit the index and readjust pointers if necessary
1172 else{
1173 const void* old_ptr = &index[0];
1174 this->index.shrink_to_fit();
1175 bool realloced = &index[0] != old_ptr;
1176 //Fix the pointers for the newly allocated buffer
1177 if(realloced){
1178 index_traits_type::fix_up_pointers_from(this->index, this->index.begin());
1179 }
1180 }
1181 }
1182 }
1183
1184 //////////////////////////////////////////////
1185 //
1186 // element access
1187 //
1188 //////////////////////////////////////////////
1189
1190 //! <b>Requires</b>: !empty()
1191 //!
1192 //! <b>Effects</b>: Returns a reference to the first
1193 //! element of the container.
1194 //!
1195 //! <b>Throws</b>: Nothing.
1196 //!
1197 //! <b>Complexity</b>: Constant.
1198 reference front() BOOST_NOEXCEPT_OR_NOTHROW
1199 {
1200 BOOST_ASSERT(!this->empty());
1201 return static_cast<node_reference>(*this->index.front()).value;
1202 }
1203
1204 //! <b>Requires</b>: !empty()
1205 //!
1206 //! <b>Effects</b>: Returns a const reference to the first
1207 //! element of the container.
1208 //!
1209 //! <b>Throws</b>: Nothing.
1210 //!
1211 //! <b>Complexity</b>: Constant.
1212 const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1213 {
1214 BOOST_ASSERT(!this->empty());
1215 return static_cast<const_node_reference>(*this->index.front()).value;
1216 }
1217
1218 //! <b>Requires</b>: !empty()
1219 //!
1220 //! <b>Effects</b>: Returns a reference to the last
1221 //! element of the container.
1222 //!
1223 //! <b>Throws</b>: Nothing.
1224 //!
1225 //! <b>Complexity</b>: Constant.
1226 reference back() BOOST_NOEXCEPT_OR_NOTHROW
1227 {
1228 BOOST_ASSERT(!this->empty());
1229 return static_cast<node_reference>(*this->index[this->size()-1u]).value;
1230 }
1231
1232 //! <b>Requires</b>: !empty()
1233 //!
1234 //! <b>Effects</b>: Returns a const reference to the last
1235 //! element of the container.
1236 //!
1237 //! <b>Throws</b>: Nothing.
1238 //!
1239 //! <b>Complexity</b>: Constant.
1240 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1241 {
1242 BOOST_ASSERT(!this->empty());
1243 return static_cast<const_node_reference>(*this->index[this->size()-1u]).value;
1244 }
1245
1246 //! <b>Requires</b>: size() > n.
1247 //!
1248 //! <b>Effects</b>: Returns a reference to the nth element
1249 //! from the beginning of the container.
1250 //!
1251 //! <b>Throws</b>: Nothing.
1252 //!
1253 //! <b>Complexity</b>: Constant.
1254 reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1255 {
1256 BOOST_ASSERT(this->size() > n);
1257 return static_cast<node_reference>(*this->index[n]).value;
1258 }
1259
1260 //! <b>Requires</b>: size() > n.
1261 //!
1262 //! <b>Effects</b>: Returns a const reference to the nth element
1263 //! from the beginning of the container.
1264 //!
1265 //! <b>Throws</b>: Nothing.
1266 //!
1267 //! <b>Complexity</b>: Constant.
1268 const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1269 {
1270 BOOST_ASSERT(this->size() > n);
1271 return static_cast<const_node_reference>(*this->index[n]).value;
1272 }
1273
1274 //! <b>Requires</b>: size() >= n.
1275 //!
1276 //! <b>Effects</b>: Returns an iterator to the nth element
1277 //! from the beginning of the container. Returns end()
1278 //! if n == size().
1279 //!
1280 //! <b>Throws</b>: Nothing.
1281 //!
1282 //! <b>Complexity</b>: Constant.
1283 //!
1284 //! <b>Note</b>: Non-standard extension
1285 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1286 {
1287 BOOST_ASSERT(this->size() >= n);
1288 return (this->index.empty()) ? this->end() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
1289 }
1290
1291 //! <b>Requires</b>: size() >= n.
1292 //!
1293 //! <b>Effects</b>: Returns a const_iterator to the nth element
1294 //! from the beginning of the container. Returns end()
1295 //! if n == size().
1296 //!
1297 //! <b>Throws</b>: Nothing.
1298 //!
1299 //! <b>Complexity</b>: Constant.
1300 //!
1301 //! <b>Note</b>: Non-standard extension
1302 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1303 {
1304 BOOST_ASSERT(this->size() >= n);
1305 return (this->index.empty()) ? this->cend() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
1306 }
1307
1308 //! <b>Requires</b>: begin() <= p <= end().
1309 //!
1310 //! <b>Effects</b>: Returns the index of the element pointed by p
1311 //! and size() if p == end().
1312 //!
1313 //! <b>Throws</b>: Nothing.
1314 //!
1315 //! <b>Complexity</b>: Constant.
1316 //!
1317 //! <b>Note</b>: Non-standard extension
1318 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1319 { return this->priv_index_of(p.node_pointer()); }
1320
1321 //! <b>Requires</b>: begin() <= p <= end().
1322 //!
1323 //! <b>Effects</b>: Returns the index of the element pointed by p
1324 //! and size() if p == end().
1325 //!
1326 //! <b>Throws</b>: Nothing.
1327 //!
1328 //! <b>Complexity</b>: Constant.
1329 //!
1330 //! <b>Note</b>: Non-standard extension
1331 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1332 { return this->priv_index_of(p.node_pointer()); }
1333
1334 //! <b>Requires</b>: size() > n.
1335 //!
1336 //! <b>Effects</b>: Returns a reference to the nth element
1337 //! from the beginning of the container.
1338 //!
1339 //! <b>Throws</b>: std::range_error if n >= size()
1340 //!
1341 //! <b>Complexity</b>: Constant.
1342 reference at(size_type n)
1343 {
1344 if(n >= this->size()){
1345 throw_out_of_range(str: "vector::at invalid subscript");
1346 }
1347 return operator[](n);
1348 }
1349
1350 //! <b>Requires</b>: size() > n.
1351 //!
1352 //! <b>Effects</b>: Returns a const reference to the nth element
1353 //! from the beginning of the container.
1354 //!
1355 //! <b>Throws</b>: std::range_error if n >= size()
1356 //!
1357 //! <b>Complexity</b>: Constant.
1358 const_reference at(size_type n)const
1359 {
1360 if(n >= this->size()){
1361 throw_out_of_range(str: "vector::at invalid subscript");
1362 }
1363 return operator[](n);
1364 }
1365
1366 //////////////////////////////////////////////
1367 //
1368 // modifiers
1369 //
1370 //////////////////////////////////////////////
1371
1372 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1373
1374 //! <b>Effects</b>: Inserts an object of type T constructed with
1375 //! std::forward<Args>(args)... in the end of the stable_vector.
1376 //!
1377 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1378 //!
1379 //! <b>Complexity</b>: Amortized constant time.
1380 template<class ...Args>
1381 void emplace_back(Args &&...args)
1382 {
1383 typedef emplace_functor<Args...> EmplaceFunctor;
1384 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
1385 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
1386 this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator());
1387 }
1388
1389 //! <b>Requires</b>: p must be a valid iterator of *this.
1390 //!
1391 //! <b>Effects</b>: Inserts an object of type T constructed with
1392 //! std::forward<Args>(args)... before p
1393 //!
1394 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1395 //!
1396 //! <b>Complexity</b>: If p is end(), amortized constant time
1397 //! Linear time otherwise.
1398 template<class ...Args>
1399 iterator emplace(const_iterator p, Args && ...args)
1400 {
1401 BOOST_ASSERT(this->priv_in_range_or_end(p));
1402 size_type pos_n = p - cbegin();
1403 typedef emplace_functor<Args...> EmplaceFunctor;
1404 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
1405 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
1406 this->insert(p, EmplaceIterator(ef), EmplaceIterator());
1407 return iterator(this->begin() + pos_n);
1408 }
1409
1410 #else
1411
1412 #define BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE(N) \
1413 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1414 void emplace_back(BOOST_MOVE_UREF##N)\
1415 {\
1416 typedef emplace_functor##N\
1417 BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
1418 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;\
1419 EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
1420 this->insert(this->cend() , EmplaceIterator(ef), EmplaceIterator());\
1421 }\
1422 \
1423 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1424 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1425 {\
1426 BOOST_ASSERT(this->priv_in_range_or_end(p));\
1427 typedef emplace_functor##N\
1428 BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
1429 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;\
1430 EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
1431 const size_type pos_n = p - this->cbegin();\
1432 this->insert(p, EmplaceIterator(ef), EmplaceIterator());\
1433 return this->begin() += pos_n;\
1434 }\
1435 //
1436 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE)
1437 #undef BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE
1438
1439 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1440
1441 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1442 //! <b>Effects</b>: Inserts a copy of x at the end of the stable_vector.
1443 //!
1444 //! <b>Throws</b>: If memory allocation throws or
1445 //! T's copy constructor throws.
1446 //!
1447 //! <b>Complexity</b>: Amortized constant time.
1448 void push_back(const T &x);
1449
1450 //! <b>Effects</b>: Constructs a new element in the end of the stable_vector
1451 //! and moves the resources of x to this new element.
1452 //!
1453 //! <b>Throws</b>: If memory allocation throws.
1454 //!
1455 //! <b>Complexity</b>: Amortized constant time.
1456 void push_back(T &&x);
1457 #else
1458 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1459 #endif
1460
1461 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1462 //! <b>Requires</b>: p must be a valid iterator of *this.
1463 //!
1464 //! <b>Effects</b>: Insert a copy of x before p.
1465 //!
1466 //! <b>Returns</b>: An iterator to the inserted element.
1467 //!
1468 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1469 //!
1470 //! <b>Complexity</b>: If p is end(), amortized constant time
1471 //! Linear time otherwise.
1472 iterator insert(const_iterator p, const T &x);
1473
1474 //! <b>Requires</b>: p must be a valid iterator of *this.
1475 //!
1476 //! <b>Effects</b>: Insert a new element before p with x's resources.
1477 //!
1478 //! <b>Returns</b>: an iterator to the inserted element.
1479 //!
1480 //! <b>Throws</b>: If memory allocation throws.
1481 //!
1482 //! <b>Complexity</b>: If p is end(), amortized constant time
1483 //! Linear time otherwise.
1484 iterator insert(const_iterator p, T &&x);
1485 #else
1486 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1487 #endif
1488
1489 //! <b>Requires</b>: p must be a valid iterator of *this.
1490 //!
1491 //! <b>Effects</b>: Insert n copies of x before p.
1492 //!
1493 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
1494 //!
1495 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1496 //!
1497 //! <b>Complexity</b>: Linear to n.
1498 iterator insert(const_iterator p, size_type n, const T& t)
1499 {
1500 BOOST_ASSERT(this->priv_in_range_or_end(p));
1501 STABLE_VECTOR_CHECK_INVARIANT;
1502 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1503 return this->insert(p, cvalue_iterator(t, n), cvalue_iterator());
1504 }
1505
1506 //! <b>Requires</b>: p must be a valid iterator of *this.
1507#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1508 //! <b>Requires</b>: p must be a valid iterator of *this.
1509 //!
1510 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p.
1511 //!
1512 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1513 //!
1514 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
1515 iterator insert(const_iterator p, std::initializer_list<value_type> il)
1516 {
1517 //Position checks done by insert()
1518 STABLE_VECTOR_CHECK_INVARIANT;
1519 return insert(p, il.begin(), il.end());
1520 }
1521#endif
1522
1523 //! <b>Requires</b>: pos must be a valid iterator of *this.
1524 //!
1525 //! <b>Effects</b>: Insert a copy of the [first, last) range before p.
1526 //!
1527 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1528 //!
1529 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1530 //! dereferenced InpIt throws or T's copy constructor throws.
1531 //!
1532 //! <b>Complexity</b>: Linear to distance [first, last).
1533 template <class InputIterator>
1534 iterator insert(const_iterator p, InputIterator first, InputIterator last
1535 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1536 //Put this as argument instead of the return type as old GCC's like 3.4
1537 //detect this and the next disable_if_or as overloads
1538 , typename container_detail::disable_if_or
1539 < void
1540 , container_detail::is_convertible<InputIterator, size_type>
1541 , container_detail::is_not_input_iterator<InputIterator>
1542 >::type* = 0
1543 #endif
1544 )
1545 {
1546 BOOST_ASSERT(this->priv_in_range_or_end(p));
1547 STABLE_VECTOR_CHECK_INVARIANT;
1548 const size_type pos_n = p - this->cbegin();
1549 for(; first != last; ++first){
1550 this->emplace(p, *first);
1551 }
1552 return this->begin() + pos_n;
1553 }
1554
1555 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1556 template <class FwdIt>
1557 typename container_detail::disable_if_or
1558 < iterator
1559 , container_detail::is_convertible<FwdIt, size_type>
1560 , container_detail::is_input_iterator<FwdIt>
1561 >::type
1562 insert(const_iterator p, FwdIt first, FwdIt last)
1563 {
1564 BOOST_ASSERT(this->priv_in_range_or_end(p));
1565 const size_type num_new = static_cast<size_type>(boost::container::iterator_distance(first, last));
1566 const size_type idx = static_cast<size_type>(p - this->cbegin());
1567 if(num_new){
1568 //Fills the node pool and inserts num_new null pointers in idx.
1569 //If a new buffer was needed fixes up pointers up to idx so
1570 //past-new nodes are not aligned until the end of this function
1571 //or in a rollback in case of exception
1572 index_iterator it_past_newly_constructed(this->priv_insert_forward_non_templated(idx, num_new));
1573 const index_iterator it_past_new(it_past_newly_constructed + num_new);
1574 {
1575 //Prepare rollback
1576 insert_rollback rollback(*this, it_past_newly_constructed, it_past_new);
1577 while(first != last){
1578 const node_ptr n = this->priv_get_from_pool();
1579 BOOST_ASSERT(!!n);
1580 //Put it in the index so rollback can return it in pool if construct_in_place throws
1581 *it_past_newly_constructed = n;
1582 //Constructs and fixes up pointers This can throw
1583 this->priv_build_node_from_it(n, it_past_newly_constructed, first);
1584 ++first;
1585 ++it_past_newly_constructed;
1586 }
1587 //rollback.~insert_rollback() called in case of exception
1588 }
1589 //Fix up pointers for past-new nodes (new nodes were fixed during construction) and
1590 //nodes before insertion p in priv_insert_forward_non_templated(...)
1591 index_traits_type::fix_up_pointers_from(this->index, it_past_newly_constructed);
1592 }
1593 return this->begin() + idx;
1594 }
1595 #endif
1596
1597 //! <b>Effects</b>: Removes the last element from the stable_vector.
1598 //!
1599 //! <b>Throws</b>: Nothing.
1600 //!
1601 //! <b>Complexity</b>: Constant time.
1602 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1603 {
1604 BOOST_ASSERT(!this->empty());
1605 this->erase(--this->cend());
1606 }
1607
1608 //! <b>Effects</b>: Erases the element at p.
1609 //!
1610 //! <b>Throws</b>: Nothing.
1611 //!
1612 //! <b>Complexity</b>: Linear to the elements between p and the
1613 //! last element. Constant if p is the last element.
1614 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1615 {
1616 BOOST_ASSERT(this->priv_in_range(p));
1617 STABLE_VECTOR_CHECK_INVARIANT;
1618 const size_type d = p - this->cbegin();
1619 index_iterator it = this->index.begin() + d;
1620 this->priv_delete_node(p.node_pointer());
1621 it = this->index.erase(it);
1622 index_traits_type::fix_up_pointers_from(this->index, it);
1623 return iterator(node_ptr_traits::static_cast_from(*it));
1624 }
1625
1626 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1627 //!
1628 //! <b>Throws</b>: Nothing.
1629 //!
1630 //! <b>Complexity</b>: Linear to the distance between first and last
1631 //! plus linear to the elements between p and the last element.
1632 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1633 {
1634 BOOST_ASSERT(first == last ||
1635 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
1636 STABLE_VECTOR_CHECK_INVARIANT;
1637 const const_iterator cbeg(this->cbegin());
1638 const size_type d1 = static_cast<size_type>(first - cbeg),
1639 d2 = static_cast<size_type>(last - cbeg);
1640 size_type d_dif = d2 - d1;
1641 if(d_dif){
1642 multiallocation_chain holder;
1643 const index_iterator it1(this->index.begin() + d1);
1644 const index_iterator it2(it1 + d_dif);
1645 index_iterator it(it1);
1646 while(d_dif--){
1647 node_base_ptr &nb = *it;
1648 ++it;
1649 node_type &n = *node_ptr_traits::static_cast_from(nb);
1650 this->priv_destroy_node(n);
1651 holder.push_back(node_ptr_traits::pointer_to(n));
1652 }
1653 this->priv_put_in_pool(holder);
1654 const index_iterator e = this->index.erase(it1, it2);
1655 index_traits_type::fix_up_pointers_from(this->index, e);
1656 }
1657 return iterator(last.node_pointer());
1658 }
1659
1660 //! <b>Effects</b>: Swaps the contents of *this and x.
1661 //!
1662 //! <b>Throws</b>: Nothing.
1663 //!
1664 //! <b>Complexity</b>: Constant.
1665 void swap(stable_vector & x)
1666 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
1667 || allocator_traits_type::is_always_equal::value)
1668 {
1669 BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value ||
1670 allocator_traits_type::is_always_equal::value ||
1671 this->get_stored_allocator() == x.get_stored_allocator());
1672 STABLE_VECTOR_CHECK_INVARIANT;
1673 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1674 container_detail::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
1675 //vector's allocator is swapped here
1676 this->index.swap(x.index);
1677 this->priv_swap_members(x);
1678 }
1679
1680 //! <b>Effects</b>: Erases all the elements of the stable_vector.
1681 //!
1682 //! <b>Throws</b>: Nothing.
1683 //!
1684 //! <b>Complexity</b>: Linear to the number of elements in the stable_vector.
1685 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1686 { this->erase(this->cbegin(),this->cend()); }
1687
1688 //! <b>Effects</b>: Returns true if x and y are equal
1689 //!
1690 //! <b>Complexity</b>: Linear to the number of elements in the container.
1691 friend bool operator==(const stable_vector& x, const stable_vector& y)
1692 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1693
1694 //! <b>Effects</b>: Returns true if x and y are unequal
1695 //!
1696 //! <b>Complexity</b>: Linear to the number of elements in the container.
1697 friend bool operator!=(const stable_vector& x, const stable_vector& y)
1698 { return !(x == y); }
1699
1700 //! <b>Effects</b>: Returns true if x is less than y
1701 //!
1702 //! <b>Complexity</b>: Linear to the number of elements in the container.
1703 friend bool operator<(const stable_vector& x, const stable_vector& y)
1704 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1705
1706 //! <b>Effects</b>: Returns true if x is greater than y
1707 //!
1708 //! <b>Complexity</b>: Linear to the number of elements in the container.
1709 friend bool operator>(const stable_vector& x, const stable_vector& y)
1710 { return y < x; }
1711
1712 //! <b>Effects</b>: Returns true if x is equal or less than y
1713 //!
1714 //! <b>Complexity</b>: Linear to the number of elements in the container.
1715 friend bool operator<=(const stable_vector& x, const stable_vector& y)
1716 { return !(y < x); }
1717
1718 //! <b>Effects</b>: Returns true if x is equal or greater than y
1719 //!
1720 //! <b>Complexity</b>: Linear to the number of elements in the container.
1721 friend bool operator>=(const stable_vector& x, const stable_vector& y)
1722 { return !(x < y); }
1723
1724 //! <b>Effects</b>: x.swap(y)
1725 //!
1726 //! <b>Complexity</b>: Constant.
1727 friend void swap(stable_vector& x, stable_vector& y)
1728 { x.swap(y); }
1729
1730 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1731 private:
1732
1733 bool priv_in_range(const_iterator pos) const
1734 {
1735 return (this->begin() <= pos) && (pos < this->end());
1736 }
1737
1738 bool priv_in_range_or_end(const_iterator pos) const
1739 {
1740 return (this->begin() <= pos) && (pos <= this->end());
1741 }
1742
1743 size_type priv_index_of(node_ptr p) const
1744 {
1745 //Check range
1746 BOOST_ASSERT(this->index.empty() || (this->index.data() <= p->up));
1747 BOOST_ASSERT(this->index.empty() || p->up <= (this->index.data() + this->index.size()));
1748 return this->index.empty() ? 0 : p->up - this->index.data();
1749 }
1750
1751 class insert_rollback
1752 {
1753 public:
1754
1755 insert_rollback(stable_vector &sv, index_iterator &it_past_constructed, const index_iterator &it_past_new)
1756 : m_sv(sv), m_it_past_constructed(it_past_constructed), m_it_past_new(it_past_new)
1757 {}
1758
1759 ~insert_rollback()
1760 {
1761 if(m_it_past_constructed != m_it_past_new){
1762 m_sv.priv_put_in_pool(node_ptr_traits::static_cast_from(*m_it_past_constructed));
1763 index_iterator e = m_sv.index.erase(m_it_past_constructed, m_it_past_new);
1764 index_traits_type::fix_up_pointers_from(m_sv.index, e);
1765 }
1766 }
1767
1768 private:
1769 stable_vector &m_sv;
1770 index_iterator &m_it_past_constructed;
1771 const index_iterator &m_it_past_new;
1772 };
1773
1774 class push_back_rollback
1775 {
1776 public:
1777 push_back_rollback(stable_vector &sv, const node_ptr &p)
1778 : m_sv(sv), m_p(p)
1779 {}
1780
1781 ~push_back_rollback()
1782 {
1783 if(m_p){
1784 m_sv.priv_put_in_pool(m_p);
1785 }
1786 }
1787
1788 void release()
1789 { m_p = node_ptr(); }
1790
1791 private:
1792 stable_vector &m_sv;
1793 node_ptr m_p;
1794 };
1795
1796 index_iterator priv_insert_forward_non_templated(size_type idx, size_type num_new)
1797 {
1798 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, num_new);
1799
1800 //Now try to fill the pool with new data
1801 if(this->internal_data.pool_size < num_new){
1802 this->priv_increase_pool(num_new - this->internal_data.pool_size);
1803 }
1804
1805 //Now try to make room in the vector
1806 const node_base_ptr_ptr old_buffer = this->index.data();
1807 this->index.insert(this->index.begin() + idx, num_new, node_ptr());
1808 bool new_buffer = this->index.data() != old_buffer;
1809
1810 //Fix the pointers for the newly allocated buffer
1811 const index_iterator index_beg = this->index.begin();
1812 if(new_buffer){
1813 index_traits_type::fix_up_pointers(index_beg, index_beg + idx);
1814 }
1815 return index_beg + idx;
1816 }
1817
1818 bool priv_capacity_bigger_than_size() const
1819 {
1820 return this->index.capacity() > this->index.size() &&
1821 this->internal_data.pool_size > 0;
1822 }
1823
1824 template <class U>
1825 void priv_push_back(BOOST_MOVE_CATCH_FWD(U) x)
1826 {
1827 if(BOOST_LIKELY(this->priv_capacity_bigger_than_size())){
1828 //Enough memory in the pool and in the index
1829 const node_ptr p = this->priv_get_from_pool();
1830 BOOST_ASSERT(!!p);
1831 {
1832 push_back_rollback rollback(*this, p);
1833 //This might throw
1834 this->priv_build_node_from_convertible(p, ::boost::forward<U>(x));
1835 rollback.release();
1836 }
1837 //This can't throw as there is room for a new elements in the index
1838 index_iterator new_index = this->index.insert(this->index.end() - ExtraPointers, p);
1839 index_traits_type::fix_up_pointers_from(this->index, new_index);
1840 }
1841 else{
1842 this->insert(this->cend(), ::boost::forward<U>(x));
1843 }
1844 }
1845
1846 iterator priv_insert(const_iterator p, const value_type &t)
1847 {
1848 BOOST_ASSERT(this->priv_in_range_or_end(p));
1849 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1850 return this->insert(p, cvalue_iterator(t, 1), cvalue_iterator());
1851 }
1852
1853 iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x)
1854 {
1855 BOOST_ASSERT(this->priv_in_range_or_end(p));
1856 typedef repeat_iterator<T, difference_type> repeat_it;
1857 typedef boost::move_iterator<repeat_it> repeat_move_it;
1858 //Just call more general insert(p, size, value) and return iterator
1859 return this->insert(p, repeat_move_it(repeat_it(x, 1)), repeat_move_it(repeat_it()));
1860 }
1861
1862 void priv_clear_pool()
1863 {
1864 if(!this->index.empty() && this->index.back()){
1865 node_base_ptr &pool_first_ref = *(this->index.end() - 2);
1866 node_base_ptr &pool_last_ref = this->index.back();
1867
1868 multiallocation_chain holder;
1869 holder.incorporate_after( holder.before_begin()
1870 , node_ptr_traits::static_cast_from(pool_first_ref)
1871 , node_ptr_traits::static_cast_from(pool_last_ref)
1872 , internal_data.pool_size);
1873 this->deallocate_individual(holder);
1874 pool_first_ref = pool_last_ref = 0;
1875 this->internal_data.pool_size = 0;
1876 }
1877 }
1878
1879 void priv_increase_pool(size_type n)
1880 {
1881 node_base_ptr &pool_first_ref = *(this->index.end() - 2);
1882 node_base_ptr &pool_last_ref = this->index.back();
1883 multiallocation_chain holder;
1884 holder.incorporate_after( holder.before_begin()
1885 , node_ptr_traits::static_cast_from(pool_first_ref)
1886 , node_ptr_traits::static_cast_from(pool_last_ref)
1887 , internal_data.pool_size);
1888 multiallocation_chain m;
1889 this->allocate_individual(n, m);
1890 holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n);
1891 this->internal_data.pool_size += n;
1892 std::pair<node_ptr, node_ptr> data(holder.extract_data());
1893 pool_first_ref = data.first;
1894 pool_last_ref = data.second;
1895 }
1896
1897 void priv_put_in_pool(const node_ptr &p)
1898 {
1899 node_base_ptr &pool_first_ref = *(this->index.end()-2);
1900 node_base_ptr &pool_last_ref = this->index.back();
1901 multiallocation_chain holder;
1902 holder.incorporate_after( holder.before_begin()
1903 , node_ptr_traits::static_cast_from(pool_first_ref)
1904 , node_ptr_traits::static_cast_from(pool_last_ref)
1905 , internal_data.pool_size);
1906 holder.push_front(p);
1907 ++this->internal_data.pool_size;
1908 std::pair<node_ptr, node_ptr> ret(holder.extract_data());
1909 pool_first_ref = ret.first;
1910 pool_last_ref = ret.second;
1911 }
1912
1913 void priv_put_in_pool(multiallocation_chain &ch)
1914 {
1915 node_base_ptr &pool_first_ref = *(this->index.end()-(ExtraPointers-1));
1916 node_base_ptr &pool_last_ref = this->index.back();
1917 ch.incorporate_after( ch.before_begin()
1918 , node_ptr_traits::static_cast_from(pool_first_ref)
1919 , node_ptr_traits::static_cast_from(pool_last_ref)
1920 , internal_data.pool_size);
1921 this->internal_data.pool_size = ch.size();
1922 const std::pair<node_ptr, node_ptr> ret(ch.extract_data());
1923 pool_first_ref = ret.first;
1924 pool_last_ref = ret.second;
1925 }
1926
1927 node_ptr priv_get_from_pool()
1928 {
1929 //Precondition: index is not empty
1930 BOOST_ASSERT(!this->index.empty());
1931 node_base_ptr &pool_first_ref = *(this->index.end() - (ExtraPointers-1));
1932 node_base_ptr &pool_last_ref = this->index.back();
1933 multiallocation_chain holder;
1934 holder.incorporate_after( holder.before_begin()
1935 , node_ptr_traits::static_cast_from(pool_first_ref)
1936 , node_ptr_traits::static_cast_from(pool_last_ref)
1937 , internal_data.pool_size);
1938 node_ptr ret = holder.pop_front();
1939 --this->internal_data.pool_size;
1940 if(!internal_data.pool_size){
1941 pool_first_ref = pool_last_ref = node_ptr();
1942 }
1943 else{
1944 const std::pair<node_ptr, node_ptr> data(holder.extract_data());
1945 pool_first_ref = data.first;
1946 pool_last_ref = data.second;
1947 }
1948 return ret;
1949 }
1950
1951 node_base_ptr priv_get_end_node() const
1952 { return node_base_ptr_traits::pointer_to(const_cast<node_base_type&>(this->internal_data.end_node)); }
1953
1954 void priv_destroy_node(const node_type &n)
1955 {
1956 allocator_traits<node_allocator_type>::
1957 destroy(this->priv_node_alloc(), container_detail::addressof(n.value));
1958 static_cast<const node_base_type*>(&n)->~node_base_type();
1959 }
1960
1961 void priv_delete_node(const node_ptr &n)
1962 {
1963 this->priv_destroy_node(*n);
1964 this->priv_put_in_pool(n);
1965 }
1966
1967 template<class Iterator>
1968 void priv_build_node_from_it(const node_ptr &p, const index_iterator &up_index, const Iterator &it)
1969 {
1970 //This can throw
1971 boost::container::construct_in_place
1972 ( this->priv_node_alloc()
1973 , container_detail::addressof(p->value)
1974 , it);
1975 //This does not throw
1976 ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t())
1977 node_base_type(index_traits_type::ptr_to_node_base_ptr(*up_index));
1978 }
1979
1980 template<class ValueConvertible>
1981 void priv_build_node_from_convertible(const node_ptr &p, BOOST_FWD_REF(ValueConvertible) value_convertible)
1982 {
1983 //This can throw
1984 boost::container::allocator_traits<node_allocator_type>::construct
1985 ( this->priv_node_alloc()
1986 , container_detail::addressof(p->value)
1987 , ::boost::forward<ValueConvertible>(value_convertible));
1988 //This does not throw
1989 ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) node_base_type;
1990 }
1991
1992 void priv_swap_members(stable_vector &x)
1993 {
1994 boost::adl_move_swap(this->internal_data.pool_size, x.internal_data.pool_size);
1995 index_traits_type::readjust_end_node(this->index, this->internal_data.end_node);
1996 index_traits_type::readjust_end_node(x.index, x.internal_data.end_node);
1997 }
1998
1999 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
2000 bool priv_invariant()const
2001 {
2002 index_type & index_ref = const_cast<index_type&>(this->index);
2003
2004 const size_type index_size = this->index.size();
2005 if(!index_size)
2006 return !this->capacity() && !this->size();
2007
2008 if(index_size < ExtraPointers)
2009 return false;
2010
2011 const size_type bucket_extra_capacity = this->index.capacity()- index_size;
2012 const size_type node_extra_capacity = this->internal_data.pool_size;
2013 if(bucket_extra_capacity < node_extra_capacity){
2014 return false;
2015 }
2016
2017 if(this->priv_get_end_node() != *(index.end() - ExtraPointers)){
2018 return false;
2019 }
2020
2021 if(!index_traits_type::invariants(index_ref)){
2022 return false;
2023 }
2024
2025 size_type n = this->capacity() - this->size();
2026 node_base_ptr &pool_first_ref = *(index_ref.end() - (ExtraPointers-1));
2027 node_base_ptr &pool_last_ref = index_ref.back();
2028 multiallocation_chain holder;
2029 holder.incorporate_after( holder.before_begin()
2030 , node_ptr_traits::static_cast_from(pool_first_ref)
2031 , node_ptr_traits::static_cast_from(pool_last_ref)
2032 , internal_data.pool_size);
2033 typename multiallocation_chain::iterator beg(holder.begin()), end(holder.end());
2034 size_type num_pool = 0;
2035 while(beg != end){
2036 ++num_pool;
2037 ++beg;
2038 }
2039 return n >= num_pool && num_pool == internal_data.pool_size;
2040 }
2041
2042 class invariant_checker
2043 {
2044 invariant_checker(const invariant_checker &);
2045 invariant_checker & operator=(const invariant_checker &);
2046 const stable_vector* p;
2047
2048 public:
2049 invariant_checker(const stable_vector& v):p(&v){}
2050 ~invariant_checker(){BOOST_ASSERT(p->priv_invariant());}
2051 void touch(){}
2052 };
2053 #endif
2054
2055 class ebo_holder
2056 : public node_allocator_type
2057 {
2058 private:
2059 BOOST_MOVABLE_BUT_NOT_COPYABLE(ebo_holder)
2060
2061 public:
2062 template<class AllocatorRLValue>
2063 explicit ebo_holder(BOOST_FWD_REF(AllocatorRLValue) a)
2064 : node_allocator_type(boost::forward<AllocatorRLValue>(a))
2065 , pool_size(0)
2066 , end_node()
2067 {}
2068
2069 ebo_holder()
2070 : node_allocator_type()
2071 , pool_size(0)
2072 , end_node()
2073 {}
2074
2075 size_type pool_size;
2076 node_base_type end_node;
2077 } internal_data;
2078
2079 node_allocator_type &priv_node_alloc() { return internal_data; }
2080 const node_allocator_type &priv_node_alloc() const { return internal_data; }
2081
2082 index_type index;
2083 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2084};
2085
2086#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2087
2088#undef STABLE_VECTOR_CHECK_INVARIANT
2089
2090} //namespace container {
2091
2092//!has_trivial_destructor_after_move<> == true_type
2093//!specialization for optimizations
2094template <class T, class Allocator>
2095struct has_trivial_destructor_after_move<boost::container::stable_vector<T, Allocator> >
2096{
2097 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
2098 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
2099 ::boost::has_trivial_destructor_after_move<pointer>::value;
2100};
2101
2102namespace container {
2103
2104#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2105
2106}} //namespace boost{ namespace container {
2107
2108#include <boost/container/detail/config_end.hpp>
2109
2110#endif //BOOST_CONTAINER_STABLE_VECTOR_HPP
2111

source code of boost/boost/container/stable_vector.hpp