1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2005-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
11#ifndef BOOST_CONTAINER_CONTAINER_VECTOR_HPP
12#define BOOST_CONTAINER_CONTAINER_VECTOR_HPP
13
14#ifndef BOOST_CONFIG_HPP
15# include <boost/config.hpp>
16#endif
17
18#if defined(BOOST_HAS_PRAGMA_ONCE)
19# pragma once
20#endif
21
22#include <boost/container/detail/config_begin.hpp>
23#include <boost/container/detail/workaround.hpp>
24
25// container
26#include <boost/container/container_fwd.hpp>
27#include <boost/container/allocator_traits.hpp>
28#include <boost/container/new_allocator.hpp> //new_allocator
29#include <boost/container/throw_exception.hpp>
30// container detail
31#include <boost/container/detail/advanced_insert_int.hpp>
32#include <boost/container/detail/algorithm.hpp> //equal()
33#include <boost/container/detail/alloc_helpers.hpp>
34#include <boost/container/detail/allocation_type.hpp>
35#include <boost/container/detail/copy_move_algo.hpp>
36#include <boost/container/detail/destroyers.hpp>
37#include <boost/container/detail/iterator.hpp>
38#include <boost/container/detail/iterators.hpp>
39#include <boost/move/detail/iterator_to_raw_pointer.hpp>
40#include <boost/container/detail/mpl.hpp>
41#include <boost/container/detail/next_capacity.hpp>
42#include <boost/move/detail/to_raw_pointer.hpp>
43#include <boost/container/detail/type_traits.hpp>
44#include <boost/container/detail/version_type.hpp>
45// intrusive
46#include <boost/intrusive/pointer_traits.hpp>
47// move
48#include <boost/move/adl_move_swap.hpp>
49#include <boost/move/iterator.hpp>
50#include <boost/move/traits.hpp>
51#include <boost/move/utility_core.hpp>
52// move/detail
53#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
54#include <boost/move/detail/fwd_macros.hpp>
55#endif
56#include <boost/move/detail/move_helpers.hpp>
57// move/algo
58#include <boost/move/algo/adaptive_merge.hpp>
59#include <boost/move/algo/unique.hpp>
60#include <boost/move/algo/predicate.hpp>
61// other
62#include <boost/core/no_exceptions_support.hpp>
63#include <boost/assert.hpp>
64#include <boost/cstdint.hpp>
65
66//std
67#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
68#include <initializer_list> //for std::initializer_list
69#endif
70
71namespace boost {
72namespace container {
73
74#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
75
76//#define BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
77
78namespace container_detail {
79
80#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
81
82template <class Pointer, bool IsConst>
83class vec_iterator
84{
85 public:
86 typedef std::random_access_iterator_tag iterator_category;
87 typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
88 typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
89 typedef typename if_c
90 < IsConst
91 , typename boost::intrusive::pointer_traits<Pointer>::template
92 rebind_pointer<const value_type>::type
93 , Pointer
94 >::type pointer;
95 typedef typename boost::intrusive::pointer_traits<pointer> ptr_traits;
96 typedef typename ptr_traits::reference reference;
97
98 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
99 private:
100 Pointer m_ptr;
101
102 public:
103 BOOST_CONTAINER_FORCEINLINE const Pointer &get_ptr() const BOOST_NOEXCEPT_OR_NOTHROW
104 { return m_ptr; }
105
106 BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr() BOOST_NOEXCEPT_OR_NOTHROW
107 { return m_ptr; }
108
109 BOOST_CONTAINER_FORCEINLINE explicit vec_iterator(Pointer ptr) BOOST_NOEXCEPT_OR_NOTHROW
110 : m_ptr(ptr)
111 {}
112 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
113
114 public:
115
116 //Constructors
117 BOOST_CONTAINER_FORCEINLINE vec_iterator() BOOST_NOEXCEPT_OR_NOTHROW
118 : m_ptr() //Value initialization to achieve "null iterators" (N3644)
119 {}
120
121 BOOST_CONTAINER_FORCEINLINE vec_iterator(vec_iterator<Pointer, false> const& other) BOOST_NOEXCEPT_OR_NOTHROW
122 : m_ptr(other.get_ptr())
123 {}
124
125 //Pointer like operators
126 BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW
127 { return *m_ptr; }
128
129 BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW
130 { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*()); }
131
132 BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW
133 { return m_ptr[off]; }
134
135 //Increment / Decrement
136 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW
137 { ++m_ptr; return *this; }
138
139 BOOST_CONTAINER_FORCEINLINE vec_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW
140 { return vec_iterator(m_ptr++); }
141
142 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW
143 { --m_ptr; return *this; }
144
145 BOOST_CONTAINER_FORCEINLINE vec_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW
146 { return vec_iterator(m_ptr--); }
147
148 //Arithmetic
149 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
150 { m_ptr += off; return *this; }
151
152 BOOST_CONTAINER_FORCEINLINE vec_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
153 { m_ptr -= off; return *this; }
154
155 BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(const vec_iterator &x, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
156 { return vec_iterator(x.m_ptr+off); }
157
158 BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(difference_type off, vec_iterator right) BOOST_NOEXCEPT_OR_NOTHROW
159 { right.m_ptr += off; return right; }
160
161 BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator-(vec_iterator left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW
162 { left.m_ptr -= off; return left; }
163
164 BOOST_CONTAINER_FORCEINLINE friend difference_type operator-(const vec_iterator &left, const vec_iterator& right) BOOST_NOEXCEPT_OR_NOTHROW
165 { return left.m_ptr - right.m_ptr; }
166
167 //Comparison operators
168 BOOST_CONTAINER_FORCEINLINE friend bool operator== (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
169 { return l.m_ptr == r.m_ptr; }
170
171 BOOST_CONTAINER_FORCEINLINE friend bool operator!= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
172 { return l.m_ptr != r.m_ptr; }
173
174 BOOST_CONTAINER_FORCEINLINE friend bool operator< (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
175 { return l.m_ptr < r.m_ptr; }
176
177 BOOST_CONTAINER_FORCEINLINE friend bool operator<= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
178 { return l.m_ptr <= r.m_ptr; }
179
180 BOOST_CONTAINER_FORCEINLINE friend bool operator> (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
181 { return l.m_ptr > r.m_ptr; }
182
183 BOOST_CONTAINER_FORCEINLINE friend bool operator>= (const vec_iterator& l, const vec_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW
184 { return l.m_ptr >= r.m_ptr; }
185};
186
187template<class BiDirPosConstIt, class BiDirValueIt>
188struct vector_insert_ordered_cursor
189{
190 typedef typename iterator_traits<BiDirPosConstIt>::value_type size_type;
191 typedef typename iterator_traits<BiDirValueIt>::reference reference;
192
193 BOOST_CONTAINER_FORCEINLINE vector_insert_ordered_cursor(BiDirPosConstIt posit, BiDirValueIt valueit)
194 : last_position_it(posit), last_value_it(valueit)
195 {}
196
197 void operator --()
198 {
199 --last_value_it;
200 --last_position_it;
201 while(this->get_pos() == size_type(-1)){
202 --last_value_it;
203 --last_position_it;
204 }
205 }
206
207 BOOST_CONTAINER_FORCEINLINE size_type get_pos() const
208 { return *last_position_it; }
209
210 BOOST_CONTAINER_FORCEINLINE reference get_val()
211 { return *last_value_it; }
212
213 BiDirPosConstIt last_position_it;
214 BiDirValueIt last_value_it;
215};
216
217template<class T, class SizeType, class BiDirValueIt, class Comp>
218struct vector_merge_cursor
219{
220 typedef SizeType size_type;
221 typedef typename iterator_traits<BiDirValueIt>::reference reference;
222
223 BOOST_CONTAINER_FORCEINLINE vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp &cmp)
224 : m_pbeg(pbeg), m_pcur(--plast), m_valueit(valueit), m_cmp(cmp)
225 {}
226
227 void operator --()
228 {
229 --m_valueit;
230 const T &t = *m_valueit;
231 while((m_pcur + 1) != m_pbeg){
232 if(!m_cmp(t, *m_pcur)){
233 break;
234 }
235 --m_pcur;
236 }
237 }
238
239 BOOST_CONTAINER_FORCEINLINE size_type get_pos() const
240 { return static_cast<size_type>((m_pcur + 1) - m_pbeg); }
241
242 BOOST_CONTAINER_FORCEINLINE reference get_val()
243 { return *m_valueit; }
244
245 T *const m_pbeg;
246 T *m_pcur;
247 BiDirValueIt m_valueit;
248 Comp &m_cmp;
249};
250
251} //namespace container_detail {
252
253template<class Pointer, bool IsConst>
254BOOST_CONTAINER_FORCEINLINE const Pointer &vector_iterator_get_ptr(const container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW
255{ return it.get_ptr(); }
256
257template<class Pointer, bool IsConst>
258BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr(container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_NOEXCEPT_OR_NOTHROW
259{ return it.get_ptr(); }
260
261namespace container_detail {
262
263#else //ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
264
265template< class MaybeConstPointer
266 , bool ElementTypeIsConst
267 = is_const< typename boost::intrusive::pointer_traits<MaybeConstPointer>::element_type>::value >
268struct vector_get_ptr_pointer_to_non_const
269{
270 typedef MaybeConstPointer const_pointer;
271 typedef boost::intrusive::pointer_traits<const_pointer> pointer_traits_t;
272 typedef typename pointer_traits_t::element_type element_type;
273 typedef typename remove_const<element_type>::type non_const_element_type;
274 typedef typename pointer_traits_t
275 ::template rebind_pointer<non_const_element_type>::type return_type;
276
277 BOOST_CONTAINER_FORCEINLINE static return_type get_ptr(const const_pointer &ptr) BOOST_NOEXCEPT_OR_NOTHROW
278 { return boost::intrusive::pointer_traits<return_type>::const_cast_from(ptr); }
279};
280
281template<class Pointer>
282struct vector_get_ptr_pointer_to_non_const<Pointer, false>
283{
284 typedef const Pointer & return_type;
285 BOOST_CONTAINER_FORCEINLINE static return_type get_ptr(const Pointer &ptr) BOOST_NOEXCEPT_OR_NOTHROW
286 { return ptr; }
287};
288
289} //namespace container_detail {
290
291template<class MaybeConstPointer>
292BOOST_CONTAINER_FORCEINLINE typename container_detail::vector_get_ptr_pointer_to_non_const<MaybeConstPointer>::return_type
293 vector_iterator_get_ptr(const MaybeConstPointer &ptr) BOOST_NOEXCEPT_OR_NOTHROW
294{
295 return container_detail::vector_get_ptr_pointer_to_non_const<MaybeConstPointer>::get_ptr(ptr);
296}
297
298namespace container_detail {
299
300#endif //#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
301
302struct uninitialized_size_t {};
303static const uninitialized_size_t uninitialized_size = uninitialized_size_t();
304
305template <class T>
306struct vector_value_traits_base
307{
308 static const bool trivial_dctr = is_trivially_destructible<T>::value;
309 static const bool trivial_dctr_after_move = has_trivial_destructor_after_move<T>::value;
310 static const bool trivial_copy = is_trivially_copy_constructible<T>::value;
311 static const bool nothrow_copy = is_nothrow_copy_constructible<T>::value || trivial_copy;
312 static const bool trivial_assign = is_trivially_copy_assignable<T>::value;
313 static const bool nothrow_assign = is_nothrow_copy_assignable<T>::value || trivial_assign;
314};
315
316
317template <class Allocator>
318struct vector_value_traits
319 : public vector_value_traits_base<typename Allocator::value_type>
320{
321 typedef vector_value_traits_base<typename Allocator::value_type> base_t;
322 //This is the anti-exception array destructor
323 //to deallocate values already constructed
324 typedef typename container_detail::if_c
325 <base_t::trivial_dctr
326 ,container_detail::null_scoped_destructor_n<Allocator>
327 ,container_detail::scoped_destructor_n<Allocator>
328 >::type ArrayDestructor;
329 //This is the anti-exception array deallocator
330 typedef container_detail::scoped_array_deallocator<Allocator> ArrayDeallocator;
331};
332
333//!This struct deallocates and allocated memory
334template < class Allocator
335 , class AllocatorVersion = typename container_detail::version<Allocator>::type
336 >
337struct vector_alloc_holder
338 : public Allocator
339{
340 private:
341 BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder)
342
343 public:
344 typedef Allocator allocator_type;
345 typedef boost::container::allocator_traits<Allocator> allocator_traits_type;
346 typedef typename allocator_traits_type::pointer pointer;
347 typedef typename allocator_traits_type::size_type size_type;
348 typedef typename allocator_traits_type::value_type value_type;
349
350 static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator)
351 {
352 (void)propagate_allocator; (void)p; (void)to_alloc; (void)from_alloc;
353 const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||
354 !allocator_traits_type::storage_is_unpropagable(from_alloc, p);
355 return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc));
356 }
357
358 static bool are_swap_propagable(const allocator_type &l_a, pointer l_p, const allocator_type &r_a, pointer r_p, bool const propagate_allocator)
359 {
360 (void)propagate_allocator; (void)l_p; (void)r_p; (void)l_a; (void)r_a;
361 const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value ||
362 !(allocator_traits_type::storage_is_unpropagable(l_a, l_p) || allocator_traits_type::storage_is_unpropagable(r_a, r_p));
363 return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(l_a, r_a));
364 }
365
366 //Constructor, does not throw
367 vector_alloc_holder()
368 BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
369 : Allocator(), m_start(), m_size(), m_capacity()
370 {}
371
372 //Constructor, does not throw
373 template<class AllocConvertible>
374 explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW
375 : Allocator(boost::forward<AllocConvertible>(a)), m_start(), m_size(), m_capacity()
376 {}
377
378 //Constructor, does not throw
379 template<class AllocConvertible>
380 vector_alloc_holder(uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)
381 : Allocator(boost::forward<AllocConvertible>(a))
382 , m_start()
383 , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this
384 , m_capacity()
385 {
386 if(initial_size){
387 pointer reuse = pointer();
388 m_start = this->allocation_command(allocate_new, initial_size, m_capacity = initial_size, reuse);
389 }
390 }
391
392 //Constructor, does not throw
393 vector_alloc_holder(uninitialized_size_t, size_type initial_size)
394 : Allocator()
395 , m_start()
396 , m_size(initial_size) //Size is initialized here so vector should only call uninitialized_xxx after this
397 , m_capacity()
398 {
399 if(initial_size){
400 pointer reuse = pointer();
401 m_start = this->allocation_command(allocate_new, initial_size, m_capacity = initial_size, reuse);
402 }
403 }
404
405 vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder) BOOST_NOEXCEPT_OR_NOTHROW
406 : Allocator(BOOST_MOVE_BASE(Allocator, holder))
407 , m_start(holder.m_start)
408 , m_size(holder.m_size)
409 , m_capacity(holder.m_capacity)
410 {
411 holder.m_start = pointer();
412 holder.m_size = holder.m_capacity = 0;
413 }
414
415 vector_alloc_holder(pointer p, size_type capacity, BOOST_RV_REF(vector_alloc_holder) holder)
416 : Allocator(BOOST_MOVE_BASE(Allocator, holder))
417 , m_start(p)
418 , m_size(holder.m_size)
419 , m_capacity(capacity)
420 {
421 allocator_type &this_alloc = this->alloc();
422 allocator_type &x_alloc = holder.alloc();
423 if(this->is_propagable_from(x_alloc, holder.start(), this_alloc, true)){
424 if(this->m_capacity){
425 this->alloc().deallocate(this->m_start, this->m_capacity);
426 }
427 m_start = holder.m_start;
428 m_capacity = holder.m_capacity;
429 holder.m_start = pointer();
430 holder.m_capacity = holder.m_size = 0;
431 }
432 else if(this->m_capacity < holder.m_size){
433 size_type const n = holder.m_size;
434 pointer reuse = pointer();
435 m_start = this->allocation_command(allocate_new, n, m_capacity = n, reuse);
436 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
437 this->num_alloc += n != 0;
438 #endif
439 }
440 }
441
442 vector_alloc_holder(pointer p, size_type n)
443 BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
444 : Allocator()
445 , m_start(p)
446 , m_size()
447 , m_capacity(n)
448 {}
449
450 template<class AllocFwd>
451 vector_alloc_holder(pointer p, size_type n, BOOST_FWD_REF(AllocFwd) a)
452 : Allocator(::boost::forward<AllocFwd>(a))
453 , m_start(p)
454 , m_size()
455 , m_capacity(n)
456 {}
457
458 BOOST_CONTAINER_FORCEINLINE ~vector_alloc_holder() BOOST_NOEXCEPT_OR_NOTHROW
459 {
460 if(this->m_capacity){
461 this->alloc().deallocate(this->m_start, this->m_capacity);
462 }
463 }
464
465 BOOST_CONTAINER_FORCEINLINE pointer allocation_command(boost::container::allocation_type command,
466 size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse)
467 {
468 typedef typename container_detail::version<Allocator>::type alloc_version;
469 return this->priv_allocation_command(alloc_version(), command, limit_size, prefer_in_recvd_out_size, reuse);
470 }
471
472 bool try_expand_fwd(size_type at_least)
473 {
474 //There is not enough memory, try to expand the old one
475 const size_type new_cap = this->capacity() + at_least;
476 size_type real_cap = new_cap;
477 pointer reuse = this->start();
478 bool const success = !!this->allocation_command(expand_fwd, new_cap, real_cap, reuse);
479 //Check for forward expansion
480 if(success){
481 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
482 ++this->num_expand_fwd;
483 #endif
484 this->capacity(real_cap);
485 }
486 return success;
487 }
488
489 BOOST_CONTAINER_FORCEINLINE size_type next_capacity(size_type additional_objects) const
490 {
491 return next_capacity_calculator
492 <size_type, NextCapacityDouble //NextCapacity60Percent
493 >::get( allocator_traits_type::max_size(this->alloc())
494 , this->m_capacity, additional_objects );
495 }
496
497 pointer m_start;
498 size_type m_size;
499 size_type m_capacity;
500
501 void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW
502 {
503 boost::adl_move_swap(this->m_start, x.m_start);
504 boost::adl_move_swap(this->m_size, x.m_size);
505 boost::adl_move_swap(this->m_capacity, x.m_capacity);
506 }
507
508 void steal_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW
509 {
510 this->m_start = x.m_start;
511 this->m_size = x.m_size;
512 this->m_capacity = x.m_capacity;
513 x.m_start = pointer();
514 x.m_size = x.m_capacity = 0;
515 }
516
517 BOOST_CONTAINER_FORCEINLINE Allocator &alloc() BOOST_NOEXCEPT_OR_NOTHROW
518 { return *this; }
519
520 BOOST_CONTAINER_FORCEINLINE const Allocator &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
521 { return *this; }
522
523 const pointer &start() const BOOST_NOEXCEPT_OR_NOTHROW { return m_start; }
524 const size_type &capacity() const BOOST_NOEXCEPT_OR_NOTHROW { return m_capacity; }
525 void start(const pointer &p) BOOST_NOEXCEPT_OR_NOTHROW { m_start = p; }
526 void capacity(const size_type &c) BOOST_NOEXCEPT_OR_NOTHROW { m_capacity = c; }
527
528 private:
529 void priv_first_allocation(size_type cap)
530 {
531 if(cap){
532 pointer reuse = pointer();
533 m_start = this->allocation_command(allocate_new, cap, cap, reuse);
534 m_capacity = cap;
535 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
536 ++this->num_alloc;
537 #endif
538 }
539 }
540
541 BOOST_CONTAINER_FORCEINLINE pointer priv_allocation_command(version_1, boost::container::allocation_type command,
542 size_type ,
543 size_type &prefer_in_recvd_out_size,
544 pointer &reuse)
545 {
546 (void)command;
547 BOOST_ASSERT( (command & allocate_new));
548 BOOST_ASSERT(!(command & nothrow_allocation));
549 pointer const p = allocator_traits_type::allocate(this->alloc(), prefer_in_recvd_out_size, reuse);
550 reuse = pointer();
551 return p;
552 }
553
554 pointer priv_allocation_command(version_2, boost::container::allocation_type command,
555 size_type limit_size,
556 size_type &prefer_in_recvd_out_size,
557 pointer &reuse)
558 {
559 return this->alloc().allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse);
560 }
561};
562
563//!This struct deallocates and allocated memory
564template <class Allocator>
565struct vector_alloc_holder<Allocator, version_0>
566 : public Allocator
567{
568 private:
569 BOOST_MOVABLE_BUT_NOT_COPYABLE(vector_alloc_holder)
570
571 public:
572 typedef boost::container::allocator_traits<Allocator> allocator_traits_type;
573 typedef typename allocator_traits_type::pointer pointer;
574 typedef typename allocator_traits_type::size_type size_type;
575 typedef typename allocator_traits_type::value_type value_type;
576
577 template <class OtherAllocator, class OtherAllocatorVersion>
578 friend struct vector_alloc_holder;
579
580 //Constructor, does not throw
581 vector_alloc_holder()
582 BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
583 : Allocator(), m_size()
584 {}
585
586 //Constructor, does not throw
587 template<class AllocConvertible>
588 explicit vector_alloc_holder(BOOST_FWD_REF(AllocConvertible) a) BOOST_NOEXCEPT_OR_NOTHROW
589 : Allocator(boost::forward<AllocConvertible>(a)), m_size()
590 {}
591
592 //Constructor, does not throw
593 template<class AllocConvertible>
594 vector_alloc_holder(uninitialized_size_t, BOOST_FWD_REF(AllocConvertible) a, size_type initial_size)
595 : Allocator(boost::forward<AllocConvertible>(a))
596 , m_size(initial_size) //Size is initialized here...
597 {
598 //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor
599 this->priv_first_allocation(initial_size);
600 }
601
602 //Constructor, does not throw
603 vector_alloc_holder(uninitialized_size_t, size_type initial_size)
604 : Allocator()
605 , m_size(initial_size) //Size is initialized here...
606 {
607 //... and capacity here, so vector, must call uninitialized_xxx in the derived constructor
608 this->priv_first_allocation(initial_size);
609 }
610
611 vector_alloc_holder(BOOST_RV_REF(vector_alloc_holder) holder)
612 : Allocator(BOOST_MOVE_BASE(Allocator, holder))
613 , m_size(holder.m_size) //Size is initialized here so vector should only call uninitialized_xxx after this
614 {
615 ::boost::container::uninitialized_move_alloc_n
616 (this->alloc(), boost::movelib::to_raw_pointer(holder.start()), m_size, boost::movelib::to_raw_pointer(this->start()));
617 }
618
619 template<class OtherAllocator, class OtherAllocatorVersion>
620 vector_alloc_holder(BOOST_RV_REF_BEG vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> BOOST_RV_REF_END holder)
621 : Allocator()
622 , m_size(holder.m_size) //Initialize it to m_size as first_allocation can only succeed or abort
623 {
624 //Different allocator type so we must check we have enough storage
625 const size_type n = holder.m_size;
626 this->priv_first_allocation(n);
627 ::boost::container::uninitialized_move_alloc_n
628 (this->alloc(), boost::movelib::to_raw_pointer(holder.start()), n, boost::movelib::to_raw_pointer(this->start()));
629 }
630
631 BOOST_CONTAINER_FORCEINLINE void priv_first_allocation(size_type cap)
632 {
633 if(cap > Allocator::internal_capacity){
634 throw_bad_alloc();
635 }
636 }
637
638 BOOST_CONTAINER_FORCEINLINE void deep_swap(vector_alloc_holder &x)
639 {
640 this->priv_deep_swap(x);
641 }
642
643 template<class OtherAllocator, class OtherAllocatorVersion>
644 void deep_swap(vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> &x)
645 {
646 if(this->m_size > OtherAllocator::internal_capacity || x.m_size > Allocator::internal_capacity){
647 throw_bad_alloc();
648 }
649 this->priv_deep_swap(x);
650 }
651
652 BOOST_CONTAINER_FORCEINLINE void swap_resources(vector_alloc_holder &) BOOST_NOEXCEPT_OR_NOTHROW
653 { //Containers with version 0 allocators can't be moved without moving elements one by one
654 throw_bad_alloc();
655 }
656
657
658 BOOST_CONTAINER_FORCEINLINE void steal_resources(vector_alloc_holder &)
659 { //Containers with version 0 allocators can't be moved without moving elements one by one
660 throw_bad_alloc();
661 }
662
663 BOOST_CONTAINER_FORCEINLINE Allocator &alloc() BOOST_NOEXCEPT_OR_NOTHROW
664 { return *this; }
665
666 BOOST_CONTAINER_FORCEINLINE const Allocator &alloc() const BOOST_NOEXCEPT_OR_NOTHROW
667 { return *this; }
668
669 BOOST_CONTAINER_FORCEINLINE bool try_expand_fwd(size_type at_least)
670 { return !at_least; }
671
672 BOOST_CONTAINER_FORCEINLINE pointer start() const BOOST_NOEXCEPT_OR_NOTHROW { return Allocator::internal_storage(); }
673 BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW { return Allocator::internal_capacity; }
674 size_type m_size;
675
676 private:
677
678 template<class OtherAllocator, class OtherAllocatorVersion>
679 void priv_deep_swap(vector_alloc_holder<OtherAllocator, OtherAllocatorVersion> &x)
680 {
681 const size_type MaxTmpStorage = sizeof(value_type)*Allocator::internal_capacity;
682 value_type *const first_this = boost::movelib::to_raw_pointer(this->start());
683 value_type *const first_x = boost::movelib::to_raw_pointer(x.start());
684
685 if(this->m_size < x.m_size){
686 boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_this, this->m_size, first_x, x.m_size);
687 }
688 else{
689 boost::container::deep_swap_alloc_n<MaxTmpStorage>(this->alloc(), first_x, x.m_size, first_this, this->m_size);
690 }
691 boost::adl_move_swap(this->m_size, x.m_size);
692 }
693};
694
695} //namespace container_detail {
696
697#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
698
699//! A vector is a sequence that supports random access to elements, constant
700//! time insertion and removal of elements at the end, and linear time insertion
701//! and removal of elements at the beginning or in the middle. The number of
702//! elements in a vector may vary dynamically; memory management is automatic.
703//!
704//! \tparam T The type of object that is stored in the vector
705//! \tparam Allocator The allocator used for all internal memory management
706template <class T, class Allocator BOOST_CONTAINER_DOCONLY(= new_allocator<T>) >
707class vector
708{
709 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
710
711 struct value_less
712 {
713 typedef typename boost::container::allocator_traits<Allocator>::value_type value_type;
714 bool operator()(const value_type &a, const value_type &b) const
715 { return a < b; }
716 };
717
718 typedef typename container_detail::version<Allocator>::type alloc_version;
719 typedef boost::container::container_detail::vector_alloc_holder<Allocator> alloc_holder_t;
720 alloc_holder_t m_holder;
721 typedef allocator_traits<Allocator> allocator_traits_type;
722 template <class U, class UAllocator>
723 friend class vector;
724
725 typedef typename allocator_traits_type::pointer pointer_impl;
726 typedef container_detail::vec_iterator<pointer_impl, false> iterator_impl;
727 typedef container_detail::vec_iterator<pointer_impl, true > const_iterator_impl;
728
729 protected:
730 static bool is_propagable_from(const Allocator &from_alloc, pointer_impl p, const Allocator &to_alloc, bool const propagate_allocator)
731 { return alloc_holder_t::is_propagable_from(from_alloc, p, to_alloc, propagate_allocator); }
732
733 static bool are_swap_propagable( const Allocator &l_a, pointer_impl l_p
734 , const Allocator &r_a, pointer_impl r_p, bool const propagate_allocator)
735 { return alloc_holder_t::are_swap_propagable(l_a, l_p, r_a, r_p, propagate_allocator); }
736
737 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
738 public:
739 //////////////////////////////////////////////
740 //
741 // types
742 //
743 //////////////////////////////////////////////
744
745 typedef T value_type;
746 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
747 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
748 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
749 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
750 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
751 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
752 typedef Allocator allocator_type;
753 typedef Allocator stored_allocator_type;
754 #if defined BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
755 typedef BOOST_CONTAINER_IMPDEF(pointer) iterator;
756 typedef BOOST_CONTAINER_IMPDEF(const_pointer) const_iterator;
757 #else
758 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
759 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
760 #endif
761 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
762 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
763
764 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
765 private:
766 BOOST_COPYABLE_AND_MOVABLE(vector)
767 typedef container_detail::vector_value_traits<Allocator> value_traits;
768 typedef constant_iterator<T, difference_type> cvalue_iterator;
769
770 protected:
771
772 BOOST_CONTAINER_FORCEINLINE void steal_resources(vector &x)
773 { return this->m_holder.steal_resources(x.m_holder); }
774
775 struct initial_capacity_t{};
776 template<class AllocFwd>
777 BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity, BOOST_FWD_REF(AllocFwd) a)
778 : m_holder(initial_memory, capacity, ::boost::forward<AllocFwd>(a))
779 {}
780
781 BOOST_CONTAINER_FORCEINLINE vector(initial_capacity_t, pointer initial_memory, size_type capacity)
782 : m_holder(initial_memory, capacity)
783 {}
784
785 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
786
787 public:
788 //////////////////////////////////////////////
789 //
790 // construct/copy/destroy
791 //
792 //////////////////////////////////////////////
793
794 //! <b>Effects</b>: Constructs a vector taking the allocator as parameter.
795 //!
796 //! <b>Throws</b>: Nothing.
797 //!
798 //! <b>Complexity</b>: Constant.
799 vector() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value)
800 : m_holder()
801 {}
802
803 //! <b>Effects</b>: Constructs a vector taking the allocator as parameter.
804 //!
805 //! <b>Throws</b>: Nothing
806 //!
807 //! <b>Complexity</b>: Constant.
808 explicit vector(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW
809 : m_holder(a)
810 {}
811
812 //! <b>Effects</b>: Constructs a vector and inserts n value initialized values.
813 //!
814 //! <b>Throws</b>: If allocator_type's allocation
815 //! throws or T's value initialization throws.
816 //!
817 //! <b>Complexity</b>: Linear to n.
818 explicit vector(size_type n)
819 : m_holder(container_detail::uninitialized_size, n)
820 {
821 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
822 this->num_alloc += n != 0;
823 #endif
824 boost::container::uninitialized_value_init_alloc_n
825 (this->m_holder.alloc(), n, this->priv_raw_begin());
826 }
827
828 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
829 //! and inserts n value initialized values.
830 //!
831 //! <b>Throws</b>: If allocator_type's allocation
832 //! throws or T's value initialization throws.
833 //!
834 //! <b>Complexity</b>: Linear to n.
835 explicit vector(size_type n, const allocator_type &a)
836 : m_holder(container_detail::uninitialized_size, a, n)
837 {
838 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
839 this->num_alloc += n != 0;
840 #endif
841 boost::container::uninitialized_value_init_alloc_n
842 (this->m_holder.alloc(), n, this->priv_raw_begin());
843 }
844
845 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
846 //! and inserts n default initialized values.
847 //!
848 //! <b>Throws</b>: If allocator_type's allocation
849 //! throws or T's default initialization throws.
850 //!
851 //! <b>Complexity</b>: Linear to n.
852 //!
853 //! <b>Note</b>: Non-standard extension
854 vector(size_type n, default_init_t)
855 : m_holder(container_detail::uninitialized_size, n)
856 {
857 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
858 this->num_alloc += n != 0;
859 #endif
860 boost::container::uninitialized_default_init_alloc_n
861 (this->m_holder.alloc(), n, this->priv_raw_begin());
862 }
863
864 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
865 //! and inserts n default initialized values.
866 //!
867 //! <b>Throws</b>: If allocator_type's allocation
868 //! throws or T's default initialization throws.
869 //!
870 //! <b>Complexity</b>: Linear to n.
871 //!
872 //! <b>Note</b>: Non-standard extension
873 vector(size_type n, default_init_t, const allocator_type &a)
874 : m_holder(container_detail::uninitialized_size, a, n)
875 {
876 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
877 this->num_alloc += n != 0;
878 #endif
879 boost::container::uninitialized_default_init_alloc_n
880 (this->m_holder.alloc(), n, this->priv_raw_begin());
881 }
882
883 //! <b>Effects</b>: Constructs a vector
884 //! and inserts n copies of value.
885 //!
886 //! <b>Throws</b>: If allocator_type's allocation
887 //! throws or T's copy constructor throws.
888 //!
889 //! <b>Complexity</b>: Linear to n.
890 vector(size_type n, const T& value)
891 : m_holder(container_detail::uninitialized_size, n)
892 {
893 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
894 this->num_alloc += n != 0;
895 #endif
896 boost::container::uninitialized_fill_alloc_n
897 (this->m_holder.alloc(), value, n, this->priv_raw_begin());
898 }
899
900 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
901 //! and inserts n copies of value.
902 //!
903 //! <b>Throws</b>: If allocation
904 //! throws or T's copy constructor throws.
905 //!
906 //! <b>Complexity</b>: Linear to n.
907 vector(size_type n, const T& value, const allocator_type& a)
908 : m_holder(container_detail::uninitialized_size, a, n)
909 {
910 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
911 this->num_alloc += n != 0;
912 #endif
913 boost::container::uninitialized_fill_alloc_n
914 (this->m_holder.alloc(), value, n, this->priv_raw_begin());
915 }
916
917 //! <b>Effects</b>: Constructs a vector
918 //! and inserts a copy of the range [first, last) in the vector.
919 //!
920 //! <b>Throws</b>: If allocator_type's allocation
921 //! throws or T's constructor taking a dereferenced InIt throws.
922 //!
923 //! <b>Complexity</b>: Linear to the range [first, last).
924 template <class InIt>
925 vector(InIt first, InIt last
926 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c
927 < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value
928 BOOST_MOVE_I container_detail::nat >::type * = 0)
929 )
930 : m_holder()
931 { this->assign(first, last); }
932
933 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
934 //! and inserts a copy of the range [first, last) in the vector.
935 //!
936 //! <b>Throws</b>: If allocator_type's allocation
937 //! throws or T's constructor taking a dereferenced InIt throws.
938 //!
939 //! <b>Complexity</b>: Linear to the range [first, last).
940 template <class InIt>
941 vector(InIt first, InIt last, const allocator_type& a
942 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c
943 < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value
944 BOOST_MOVE_I container_detail::nat >::type * = 0)
945 )
946 : m_holder(a)
947 { this->assign(first, last); }
948
949 //! <b>Effects</b>: Copy constructs a vector.
950 //!
951 //! <b>Postcondition</b>: x == *this.
952 //!
953 //! <b>Throws</b>: If allocator_type's allocation
954 //! throws or T's copy constructor throws.
955 //!
956 //! <b>Complexity</b>: Linear to the elements x contains.
957 vector(const vector &x)
958 : m_holder( container_detail::uninitialized_size
959 , allocator_traits_type::select_on_container_copy_construction(x.m_holder.alloc())
960 , x.size())
961 {
962 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
963 this->num_alloc += x.size() != 0;
964 #endif
965 ::boost::container::uninitialized_copy_alloc_n
966 ( this->m_holder.alloc(), x.priv_raw_begin()
967 , x.size(), this->priv_raw_begin());
968 }
969
970 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
971 //!
972 //! <b>Throws</b>: Nothing
973 //!
974 //! <b>Complexity</b>: Constant.
975 vector(BOOST_RV_REF(vector) x) BOOST_NOEXCEPT_OR_NOTHROW
976 : m_holder(boost::move(x.m_holder))
977 { BOOST_STATIC_ASSERT((!allocator_traits_type::is_partially_propagable::value)); }
978
979 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
980 //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a
981 //! and inserts a copy of the range [il.begin(), il.last()) in the vector
982 //!
983 //! <b>Throws</b>: If T's constructor taking a dereferenced initializer_list iterator throws.
984 //!
985 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
986 vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type())
987 : m_holder(a)
988 {
989 this->assign(il.begin(), il.end());
990 }
991 #endif
992
993 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
994
995 //! <b>Effects</b>: Move constructor. Moves x's resources to *this.
996 //!
997 //! <b>Throws</b>: If T's move constructor or allocation throws
998 //!
999 //! <b>Complexity</b>: Linear.
1000 //!
1001 //! <b>Note</b>: Non-standard extension to support static_vector
1002 template<class OtherAllocator>
1003 vector(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
1004 , typename container_detail::enable_if_c
1005 < container_detail::is_version<OtherAllocator, 0>::value>::type * = 0
1006 )
1007 : m_holder(boost::move(x.m_holder))
1008 {}
1009
1010 #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1011
1012 //! <b>Effects</b>: Copy constructs a vector using the specified allocator.
1013 //!
1014 //! <b>Postcondition</b>: x == *this.
1015 //!
1016 //! <b>Throws</b>: If allocation
1017 //! throws or T's copy constructor throws.
1018 //!
1019 //! <b>Complexity</b>: Linear to the elements x contains.
1020 vector(const vector &x, const allocator_type &a)
1021 : m_holder(container_detail::uninitialized_size, a, x.size())
1022 {
1023 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
1024 this->num_alloc += x.size() != 0;
1025 #endif
1026 ::boost::container::uninitialized_copy_alloc_n_source
1027 ( this->m_holder.alloc(), x.priv_raw_begin()
1028 , x.size(), this->priv_raw_begin());
1029 }
1030
1031 //! <b>Effects</b>: Move constructor using the specified allocator.
1032 //! Moves x's resources to *this if a == allocator_type().
1033 //! Otherwise copies values from x to *this.
1034 //!
1035 //! <b>Throws</b>: If allocation or T's copy constructor throws.
1036 //!
1037 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
1038 vector(BOOST_RV_REF(vector) x, const allocator_type &a)
1039 : m_holder( container_detail::uninitialized_size, a
1040 , is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true) ? 0 : x.size()
1041 )
1042 {
1043 if(is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true)){
1044 this->m_holder.steal_resources(x.m_holder);
1045 }
1046 else{
1047 const size_type n = x.size();
1048 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
1049 this->num_alloc += n != 0;
1050 #endif
1051 ::boost::container::uninitialized_move_alloc_n_source
1052 ( this->m_holder.alloc(), x.priv_raw_begin()
1053 , n, this->priv_raw_begin());
1054 }
1055 }
1056
1057 //! <b>Effects</b>: Destroys the vector. All stored values are destroyed
1058 //! and used memory is deallocated.
1059 //!
1060 //! <b>Throws</b>: Nothing.
1061 //!
1062 //! <b>Complexity</b>: Linear to the number of elements.
1063 ~vector() BOOST_NOEXCEPT_OR_NOTHROW
1064 {
1065 boost::container::destroy_alloc_n
1066 (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size);
1067 //vector_alloc_holder deallocates the data
1068 }
1069
1070 //! <b>Effects</b>: Makes *this contain the same elements as x.
1071 //!
1072 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
1073 //! of each of x's elements.
1074 //!
1075 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws.
1076 //!
1077 //! <b>Complexity</b>: Linear to the number of elements in x.
1078 BOOST_CONTAINER_FORCEINLINE vector& operator=(BOOST_COPY_ASSIGN_REF(vector) x)
1079 {
1080 if (&x != this){
1081 this->priv_copy_assign(x);
1082 }
1083 return *this;
1084 }
1085
1086 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1087 //! <b>Effects</b>: Make *this container contains elements from il.
1088 //!
1089 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
1090 BOOST_CONTAINER_FORCEINLINE vector& operator=(std::initializer_list<value_type> il)
1091 {
1092 this->assign(il.begin(), il.end());
1093 return *this;
1094 }
1095 #endif
1096
1097 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
1098 //!
1099 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
1100 //! before the function.
1101 //!
1102 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
1103 //! is false and (allocation throws or value_type's move constructor throws)
1104 //!
1105 //! <b>Complexity</b>: Constant if allocator_traits_type::
1106 //! propagate_on_container_move_assignment is true or
1107 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
1108 BOOST_CONTAINER_FORCEINLINE vector& operator=(BOOST_RV_REF(vector) x)
1109 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
1110 || allocator_traits_type::is_always_equal::value)
1111 {
1112 BOOST_ASSERT(&x != this);
1113 this->priv_move_assign(boost::move(x));
1114 return *this;
1115 }
1116
1117 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1118
1119 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
1120 //!
1121 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
1122 //! before the function.
1123 //!
1124 //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws
1125 //!
1126 //! <b>Complexity</b>: Linear.
1127 //!
1128 //! <b>Note</b>: Non-standard extension to support static_vector
1129 template<class OtherAllocator>
1130 BOOST_CONTAINER_FORCEINLINE typename container_detail::enable_if_and
1131 < vector&
1132 , container_detail::is_version<OtherAllocator, 0>
1133 , container_detail::is_different<OtherAllocator, allocator_type>
1134 >::type
1135 operator=(BOOST_RV_REF_BEG vector<value_type, OtherAllocator> BOOST_RV_REF_END x)
1136 {
1137 this->priv_move_assign(boost::move(x));
1138 return *this;
1139 }
1140
1141 //! <b>Effects</b>: Copy assignment. All x's values are copied to *this.
1142 //!
1143 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
1144 //! before the function.
1145 //!
1146 //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws
1147 //!
1148 //! <b>Complexity</b>: Linear.
1149 //!
1150 //! <b>Note</b>: Non-standard extension to support static_vector
1151 template<class OtherAllocator>
1152 BOOST_CONTAINER_FORCEINLINE typename container_detail::enable_if_and
1153 < vector&
1154 , container_detail::is_version<OtherAllocator, 0>
1155 , container_detail::is_different<OtherAllocator, allocator_type>
1156 >::type
1157 operator=(const vector<value_type, OtherAllocator> &x)
1158 {
1159 this->priv_copy_assign(x);
1160 return *this;
1161 }
1162
1163 #endif
1164
1165 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
1166 //!
1167 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or
1168 //! T's constructor/assignment from dereferencing InpIt throws.
1169 //!
1170 //! <b>Complexity</b>: Linear to n.
1171 template <class InIt>
1172 void assign(InIt first, InIt last
1173 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or
1174 < void
1175 BOOST_MOVE_I container_detail::is_convertible<InIt BOOST_MOVE_I size_type>
1176 BOOST_MOVE_I container_detail::and_
1177 < container_detail::is_different<alloc_version BOOST_MOVE_I version_0>
1178 BOOST_MOVE_I container_detail::is_not_input_iterator<InIt>
1179 >
1180 >::type * = 0)
1181 )
1182 {
1183 //Overwrite all elements we can from [first, last)
1184 iterator cur = this->begin();
1185 const iterator end_it = this->end();
1186 for ( ; first != last && cur != end_it; ++cur, ++first){
1187 *cur = *first;
1188 }
1189
1190 if (first == last){
1191 //There are no more elements in the sequence, erase remaining
1192 T* const end_pos = this->priv_raw_end();
1193 const size_type n = static_cast<size_type>(end_pos - boost::movelib::iterator_to_raw_pointer(cur));
1194 this->priv_destroy_last_n(n);
1195 }
1196 else{
1197 //There are more elements in the range, insert the remaining ones
1198 this->insert(this->cend(), first, last);
1199 }
1200 }
1201
1202 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1203 //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this.
1204 //!
1205 //! <b>Throws</b>: If memory allocation throws or
1206 //! T's constructor from dereferencing iniializer_list iterator throws.
1207 //!
1208 BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<T> il)
1209 {
1210 this->assign(il.begin(), il.end());
1211 }
1212 #endif
1213
1214 //! <b>Effects</b>: Assigns the the range [first, last) to *this.
1215 //!
1216 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or
1217 //! T's constructor/assignment from dereferencing InpIt throws.
1218 //!
1219 //! <b>Complexity</b>: Linear to n.
1220 template <class FwdIt>
1221 void assign(FwdIt first, FwdIt last
1222 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or
1223 < void
1224 BOOST_MOVE_I container_detail::is_same<alloc_version BOOST_MOVE_I version_0>
1225 BOOST_MOVE_I container_detail::is_convertible<FwdIt BOOST_MOVE_I size_type>
1226 BOOST_MOVE_I container_detail::is_input_iterator<FwdIt>
1227 >::type * = 0)
1228 )
1229 {
1230 //For Fwd iterators the standard only requires EmplaceConstructible and assignable from *first
1231 //so we can't do any backwards allocation
1232 const size_type input_sz = static_cast<size_type>(boost::container::iterator_distance(first, last));
1233 const size_type old_capacity = this->capacity();
1234 if(input_sz > old_capacity){ //If input range is too big, we need to reallocate
1235 size_type real_cap = 0;
1236 pointer reuse(this->m_holder.start());
1237 pointer const ret(this->m_holder.allocation_command(allocate_new|expand_fwd, input_sz, real_cap = input_sz, reuse));
1238 if(!reuse){ //New allocation, just emplace new values
1239 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
1240 ++this->num_alloc;
1241 #endif
1242 pointer const old_p = this->m_holder.start();
1243 if(old_p){
1244 this->priv_destroy_all();
1245 this->m_holder.alloc().deallocate(old_p, old_capacity);
1246 }
1247 this->m_holder.start(ret);
1248 this->m_holder.capacity(real_cap);
1249 this->m_holder.m_size = 0;
1250 this->priv_uninitialized_construct_at_end(first, last);
1251 return;
1252 }
1253 else{
1254 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
1255 ++this->num_expand_fwd;
1256 #endif
1257 this->m_holder.capacity(real_cap);
1258 //Forward expansion, use assignment + back deletion/construction that comes later
1259 }
1260 }
1261 //Overwrite all elements we can from [first, last)
1262 iterator cur = this->begin();
1263 const iterator end_it = this->end();
1264 for ( ; first != last && cur != end_it; ++cur, ++first){
1265 *cur = *first;
1266 }
1267
1268 if (first == last){
1269 //There are no more elements in the sequence, erase remaining
1270 this->priv_destroy_last_n(this->size() - input_sz);
1271 }
1272 else{
1273 //Uninitialized construct at end the remaining range
1274 this->priv_uninitialized_construct_at_end(first, last);
1275 }
1276 }
1277
1278 //! <b>Effects</b>: Assigns the n copies of val to *this.
1279 //!
1280 //! <b>Throws</b>: If memory allocation throws or
1281 //! T's copy/move constructor/assignment throws.
1282 //!
1283 //! <b>Complexity</b>: Linear to n.
1284 BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const value_type& val)
1285 { this->assign(cvalue_iterator(val, n), cvalue_iterator()); }
1286
1287 //! <b>Effects</b>: Returns a copy of the internal allocator.
1288 //!
1289 //! <b>Throws</b>: If allocator's copy constructor throws.
1290 //!
1291 //! <b>Complexity</b>: Constant.
1292 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
1293 { return this->m_holder.alloc(); }
1294
1295 //! <b>Effects</b>: Returns a reference to the internal allocator.
1296 //!
1297 //! <b>Throws</b>: Nothing
1298 //!
1299 //! <b>Complexity</b>: Constant.
1300 //!
1301 //! <b>Note</b>: Non-standard extension.
1302 BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
1303 { return this->m_holder.alloc(); }
1304
1305 //! <b>Effects</b>: Returns a reference to the internal allocator.
1306 //!
1307 //! <b>Throws</b>: Nothing
1308 //!
1309 //! <b>Complexity</b>: Constant.
1310 //!
1311 //! <b>Note</b>: Non-standard extension.
1312 BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
1313 { return this->m_holder.alloc(); }
1314
1315 //////////////////////////////////////////////
1316 //
1317 // iterators
1318 //
1319 //////////////////////////////////////////////
1320
1321 //! <b>Effects</b>: Returns an iterator to the first element contained in the vector.
1322 //!
1323 //! <b>Throws</b>: Nothing.
1324 //!
1325 //! <b>Complexity</b>: Constant.
1326 BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
1327 { return iterator(this->m_holder.start()); }
1328
1329 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector.
1330 //!
1331 //! <b>Throws</b>: Nothing.
1332 //!
1333 //! <b>Complexity</b>: Constant.
1334 BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
1335 { return const_iterator(this->m_holder.start()); }
1336
1337 //! <b>Effects</b>: Returns an iterator to the end of the vector.
1338 //!
1339 //! <b>Throws</b>: Nothing.
1340 //!
1341 //! <b>Complexity</b>: Constant.
1342 BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW
1343 { return iterator(this->m_holder.start() + this->m_holder.m_size); }
1344
1345 //! <b>Effects</b>: Returns a const_iterator to the end of the vector.
1346 //!
1347 //! <b>Throws</b>: Nothing.
1348 //!
1349 //! <b>Complexity</b>: Constant.
1350 BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
1351 { return this->cend(); }
1352
1353 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1354 //! of the reversed vector.
1355 //!
1356 //! <b>Throws</b>: Nothing.
1357 //!
1358 //! <b>Complexity</b>: Constant.
1359 BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
1360 { return reverse_iterator(this->end()); }
1361
1362 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1363 //! of the reversed vector.
1364 //!
1365 //! <b>Throws</b>: Nothing.
1366 //!
1367 //! <b>Complexity</b>: Constant.
1368 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1369 { return this->crbegin(); }
1370
1371 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1372 //! of the reversed vector.
1373 //!
1374 //! <b>Throws</b>: Nothing.
1375 //!
1376 //! <b>Complexity</b>: Constant.
1377 BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1378 { return reverse_iterator(this->begin()); }
1379
1380 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1381 //! of the reversed vector.
1382 //!
1383 //! <b>Throws</b>: Nothing.
1384 //!
1385 //! <b>Complexity</b>: Constant.
1386 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1387 { return this->crend(); }
1388
1389 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector.
1390 //!
1391 //! <b>Throws</b>: Nothing.
1392 //!
1393 //! <b>Complexity</b>: Constant.
1394 BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1395 { return const_iterator(this->m_holder.start()); }
1396
1397 //! <b>Effects</b>: Returns a const_iterator to the end of the vector.
1398 //!
1399 //! <b>Throws</b>: Nothing.
1400 //!
1401 //! <b>Complexity</b>: Constant.
1402 BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1403 { return const_iterator(this->m_holder.start() + this->m_holder.m_size); }
1404
1405 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1406 //! of the reversed vector.
1407 //!
1408 //! <b>Throws</b>: Nothing.
1409 //!
1410 //! <b>Complexity</b>: Constant.
1411 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1412 { return const_reverse_iterator(this->end());}
1413
1414 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1415 //! of the reversed vector.
1416 //!
1417 //! <b>Throws</b>: Nothing.
1418 //!
1419 //! <b>Complexity</b>: Constant.
1420 BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
1421 { return const_reverse_iterator(this->begin()); }
1422
1423 //////////////////////////////////////////////
1424 //
1425 // capacity
1426 //
1427 //////////////////////////////////////////////
1428
1429 //! <b>Effects</b>: Returns true if the vector contains no elements.
1430 //!
1431 //! <b>Throws</b>: Nothing.
1432 //!
1433 //! <b>Complexity</b>: Constant.
1434 BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1435 { return !this->m_holder.m_size; }
1436
1437 //! <b>Effects</b>: Returns the number of the elements contained in the vector.
1438 //!
1439 //! <b>Throws</b>: Nothing.
1440 //!
1441 //! <b>Complexity</b>: Constant.
1442 BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1443 { return this->m_holder.m_size; }
1444
1445 //! <b>Effects</b>: Returns the largest possible size of the vector.
1446 //!
1447 //! <b>Throws</b>: Nothing.
1448 //!
1449 //! <b>Complexity</b>: Constant.
1450 BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1451 { return allocator_traits_type::max_size(this->m_holder.alloc()); }
1452
1453 //! <b>Effects</b>: Inserts or erases elements at the end such that
1454 //! the size becomes n. New elements are value initialized.
1455 //!
1456 //! <b>Throws</b>: If memory allocation throws, or T's copy/move or value initialization throws.
1457 //!
1458 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1459 void resize(size_type new_size)
1460 { this->priv_resize(new_size, value_init); }
1461
1462 //! <b>Effects</b>: Inserts or erases elements at the end such that
1463 //! the size becomes n. New elements are default initialized.
1464 //!
1465 //! <b>Throws</b>: If memory allocation throws, or T's copy/move or default initialization throws.
1466 //!
1467 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1468 //!
1469 //! <b>Note</b>: Non-standard extension
1470 void resize(size_type new_size, default_init_t)
1471 { this->priv_resize(new_size, default_init); }
1472
1473 //! <b>Effects</b>: Inserts or erases elements at the end such that
1474 //! the size becomes n. New elements are copy constructed from x.
1475 //!
1476 //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws.
1477 //!
1478 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1479 void resize(size_type new_size, const T& x)
1480 { this->priv_resize(new_size, x); }
1481
1482 //! <b>Effects</b>: Number of elements for which memory has been allocated.
1483 //! capacity() is always greater than or equal to size().
1484 //!
1485 //! <b>Throws</b>: Nothing.
1486 //!
1487 //! <b>Complexity</b>: Constant.
1488 BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
1489 { return this->m_holder.capacity(); }
1490
1491 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
1492 //! effect. Otherwise, it is a request for allocation of additional memory.
1493 //! If the request is successful, then capacity() is greater than or equal to
1494 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
1495 //!
1496 //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws.
1497 BOOST_CONTAINER_FORCEINLINE void reserve(size_type new_cap)
1498 {
1499 if (this->capacity() < new_cap){
1500 this->priv_reserve_no_capacity(new_cap, alloc_version());
1501 }
1502 }
1503
1504 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1505 //! with previous allocations. The size of the vector is unchanged
1506 //!
1507 //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws.
1508 //!
1509 //! <b>Complexity</b>: Linear to size().
1510 BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
1511 { this->priv_shrink_to_fit(alloc_version()); }
1512
1513 //////////////////////////////////////////////
1514 //
1515 // element access
1516 //
1517 //////////////////////////////////////////////
1518
1519 //! <b>Requires</b>: !empty()
1520 //!
1521 //! <b>Effects</b>: Returns a reference to the first
1522 //! element of the container.
1523 //!
1524 //! <b>Throws</b>: Nothing.
1525 //!
1526 //! <b>Complexity</b>: Constant.
1527 reference front() BOOST_NOEXCEPT_OR_NOTHROW
1528 {
1529 BOOST_ASSERT(!this->empty());
1530 return *this->m_holder.start();
1531 }
1532
1533 //! <b>Requires</b>: !empty()
1534 //!
1535 //! <b>Effects</b>: Returns a const reference to the first
1536 //! element of the container.
1537 //!
1538 //! <b>Throws</b>: Nothing.
1539 //!
1540 //! <b>Complexity</b>: Constant.
1541 const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1542 {
1543 BOOST_ASSERT(!this->empty());
1544 return *this->m_holder.start();
1545 }
1546
1547 //! <b>Requires</b>: !empty()
1548 //!
1549 //! <b>Effects</b>: Returns a reference to the last
1550 //! element of the container.
1551 //!
1552 //! <b>Throws</b>: Nothing.
1553 //!
1554 //! <b>Complexity</b>: Constant.
1555 reference back() BOOST_NOEXCEPT_OR_NOTHROW
1556 {
1557 BOOST_ASSERT(!this->empty());
1558 return this->m_holder.start()[this->m_holder.m_size - 1];
1559 }
1560
1561 //! <b>Requires</b>: !empty()
1562 //!
1563 //! <b>Effects</b>: Returns a const reference to the last
1564 //! element of the container.
1565 //!
1566 //! <b>Throws</b>: Nothing.
1567 //!
1568 //! <b>Complexity</b>: Constant.
1569 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1570 {
1571 BOOST_ASSERT(!this->empty());
1572 return this->m_holder.start()[this->m_holder.m_size - 1];
1573 }
1574
1575 //! <b>Requires</b>: size() > n.
1576 //!
1577 //! <b>Effects</b>: Returns a reference to the nth element
1578 //! from the beginning of the container.
1579 //!
1580 //! <b>Throws</b>: Nothing.
1581 //!
1582 //! <b>Complexity</b>: Constant.
1583 reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1584 {
1585 BOOST_ASSERT(this->m_holder.m_size > n);
1586 return this->m_holder.start()[n];
1587 }
1588
1589 //! <b>Requires</b>: size() > n.
1590 //!
1591 //! <b>Effects</b>: Returns a const reference to the nth element
1592 //! from the beginning of the container.
1593 //!
1594 //! <b>Throws</b>: Nothing.
1595 //!
1596 //! <b>Complexity</b>: Constant.
1597 const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1598 {
1599 BOOST_ASSERT(this->m_holder.m_size > n);
1600 return this->m_holder.start()[n];
1601 }
1602
1603 //! <b>Requires</b>: size() >= n.
1604 //!
1605 //! <b>Effects</b>: Returns an iterator to the nth element
1606 //! from the beginning of the container. Returns end()
1607 //! if n == size().
1608 //!
1609 //! <b>Throws</b>: Nothing.
1610 //!
1611 //! <b>Complexity</b>: Constant.
1612 //!
1613 //! <b>Note</b>: Non-standard extension
1614 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1615 {
1616 BOOST_ASSERT(this->m_holder.m_size >= n);
1617 return iterator(this->m_holder.start()+n);
1618 }
1619
1620 //! <b>Requires</b>: size() >= n.
1621 //!
1622 //! <b>Effects</b>: Returns a const_iterator to the nth element
1623 //! from the beginning of the container. Returns end()
1624 //! if n == size().
1625 //!
1626 //! <b>Throws</b>: Nothing.
1627 //!
1628 //! <b>Complexity</b>: Constant.
1629 //!
1630 //! <b>Note</b>: Non-standard extension
1631 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1632 {
1633 BOOST_ASSERT(this->m_holder.m_size >= n);
1634 return const_iterator(this->m_holder.start()+n);
1635 }
1636
1637 //! <b>Requires</b>: begin() <= p <= end().
1638 //!
1639 //! <b>Effects</b>: Returns the index of the element pointed by p
1640 //! and size() if p == end().
1641 //!
1642 //! <b>Throws</b>: Nothing.
1643 //!
1644 //! <b>Complexity</b>: Constant.
1645 //!
1646 //! <b>Note</b>: Non-standard extension
1647 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1648 {
1649 //Range check assert done in priv_index_of
1650 return this->priv_index_of(vector_iterator_get_ptr(p));
1651 }
1652
1653 //! <b>Requires</b>: begin() <= p <= end().
1654 //!
1655 //! <b>Effects</b>: Returns the index of the element pointed by p
1656 //! and size() if p == end().
1657 //!
1658 //! <b>Throws</b>: Nothing.
1659 //!
1660 //! <b>Complexity</b>: Constant.
1661 //!
1662 //! <b>Note</b>: Non-standard extension
1663 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1664 {
1665 //Range check assert done in priv_index_of
1666 return this->priv_index_of(vector_iterator_get_ptr(p));
1667 }
1668
1669 //! <b>Requires</b>: size() > n.
1670 //!
1671 //! <b>Effects</b>: Returns a reference to the nth element
1672 //! from the beginning of the container.
1673 //!
1674 //! <b>Throws</b>: std::range_error if n >= size()
1675 //!
1676 //! <b>Complexity</b>: Constant.
1677 reference at(size_type n)
1678 {
1679 this->priv_throw_if_out_of_range(n);
1680 return this->m_holder.start()[n];
1681 }
1682
1683 //! <b>Requires</b>: size() > n.
1684 //!
1685 //! <b>Effects</b>: Returns a const reference to the nth element
1686 //! from the beginning of the container.
1687 //!
1688 //! <b>Throws</b>: std::range_error if n >= size()
1689 //!
1690 //! <b>Complexity</b>: Constant.
1691 const_reference at(size_type n) const
1692 {
1693 this->priv_throw_if_out_of_range(n);
1694 return this->m_holder.start()[n];
1695 }
1696
1697 //////////////////////////////////////////////
1698 //
1699 // data access
1700 //
1701 //////////////////////////////////////////////
1702
1703 //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range.
1704 //! For a non-empty vector, data() == &front().
1705 //!
1706 //! <b>Throws</b>: Nothing.
1707 //!
1708 //! <b>Complexity</b>: Constant.
1709 T* data() BOOST_NOEXCEPT_OR_NOTHROW
1710 { return this->priv_raw_begin(); }
1711
1712 //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range.
1713 //! For a non-empty vector, data() == &front().
1714 //!
1715 //! <b>Throws</b>: Nothing.
1716 //!
1717 //! <b>Complexity</b>: Constant.
1718 const T * data() const BOOST_NOEXCEPT_OR_NOTHROW
1719 { return this->priv_raw_begin(); }
1720
1721 //////////////////////////////////////////////
1722 //
1723 // modifiers
1724 //
1725 //////////////////////////////////////////////
1726
1727 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1728 //! <b>Effects</b>: Inserts an object of type T constructed with
1729 //! std::forward<Args>(args)... in the end of the vector.
1730 //!
1731 //! <b>Returns</b>: A reference to the created object.
1732 //!
1733 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or
1734 //! T's copy/move constructor throws.
1735 //!
1736 //! <b>Complexity</b>: Amortized constant time.
1737 template<class ...Args>
1738 BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_FWD_REF(Args)...args)
1739 {
1740 if (BOOST_LIKELY(this->room_enough())){
1741 //There is more memory, just construct a new object at the end
1742 T* const p = this->priv_raw_end();
1743 allocator_traits_type::construct(this->m_holder.alloc(), p, ::boost::forward<Args>(args)...);
1744 ++this->m_holder.m_size;
1745 return *p;
1746 }
1747 else{
1748 typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type;
1749 return *this->priv_forward_range_insert_no_capacity
1750 (this->back_ptr(), 1, type(::boost::forward<Args>(args)...), alloc_version());
1751 }
1752 }
1753
1754 //! <b>Effects</b>: Inserts an object of type T constructed with
1755 //! std::forward<Args>(args)... in the end of the vector.
1756 //!
1757 //! <b>Throws</b>: If the in-place constructor throws.
1758 //!
1759 //! <b>Complexity</b>: Constant time.
1760 //!
1761 //! <b>Note</b>: Non-standard extension.
1762 template<class ...Args>
1763 BOOST_CONTAINER_FORCEINLINE bool stable_emplace_back(BOOST_FWD_REF(Args)...args)
1764 {
1765 const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));
1766 if (BOOST_LIKELY(is_room_enough)){
1767 //There is more memory, just construct a new object at the end
1768 allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<Args>(args)...);
1769 ++this->m_holder.m_size;
1770 }
1771 return is_room_enough;
1772 }
1773
1774 //! <b>Requires</b>: position must be a valid iterator of *this.
1775 //!
1776 //! <b>Effects</b>: Inserts an object of type T constructed with
1777 //! std::forward<Args>(args)... before position
1778 //!
1779 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or
1780 //! T's copy/move constructor/assignment throws.
1781 //!
1782 //! <b>Complexity</b>: If position is end(), amortized constant time
1783 //! Linear time otherwise.
1784 template<class ...Args>
1785 iterator emplace(const_iterator position, BOOST_FWD_REF(Args) ...args)
1786 {
1787 BOOST_ASSERT(this->priv_in_range_or_end(position));
1788 //Just call more general insert(pos, size, value) and return iterator
1789 typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type;
1790 return this->priv_forward_range_insert( vector_iterator_get_ptr(position), 1
1791 , type(::boost::forward<Args>(args)...));
1792 }
1793
1794 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1795
1796 #define BOOST_CONTAINER_VECTOR_EMPLACE_CODE(N) \
1797 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1798 BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_MOVE_UREF##N)\
1799 {\
1800 if (BOOST_LIKELY(this->room_enough())){\
1801 T* const p = this->priv_raw_end();\
1802 allocator_traits_type::construct (this->m_holder.alloc()\
1803 , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1804 ++this->m_holder.m_size;\
1805 return *p;\
1806 }\
1807 else{\
1808 typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1809 return *this->priv_forward_range_insert_no_capacity\
1810 ( this->back_ptr(), 1, type(BOOST_MOVE_FWD##N), alloc_version());\
1811 }\
1812 }\
1813 \
1814 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1815 BOOST_CONTAINER_FORCEINLINE bool stable_emplace_back(BOOST_MOVE_UREF##N)\
1816 {\
1817 const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));\
1818 if (BOOST_LIKELY(is_room_enough)){\
1819 allocator_traits_type::construct (this->m_holder.alloc()\
1820 , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1821 ++this->m_holder.m_size;\
1822 }\
1823 return is_room_enough;\
1824 }\
1825 \
1826 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1827 iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1828 {\
1829 BOOST_ASSERT(this->priv_in_range_or_end(pos));\
1830 typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\
1831 return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), 1, type(BOOST_MOVE_FWD##N));\
1832 }\
1833 //
1834 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_VECTOR_EMPLACE_CODE)
1835 #undef BOOST_CONTAINER_VECTOR_EMPLACE_CODE
1836
1837 #endif
1838
1839 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1840 //! <b>Effects</b>: Inserts a copy of x at the end of the vector.
1841 //!
1842 //! <b>Throws</b>: If memory allocation throws or
1843 //! T's copy/move constructor throws.
1844 //!
1845 //! <b>Complexity</b>: Amortized constant time.
1846 void push_back(const T &x);
1847
1848 //! <b>Effects</b>: Constructs a new element in the end of the vector
1849 //! and moves the resources of x to this new element.
1850 //!
1851 //! <b>Throws</b>: If memory allocation throws or
1852 //! T's copy/move constructor throws.
1853 //!
1854 //! <b>Complexity</b>: Amortized constant time.
1855 void push_back(T &&x);
1856 #else
1857 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1858 #endif
1859
1860 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1861 //! <b>Requires</b>: position must be a valid iterator of *this.
1862 //!
1863 //! <b>Effects</b>: Insert a copy of x before position.
1864 //!
1865 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws.
1866 //!
1867 //! <b>Complexity</b>: If position is end(), amortized constant time
1868 //! Linear time otherwise.
1869 iterator insert(const_iterator position, const T &x);
1870
1871 //! <b>Requires</b>: position must be a valid iterator of *this.
1872 //!
1873 //! <b>Effects</b>: Insert a new element before position with x's resources.
1874 //!
1875 //! <b>Throws</b>: If memory allocation throws.
1876 //!
1877 //! <b>Complexity</b>: If position is end(), amortized constant time
1878 //! Linear time otherwise.
1879 iterator insert(const_iterator position, T &&x);
1880 #else
1881 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1882 #endif
1883
1884 //! <b>Requires</b>: p must be a valid iterator of *this.
1885 //!
1886 //! <b>Effects</b>: Insert n copies of x before pos.
1887 //!
1888 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
1889 //!
1890 //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor throws.
1891 //!
1892 //! <b>Complexity</b>: Linear to n.
1893 iterator insert(const_iterator p, size_type n, const T& x)
1894 {
1895 BOOST_ASSERT(this->priv_in_range_or_end(p));
1896 container_detail::insert_n_copies_proxy<Allocator, T*> proxy(x);
1897 return this->priv_forward_range_insert(vector_iterator_get_ptr(p), n, proxy);
1898 }
1899
1900 //! <b>Requires</b>: p must be a valid iterator of *this.
1901 //!
1902 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1903 //!
1904 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
1905 //!
1906 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1907 //! dereferenced InpIt throws or T's copy/move constructor/assignment throws.
1908 //!
1909 //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last).
1910 template <class InIt>
1911 iterator insert(const_iterator pos, InIt first, InIt last
1912 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1913 , typename container_detail::disable_if_or
1914 < void
1915 , container_detail::is_convertible<InIt, size_type>
1916 , container_detail::is_not_input_iterator<InIt>
1917 >::type * = 0
1918 #endif
1919 )
1920 {
1921 BOOST_ASSERT(this->priv_in_range_or_end(pos));
1922 const size_type n_pos = pos - this->cbegin();
1923 iterator it(vector_iterator_get_ptr(pos));
1924 for(;first != last; ++first){
1925 it = this->emplace(it, *first);
1926 ++it;
1927 }
1928 return iterator(this->m_holder.start() + n_pos);
1929 }
1930
1931 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1932 template <class FwdIt>
1933 iterator insert(const_iterator pos, FwdIt first, FwdIt last
1934 , typename container_detail::disable_if_or
1935 < void
1936 , container_detail::is_convertible<FwdIt, size_type>
1937 , container_detail::is_input_iterator<FwdIt>
1938 >::type * = 0
1939 )
1940 {
1941 BOOST_ASSERT(this->priv_in_range_or_end(pos));
1942 container_detail::insert_range_proxy<Allocator, FwdIt, T*> proxy(first);
1943 return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), boost::container::iterator_distance(first, last), proxy);
1944 }
1945 #endif
1946
1947 //! <b>Requires</b>: p must be a valid iterator of *this. num, must
1948 //! be equal to boost::container::iterator_distance(first, last)
1949 //!
1950 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1951 //!
1952 //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last.
1953 //!
1954 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1955 //! dereferenced InpIt throws or T's copy/move constructor/assignment throws.
1956 //!
1957 //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last).
1958 //!
1959 //! <b>Note</b>: This function avoids a linear operation to calculate boost::container::iterator_distance[first, last)
1960 //! for forward and bidirectional iterators, and a one by one insertion for input iterators. This is a
1961 //! a non-standard extension.
1962 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1963 template <class InIt>
1964 iterator insert(const_iterator pos, size_type num, InIt first, InIt last)
1965 {
1966 BOOST_ASSERT(this->priv_in_range_or_end(pos));
1967 BOOST_ASSERT(container_detail::is_input_iterator<InIt>::value ||
1968 num == static_cast<size_type>(boost::container::iterator_distance(first, last)));
1969 (void)last;
1970 container_detail::insert_range_proxy<Allocator, InIt, T*> proxy(first);
1971 return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), num, proxy);
1972 }
1973 #endif
1974
1975 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1976 //! <b>Requires</b>: position must be a valid iterator of *this.
1977 //!
1978 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before position.
1979 //!
1980 //! <b>Returns</b>: an iterator to the first inserted element or position if first == last.
1981 //!
1982 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
1983 iterator insert(const_iterator position, std::initializer_list<value_type> il)
1984 {
1985 //Assertion done in insert()
1986 return this->insert(position, il.begin(), il.end());
1987 }
1988 #endif
1989
1990 //! <b>Effects</b>: Removes the last element from the container.
1991 //!
1992 //! <b>Throws</b>: Nothing.
1993 //!
1994 //! <b>Complexity</b>: Constant time.
1995 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1996 {
1997 BOOST_ASSERT(!this->empty());
1998 //Destroy last element
1999 this->priv_destroy_last();
2000 }
2001
2002 //! <b>Effects</b>: Erases the element at position pos.
2003 //!
2004 //! <b>Throws</b>: Nothing.
2005 //!
2006 //! <b>Complexity</b>: Linear to the elements between pos and the
2007 //! last element. Constant if pos is the last element.
2008 iterator erase(const_iterator position)
2009 {
2010 BOOST_ASSERT(this->priv_in_range(position));
2011 const pointer p = vector_iterator_get_ptr(position);
2012 T *const pos_ptr = boost::movelib::to_raw_pointer(p);
2013 T *const beg_ptr = this->priv_raw_begin();
2014 T *const new_end_ptr = ::boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr);
2015 //Move elements forward and destroy last
2016 this->priv_destroy_last(pos_ptr == new_end_ptr);
2017 return iterator(p);
2018 }
2019
2020 //! <b>Effects</b>: Erases the elements pointed by [first, last).
2021 //!
2022 //! <b>Throws</b>: Nothing.
2023 //!
2024 //! <b>Complexity</b>: Linear to the distance between first and last
2025 //! plus linear to the elements between pos and the last element.
2026 iterator erase(const_iterator first, const_iterator last)
2027 {
2028 BOOST_ASSERT(first == last ||
2029 (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last)));
2030 if (first != last){
2031 T* const old_end_ptr = this->priv_raw_end();
2032 T* const first_ptr = boost::movelib::to_raw_pointer(vector_iterator_get_ptr(first));
2033 T* const last_ptr = boost::movelib::to_raw_pointer(vector_iterator_get_ptr(last));
2034 T* const ptr = boost::movelib::to_raw_pointer(boost::container::move(last_ptr, old_end_ptr, first_ptr));
2035 this->priv_destroy_last_n(old_end_ptr - ptr);
2036 }
2037 return iterator(vector_iterator_get_ptr(first));
2038 }
2039
2040 //! <b>Effects</b>: Swaps the contents of *this and x.
2041 //!
2042 //! <b>Throws</b>: Nothing.
2043 //!
2044 //! <b>Complexity</b>: Constant.
2045 void swap(vector& x)
2046 BOOST_NOEXCEPT_IF( ((allocator_traits_type::propagate_on_container_swap::value
2047 || allocator_traits_type::is_always_equal::value) &&
2048 !container_detail::is_version<Allocator, 0>::value))
2049 {
2050 this->priv_swap(x, container_detail::bool_<container_detail::is_version<Allocator, 0>::value>());
2051 }
2052
2053 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2054
2055 //! <b>Effects</b>: Swaps the contents of *this and x.
2056 //!
2057 //! <b>Throws</b>: Nothing.
2058 //!
2059 //! <b>Complexity</b>: Linear
2060 //!
2061 //! <b>Note</b>: Non-standard extension to support static_vector
2062 template<class OtherAllocator>
2063 void swap(vector<T, OtherAllocator> & x
2064 , typename container_detail::enable_if_and
2065 < void
2066 , container_detail::is_version<OtherAllocator, 0>
2067 , container_detail::is_different<OtherAllocator, allocator_type>
2068 >::type * = 0
2069 )
2070 { this->m_holder.deep_swap(x.m_holder); }
2071
2072 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2073
2074 //! <b>Effects</b>: Erases all the elements of the vector.
2075 //!
2076 //! <b>Throws</b>: Nothing.
2077 //!
2078 //! <b>Complexity</b>: Linear to the number of elements in the container.
2079 void clear() BOOST_NOEXCEPT_OR_NOTHROW
2080 { this->priv_destroy_all(); }
2081
2082 //! <b>Effects</b>: Returns true if x and y are equal
2083 //!
2084 //! <b>Complexity</b>: Linear to the number of elements in the container.
2085 friend bool operator==(const vector& x, const vector& y)
2086 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
2087
2088 //! <b>Effects</b>: Returns true if x and y are unequal
2089 //!
2090 //! <b>Complexity</b>: Linear to the number of elements in the container.
2091 friend bool operator!=(const vector& x, const vector& y)
2092 { return !(x == y); }
2093
2094 //! <b>Effects</b>: Returns true if x is less than y
2095 //!
2096 //! <b>Complexity</b>: Linear to the number of elements in the container.
2097 friend bool operator<(const vector& x, const vector& y)
2098 {
2099 const_iterator first1(x.cbegin()), first2(y.cbegin());
2100 const const_iterator last1(x.cend()), last2(y.cend());
2101 for ( ; (first1 != last1) && (first2 != last2); ++first1, ++first2 ) {
2102 if (*first1 < *first2) return true;
2103 if (*first2 < *first1) return false;
2104 }
2105 return (first1 == last1) && (first2 != last2);
2106 }
2107
2108 //! <b>Effects</b>: Returns true if x is greater than y
2109 //!
2110 //! <b>Complexity</b>: Linear to the number of elements in the container.
2111 friend bool operator>(const vector& x, const vector& y)
2112 { return y < x; }
2113
2114 //! <b>Effects</b>: Returns true if x is equal or less than y
2115 //!
2116 //! <b>Complexity</b>: Linear to the number of elements in the container.
2117 friend bool operator<=(const vector& x, const vector& y)
2118 { return !(y < x); }
2119
2120 //! <b>Effects</b>: Returns true if x is equal or greater than y
2121 //!
2122 //! <b>Complexity</b>: Linear to the number of elements in the container.
2123 friend bool operator>=(const vector& x, const vector& y)
2124 { return !(x < y); }
2125
2126 //! <b>Effects</b>: x.swap(y)
2127 //!
2128 //! <b>Complexity</b>: Constant.
2129 friend void swap(vector& x, vector& y)
2130 { x.swap(y); }
2131
2132 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2133 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
2134 //! effect. Otherwise, it is a request for allocation of additional memory
2135 //! (memory expansion) that will not invalidate iterators.
2136 //! If the request is successful, then capacity() is greater than or equal to
2137 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
2138 //!
2139 //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws.
2140 //!
2141 //! <b>Note</b>: Non-standard extension.
2142 bool stable_reserve(size_type new_cap)
2143 {
2144 const size_type cp = this->capacity();
2145 return cp >= new_cap || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(new_cap - cp));
2146 }
2147
2148 //Absolutely experimental. This function might change, disappear or simply crash!
2149 template<class BiDirPosConstIt, class BiDirValueIt>
2150 void insert_ordered_at(const size_type element_count, BiDirPosConstIt last_position_it, BiDirValueIt last_value_it)
2151 {
2152 typedef container_detail::vector_insert_ordered_cursor<BiDirPosConstIt, BiDirValueIt> inserter_t;
2153 return this->priv_insert_ordered_at(element_count, inserter_t(last_position_it, last_value_it));
2154 }
2155
2156 template<class BidirIt>
2157 void merge(BidirIt first, BidirIt last)
2158 { this->merge(first, last, value_less()); }
2159
2160 template<class BidirIt, class Compare>
2161 void merge(BidirIt first, BidirIt last, Compare comp)
2162 { this->priv_merge(container_detail::false_type(), first, last, comp); }
2163
2164 template<class BidirIt>
2165 void merge_unique(BidirIt first, BidirIt last)
2166 { this->priv_merge(container_detail::true_type(), first, last, value_less()); }
2167
2168 template<class BidirIt, class Compare>
2169 void merge_unique(BidirIt first, BidirIt last, Compare comp)
2170 { this->priv_merge(container_detail::true_type(), first, last, comp); }
2171
2172 private:
2173 template<class PositionValue>
2174 void priv_insert_ordered_at(const size_type element_count, PositionValue position_value)
2175 {
2176 const size_type old_size_pos = this->size();
2177 this->reserve(old_size_pos + element_count);
2178 T* const begin_ptr = this->priv_raw_begin();
2179 size_type insertions_left = element_count;
2180 size_type prev_pos = old_size_pos;
2181 size_type old_hole_size = element_count;
2182
2183 //Exception rollback. If any copy throws before the hole is filled, values
2184 //already inserted/copied at the end of the buffer will be destroyed.
2185 typename value_traits::ArrayDestructor past_hole_values_destroyer
2186 (begin_ptr + old_size_pos + element_count, this->m_holder.alloc(), size_type(0u));
2187 //Loop for each insertion backwards, first moving the elements after the insertion point,
2188 //then inserting the element.
2189 while(insertions_left){
2190 --position_value;
2191 size_type const pos = position_value.get_pos();
2192 BOOST_ASSERT(pos != size_type(-1) && pos <= old_size_pos && pos <= prev_pos);
2193 //If needed shift the range after the insertion point and the previous insertion point.
2194 //Function will take care if the shift crosses the size() boundary, using copy/move
2195 //or uninitialized copy/move if necessary.
2196 size_type new_hole_size = (pos != prev_pos)
2197 ? priv_insert_ordered_at_shift_range(pos, prev_pos, this->size(), insertions_left)
2198 : old_hole_size
2199 ;
2200 if(new_hole_size){
2201 //The hole was reduced by priv_insert_ordered_at_shift_range so expand exception rollback range backwards
2202 past_hole_values_destroyer.increment_size_backwards(prev_pos - pos);
2203 //Insert the new value in the hole
2204 allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, position_value.get_val());
2205 if(--new_hole_size){
2206 //The hole was reduced by the new insertion by one
2207 past_hole_values_destroyer.increment_size_backwards(size_type(1u));
2208 }
2209 else{
2210 //Hole was just filled, disable exception rollback and change vector size
2211 past_hole_values_destroyer.release();
2212 this->m_holder.m_size += element_count;
2213 }
2214 }
2215 else{
2216 if(old_hole_size){
2217 //Hole was just filled by priv_insert_ordered_at_shift_range, disable exception rollback and change vector size
2218 past_hole_values_destroyer.release();
2219 this->m_holder.m_size += element_count;
2220 }
2221 //Insert the new value in the already constructed range
2222 begin_ptr[pos + insertions_left - 1] = position_value.get_val();
2223 }
2224 --insertions_left;
2225 old_hole_size = new_hole_size;
2226 prev_pos = pos;
2227 }
2228 }
2229
2230 template<class UniqueBool, class BidirIt, class Compare>
2231 void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp)
2232 {
2233 size_type const n = static_cast<size_type>(boost::container::iterator_distance(first, last));
2234 size_type const s = this->size();
2235 if(BOOST_LIKELY(s)){
2236 size_type const c = this->capacity();
2237 size_type const free_c = (c - s);
2238 //Use a new buffer if current one is too small for new elements,
2239 //or there is no room for position indexes
2240 if(free_c < n){
2241 size_type const new_size = s + n;
2242 size_type new_cap = new_size;
2243 pointer p = pointer();
2244 p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p);
2245 this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap);
2246 }
2247 else{
2248 T *raw_pos = boost::movelib::iterator_to_raw_pointer(this->insert(this->cend(), first, last));
2249 T *raw_beg = this->priv_raw_begin();
2250 T *raw_end = this->priv_raw_end();
2251 boost::movelib::adaptive_merge(raw_beg, raw_pos, raw_end, comp, raw_end, free_c - n);
2252 if(UniqueBool::value){
2253 size_type const count =
2254 static_cast<size_type>(raw_end - boost::movelib::unique(raw_beg, raw_end, boost::movelib::negate<Compare>(comp)));
2255 this->priv_destroy_last_n(count);
2256 }
2257 }
2258 }
2259 else{
2260 this->insert(this->cend(), n, first, last);
2261 }
2262 }
2263
2264 template<class UniqueBool, class FwdIt, class Compare>
2265 void priv_merge_in_new_buffer
2266 (UniqueBool, FwdIt first, size_type n, Compare comp, pointer new_storage, size_type const new_cap)
2267 {
2268 BOOST_ASSERT((new_cap >= this->size() ) && (new_cap - this->size()) >= n);
2269 allocator_type &a = this->m_holder.alloc();
2270 typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap);
2271 typename value_traits::ArrayDestructor new_values_destroyer(new_storage, a, 0u);
2272 T* pbeg = this->priv_raw_begin();
2273 size_type const old_size = this->size();
2274 T* const pend = pbeg + old_size;
2275 T* d_first = boost::movelib::to_raw_pointer(new_storage);
2276 size_type added = n;
2277 //Merge in new buffer loop
2278 while(1){
2279 if(!n) {
2280 ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pbeg, pend, d_first);
2281 break;
2282 }
2283 else if(pbeg == pend) {
2284 ::boost::container::uninitialized_move_alloc_n(this->m_holder.alloc(), first, n, d_first);
2285 break;
2286 }
2287 //maintain stability moving external values only if they are strictly less
2288 else if(comp(*first, *pbeg)) {
2289 allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::boost::move(*first) );
2290 new_values_destroyer.increment_size(1u);
2291 ++first;
2292 --n;
2293 ++d_first;
2294 }
2295 else if(UniqueBool::value && !comp(*pbeg, *first)){
2296 ++first;
2297 --n;
2298 --added;
2299 }
2300 else{
2301 allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::boost::move(*pbeg) );
2302 new_values_destroyer.increment_size(1u);
2303 ++pbeg;
2304 ++d_first;
2305 }
2306 }
2307
2308 //Nothrow operations
2309 pointer const old_p = this->m_holder.start();
2310 size_type const old_cap = this->m_holder.capacity();
2311 boost::container::destroy_alloc_n(a, boost::movelib::to_raw_pointer(old_p), old_size);
2312 a.deallocate(old_p, old_cap);
2313 this->m_holder.m_size = old_size + added;
2314 this->m_holder.start(new_storage);
2315 this->m_holder.capacity(new_cap);
2316 new_buffer_deallocator.release();
2317 new_values_destroyer.release();
2318 }
2319
2320 bool room_enough() const
2321 { return this->m_holder.m_size < this->m_holder.capacity(); }
2322
2323 pointer back_ptr() const
2324 { return this->m_holder.start() + this->m_holder.m_size; }
2325
2326 size_type priv_index_of(pointer p) const
2327 {
2328 BOOST_ASSERT(this->m_holder.start() <= p);
2329 BOOST_ASSERT(p <= (this->m_holder.start()+this->size()));
2330 return static_cast<size_type>(p - this->m_holder.start());
2331 }
2332
2333 template<class OtherAllocator>
2334 void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
2335 , typename container_detail::enable_if_c
2336 < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0)
2337 {
2338 if(!container_detail::is_same<OtherAllocator, allocator_type>::value &&
2339 this->capacity() < x.size()){
2340 throw_bad_alloc();
2341 }
2342 T* const this_start = this->priv_raw_begin();
2343 T* const other_start = x.priv_raw_begin();
2344 const size_type this_sz = m_holder.m_size;
2345 const size_type other_sz = static_cast<size_type>(x.m_holder.m_size);
2346 boost::container::move_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz);
2347 this->m_holder.m_size = other_sz;
2348 }
2349
2350 template<class OtherAllocator>
2351 void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x
2352 , typename container_detail::disable_if_or
2353 < void
2354 , container_detail::is_version<OtherAllocator, 0>
2355 , container_detail::is_different<OtherAllocator, allocator_type>
2356 >::type * = 0)
2357 {
2358 //for move assignment, no aliasing (&x != this) is assummed.
2359 BOOST_ASSERT(this != &x);
2360 allocator_type &this_alloc = this->m_holder.alloc();
2361 allocator_type &x_alloc = x.m_holder.alloc();
2362 const bool propagate_alloc = allocator_traits_type::propagate_on_container_move_assignment::value;
2363
2364 const bool is_propagable_from_x = is_propagable_from(x_alloc, x.m_holder.start(), this_alloc, propagate_alloc);
2365 const bool is_propagable_from_t = is_propagable_from(this_alloc, m_holder.start(), x_alloc, propagate_alloc);
2366 const bool are_both_propagable = is_propagable_from_x && is_propagable_from_t;
2367
2368 //Resources can be transferred if both allocators are
2369 //going to be equal after this function (either propagated or already equal)
2370 if(are_both_propagable){
2371 //Destroy objects but retain memory in case x reuses it in the future
2372 this->clear();
2373 this->m_holder.swap_resources(x.m_holder);
2374 }
2375 else if(is_propagable_from_x){
2376 this->clear();
2377 this->m_holder.alloc().deallocate(this->m_holder.m_start, this->m_holder.m_capacity);
2378 this->m_holder.steal_resources(x.m_holder);
2379 }
2380 //Else do a one by one move
2381 else{
2382 this->assign( boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(x.begin()))
2383 , boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(x.end() ))
2384 );
2385 }
2386 //Move allocator if needed
2387 container_detail::move_alloc(this_alloc, x_alloc, container_detail::bool_<propagate_alloc>());
2388 }
2389
2390 template<class OtherAllocator>
2391 void priv_copy_assign(const vector<T, OtherAllocator> &x
2392 , typename container_detail::enable_if_c
2393 < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0)
2394 {
2395 if(!container_detail::is_same<OtherAllocator, allocator_type>::value &&
2396 this->capacity() < x.size()){
2397 throw_bad_alloc();
2398 }
2399 T* const this_start = this->priv_raw_begin();
2400 T* const other_start = x.priv_raw_begin();
2401 const size_type this_sz = m_holder.m_size;
2402 const size_type other_sz = static_cast<size_type>(x.m_holder.m_size);
2403 boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz);
2404 this->m_holder.m_size = other_sz;
2405 }
2406
2407 template<class OtherAllocator>
2408 typename container_detail::disable_if_or
2409 < void
2410 , container_detail::is_version<OtherAllocator, 0>
2411 , container_detail::is_different<OtherAllocator, allocator_type>
2412 >::type
2413 priv_copy_assign(const vector<T, OtherAllocator> &x)
2414 {
2415 allocator_type &this_alloc = this->m_holder.alloc();
2416 const allocator_type &x_alloc = x.m_holder.alloc();
2417 container_detail::bool_<allocator_traits_type::
2418 propagate_on_container_copy_assignment::value> flag;
2419 if(flag && this_alloc != x_alloc){
2420 this->clear();
2421 this->shrink_to_fit();
2422 }
2423 container_detail::assign_alloc(this_alloc, x_alloc, flag);
2424 this->assign( x.priv_raw_begin(), x.priv_raw_end() );
2425 }
2426
2427 template<class Vector> //Template it to avoid it in explicit instantiations
2428 void priv_swap(Vector &x, container_detail::true_type) //version_0
2429 { this->m_holder.deep_swap(x.m_holder); }
2430
2431 template<class Vector> //Template it to avoid it in explicit instantiations
2432 void priv_swap(Vector &x, container_detail::false_type) //version_N
2433 {
2434 const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
2435 if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start()
2436 , x.get_stored_allocator(), x.m_holder.start(), propagate_alloc)){
2437 //Just swap internals
2438 this->m_holder.swap_resources(x.m_holder);
2439 }
2440 else{
2441 //Else swap element by element...
2442 bool const t_smaller = this->size() < x.size();
2443 vector &sml = t_smaller ? *this : x;
2444 vector &big = t_smaller ? x : *this;
2445
2446 size_type const common_elements = sml.size();
2447 for(size_type i = 0; i != common_elements; ++i){
2448 boost::adl_move_swap(sml[i], big[i]);
2449 }
2450 //... and move-insert the remaining range
2451 sml.insert( sml.cend()
2452 , boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(big.nth(common_elements)))
2453 , boost::make_move_iterator(boost::movelib::iterator_to_raw_pointer(big.end()))
2454 );
2455 //Destroy remaining elements
2456 big.erase(big.nth(common_elements), big.cend());
2457 }
2458 //And now swap the allocator
2459 container_detail::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), container_detail::bool_<propagate_alloc>());
2460 }
2461
2462 void priv_reserve_no_capacity(size_type, version_0)
2463 { throw_bad_alloc(); }
2464
2465 container_detail::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> priv_dummy_empty_proxy()
2466 {
2467 return container_detail::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*>
2468 (::boost::make_move_iterator((T *)0));
2469 }
2470
2471 void priv_reserve_no_capacity(size_type new_cap, version_1)
2472 {
2473 //There is not enough memory, allocate a new buffer
2474 //Pass the hint so that allocators can take advantage of this.
2475 pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start);
2476 //We will reuse insert code, so create a dummy input iterator
2477 this->priv_forward_range_insert_new_allocation
2478 ( boost::movelib::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy());
2479 }
2480
2481 void priv_reserve_no_capacity(size_type new_cap, version_2)
2482 {
2483 //There is not enough memory, allocate a new
2484 //buffer or expand the old one.
2485 bool same_buffer_start;
2486 size_type real_cap = 0;
2487 pointer reuse(this->m_holder.start());
2488 pointer const ret(this->m_holder.allocation_command(allocate_new | expand_fwd | expand_bwd, new_cap, real_cap = new_cap, reuse));
2489
2490 //Check for forward expansion
2491 same_buffer_start = reuse && this->m_holder.start() == ret;
2492 if(same_buffer_start){
2493 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2494 ++this->num_expand_fwd;
2495 #endif
2496 this->m_holder.capacity(real_cap);
2497 }
2498 else{ //If there is no forward expansion, move objects, we will reuse insertion code
2499 T * const new_mem = boost::movelib::to_raw_pointer(ret);
2500 T * const ins_pos = this->priv_raw_end();
2501 if(reuse){ //Backwards (and possibly forward) expansion
2502 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2503 ++this->num_expand_bwd;
2504 #endif
2505 this->priv_forward_range_insert_expand_backwards
2506 ( new_mem , real_cap, ins_pos, 0, this->priv_dummy_empty_proxy());
2507 }
2508 else{ //New buffer
2509 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2510 ++this->num_alloc;
2511 #endif
2512 this->priv_forward_range_insert_new_allocation
2513 ( new_mem, real_cap, ins_pos, 0, this->priv_dummy_empty_proxy());
2514 }
2515 }
2516 }
2517
2518 void priv_destroy_last(const bool moved = false) BOOST_NOEXCEPT_OR_NOTHROW
2519 {
2520 (void)moved;
2521 if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){
2522 value_type* const p = this->priv_raw_end() - 1;
2523 allocator_traits_type::destroy(this->get_stored_allocator(), p);
2524 }
2525 --this->m_holder.m_size;
2526 }
2527
2528 void priv_destroy_last_n(const size_type n) BOOST_NOEXCEPT_OR_NOTHROW
2529 {
2530 BOOST_ASSERT(n <= this->m_holder.m_size);
2531 if(!value_traits::trivial_dctr){
2532 T* const destroy_pos = this->priv_raw_begin() + (this->m_holder.m_size-n);
2533 boost::container::destroy_alloc_n(this->get_stored_allocator(), destroy_pos, n);
2534 }
2535 this->m_holder.m_size -= n;
2536 }
2537
2538 template<class InpIt>
2539 void priv_uninitialized_construct_at_end(InpIt first, InpIt last)
2540 {
2541 T* const old_end_pos = this->priv_raw_end();
2542 T* const new_end_pos = boost::container::uninitialized_copy_alloc(this->m_holder.alloc(), first, last, old_end_pos);
2543 this->m_holder.m_size += new_end_pos - old_end_pos;
2544 }
2545
2546 void priv_destroy_all() BOOST_NOEXCEPT_OR_NOTHROW
2547 {
2548 boost::container::destroy_alloc_n
2549 (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size);
2550 this->m_holder.m_size = 0;
2551 }
2552
2553 template<class U>
2554 iterator priv_insert(const const_iterator &p, BOOST_FWD_REF(U) x)
2555 {
2556 BOOST_ASSERT(this->priv_in_range_or_end(p));
2557 return this->priv_forward_range_insert
2558 ( vector_iterator_get_ptr(p), 1, container_detail::get_insert_value_proxy<T*, Allocator>(::boost::forward<U>(x)));
2559 }
2560
2561 container_detail::insert_copy_proxy<Allocator, T*> priv_single_insert_proxy(const T &x)
2562 { return container_detail::insert_copy_proxy<Allocator, T*> (x); }
2563
2564 container_detail::insert_move_proxy<Allocator, T*> priv_single_insert_proxy(BOOST_RV_REF(T) x)
2565 { return container_detail::insert_move_proxy<Allocator, T*> (x); }
2566
2567 template <class U>
2568 void priv_push_back(BOOST_FWD_REF(U) u)
2569 {
2570 if (BOOST_LIKELY(this->room_enough())){
2571 //There is more memory, just construct a new object at the end
2572 allocator_traits_type::construct
2573 ( this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<U>(u) );
2574 ++this->m_holder.m_size;
2575 }
2576 else{
2577 this->priv_forward_range_insert_no_capacity
2578 ( this->back_ptr(), 1
2579 , this->priv_single_insert_proxy(::boost::forward<U>(u)), alloc_version());
2580 }
2581 }
2582
2583 container_detail::insert_n_copies_proxy<Allocator, T*> priv_resize_proxy(const T &x)
2584 { return container_detail::insert_n_copies_proxy<Allocator, T*>(x); }
2585
2586 container_detail::insert_default_initialized_n_proxy<Allocator, T*> priv_resize_proxy(default_init_t)
2587 { return container_detail::insert_default_initialized_n_proxy<Allocator, T*>(); }
2588
2589 container_detail::insert_value_initialized_n_proxy<Allocator, T*> priv_resize_proxy(value_init_t)
2590 { return container_detail::insert_value_initialized_n_proxy<Allocator, T*>(); }
2591
2592 template <class U>
2593 void priv_resize(size_type new_size, const U& u)
2594 {
2595 const size_type sz = this->size();
2596 if (new_size < sz){
2597 //Destroy last elements
2598 this->priv_destroy_last_n(sz - new_size);
2599 }
2600 else{
2601 const size_type n = new_size - this->size();
2602 this->priv_forward_range_insert_at_end(n, this->priv_resize_proxy(u), alloc_version());
2603 }
2604 }
2605
2606 void priv_shrink_to_fit(version_0) BOOST_NOEXCEPT_OR_NOTHROW
2607 {}
2608
2609 void priv_shrink_to_fit(version_1)
2610 {
2611 const size_type cp = this->m_holder.capacity();
2612 if(cp){
2613 const size_type sz = this->size();
2614 if(!sz){
2615 this->m_holder.alloc().deallocate(this->m_holder.m_start, cp);
2616 this->m_holder.m_start = pointer();
2617 this->m_holder.m_capacity = 0;
2618 }
2619 else if(sz < cp){
2620 //Allocate a new buffer.
2621 //Pass the hint so that allocators can take advantage of this.
2622 pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), sz, this->m_holder.m_start);
2623
2624 //We will reuse insert code, so create a dummy input iterator
2625 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2626 ++this->num_alloc;
2627 #endif
2628 this->priv_forward_range_insert_new_allocation
2629 ( boost::movelib::to_raw_pointer(p), sz
2630 , this->priv_raw_begin(), 0, this->priv_dummy_empty_proxy());
2631 }
2632 }
2633 }
2634
2635 void priv_shrink_to_fit(version_2) BOOST_NOEXCEPT_OR_NOTHROW
2636 {
2637 const size_type cp = this->m_holder.capacity();
2638 if(cp){
2639 const size_type sz = this->size();
2640 if(!sz){
2641 this->m_holder.alloc().deallocate(this->m_holder.m_start, cp);
2642 this->m_holder.m_start = pointer();
2643 this->m_holder.m_capacity = 0;
2644 }
2645 else{
2646 size_type received_size = sz;
2647 pointer reuse(this->m_holder.start());
2648 if(this->m_holder.allocation_command
2649 (shrink_in_place | nothrow_allocation, cp, received_size, reuse)){
2650 this->m_holder.capacity(received_size);
2651 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2652 ++this->num_shrink;
2653 #endif
2654 }
2655 }
2656 }
2657 }
2658
2659 template <class InsertionProxy>
2660 iterator priv_forward_range_insert_no_capacity
2661 (const pointer &pos, const size_type, const InsertionProxy , version_0)
2662 {
2663 throw_bad_alloc();
2664 return iterator(pos);
2665 }
2666
2667 template <class InsertionProxy>
2668 iterator priv_forward_range_insert_no_capacity
2669 (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy, version_1)
2670 {
2671 //Check if we have enough memory or try to expand current memory
2672 const size_type n_pos = pos - this->m_holder.start();
2673 T *const raw_pos = boost::movelib::to_raw_pointer(pos);
2674
2675 const size_type new_cap = this->m_holder.next_capacity(n);
2676 //Pass the hint so that allocators can take advantage of this.
2677 T * const new_buf = boost::movelib::to_raw_pointer
2678 (allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start));
2679 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2680 ++this->num_alloc;
2681 #endif
2682 this->priv_forward_range_insert_new_allocation
2683 ( new_buf, new_cap, raw_pos, n, insert_range_proxy);
2684 return iterator(this->m_holder.start() + n_pos);
2685 }
2686
2687 template <class InsertionProxy>
2688 iterator priv_forward_range_insert_no_capacity
2689 (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy, version_2)
2690 {
2691 //Check if we have enough memory or try to expand current memory
2692 T *const raw_pos = boost::movelib::to_raw_pointer(pos);
2693 const size_type n_pos = raw_pos - this->priv_raw_begin();
2694
2695 //There is not enough memory, allocate a new
2696 //buffer or expand the old one.
2697 size_type real_cap = this->m_holder.next_capacity(n);
2698 pointer reuse(this->m_holder.start());
2699 pointer const ret (this->m_holder.allocation_command
2700 (allocate_new | expand_fwd | expand_bwd, this->m_holder.m_size + n, real_cap, reuse));
2701
2702 //Buffer reallocated
2703 if(reuse){
2704 //Forward expansion, delay insertion
2705 if(this->m_holder.start() == ret){
2706 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2707 ++this->num_expand_fwd;
2708 #endif
2709 this->m_holder.capacity(real_cap);
2710 //Expand forward
2711 this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy);
2712 }
2713 //Backwards (and possibly forward) expansion
2714 else{
2715 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2716 ++this->num_expand_bwd;
2717 #endif
2718 this->priv_forward_range_insert_expand_backwards
2719 (boost::movelib::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy);
2720 }
2721 }
2722 //New buffer
2723 else{
2724 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
2725 ++this->num_alloc;
2726 #endif
2727 this->priv_forward_range_insert_new_allocation
2728 ( boost::movelib::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy);
2729 }
2730
2731 return iterator(this->m_holder.start() + n_pos);
2732 }
2733
2734 template <class InsertionProxy>
2735 iterator priv_forward_range_insert
2736 (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy)
2737 {
2738 BOOST_ASSERT(this->m_holder.capacity() >= this->m_holder.m_size);
2739 //Check if we have enough memory or try to expand current memory
2740 const size_type remaining = this->m_holder.capacity() - this->m_holder.m_size;
2741
2742 bool same_buffer_start = n <= remaining;
2743 if (!same_buffer_start){
2744 return priv_forward_range_insert_no_capacity(pos, n, insert_range_proxy, alloc_version());
2745 }
2746 else{
2747 //Expand forward
2748 T *const raw_pos = boost::movelib::to_raw_pointer(pos);
2749 const size_type n_pos = raw_pos - this->priv_raw_begin();
2750 this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy);
2751 return iterator(this->m_holder.start() + n_pos);
2752 }
2753 }
2754
2755 template <class InsertionProxy>
2756 iterator priv_forward_range_insert_at_end
2757 (const size_type n, const InsertionProxy insert_range_proxy, version_0)
2758 {
2759 //Check if we have enough memory or try to expand current memory
2760 const size_type remaining = this->m_holder.capacity() - this->m_holder.m_size;
2761
2762 if (n > remaining){
2763 //This will trigger an error
2764 throw_bad_alloc();
2765 }
2766 this->priv_forward_range_insert_at_end_expand_forward(n, insert_range_proxy);
2767 return this->end();
2768 }
2769
2770 template <class InsertionProxy, class AllocVersion>
2771 iterator priv_forward_range_insert_at_end
2772 (const size_type n, const InsertionProxy insert_range_proxy, AllocVersion)
2773 {
2774 return this->priv_forward_range_insert(this->back_ptr(), n, insert_range_proxy);
2775 }
2776
2777 //Takes the range pointed by [first_pos, last_pos) and shifts it to the right
2778 //by 'shift_count'. 'limit_pos' marks the end of constructed elements.
2779 //
2780 //Precondition: first_pos <= last_pos <= limit_pos
2781 //
2782 //The shift operation might cross limit_pos so elements to moved beyond limit_pos
2783 //are uninitialized_moved with an allocator. Other elements are moved.
2784 //
2785 //The shift operation might left uninitialized elements after limit_pos
2786 //and the number of uninitialized elements is returned by the function.
2787 //
2788 //Old situation:
2789 // first_pos last_pos old_limit
2790 // | | |
2791 // ____________V_______V__________________V_____________
2792 //| prefix | range | suffix |raw_mem ~
2793 //|____________|_______|__________________|_____________~
2794 //
2795 //New situation in Case A (hole_size == 0):
2796 // range is moved through move assignments
2797 //
2798 // first_pos last_pos limit_pos
2799 // | | |
2800 // ____________V_______V__________________V_____________
2801 //| prefix' | | | range |suffix'|raw_mem ~
2802 //|________________+______|___^___|_______|_____________~
2803 // | |
2804 // |_>_>_>_>_>^
2805 //
2806 //
2807 //New situation in Case B (hole_size >= 0):
2808 // range is moved through uninitialized moves
2809 //
2810 // first_pos last_pos limit_pos
2811 // | | |
2812 // ____________V_______V__________________V________________
2813 //| prefix' | | | [hole] | range |
2814 //|_______________________________________|________|___^___|
2815 // | |
2816 // |_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_^
2817 //
2818 //New situation in Case C (hole_size == 0):
2819 // range is moved through move assignments and uninitialized moves
2820 //
2821 // first_pos last_pos limit_pos
2822 // | | |
2823 // ____________V_______V__________________V___
2824 //| prefix' | | | range |
2825 //|___________________________________|___^___|
2826 // | |
2827 // |_>_>_>_>_>_>_>_>_>_>_>^
2828 size_type priv_insert_ordered_at_shift_range
2829 (size_type first_pos, size_type last_pos, size_type limit_pos, size_type shift_count)
2830 {
2831 BOOST_ASSERT(first_pos <= last_pos);
2832 BOOST_ASSERT(last_pos <= limit_pos);
2833 //
2834 T* const begin_ptr = this->priv_raw_begin();
2835 T* const first_ptr = begin_ptr + first_pos;
2836 T* const last_ptr = begin_ptr + last_pos;
2837
2838 size_type hole_size = 0;
2839 //Case A:
2840 if((last_pos + shift_count) <= limit_pos){
2841 //All move assigned
2842 boost::container::move_backward(first_ptr, last_ptr, last_ptr + shift_count);
2843 }
2844 //Case B:
2845 else if((first_pos + shift_count) >= limit_pos){
2846 //All uninitialized_moved
2847 ::boost::container::uninitialized_move_alloc
2848 (this->m_holder.alloc(), first_ptr, last_ptr, first_ptr + shift_count);
2849 hole_size = first_pos + shift_count - limit_pos;
2850 }
2851 //Case C:
2852 else{
2853 //Some uninitialized_moved
2854 T* const limit_ptr = begin_ptr + limit_pos;
2855 T* const boundary_ptr = limit_ptr - shift_count;
2856 ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), boundary_ptr, last_ptr, limit_ptr);
2857 //The rest is move assigned
2858 boost::container::move_backward(first_ptr, boundary_ptr, limit_ptr);
2859 }
2860 return hole_size;
2861 }
2862
2863 private:
2864 BOOST_CONTAINER_FORCEINLINE T *priv_raw_begin() const
2865 { return boost::movelib::to_raw_pointer(m_holder.start()); }
2866
2867 BOOST_CONTAINER_FORCEINLINE T* priv_raw_end() const
2868 { return this->priv_raw_begin() + this->m_holder.m_size; }
2869
2870 template <class InsertionProxy>
2871 void priv_forward_range_insert_at_end_expand_forward(const size_type n, InsertionProxy insert_range_proxy)
2872 {
2873 T* const old_finish = this->priv_raw_end();
2874 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n);
2875 this->m_holder.m_size += n;
2876 }
2877
2878 template <class InsertionProxy>
2879 void priv_forward_range_insert_expand_forward(T* const pos, const size_type n, InsertionProxy insert_range_proxy)
2880 {
2881 //n can't be 0, because there is nothing to do in that case
2882 if(BOOST_UNLIKELY(!n)) return;
2883 //There is enough memory
2884 T* const old_finish = this->priv_raw_end();
2885 const size_type elems_after = old_finish - pos;
2886
2887 if (!elems_after){
2888 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n);
2889 this->m_holder.m_size += n;
2890 }
2891 else if (elems_after >= n){
2892 //New elements can be just copied.
2893 //Move to uninitialized memory last objects
2894 ::boost::container::uninitialized_move_alloc
2895 (this->m_holder.alloc(), old_finish - n, old_finish, old_finish);
2896 this->m_holder.m_size += n;
2897 //Copy previous to last objects to the initialized end
2898 boost::container::move_backward(pos, old_finish - n, old_finish);
2899 //Insert new objects in the pos
2900 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, n);
2901 }
2902 else {
2903 //The new elements don't fit in the [pos, end()) range.
2904
2905 //Copy old [pos, end()) elements to the uninitialized memory (a gap is created)
2906 ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pos, old_finish, pos + n);
2907 BOOST_TRY{
2908 //Copy first new elements in pos (gap is still there)
2909 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, elems_after);
2910 //Copy to the beginning of the unallocated zone the last new elements (the gap is closed).
2911 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n - elems_after);
2912 this->m_holder.m_size += n;
2913 }
2914 BOOST_CATCH(...){
2915 boost::container::destroy_alloc_n(this->get_stored_allocator(), pos + n, elems_after);
2916 BOOST_RETHROW
2917 }
2918 BOOST_CATCH_END
2919 }
2920 }
2921
2922 template <class InsertionProxy>
2923 void priv_forward_range_insert_new_allocation
2924 (T* const new_start, size_type new_cap, T* const pos, const size_type n, InsertionProxy insert_range_proxy)
2925 {
2926 //n can be zero, if we want to reallocate!
2927 T *new_finish = new_start;
2928 T *old_finish;
2929 //Anti-exception rollbacks
2930 typename value_traits::ArrayDeallocator new_buffer_deallocator(new_start, this->m_holder.alloc(), new_cap);
2931 typename value_traits::ArrayDestructor new_values_destroyer(new_start, this->m_holder.alloc(), 0u);
2932
2933 //Initialize with [begin(), pos) old buffer
2934 //the start of the new buffer
2935 T * const old_buffer = this->priv_raw_begin();
2936 if(old_buffer){
2937 new_finish = ::boost::container::uninitialized_move_alloc
2938 (this->m_holder.alloc(), this->priv_raw_begin(), pos, old_finish = new_finish);
2939 new_values_destroyer.increment_size(new_finish - old_finish);
2940 }
2941 //Initialize new objects, starting from previous point
2942 old_finish = new_finish;
2943 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n);
2944 new_finish += n;
2945 new_values_destroyer.increment_size(new_finish - old_finish);
2946 //Initialize from the rest of the old buffer,
2947 //starting from previous point
2948 if(old_buffer){
2949 new_finish = ::boost::container::uninitialized_move_alloc
2950 (this->m_holder.alloc(), pos, old_buffer + this->m_holder.m_size, new_finish);
2951 //Destroy and deallocate old elements
2952 //If there is allocated memory, destroy and deallocate
2953 if(!value_traits::trivial_dctr_after_move)
2954 boost::container::destroy_alloc_n(this->get_stored_allocator(), old_buffer, this->m_holder.m_size);
2955 this->m_holder.alloc().deallocate(this->m_holder.start(), this->m_holder.capacity());
2956 }
2957 this->m_holder.start(new_start);
2958 this->m_holder.m_size = new_finish - new_start;
2959 this->m_holder.capacity(new_cap);
2960 //All construction successful, disable rollbacks
2961 new_values_destroyer.release();
2962 new_buffer_deallocator.release();
2963 }
2964
2965 template <class InsertionProxy>
2966 void priv_forward_range_insert_expand_backwards
2967 (T* const new_start, const size_type new_capacity,
2968 T* const pos, const size_type n, InsertionProxy insert_range_proxy)
2969 {
2970 //n can be zero to just expand capacity
2971 //Backup old data
2972 T* const old_start = this->priv_raw_begin();
2973 const size_type old_size = this->m_holder.m_size;
2974 T* const old_finish = old_start + old_size;
2975
2976 //We can have 8 possibilities:
2977 const size_type elemsbefore = static_cast<size_type>(pos - old_start);
2978 const size_type s_before = static_cast<size_type>(old_start - new_start);
2979 const size_type before_plus_new = elemsbefore + n;
2980
2981 //Update the vector buffer information to a safe state
2982 this->m_holder.start(new_start);
2983 this->m_holder.capacity(new_capacity);
2984 this->m_holder.m_size = 0;
2985
2986 //If anything goes wrong, this object will destroy
2987 //all the old objects to fulfill previous vector state
2988 typename value_traits::ArrayDestructor old_values_destroyer(old_start, this->m_holder.alloc(), old_size);
2989 //Check if s_before is big enough to hold the beginning of old data + new data
2990 if(s_before >= before_plus_new){
2991 //Copy first old values before pos, after that the new objects
2992 T *const new_elem_pos =
2993 ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), old_start, pos, new_start);
2994 this->m_holder.m_size = elemsbefore;
2995 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), new_elem_pos, n);
2996 this->m_holder.m_size = before_plus_new;
2997 const size_type new_size = old_size + n;
2998 //Check if s_before is so big that even copying the old data + new data
2999 //there is a gap between the new data and the old data
3000 if(s_before >= new_size){
3001 //Old situation:
3002 // _________________________________________________________
3003 //| raw_mem | old_begin | old_end |
3004 //| __________________________________|___________|_________|
3005 //
3006 //New situation:
3007 // _________________________________________________________
3008 //| old_begin | new | old_end | raw_mem |
3009 //|___________|__________|_________|________________________|
3010 //
3011 //Now initialize the rest of memory with the last old values
3012 if(before_plus_new != new_size){ //Special case to avoid operations in back insertion
3013 ::boost::container::uninitialized_move_alloc
3014 (this->m_holder.alloc(), pos, old_finish, new_start + before_plus_new);
3015 //All new elements correctly constructed, avoid new element destruction
3016 this->m_holder.m_size = new_size;
3017 }
3018 //Old values destroyed automatically with "old_values_destroyer"
3019 //when "old_values_destroyer" goes out of scope unless the have trivial
3020 //destructor after move.
3021 if(value_traits::trivial_dctr_after_move)
3022 old_values_destroyer.release();
3023 }
3024 //s_before is so big that divides old_end
3025 else{
3026 //Old situation:
3027 // __________________________________________________
3028 //| raw_mem | old_begin | old_end |
3029 //| ___________________________|___________|_________|
3030 //
3031 //New situation:
3032 // __________________________________________________
3033 //| old_begin | new | old_end | raw_mem |
3034 //|___________|__________|_________|_________________|
3035 //
3036 //Now initialize the rest of memory with the last old values
3037 //All new elements correctly constructed, avoid new element destruction
3038 const size_type raw_gap = s_before - before_plus_new;
3039 if(!value_traits::trivial_dctr){
3040 //Now initialize the rest of s_before memory with the
3041 //first of elements after new values
3042 ::boost::container::uninitialized_move_alloc_n
3043 (this->m_holder.alloc(), pos, raw_gap, new_start + before_plus_new);
3044 //Now we have a contiguous buffer so program trailing element destruction
3045 //and update size to the final size.
3046 old_values_destroyer.shrink_forward(new_size-s_before);
3047 this->m_holder.m_size = new_size;
3048 //Now move remaining last objects in the old buffer begin
3049 T * const remaining_pos = pos + raw_gap;
3050 if(remaining_pos != old_start){ //Make sure data has to be moved
3051 ::boost::container::move(remaining_pos, old_finish, old_start);
3052 }
3053 //Once moved, avoid calling the destructors if trivial after move
3054 if(value_traits::trivial_dctr_after_move){
3055 old_values_destroyer.release();
3056 }
3057 }
3058 else{ //If trivial destructor, we can uninitialized copy + copy in a single uninitialized copy
3059 ::boost::container::uninitialized_move_alloc_n
3060 (this->m_holder.alloc(), pos, static_cast<size_type>(old_finish - pos), new_start + before_plus_new);
3061 this->m_holder.m_size = new_size;
3062 old_values_destroyer.release();
3063 }
3064 }
3065 }
3066 else{
3067 //Check if we have to do the insertion in two phases
3068 //since maybe s_before is not big enough and
3069 //the buffer was expanded both sides
3070 //
3071 //Old situation:
3072 // _________________________________________________
3073 //| raw_mem | old_begin + old_end | raw_mem |
3074 //|_________|_____________________|_________________|
3075 //
3076 //New situation with do_after:
3077 // _________________________________________________
3078 //| old_begin + new + old_end | raw_mem |
3079 //|___________________________________|_____________|
3080 //
3081 //New without do_after:
3082 // _________________________________________________
3083 //| old_begin + new + old_end | raw_mem |
3084 //|____________________________|____________________|
3085 //
3086 const bool do_after = n > s_before;
3087
3088 //Now we can have two situations: the raw_mem of the
3089 //beginning divides the old_begin, or the new elements:
3090 if (s_before <= elemsbefore) {
3091 //The raw memory divides the old_begin group:
3092 //
3093 //If we need two phase construction (do_after)
3094 //new group is divided in new = new_beg + new_end groups
3095 //In this phase only new_beg will be inserted
3096 //
3097 //Old situation:
3098 // _________________________________________________
3099 //| raw_mem | old_begin | old_end | raw_mem |
3100 //|_________|___________|_________|_________________|
3101 //
3102 //New situation with do_after(1):
3103 //This is not definitive situation, the second phase
3104 //will include
3105 // _________________________________________________
3106 //| old_begin | new_beg | old_end | raw_mem |
3107 //|___________|_________|_________|_________________|
3108 //
3109 //New situation without do_after:
3110 // _________________________________________________
3111 //| old_begin | new | old_end | raw_mem |
3112 //|___________|_____|_________|_____________________|
3113 //
3114 //Copy the first part of old_begin to raw_mem
3115 ::boost::container::uninitialized_move_alloc_n
3116 (this->m_holder.alloc(), old_start, s_before, new_start);
3117 //The buffer is all constructed until old_end,
3118 //so program trailing destruction and assign final size
3119 //if !do_after, s_before+n otherwise.
3120 size_type new_1st_range;
3121 if(do_after){
3122 new_1st_range = s_before;
3123 //release destroyer and update size
3124 old_values_destroyer.release();
3125 }
3126 else{
3127 new_1st_range = n;
3128 if(value_traits::trivial_dctr_after_move)
3129 old_values_destroyer.release();
3130 else{
3131 old_values_destroyer.shrink_forward(old_size - (s_before - n));
3132 }
3133 }
3134 this->m_holder.m_size = old_size + new_1st_range;
3135 //Now copy the second part of old_begin overwriting itself
3136 T *const next = ::boost::container::move(old_start + s_before, pos, old_start);
3137 //Now copy the new_beg elements
3138 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), next, new_1st_range);
3139
3140 //If there is no after work and the last old part needs to be moved to front, do it
3141 if(!do_after && (n != s_before)){
3142 //Now displace old_end elements
3143 ::boost::container::move(pos, old_finish, next + new_1st_range);
3144 }
3145 }
3146 else {
3147 //If we have to expand both sides,
3148 //we will play if the first new values so
3149 //calculate the upper bound of new values
3150
3151 //The raw memory divides the new elements
3152 //
3153 //If we need two phase construction (do_after)
3154 //new group is divided in new = new_beg + new_end groups
3155 //In this phase only new_beg will be inserted
3156 //
3157 //Old situation:
3158 // _______________________________________________________
3159 //| raw_mem | old_begin | old_end | raw_mem |
3160 //|_______________|___________|_________|_________________|
3161 //
3162 //New situation with do_after():
3163 // ____________________________________________________
3164 //| old_begin | new_beg | old_end | raw_mem |
3165 //|___________|_______________|_________|______________|
3166 //
3167 //New situation without do_after:
3168 // ______________________________________________________
3169 //| old_begin | new | old_end | raw_mem |
3170 //|___________|_____|_________|__________________________|
3171 //
3172 //First copy whole old_begin and part of new to raw_mem
3173 T * const new_pos = ::boost::container::uninitialized_move_alloc
3174 (this->m_holder.alloc(), old_start, pos, new_start);
3175 this->m_holder.m_size = elemsbefore;
3176 const size_type mid_n = s_before - elemsbefore;
3177 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), new_pos, mid_n);
3178 //The buffer is all constructed until old_end,
3179 //release destroyer
3180 this->m_holder.m_size = old_size + s_before;
3181 old_values_destroyer.release();
3182
3183 if(do_after){
3184 //Copy new_beg part
3185 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), old_start, elemsbefore);
3186 }
3187 else{
3188 //Copy all new elements
3189 const size_type rest_new = n - mid_n;
3190 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), old_start, rest_new);
3191 T* const move_start = old_start + rest_new;
3192 //Displace old_end, but make sure data has to be moved
3193 T* const move_end = move_start != pos ? ::boost::container::move(pos, old_finish, move_start)
3194 : old_finish;
3195 //Destroy remaining moved elements from old_end except if they
3196 //have trivial destructor after being moved
3197 size_type n_destroy = s_before - n;
3198 if(!value_traits::trivial_dctr_after_move)
3199 boost::container::destroy_alloc_n(this->get_stored_allocator(), move_end, n_destroy);
3200 this->m_holder.m_size -= n_destroy;
3201 }
3202 }
3203
3204 //This is only executed if two phase construction is needed
3205 if(do_after){
3206 //The raw memory divides the new elements
3207 //
3208 //Old situation:
3209 // ______________________________________________________
3210 //| raw_mem | old_begin | old_end | raw_mem |
3211 //|______________|___________|____________|______________|
3212 //
3213 //New situation with do_after(1):
3214 // _______________________________________________________
3215 //| old_begin + new_beg | new_end |old_end | raw_mem |
3216 //|__________________________|_________|________|_________|
3217 //
3218 //New situation with do_after(2):
3219 // ______________________________________________________
3220 //| old_begin + new | old_end |raw |
3221 //|_______________________________________|_________|____|
3222 //
3223 const size_type n_after = n - s_before;
3224 const size_type elemsafter = old_size - elemsbefore;
3225
3226 //We can have two situations:
3227 if (elemsafter >= n_after){
3228 //The raw_mem from end will divide displaced old_end
3229 //
3230 //Old situation:
3231 // ______________________________________________________
3232 //| raw_mem | old_begin | old_end | raw_mem |
3233 //|______________|___________|____________|______________|
3234 //
3235 //New situation with do_after(1):
3236 // _______________________________________________________
3237 //| old_begin + new_beg | new_end |old_end | raw_mem |
3238 //|__________________________|_________|________|_________|
3239 //
3240 //First copy the part of old_end raw_mem
3241 T* finish_n = old_finish - n_after;
3242 ::boost::container::uninitialized_move_alloc
3243 (this->m_holder.alloc(), finish_n, old_finish, old_finish);
3244 this->m_holder.m_size += n_after;
3245 //Displace the rest of old_end to the new position
3246 boost::container::move_backward(pos, finish_n, old_finish);
3247 //Now overwrite with new_end
3248 //The new_end part is [first + (n - n_after), last)
3249 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, n_after);
3250 }
3251 else {
3252 //The raw_mem from end will divide new_end part
3253 //
3254 //Old situation:
3255 // _____________________________________________________________
3256 //| raw_mem | old_begin | old_end | raw_mem |
3257 //|______________|___________|____________|_____________________|
3258 //
3259 //New situation with do_after(2):
3260 // _____________________________________________________________
3261 //| old_begin + new_beg | new_end |old_end | raw_mem |
3262 //|__________________________|_______________|________|_________|
3263 //
3264
3265 const size_type mid_last_dist = n_after - elemsafter;
3266 //First initialize data in raw memory
3267
3268 //Copy to the old_end part to the uninitialized zone leaving a gap.
3269 ::boost::container::uninitialized_move_alloc
3270 (this->m_holder.alloc(), pos, old_finish, old_finish + mid_last_dist);
3271
3272 typename value_traits::ArrayDestructor old_end_destroyer
3273 (old_finish + mid_last_dist, this->m_holder.alloc(), old_finish - pos);
3274
3275 //Copy the first part to the already constructed old_end zone
3276 insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, elemsafter);
3277 //Copy the rest to the uninitialized zone filling the gap
3278 insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, mid_last_dist);
3279 this->m_holder.m_size += n_after;
3280 old_end_destroyer.release();
3281 }
3282 }
3283 }
3284 }
3285
3286 void priv_throw_if_out_of_range(size_type n) const
3287 {
3288 //If n is out of range, throw an out_of_range exception
3289 if (n >= this->size()){
3290 throw_out_of_range("vector::at out of range");
3291 }
3292 }
3293
3294 bool priv_in_range(const_iterator pos) const
3295 {
3296 return (this->begin() <= pos) && (pos < this->end());
3297 }
3298
3299 bool priv_in_range_or_end(const_iterator pos) const
3300 {
3301 return (this->begin() <= pos) && (pos <= this->end());
3302 }
3303
3304 #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS
3305 public:
3306 unsigned int num_expand_fwd;
3307 unsigned int num_expand_bwd;
3308 unsigned int num_shrink;
3309 unsigned int num_alloc;
3310 void reset_alloc_stats()
3311 { num_expand_fwd = num_expand_bwd = num_alloc = 0, num_shrink = 0; }
3312 #endif
3313 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3314};
3315
3316}} //namespace boost::container
3317
3318#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3319
3320namespace boost {
3321
3322//!has_trivial_destructor_after_move<> == true_type
3323//!specialization for optimizations
3324template <class T, class Allocator>
3325struct has_trivial_destructor_after_move<boost::container::vector<T, Allocator> >
3326{
3327 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
3328 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
3329 ::boost::has_trivial_destructor_after_move<pointer>::value;
3330};
3331
3332}
3333
3334#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3335
3336#include <boost/container/detail/config_end.hpp>
3337
3338#endif // #ifndef BOOST_CONTAINER_CONTAINER_VECTOR_HPP
3339