]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | BOOST_CONTAINER_FORCEINLINE const Pointer &get_ptr() const BOOST_NOEXCEPT_OR_NOTHROW | |
100 | { return m_ptr; } | |
101 | ||
102 | BOOST_CONTAINER_FORCEINLINE Pointer &get_ptr() BOOST_NOEXCEPT_OR_NOTHROW | |
103 | { return m_ptr; } | |
104 | ||
105 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE vec_iterator() BOOST_NOEXCEPT_OR_NOTHROW | |
114 | : m_ptr() //Value initialization to achieve "null iterators" (N3644) | |
115 | {} | |
116 | ||
117 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW | |
123 | { return *m_ptr; } | |
124 | ||
125 | BOOST_CONTAINER_FORCEINLINE pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW | |
126 | { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*()); } | |
127 | ||
128 | BOOST_CONTAINER_FORCEINLINE reference operator[](difference_type off) const BOOST_NOEXCEPT_OR_NOTHROW | |
129 | { return m_ptr[off]; } | |
130 | ||
131 | //Increment / Decrement | |
132 | BOOST_CONTAINER_FORCEINLINE vec_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW | |
133 | { ++m_ptr; return *this; } | |
134 | ||
135 | BOOST_CONTAINER_FORCEINLINE vec_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW | |
136 | { return vec_iterator(m_ptr++); } | |
137 | ||
138 | BOOST_CONTAINER_FORCEINLINE vec_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW | |
139 | { --m_ptr; return *this; } | |
140 | ||
141 | BOOST_CONTAINER_FORCEINLINE vec_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW | |
142 | { return vec_iterator(m_ptr--); } | |
143 | ||
144 | //Arithmetic | |
145 | BOOST_CONTAINER_FORCEINLINE vec_iterator& operator+=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW | |
146 | { m_ptr += off; return *this; } | |
147 | ||
148 | BOOST_CONTAINER_FORCEINLINE vec_iterator& operator-=(difference_type off) BOOST_NOEXCEPT_OR_NOTHROW | |
149 | { m_ptr -= off; return *this; } | |
150 | ||
151 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator+(difference_type off, vec_iterator right) BOOST_NOEXCEPT_OR_NOTHROW | |
155 | { right.m_ptr += off; return right; } | |
156 | ||
157 | BOOST_CONTAINER_FORCEINLINE friend vec_iterator operator-(vec_iterator left, difference_type off) BOOST_NOEXCEPT_OR_NOTHROW | |
158 | { left.m_ptr -= off; return left; } | |
159 | ||
160 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE size_type get_pos() const | |
204 | { return *last_position_it; } | |
205 | ||
206 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE size_type get_pos() const | |
236 | { return static_cast<size_type>((m_pcur + 1) - m_pbeg); } | |
237 | ||
238 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 = pointer(); | |
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 = pointer(); | |
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 | BOOST_CONTAINER_FORCEINLINE ~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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE Allocator &alloc() BOOST_NOEXCEPT_OR_NOTHROW | |
514 | { return *this; } | |
515 | ||
516 | BOOST_CONTAINER_FORCEINLINE 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 = pointer(); | |
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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE void priv_first_allocation(size_type cap) | |
628 | { | |
629 | if(cap > Allocator::internal_capacity){ | |
630 | throw_bad_alloc(); | |
631 | } | |
632 | } | |
633 | ||
634 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE Allocator &alloc() BOOST_NOEXCEPT_OR_NOTHROW | |
660 | { return *this; } | |
661 | ||
662 | BOOST_CONTAINER_FORCEINLINE const Allocator &alloc() const BOOST_NOEXCEPT_OR_NOTHROW | |
663 | { return *this; } | |
664 | ||
665 | BOOST_CONTAINER_FORCEINLINE bool try_expand_fwd(size_type at_least) | |
666 | { return !at_least; } | |
667 | ||
668 | BOOST_CONTAINER_FORCEINLINE pointer start() const BOOST_NOEXCEPT_OR_NOTHROW { return Allocator::internal_storage(); } | |
669 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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 | BOOST_CONTAINER_FORCEINLINE 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_IF(container_detail::is_nothrow_default_constructible<Allocator>::value) | |
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 value initialized values. | |
826 | //! | |
827 | //! <b>Throws</b>: If allocator_type's allocation | |
828 | //! throws or T's value initialization throws. | |
829 | //! | |
830 | //! <b>Complexity</b>: Linear to n. | |
831 | explicit vector(size_type n, const allocator_type &a) | |
832 | : m_holder(container_detail::uninitialized_size, a, n) | |
833 | { | |
834 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
835 | this->num_alloc += n != 0; | |
836 | #endif | |
837 | boost::container::uninitialized_value_init_alloc_n | |
838 | (this->m_holder.alloc(), n, this->priv_raw_begin()); | |
839 | } | |
840 | ||
841 | //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a | |
842 | //! and inserts n default initialized values. | |
843 | //! | |
844 | //! <b>Throws</b>: If allocator_type's allocation | |
845 | //! throws or T's default initialization throws. | |
846 | //! | |
847 | //! <b>Complexity</b>: Linear to n. | |
848 | //! | |
849 | //! <b>Note</b>: Non-standard extension | |
850 | vector(size_type n, default_init_t) | |
851 | : m_holder(container_detail::uninitialized_size, n) | |
852 | { | |
853 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
854 | this->num_alloc += n != 0; | |
855 | #endif | |
856 | boost::container::uninitialized_default_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 | BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c | |
923 | < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value | |
924 | BOOST_MOVE_I container_detail::nat >::type * = 0) | |
925 | ) | |
926 | : m_holder() | |
927 | { this->assign(first, last); } | |
928 | ||
929 | //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a | |
930 | //! and inserts a copy of the range [first, last) in the vector. | |
931 | //! | |
932 | //! <b>Throws</b>: If allocator_type's allocation | |
933 | //! throws or T's constructor taking a dereferenced InIt throws. | |
934 | //! | |
935 | //! <b>Complexity</b>: Linear to the range [first, last). | |
936 | template <class InIt> | |
937 | vector(InIt first, InIt last, const allocator_type& a | |
938 | BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_c | |
939 | < container_detail::is_convertible<InIt BOOST_MOVE_I size_type>::value | |
940 | BOOST_MOVE_I container_detail::nat >::type * = 0) | |
941 | ) | |
942 | : m_holder(a) | |
943 | { this->assign(first, last); } | |
944 | ||
945 | //! <b>Effects</b>: Copy constructs a vector. | |
946 | //! | |
947 | //! <b>Postcondition</b>: x == *this. | |
948 | //! | |
949 | //! <b>Throws</b>: If allocator_type's allocation | |
950 | //! throws or T's copy constructor throws. | |
951 | //! | |
952 | //! <b>Complexity</b>: Linear to the elements x contains. | |
953 | vector(const vector &x) | |
954 | : m_holder( container_detail::uninitialized_size | |
955 | , allocator_traits_type::select_on_container_copy_construction(x.m_holder.alloc()) | |
956 | , x.size()) | |
957 | { | |
958 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
959 | this->num_alloc += x.size() != 0; | |
960 | #endif | |
961 | ::boost::container::uninitialized_copy_alloc_n | |
962 | ( this->m_holder.alloc(), x.priv_raw_begin() | |
963 | , x.size(), this->priv_raw_begin()); | |
964 | } | |
965 | ||
966 | //! <b>Effects</b>: Move constructor. Moves x's resources to *this. | |
967 | //! | |
968 | //! <b>Throws</b>: Nothing | |
969 | //! | |
970 | //! <b>Complexity</b>: Constant. | |
971 | vector(BOOST_RV_REF(vector) x) BOOST_NOEXCEPT_OR_NOTHROW | |
972 | : m_holder(boost::move(x.m_holder)) | |
973 | { BOOST_STATIC_ASSERT((!allocator_traits_type::is_partially_propagable::value)); } | |
974 | ||
975 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
976 | //! <b>Effects</b>: Constructs a vector that will use a copy of allocator a | |
977 | //! and inserts a copy of the range [il.begin(), il.last()) in the vector | |
978 | //! | |
979 | //! <b>Throws</b>: If T's constructor taking a dereferenced initializer_list iterator throws. | |
980 | //! | |
981 | //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). | |
982 | vector(std::initializer_list<value_type> il, const allocator_type& a = allocator_type()) | |
983 | : m_holder(a) | |
984 | { | |
985 | this->assign(il.begin(), il.end()); | |
986 | } | |
987 | #endif | |
988 | ||
989 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
990 | ||
991 | //! <b>Effects</b>: Move constructor. Moves x's resources to *this. | |
992 | //! | |
993 | //! <b>Throws</b>: If T's move constructor or allocation throws | |
994 | //! | |
995 | //! <b>Complexity</b>: Linear. | |
996 | //! | |
997 | //! <b>Note</b>: Non-standard extension to support static_vector | |
998 | template<class OtherAllocator> | |
999 | vector(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x | |
1000 | , typename container_detail::enable_if_c | |
1001 | < container_detail::is_version<OtherAllocator, 0>::value>::type * = 0 | |
1002 | ) | |
1003 | : m_holder(boost::move(x.m_holder)) | |
1004 | {} | |
1005 | ||
1006 | #endif //!defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1007 | ||
1008 | //! <b>Effects</b>: Copy constructs a vector using the specified allocator. | |
1009 | //! | |
1010 | //! <b>Postcondition</b>: x == *this. | |
1011 | //! | |
1012 | //! <b>Throws</b>: If allocation | |
1013 | //! throws or T's copy constructor throws. | |
1014 | //! | |
1015 | //! <b>Complexity</b>: Linear to the elements x contains. | |
1016 | vector(const vector &x, const allocator_type &a) | |
1017 | : m_holder(container_detail::uninitialized_size, a, x.size()) | |
1018 | { | |
1019 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
1020 | this->num_alloc += x.size() != 0; | |
1021 | #endif | |
1022 | ::boost::container::uninitialized_copy_alloc_n_source | |
1023 | ( this->m_holder.alloc(), x.priv_raw_begin() | |
1024 | , x.size(), this->priv_raw_begin()); | |
1025 | } | |
1026 | ||
1027 | //! <b>Effects</b>: Move constructor using the specified allocator. | |
1028 | //! Moves x's resources to *this if a == allocator_type(). | |
1029 | //! Otherwise copies values from x to *this. | |
1030 | //! | |
1031 | //! <b>Throws</b>: If allocation or T's copy constructor throws. | |
1032 | //! | |
1033 | //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. | |
1034 | vector(BOOST_RV_REF(vector) x, const allocator_type &a) | |
1035 | : m_holder( container_detail::uninitialized_size, a | |
1036 | , is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true) ? 0 : x.size() | |
1037 | ) | |
1038 | { | |
1039 | if(is_propagable_from(x.get_stored_allocator(), x.m_holder.start(), a, true)){ | |
1040 | this->m_holder.steal_resources(x.m_holder); | |
1041 | } | |
1042 | else{ | |
1043 | const size_type n = x.size(); | |
1044 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
1045 | this->num_alloc += n != 0; | |
1046 | #endif | |
1047 | ::boost::container::uninitialized_move_alloc_n_source | |
1048 | ( this->m_holder.alloc(), x.priv_raw_begin() | |
1049 | , n, this->priv_raw_begin()); | |
1050 | } | |
1051 | } | |
1052 | ||
1053 | //! <b>Effects</b>: Destroys the vector. All stored values are destroyed | |
1054 | //! and used memory is deallocated. | |
1055 | //! | |
1056 | //! <b>Throws</b>: Nothing. | |
1057 | //! | |
1058 | //! <b>Complexity</b>: Linear to the number of elements. | |
1059 | ~vector() BOOST_NOEXCEPT_OR_NOTHROW | |
1060 | { | |
1061 | boost::container::destroy_alloc_n | |
1062 | (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size); | |
1063 | //vector_alloc_holder deallocates the data | |
1064 | } | |
1065 | ||
1066 | //! <b>Effects</b>: Makes *this contain the same elements as x. | |
1067 | //! | |
1068 | //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy | |
1069 | //! of each of x's elements. | |
1070 | //! | |
1071 | //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws. | |
1072 | //! | |
1073 | //! <b>Complexity</b>: Linear to the number of elements in x. | |
1074 | BOOST_CONTAINER_FORCEINLINE vector& operator=(BOOST_COPY_ASSIGN_REF(vector) x) | |
1075 | { | |
1076 | if (&x != this){ | |
1077 | this->priv_copy_assign(x); | |
1078 | } | |
1079 | return *this; | |
1080 | } | |
1081 | ||
1082 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1083 | //! <b>Effects</b>: Make *this container contains elements from il. | |
1084 | //! | |
1085 | //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). | |
1086 | BOOST_CONTAINER_FORCEINLINE vector& operator=(std::initializer_list<value_type> il) | |
1087 | { | |
1088 | this->assign(il.begin(), il.end()); | |
1089 | return *this; | |
1090 | } | |
1091 | #endif | |
1092 | ||
1093 | //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. | |
1094 | //! | |
1095 | //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had | |
1096 | //! before the function. | |
1097 | //! | |
1098 | //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment | |
1099 | //! is false and (allocation throws or value_type's move constructor throws) | |
1100 | //! | |
1101 | //! <b>Complexity</b>: Constant if allocator_traits_type:: | |
1102 | //! propagate_on_container_move_assignment is true or | |
1103 | //! this->get>allocator() == x.get_allocator(). Linear otherwise. | |
1104 | BOOST_CONTAINER_FORCEINLINE vector& operator=(BOOST_RV_REF(vector) x) | |
1105 | BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value | |
1106 | || allocator_traits_type::is_always_equal::value) | |
1107 | { | |
1108 | BOOST_ASSERT(&x != this); | |
1109 | this->priv_move_assign(boost::move(x)); | |
1110 | return *this; | |
1111 | } | |
1112 | ||
1113 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1114 | ||
1115 | //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. | |
1116 | //! | |
1117 | //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had | |
1118 | //! before the function. | |
1119 | //! | |
1120 | //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws | |
1121 | //! | |
1122 | //! <b>Complexity</b>: Linear. | |
1123 | //! | |
1124 | //! <b>Note</b>: Non-standard extension to support static_vector | |
1125 | template<class OtherAllocator> | |
1126 | BOOST_CONTAINER_FORCEINLINE typename container_detail::enable_if_and | |
1127 | < vector& | |
1128 | , container_detail::is_version<OtherAllocator, 0> | |
1129 | , container_detail::is_different<OtherAllocator, allocator_type> | |
1130 | >::type | |
1131 | operator=(BOOST_RV_REF_BEG vector<value_type, OtherAllocator> BOOST_RV_REF_END x) | |
1132 | { | |
1133 | this->priv_move_assign(boost::move(x)); | |
1134 | return *this; | |
1135 | } | |
1136 | ||
1137 | //! <b>Effects</b>: Copy assignment. All x's values are copied to *this. | |
1138 | //! | |
1139 | //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had | |
1140 | //! before the function. | |
1141 | //! | |
1142 | //! <b>Throws</b>: If move constructor/assignment of T throws or allocation throws | |
1143 | //! | |
1144 | //! <b>Complexity</b>: Linear. | |
1145 | //! | |
1146 | //! <b>Note</b>: Non-standard extension to support static_vector | |
1147 | template<class OtherAllocator> | |
1148 | BOOST_CONTAINER_FORCEINLINE typename container_detail::enable_if_and | |
1149 | < vector& | |
1150 | , container_detail::is_version<OtherAllocator, 0> | |
1151 | , container_detail::is_different<OtherAllocator, allocator_type> | |
1152 | >::type | |
1153 | operator=(const vector<value_type, OtherAllocator> &x) | |
1154 | { | |
1155 | this->priv_copy_assign(x); | |
1156 | return *this; | |
1157 | } | |
1158 | ||
1159 | #endif | |
1160 | ||
1161 | //! <b>Effects</b>: Assigns the the range [first, last) to *this. | |
1162 | //! | |
1163 | //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or | |
1164 | //! T's constructor/assignment from dereferencing InpIt throws. | |
1165 | //! | |
1166 | //! <b>Complexity</b>: Linear to n. | |
1167 | template <class InIt> | |
1168 | void assign(InIt first, InIt last | |
1169 | BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or | |
1170 | < void | |
1171 | BOOST_MOVE_I container_detail::is_convertible<InIt BOOST_MOVE_I size_type> | |
1172 | BOOST_MOVE_I container_detail::and_ | |
1173 | < container_detail::is_different<alloc_version BOOST_MOVE_I version_0> | |
1174 | BOOST_MOVE_I container_detail::is_not_input_iterator<InIt> | |
1175 | > | |
1176 | >::type * = 0) | |
1177 | ) | |
1178 | { | |
1179 | //Overwrite all elements we can from [first, last) | |
1180 | iterator cur = this->begin(); | |
1181 | const iterator end_it = this->end(); | |
1182 | for ( ; first != last && cur != end_it; ++cur, ++first){ | |
1183 | *cur = *first; | |
1184 | } | |
1185 | ||
1186 | if (first == last){ | |
1187 | //There are no more elements in the sequence, erase remaining | |
1188 | T* const end_pos = this->priv_raw_end(); | |
1189 | const size_type n = static_cast<size_type>(end_pos - container_detail::iterator_to_raw_pointer(cur)); | |
1190 | this->priv_destroy_last_n(n); | |
1191 | } | |
1192 | else{ | |
1193 | //There are more elements in the range, insert the remaining ones | |
1194 | this->insert(this->cend(), first, last); | |
1195 | } | |
1196 | } | |
1197 | ||
1198 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1199 | //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this. | |
1200 | //! | |
1201 | //! <b>Throws</b>: If memory allocation throws or | |
1202 | //! T's constructor from dereferencing iniializer_list iterator throws. | |
1203 | //! | |
1204 | BOOST_CONTAINER_FORCEINLINE void assign(std::initializer_list<T> il) | |
1205 | { | |
1206 | this->assign(il.begin(), il.end()); | |
1207 | } | |
1208 | #endif | |
1209 | ||
1210 | //! <b>Effects</b>: Assigns the the range [first, last) to *this. | |
1211 | //! | |
1212 | //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment or | |
1213 | //! T's constructor/assignment from dereferencing InpIt throws. | |
1214 | //! | |
1215 | //! <b>Complexity</b>: Linear to n. | |
1216 | template <class FwdIt> | |
1217 | void assign(FwdIt first, FwdIt last | |
1218 | BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename container_detail::disable_if_or | |
1219 | < void | |
1220 | BOOST_MOVE_I container_detail::is_same<alloc_version BOOST_MOVE_I version_0> | |
1221 | BOOST_MOVE_I container_detail::is_convertible<FwdIt BOOST_MOVE_I size_type> | |
1222 | BOOST_MOVE_I container_detail::is_input_iterator<FwdIt> | |
1223 | >::type * = 0) | |
1224 | ) | |
1225 | { | |
1226 | //For Fwd iterators the standard only requires EmplaceConstructible and assignable from *first | |
1227 | //so we can't do any backwards allocation | |
1228 | const size_type input_sz = static_cast<size_type>(boost::container::iterator_distance(first, last)); | |
1229 | const size_type old_capacity = this->capacity(); | |
1230 | if(input_sz > old_capacity){ //If input range is too big, we need to reallocate | |
1231 | size_type real_cap = 0; | |
1232 | pointer reuse(this->m_holder.start()); | |
1233 | pointer const ret(this->m_holder.allocation_command(allocate_new|expand_fwd, input_sz, real_cap = input_sz, reuse)); | |
1234 | if(!reuse){ //New allocation, just emplace new values | |
1235 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
1236 | ++this->num_alloc; | |
1237 | #endif | |
1238 | pointer const old_p = this->m_holder.start(); | |
1239 | if(old_p){ | |
1240 | this->priv_destroy_all(); | |
1241 | this->m_holder.alloc().deallocate(old_p, old_capacity); | |
1242 | } | |
1243 | this->m_holder.start(ret); | |
1244 | this->m_holder.capacity(real_cap); | |
1245 | this->m_holder.m_size = 0; | |
1246 | this->priv_uninitialized_construct_at_end(first, last); | |
1247 | return; | |
1248 | } | |
1249 | else{ | |
1250 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
1251 | ++this->num_expand_fwd; | |
1252 | #endif | |
1253 | this->m_holder.capacity(real_cap); | |
1254 | //Forward expansion, use assignment + back deletion/construction that comes later | |
1255 | } | |
1256 | } | |
1257 | //Overwrite all elements we can from [first, last) | |
1258 | iterator cur = this->begin(); | |
1259 | const iterator end_it = this->end(); | |
1260 | for ( ; first != last && cur != end_it; ++cur, ++first){ | |
1261 | *cur = *first; | |
1262 | } | |
1263 | ||
1264 | if (first == last){ | |
1265 | //There are no more elements in the sequence, erase remaining | |
1266 | this->priv_destroy_last_n(this->size() - input_sz); | |
1267 | } | |
1268 | else{ | |
1269 | //Uninitialized construct at end the remaining range | |
1270 | this->priv_uninitialized_construct_at_end(first, last); | |
1271 | } | |
1272 | } | |
1273 | ||
1274 | //! <b>Effects</b>: Assigns the n copies of val to *this. | |
1275 | //! | |
1276 | //! <b>Throws</b>: If memory allocation throws or | |
1277 | //! T's copy/move constructor/assignment throws. | |
1278 | //! | |
1279 | //! <b>Complexity</b>: Linear to n. | |
1280 | BOOST_CONTAINER_FORCEINLINE void assign(size_type n, const value_type& val) | |
1281 | { this->assign(cvalue_iterator(val, n), cvalue_iterator()); } | |
1282 | ||
1283 | //! <b>Effects</b>: Returns a copy of the internal allocator. | |
1284 | //! | |
1285 | //! <b>Throws</b>: If allocator's copy constructor throws. | |
1286 | //! | |
1287 | //! <b>Complexity</b>: Constant. | |
1288 | allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
1289 | { return this->m_holder.alloc(); } | |
1290 | ||
1291 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
1292 | //! | |
1293 | //! <b>Throws</b>: Nothing | |
1294 | //! | |
1295 | //! <b>Complexity</b>: Constant. | |
1296 | //! | |
1297 | //! <b>Note</b>: Non-standard extension. | |
1298 | BOOST_CONTAINER_FORCEINLINE stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW | |
1299 | { return this->m_holder.alloc(); } | |
1300 | ||
1301 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
1302 | //! | |
1303 | //! <b>Throws</b>: Nothing | |
1304 | //! | |
1305 | //! <b>Complexity</b>: Constant. | |
1306 | //! | |
1307 | //! <b>Note</b>: Non-standard extension. | |
1308 | BOOST_CONTAINER_FORCEINLINE const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
1309 | { return this->m_holder.alloc(); } | |
1310 | ||
1311 | ////////////////////////////////////////////// | |
1312 | // | |
1313 | // iterators | |
1314 | // | |
1315 | ////////////////////////////////////////////// | |
1316 | ||
1317 | //! <b>Effects</b>: Returns an iterator to the first element contained in the vector. | |
1318 | //! | |
1319 | //! <b>Throws</b>: Nothing. | |
1320 | //! | |
1321 | //! <b>Complexity</b>: Constant. | |
1322 | BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW | |
1323 | { return iterator(this->m_holder.start()); } | |
1324 | ||
1325 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector. | |
1326 | //! | |
1327 | //! <b>Throws</b>: Nothing. | |
1328 | //! | |
1329 | //! <b>Complexity</b>: Constant. | |
1330 | BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1331 | { return const_iterator(this->m_holder.start()); } | |
1332 | ||
1333 | //! <b>Effects</b>: Returns an iterator to the end of the vector. | |
1334 | //! | |
1335 | //! <b>Throws</b>: Nothing. | |
1336 | //! | |
1337 | //! <b>Complexity</b>: Constant. | |
1338 | BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW | |
1339 | { return iterator(this->m_holder.start() + this->m_holder.m_size); } | |
1340 | ||
1341 | //! <b>Effects</b>: Returns a const_iterator to the end of the vector. | |
1342 | //! | |
1343 | //! <b>Throws</b>: Nothing. | |
1344 | //! | |
1345 | //! <b>Complexity</b>: Constant. | |
1346 | BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW | |
1347 | { return this->cend(); } | |
1348 | ||
1349 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning | |
1350 | //! of the reversed vector. | |
1351 | //! | |
1352 | //! <b>Throws</b>: Nothing. | |
1353 | //! | |
1354 | //! <b>Complexity</b>: Constant. | |
1355 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW | |
1356 | { return reverse_iterator(this->end()); } | |
1357 | ||
1358 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
1359 | //! of the reversed vector. | |
1360 | //! | |
1361 | //! <b>Throws</b>: Nothing. | |
1362 | //! | |
1363 | //! <b>Complexity</b>: Constant. | |
1364 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1365 | { return this->crbegin(); } | |
1366 | ||
1367 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end | |
1368 | //! of the reversed vector. | |
1369 | //! | |
1370 | //! <b>Throws</b>: Nothing. | |
1371 | //! | |
1372 | //! <b>Complexity</b>: Constant. | |
1373 | BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW | |
1374 | { return reverse_iterator(this->begin()); } | |
1375 | ||
1376 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
1377 | //! of the reversed vector. | |
1378 | //! | |
1379 | //! <b>Throws</b>: Nothing. | |
1380 | //! | |
1381 | //! <b>Complexity</b>: Constant. | |
1382 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1383 | { return this->crend(); } | |
1384 | ||
1385 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector. | |
1386 | //! | |
1387 | //! <b>Throws</b>: Nothing. | |
1388 | //! | |
1389 | //! <b>Complexity</b>: Constant. | |
1390 | BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1391 | { return const_iterator(this->m_holder.start()); } | |
1392 | ||
1393 | //! <b>Effects</b>: Returns a const_iterator to the end of the vector. | |
1394 | //! | |
1395 | //! <b>Throws</b>: Nothing. | |
1396 | //! | |
1397 | //! <b>Complexity</b>: Constant. | |
1398 | BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1399 | { return const_iterator(this->m_holder.start() + this->m_holder.m_size); } | |
1400 | ||
1401 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
1402 | //! of the reversed vector. | |
1403 | //! | |
1404 | //! <b>Throws</b>: Nothing. | |
1405 | //! | |
1406 | //! <b>Complexity</b>: Constant. | |
1407 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1408 | { return const_reverse_iterator(this->end());} | |
1409 | ||
1410 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
1411 | //! of the reversed vector. | |
1412 | //! | |
1413 | //! <b>Throws</b>: Nothing. | |
1414 | //! | |
1415 | //! <b>Complexity</b>: Constant. | |
1416 | BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1417 | { return const_reverse_iterator(this->begin()); } | |
1418 | ||
1419 | ////////////////////////////////////////////// | |
1420 | // | |
1421 | // capacity | |
1422 | // | |
1423 | ////////////////////////////////////////////// | |
1424 | ||
1425 | //! <b>Effects</b>: Returns true if the vector contains no elements. | |
1426 | //! | |
1427 | //! <b>Throws</b>: Nothing. | |
1428 | //! | |
1429 | //! <b>Complexity</b>: Constant. | |
1430 | BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW | |
1431 | { return !this->m_holder.m_size; } | |
1432 | ||
1433 | //! <b>Effects</b>: Returns the number of the elements contained in the vector. | |
1434 | //! | |
1435 | //! <b>Throws</b>: Nothing. | |
1436 | //! | |
1437 | //! <b>Complexity</b>: Constant. | |
1438 | BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW | |
1439 | { return this->m_holder.m_size; } | |
1440 | ||
1441 | //! <b>Effects</b>: Returns the largest possible size of the vector. | |
1442 | //! | |
1443 | //! <b>Throws</b>: Nothing. | |
1444 | //! | |
1445 | //! <b>Complexity</b>: Constant. | |
1446 | BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW | |
1447 | { return allocator_traits_type::max_size(this->m_holder.alloc()); } | |
1448 | ||
1449 | //! <b>Effects</b>: Inserts or erases elements at the end such that | |
1450 | //! the size becomes n. New elements are value initialized. | |
1451 | //! | |
1452 | //! <b>Throws</b>: If memory allocation throws, or T's copy/move or value initialization throws. | |
1453 | //! | |
1454 | //! <b>Complexity</b>: Linear to the difference between size() and new_size. | |
1455 | void resize(size_type new_size) | |
1456 | { this->priv_resize(new_size, value_init); } | |
1457 | ||
1458 | //! <b>Effects</b>: Inserts or erases elements at the end such that | |
1459 | //! the size becomes n. New elements are default initialized. | |
1460 | //! | |
1461 | //! <b>Throws</b>: If memory allocation throws, or T's copy/move or default initialization throws. | |
1462 | //! | |
1463 | //! <b>Complexity</b>: Linear to the difference between size() and new_size. | |
1464 | //! | |
1465 | //! <b>Note</b>: Non-standard extension | |
1466 | void resize(size_type new_size, default_init_t) | |
1467 | { this->priv_resize(new_size, default_init); } | |
1468 | ||
1469 | //! <b>Effects</b>: Inserts or erases elements at the end such that | |
1470 | //! the size becomes n. New elements are copy constructed from x. | |
1471 | //! | |
1472 | //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws. | |
1473 | //! | |
1474 | //! <b>Complexity</b>: Linear to the difference between size() and new_size. | |
1475 | void resize(size_type new_size, const T& x) | |
1476 | { this->priv_resize(new_size, x); } | |
1477 | ||
1478 | //! <b>Effects</b>: Number of elements for which memory has been allocated. | |
1479 | //! capacity() is always greater than or equal to size(). | |
1480 | //! | |
1481 | //! <b>Throws</b>: Nothing. | |
1482 | //! | |
1483 | //! <b>Complexity</b>: Constant. | |
1484 | BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW | |
1485 | { return this->m_holder.capacity(); } | |
1486 | ||
1487 | //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no | |
1488 | //! effect. Otherwise, it is a request for allocation of additional memory. | |
1489 | //! If the request is successful, then capacity() is greater than or equal to | |
1490 | //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. | |
1491 | //! | |
1492 | //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws. | |
1493 | BOOST_CONTAINER_FORCEINLINE void reserve(size_type new_cap) | |
1494 | { | |
1495 | if (this->capacity() < new_cap){ | |
1496 | this->priv_reserve_no_capacity(new_cap, alloc_version()); | |
1497 | } | |
1498 | } | |
1499 | ||
1500 | //! <b>Effects</b>: Tries to deallocate the excess of memory created | |
1501 | //! with previous allocations. The size of the vector is unchanged | |
1502 | //! | |
1503 | //! <b>Throws</b>: If memory allocation throws, or T's copy/move constructor throws. | |
1504 | //! | |
1505 | //! <b>Complexity</b>: Linear to size(). | |
1506 | BOOST_CONTAINER_FORCEINLINE void shrink_to_fit() | |
1507 | { this->priv_shrink_to_fit(alloc_version()); } | |
1508 | ||
1509 | ////////////////////////////////////////////// | |
1510 | // | |
1511 | // element access | |
1512 | // | |
1513 | ////////////////////////////////////////////// | |
1514 | ||
1515 | //! <b>Requires</b>: !empty() | |
1516 | //! | |
1517 | //! <b>Effects</b>: Returns a reference to the first | |
1518 | //! element of the container. | |
1519 | //! | |
1520 | //! <b>Throws</b>: Nothing. | |
1521 | //! | |
1522 | //! <b>Complexity</b>: Constant. | |
1523 | reference front() BOOST_NOEXCEPT_OR_NOTHROW | |
1524 | { | |
1525 | BOOST_ASSERT(!this->empty()); | |
1526 | return *this->m_holder.start(); | |
1527 | } | |
1528 | ||
1529 | //! <b>Requires</b>: !empty() | |
1530 | //! | |
1531 | //! <b>Effects</b>: Returns a const reference to the first | |
1532 | //! element of the container. | |
1533 | //! | |
1534 | //! <b>Throws</b>: Nothing. | |
1535 | //! | |
1536 | //! <b>Complexity</b>: Constant. | |
1537 | const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW | |
1538 | { | |
1539 | BOOST_ASSERT(!this->empty()); | |
1540 | return *this->m_holder.start(); | |
1541 | } | |
1542 | ||
1543 | //! <b>Requires</b>: !empty() | |
1544 | //! | |
1545 | //! <b>Effects</b>: Returns a reference to the last | |
1546 | //! element of the container. | |
1547 | //! | |
1548 | //! <b>Throws</b>: Nothing. | |
1549 | //! | |
1550 | //! <b>Complexity</b>: Constant. | |
1551 | reference back() BOOST_NOEXCEPT_OR_NOTHROW | |
1552 | { | |
1553 | BOOST_ASSERT(!this->empty()); | |
1554 | return this->m_holder.start()[this->m_holder.m_size - 1]; | |
1555 | } | |
1556 | ||
1557 | //! <b>Requires</b>: !empty() | |
1558 | //! | |
1559 | //! <b>Effects</b>: Returns a const reference to the last | |
1560 | //! element of the container. | |
1561 | //! | |
1562 | //! <b>Throws</b>: Nothing. | |
1563 | //! | |
1564 | //! <b>Complexity</b>: Constant. | |
1565 | const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW | |
1566 | { | |
1567 | BOOST_ASSERT(!this->empty()); | |
1568 | return this->m_holder.start()[this->m_holder.m_size - 1]; | |
1569 | } | |
1570 | ||
1571 | //! <b>Requires</b>: size() > n. | |
1572 | //! | |
1573 | //! <b>Effects</b>: Returns a reference to the nth element | |
1574 | //! from the beginning of the container. | |
1575 | //! | |
1576 | //! <b>Throws</b>: Nothing. | |
1577 | //! | |
1578 | //! <b>Complexity</b>: Constant. | |
1579 | reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
1580 | { | |
1581 | BOOST_ASSERT(this->m_holder.m_size > n); | |
1582 | return this->m_holder.start()[n]; | |
1583 | } | |
1584 | ||
1585 | //! <b>Requires</b>: size() > n. | |
1586 | //! | |
1587 | //! <b>Effects</b>: Returns a const reference to the nth element | |
1588 | //! from the beginning of the container. | |
1589 | //! | |
1590 | //! <b>Throws</b>: Nothing. | |
1591 | //! | |
1592 | //! <b>Complexity</b>: Constant. | |
1593 | const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
1594 | { | |
1595 | BOOST_ASSERT(this->m_holder.m_size > n); | |
1596 | return this->m_holder.start()[n]; | |
1597 | } | |
1598 | ||
1599 | //! <b>Requires</b>: size() >= n. | |
1600 | //! | |
1601 | //! <b>Effects</b>: Returns an iterator to the nth element | |
1602 | //! from the beginning of the container. Returns end() | |
1603 | //! if n == size(). | |
1604 | //! | |
1605 | //! <b>Throws</b>: Nothing. | |
1606 | //! | |
1607 | //! <b>Complexity</b>: Constant. | |
1608 | //! | |
1609 | //! <b>Note</b>: Non-standard extension | |
1610 | iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
1611 | { | |
1612 | BOOST_ASSERT(this->m_holder.m_size >= n); | |
1613 | return iterator(this->m_holder.start()+n); | |
1614 | } | |
1615 | ||
1616 | //! <b>Requires</b>: size() >= n. | |
1617 | //! | |
1618 | //! <b>Effects</b>: Returns a const_iterator to the nth element | |
1619 | //! from the beginning of the container. Returns end() | |
1620 | //! if n == size(). | |
1621 | //! | |
1622 | //! <b>Throws</b>: Nothing. | |
1623 | //! | |
1624 | //! <b>Complexity</b>: Constant. | |
1625 | //! | |
1626 | //! <b>Note</b>: Non-standard extension | |
1627 | const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
1628 | { | |
1629 | BOOST_ASSERT(this->m_holder.m_size >= n); | |
1630 | return const_iterator(this->m_holder.start()+n); | |
1631 | } | |
1632 | ||
1633 | //! <b>Requires</b>: begin() <= p <= end(). | |
1634 | //! | |
1635 | //! <b>Effects</b>: Returns the index of the element pointed by p | |
1636 | //! and size() if p == end(). | |
1637 | //! | |
1638 | //! <b>Throws</b>: Nothing. | |
1639 | //! | |
1640 | //! <b>Complexity</b>: Constant. | |
1641 | //! | |
1642 | //! <b>Note</b>: Non-standard extension | |
1643 | size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW | |
1644 | { | |
1645 | //Range check assert done in priv_index_of | |
1646 | return this->priv_index_of(vector_iterator_get_ptr(p)); | |
1647 | } | |
1648 | ||
1649 | //! <b>Requires</b>: begin() <= p <= end(). | |
1650 | //! | |
1651 | //! <b>Effects</b>: Returns the index of the element pointed by p | |
1652 | //! and size() if p == end(). | |
1653 | //! | |
1654 | //! <b>Throws</b>: Nothing. | |
1655 | //! | |
1656 | //! <b>Complexity</b>: Constant. | |
1657 | //! | |
1658 | //! <b>Note</b>: Non-standard extension | |
1659 | size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW | |
1660 | { | |
1661 | //Range check assert done in priv_index_of | |
1662 | return this->priv_index_of(vector_iterator_get_ptr(p)); | |
1663 | } | |
1664 | ||
1665 | //! <b>Requires</b>: size() > n. | |
1666 | //! | |
1667 | //! <b>Effects</b>: Returns a reference to the nth element | |
1668 | //! from the beginning of the container. | |
1669 | //! | |
1670 | //! <b>Throws</b>: std::range_error if n >= size() | |
1671 | //! | |
1672 | //! <b>Complexity</b>: Constant. | |
1673 | reference at(size_type n) | |
1674 | { | |
1675 | this->priv_throw_if_out_of_range(n); | |
1676 | return this->m_holder.start()[n]; | |
1677 | } | |
1678 | ||
1679 | //! <b>Requires</b>: size() > n. | |
1680 | //! | |
1681 | //! <b>Effects</b>: Returns a const reference to the nth element | |
1682 | //! from the beginning of the container. | |
1683 | //! | |
1684 | //! <b>Throws</b>: std::range_error if n >= size() | |
1685 | //! | |
1686 | //! <b>Complexity</b>: Constant. | |
1687 | const_reference at(size_type n) const | |
1688 | { | |
1689 | this->priv_throw_if_out_of_range(n); | |
1690 | return this->m_holder.start()[n]; | |
1691 | } | |
1692 | ||
1693 | ////////////////////////////////////////////// | |
1694 | // | |
1695 | // data access | |
1696 | // | |
1697 | ////////////////////////////////////////////// | |
1698 | ||
1699 | //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range. | |
1700 | //! For a non-empty vector, data() == &front(). | |
1701 | //! | |
1702 | //! <b>Throws</b>: Nothing. | |
1703 | //! | |
1704 | //! <b>Complexity</b>: Constant. | |
1705 | T* data() BOOST_NOEXCEPT_OR_NOTHROW | |
1706 | { return this->priv_raw_begin(); } | |
1707 | ||
1708 | //! <b>Returns</b>: A pointer such that [data(),data() + size()) is a valid range. | |
1709 | //! For a non-empty vector, data() == &front(). | |
1710 | //! | |
1711 | //! <b>Throws</b>: Nothing. | |
1712 | //! | |
1713 | //! <b>Complexity</b>: Constant. | |
1714 | const T * data() const BOOST_NOEXCEPT_OR_NOTHROW | |
1715 | { return this->priv_raw_begin(); } | |
1716 | ||
1717 | ////////////////////////////////////////////// | |
1718 | // | |
1719 | // modifiers | |
1720 | // | |
1721 | ////////////////////////////////////////////// | |
1722 | ||
1723 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1724 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1725 | //! std::forward<Args>(args)... in the end of the vector. | |
1726 | //! | |
1727 | //! <b>Returns</b>: A reference to the created object. | |
1728 | //! | |
1729 | //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or | |
1730 | //! T's copy/move constructor throws. | |
1731 | //! | |
1732 | //! <b>Complexity</b>: Amortized constant time. | |
1733 | template<class ...Args> | |
1734 | BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_FWD_REF(Args)...args) | |
1735 | { | |
1736 | if (BOOST_LIKELY(this->room_enough())){ | |
1737 | //There is more memory, just construct a new object at the end | |
1738 | allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<Args>(args)...); | |
1739 | ++this->m_holder.m_size; | |
1740 | return *this->priv_raw_end(); | |
1741 | } | |
1742 | else{ | |
1743 | typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type; | |
1744 | return *this->priv_forward_range_insert_no_capacity | |
1745 | (this->back_ptr(), 1, type(::boost::forward<Args>(args)...), alloc_version()); | |
1746 | } | |
1747 | } | |
1748 | ||
1749 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1750 | //! std::forward<Args>(args)... in the end of the vector. | |
1751 | //! | |
1752 | //! <b>Throws</b>: If the in-place constructor throws. | |
1753 | //! | |
1754 | //! <b>Complexity</b>: Constant time. | |
1755 | //! | |
1756 | //! <b>Note</b>: Non-standard extension. | |
1757 | template<class ...Args> | |
1758 | BOOST_CONTAINER_FORCEINLINE bool stable_emplace_back(BOOST_FWD_REF(Args)...args) | |
1759 | { | |
1760 | const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u)); | |
1761 | if (BOOST_LIKELY(is_room_enough)){ | |
1762 | //There is more memory, just construct a new object at the end | |
1763 | allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<Args>(args)...); | |
1764 | ++this->m_holder.m_size; | |
1765 | } | |
1766 | return is_room_enough; | |
1767 | } | |
1768 | ||
1769 | //! <b>Requires</b>: position must be a valid iterator of *this. | |
1770 | //! | |
1771 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1772 | //! std::forward<Args>(args)... before position | |
1773 | //! | |
1774 | //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws or | |
1775 | //! T's copy/move constructor/assignment throws. | |
1776 | //! | |
1777 | //! <b>Complexity</b>: If position is end(), amortized constant time | |
1778 | //! Linear time otherwise. | |
1779 | template<class ...Args> | |
1780 | iterator emplace(const_iterator position, BOOST_FWD_REF(Args) ...args) | |
1781 | { | |
1782 | BOOST_ASSERT(this->priv_in_range_or_end(position)); | |
1783 | //Just call more general insert(pos, size, value) and return iterator | |
1784 | typedef container_detail::insert_emplace_proxy<Allocator, T*, Args...> type; | |
1785 | return this->priv_forward_range_insert( vector_iterator_get_ptr(position), 1 | |
1786 | , type(::boost::forward<Args>(args)...)); | |
1787 | } | |
1788 | ||
1789 | #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1790 | ||
1791 | #define BOOST_CONTAINER_VECTOR_EMPLACE_CODE(N) \ | |
1792 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1793 | BOOST_CONTAINER_FORCEINLINE reference emplace_back(BOOST_MOVE_UREF##N)\ | |
1794 | {\ | |
1795 | if (BOOST_LIKELY(this->room_enough())){\ | |
1796 | allocator_traits_type::construct (this->m_holder.alloc()\ | |
1797 | , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ | |
1798 | ++this->m_holder.m_size;\ | |
1799 | return *this->priv_raw_end();\ | |
1800 | }\ | |
1801 | else{\ | |
1802 | typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ | |
1803 | return *this->priv_forward_range_insert_no_capacity\ | |
1804 | ( this->back_ptr(), 1, type(BOOST_MOVE_FWD##N), alloc_version());\ | |
1805 | }\ | |
1806 | }\ | |
1807 | \ | |
1808 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1809 | BOOST_CONTAINER_FORCEINLINE bool stable_emplace_back(BOOST_MOVE_UREF##N)\ | |
1810 | {\ | |
1811 | const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));\ | |
1812 | if (BOOST_LIKELY(is_room_enough)){\ | |
1813 | allocator_traits_type::construct (this->m_holder.alloc()\ | |
1814 | , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ | |
1815 | ++this->m_holder.m_size;\ | |
1816 | }\ | |
1817 | return is_room_enough;\ | |
1818 | }\ | |
1819 | \ | |
1820 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
1821 | iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1822 | {\ | |
1823 | BOOST_ASSERT(this->priv_in_range_or_end(pos));\ | |
1824 | typedef container_detail::insert_emplace_proxy_arg##N<Allocator, T* BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ | |
1825 | return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), 1, type(BOOST_MOVE_FWD##N));\ | |
1826 | }\ | |
1827 | // | |
1828 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_VECTOR_EMPLACE_CODE) | |
1829 | #undef BOOST_CONTAINER_VECTOR_EMPLACE_CODE | |
1830 | ||
1831 | #endif | |
1832 | ||
1833 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1834 | //! <b>Effects</b>: Inserts a copy of x at the end of the vector. | |
1835 | //! | |
1836 | //! <b>Throws</b>: If memory allocation throws or | |
1837 | //! T's copy/move constructor throws. | |
1838 | //! | |
1839 | //! <b>Complexity</b>: Amortized constant time. | |
1840 | void push_back(const T &x); | |
1841 | ||
1842 | //! <b>Effects</b>: Constructs a new element in the end of the vector | |
1843 | //! and moves the resources of x to this new element. | |
1844 | //! | |
1845 | //! <b>Throws</b>: If memory allocation throws or | |
1846 | //! T's copy/move constructor throws. | |
1847 | //! | |
1848 | //! <b>Complexity</b>: Amortized constant time. | |
1849 | void push_back(T &&x); | |
1850 | #else | |
1851 | BOOST_CONTAINER_FORCEINLINE BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) | |
1852 | #endif | |
1853 | ||
1854 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1855 | //! <b>Requires</b>: position must be a valid iterator of *this. | |
1856 | //! | |
1857 | //! <b>Effects</b>: Insert a copy of x before position. | |
1858 | //! | |
1859 | //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor/assignment throws. | |
1860 | //! | |
1861 | //! <b>Complexity</b>: If position is end(), amortized constant time | |
1862 | //! Linear time otherwise. | |
1863 | iterator insert(const_iterator position, const T &x); | |
1864 | ||
1865 | //! <b>Requires</b>: position must be a valid iterator of *this. | |
1866 | //! | |
1867 | //! <b>Effects</b>: Insert a new element before position with x's resources. | |
1868 | //! | |
1869 | //! <b>Throws</b>: If memory allocation throws. | |
1870 | //! | |
1871 | //! <b>Complexity</b>: If position is end(), amortized constant time | |
1872 | //! Linear time otherwise. | |
1873 | iterator insert(const_iterator position, T &&x); | |
1874 | #else | |
1875 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) | |
1876 | #endif | |
1877 | ||
1878 | //! <b>Requires</b>: p must be a valid iterator of *this. | |
1879 | //! | |
1880 | //! <b>Effects</b>: Insert n copies of x before pos. | |
1881 | //! | |
1882 | //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0. | |
1883 | //! | |
1884 | //! <b>Throws</b>: If memory allocation throws or T's copy/move constructor throws. | |
1885 | //! | |
1886 | //! <b>Complexity</b>: Linear to n. | |
1887 | iterator insert(const_iterator p, size_type n, const T& x) | |
1888 | { | |
1889 | BOOST_ASSERT(this->priv_in_range_or_end(p)); | |
1890 | container_detail::insert_n_copies_proxy<Allocator, T*> proxy(x); | |
1891 | return this->priv_forward_range_insert(vector_iterator_get_ptr(p), n, proxy); | |
1892 | } | |
1893 | ||
1894 | //! <b>Requires</b>: p must be a valid iterator of *this. | |
1895 | //! | |
1896 | //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. | |
1897 | //! | |
1898 | //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last. | |
1899 | //! | |
1900 | //! <b>Throws</b>: If memory allocation throws, T's constructor from a | |
1901 | //! dereferenced InpIt throws or T's copy/move constructor/assignment throws. | |
1902 | //! | |
1903 | //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last). | |
1904 | template <class InIt> | |
1905 | iterator insert(const_iterator pos, InIt first, InIt last | |
1906 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1907 | , typename container_detail::disable_if_or | |
1908 | < void | |
1909 | , container_detail::is_convertible<InIt, size_type> | |
1910 | , container_detail::is_not_input_iterator<InIt> | |
1911 | >::type * = 0 | |
1912 | #endif | |
1913 | ) | |
1914 | { | |
1915 | BOOST_ASSERT(this->priv_in_range_or_end(pos)); | |
1916 | const size_type n_pos = pos - this->cbegin(); | |
1917 | iterator it(vector_iterator_get_ptr(pos)); | |
1918 | for(;first != last; ++first){ | |
1919 | it = this->emplace(it, *first); | |
1920 | ++it; | |
1921 | } | |
1922 | return iterator(this->m_holder.start() + n_pos); | |
1923 | } | |
1924 | ||
1925 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1926 | template <class FwdIt> | |
1927 | iterator insert(const_iterator pos, FwdIt first, FwdIt last | |
1928 | , typename container_detail::disable_if_or | |
1929 | < void | |
1930 | , container_detail::is_convertible<FwdIt, size_type> | |
1931 | , container_detail::is_input_iterator<FwdIt> | |
1932 | >::type * = 0 | |
1933 | ) | |
1934 | { | |
1935 | BOOST_ASSERT(this->priv_in_range_or_end(pos)); | |
1936 | container_detail::insert_range_proxy<Allocator, FwdIt, T*> proxy(first); | |
1937 | return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), boost::container::iterator_distance(first, last), proxy); | |
1938 | } | |
1939 | #endif | |
1940 | ||
1941 | //! <b>Requires</b>: p must be a valid iterator of *this. num, must | |
1942 | //! be equal to boost::container::iterator_distance(first, last) | |
1943 | //! | |
1944 | //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. | |
1945 | //! | |
1946 | //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last. | |
1947 | //! | |
1948 | //! <b>Throws</b>: If memory allocation throws, T's constructor from a | |
1949 | //! dereferenced InpIt throws or T's copy/move constructor/assignment throws. | |
1950 | //! | |
1951 | //! <b>Complexity</b>: Linear to boost::container::iterator_distance [first, last). | |
1952 | //! | |
1953 | //! <b>Note</b>: This function avoids a linear operation to calculate boost::container::iterator_distance[first, last) | |
1954 | //! for forward and bidirectional iterators, and a one by one insertion for input iterators. This is a | |
1955 | //! a non-standard extension. | |
1956 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1957 | template <class InIt> | |
1958 | iterator insert(const_iterator pos, size_type num, InIt first, InIt last) | |
1959 | { | |
1960 | BOOST_ASSERT(this->priv_in_range_or_end(pos)); | |
1961 | BOOST_ASSERT(container_detail::is_input_iterator<InIt>::value || | |
1962 | num == static_cast<size_type>(boost::container::iterator_distance(first, last))); | |
1963 | (void)last; | |
1964 | container_detail::insert_range_proxy<Allocator, InIt, T*> proxy(first); | |
1965 | return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), num, proxy); | |
1966 | } | |
1967 | #endif | |
1968 | ||
1969 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1970 | //! <b>Requires</b>: position must be a valid iterator of *this. | |
1971 | //! | |
1972 | //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before position. | |
1973 | //! | |
1974 | //! <b>Returns</b>: an iterator to the first inserted element or position if first == last. | |
1975 | //! | |
1976 | //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). | |
1977 | iterator insert(const_iterator position, std::initializer_list<value_type> il) | |
1978 | { | |
1979 | //Assertion done in insert() | |
1980 | return this->insert(position, il.begin(), il.end()); | |
1981 | } | |
1982 | #endif | |
1983 | ||
1984 | //! <b>Effects</b>: Removes the last element from the container. | |
1985 | //! | |
1986 | //! <b>Throws</b>: Nothing. | |
1987 | //! | |
1988 | //! <b>Complexity</b>: Constant time. | |
1989 | void pop_back() BOOST_NOEXCEPT_OR_NOTHROW | |
1990 | { | |
1991 | BOOST_ASSERT(!this->empty()); | |
1992 | //Destroy last element | |
1993 | this->priv_destroy_last(); | |
1994 | } | |
1995 | ||
1996 | //! <b>Effects</b>: Erases the element at position pos. | |
1997 | //! | |
1998 | //! <b>Throws</b>: Nothing. | |
1999 | //! | |
2000 | //! <b>Complexity</b>: Linear to the elements between pos and the | |
2001 | //! last element. Constant if pos is the last element. | |
2002 | iterator erase(const_iterator position) | |
2003 | { | |
2004 | BOOST_ASSERT(this->priv_in_range(position)); | |
2005 | const pointer p = vector_iterator_get_ptr(position); | |
2006 | T *const pos_ptr = container_detail::to_raw_pointer(p); | |
2007 | T *const beg_ptr = this->priv_raw_begin(); | |
2008 | T *const new_end_ptr = ::boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr); | |
2009 | //Move elements forward and destroy last | |
2010 | this->priv_destroy_last(pos_ptr == new_end_ptr); | |
2011 | return iterator(p); | |
2012 | } | |
2013 | ||
2014 | //! <b>Effects</b>: Erases the elements pointed by [first, last). | |
2015 | //! | |
2016 | //! <b>Throws</b>: Nothing. | |
2017 | //! | |
2018 | //! <b>Complexity</b>: Linear to the distance between first and last | |
2019 | //! plus linear to the elements between pos and the last element. | |
2020 | iterator erase(const_iterator first, const_iterator last) | |
2021 | { | |
2022 | BOOST_ASSERT(first == last || | |
2023 | (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last))); | |
2024 | if (first != last){ | |
2025 | T* const old_end_ptr = this->priv_raw_end(); | |
2026 | T* const first_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(first)); | |
2027 | T* const last_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(last)); | |
2028 | T* const ptr = container_detail::to_raw_pointer(boost::container::move(last_ptr, old_end_ptr, first_ptr)); | |
2029 | this->priv_destroy_last_n(old_end_ptr - ptr); | |
2030 | } | |
2031 | return iterator(vector_iterator_get_ptr(first)); | |
2032 | } | |
2033 | ||
2034 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
2035 | //! | |
2036 | //! <b>Throws</b>: Nothing. | |
2037 | //! | |
2038 | //! <b>Complexity</b>: Constant. | |
2039 | void swap(vector& x) | |
2040 | BOOST_NOEXCEPT_IF( ((allocator_traits_type::propagate_on_container_swap::value | |
2041 | || allocator_traits_type::is_always_equal::value) && | |
2042 | !container_detail::is_version<Allocator, 0>::value)) | |
2043 | { | |
2044 | this->priv_swap(x, container_detail::bool_<container_detail::is_version<Allocator, 0>::value>()); | |
2045 | } | |
2046 | ||
2047 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2048 | ||
2049 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
2050 | //! | |
2051 | //! <b>Throws</b>: Nothing. | |
2052 | //! | |
2053 | //! <b>Complexity</b>: Linear | |
2054 | //! | |
2055 | //! <b>Note</b>: Non-standard extension to support static_vector | |
2056 | template<class OtherAllocator> | |
2057 | void swap(vector<T, OtherAllocator> & x | |
2058 | , typename container_detail::enable_if_and | |
2059 | < void | |
2060 | , container_detail::is_version<OtherAllocator, 0> | |
2061 | , container_detail::is_different<OtherAllocator, allocator_type> | |
2062 | >::type * = 0 | |
2063 | ) | |
2064 | { this->m_holder.deep_swap(x.m_holder); } | |
2065 | ||
2066 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2067 | ||
2068 | //! <b>Effects</b>: Erases all the elements of the vector. | |
2069 | //! | |
2070 | //! <b>Throws</b>: Nothing. | |
2071 | //! | |
2072 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2073 | void clear() BOOST_NOEXCEPT_OR_NOTHROW | |
2074 | { this->priv_destroy_all(); } | |
2075 | ||
2076 | //! <b>Effects</b>: Returns true if x and y are equal | |
2077 | //! | |
2078 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2079 | friend bool operator==(const vector& x, const vector& y) | |
2080 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
2081 | ||
2082 | //! <b>Effects</b>: Returns true if x and y are unequal | |
2083 | //! | |
2084 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2085 | friend bool operator!=(const vector& x, const vector& y) | |
2086 | { return !(x == y); } | |
2087 | ||
2088 | //! <b>Effects</b>: Returns true if x is less than y | |
2089 | //! | |
2090 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2091 | friend bool operator<(const vector& x, const vector& y) | |
2092 | { | |
2093 | const_iterator first1(x.cbegin()), first2(y.cbegin()); | |
2094 | const const_iterator last1(x.cend()), last2(y.cend()); | |
2095 | for ( ; (first1 != last1) && (first2 != last2); ++first1, ++first2 ) { | |
2096 | if (*first1 < *first2) return true; | |
2097 | if (*first2 < *first1) return false; | |
2098 | } | |
2099 | return (first1 == last1) && (first2 != last2); | |
2100 | } | |
2101 | ||
2102 | //! <b>Effects</b>: Returns true if x is greater than y | |
2103 | //! | |
2104 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2105 | friend bool operator>(const vector& x, const vector& y) | |
2106 | { return y < x; } | |
2107 | ||
2108 | //! <b>Effects</b>: Returns true if x is equal or less than y | |
2109 | //! | |
2110 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2111 | friend bool operator<=(const vector& x, const vector& y) | |
2112 | { return !(y < x); } | |
2113 | ||
2114 | //! <b>Effects</b>: Returns true if x is equal or greater than y | |
2115 | //! | |
2116 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
2117 | friend bool operator>=(const vector& x, const vector& y) | |
2118 | { return !(x < y); } | |
2119 | ||
2120 | //! <b>Effects</b>: x.swap(y) | |
2121 | //! | |
2122 | //! <b>Complexity</b>: Constant. | |
2123 | friend void swap(vector& x, vector& y) | |
2124 | { x.swap(y); } | |
2125 | ||
2126 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2127 | //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no | |
2128 | //! effect. Otherwise, it is a request for allocation of additional memory | |
2129 | //! (memory expansion) that will not invalidate iterators. | |
2130 | //! If the request is successful, then capacity() is greater than or equal to | |
2131 | //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged. | |
2132 | //! | |
2133 | //! <b>Throws</b>: If memory allocation allocation throws or T's copy/move constructor throws. | |
2134 | //! | |
2135 | //! <b>Note</b>: Non-standard extension. | |
2136 | bool stable_reserve(size_type new_cap) | |
2137 | { | |
2138 | const size_type cp = this->capacity(); | |
2139 | return cp >= new_cap || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(new_cap - cp)); | |
2140 | } | |
2141 | ||
2142 | //Absolutely experimental. This function might change, disappear or simply crash! | |
2143 | template<class BiDirPosConstIt, class BiDirValueIt> | |
2144 | void insert_ordered_at(const size_type element_count, BiDirPosConstIt last_position_it, BiDirValueIt last_value_it) | |
2145 | { | |
2146 | typedef container_detail::vector_insert_ordered_cursor<BiDirPosConstIt, BiDirValueIt> inserter_t; | |
2147 | return this->priv_insert_ordered_at(element_count, inserter_t(last_position_it, last_value_it)); | |
2148 | } | |
2149 | ||
2150 | template<class BidirIt> | |
2151 | void merge(BidirIt first, BidirIt last) | |
2152 | { this->merge(first, last, value_less()); } | |
2153 | ||
2154 | template<class BidirIt, class Compare> | |
2155 | void merge(BidirIt first, BidirIt last, Compare comp) | |
2156 | { this->priv_merge(container_detail::false_type(), first, last, comp); } | |
2157 | ||
2158 | template<class BidirIt> | |
2159 | void merge_unique(BidirIt first, BidirIt last) | |
2160 | { this->priv_merge(container_detail::true_type(), first, last, value_less()); } | |
2161 | ||
2162 | template<class BidirIt, class Compare> | |
2163 | void merge_unique(BidirIt first, BidirIt last, Compare comp) | |
2164 | { this->priv_merge(container_detail::true_type(), first, last, comp); } | |
2165 | ||
2166 | private: | |
2167 | template<class PositionValue> | |
2168 | void priv_insert_ordered_at(const size_type element_count, PositionValue position_value) | |
2169 | { | |
2170 | const size_type old_size_pos = this->size(); | |
2171 | this->reserve(old_size_pos + element_count); | |
2172 | T* const begin_ptr = this->priv_raw_begin(); | |
2173 | size_type insertions_left = element_count; | |
2174 | size_type prev_pos = old_size_pos; | |
2175 | size_type old_hole_size = element_count; | |
2176 | ||
2177 | //Exception rollback. If any copy throws before the hole is filled, values | |
2178 | //already inserted/copied at the end of the buffer will be destroyed. | |
2179 | typename value_traits::ArrayDestructor past_hole_values_destroyer | |
2180 | (begin_ptr + old_size_pos + element_count, this->m_holder.alloc(), size_type(0u)); | |
2181 | //Loop for each insertion backwards, first moving the elements after the insertion point, | |
2182 | //then inserting the element. | |
2183 | while(insertions_left){ | |
2184 | --position_value; | |
2185 | size_type const pos = position_value.get_pos(); | |
2186 | BOOST_ASSERT(pos != size_type(-1) && pos <= old_size_pos && pos <= prev_pos); | |
2187 | //If needed shift the range after the insertion point and the previous insertion point. | |
2188 | //Function will take care if the shift crosses the size() boundary, using copy/move | |
2189 | //or uninitialized copy/move if necessary. | |
2190 | size_type new_hole_size = (pos != prev_pos) | |
2191 | ? priv_insert_ordered_at_shift_range(pos, prev_pos, this->size(), insertions_left) | |
2192 | : old_hole_size | |
2193 | ; | |
2194 | if(new_hole_size){ | |
2195 | //The hole was reduced by priv_insert_ordered_at_shift_range so expand exception rollback range backwards | |
2196 | past_hole_values_destroyer.increment_size_backwards(prev_pos - pos); | |
2197 | //Insert the new value in the hole | |
2198 | allocator_traits_type::construct(this->m_holder.alloc(), begin_ptr + pos + insertions_left - 1, position_value.get_val()); | |
2199 | if(--new_hole_size){ | |
2200 | //The hole was reduced by the new insertion by one | |
2201 | past_hole_values_destroyer.increment_size_backwards(size_type(1u)); | |
2202 | } | |
2203 | else{ | |
2204 | //Hole was just filled, disable exception rollback and change vector size | |
2205 | past_hole_values_destroyer.release(); | |
2206 | this->m_holder.m_size += element_count; | |
2207 | } | |
2208 | } | |
2209 | else{ | |
2210 | if(old_hole_size){ | |
2211 | //Hole was just filled by priv_insert_ordered_at_shift_range, disable exception rollback and change vector size | |
2212 | past_hole_values_destroyer.release(); | |
2213 | this->m_holder.m_size += element_count; | |
2214 | } | |
2215 | //Insert the new value in the already constructed range | |
2216 | begin_ptr[pos + insertions_left - 1] = position_value.get_val(); | |
2217 | } | |
2218 | --insertions_left; | |
2219 | old_hole_size = new_hole_size; | |
2220 | prev_pos = pos; | |
2221 | } | |
2222 | } | |
2223 | ||
2224 | template<class UniqueBool, class BidirIt, class Compare> | |
2225 | void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp) | |
2226 | { | |
2227 | size_type const n = static_cast<size_type>(boost::container::iterator_distance(first, last)); | |
2228 | size_type const s = this->size(); | |
2229 | if(BOOST_LIKELY(s)){ | |
2230 | size_type const c = this->capacity(); | |
2231 | size_type const free_c = (c - s); | |
2232 | //Use a new buffer if current one is too small for new elements, | |
2233 | //or there is no room for position indexes | |
2234 | if(free_c < n){ | |
2235 | size_type const new_size = s + n; | |
2236 | size_type new_cap = new_size; | |
2237 | pointer p = pointer(); | |
2238 | p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p); | |
2239 | this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap); | |
2240 | } | |
2241 | else if(!UniqueBool::value && free_c >= n){ | |
2242 | typedef container_detail::vector_merge_cursor<T, size_type, BidirIt, Compare> inserter_t; | |
2243 | T* const pbeg = this->priv_raw_begin(); | |
2244 | return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp)); | |
2245 | } | |
2246 | else{ //UniqueBool::value == true and free_c >= n | |
2247 | std::size_t remaining = n; | |
2248 | static const std::size_t PosCount = 64u; | |
2249 | size_type positions[PosCount]; | |
2250 | size_type *indexes = 0; | |
2251 | while(remaining){ | |
2252 | //Query for room to store indexes in the remaining buffer | |
2253 | boost::uintptr_t const szt_align_mask = container_detail::alignment_of<size_type>::value - 1; | |
2254 | boost::uintptr_t const addr = boost::uintptr_t(this->priv_raw_begin() + s + n); | |
2255 | boost::uintptr_t const capaddr = boost::uintptr_t(this->priv_raw_begin() + c); | |
2256 | boost::uintptr_t const aligned_addr = (addr + szt_align_mask) & ~szt_align_mask; | |
2257 | indexes = reinterpret_cast<size_type *>(aligned_addr); | |
2258 | std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - addr)/sizeof(size_type); | |
2259 | ||
2260 | //Capacity is constant, we're not going to change it | |
2261 | if(index_capacity < PosCount){ | |
2262 | indexes = positions; | |
2263 | index_capacity = PosCount; | |
2264 | } | |
2265 | if(index_capacity > remaining) | |
2266 | index_capacity = remaining; | |
2267 | BidirIt limit = first; | |
2268 | boost::container::iterator_advance(limit, index_capacity); | |
2269 | this->priv_insert_ordered_range(UniqueBool(), index_capacity, first, limit, indexes, comp); | |
2270 | first = limit; | |
2271 | remaining -= index_capacity; | |
2272 | } | |
2273 | } | |
2274 | } | |
2275 | else{ | |
2276 | this->insert(this->cend(), n, first, last); | |
2277 | } | |
2278 | } | |
2279 | ||
2280 | template <class UniqueBool, class BidirIt, class Compare> | |
2281 | void priv_insert_ordered_range | |
2282 | (UniqueBool, size_type const n, BidirIt first, BidirIt const last, size_type positions[], Compare comp) | |
2283 | { | |
2284 | //Linear: at most N + M -1 comparisons | |
2285 | //Log: MlogN | |
2286 | //Average | |
2287 | //Linear: N + M - 2 | |
2288 | //Log: MlogN | |
2289 | //N+M - 2 | |
2290 | //N | |
2291 | //(N+M)/2 < MlogN | |
2292 | //(N/M+1)/2 <= logN | |
2293 | //bool const linear = !s || !n || (s <= n) || ((s+n)/n/2 < logN); | |
2294 | size_type const s = this->size(); | |
2295 | size_type remaining = n; | |
2296 | T* const pbeg = this->priv_raw_begin(); | |
2297 | T* const pend = pbeg + s; | |
2298 | T* pcur = pbeg; | |
2299 | size_type *position = positions; | |
2300 | size_type added_in_middle = 0; | |
2301 | if(first != last && pcur != pend){ | |
2302 | while(1){ | |
2303 | //maintain stability moving external values only if they are strictly less | |
2304 | if(comp(*first, *pcur)) { | |
2305 | *position = static_cast<size_type>(pcur - pbeg); | |
2306 | BOOST_ASSERT((position == positions) || (*(position-1) == size_type(-1)) || (*(position-1) <= *position)); | |
2307 | ++position; | |
2308 | ++added_in_middle; | |
2309 | --remaining; | |
2310 | if(++first == last) break; | |
2311 | } | |
2312 | else if(UniqueBool::value && !comp(*pcur, *first)){ | |
2313 | *position = size_type(-1); | |
2314 | ++position; | |
2315 | --remaining; | |
2316 | if(++first == last) break; | |
2317 | } | |
2318 | else{ | |
2319 | if(++pcur == pend) break; | |
2320 | } | |
2321 | } | |
2322 | } | |
2323 | this->insert_ordered_at(added_in_middle, position, first); | |
2324 | this->insert(this->cend(), remaining, first, last); | |
2325 | } | |
2326 | ||
2327 | template<class UniqueBool, class FwdIt, class Compare> | |
2328 | void priv_merge_in_new_buffer | |
2329 | (UniqueBool, FwdIt first, size_type n, Compare comp, pointer new_storage, size_type const new_cap) | |
2330 | { | |
2331 | BOOST_ASSERT((new_cap >= this->size() ) && (new_cap - this->size()) >= n); | |
2332 | allocator_type &a = this->m_holder.alloc(); | |
2333 | typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap); | |
2334 | typename value_traits::ArrayDestructor new_values_destroyer(new_storage, a, 0u); | |
2335 | T* pbeg = this->priv_raw_begin(); | |
2336 | size_type const old_size = this->size(); | |
2337 | T* const pend = pbeg + old_size; | |
2338 | T* d_first = container_detail::to_raw_pointer(new_storage); | |
2339 | size_type added = n; | |
2340 | //Merge in new buffer loop | |
2341 | while(1){ | |
2342 | if(!n) { | |
2343 | ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pbeg, pend, d_first); | |
2344 | break; | |
2345 | } | |
2346 | else if(pbeg == pend) { | |
2347 | ::boost::container::uninitialized_move_alloc_n(this->m_holder.alloc(), first, n, d_first); | |
2348 | break; | |
2349 | } | |
2350 | //maintain stability moving external values only if they are strictly less | |
2351 | else if(comp(*first, *pbeg)) { | |
2352 | allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::boost::move(*first) ); | |
2353 | new_values_destroyer.increment_size(1u); | |
2354 | ++first; | |
2355 | --n; | |
2356 | ++d_first; | |
2357 | } | |
2358 | else if(UniqueBool::value && !comp(*pbeg, *first)){ | |
2359 | ++first; | |
2360 | --n; | |
2361 | --added; | |
2362 | } | |
2363 | else{ | |
2364 | allocator_traits_type::construct( this->m_holder.alloc(), d_first, ::boost::move(*pbeg) ); | |
2365 | new_values_destroyer.increment_size(1u); | |
2366 | ++pbeg; | |
2367 | ++d_first; | |
2368 | } | |
2369 | } | |
2370 | ||
2371 | //Nothrow operations | |
2372 | pointer const old_p = this->m_holder.start(); | |
2373 | size_type const old_cap = this->m_holder.capacity(); | |
2374 | boost::container::destroy_alloc_n(a, container_detail::to_raw_pointer(old_p), old_size); | |
2375 | a.deallocate(old_p, old_cap); | |
2376 | this->m_holder.m_size = old_size + added; | |
2377 | this->m_holder.start(new_storage); | |
2378 | this->m_holder.capacity(new_cap); | |
2379 | new_buffer_deallocator.release(); | |
2380 | new_values_destroyer.release(); | |
2381 | } | |
2382 | ||
2383 | bool room_enough() const | |
2384 | { return this->m_holder.m_size < this->m_holder.capacity(); } | |
2385 | ||
2386 | pointer back_ptr() const | |
2387 | { return this->m_holder.start() + this->m_holder.m_size; } | |
2388 | ||
2389 | size_type priv_index_of(pointer p) const | |
2390 | { | |
2391 | BOOST_ASSERT(this->m_holder.start() <= p); | |
2392 | BOOST_ASSERT(p <= (this->m_holder.start()+this->size())); | |
2393 | return static_cast<size_type>(p - this->m_holder.start()); | |
2394 | } | |
2395 | ||
2396 | template<class OtherAllocator> | |
2397 | void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x | |
2398 | , typename container_detail::enable_if_c | |
2399 | < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0) | |
2400 | { | |
2401 | if(!container_detail::is_same<OtherAllocator, allocator_type>::value && | |
2402 | this->capacity() < x.size()){ | |
2403 | throw_bad_alloc(); | |
2404 | } | |
2405 | T* const this_start = this->priv_raw_begin(); | |
2406 | T* const other_start = x.priv_raw_begin(); | |
2407 | const size_type this_sz = m_holder.m_size; | |
2408 | const size_type other_sz = static_cast<size_type>(x.m_holder.m_size); | |
2409 | boost::container::move_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz); | |
2410 | this->m_holder.m_size = other_sz; | |
2411 | } | |
2412 | ||
2413 | template<class OtherAllocator> | |
2414 | void priv_move_assign(BOOST_RV_REF_BEG vector<T, OtherAllocator> BOOST_RV_REF_END x | |
2415 | , typename container_detail::disable_if_or | |
2416 | < void | |
2417 | , container_detail::is_version<OtherAllocator, 0> | |
2418 | , container_detail::is_different<OtherAllocator, allocator_type> | |
2419 | >::type * = 0) | |
2420 | { | |
2421 | //for move assignment, no aliasing (&x != this) is assummed. | |
2422 | BOOST_ASSERT(this != &x); | |
2423 | allocator_type &this_alloc = this->m_holder.alloc(); | |
2424 | allocator_type &x_alloc = x.m_holder.alloc(); | |
2425 | const bool propagate_alloc = allocator_traits_type::propagate_on_container_move_assignment::value; | |
2426 | ||
2427 | const bool is_propagable_from_x = is_propagable_from(x_alloc, x.m_holder.start(), this_alloc, propagate_alloc); | |
2428 | const bool is_propagable_from_t = is_propagable_from(this_alloc, m_holder.start(), x_alloc, propagate_alloc); | |
2429 | const bool are_both_propagable = is_propagable_from_x && is_propagable_from_t; | |
2430 | ||
2431 | //Resources can be transferred if both allocators are | |
2432 | //going to be equal after this function (either propagated or already equal) | |
2433 | if(are_both_propagable){ | |
2434 | //Destroy objects but retain memory in case x reuses it in the future | |
2435 | this->clear(); | |
2436 | this->m_holder.swap_resources(x.m_holder); | |
2437 | } | |
2438 | else if(is_propagable_from_x){ | |
2439 | this->clear(); | |
2440 | this->m_holder.alloc().deallocate(this->m_holder.m_start, this->m_holder.m_capacity); | |
2441 | this->m_holder.steal_resources(x.m_holder); | |
2442 | } | |
2443 | //Else do a one by one move | |
2444 | else{ | |
2445 | this->assign( boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.begin())) | |
2446 | , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(x.end() )) | |
2447 | ); | |
2448 | } | |
2449 | //Move allocator if needed | |
2450 | container_detail::move_alloc(this_alloc, x_alloc, container_detail::bool_<propagate_alloc>()); | |
2451 | } | |
2452 | ||
2453 | template<class OtherAllocator> | |
2454 | void priv_copy_assign(const vector<T, OtherAllocator> &x | |
2455 | , typename container_detail::enable_if_c | |
2456 | < container_detail::is_version<OtherAllocator, 0>::value >::type * = 0) | |
2457 | { | |
2458 | if(!container_detail::is_same<OtherAllocator, allocator_type>::value && | |
2459 | this->capacity() < x.size()){ | |
2460 | throw_bad_alloc(); | |
2461 | } | |
2462 | T* const this_start = this->priv_raw_begin(); | |
2463 | T* const other_start = x.priv_raw_begin(); | |
2464 | const size_type this_sz = m_holder.m_size; | |
2465 | const size_type other_sz = static_cast<size_type>(x.m_holder.m_size); | |
2466 | boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz); | |
2467 | this->m_holder.m_size = other_sz; | |
2468 | } | |
2469 | ||
2470 | template<class OtherAllocator> | |
2471 | typename container_detail::disable_if_or | |
2472 | < void | |
2473 | , container_detail::is_version<OtherAllocator, 0> | |
2474 | , container_detail::is_different<OtherAllocator, allocator_type> | |
2475 | >::type | |
2476 | priv_copy_assign(const vector<T, OtherAllocator> &x) | |
2477 | { | |
2478 | allocator_type &this_alloc = this->m_holder.alloc(); | |
2479 | const allocator_type &x_alloc = x.m_holder.alloc(); | |
2480 | container_detail::bool_<allocator_traits_type:: | |
2481 | propagate_on_container_copy_assignment::value> flag; | |
2482 | if(flag && this_alloc != x_alloc){ | |
2483 | this->clear(); | |
2484 | this->shrink_to_fit(); | |
2485 | } | |
2486 | container_detail::assign_alloc(this_alloc, x_alloc, flag); | |
2487 | this->assign( x.priv_raw_begin(), x.priv_raw_end() ); | |
2488 | } | |
2489 | ||
2490 | template<class Vector> //Template it to avoid it in explicit instantiations | |
2491 | void priv_swap(Vector &x, container_detail::true_type) //version_0 | |
2492 | { this->m_holder.deep_swap(x.m_holder); } | |
2493 | ||
2494 | template<class Vector> //Template it to avoid it in explicit instantiations | |
2495 | void priv_swap(Vector &x, container_detail::false_type) //version_N | |
2496 | { | |
2497 | const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value; | |
2498 | if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start() | |
2499 | , x.get_stored_allocator(), x.m_holder.start(), propagate_alloc)){ | |
2500 | //Just swap internals | |
2501 | this->m_holder.swap_resources(x.m_holder); | |
2502 | } | |
2503 | else{ | |
2504 | //Else swap element by element... | |
2505 | bool const t_smaller = this->size() < x.size(); | |
2506 | vector &sml = t_smaller ? *this : x; | |
2507 | vector &big = t_smaller ? x : *this; | |
2508 | ||
2509 | size_type const common_elements = sml.size(); | |
2510 | for(size_type i = 0; i != common_elements; ++i){ | |
2511 | boost::adl_move_swap(sml[i], big[i]); | |
2512 | } | |
2513 | //... and move-insert the remaining range | |
2514 | sml.insert( sml.cend() | |
2515 | , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.nth(common_elements))) | |
2516 | , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.end())) | |
2517 | ); | |
2518 | //Destroy remaining elements | |
2519 | big.erase(big.nth(common_elements), big.cend()); | |
2520 | } | |
2521 | //And now swap the allocator | |
2522 | container_detail::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), container_detail::bool_<propagate_alloc>()); | |
2523 | } | |
2524 | ||
2525 | void priv_reserve_no_capacity(size_type, version_0) | |
2526 | { throw_bad_alloc(); } | |
2527 | ||
2528 | container_detail::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> priv_dummy_empty_proxy() | |
2529 | { | |
2530 | return container_detail::insert_range_proxy<Allocator, boost::move_iterator<T*>, T*> | |
2531 | (::boost::make_move_iterator((T *)0)); | |
2532 | } | |
2533 | ||
2534 | void priv_reserve_no_capacity(size_type new_cap, version_1) | |
2535 | { | |
2536 | //There is not enough memory, allocate a new buffer | |
2537 | //Pass the hint so that allocators can take advantage of this. | |
2538 | pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start); | |
2539 | //We will reuse insert code, so create a dummy input iterator | |
2540 | this->priv_forward_range_insert_new_allocation | |
2541 | ( container_detail::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy()); | |
2542 | } | |
2543 | ||
2544 | void priv_reserve_no_capacity(size_type new_cap, version_2) | |
2545 | { | |
2546 | //There is not enough memory, allocate a new | |
2547 | //buffer or expand the old one. | |
2548 | bool same_buffer_start; | |
2549 | size_type real_cap = 0; | |
2550 | pointer reuse(this->m_holder.start()); | |
2551 | pointer const ret(this->m_holder.allocation_command(allocate_new | expand_fwd | expand_bwd, new_cap, real_cap = new_cap, reuse)); | |
2552 | ||
2553 | //Check for forward expansion | |
2554 | same_buffer_start = reuse && this->m_holder.start() == ret; | |
2555 | if(same_buffer_start){ | |
2556 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2557 | ++this->num_expand_fwd; | |
2558 | #endif | |
2559 | this->m_holder.capacity(real_cap); | |
2560 | } | |
2561 | else{ //If there is no forward expansion, move objects, we will reuse insertion code | |
2562 | T * const new_mem = container_detail::to_raw_pointer(ret); | |
2563 | T * const ins_pos = this->priv_raw_end(); | |
2564 | if(reuse){ //Backwards (and possibly forward) expansion | |
2565 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2566 | ++this->num_expand_bwd; | |
2567 | #endif | |
2568 | this->priv_forward_range_insert_expand_backwards | |
2569 | ( new_mem , real_cap, ins_pos, 0, this->priv_dummy_empty_proxy()); | |
2570 | } | |
2571 | else{ //New buffer | |
2572 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2573 | ++this->num_alloc; | |
2574 | #endif | |
2575 | this->priv_forward_range_insert_new_allocation | |
2576 | ( new_mem, real_cap, ins_pos, 0, this->priv_dummy_empty_proxy()); | |
2577 | } | |
2578 | } | |
2579 | } | |
2580 | ||
2581 | void priv_destroy_last(const bool moved = false) BOOST_NOEXCEPT_OR_NOTHROW | |
2582 | { | |
2583 | (void)moved; | |
2584 | if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){ | |
2585 | value_type* const p = this->priv_raw_end() - 1; | |
2586 | allocator_traits_type::destroy(this->get_stored_allocator(), p); | |
2587 | } | |
2588 | --this->m_holder.m_size; | |
2589 | } | |
2590 | ||
2591 | void priv_destroy_last_n(const size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
2592 | { | |
2593 | BOOST_ASSERT(n <= this->m_holder.m_size); | |
2594 | if(!value_traits::trivial_dctr){ | |
2595 | T* const destroy_pos = this->priv_raw_begin() + (this->m_holder.m_size-n); | |
2596 | boost::container::destroy_alloc_n(this->get_stored_allocator(), destroy_pos, n); | |
2597 | } | |
2598 | this->m_holder.m_size -= n; | |
2599 | } | |
2600 | ||
2601 | template<class InpIt> | |
2602 | void priv_uninitialized_construct_at_end(InpIt first, InpIt last) | |
2603 | { | |
2604 | T* const old_end_pos = this->priv_raw_end(); | |
2605 | T* const new_end_pos = boost::container::uninitialized_copy_alloc(this->m_holder.alloc(), first, last, old_end_pos); | |
2606 | this->m_holder.m_size += new_end_pos - old_end_pos; | |
2607 | } | |
2608 | ||
2609 | void priv_destroy_all() BOOST_NOEXCEPT_OR_NOTHROW | |
2610 | { | |
2611 | boost::container::destroy_alloc_n | |
2612 | (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size); | |
2613 | this->m_holder.m_size = 0; | |
2614 | } | |
2615 | ||
2616 | template<class U> | |
2617 | iterator priv_insert(const const_iterator &p, BOOST_FWD_REF(U) x) | |
2618 | { | |
2619 | BOOST_ASSERT(this->priv_in_range_or_end(p)); | |
2620 | return this->priv_forward_range_insert | |
2621 | ( vector_iterator_get_ptr(p), 1, container_detail::get_insert_value_proxy<T*, Allocator>(::boost::forward<U>(x))); | |
2622 | } | |
2623 | ||
2624 | container_detail::insert_copy_proxy<Allocator, T*> priv_single_insert_proxy(const T &x) | |
2625 | { return container_detail::insert_copy_proxy<Allocator, T*> (x); } | |
2626 | ||
2627 | container_detail::insert_move_proxy<Allocator, T*> priv_single_insert_proxy(BOOST_RV_REF(T) x) | |
2628 | { return container_detail::insert_move_proxy<Allocator, T*> (x); } | |
2629 | ||
2630 | template <class U> | |
2631 | void priv_push_back(BOOST_FWD_REF(U) u) | |
2632 | { | |
2633 | if (BOOST_LIKELY(this->room_enough())){ | |
2634 | //There is more memory, just construct a new object at the end | |
2635 | allocator_traits_type::construct | |
2636 | ( this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward<U>(u) ); | |
2637 | ++this->m_holder.m_size; | |
2638 | } | |
2639 | else{ | |
2640 | this->priv_forward_range_insert_no_capacity | |
2641 | ( this->back_ptr(), 1 | |
2642 | , this->priv_single_insert_proxy(::boost::forward<U>(u)), alloc_version()); | |
2643 | } | |
2644 | } | |
2645 | ||
2646 | container_detail::insert_n_copies_proxy<Allocator, T*> priv_resize_proxy(const T &x) | |
2647 | { return container_detail::insert_n_copies_proxy<Allocator, T*>(x); } | |
2648 | ||
2649 | container_detail::insert_default_initialized_n_proxy<Allocator, T*> priv_resize_proxy(default_init_t) | |
2650 | { return container_detail::insert_default_initialized_n_proxy<Allocator, T*>(); } | |
2651 | ||
2652 | container_detail::insert_value_initialized_n_proxy<Allocator, T*> priv_resize_proxy(value_init_t) | |
2653 | { return container_detail::insert_value_initialized_n_proxy<Allocator, T*>(); } | |
2654 | ||
2655 | template <class U> | |
2656 | void priv_resize(size_type new_size, const U& u) | |
2657 | { | |
2658 | const size_type sz = this->size(); | |
2659 | if (new_size < sz){ | |
2660 | //Destroy last elements | |
2661 | this->priv_destroy_last_n(sz - new_size); | |
2662 | } | |
2663 | else{ | |
2664 | const size_type n = new_size - this->size(); | |
2665 | this->priv_forward_range_insert_at_end(n, this->priv_resize_proxy(u), alloc_version()); | |
2666 | } | |
2667 | } | |
2668 | ||
2669 | void priv_shrink_to_fit(version_0) BOOST_NOEXCEPT_OR_NOTHROW | |
2670 | {} | |
2671 | ||
2672 | void priv_shrink_to_fit(version_1) | |
2673 | { | |
2674 | const size_type cp = this->m_holder.capacity(); | |
2675 | if(cp){ | |
2676 | const size_type sz = this->size(); | |
2677 | if(!sz){ | |
2678 | this->m_holder.alloc().deallocate(this->m_holder.m_start, cp); | |
2679 | this->m_holder.m_start = pointer(); | |
2680 | this->m_holder.m_capacity = 0; | |
2681 | } | |
2682 | else if(sz < cp){ | |
2683 | //Allocate a new buffer. | |
2684 | //Pass the hint so that allocators can take advantage of this. | |
2685 | pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), sz, this->m_holder.m_start); | |
2686 | ||
2687 | //We will reuse insert code, so create a dummy input iterator | |
2688 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2689 | ++this->num_alloc; | |
2690 | #endif | |
2691 | this->priv_forward_range_insert_new_allocation | |
2692 | ( container_detail::to_raw_pointer(p), sz | |
2693 | , this->priv_raw_begin(), 0, this->priv_dummy_empty_proxy()); | |
2694 | } | |
2695 | } | |
2696 | } | |
2697 | ||
2698 | void priv_shrink_to_fit(version_2) BOOST_NOEXCEPT_OR_NOTHROW | |
2699 | { | |
2700 | const size_type cp = this->m_holder.capacity(); | |
2701 | if(cp){ | |
2702 | const size_type sz = this->size(); | |
2703 | if(!sz){ | |
2704 | this->m_holder.alloc().deallocate(this->m_holder.m_start, cp); | |
2705 | this->m_holder.m_start = pointer(); | |
2706 | this->m_holder.m_capacity = 0; | |
2707 | } | |
2708 | else{ | |
2709 | size_type received_size = sz; | |
2710 | pointer reuse(this->m_holder.start()); | |
2711 | if(this->m_holder.allocation_command | |
2712 | (shrink_in_place | nothrow_allocation, cp, received_size, reuse)){ | |
2713 | this->m_holder.capacity(received_size); | |
2714 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2715 | ++this->num_shrink; | |
2716 | #endif | |
2717 | } | |
2718 | } | |
2719 | } | |
2720 | } | |
2721 | ||
2722 | template <class InsertionProxy> | |
2723 | iterator priv_forward_range_insert_no_capacity | |
2724 | (const pointer &pos, const size_type, const InsertionProxy , version_0) | |
2725 | { | |
2726 | throw_bad_alloc(); | |
2727 | return iterator(pos); | |
2728 | } | |
2729 | ||
2730 | template <class InsertionProxy> | |
2731 | iterator priv_forward_range_insert_no_capacity | |
2732 | (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy, version_1) | |
2733 | { | |
2734 | //Check if we have enough memory or try to expand current memory | |
2735 | const size_type n_pos = pos - this->m_holder.start(); | |
2736 | T *const raw_pos = container_detail::to_raw_pointer(pos); | |
2737 | ||
2738 | const size_type new_cap = this->m_holder.next_capacity(n); | |
2739 | //Pass the hint so that allocators can take advantage of this. | |
2740 | T * const new_buf = container_detail::to_raw_pointer | |
2741 | (allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start)); | |
2742 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2743 | ++this->num_alloc; | |
2744 | #endif | |
2745 | this->priv_forward_range_insert_new_allocation | |
2746 | ( new_buf, new_cap, raw_pos, n, insert_range_proxy); | |
2747 | return iterator(this->m_holder.start() + n_pos); | |
2748 | } | |
2749 | ||
2750 | template <class InsertionProxy> | |
2751 | iterator priv_forward_range_insert_no_capacity | |
2752 | (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy, version_2) | |
2753 | { | |
2754 | //Check if we have enough memory or try to expand current memory | |
2755 | T *const raw_pos = container_detail::to_raw_pointer(pos); | |
2756 | const size_type n_pos = raw_pos - this->priv_raw_begin(); | |
2757 | ||
2758 | //There is not enough memory, allocate a new | |
2759 | //buffer or expand the old one. | |
2760 | size_type real_cap = this->m_holder.next_capacity(n); | |
2761 | pointer reuse(this->m_holder.start()); | |
2762 | pointer const ret (this->m_holder.allocation_command | |
2763 | (allocate_new | expand_fwd | expand_bwd, this->m_holder.m_size + n, real_cap, reuse)); | |
2764 | ||
2765 | //Buffer reallocated | |
2766 | if(reuse){ | |
2767 | //Forward expansion, delay insertion | |
2768 | if(this->m_holder.start() == ret){ | |
2769 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2770 | ++this->num_expand_fwd; | |
2771 | #endif | |
2772 | this->m_holder.capacity(real_cap); | |
2773 | //Expand forward | |
2774 | this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy); | |
2775 | } | |
2776 | //Backwards (and possibly forward) expansion | |
2777 | else{ | |
2778 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2779 | ++this->num_expand_bwd; | |
2780 | #endif | |
2781 | this->priv_forward_range_insert_expand_backwards | |
2782 | (container_detail::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy); | |
2783 | } | |
2784 | } | |
2785 | //New buffer | |
2786 | else{ | |
2787 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
2788 | ++this->num_alloc; | |
2789 | #endif | |
2790 | this->priv_forward_range_insert_new_allocation | |
2791 | ( container_detail::to_raw_pointer(ret), real_cap, raw_pos, n, insert_range_proxy); | |
2792 | } | |
2793 | ||
2794 | return iterator(this->m_holder.start() + n_pos); | |
2795 | } | |
2796 | ||
2797 | template <class InsertionProxy> | |
2798 | iterator priv_forward_range_insert | |
2799 | (const pointer &pos, const size_type n, const InsertionProxy insert_range_proxy) | |
2800 | { | |
2801 | BOOST_ASSERT(this->m_holder.capacity() >= this->m_holder.m_size); | |
2802 | //Check if we have enough memory or try to expand current memory | |
2803 | const size_type remaining = this->m_holder.capacity() - this->m_holder.m_size; | |
2804 | ||
2805 | bool same_buffer_start = n <= remaining; | |
2806 | if (!same_buffer_start){ | |
2807 | return priv_forward_range_insert_no_capacity(pos, n, insert_range_proxy, alloc_version()); | |
2808 | } | |
2809 | else{ | |
2810 | //Expand forward | |
2811 | T *const raw_pos = container_detail::to_raw_pointer(pos); | |
2812 | const size_type n_pos = raw_pos - this->priv_raw_begin(); | |
2813 | this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy); | |
2814 | return iterator(this->m_holder.start() + n_pos); | |
2815 | } | |
2816 | } | |
2817 | ||
2818 | template <class InsertionProxy> | |
2819 | iterator priv_forward_range_insert_at_end | |
2820 | (const size_type n, const InsertionProxy insert_range_proxy, version_0) | |
2821 | { | |
2822 | //Check if we have enough memory or try to expand current memory | |
2823 | const size_type remaining = this->m_holder.capacity() - this->m_holder.m_size; | |
2824 | ||
2825 | if (n > remaining){ | |
2826 | //This will trigger an error | |
2827 | throw_bad_alloc(); | |
2828 | } | |
2829 | this->priv_forward_range_insert_at_end_expand_forward(n, insert_range_proxy); | |
2830 | return this->end(); | |
2831 | } | |
2832 | ||
2833 | template <class InsertionProxy, class AllocVersion> | |
2834 | iterator priv_forward_range_insert_at_end | |
2835 | (const size_type n, const InsertionProxy insert_range_proxy, AllocVersion) | |
2836 | { | |
2837 | return this->priv_forward_range_insert(this->back_ptr(), n, insert_range_proxy); | |
2838 | } | |
2839 | ||
2840 | //Takes the range pointed by [first_pos, last_pos) and shifts it to the right | |
2841 | //by 'shift_count'. 'limit_pos' marks the end of constructed elements. | |
2842 | // | |
2843 | //Precondition: first_pos <= last_pos <= limit_pos | |
2844 | // | |
2845 | //The shift operation might cross limit_pos so elements to moved beyond limit_pos | |
2846 | //are uninitialized_moved with an allocator. Other elements are moved. | |
2847 | // | |
2848 | //The shift operation might left uninitialized elements after limit_pos | |
2849 | //and the number of uninitialized elements is returned by the function. | |
2850 | // | |
2851 | //Old situation: | |
2852 | // first_pos last_pos old_limit | |
2853 | // | | | | |
2854 | // ____________V_______V__________________V_____________ | |
2855 | //| prefix | range | suffix |raw_mem ~ | |
2856 | //|____________|_______|__________________|_____________~ | |
2857 | // | |
2858 | //New situation in Case A (hole_size == 0): | |
2859 | // range is moved through move assignments | |
2860 | // | |
2861 | // first_pos last_pos limit_pos | |
2862 | // | | | | |
2863 | // ____________V_______V__________________V_____________ | |
2864 | //| prefix' | | | range |suffix'|raw_mem ~ | |
2865 | //|________________+______|___^___|_______|_____________~ | |
2866 | // | | | |
2867 | // |_>_>_>_>_>^ | |
2868 | // | |
2869 | // | |
2870 | //New situation in Case B (hole_size >= 0): | |
2871 | // range is moved through uninitialized moves | |
2872 | // | |
2873 | // first_pos last_pos limit_pos | |
2874 | // | | | | |
2875 | // ____________V_______V__________________V________________ | |
2876 | //| prefix' | | | [hole] | range | | |
2877 | //|_______________________________________|________|___^___| | |
2878 | // | | | |
2879 | // |_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_>_^ | |
2880 | // | |
2881 | //New situation in Case C (hole_size == 0): | |
2882 | // range is moved through move assignments and uninitialized moves | |
2883 | // | |
2884 | // first_pos last_pos limit_pos | |
2885 | // | | | | |
2886 | // ____________V_______V__________________V___ | |
2887 | //| prefix' | | | range | | |
2888 | //|___________________________________|___^___| | |
2889 | // | | | |
2890 | // |_>_>_>_>_>_>_>_>_>_>_>^ | |
2891 | size_type priv_insert_ordered_at_shift_range | |
2892 | (size_type first_pos, size_type last_pos, size_type limit_pos, size_type shift_count) | |
2893 | { | |
2894 | BOOST_ASSERT(first_pos <= last_pos); | |
2895 | BOOST_ASSERT(last_pos <= limit_pos); | |
2896 | // | |
2897 | T* const begin_ptr = this->priv_raw_begin(); | |
2898 | T* const first_ptr = begin_ptr + first_pos; | |
2899 | T* const last_ptr = begin_ptr + last_pos; | |
2900 | ||
2901 | size_type hole_size = 0; | |
2902 | //Case A: | |
2903 | if((last_pos + shift_count) <= limit_pos){ | |
2904 | //All move assigned | |
2905 | boost::container::move_backward(first_ptr, last_ptr, last_ptr + shift_count); | |
2906 | } | |
2907 | //Case B: | |
2908 | else if((first_pos + shift_count) >= limit_pos){ | |
2909 | //All uninitialized_moved | |
2910 | ::boost::container::uninitialized_move_alloc | |
2911 | (this->m_holder.alloc(), first_ptr, last_ptr, first_ptr + shift_count); | |
2912 | hole_size = first_pos + shift_count - limit_pos; | |
2913 | } | |
2914 | //Case C: | |
2915 | else{ | |
2916 | //Some uninitialized_moved | |
2917 | T* const limit_ptr = begin_ptr + limit_pos; | |
2918 | T* const boundary_ptr = limit_ptr - shift_count; | |
2919 | ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), boundary_ptr, last_ptr, limit_ptr); | |
2920 | //The rest is move assigned | |
2921 | boost::container::move_backward(first_ptr, boundary_ptr, limit_ptr); | |
2922 | } | |
2923 | return hole_size; | |
2924 | } | |
2925 | ||
2926 | private: | |
2927 | T *priv_raw_begin() const | |
2928 | { return container_detail::to_raw_pointer(m_holder.start()); } | |
2929 | ||
2930 | T* priv_raw_end() const | |
2931 | { return this->priv_raw_begin() + this->m_holder.m_size; } | |
2932 | ||
2933 | template <class InsertionProxy> | |
2934 | void priv_forward_range_insert_at_end_expand_forward(const size_type n, InsertionProxy insert_range_proxy) | |
2935 | { | |
2936 | T* const old_finish = this->priv_raw_end(); | |
2937 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n); | |
2938 | this->m_holder.m_size += n; | |
2939 | } | |
2940 | ||
2941 | template <class InsertionProxy> | |
2942 | void priv_forward_range_insert_expand_forward(T* const pos, const size_type n, InsertionProxy insert_range_proxy) | |
2943 | { | |
2944 | //n can't be 0, because there is nothing to do in that case | |
2945 | if(BOOST_UNLIKELY(!n)) return; | |
2946 | //There is enough memory | |
2947 | T* const old_finish = this->priv_raw_end(); | |
2948 | const size_type elems_after = old_finish - pos; | |
2949 | ||
2950 | if (!elems_after){ | |
2951 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n); | |
2952 | this->m_holder.m_size += n; | |
2953 | } | |
2954 | else if (elems_after >= n){ | |
2955 | //New elements can be just copied. | |
2956 | //Move to uninitialized memory last objects | |
2957 | ::boost::container::uninitialized_move_alloc | |
2958 | (this->m_holder.alloc(), old_finish - n, old_finish, old_finish); | |
2959 | this->m_holder.m_size += n; | |
2960 | //Copy previous to last objects to the initialized end | |
2961 | boost::container::move_backward(pos, old_finish - n, old_finish); | |
2962 | //Insert new objects in the pos | |
2963 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, n); | |
2964 | } | |
2965 | else { | |
2966 | //The new elements don't fit in the [pos, end()) range. | |
2967 | ||
2968 | //Copy old [pos, end()) elements to the uninitialized memory (a gap is created) | |
2969 | ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), pos, old_finish, pos + n); | |
2970 | BOOST_TRY{ | |
2971 | //Copy first new elements in pos (gap is still there) | |
2972 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, elems_after); | |
2973 | //Copy to the beginning of the unallocated zone the last new elements (the gap is closed). | |
2974 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n - elems_after); | |
2975 | this->m_holder.m_size += n; | |
2976 | } | |
2977 | BOOST_CATCH(...){ | |
2978 | boost::container::destroy_alloc_n(this->get_stored_allocator(), pos + n, elems_after); | |
2979 | BOOST_RETHROW | |
2980 | } | |
2981 | BOOST_CATCH_END | |
2982 | } | |
2983 | } | |
2984 | ||
2985 | template <class InsertionProxy> | |
2986 | void priv_forward_range_insert_new_allocation | |
2987 | (T* const new_start, size_type new_cap, T* const pos, const size_type n, InsertionProxy insert_range_proxy) | |
2988 | { | |
2989 | //n can be zero, if we want to reallocate! | |
2990 | T *new_finish = new_start; | |
2991 | T *old_finish; | |
2992 | //Anti-exception rollbacks | |
2993 | typename value_traits::ArrayDeallocator new_buffer_deallocator(new_start, this->m_holder.alloc(), new_cap); | |
2994 | typename value_traits::ArrayDestructor new_values_destroyer(new_start, this->m_holder.alloc(), 0u); | |
2995 | ||
2996 | //Initialize with [begin(), pos) old buffer | |
2997 | //the start of the new buffer | |
2998 | T * const old_buffer = this->priv_raw_begin(); | |
2999 | if(old_buffer){ | |
3000 | new_finish = ::boost::container::uninitialized_move_alloc | |
3001 | (this->m_holder.alloc(), this->priv_raw_begin(), pos, old_finish = new_finish); | |
3002 | new_values_destroyer.increment_size(new_finish - old_finish); | |
3003 | } | |
3004 | //Initialize new objects, starting from previous point | |
3005 | old_finish = new_finish; | |
3006 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n); | |
3007 | new_finish += n; | |
3008 | new_values_destroyer.increment_size(new_finish - old_finish); | |
3009 | //Initialize from the rest of the old buffer, | |
3010 | //starting from previous point | |
3011 | if(old_buffer){ | |
3012 | new_finish = ::boost::container::uninitialized_move_alloc | |
3013 | (this->m_holder.alloc(), pos, old_buffer + this->m_holder.m_size, new_finish); | |
3014 | //Destroy and deallocate old elements | |
3015 | //If there is allocated memory, destroy and deallocate | |
3016 | if(!value_traits::trivial_dctr_after_move) | |
3017 | boost::container::destroy_alloc_n(this->get_stored_allocator(), old_buffer, this->m_holder.m_size); | |
3018 | this->m_holder.alloc().deallocate(this->m_holder.start(), this->m_holder.capacity()); | |
3019 | } | |
3020 | this->m_holder.start(new_start); | |
3021 | this->m_holder.m_size = new_finish - new_start; | |
3022 | this->m_holder.capacity(new_cap); | |
3023 | //All construction successful, disable rollbacks | |
3024 | new_values_destroyer.release(); | |
3025 | new_buffer_deallocator.release(); | |
3026 | } | |
3027 | ||
3028 | template <class InsertionProxy> | |
3029 | void priv_forward_range_insert_expand_backwards | |
3030 | (T* const new_start, const size_type new_capacity, | |
3031 | T* const pos, const size_type n, InsertionProxy insert_range_proxy) | |
3032 | { | |
3033 | //n can be zero to just expand capacity | |
3034 | //Backup old data | |
3035 | T* const old_start = this->priv_raw_begin(); | |
3036 | const size_type old_size = this->m_holder.m_size; | |
3037 | T* const old_finish = old_start + old_size; | |
3038 | ||
3039 | //We can have 8 possibilities: | |
3040 | const size_type elemsbefore = static_cast<size_type>(pos - old_start); | |
3041 | const size_type s_before = static_cast<size_type>(old_start - new_start); | |
3042 | const size_type before_plus_new = elemsbefore + n; | |
3043 | ||
3044 | //Update the vector buffer information to a safe state | |
3045 | this->m_holder.start(new_start); | |
3046 | this->m_holder.capacity(new_capacity); | |
3047 | this->m_holder.m_size = 0; | |
3048 | ||
3049 | //If anything goes wrong, this object will destroy | |
3050 | //all the old objects to fulfill previous vector state | |
3051 | typename value_traits::ArrayDestructor old_values_destroyer(old_start, this->m_holder.alloc(), old_size); | |
3052 | //Check if s_before is big enough to hold the beginning of old data + new data | |
3053 | if(s_before >= before_plus_new){ | |
3054 | //Copy first old values before pos, after that the new objects | |
3055 | T *const new_elem_pos = | |
3056 | ::boost::container::uninitialized_move_alloc(this->m_holder.alloc(), old_start, pos, new_start); | |
3057 | this->m_holder.m_size = elemsbefore; | |
3058 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), new_elem_pos, n); | |
3059 | this->m_holder.m_size = before_plus_new; | |
3060 | const size_type new_size = old_size + n; | |
3061 | //Check if s_before is so big that even copying the old data + new data | |
3062 | //there is a gap between the new data and the old data | |
3063 | if(s_before >= new_size){ | |
3064 | //Old situation: | |
3065 | // _________________________________________________________ | |
3066 | //| raw_mem | old_begin | old_end | | |
3067 | //| __________________________________|___________|_________| | |
3068 | // | |
3069 | //New situation: | |
3070 | // _________________________________________________________ | |
3071 | //| old_begin | new | old_end | raw_mem | | |
3072 | //|___________|__________|_________|________________________| | |
3073 | // | |
3074 | //Now initialize the rest of memory with the last old values | |
3075 | if(before_plus_new != new_size){ //Special case to avoid operations in back insertion | |
3076 | ::boost::container::uninitialized_move_alloc | |
3077 | (this->m_holder.alloc(), pos, old_finish, new_start + before_plus_new); | |
3078 | //All new elements correctly constructed, avoid new element destruction | |
3079 | this->m_holder.m_size = new_size; | |
3080 | } | |
3081 | //Old values destroyed automatically with "old_values_destroyer" | |
3082 | //when "old_values_destroyer" goes out of scope unless the have trivial | |
3083 | //destructor after move. | |
3084 | if(value_traits::trivial_dctr_after_move) | |
3085 | old_values_destroyer.release(); | |
3086 | } | |
3087 | //s_before is so big that divides old_end | |
3088 | else{ | |
3089 | //Old situation: | |
3090 | // __________________________________________________ | |
3091 | //| raw_mem | old_begin | old_end | | |
3092 | //| ___________________________|___________|_________| | |
3093 | // | |
3094 | //New situation: | |
3095 | // __________________________________________________ | |
3096 | //| old_begin | new | old_end | raw_mem | | |
3097 | //|___________|__________|_________|_________________| | |
3098 | // | |
3099 | //Now initialize the rest of memory with the last old values | |
3100 | //All new elements correctly constructed, avoid new element destruction | |
3101 | const size_type raw_gap = s_before - before_plus_new; | |
3102 | if(!value_traits::trivial_dctr){ | |
3103 | //Now initialize the rest of s_before memory with the | |
3104 | //first of elements after new values | |
3105 | ::boost::container::uninitialized_move_alloc_n | |
3106 | (this->m_holder.alloc(), pos, raw_gap, new_start + before_plus_new); | |
3107 | //Now we have a contiguous buffer so program trailing element destruction | |
3108 | //and update size to the final size. | |
3109 | old_values_destroyer.shrink_forward(new_size-s_before); | |
3110 | this->m_holder.m_size = new_size; | |
3111 | //Now move remaining last objects in the old buffer begin | |
3112 | T * const remaining_pos = pos + raw_gap; | |
3113 | if(remaining_pos != old_start){ //Make sure data has to be moved | |
3114 | ::boost::container::move(remaining_pos, old_finish, old_start); | |
3115 | } | |
3116 | //Once moved, avoid calling the destructors if trivial after move | |
3117 | if(value_traits::trivial_dctr_after_move){ | |
3118 | old_values_destroyer.release(); | |
3119 | } | |
3120 | } | |
3121 | else{ //If trivial destructor, we can uninitialized copy + copy in a single uninitialized copy | |
3122 | ::boost::container::uninitialized_move_alloc_n | |
3123 | (this->m_holder.alloc(), pos, old_finish - pos, new_start + before_plus_new); | |
3124 | this->m_holder.m_size = new_size; | |
3125 | old_values_destroyer.release(); | |
3126 | } | |
3127 | } | |
3128 | } | |
3129 | else{ | |
3130 | //Check if we have to do the insertion in two phases | |
3131 | //since maybe s_before is not big enough and | |
3132 | //the buffer was expanded both sides | |
3133 | // | |
3134 | //Old situation: | |
3135 | // _________________________________________________ | |
3136 | //| raw_mem | old_begin + old_end | raw_mem | | |
3137 | //|_________|_____________________|_________________| | |
3138 | // | |
3139 | //New situation with do_after: | |
3140 | // _________________________________________________ | |
3141 | //| old_begin + new + old_end | raw_mem | | |
3142 | //|___________________________________|_____________| | |
3143 | // | |
3144 | //New without do_after: | |
3145 | // _________________________________________________ | |
3146 | //| old_begin + new + old_end | raw_mem | | |
3147 | //|____________________________|____________________| | |
3148 | // | |
3149 | const bool do_after = n > s_before; | |
3150 | ||
3151 | //Now we can have two situations: the raw_mem of the | |
3152 | //beginning divides the old_begin, or the new elements: | |
3153 | if (s_before <= elemsbefore) { | |
3154 | //The raw memory divides the old_begin group: | |
3155 | // | |
3156 | //If we need two phase construction (do_after) | |
3157 | //new group is divided in new = new_beg + new_end groups | |
3158 | //In this phase only new_beg will be inserted | |
3159 | // | |
3160 | //Old situation: | |
3161 | // _________________________________________________ | |
3162 | //| raw_mem | old_begin | old_end | raw_mem | | |
3163 | //|_________|___________|_________|_________________| | |
3164 | // | |
3165 | //New situation with do_after(1): | |
3166 | //This is not definitive situation, the second phase | |
3167 | //will include | |
3168 | // _________________________________________________ | |
3169 | //| old_begin | new_beg | old_end | raw_mem | | |
3170 | //|___________|_________|_________|_________________| | |
3171 | // | |
3172 | //New situation without do_after: | |
3173 | // _________________________________________________ | |
3174 | //| old_begin | new | old_end | raw_mem | | |
3175 | //|___________|_____|_________|_____________________| | |
3176 | // | |
3177 | //Copy the first part of old_begin to raw_mem | |
3178 | ::boost::container::uninitialized_move_alloc_n | |
3179 | (this->m_holder.alloc(), old_start, s_before, new_start); | |
3180 | //The buffer is all constructed until old_end, | |
3181 | //so program trailing destruction and assign final size | |
3182 | //if !do_after, s_before+n otherwise. | |
3183 | size_type new_1st_range; | |
3184 | if(do_after){ | |
3185 | new_1st_range = s_before; | |
3186 | //release destroyer and update size | |
3187 | old_values_destroyer.release(); | |
3188 | } | |
3189 | else{ | |
3190 | new_1st_range = n; | |
3191 | if(value_traits::trivial_dctr_after_move) | |
3192 | old_values_destroyer.release(); | |
3193 | else{ | |
3194 | old_values_destroyer.shrink_forward(old_size - (s_before - n)); | |
3195 | } | |
3196 | } | |
3197 | this->m_holder.m_size = old_size + new_1st_range; | |
3198 | //Now copy the second part of old_begin overwriting itself | |
3199 | T *const next = ::boost::container::move(old_start + s_before, pos, old_start); | |
3200 | //Now copy the new_beg elements | |
3201 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), next, new_1st_range); | |
3202 | ||
3203 | //If there is no after work and the last old part needs to be moved to front, do it | |
3204 | if(!do_after && (n != s_before)){ | |
3205 | //Now displace old_end elements | |
3206 | ::boost::container::move(pos, old_finish, next + new_1st_range); | |
3207 | } | |
3208 | } | |
3209 | else { | |
3210 | //If we have to expand both sides, | |
3211 | //we will play if the first new values so | |
3212 | //calculate the upper bound of new values | |
3213 | ||
3214 | //The raw memory divides the new elements | |
3215 | // | |
3216 | //If we need two phase construction (do_after) | |
3217 | //new group is divided in new = new_beg + new_end groups | |
3218 | //In this phase only new_beg will be inserted | |
3219 | // | |
3220 | //Old situation: | |
3221 | // _______________________________________________________ | |
3222 | //| raw_mem | old_begin | old_end | raw_mem | | |
3223 | //|_______________|___________|_________|_________________| | |
3224 | // | |
3225 | //New situation with do_after(): | |
3226 | // ____________________________________________________ | |
3227 | //| old_begin | new_beg | old_end | raw_mem | | |
3228 | //|___________|_______________|_________|______________| | |
3229 | // | |
3230 | //New situation without do_after: | |
3231 | // ______________________________________________________ | |
3232 | //| old_begin | new | old_end | raw_mem | | |
3233 | //|___________|_____|_________|__________________________| | |
3234 | // | |
3235 | //First copy whole old_begin and part of new to raw_mem | |
3236 | T * const new_pos = ::boost::container::uninitialized_move_alloc | |
3237 | (this->m_holder.alloc(), old_start, pos, new_start); | |
3238 | this->m_holder.m_size = elemsbefore; | |
3239 | const size_type mid_n = s_before - elemsbefore; | |
3240 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), new_pos, mid_n); | |
3241 | //The buffer is all constructed until old_end, | |
3242 | //release destroyer | |
3243 | this->m_holder.m_size = old_size + s_before; | |
3244 | old_values_destroyer.release(); | |
3245 | ||
3246 | if(do_after){ | |
3247 | //Copy new_beg part | |
3248 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), old_start, elemsbefore); | |
3249 | } | |
3250 | else{ | |
3251 | //Copy all new elements | |
3252 | const size_type rest_new = n - mid_n; | |
3253 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), old_start, rest_new); | |
3254 | T* const move_start = old_start + rest_new; | |
3255 | //Displace old_end, but make sure data has to be moved | |
3256 | T* const move_end = move_start != pos ? ::boost::container::move(pos, old_finish, move_start) | |
3257 | : old_finish; | |
3258 | //Destroy remaining moved elements from old_end except if they | |
3259 | //have trivial destructor after being moved | |
3260 | size_type n_destroy = s_before - n; | |
3261 | if(!value_traits::trivial_dctr_after_move) | |
3262 | boost::container::destroy_alloc_n(this->get_stored_allocator(), move_end, n_destroy); | |
3263 | this->m_holder.m_size -= n_destroy; | |
3264 | } | |
3265 | } | |
3266 | ||
3267 | //This is only executed if two phase construction is needed | |
3268 | if(do_after){ | |
3269 | //The raw memory divides the new elements | |
3270 | // | |
3271 | //Old situation: | |
3272 | // ______________________________________________________ | |
3273 | //| raw_mem | old_begin | old_end | raw_mem | | |
3274 | //|______________|___________|____________|______________| | |
3275 | // | |
3276 | //New situation with do_after(1): | |
3277 | // _______________________________________________________ | |
3278 | //| old_begin + new_beg | new_end |old_end | raw_mem | | |
3279 | //|__________________________|_________|________|_________| | |
3280 | // | |
3281 | //New situation with do_after(2): | |
3282 | // ______________________________________________________ | |
3283 | //| old_begin + new | old_end |raw | | |
3284 | //|_______________________________________|_________|____| | |
3285 | // | |
3286 | const size_type n_after = n - s_before; | |
3287 | const size_type elemsafter = old_size - elemsbefore; | |
3288 | ||
3289 | //We can have two situations: | |
3290 | if (elemsafter >= n_after){ | |
3291 | //The raw_mem from end will divide displaced old_end | |
3292 | // | |
3293 | //Old situation: | |
3294 | // ______________________________________________________ | |
3295 | //| raw_mem | old_begin | old_end | raw_mem | | |
3296 | //|______________|___________|____________|______________| | |
3297 | // | |
3298 | //New situation with do_after(1): | |
3299 | // _______________________________________________________ | |
3300 | //| old_begin + new_beg | new_end |old_end | raw_mem | | |
3301 | //|__________________________|_________|________|_________| | |
3302 | // | |
3303 | //First copy the part of old_end raw_mem | |
3304 | T* finish_n = old_finish - n_after; | |
3305 | ::boost::container::uninitialized_move_alloc | |
3306 | (this->m_holder.alloc(), finish_n, old_finish, old_finish); | |
3307 | this->m_holder.m_size += n_after; | |
3308 | //Displace the rest of old_end to the new position | |
3309 | boost::container::move_backward(pos, finish_n, old_finish); | |
3310 | //Now overwrite with new_end | |
3311 | //The new_end part is [first + (n - n_after), last) | |
3312 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, n_after); | |
3313 | } | |
3314 | else { | |
3315 | //The raw_mem from end will divide new_end part | |
3316 | // | |
3317 | //Old situation: | |
3318 | // _____________________________________________________________ | |
3319 | //| raw_mem | old_begin | old_end | raw_mem | | |
3320 | //|______________|___________|____________|_____________________| | |
3321 | // | |
3322 | //New situation with do_after(2): | |
3323 | // _____________________________________________________________ | |
3324 | //| old_begin + new_beg | new_end |old_end | raw_mem | | |
3325 | //|__________________________|_______________|________|_________| | |
3326 | // | |
3327 | ||
3328 | const size_type mid_last_dist = n_after - elemsafter; | |
3329 | //First initialize data in raw memory | |
3330 | ||
3331 | //Copy to the old_end part to the uninitialized zone leaving a gap. | |
3332 | ::boost::container::uninitialized_move_alloc | |
3333 | (this->m_holder.alloc(), pos, old_finish, old_finish + mid_last_dist); | |
3334 | ||
3335 | typename value_traits::ArrayDestructor old_end_destroyer | |
3336 | (old_finish + mid_last_dist, this->m_holder.alloc(), old_finish - pos); | |
3337 | ||
3338 | //Copy the first part to the already constructed old_end zone | |
3339 | insert_range_proxy.copy_n_and_update(this->m_holder.alloc(), pos, elemsafter); | |
3340 | //Copy the rest to the uninitialized zone filling the gap | |
3341 | insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, mid_last_dist); | |
3342 | this->m_holder.m_size += n_after; | |
3343 | old_end_destroyer.release(); | |
3344 | } | |
3345 | } | |
3346 | } | |
3347 | } | |
3348 | ||
3349 | void priv_throw_if_out_of_range(size_type n) const | |
3350 | { | |
3351 | //If n is out of range, throw an out_of_range exception | |
3352 | if (n >= this->size()){ | |
3353 | throw_out_of_range("vector::at out of range"); | |
3354 | } | |
3355 | } | |
3356 | ||
3357 | bool priv_in_range(const_iterator pos) const | |
3358 | { | |
3359 | return (this->begin() <= pos) && (pos < this->end()); | |
3360 | } | |
3361 | ||
3362 | bool priv_in_range_or_end(const_iterator pos) const | |
3363 | { | |
3364 | return (this->begin() <= pos) && (pos <= this->end()); | |
3365 | } | |
3366 | ||
3367 | #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS | |
3368 | public: | |
3369 | unsigned int num_expand_fwd; | |
3370 | unsigned int num_expand_bwd; | |
3371 | unsigned int num_shrink; | |
3372 | unsigned int num_alloc; | |
3373 | void reset_alloc_stats() | |
3374 | { num_expand_fwd = num_expand_bwd = num_alloc = 0, num_shrink = 0; } | |
3375 | #endif | |
3376 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
3377 | }; | |
3378 | ||
3379 | }} //namespace boost::container | |
3380 | ||
3381 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
3382 | ||
3383 | namespace boost { | |
3384 | ||
3385 | //!has_trivial_destructor_after_move<> == true_type | |
3386 | //!specialization for optimizations | |
3387 | template <class T, class Allocator> | |
3388 | struct has_trivial_destructor_after_move<boost::container::vector<T, Allocator> > | |
3389 | { | |
3390 | typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; | |
3391 | static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && | |
3392 | ::boost::has_trivial_destructor_after_move<pointer>::value; | |
3393 | }; | |
3394 | ||
3395 | } | |
3396 | ||
3397 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
3398 | ||
3399 | #include <boost/container/detail/config_end.hpp> | |
3400 | ||
3401 | #endif // #ifndef BOOST_CONTAINER_CONTAINER_VECTOR_HPP |