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