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

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