1 //////////////////////////////////////////////////////////////////////////////
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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
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)
17 //////////////////////////////////////////////////////////////////////////////
19 #ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP
20 #define BOOST_CONTAINER_STABLE_VECTOR_HPP
22 #ifndef BOOST_CONFIG_HPP
23 # include <boost/config.hpp>
26 #if defined(BOOST_HAS_PRAGMA_ONCE)
30 #include <boost/container/detail/config_begin.hpp>
31 #include <boost/container/detail/workaround.hpp>
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>
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/move/detail/to_raw_pointer.hpp>
48 #include <boost/container/detail/type_traits.hpp>
50 #include <boost/intrusive/pointer_traits.hpp>
52 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
54 #include <boost/move/utility_core.hpp>
55 #include <boost/move/iterator.hpp>
56 #include <boost/move/adl_move_swap.hpp>
58 #include <boost/move/detail/move_helpers.hpp>
60 #include <boost/assert.hpp>
61 #include <boost/core/no_exceptions_support.hpp>
63 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
64 #include <initializer_list>
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
75 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
77 namespace stable_vector_detail{
80 class clear_on_destroy
83 BOOST_CONTAINER_FORCEINLINE clear_on_destroy(C &c)
84 : c_(c), do_clear_(true)
87 BOOST_CONTAINER_FORCEINLINE void release()
88 { do_clear_ = false; }
90 BOOST_CONTAINER_FORCEINLINE ~clear_on_destroy()
99 clear_on_destroy(const clear_on_destroy &);
100 clear_on_destroy &operator=(const clear_on_destroy &);
105 template<typename Pointer>
108 template<class VoidPtr>
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;
119 typedef typename void_ptr_traits::
120 template rebind_pointer
121 <node_base_ptr>::type node_base_ptr_ptr;
124 BOOST_CONTAINER_FORCEINLINE explicit node_base(const node_base_ptr_ptr &n)
128 BOOST_CONTAINER_FORCEINLINE node_base()
132 node_base_ptr_ptr up;
136 template<typename Pointer>
139 <typename ::boost::intrusive::pointer_traits<Pointer>::template
140 rebind_pointer<void>::type
144 typedef typename ::boost::intrusive::pointer_traits<Pointer>::element_type T;
146 <typename ::boost::intrusive::pointer_traits<Pointer>::template
147 rebind_pointer<void>::type
150 typedef typename boost::container::dtl::aligned_storage
151 <sizeof(T), boost::container::dtl::alignment_of<T>::value>::type storage_t;
154 BOOST_CONTAINER_FORCEINLINE explicit node(const typename hook_type::node_base_ptr_ptr &n)
158 BOOST_CONTAINER_FORCEINLINE node()
161 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000)
162 #pragma GCC diagnostic push
163 #pragma GCC diagnostic ignored "-Wstrict-aliasing"
164 #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING
167 BOOST_CONTAINER_FORCEINLINE T &get_data()
168 { return *reinterpret_cast<T*>(this->m_storage.data); }
170 BOOST_CONTAINER_FORCEINLINE const T &get_data() const
171 { return *reinterpret_cast<const T*>(this->m_storage.data); }
173 BOOST_CONTAINER_FORCEINLINE T *get_data_ptr()
174 { return reinterpret_cast<T*>(this->m_storage.data); }
176 BOOST_CONTAINER_FORCEINLINE const T *get_data_ptr() const
177 { return reinterpret_cast<T*>(this->m_storage.data); }
179 BOOST_CONTAINER_FORCEINLINE ~node()
180 { reinterpret_cast<T*>(this->m_storage.data)->~T(); }
182 #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING)
183 #pragma GCC diagnostic pop
184 #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING
187 BOOST_CONTAINER_FORCEINLINE void destroy_header()
188 { static_cast<hook_type*>(this)->~hook_type(); }
191 template<class VoidPtr, class VoidAllocator>
194 typedef boost::intrusive::
196 <VoidPtr> void_ptr_traits;
197 typedef stable_vector_detail::
198 node_base<VoidPtr> node_base_type;
199 typedef typename void_ptr_traits::template
200 rebind_pointer<node_base_type>::type node_base_ptr;
201 typedef typename void_ptr_traits::template
202 rebind_pointer<node_base_ptr>::type node_base_ptr_ptr;
203 typedef boost::intrusive::
204 pointer_traits<node_base_ptr> node_base_ptr_traits;
205 typedef boost::intrusive::
206 pointer_traits<node_base_ptr_ptr> node_base_ptr_ptr_traits;
207 typedef typename allocator_traits<VoidAllocator>::
208 template portable_rebind_alloc
209 <node_base_ptr>::type node_base_ptr_allocator;
210 typedef ::boost::container::vector
211 <node_base_ptr, node_base_ptr_allocator> index_type;
212 typedef typename index_type::iterator index_iterator;
213 typedef typename index_type::const_iterator const_index_iterator;
214 typedef typename index_type::size_type size_type;
216 static const size_type ExtraPointers = 3;
217 //Stable vector stores metadata at the end of the index (node_base_ptr vector) with additional 3 pointers:
218 // back() is this->index.back() - ExtraPointers;
219 // end node index is *(this->index.end() - 3)
220 // Node cache first is *(this->index.end() - 2);
221 // Node cache last is this->index.back();
223 BOOST_CONTAINER_FORCEINLINE static node_base_ptr_ptr ptr_to_node_base_ptr(node_base_ptr &n)
224 { return node_base_ptr_ptr_traits::pointer_to(n); }
226 static void fix_up_pointers(index_iterator first, index_iterator last)
228 while(first != last){
229 typedef typename index_type::reference node_base_ptr_ref;
230 node_base_ptr_ref nbp = *first;
231 nbp->up = index_traits::ptr_to_node_base_ptr(nbp);
236 BOOST_CONTAINER_FORCEINLINE static index_iterator get_fix_up_end(index_type &index)
237 { return index.end() - (ExtraPointers - 1); }
239 BOOST_CONTAINER_FORCEINLINE static void fix_up_pointers_from(index_type & index, index_iterator first)
240 { index_traits::fix_up_pointers(first, index_traits::get_fix_up_end(index)); }
242 static void readjust_end_node(index_type &index, node_base_type &end_node)
245 index_iterator end_node_it(index_traits::get_fix_up_end(index));
246 node_base_ptr &end_node_idx_ref = *(--end_node_it);
247 end_node_idx_ref = node_base_ptr_traits::pointer_to(end_node);
248 end_node.up = node_base_ptr_ptr_traits::pointer_to(end_node_idx_ref);
251 end_node.up = node_base_ptr_ptr();
255 static void initialize_end_node(index_type &index, node_base_type &end_node, const size_type index_capacity_if_empty)
258 index.reserve(index_capacity_if_empty + ExtraPointers);
259 index.resize(ExtraPointers);
260 node_base_ptr &end_node_ref = *index.data();
261 end_node_ref = node_base_ptr_traits::pointer_to(end_node);
262 end_node.up = index_traits::ptr_to_node_base_ptr(end_node_ref);
266 #ifdef STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
267 static bool invariants(index_type &index)
269 for( index_iterator it = index.begin()
270 , it_end = index_traits::get_fix_up_end(index)
273 if((*it)->up != index_traits::ptr_to_node_base_ptr(*it)){
279 #endif //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
282 } //namespace stable_vector_detail
284 template<typename Pointer, bool IsConst>
285 class stable_vector_iterator
287 typedef boost::intrusive::pointer_traits<Pointer> non_const_ptr_traits;
289 typedef std::random_access_iterator_tag iterator_category;
290 typedef typename non_const_ptr_traits::element_type value_type;
291 typedef typename non_const_ptr_traits::difference_type difference_type;
292 typedef typename ::boost::container::dtl::if_c
294 , typename non_const_ptr_traits::template
295 rebind_pointer<const value_type>::type
298 typedef boost::intrusive::pointer_traits<pointer> ptr_traits;
299 typedef typename ptr_traits::reference reference;
301 typedef typename non_const_ptr_traits::template
302 rebind_pointer<void>::type void_ptr;
303 typedef stable_vector_detail::node<Pointer> node_type;
304 typedef stable_vector_detail::node_base<void_ptr> node_base_type;
305 typedef typename non_const_ptr_traits::template
306 rebind_pointer<node_type>::type node_ptr;
307 typedef boost::intrusive::
308 pointer_traits<node_ptr> node_ptr_traits;
309 typedef typename non_const_ptr_traits::template
310 rebind_pointer<node_base_type>::type node_base_ptr;
311 typedef typename non_const_ptr_traits::template
312 rebind_pointer<node_base_ptr>::type node_base_ptr_ptr;
317 node_base_ptr node_pointer() const
318 { return node_base_ptr(); }
320 typedef typename dtl::if_c< IsConst
321 , stable_vector_iterator<Pointer, false>
322 , nat>::type nonconst_iterator;
328 BOOST_CONTAINER_FORCEINLINE explicit stable_vector_iterator(node_base_ptr p) BOOST_NOEXCEPT_OR_NOTHROW
332 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator() BOOST_NOEXCEPT_OR_NOTHROW
333 : m_pn() //Value initialization to achieve "null iterators" (N3644)
336 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator(const stable_vector_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
337 : m_pn(other.node_pointer())
340 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator(const nonconst_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
341 : m_pn(other.node_pointer())
344 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator & operator=(const stable_vector_iterator& other) BOOST_NOEXCEPT_OR_NOTHROW
345 { m_pn = other.node_pointer(); return *this; }
347 BOOST_CONTAINER_FORCEINLINE node_ptr node_pointer() const BOOST_NOEXCEPT_OR_NOTHROW
348 { return node_ptr_traits::static_cast_from(m_pn); }
351 //Pointer like operators
352 BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW
353 { return node_pointer()->get_data(); }
355 BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
356 { return ptr_traits::pointer_to(this->operator*()); }
358 //Increment / Decrement
359 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
361 node_base_ptr_ptr p(this->m_pn->up);
366 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
367 { stable_vector_iterator tmp(*this); ++*this; return stable_vector_iterator(tmp); }
369 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
371 node_base_ptr_ptr p(this->m_pn->up);
376 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
377 { stable_vector_iterator tmp(*this); --*this; return stable_vector_iterator(tmp); }
379 BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW
380 { return node_ptr_traits::static_cast_from(this->m_pn->up[off])->get_data(); }
382 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
384 if(off) this->m_pn = this->m_pn->up[off];
388 BOOST_CONTAINER_FORCEINLINE friend stable_vector_iterator operator+(const stable_vector_iterator &left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
390 stable_vector_iterator tmp(left);
395 BOOST_CONTAINER_FORCEINLINE friend stable_vector_iterator operator+(difference_type off, const stable_vector_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW
397 stable_vector_iterator tmp(right);
402 BOOST_CONTAINER_FORCEINLINE stable_vector_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
403 { *this += -off; return *this; }
405 BOOST_CONTAINER_FORCEINLINE friend stable_vector_iterator operator-(const stable_vector_iterator &left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
407 stable_vector_iterator tmp(left);
412 BOOST_CONTAINER_FORCEINLINE friend difference_type operator-(const stable_vector_iterator &left, const stable_vector_iterator &right) BOOST_NOEXCEPT_OR_NOTHROW
413 { return left.m_pn->up - right.m_pn->up; }
415 //Comparison operators
416 BOOST_CONTAINER_FORCEINLINE friend bool operator== (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
417 { return l.m_pn == r.m_pn; }
419 BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
420 { return l.m_pn != r.m_pn; }
422 BOOST_CONTAINER_FORCEINLINE friend bool operator< (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
423 { return l.m_pn->up < r.m_pn->up; }
425 BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
426 { return l.m_pn->up <= r.m_pn->up; }
428 BOOST_CONTAINER_FORCEINLINE friend bool operator> (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
429 { return l.m_pn->up > r.m_pn->up; }
431 BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const stable_vector_iterator& l, const stable_vector_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
432 { return l.m_pn->up >= r.m_pn->up; }
435 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
437 #define STABLE_VECTOR_CHECK_INVARIANT \
438 invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \
439 BOOST_JOIN(check_invariant_,__LINE__).touch();
441 #else //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
443 #define STABLE_VECTOR_CHECK_INVARIANT
445 #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
447 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
449 //! Originally developed by Joaquin M. Lopez Munoz, stable_vector is a std::vector
450 //! drop-in replacement implemented as a node container, offering iterator and reference
453 //! Here are the details taken from the author's blog
454 //! (<a href="http://bannalia.blogspot.com/2008/09/introducing-stablevector.html" >
455 //! Introducing stable_vector</a>):
457 //! We present stable_vector, a fully STL-compliant stable container that provides
458 //! most of the features of std::vector except element contiguity.
460 //! General properties: stable_vector satisfies all the requirements of a container,
461 //! a reversible container and a sequence and provides all the optional operations
462 //! present in std::vector. Like std::vector, iterators are random access.
463 //! stable_vector does not provide element contiguity; in exchange for this absence,
464 //! the container is stable, i.e. references and iterators to an element of a stable_vector
465 //! remain valid as long as the element is not erased, and an iterator that has been
466 //! assigned the return value of end() always remain valid until the destruction of
467 //! the associated stable_vector.
469 //! Operation complexity: The big-O complexities of stable_vector operations match
470 //! exactly those of std::vector. In general, insertion/deletion is constant time at
471 //! the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector
472 //! does not internally perform any value_type destruction, copy or assignment
473 //! operations other than those exactly corresponding to the insertion of new
474 //! elements or deletion of stored elements, which can sometimes compensate in terms
475 //! of performance for the extra burden of doing more pointer manipulation and an
476 //! additional allocation per element.
478 //! Exception safety: As stable_vector does not internally copy elements around, some
479 //! operations provide stronger exception safety guarantees than in std::vector.
481 //! \tparam T The type of object that is stored in the stable_vector
482 //! \tparam Allocator The allocator used for all internal memory management
483 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
484 template <class T, class Allocator = void >
486 template <class T, class Allocator>
490 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
491 typedef typename real_allocator<T, Allocator>::type ValueAllocator;
492 typedef allocator_traits<ValueAllocator> allocator_traits_type;
493 typedef boost::intrusive::
495 <typename allocator_traits_type::pointer> ptr_traits;
496 typedef typename ptr_traits::
497 template rebind_pointer<void>::type void_ptr;
498 typedef typename allocator_traits_type::
499 template portable_rebind_alloc
500 <void>::type void_allocator_type;
501 typedef stable_vector_detail::index_traits
502 <void_ptr, void_allocator_type> index_traits_type;
503 typedef typename index_traits_type::node_base_type node_base_type;
504 typedef typename index_traits_type::node_base_ptr node_base_ptr;
505 typedef typename index_traits_type::
506 node_base_ptr_ptr node_base_ptr_ptr;
507 typedef typename index_traits_type::
508 node_base_ptr_traits node_base_ptr_traits;
509 typedef typename index_traits_type::
510 node_base_ptr_ptr_traits node_base_ptr_ptr_traits;
511 typedef typename index_traits_type::index_type index_type;
512 typedef typename index_traits_type::index_iterator index_iterator;
513 typedef typename index_traits_type::
514 const_index_iterator const_index_iterator;
515 typedef stable_vector_detail::node
516 <typename ptr_traits::pointer> node_type;
517 typedef typename ptr_traits::template
518 rebind_pointer<node_type>::type node_ptr;
519 typedef boost::intrusive::
520 pointer_traits<node_ptr> node_ptr_traits;
521 typedef typename ptr_traits::template
522 rebind_pointer<const node_type>::type const_node_ptr;
523 typedef boost::intrusive::
524 pointer_traits<const_node_ptr> const_node_ptr_traits;
525 typedef typename node_ptr_traits::reference node_reference;
526 typedef typename const_node_ptr_traits::reference const_node_reference;
528 typedef ::boost::container::dtl::integral_constant
529 <unsigned, boost::container::dtl::
530 version<ValueAllocator>::value> alloc_version;
531 typedef typename allocator_traits_type::
532 template portable_rebind_alloc
533 <node_type>::type node_allocator_type;
535 typedef ::boost::container::dtl::
536 allocator_version_traits<node_allocator_type> allocator_version_traits_t;
537 typedef typename allocator_version_traits_t::multiallocation_chain multiallocation_chain;
539 BOOST_CONTAINER_FORCEINLINE node_ptr allocate_one()
540 { return allocator_version_traits_t::allocate_one(this->priv_node_alloc()); }
542 BOOST_CONTAINER_FORCEINLINE void deallocate_one(const node_ptr &p)
543 { allocator_version_traits_t::deallocate_one(this->priv_node_alloc(), p); }
545 BOOST_CONTAINER_FORCEINLINE void allocate_individual(typename allocator_traits_type::size_type n, multiallocation_chain &m)
546 { allocator_version_traits_t::allocate_individual(this->priv_node_alloc(), n, m); }
548 BOOST_CONTAINER_FORCEINLINE void deallocate_individual(multiallocation_chain &holder)
549 { allocator_version_traits_t::deallocate_individual(this->priv_node_alloc(), holder); }
551 friend class stable_vector_detail::clear_on_destroy<stable_vector>;
552 typedef stable_vector_iterator
553 < typename allocator_traits<ValueAllocator>::pointer
554 , false> iterator_impl;
555 typedef stable_vector_iterator
556 < typename allocator_traits<ValueAllocator>::pointer
557 , true> const_iterator_impl;
558 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
561 //////////////////////////////////////////////
565 //////////////////////////////////////////////
566 typedef T value_type;
567 typedef typename ::boost::container::allocator_traits<ValueAllocator>::pointer pointer;
568 typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_pointer const_pointer;
569 typedef typename ::boost::container::allocator_traits<ValueAllocator>::reference reference;
570 typedef typename ::boost::container::allocator_traits<ValueAllocator>::const_reference const_reference;
571 typedef typename ::boost::container::allocator_traits<ValueAllocator>::size_type size_type;
572 typedef typename ::boost::container::allocator_traits<ValueAllocator>::difference_type difference_type;
573 typedef ValueAllocator allocator_type;
574 typedef node_allocator_type stored_allocator_type;
575 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
576 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
577 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
578 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
580 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
582 BOOST_COPYABLE_AND_MOVABLE(stable_vector)
583 static const size_type ExtraPointers = index_traits_type::ExtraPointers;
585 class insert_rollback;
586 friend class insert_rollback;
588 class push_back_rollback;
589 friend class push_back_rollback;
590 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
593 //////////////////////////////////////////////
595 // construct/copy/destroy
597 //////////////////////////////////////////////
599 //! <b>Effects</b>: Default constructs a stable_vector.
601 //! <b>Throws</b>: If allocator_type's default constructor throws.
603 //! <b>Complexity</b>: Constant.
604 BOOST_CONTAINER_FORCEINLINE stable_vector() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<ValueAllocator>::value)
605 : internal_data(), index()
607 STABLE_VECTOR_CHECK_INVARIANT;
610 //! <b>Effects</b>: Constructs a stable_vector taking the allocator as parameter.
612 //! <b>Throws</b>: Nothing
614 //! <b>Complexity</b>: Constant.
615 BOOST_CONTAINER_FORCEINLINE explicit stable_vector(const allocator_type& al) BOOST_NOEXCEPT_OR_NOTHROW
616 : internal_data(al), index(al)
618 STABLE_VECTOR_CHECK_INVARIANT;
621 //! <b>Effects</b>: Constructs a stable_vector
622 //! and inserts n value initialized values.
624 //! <b>Throws</b>: If allocator_type's default constructor
625 //! throws or T's default or copy constructor throws.
627 //! <b>Complexity</b>: Linear to n.
628 explicit stable_vector(size_type n)
629 : internal_data(), index()
631 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
633 STABLE_VECTOR_CHECK_INVARIANT;
637 //! <b>Effects</b>: Constructs a stable_vector
638 //! and inserts n default initialized values.
640 //! <b>Throws</b>: If allocator_type's default constructor
641 //! throws or T's default or copy constructor throws.
643 //! <b>Complexity</b>: Linear to n.
645 //! <b>Note</b>: Non-standard extension
646 stable_vector(size_type n, default_init_t)
647 : internal_data(), index()
649 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
650 this->resize(n, default_init);
651 STABLE_VECTOR_CHECK_INVARIANT;
655 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
656 //! and inserts n value initialized values.
658 //! <b>Throws</b>: If allocator_type's default constructor
659 //! throws or T's default or copy constructor throws.
661 //! <b>Complexity</b>: Linear to n.
662 explicit stable_vector(size_type n, const allocator_type &a)
663 : internal_data(), index(a)
665 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
667 STABLE_VECTOR_CHECK_INVARIANT;
671 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
672 //! and inserts n default initialized values.
674 //! <b>Throws</b>: If allocator_type's default constructor
675 //! throws or T's default or copy constructor throws.
677 //! <b>Complexity</b>: Linear to n.
679 //! <b>Note</b>: Non-standard extension
680 stable_vector(size_type n, default_init_t, const allocator_type &a)
681 : internal_data(), index(a)
683 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
684 this->resize(n, default_init);
685 STABLE_VECTOR_CHECK_INVARIANT;
689 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
690 //! and inserts n copies of value.
692 //! <b>Throws</b>: If allocator_type's default constructor
693 //! throws or T's default or copy constructor throws.
695 //! <b>Complexity</b>: Linear to n.
696 stable_vector(size_type n, const T& t, const allocator_type& al = allocator_type())
697 : internal_data(al), index(al)
699 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
700 this->insert(this->cend(), n, t);
701 STABLE_VECTOR_CHECK_INVARIANT;
705 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
706 //! and inserts a copy of the range [first, last) in the stable_vector.
708 //! <b>Throws</b>: If allocator_type's default constructor
709 //! throws or T's constructor taking a dereferenced InIt throws.
711 //! <b>Complexity</b>: Linear to the range [first, last).
712 template <class InputIterator>
713 stable_vector(InputIterator first,InputIterator last, const allocator_type& al = allocator_type())
714 : internal_data(al), index(al)
716 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
717 this->insert(this->cend(), first, last);
718 STABLE_VECTOR_CHECK_INVARIANT;
722 //! <b>Effects</b>: Copy constructs a stable_vector.
724 //! <b>Postcondition</b>: x == *this.
726 //! <b>Complexity</b>: Linear to the elements x contains.
727 stable_vector(const stable_vector& x)
728 : internal_data(allocator_traits<node_allocator_type>::
729 select_on_container_copy_construction(x.priv_node_alloc()))
730 , index(allocator_traits<allocator_type>::
731 select_on_container_copy_construction(x.index.get_stored_allocator()))
733 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
734 this->insert(this->cend(), x.begin(), x.end());
735 STABLE_VECTOR_CHECK_INVARIANT;
739 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
740 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
741 //! and inserts a copy of the range [il.begin(), il.last()) in the stable_vector
743 //! <b>Throws</b>: If allocator_type's default constructor
744 //! throws or T's constructor taking a dereferenced initializer_list iterator throws.
746 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
747 stable_vector(std::initializer_list<value_type> il, const allocator_type& l = allocator_type())
748 : internal_data(l), index(l)
750 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
751 insert(cend(), il.begin(), il.end());
752 STABLE_VECTOR_CHECK_INVARIANT;
757 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
759 //! <b>Throws</b>: If allocator_type's copy constructor throws.
761 //! <b>Complexity</b>: Constant.
762 BOOST_CONTAINER_FORCEINLINE stable_vector(BOOST_RV_REF(stable_vector) x) BOOST_NOEXCEPT_OR_NOTHROW
763 : internal_data(boost::move(x.priv_node_alloc())), index(boost::move(x.index))
765 this->priv_swap_members(x);
768 //! <b>Effects</b>: Copy constructs a stable_vector using the specified allocator.
770 //! <b>Postcondition</b>: x == *this.
772 //! <b>Complexity</b>: Linear to the elements x contains.
773 stable_vector(const stable_vector& x, const allocator_type &a)
774 : internal_data(a), index(a)
776 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
777 this->insert(this->cend(), x.begin(), x.end());
778 STABLE_VECTOR_CHECK_INVARIANT;
782 //! <b>Effects</b>: Move constructor using the specified allocator.
783 //! Moves x's resources to *this.
785 //! <b>Throws</b>: If allocator_type's copy constructor throws.
787 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
788 stable_vector(BOOST_RV_REF(stable_vector) x, const allocator_type &a)
789 : internal_data(a), index(a)
791 if(this->priv_node_alloc() == x.priv_node_alloc()){
792 this->index.swap(x.index);
793 this->priv_swap_members(x);
796 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
797 this->insert(this->cend(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end()));
798 STABLE_VECTOR_CHECK_INVARIANT;
803 //! <b>Effects</b>: Destroys the stable_vector. All stored values are destroyed
804 //! and used memory is deallocated.
806 //! <b>Throws</b>: Nothing.
808 //! <b>Complexity</b>: Linear to the number of elements.
812 this->priv_clear_pool();
815 //! <b>Effects</b>: Makes *this contain the same elements as x.
817 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
818 //! of each of x's elements.
820 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
822 //! <b>Complexity</b>: Linear to the number of elements in x.
823 stable_vector& operator=(BOOST_COPY_ASSIGN_REF(stable_vector) x)
825 STABLE_VECTOR_CHECK_INVARIANT;
826 if (BOOST_LIKELY(this != &x)) {
827 node_allocator_type &this_alloc = this->priv_node_alloc();
828 const node_allocator_type &x_alloc = x.priv_node_alloc();
829 dtl::bool_<allocator_traits_type::
830 propagate_on_container_copy_assignment::value> flag;
831 if(flag && this_alloc != x_alloc){
833 this->shrink_to_fit();
835 dtl::assign_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
836 dtl::assign_alloc(this->index.get_stored_allocator(), x.index.get_stored_allocator(), flag);
837 this->assign(x.begin(), x.end());
842 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
844 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
845 //! before the function.
847 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
848 //! is false and (allocation throws or T's move constructor throws)
850 //! <b>Complexity</b>: Constant if allocator_traits_type::
851 //! propagate_on_container_move_assignment is true or
852 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
853 stable_vector& operator=(BOOST_RV_REF(stable_vector) x)
854 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
855 || allocator_traits_type::is_always_equal::value)
857 //for move constructor, no aliasing (&x != this) is assumed.
858 if (BOOST_LIKELY(this != &x)) {
859 node_allocator_type &this_alloc = this->priv_node_alloc();
860 node_allocator_type &x_alloc = x.priv_node_alloc();
861 const bool propagate_alloc = allocator_traits_type::
862 propagate_on_container_move_assignment::value;
863 dtl::bool_<propagate_alloc> flag;
864 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
865 //Resources can be transferred if both allocators are
866 //going to be equal after this function (either propagated or already equal)
867 if(propagate_alloc || allocators_equal){
868 STABLE_VECTOR_CHECK_INVARIANT
869 //Destroy objects but retain memory in case x reuses it in the future
871 //Move allocator if needed
872 dtl::move_alloc(this_alloc, x_alloc, flag);
874 this->index.swap(x.index);
875 this->priv_swap_members(x);
877 //Else do a one by one move
879 this->assign( boost::make_move_iterator(x.begin())
880 , boost::make_move_iterator(x.end()));
886 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
887 //! <b>Effects</b>: Make *this container contains elements from il.
889 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
890 stable_vector& operator=(std::initializer_list<value_type> il)
892 STABLE_VECTOR_CHECK_INVARIANT;
893 assign(il.begin(), il.end());
898 //! <b>Effects</b>: Assigns the n copies of val to *this.
900 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
902 //! <b>Complexity</b>: Linear to n.
903 BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const T& t)
905 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
906 this->assign(cvalue_iterator(t, n), cvalue_iterator());
909 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
911 //! <b>Throws</b>: If memory allocation throws or
912 //! T's constructor from dereferencing InpIt throws.
914 //! <b>Complexity</b>: Linear to n.
915 template<typename InputIterator>
916 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
917 typename dtl::disable_if_convertible<InputIterator, size_type>::type
921 assign(InputIterator first,InputIterator last)
923 STABLE_VECTOR_CHECK_INVARIANT;
924 iterator first1 = this->begin();
925 iterator last1 = this->end();
926 for ( ; first1 != last1 && first != last; ++first1, ++first)
929 this->erase(first1, last1);
932 this->insert(last1, first, last);
936 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
937 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
939 //! <b>Throws</b>: If memory allocation throws or
940 //! T's constructor from dereferencing initializer_list iterator throws.
942 BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<value_type> il)
944 STABLE_VECTOR_CHECK_INVARIANT;
945 assign(il.begin(), il.end());
949 //! <b>Effects</b>: Returns a copy of the internal allocator.
951 //! <b>Throws</b>: If allocator's copy constructor throws.
953 //! <b>Complexity</b>: Constant.
954 BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const
955 { return this->priv_node_alloc(); }
957 //! <b>Effects</b>: Returns a reference to the internal allocator.
959 //! <b>Throws</b>: Nothing
961 //! <b>Complexity</b>: Constant.
963 //! <b>Note</b>: Non-standard extension.
964 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
965 { return this->priv_node_alloc(); }
967 //! <b>Effects</b>: Returns a reference to the internal allocator.
969 //! <b>Throws</b>: Nothing
971 //! <b>Complexity</b>: Constant.
973 //! <b>Note</b>: Non-standard extension.
974 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
975 { return this->priv_node_alloc(); }
977 //////////////////////////////////////////////
981 //////////////////////////////////////////////
983 //! <b>Effects</b>: Returns an iterator to the first element contained in the stable_vector.
985 //! <b>Throws</b>: Nothing.
987 //! <b>Complexity</b>: Constant.
988 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
989 { return (this->index.empty()) ? this->end(): iterator(node_ptr_traits::static_cast_from(this->index.front())); }
991 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
993 //! <b>Throws</b>: Nothing.
995 //! <b>Complexity</b>: Constant.
996 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
997 { return (this->index.empty()) ? this->cend() : const_iterator(node_ptr_traits::static_cast_from(this->index.front())) ; }
999 //! <b>Effects</b>: Returns an iterator to the end of the stable_vector.
1001 //! <b>Throws</b>: Nothing.
1003 //! <b>Complexity</b>: Constant.
1004 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW
1005 { return iterator(this->priv_get_end_node()); }
1007 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
1009 //! <b>Throws</b>: Nothing.
1011 //! <b>Complexity</b>: Constant.
1012 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
1013 { return const_iterator(this->priv_get_end_node()); }
1015 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1016 //! of the reversed stable_vector.
1018 //! <b>Throws</b>: Nothing.
1020 //! <b>Complexity</b>: Constant.
1021 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
1022 { return reverse_iterator(this->end()); }
1024 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1025 //! of the reversed stable_vector.
1027 //! <b>Throws</b>: Nothing.
1029 //! <b>Complexity</b>: Constant.
1030 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1031 { return const_reverse_iterator(this->end()); }
1033 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1034 //! of the reversed stable_vector.
1036 //! <b>Throws</b>: Nothing.
1038 //! <b>Complexity</b>: Constant.
1039 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1040 { return reverse_iterator(this->begin()); }
1042 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1043 //! of the reversed stable_vector.
1045 //! <b>Throws</b>: Nothing.
1047 //! <b>Complexity</b>: Constant.
1048 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1049 { return const_reverse_iterator(this->begin()); }
1051 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
1053 //! <b>Throws</b>: Nothing.
1055 //! <b>Complexity</b>: Constant.
1056 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1057 { return this->begin(); }
1059 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
1061 //! <b>Throws</b>: Nothing.
1063 //! <b>Complexity</b>: Constant.
1064 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1065 { return this->end(); }
1067 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1068 //! of the reversed stable_vector.
1070 //! <b>Throws</b>: Nothing.
1072 //! <b>Complexity</b>: Constant.
1073 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1074 { return this->rbegin(); }
1076 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1077 //! of the reversed stable_vector.
1079 //! <b>Throws</b>: Nothing.
1081 //! <b>Complexity</b>: Constant.
1082 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend()const BOOST_NOEXCEPT_OR_NOTHROW
1083 { return this->rend(); }
1085 //////////////////////////////////////////////
1089 //////////////////////////////////////////////
1091 //! <b>Effects</b>: Returns true if the stable_vector contains no elements.
1093 //! <b>Throws</b>: Nothing.
1095 //! <b>Complexity</b>: Constant.
1096 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1097 { return this->index.size() <= ExtraPointers; }
1099 //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector.
1101 //! <b>Throws</b>: Nothing.
1103 //! <b>Complexity</b>: Constant.
1104 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1106 const size_type index_size = this->index.size();
1107 return (index_size - ExtraPointers) & (size_type(0u) -size_type(index_size != 0));
1110 //! <b>Effects</b>: Returns the largest possible size of the stable_vector.
1112 //! <b>Throws</b>: Nothing.
1114 //! <b>Complexity</b>: Constant.
1115 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1116 { return this->index.max_size() - ExtraPointers; }
1118 //! <b>Effects</b>: Inserts or erases elements at the end such that
1119 //! the size becomes n. New elements are value initialized.
1121 //! <b>Throws</b>: If memory allocation throws, or T's value initialization throws.
1123 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1124 void resize(size_type n)
1126 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
1127 STABLE_VECTOR_CHECK_INVARIANT;
1128 if(n > this->size())
1129 this->insert(this->cend(), value_init_iterator(n - this->size()), value_init_iterator());
1130 else if(n < this->size())
1131 this->erase(this->cbegin() + n, this->cend());
1134 //! <b>Effects</b>: Inserts or erases elements at the end such that
1135 //! the size becomes n. New elements are default initialized.
1137 //! <b>Throws</b>: If memory allocation throws, or T's default initialization throws.
1139 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1141 //! <b>Note</b>: Non-standard extension
1142 void resize(size_type n, default_init_t)
1144 typedef default_init_construct_iterator<value_type, difference_type> default_init_iterator;
1145 STABLE_VECTOR_CHECK_INVARIANT;
1146 if(n > this->size())
1147 this->insert(this->cend(), default_init_iterator(n - this->size()), default_init_iterator());
1148 else if(n < this->size())
1149 this->erase(this->cbegin() + n, this->cend());
1152 //! <b>Effects</b>: Inserts or erases elements at the end such that
1153 //! the size becomes n. New elements are copy constructed from x.
1155 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1157 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1158 void resize(size_type n, const T& t)
1160 STABLE_VECTOR_CHECK_INVARIANT;
1161 if(n > this->size())
1162 this->insert(this->cend(), n - this->size(), t);
1163 else if(n < this->size())
1164 this->erase(this->cbegin() + n, this->cend());
1167 //! <b>Effects</b>: Number of elements for which memory has been allocated.
1168 //! capacity() is always greater than or equal to size().
1170 //! <b>Throws</b>: Nothing.
1172 //! <b>Complexity</b>: Constant.
1173 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
1175 const size_type index_size = this->index.size();
1176 BOOST_ASSERT(!index_size || index_size >= ExtraPointers);
1177 const size_type node_extra_capacity = this->internal_data.pool_size;
1178 //Pool count must be less than index capacity, as index is a vector
1179 BOOST_ASSERT(node_extra_capacity <= (this->index.capacity()- index_size));
1180 const size_type index_offset =
1181 (node_extra_capacity - ExtraPointers) & (size_type(0u) - size_type(index_size != 0));
1182 return index_size + index_offset;
1185 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
1186 //! effect. Otherwise, it is a request for allocation of additional memory.
1187 //! If the request is successful, then capacity() is greater than or equal to
1188 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
1190 //! <b>Throws</b>: If memory allocation allocation throws.
1191 void reserve(size_type n)
1193 STABLE_VECTOR_CHECK_INVARIANT;
1194 if(n > this->max_size()){
1195 throw_length_error("stable_vector::reserve max_size() exceeded");
1198 size_type sz = this->size();
1199 size_type old_capacity = this->capacity();
1200 if(n > old_capacity){
1201 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, n);
1202 const void * old_ptr = &index[0];
1203 this->index.reserve(n + ExtraPointers);
1204 bool realloced = &index[0] != old_ptr;
1205 //Fix the pointers for the newly allocated buffer
1207 index_traits_type::fix_up_pointers_from(this->index, this->index.begin());
1209 //Now fill pool if data is not enough
1210 if((n - sz) > this->internal_data.pool_size){
1211 this->priv_increase_pool((n - sz) - this->internal_data.pool_size);
1216 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1217 //! with previous allocations. The size of the stable_vector is unchanged
1219 //! <b>Throws</b>: If memory allocation throws.
1221 //! <b>Complexity</b>: Linear to size().
1222 void shrink_to_fit()
1224 if(this->capacity()){
1225 //First empty allocated node pool
1226 this->priv_clear_pool();
1227 //If empty completely destroy the index, let's recover default-constructed state
1229 this->index.clear();
1230 this->index.shrink_to_fit();
1231 this->internal_data.end_node.up = node_base_ptr_ptr();
1233 //Otherwise, try to shrink-to-fit the index and readjust pointers if necessary
1235 const void* old_ptr = &index[0];
1236 this->index.shrink_to_fit();
1237 bool realloced = &index[0] != old_ptr;
1238 //Fix the pointers for the newly allocated buffer
1240 index_traits_type::fix_up_pointers_from(this->index, this->index.begin());
1246 //////////////////////////////////////////////
1250 //////////////////////////////////////////////
1252 //! <b>Requires</b>: !empty()
1254 //! <b>Effects</b>: Returns a reference to the first
1255 //! element of the container.
1257 //! <b>Throws</b>: Nothing.
1259 //! <b>Complexity</b>: Constant.
1260 BOOST_CONTAINER_FORCEINLINE reference front() BOOST_NOEXCEPT_OR_NOTHROW
1262 BOOST_ASSERT(!this->empty());
1263 return static_cast<node_reference>(*this->index.front()).get_data();
1266 //! <b>Requires</b>: !empty()
1268 //! <b>Effects</b>: Returns a const reference to the first
1269 //! element of the container.
1271 //! <b>Throws</b>: Nothing.
1273 //! <b>Complexity</b>: Constant.
1274 BOOST_CONTAINER_FORCEINLINE const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1276 BOOST_ASSERT(!this->empty());
1277 return static_cast<const_node_reference>(*this->index.front()).get_data();
1280 //! <b>Requires</b>: !empty()
1282 //! <b>Effects</b>: Returns a reference to the last
1283 //! element of the container.
1285 //! <b>Throws</b>: Nothing.
1287 //! <b>Complexity</b>: Constant.
1288 BOOST_CONTAINER_FORCEINLINE reference back() BOOST_NOEXCEPT_OR_NOTHROW
1290 BOOST_ASSERT(!this->empty());
1291 return static_cast<node_reference>(*this->index[this->size()-1u]).get_data();
1294 //! <b>Requires</b>: !empty()
1296 //! <b>Effects</b>: Returns a const reference to the last
1297 //! element of the container.
1299 //! <b>Throws</b>: Nothing.
1301 //! <b>Complexity</b>: Constant.
1302 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1304 BOOST_ASSERT(!this->empty());
1305 return static_cast<const_node_reference>(*this->index[this->size()-1u]).get_data();
1308 //! <b>Requires</b>: size() > n.
1310 //! <b>Effects</b>: Returns a reference to the nth element
1311 //! from the beginning of the container.
1313 //! <b>Throws</b>: Nothing.
1315 //! <b>Complexity</b>: Constant.
1316 BOOST_CONTAINER_FORCEINLINE reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1318 BOOST_ASSERT(this->size() > n);
1319 return static_cast<node_reference>(*this->index[n]).get_data();
1322 //! <b>Requires</b>: size() > n.
1324 //! <b>Effects</b>: Returns a const reference to the nth element
1325 //! from the beginning of the container.
1327 //! <b>Throws</b>: Nothing.
1329 //! <b>Complexity</b>: Constant.
1330 BOOST_CONTAINER_FORCEINLINE const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1332 BOOST_ASSERT(this->size() > n);
1333 return static_cast<const_node_reference>(*this->index[n]).get_data();
1336 //! <b>Requires</b>: size() >= n.
1338 //! <b>Effects</b>: Returns an iterator to the nth element
1339 //! from the beginning of the container. Returns end()
1342 //! <b>Throws</b>: Nothing.
1344 //! <b>Complexity</b>: Constant.
1346 //! <b>Note</b>: Non-standard extension
1347 BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1349 BOOST_ASSERT(this->size() >= n);
1350 return (this->index.empty()) ? this->end() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
1353 //! <b>Requires</b>: size() >= n.
1355 //! <b>Effects</b>: Returns a const_iterator to the nth element
1356 //! from the beginning of the container. Returns end()
1359 //! <b>Throws</b>: Nothing.
1361 //! <b>Complexity</b>: Constant.
1363 //! <b>Note</b>: Non-standard extension
1364 BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1366 BOOST_ASSERT(this->size() >= n);
1367 return (this->index.empty()) ? this->cend() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
1370 //! <b>Requires</b>: begin() <= p <= end().
1372 //! <b>Effects</b>: Returns the index of the element pointed by p
1373 //! and size() if p == end().
1375 //! <b>Throws</b>: Nothing.
1377 //! <b>Complexity</b>: Constant.
1379 //! <b>Note</b>: Non-standard extension
1380 BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1381 { return this->priv_index_of(p.node_pointer()); }
1383 //! <b>Requires</b>: begin() <= p <= end().
1385 //! <b>Effects</b>: Returns the index of the element pointed by p
1386 //! and size() if p == end().
1388 //! <b>Throws</b>: Nothing.
1390 //! <b>Complexity</b>: Constant.
1392 //! <b>Note</b>: Non-standard extension
1393 BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1394 { return this->priv_index_of(p.node_pointer()); }
1396 //! <b>Requires</b>: size() > n.
1398 //! <b>Effects</b>: Returns a reference to the nth element
1399 //! from the beginning of the container.
1401 //! <b>Throws</b>: std::range_error if n >= size()
1403 //! <b>Complexity</b>: Constant.
1404 reference at(size_type n)
1406 if(n >= this->size()){
1407 throw_out_of_range("vector::at invalid subscript");
1409 return operator[](n);
1412 //! <b>Requires</b>: size() > n.
1414 //! <b>Effects</b>: Returns a const reference to the nth element
1415 //! from the beginning of the container.
1417 //! <b>Throws</b>: std::range_error if n >= size()
1419 //! <b>Complexity</b>: Constant.
1420 const_reference at(size_type n)const
1422 if(n >= this->size()){
1423 throw_out_of_range("vector::at invalid subscript");
1425 return operator[](n);
1428 //////////////////////////////////////////////
1432 //////////////////////////////////////////////
1434 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1436 //! <b>Effects</b>: Inserts an object of type T constructed with
1437 //! std::forward<Args>(args)... in the end of the stable_vector.
1439 //! <b>Returns</b>: A reference to the created object.
1441 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1443 //! <b>Complexity</b>: Amortized constant time.
1444 template<class ...Args>
1445 reference emplace_back(Args &&...args)
1447 typedef emplace_functor<Args...> EmplaceFunctor;
1448 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
1449 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
1450 return *this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator());
1453 //! <b>Requires</b>: p must be a valid iterator of *this.
1455 //! <b>Effects</b>: Inserts an object of type T constructed with
1456 //! std::forward<Args>(args)... before p
1458 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1460 //! <b>Complexity</b>: If p is end(), amortized constant time
1461 //! Linear time otherwise.
1462 template<class ...Args>
1463 iterator emplace(const_iterator p, Args && ...args)
1465 BOOST_ASSERT(this->priv_in_range_or_end(p));
1466 size_type pos_n = p - cbegin();
1467 typedef emplace_functor<Args...> EmplaceFunctor;
1468 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
1469 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
1470 this->insert(p, EmplaceIterator(ef), EmplaceIterator());
1471 return iterator(this->begin() + pos_n);
1476 #define BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE(N) \
1477 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1478 reference emplace_back(BOOST_MOVE_UREF##N)\
1480 typedef emplace_functor##N\
1481 BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
1482 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;\
1483 EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
1484 return *this->insert(this->cend() , EmplaceIterator(ef), EmplaceIterator());\
1487 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1488 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1490 BOOST_ASSERT(this->priv_in_range_or_end(p));\
1491 typedef emplace_functor##N\
1492 BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
1493 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;\
1494 EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
1495 const size_type pos_n = p - this->cbegin();\
1496 this->insert(p, EmplaceIterator(ef), EmplaceIterator());\
1497 return this->begin() += pos_n;\
1500 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE)
1501 #undef BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE
1503 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1505 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1506 //! <b>Effects</b>: Inserts a copy of x at the end of the stable_vector.
1508 //! <b>Throws</b>: If memory allocation throws or
1509 //! T's copy constructor throws.
1511 //! <b>Complexity</b>: Amortized constant time.
1512 void push_back(const T &x);
1514 //! <b>Effects</b>: Constructs a new element in the end of the stable_vector
1515 //! and moves the resources of x to this new element.
1517 //! <b>Throws</b>: If memory allocation throws.
1519 //! <b>Complexity</b>: Amortized constant time.
1520 void push_back(T &&x);
1522 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1525 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1526 //! <b>Requires</b>: p must be a valid iterator of *this.
1528 //! <b>Effects</b>: Insert a copy of x before p.
1530 //! <b>Returns</b>: An iterator to the inserted element.
1532 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1534 //! <b>Complexity</b>: If p is end(), amortized constant time
1535 //! Linear time otherwise.
1536 iterator insert(const_iterator p, const T &x);
1538 //! <b>Requires</b>: p must be a valid iterator of *this.
1540 //! <b>Effects</b>: Insert a new element before p with x's resources.
1542 //! <b>Returns</b>: an iterator to the inserted element.
1544 //! <b>Throws</b>: If memory allocation throws.
1546 //! <b>Complexity</b>: If p is end(), amortized constant time
1547 //! Linear time otherwise.
1548 iterator insert(const_iterator p, T &&x);
1550 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1553 //! <b>Requires</b>: p must be a valid iterator of *this.
1555 //! <b>Effects</b>: Insert n copies of x before p.
1557 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
1559 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1561 //! <b>Complexity</b>: Linear to n.
1562 iterator insert(const_iterator p, size_type n, const T& t)
1564 BOOST_ASSERT(this->priv_in_range_or_end(p));
1565 STABLE_VECTOR_CHECK_INVARIANT;
1566 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1567 return this->insert(p, cvalue_iterator(t, n), cvalue_iterator());
1570 //! <b>Requires</b>: p must be a valid iterator of *this.
1571 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1572 //! <b>Requires</b>: p must be a valid iterator of *this.
1574 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p.
1576 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1578 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
1579 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, std::initializer_list<value_type> il)
1581 //Position checks done by insert()
1582 STABLE_VECTOR_CHECK_INVARIANT;
1583 return insert(p, il.begin(), il.end());
1587 //! <b>Requires</b>: pos must be a valid iterator of *this.
1589 //! <b>Effects</b>: Insert a copy of the [first, last) range before p.
1591 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1593 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1594 //! dereferenced InpIt throws or T's copy constructor throws.
1596 //! <b>Complexity</b>: Linear to distance [first, last).
1597 template <class InputIterator>
1598 iterator insert(const_iterator p, InputIterator first, InputIterator last
1599 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1600 //Put this as argument instead of the return type as old GCC's like 3.4
1601 //detect this and the next disable_if_or as overloads
1602 , typename dtl::disable_if_or
1604 , dtl::is_convertible<InputIterator, size_type>
1605 , dtl::is_not_input_iterator<InputIterator>
1610 BOOST_ASSERT(this->priv_in_range_or_end(p));
1611 STABLE_VECTOR_CHECK_INVARIANT;
1612 const size_type pos_n = p - this->cbegin();
1613 for(; first != last; ++first){
1614 this->emplace(p, *first);
1616 return this->begin() + pos_n;
1619 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1620 template <class FwdIt>
1621 typename dtl::disable_if_or
1623 , dtl::is_convertible<FwdIt, size_type>
1624 , dtl::is_input_iterator<FwdIt>
1626 insert(const_iterator p, FwdIt first, FwdIt last)
1628 BOOST_ASSERT(this->priv_in_range_or_end(p));
1629 const size_type num_new = static_cast<size_type>(boost::container::iterator_distance(first, last));
1630 const size_type idx = static_cast<size_type>(p - this->cbegin());
1632 //Fills the node pool and inserts num_new null pointers in idx.
1633 //If a new buffer was needed fixes up pointers up to idx so
1634 //past-new nodes are not aligned until the end of this function
1635 //or in a rollback in case of exception
1636 index_iterator it_past_newly_constructed(this->priv_insert_forward_non_templated(idx, num_new));
1637 const index_iterator it_past_new(it_past_newly_constructed + num_new);
1640 insert_rollback rollback(*this, it_past_newly_constructed, it_past_new);
1641 while(first != last){
1642 const node_ptr n = this->priv_get_from_pool();
1644 //Put it in the index so rollback can return it in pool if construct_in_place throws
1645 *it_past_newly_constructed = n;
1646 //Constructs and fixes up pointers This can throw
1647 this->priv_build_node_from_it(n, it_past_newly_constructed, first);
1649 ++it_past_newly_constructed;
1651 //rollback.~insert_rollback() called in case of exception
1653 //Fix up pointers for past-new nodes (new nodes were fixed during construction) and
1654 //nodes before insertion p in priv_insert_forward_non_templated(...)
1655 index_traits_type::fix_up_pointers_from(this->index, it_past_newly_constructed);
1657 return this->begin() + idx;
1661 //! <b>Effects</b>: Removes the last element from the stable_vector.
1663 //! <b>Throws</b>: Nothing.
1665 //! <b>Complexity</b>: Constant time.
1666 BOOST_CONTAINER_FORCEINLINE void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1668 BOOST_ASSERT(!this->empty());
1669 this->erase(--this->cend());
1672 //! <b>Effects</b>: Erases the element at p.
1674 //! <b>Throws</b>: Nothing.
1676 //! <b>Complexity</b>: Linear to the elements between p and the
1677 //! last element. Constant if p is the last element.
1678 BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1680 BOOST_ASSERT(this->priv_in_range(p));
1681 STABLE_VECTOR_CHECK_INVARIANT;
1682 const size_type d = p - this->cbegin();
1683 index_iterator it = this->index.begin() + d;
1684 this->priv_delete_node(p.node_pointer());
1685 it = this->index.erase(it);
1686 index_traits_type::fix_up_pointers_from(this->index, it);
1687 return iterator(node_ptr_traits::static_cast_from(*it));
1690 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1692 //! <b>Throws</b>: Nothing.
1694 //! <b>Complexity</b>: Linear to the distance between first and last
1695 //! plus linear to the elements between p and the last element.
1696 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1698 BOOST_ASSERT(first == last ||
1699 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
1700 STABLE_VECTOR_CHECK_INVARIANT;
1701 const const_iterator cbeg(this->cbegin());
1702 const size_type d1 = static_cast<size_type>(first - cbeg),
1703 d2 = static_cast<size_type>(last - cbeg);
1704 size_type d_dif = d2 - d1;
1706 multiallocation_chain holder;
1707 const index_iterator it1(this->index.begin() + d1);
1708 const index_iterator it2(it1 + d_dif);
1709 index_iterator it(it1);
1711 node_base_ptr &nb = *it;
1713 node_type &n = *node_ptr_traits::static_cast_from(nb);
1714 this->priv_destroy_node(n);
1715 holder.push_back(node_ptr_traits::pointer_to(n));
1717 this->priv_put_in_pool(holder);
1718 const index_iterator e = this->index.erase(it1, it2);
1719 index_traits_type::fix_up_pointers_from(this->index, e);
1721 return iterator(last.node_pointer());
1724 //! <b>Effects</b>: Swaps the contents of *this and x.
1726 //! <b>Throws</b>: Nothing.
1728 //! <b>Complexity</b>: Constant.
1729 void swap(stable_vector & x)
1730 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
1731 || allocator_traits_type::is_always_equal::value)
1733 BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value ||
1734 allocator_traits_type::is_always_equal::value ||
1735 this->get_stored_allocator() == x.get_stored_allocator());
1736 STABLE_VECTOR_CHECK_INVARIANT;
1737 dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1738 dtl::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
1739 //vector's allocator is swapped here
1740 this->index.swap(x.index);
1741 this->priv_swap_members(x);
1744 //! <b>Effects</b>: Erases all the elements of the stable_vector.
1746 //! <b>Throws</b>: Nothing.
1748 //! <b>Complexity</b>: Linear to the number of elements in the stable_vector.
1749 BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW
1750 { this->erase(this->cbegin(),this->cend()); }
1752 //! <b>Effects</b>: Returns true if x and y are equal
1754 //! <b>Complexity</b>: Linear to the number of elements in the container.
1755 BOOST_CONTAINER_FORCEINLINE friend bool operator==(const stable_vector& x, const stable_vector& y)
1756 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1758 //! <b>Effects</b>: Returns true if x and y are unequal
1760 //! <b>Complexity</b>: Linear to the number of elements in the container.
1761 BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const stable_vector& x, const stable_vector& y)
1762 { return !(x == y); }
1764 //! <b>Effects</b>: Returns true if x is less than y
1766 //! <b>Complexity</b>: Linear to the number of elements in the container.
1767 BOOST_CONTAINER_FORCEINLINE friend bool operator<(const stable_vector& x, const stable_vector& y)
1768 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1770 //! <b>Effects</b>: Returns true if x is greater than y
1772 //! <b>Complexity</b>: Linear to the number of elements in the container.
1773 BOOST_CONTAINER_FORCEINLINE friend bool operator>(const stable_vector& x, const stable_vector& y)
1776 //! <b>Effects</b>: Returns true if x is equal or less than y
1778 //! <b>Complexity</b>: Linear to the number of elements in the container.
1779 BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const stable_vector& x, const stable_vector& y)
1780 { return !(y < x); }
1782 //! <b>Effects</b>: Returns true if x is equal or greater than y
1784 //! <b>Complexity</b>: Linear to the number of elements in the container.
1785 BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const stable_vector& x, const stable_vector& y)
1786 { return !(x < y); }
1788 //! <b>Effects</b>: x.swap(y)
1790 //! <b>Complexity</b>: Constant.
1791 BOOST_CONTAINER_FORCEINLINE friend void swap(stable_vector& x, stable_vector& y)
1794 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1797 bool priv_in_range(const_iterator pos) const
1799 return (this->begin() <= pos) && (pos < this->end());
1802 BOOST_CONTAINER_FORCEINLINE bool priv_in_range_or_end(const_iterator pos) const
1804 return (this->begin() <= pos) && (pos <= this->end());
1807 BOOST_CONTAINER_FORCEINLINE size_type priv_index_of(node_ptr p) const
1810 BOOST_ASSERT(this->index.empty() || (this->index.data() <= p->up));
1811 BOOST_ASSERT(this->index.empty() || p->up <= (this->index.data() + this->index.size()));
1812 return this->index.empty() ? 0 : p->up - this->index.data();
1815 class insert_rollback
1819 insert_rollback(stable_vector &sv, index_iterator &it_past_constructed, const index_iterator &it_past_new)
1820 : m_sv(sv), m_it_past_constructed(it_past_constructed), m_it_past_new(it_past_new)
1825 if(m_it_past_constructed != m_it_past_new){
1826 m_sv.priv_put_in_pool(node_ptr_traits::static_cast_from(*m_it_past_constructed));
1827 index_iterator e = m_sv.index.erase(m_it_past_constructed, m_it_past_new);
1828 index_traits_type::fix_up_pointers_from(m_sv.index, e);
1833 stable_vector &m_sv;
1834 index_iterator &m_it_past_constructed;
1835 const index_iterator &m_it_past_new;
1838 class push_back_rollback
1841 BOOST_CONTAINER_FORCEINLINE push_back_rollback(stable_vector &sv, const node_ptr &p)
1845 BOOST_CONTAINER_FORCEINLINE ~push_back_rollback()
1848 m_sv.priv_put_in_pool(m_p);
1852 BOOST_CONTAINER_FORCEINLINE void release()
1853 { m_p = node_ptr(); }
1856 stable_vector &m_sv;
1860 index_iterator priv_insert_forward_non_templated(size_type idx, size_type num_new)
1862 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, num_new);
1864 //Now try to fill the pool with new data
1865 if(this->internal_data.pool_size < num_new){
1866 this->priv_increase_pool(num_new - this->internal_data.pool_size);
1869 //Now try to make room in the vector
1870 const node_base_ptr_ptr old_buffer = this->index.data();
1871 this->index.insert(this->index.begin() + idx, num_new, node_ptr());
1872 bool new_buffer = this->index.data() != old_buffer;
1874 //Fix the pointers for the newly allocated buffer
1875 const index_iterator index_beg = this->index.begin();
1877 index_traits_type::fix_up_pointers(index_beg, index_beg + idx);
1879 return index_beg + idx;
1882 BOOST_CONTAINER_FORCEINLINE bool priv_capacity_bigger_than_size() const
1884 return this->index.capacity() > this->index.size() &&
1885 this->internal_data.pool_size > 0;
1889 void priv_push_back(BOOST_MOVE_CATCH_FWD(U) x)
1891 if(BOOST_LIKELY(this->priv_capacity_bigger_than_size())){
1892 //Enough memory in the pool and in the index
1893 const node_ptr p = this->priv_get_from_pool();
1896 push_back_rollback rollback(*this, p);
1898 this->priv_build_node_from_convertible(p, ::boost::forward<U>(x));
1901 //This can't throw as there is room for a new elements in the index
1902 index_iterator new_index = this->index.insert(this->index.end() - ExtraPointers, p);
1903 index_traits_type::fix_up_pointers_from(this->index, new_index);
1906 this->insert(this->cend(), ::boost::forward<U>(x));
1910 iterator priv_insert(const_iterator p, const value_type &t)
1912 BOOST_ASSERT(this->priv_in_range_or_end(p));
1913 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1914 return this->insert(p, cvalue_iterator(t, 1), cvalue_iterator());
1917 iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x)
1919 BOOST_ASSERT(this->priv_in_range_or_end(p));
1920 typedef repeat_iterator<T, difference_type> repeat_it;
1921 typedef boost::move_iterator<repeat_it> repeat_move_it;
1922 //Just call more general insert(p, size, value) and return iterator
1923 return this->insert(p, repeat_move_it(repeat_it(x, 1)), repeat_move_it(repeat_it()));
1926 void priv_clear_pool()
1928 if(!this->index.empty() && this->index.back()){
1929 node_base_ptr &pool_first_ref = *(this->index.end() - 2);
1930 node_base_ptr &pool_last_ref = this->index.back();
1932 multiallocation_chain holder;
1933 holder.incorporate_after( holder.before_begin()
1934 , node_ptr_traits::static_cast_from(pool_first_ref)
1935 , node_ptr_traits::static_cast_from(pool_last_ref)
1936 , internal_data.pool_size);
1937 this->deallocate_individual(holder);
1938 pool_first_ref = pool_last_ref = 0;
1939 this->internal_data.pool_size = 0;
1943 void priv_increase_pool(size_type n)
1945 node_base_ptr &pool_first_ref = *(this->index.end() - 2);
1946 node_base_ptr &pool_last_ref = this->index.back();
1947 multiallocation_chain holder;
1948 holder.incorporate_after( holder.before_begin()
1949 , node_ptr_traits::static_cast_from(pool_first_ref)
1950 , node_ptr_traits::static_cast_from(pool_last_ref)
1951 , internal_data.pool_size);
1952 multiallocation_chain m;
1953 this->allocate_individual(n, m);
1954 holder.splice_after(holder.before_begin(), m, m.before_begin(), m.last(), n);
1955 this->internal_data.pool_size += n;
1956 std::pair<node_ptr, node_ptr> data(holder.extract_data());
1957 pool_first_ref = data.first;
1958 pool_last_ref = data.second;
1961 void priv_put_in_pool(const node_ptr &p)
1963 node_base_ptr &pool_first_ref = *(this->index.end()-2);
1964 node_base_ptr &pool_last_ref = this->index.back();
1965 multiallocation_chain holder;
1966 holder.incorporate_after( holder.before_begin()
1967 , node_ptr_traits::static_cast_from(pool_first_ref)
1968 , node_ptr_traits::static_cast_from(pool_last_ref)
1969 , internal_data.pool_size);
1970 holder.push_front(p);
1971 ++this->internal_data.pool_size;
1972 std::pair<node_ptr, node_ptr> ret(holder.extract_data());
1973 pool_first_ref = ret.first;
1974 pool_last_ref = ret.second;
1977 void priv_put_in_pool(multiallocation_chain &ch)
1979 node_base_ptr &pool_first_ref = *(this->index.end()-(ExtraPointers-1));
1980 node_base_ptr &pool_last_ref = this->index.back();
1981 ch.incorporate_after( ch.before_begin()
1982 , node_ptr_traits::static_cast_from(pool_first_ref)
1983 , node_ptr_traits::static_cast_from(pool_last_ref)
1984 , internal_data.pool_size);
1985 this->internal_data.pool_size = ch.size();
1986 const std::pair<node_ptr, node_ptr> ret(ch.extract_data());
1987 pool_first_ref = ret.first;
1988 pool_last_ref = ret.second;
1991 node_ptr priv_get_from_pool()
1993 //Precondition: index is not empty
1994 BOOST_ASSERT(!this->index.empty());
1995 node_base_ptr &pool_first_ref = *(this->index.end() - (ExtraPointers-1));
1996 node_base_ptr &pool_last_ref = this->index.back();
1997 multiallocation_chain holder;
1998 holder.incorporate_after( holder.before_begin()
1999 , node_ptr_traits::static_cast_from(pool_first_ref)
2000 , node_ptr_traits::static_cast_from(pool_last_ref)
2001 , internal_data.pool_size);
2002 node_ptr ret = holder.pop_front();
2003 --this->internal_data.pool_size;
2004 if(!internal_data.pool_size){
2005 pool_first_ref = pool_last_ref = node_ptr();
2008 const std::pair<node_ptr, node_ptr> data(holder.extract_data());
2009 pool_first_ref = data.first;
2010 pool_last_ref = data.second;
2015 BOOST_CONTAINER_FORCEINLINE node_base_ptr priv_get_end_node() const
2016 { return node_base_ptr_traits::pointer_to(const_cast<node_base_type&>(this->internal_data.end_node)); }
2018 BOOST_CONTAINER_FORCEINLINE void priv_destroy_node(const node_type &n)
2020 allocator_traits<node_allocator_type>::
2021 destroy(this->priv_node_alloc(), &n);
2024 BOOST_CONTAINER_FORCEINLINE void priv_delete_node(const node_ptr &n)
2026 this->priv_destroy_node(*n);
2027 this->priv_put_in_pool(n);
2030 template<class Iterator>
2031 void priv_build_node_from_it(const node_ptr &p, const index_iterator &up_index, const Iterator &it)
2033 node_type *praw = ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t())
2034 node_type(index_traits_type::ptr_to_node_base_ptr(*up_index));
2037 boost::container::construct_in_place
2038 ( this->priv_node_alloc()
2039 , praw->get_data_ptr()
2043 praw->destroy_header();
2044 this->priv_node_alloc().deallocate(p, 1);
2050 template<class ValueConvertible>
2051 void priv_build_node_from_convertible(const node_ptr &p, BOOST_FWD_REF(ValueConvertible) value_convertible)
2053 node_type *praw = ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) node_type;
2056 boost::container::allocator_traits<node_allocator_type>::construct
2057 ( this->priv_node_alloc()
2059 , ::boost::forward<ValueConvertible>(value_convertible));
2062 praw->destroy_header();
2063 this->priv_node_alloc().deallocate(p, 1);
2069 void priv_swap_members(stable_vector &x)
2071 boost::adl_move_swap(this->internal_data.pool_size, x.internal_data.pool_size);
2072 index_traits_type::readjust_end_node(this->index, this->internal_data.end_node);
2073 index_traits_type::readjust_end_node(x.index, x.internal_data.end_node);
2076 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
2077 bool priv_invariant()const
2079 index_type & index_ref = const_cast<index_type&>(this->index);
2081 const size_type index_size = this->index.size();
2083 return !this->capacity() && !this->size();
2085 if(index_size < ExtraPointers)
2088 const size_type bucket_extra_capacity = this->index.capacity()- index_size;
2089 const size_type node_extra_capacity = this->internal_data.pool_size;
2090 if(bucket_extra_capacity < node_extra_capacity){
2094 if(this->priv_get_end_node() != *(index.end() - ExtraPointers)){
2098 if(!index_traits_type::invariants(index_ref)){
2102 size_type n = this->capacity() - this->size();
2103 node_base_ptr &pool_first_ref = *(index_ref.end() - (ExtraPointers-1));
2104 node_base_ptr &pool_last_ref = index_ref.back();
2105 multiallocation_chain holder;
2106 holder.incorporate_after( holder.before_begin()
2107 , node_ptr_traits::static_cast_from(pool_first_ref)
2108 , node_ptr_traits::static_cast_from(pool_last_ref)
2109 , internal_data.pool_size);
2110 typename multiallocation_chain::iterator beg(holder.begin()), end(holder.end());
2111 size_type num_pool = 0;
2116 return n >= num_pool && num_pool == internal_data.pool_size;
2119 class invariant_checker
2121 invariant_checker(const invariant_checker &);
2122 invariant_checker & operator=(const invariant_checker &);
2123 const stable_vector* p;
2126 invariant_checker(const stable_vector& v):p(&v){}
2127 ~invariant_checker(){BOOST_ASSERT(p->priv_invariant());}
2133 : public node_allocator_type
2136 BOOST_MOVABLE_BUT_NOT_COPYABLE(ebo_holder)
2139 template<class AllocatorRLValue>
2140 explicit ebo_holder(BOOST_FWD_REF(AllocatorRLValue) a)
2141 : node_allocator_type(boost::forward<AllocatorRLValue>(a))
2147 : node_allocator_type()
2152 size_type pool_size;
2153 node_base_type end_node;
2156 node_allocator_type &priv_node_alloc() { return internal_data; }
2157 const node_allocator_type &priv_node_alloc() const { return internal_data; }
2160 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2163 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2165 template <typename InputIterator>
2166 stable_vector(InputIterator, InputIterator) ->
2167 stable_vector<typename iterator_traits<InputIterator>::value_type>;
2169 template <typename InputIterator, typename Allocator>
2170 stable_vector(InputIterator, InputIterator, Allocator const&) ->
2171 stable_vector<typename iterator_traits<InputIterator>::value_type, Allocator>;
2175 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2177 #undef STABLE_VECTOR_CHECK_INVARIANT
2179 } //namespace container {
2181 //!has_trivial_destructor_after_move<> == true_type
2182 //!specialization for optimizations
2183 template <class T, class Allocator>
2184 struct has_trivial_destructor_after_move<boost::container::stable_vector<T, Allocator> >
2186 typedef typename boost::container::stable_vector<T, Allocator>::allocator_type allocator_type;
2187 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
2188 static const bool value = ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
2189 ::boost::has_trivial_destructor_after_move<pointer>::value;
2192 namespace container {
2194 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2196 }} //namespace boost{ namespace container {
2198 #include <boost/container/detail/config_end.hpp>
2200 #endif //BOOST_CONTAINER_STABLE_VECTOR_HPP