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