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