]>
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 | #ifndef BOOST_CONTAINER_DEQUE_HPP | |
11 | #define BOOST_CONTAINER_DEQUE_HPP | |
12 | ||
13 | #ifndef BOOST_CONFIG_HPP | |
14 | # include <boost/config.hpp> | |
15 | #endif | |
16 | ||
17 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
18 | # pragma once | |
19 | #endif | |
20 | ||
21 | #include <boost/container/detail/config_begin.hpp> | |
22 | #include <boost/container/detail/workaround.hpp> | |
23 | // container | |
24 | #include <boost/container/allocator_traits.hpp> | |
25 | #include <boost/container/container_fwd.hpp> | |
26 | #include <boost/container/new_allocator.hpp> //new_allocator | |
27 | #include <boost/container/throw_exception.hpp> | |
28 | // container/detail | |
29 | #include <boost/container/detail/advanced_insert_int.hpp> | |
30 | #include <boost/container/detail/algorithm.hpp> //algo_equal(), algo_lexicographical_compare | |
31 | #include <boost/container/detail/alloc_helpers.hpp> | |
32 | #include <boost/container/detail/copy_move_algo.hpp> | |
33 | #include <boost/container/detail/iterator.hpp> | |
34 | #include <boost/container/detail/iterator_to_raw_pointer.hpp> | |
35 | #include <boost/container/detail/iterators.hpp> | |
36 | #include <boost/container/detail/min_max.hpp> | |
37 | #include <boost/container/detail/mpl.hpp> | |
38 | #include <boost/container/detail/to_raw_pointer.hpp> | |
39 | #include <boost/container/detail/type_traits.hpp> | |
40 | // move | |
41 | #include <boost/move/adl_move_swap.hpp> | |
42 | #include <boost/move/iterator.hpp> | |
43 | #include <boost/move/traits.hpp> | |
44 | #include <boost/move/utility_core.hpp> | |
45 | // move/detail | |
46 | #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
47 | #include <boost/move/detail/fwd_macros.hpp> | |
48 | #endif | |
49 | #include <boost/move/detail/move_helpers.hpp> | |
50 | // other | |
51 | #include <boost/assert.hpp> | |
52 | #include <boost/core/no_exceptions_support.hpp> | |
53 | // std | |
54 | #include <cstddef> | |
55 | ||
56 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
57 | #include <initializer_list> | |
58 | #endif | |
59 | ||
60 | namespace boost { | |
61 | namespace container { | |
62 | ||
63 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
64 | template <class T, class Allocator> | |
65 | class deque; | |
66 | ||
67 | template <class T> | |
68 | struct deque_value_traits | |
69 | { | |
70 | typedef T value_type; | |
71 | static const bool trivial_dctr = container_detail::is_trivially_destructible<value_type>::value; | |
72 | static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value; | |
73 | }; | |
74 | ||
75 | // Note: this function is simply a kludge to work around several compilers' | |
76 | // bugs in handling constant expressions. | |
77 | template<class T> | |
78 | struct deque_buf_size | |
79 | { | |
80 | static const std::size_t min_size = 512u; | |
81 | static const std::size_t sizeof_t = sizeof(T); | |
82 | static const std::size_t value = sizeof_t < min_size ? (min_size/sizeof_t) : std::size_t(1); | |
83 | }; | |
84 | ||
85 | namespace container_detail { | |
86 | ||
87 | // Class invariants: | |
88 | // For any nonsingular iterator i: | |
89 | // i.node is the address of an element in the map array. The | |
90 | // contents of i.node is a pointer to the beginning of a node. | |
91 | // i.first == //(i.node) | |
92 | // i.last == i.first + node_size | |
93 | // i.cur is a pointer in the range [i.first, i.last). NOTE: | |
94 | // the implication of this is that i.cur is always a dereferenceable | |
95 | // pointer, even if i is a past-the-end iterator. | |
96 | // Start and Finish are always nonsingular iterators. NOTE: this means | |
97 | // that an empty deque must have one node, and that a deque | |
98 | // with N elements, where N is the buffer size, must have two nodes. | |
99 | // For every node other than start.node and finish.node, every element | |
100 | // in the node is an initialized object. If start.node == finish.node, | |
101 | // then [start.cur, finish.cur) are initialized objects, and | |
102 | // the elements outside that range are uninitialized storage. Otherwise, | |
103 | // [start.cur, start.last) and [finish.first, finish.cur) are initialized | |
104 | // objects, and [start.first, start.cur) and [finish.cur, finish.last) | |
105 | // are uninitialized storage. | |
106 | // [map, map + map_size) is a valid, non-empty range. | |
107 | // [start.node, finish.node] is a valid range contained within | |
108 | // [map, map + map_size). | |
109 | // A pointer in the range [map, map + map_size) points to an allocated node | |
110 | // if and only if the pointer is in the range [start.node, finish.node]. | |
111 | template<class Pointer, bool IsConst> | |
112 | class deque_iterator | |
113 | { | |
114 | public: | |
115 | typedef std::random_access_iterator_tag iterator_category; | |
116 | typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type; | |
117 | typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type; | |
118 | typedef typename if_c | |
119 | < IsConst | |
120 | , typename boost::intrusive::pointer_traits<Pointer>::template | |
121 | rebind_pointer<const value_type>::type | |
122 | , Pointer | |
123 | >::type pointer; | |
124 | typedef typename if_c | |
125 | < IsConst | |
126 | , const value_type& | |
127 | , value_type& | |
128 | >::type reference; | |
129 | ||
130 | static std::size_t s_buffer_size() | |
131 | { return deque_buf_size<value_type>::value; } | |
132 | ||
133 | typedef Pointer val_alloc_ptr; | |
134 | typedef typename boost::intrusive::pointer_traits<Pointer>:: | |
135 | template rebind_pointer<Pointer>::type index_pointer; | |
136 | ||
137 | Pointer m_cur; | |
138 | Pointer m_first; | |
139 | Pointer m_last; | |
140 | index_pointer m_node; | |
141 | ||
142 | public: | |
143 | ||
144 | Pointer get_cur() const { return m_cur; } | |
145 | Pointer get_first() const { return m_first; } | |
146 | Pointer get_last() const { return m_last; } | |
147 | index_pointer get_node() const { return m_node; } | |
148 | ||
149 | deque_iterator(val_alloc_ptr x, index_pointer y) BOOST_NOEXCEPT_OR_NOTHROW | |
150 | : m_cur(x), m_first(*y), m_last(*y + s_buffer_size()), m_node(y) | |
151 | {} | |
152 | ||
153 | deque_iterator() BOOST_NOEXCEPT_OR_NOTHROW | |
154 | : m_cur(), m_first(), m_last(), m_node() //Value initialization to achieve "null iterators" (N3644) | |
155 | {} | |
156 | ||
157 | deque_iterator(deque_iterator<Pointer, false> const& x) BOOST_NOEXCEPT_OR_NOTHROW | |
158 | : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node()) | |
159 | {} | |
160 | ||
161 | deque_iterator(Pointer cur, Pointer first, Pointer last, index_pointer node) BOOST_NOEXCEPT_OR_NOTHROW | |
162 | : m_cur(cur), m_first(first), m_last(last), m_node(node) | |
163 | {} | |
164 | ||
165 | deque_iterator<Pointer, false> unconst() const BOOST_NOEXCEPT_OR_NOTHROW | |
166 | { | |
167 | return deque_iterator<Pointer, false>(this->get_cur(), this->get_first(), this->get_last(), this->get_node()); | |
168 | } | |
169 | ||
170 | reference operator*() const BOOST_NOEXCEPT_OR_NOTHROW | |
171 | { return *this->m_cur; } | |
172 | ||
173 | pointer operator->() const BOOST_NOEXCEPT_OR_NOTHROW | |
174 | { return this->m_cur; } | |
175 | ||
176 | difference_type operator-(const deque_iterator& x) const BOOST_NOEXCEPT_OR_NOTHROW | |
177 | { | |
178 | if(!this->m_cur && !x.m_cur){ | |
179 | return 0; | |
180 | } | |
181 | return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) + | |
182 | (this->m_cur - this->m_first) + (x.m_last - x.m_cur); | |
183 | } | |
184 | ||
185 | deque_iterator& operator++() BOOST_NOEXCEPT_OR_NOTHROW | |
186 | { | |
187 | ++this->m_cur; | |
188 | if (this->m_cur == this->m_last) { | |
189 | this->priv_set_node(this->m_node + 1); | |
190 | this->m_cur = this->m_first; | |
191 | } | |
192 | return *this; | |
193 | } | |
194 | ||
195 | deque_iterator operator++(int) BOOST_NOEXCEPT_OR_NOTHROW | |
196 | { | |
197 | deque_iterator tmp(*this); | |
198 | ++*this; | |
199 | return tmp; | |
200 | } | |
201 | ||
202 | deque_iterator& operator--() BOOST_NOEXCEPT_OR_NOTHROW | |
203 | { | |
204 | if (this->m_cur == this->m_first) { | |
205 | this->priv_set_node(this->m_node - 1); | |
206 | this->m_cur = this->m_last; | |
207 | } | |
208 | --this->m_cur; | |
209 | return *this; | |
210 | } | |
211 | ||
212 | deque_iterator operator--(int) BOOST_NOEXCEPT_OR_NOTHROW | |
213 | { | |
214 | deque_iterator tmp(*this); | |
215 | --*this; | |
216 | return tmp; | |
217 | } | |
218 | ||
219 | deque_iterator& operator+=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
220 | { | |
221 | difference_type offset = n + (this->m_cur - this->m_first); | |
222 | if (offset >= 0 && offset < difference_type(this->s_buffer_size())) | |
223 | this->m_cur += n; | |
224 | else { | |
225 | difference_type node_offset = | |
226 | offset > 0 ? offset / difference_type(this->s_buffer_size()) | |
227 | : -difference_type((-offset - 1) / this->s_buffer_size()) - 1; | |
228 | this->priv_set_node(this->m_node + node_offset); | |
229 | this->m_cur = this->m_first + | |
230 | (offset - node_offset * difference_type(this->s_buffer_size())); | |
231 | } | |
232 | return *this; | |
233 | } | |
234 | ||
235 | deque_iterator operator+(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
236 | { deque_iterator tmp(*this); return tmp += n; } | |
237 | ||
238 | deque_iterator& operator-=(difference_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
239 | { return *this += -n; } | |
240 | ||
241 | deque_iterator operator-(difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
242 | { deque_iterator tmp(*this); return tmp -= n; } | |
243 | ||
244 | reference operator[](difference_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
245 | { return *(*this + n); } | |
246 | ||
247 | friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW | |
248 | { return l.m_cur == r.m_cur; } | |
249 | ||
250 | friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW | |
251 | { return l.m_cur != r.m_cur; } | |
252 | ||
253 | friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW | |
254 | { return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); } | |
255 | ||
256 | friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW | |
257 | { return r < l; } | |
258 | ||
259 | friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW | |
260 | { return !(r < l); } | |
261 | ||
262 | friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_NOEXCEPT_OR_NOTHROW | |
263 | { return !(l < r); } | |
264 | ||
265 | void priv_set_node(index_pointer new_node) BOOST_NOEXCEPT_OR_NOTHROW | |
266 | { | |
267 | this->m_node = new_node; | |
268 | this->m_first = *new_node; | |
269 | this->m_last = this->m_first + this->s_buffer_size(); | |
270 | } | |
271 | ||
272 | friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_NOEXCEPT_OR_NOTHROW | |
273 | { return x += n; } | |
274 | }; | |
275 | ||
276 | } //namespace container_detail { | |
277 | ||
278 | // Deque base class. It has two purposes. First, its constructor | |
279 | // and destructor allocate (but don't initialize) storage. This makes | |
280 | // exception safety easier. | |
281 | template <class Allocator> | |
282 | class deque_base | |
283 | { | |
284 | BOOST_COPYABLE_AND_MOVABLE(deque_base) | |
285 | public: | |
286 | typedef allocator_traits<Allocator> val_alloc_traits_type; | |
287 | typedef typename val_alloc_traits_type::value_type val_alloc_val; | |
288 | typedef typename val_alloc_traits_type::pointer val_alloc_ptr; | |
289 | typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr; | |
290 | typedef typename val_alloc_traits_type::reference val_alloc_ref; | |
291 | typedef typename val_alloc_traits_type::const_reference val_alloc_cref; | |
292 | typedef typename val_alloc_traits_type::difference_type val_alloc_diff; | |
293 | typedef typename val_alloc_traits_type::size_type val_alloc_size; | |
294 | typedef typename val_alloc_traits_type::template | |
295 | portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t; | |
296 | typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type; | |
297 | typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val; | |
298 | typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr; | |
299 | typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr; | |
300 | typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref; | |
301 | typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref; | |
302 | typedef Allocator allocator_type; | |
303 | typedef allocator_type stored_allocator_type; | |
304 | typedef val_alloc_size size_type; | |
305 | ||
306 | protected: | |
307 | ||
308 | typedef deque_value_traits<val_alloc_val> traits_t; | |
309 | typedef ptr_alloc_t map_allocator_type; | |
310 | ||
311 | static size_type s_buffer_size() BOOST_NOEXCEPT_OR_NOTHROW | |
312 | { return deque_buf_size<val_alloc_val>::value; } | |
313 | ||
314 | val_alloc_ptr priv_allocate_node() | |
315 | { return this->alloc().allocate(s_buffer_size()); } | |
316 | ||
317 | void priv_deallocate_node(val_alloc_ptr p) BOOST_NOEXCEPT_OR_NOTHROW | |
318 | { this->alloc().deallocate(p, s_buffer_size()); } | |
319 | ||
320 | ptr_alloc_ptr priv_allocate_map(size_type n) | |
321 | { return this->ptr_alloc().allocate(n); } | |
322 | ||
323 | void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
324 | { this->ptr_alloc().deallocate(p, n); } | |
325 | ||
326 | typedef container_detail::deque_iterator<val_alloc_ptr, false> iterator; | |
327 | typedef container_detail::deque_iterator<val_alloc_ptr, true > const_iterator; | |
328 | ||
329 | deque_base(size_type num_elements, const allocator_type& a) | |
330 | : members_(a) | |
331 | { this->priv_initialize_map(num_elements); } | |
332 | ||
333 | explicit deque_base(const allocator_type& a) | |
334 | : members_(a) | |
335 | {} | |
336 | ||
337 | deque_base() | |
338 | : members_() | |
339 | {} | |
340 | ||
341 | explicit deque_base(BOOST_RV_REF(deque_base) x) | |
342 | : members_( boost::move(x.ptr_alloc()) | |
343 | , boost::move(x.alloc()) ) | |
344 | {} | |
345 | ||
346 | ~deque_base() | |
347 | { | |
348 | if (this->members_.m_map) { | |
349 | this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1); | |
350 | this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); | |
351 | } | |
352 | } | |
353 | ||
354 | private: | |
355 | deque_base(const deque_base&); | |
356 | ||
357 | protected: | |
358 | ||
359 | void swap_members(deque_base &x) BOOST_NOEXCEPT_OR_NOTHROW | |
360 | { | |
361 | ::boost::adl_move_swap(this->members_.m_start, x.members_.m_start); | |
362 | ::boost::adl_move_swap(this->members_.m_finish, x.members_.m_finish); | |
363 | ::boost::adl_move_swap(this->members_.m_map, x.members_.m_map); | |
364 | ::boost::adl_move_swap(this->members_.m_map_size, x.members_.m_map_size); | |
365 | } | |
366 | ||
367 | void priv_initialize_map(size_type num_elements) | |
368 | { | |
369 | // if(num_elements){ | |
370 | size_type num_nodes = num_elements / s_buffer_size() + 1; | |
371 | ||
372 | this->members_.m_map_size = container_detail::max_value((size_type) InitialMapSize, num_nodes + 2); | |
373 | this->members_.m_map = this->priv_allocate_map(this->members_.m_map_size); | |
374 | ||
375 | ptr_alloc_ptr nstart = this->members_.m_map + (this->members_.m_map_size - num_nodes) / 2; | |
376 | ptr_alloc_ptr nfinish = nstart + num_nodes; | |
377 | ||
378 | BOOST_TRY { | |
379 | this->priv_create_nodes(nstart, nfinish); | |
380 | } | |
381 | BOOST_CATCH(...){ | |
382 | this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); | |
383 | this->members_.m_map = 0; | |
384 | this->members_.m_map_size = 0; | |
385 | BOOST_RETHROW | |
386 | } | |
387 | BOOST_CATCH_END | |
388 | ||
389 | this->members_.m_start.priv_set_node(nstart); | |
390 | this->members_.m_finish.priv_set_node(nfinish - 1); | |
391 | this->members_.m_start.m_cur = this->members_.m_start.m_first; | |
392 | this->members_.m_finish.m_cur = this->members_.m_finish.m_first + | |
393 | num_elements % s_buffer_size(); | |
394 | // } | |
395 | } | |
396 | ||
397 | void priv_create_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) | |
398 | { | |
399 | ptr_alloc_ptr cur = nstart; | |
400 | BOOST_TRY { | |
401 | for (; cur < nfinish; ++cur) | |
402 | *cur = this->priv_allocate_node(); | |
403 | } | |
404 | BOOST_CATCH(...){ | |
405 | this->priv_destroy_nodes(nstart, cur); | |
406 | BOOST_RETHROW | |
407 | } | |
408 | BOOST_CATCH_END | |
409 | } | |
410 | ||
411 | void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_NOEXCEPT_OR_NOTHROW | |
412 | { | |
413 | for (ptr_alloc_ptr n = nstart; n < nfinish; ++n) | |
414 | this->priv_deallocate_node(*n); | |
415 | } | |
416 | ||
417 | void priv_clear_map() BOOST_NOEXCEPT_OR_NOTHROW | |
418 | { | |
419 | if (this->members_.m_map) { | |
420 | this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1); | |
421 | this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); | |
422 | this->members_.m_map = 0; | |
423 | this->members_.m_map_size = 0; | |
424 | this->members_.m_start = iterator(); | |
425 | this->members_.m_finish = this->members_.m_start; | |
426 | } | |
427 | } | |
428 | ||
429 | enum { InitialMapSize = 8 }; | |
430 | ||
431 | protected: | |
432 | struct members_holder | |
433 | : public ptr_alloc_t | |
434 | , public allocator_type | |
435 | { | |
436 | members_holder() | |
437 | : map_allocator_type(), allocator_type() | |
438 | , m_map(0), m_map_size(0) | |
439 | , m_start(), m_finish(m_start) | |
440 | {} | |
441 | ||
442 | explicit members_holder(const allocator_type &a) | |
443 | : map_allocator_type(a), allocator_type(a) | |
444 | , m_map(0), m_map_size(0) | |
445 | , m_start(), m_finish(m_start) | |
446 | {} | |
447 | ||
448 | template<class ValAllocConvertible, class PtrAllocConvertible> | |
449 | members_holder(BOOST_FWD_REF(PtrAllocConvertible) pa, BOOST_FWD_REF(ValAllocConvertible) va) | |
450 | : map_allocator_type(boost::forward<PtrAllocConvertible>(pa)) | |
451 | , allocator_type (boost::forward<ValAllocConvertible>(va)) | |
452 | , m_map(0), m_map_size(0) | |
453 | , m_start(), m_finish(m_start) | |
454 | {} | |
455 | ||
456 | ptr_alloc_ptr m_map; | |
457 | val_alloc_size m_map_size; | |
458 | iterator m_start; | |
459 | iterator m_finish; | |
460 | } members_; | |
461 | ||
462 | ptr_alloc_t &ptr_alloc() BOOST_NOEXCEPT_OR_NOTHROW | |
463 | { return members_; } | |
464 | ||
465 | const ptr_alloc_t &ptr_alloc() const BOOST_NOEXCEPT_OR_NOTHROW | |
466 | { return members_; } | |
467 | ||
468 | allocator_type &alloc() BOOST_NOEXCEPT_OR_NOTHROW | |
469 | { return members_; } | |
470 | ||
471 | const allocator_type &alloc() const BOOST_NOEXCEPT_OR_NOTHROW | |
472 | { return members_; } | |
473 | }; | |
474 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
475 | ||
476 | #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED | |
477 | //! A double-ended queue is a sequence that supports random access to elements, constant time insertion | |
478 | //! and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle. | |
479 | //! | |
480 | //! \tparam T The type of object that is stored in the deque | |
481 | //! \tparam Allocator The allocator used for all internal memory management | |
482 | template <class T, class Allocator = new_allocator<T> > | |
483 | #else | |
484 | template <class T, class Allocator> | |
485 | #endif | |
486 | class deque : protected deque_base<Allocator> | |
487 | { | |
488 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
489 | private: | |
490 | typedef deque_base<Allocator> Base; | |
491 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
492 | ||
493 | public: | |
494 | ||
495 | ////////////////////////////////////////////// | |
496 | // | |
497 | // types | |
498 | // | |
499 | ////////////////////////////////////////////// | |
500 | ||
501 | typedef T value_type; | |
502 | typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; | |
503 | typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer; | |
504 | typedef typename ::boost::container::allocator_traits<Allocator>::reference reference; | |
505 | typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference; | |
506 | typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type; | |
507 | typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; | |
508 | typedef Allocator allocator_type; | |
509 | typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type; | |
510 | typedef BOOST_CONTAINER_IMPDEF(typename Base::iterator) iterator; | |
511 | typedef BOOST_CONTAINER_IMPDEF(typename Base::const_iterator) const_iterator; | |
512 | typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator; | |
513 | typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator; | |
514 | ||
515 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
516 | ||
517 | private: // Internal typedefs | |
518 | BOOST_COPYABLE_AND_MOVABLE(deque) | |
519 | typedef typename Base::ptr_alloc_ptr index_pointer; | |
520 | static size_type s_buffer_size() | |
521 | { return Base::s_buffer_size(); } | |
522 | typedef allocator_traits<Allocator> allocator_traits_type; | |
523 | ||
524 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
525 | ||
526 | public: | |
527 | ////////////////////////////////////////////// | |
528 | // | |
529 | // construct/copy/destroy | |
530 | // | |
531 | ////////////////////////////////////////////// | |
532 | ||
533 | //! <b>Effects</b>: Default constructors a deque. | |
534 | //! | |
535 | //! <b>Throws</b>: If allocator_type's default constructor throws. | |
536 | //! | |
537 | //! <b>Complexity</b>: Constant. | |
538 | deque() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value) | |
539 | : Base() | |
540 | {} | |
541 | ||
542 | //! <b>Effects</b>: Constructs a deque taking the allocator as parameter. | |
543 | //! | |
544 | //! <b>Throws</b>: Nothing | |
545 | //! | |
546 | //! <b>Complexity</b>: Constant. | |
547 | explicit deque(const allocator_type& a) BOOST_NOEXCEPT_OR_NOTHROW | |
548 | : Base(a) | |
549 | {} | |
550 | ||
551 | //! <b>Effects</b>: Constructs a deque | |
552 | //! and inserts n value initialized values. | |
553 | //! | |
554 | //! <b>Throws</b>: If allocator_type's default constructor | |
555 | //! throws or T's value initialization throws. | |
556 | //! | |
557 | //! <b>Complexity</b>: Linear to n. | |
558 | explicit deque(size_type n) | |
559 | : Base(n, allocator_type()) | |
560 | { | |
561 | container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy; | |
562 | proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); | |
563 | //deque_base will deallocate in case of exception... | |
564 | } | |
565 | ||
566 | //! <b>Effects</b>: Constructs a deque | |
567 | //! and inserts n default initialized values. | |
568 | //! | |
569 | //! <b>Throws</b>: If allocator_type's default constructor | |
570 | //! throws or T's default initialization or copy constructor throws. | |
571 | //! | |
572 | //! <b>Complexity</b>: Linear to n. | |
573 | //! | |
574 | //! <b>Note</b>: Non-standard extension | |
575 | deque(size_type n, default_init_t) | |
576 | : Base(n, allocator_type()) | |
577 | { | |
578 | container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy; | |
579 | proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); | |
580 | //deque_base will deallocate in case of exception... | |
581 | } | |
582 | ||
583 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
584 | //! and inserts n value initialized values. | |
585 | //! | |
586 | //! <b>Throws</b>: If allocator_type's default constructor | |
587 | //! throws or T's value initialization throws. | |
588 | //! | |
589 | //! <b>Complexity</b>: Linear to n. | |
590 | explicit deque(size_type n, const allocator_type &a) | |
591 | : Base(n, a) | |
592 | { | |
593 | container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy; | |
594 | proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); | |
595 | //deque_base will deallocate in case of exception... | |
596 | } | |
597 | ||
598 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
599 | //! and inserts n default initialized values. | |
600 | //! | |
601 | //! <b>Throws</b>: If allocator_type's default constructor | |
602 | //! throws or T's default initialization or copy constructor throws. | |
603 | //! | |
604 | //! <b>Complexity</b>: Linear to n. | |
605 | //! | |
606 | //! <b>Note</b>: Non-standard extension | |
607 | deque(size_type n, default_init_t, const allocator_type &a) | |
608 | : Base(n, a) | |
609 | { | |
610 | container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy; | |
611 | proxy.uninitialized_copy_n_and_update(this->alloc(), this->begin(), n); | |
612 | //deque_base will deallocate in case of exception... | |
613 | } | |
614 | ||
615 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
616 | //! and inserts n copies of value. | |
617 | //! | |
618 | //! <b>Throws</b>: If allocator_type's default constructor | |
619 | //! throws or T's copy constructor throws. | |
620 | //! | |
621 | //! <b>Complexity</b>: Linear to n. | |
622 | deque(size_type n, const value_type& value) | |
623 | : Base(n, allocator_type()) | |
624 | { this->priv_fill_initialize(value); } | |
625 | ||
626 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
627 | //! and inserts n copies of value. | |
628 | //! | |
629 | //! <b>Throws</b>: If allocator_type's default constructor | |
630 | //! throws or T's copy constructor throws. | |
631 | //! | |
632 | //! <b>Complexity</b>: Linear to n. | |
633 | deque(size_type n, const value_type& value, const allocator_type& a) | |
634 | : Base(n, a) | |
635 | { this->priv_fill_initialize(value); } | |
636 | ||
637 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
638 | //! and inserts a copy of the range [first, last) in the deque. | |
639 | //! | |
640 | //! <b>Throws</b>: If allocator_type's default constructor | |
641 | //! throws or T's constructor taking a dereferenced InIt throws. | |
642 | //! | |
643 | //! <b>Complexity</b>: Linear to the range [first, last). | |
644 | template <class InIt> | |
645 | deque(InIt first, InIt last | |
646 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
647 | , typename container_detail::disable_if_convertible | |
648 | <InIt, size_type>::type * = 0 | |
649 | #endif | |
650 | ) | |
651 | : Base(allocator_type()) | |
652 | { | |
653 | this->priv_range_initialize(first, last); | |
654 | } | |
655 | ||
656 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
657 | //! and inserts a copy of the range [first, last) in the deque. | |
658 | //! | |
659 | //! <b>Throws</b>: If allocator_type's default constructor | |
660 | //! throws or T's constructor taking a dereferenced InIt throws. | |
661 | //! | |
662 | //! <b>Complexity</b>: Linear to the range [first, last). | |
663 | template <class InIt> | |
664 | deque(InIt first, InIt last, const allocator_type& a | |
665 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
666 | , typename container_detail::disable_if_convertible | |
667 | <InIt, size_type>::type * = 0 | |
668 | #endif | |
669 | ) | |
670 | : Base(a) | |
671 | { | |
672 | this->priv_range_initialize(first, last); | |
673 | } | |
674 | ||
675 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
676 | //! <b>Effects</b>: Constructs a deque that will use a copy of allocator a | |
677 | //! and inserts a copy of the range [il.begin(), il.end()) in the deque. | |
678 | //! | |
679 | //! <b>Throws</b>: If allocator_type's default constructor | |
680 | //! throws or T's constructor taking a dereferenced std::initializer_list iterator throws. | |
681 | //! | |
682 | //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()). | |
683 | deque(std::initializer_list<value_type> il, const allocator_type& a = allocator_type()) | |
684 | : Base(a) | |
685 | { | |
686 | this->priv_range_initialize(il.begin(), il.end()); | |
687 | } | |
688 | #endif | |
689 | ||
690 | //! <b>Effects</b>: Copy constructs a deque. | |
691 | //! | |
692 | //! <b>Postcondition</b>: x == *this. | |
693 | //! | |
694 | //! <b>Complexity</b>: Linear to the elements x contains. | |
695 | deque(const deque& x) | |
696 | : Base(allocator_traits_type::select_on_container_copy_construction(x.alloc())) | |
697 | { | |
698 | if(x.size()){ | |
699 | this->priv_initialize_map(x.size()); | |
700 | boost::container::uninitialized_copy_alloc | |
701 | (this->alloc(), x.begin(), x.end(), this->members_.m_start); | |
702 | } | |
703 | } | |
704 | ||
705 | //! <b>Effects</b>: Move constructor. Moves x's resources to *this. | |
706 | //! | |
707 | //! <b>Throws</b>: If allocator_type's copy constructor throws. | |
708 | //! | |
709 | //! <b>Complexity</b>: Constant. | |
710 | deque(BOOST_RV_REF(deque) x) BOOST_NOEXCEPT_OR_NOTHROW | |
711 | : Base(BOOST_MOVE_BASE(Base, x)) | |
712 | { this->swap_members(x); } | |
713 | ||
714 | //! <b>Effects</b>: Copy constructs a vector using the specified allocator. | |
715 | //! | |
716 | //! <b>Postcondition</b>: x == *this. | |
717 | //! | |
718 | //! <b>Throws</b>: If allocation | |
719 | //! throws or T's copy constructor throws. | |
720 | //! | |
721 | //! <b>Complexity</b>: Linear to the elements x contains. | |
722 | deque(const deque& x, const allocator_type &a) | |
723 | : Base(a) | |
724 | { | |
725 | if(x.size()){ | |
726 | this->priv_initialize_map(x.size()); | |
727 | boost::container::uninitialized_copy_alloc | |
728 | (this->alloc(), x.begin(), x.end(), this->members_.m_start); | |
729 | } | |
730 | } | |
731 | ||
732 | //! <b>Effects</b>: Move constructor using the specified allocator. | |
733 | //! Moves x's resources to *this if a == allocator_type(). | |
734 | //! Otherwise copies values from x to *this. | |
735 | //! | |
736 | //! <b>Throws</b>: If allocation or T's copy constructor throws. | |
737 | //! | |
738 | //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. | |
739 | deque(BOOST_RV_REF(deque) x, const allocator_type &a) | |
740 | : Base(a) | |
741 | { | |
742 | if(x.alloc() == a){ | |
743 | this->swap_members(x); | |
744 | } | |
745 | else{ | |
746 | if(x.size()){ | |
747 | this->priv_initialize_map(x.size()); | |
748 | boost::container::uninitialized_copy_alloc | |
749 | ( this->alloc(), boost::make_move_iterator(x.begin()) | |
750 | , boost::make_move_iterator(x.end()), this->members_.m_start); | |
751 | } | |
752 | } | |
753 | } | |
754 | ||
755 | //! <b>Effects</b>: Destroys the deque. All stored values are destroyed | |
756 | //! and used memory is deallocated. | |
757 | //! | |
758 | //! <b>Throws</b>: Nothing. | |
759 | //! | |
760 | //! <b>Complexity</b>: Linear to the number of elements. | |
761 | ~deque() BOOST_NOEXCEPT_OR_NOTHROW | |
762 | { | |
763 | this->priv_destroy_range(this->members_.m_start, this->members_.m_finish); | |
764 | } | |
765 | ||
766 | //! <b>Effects</b>: Makes *this contain the same elements as x. | |
767 | //! | |
768 | //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy | |
769 | //! of each of x's elements. | |
770 | //! | |
771 | //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. | |
772 | //! | |
773 | //! <b>Complexity</b>: Linear to the number of elements in x. | |
774 | deque& operator= (BOOST_COPY_ASSIGN_REF(deque) x) | |
775 | { | |
776 | if (&x != this){ | |
777 | allocator_type &this_alloc = this->alloc(); | |
778 | const allocator_type &x_alloc = x.alloc(); | |
779 | container_detail::bool_<allocator_traits_type:: | |
780 | propagate_on_container_copy_assignment::value> flag; | |
781 | if(flag && this_alloc != x_alloc){ | |
782 | this->clear(); | |
783 | this->shrink_to_fit(); | |
784 | } | |
785 | container_detail::assign_alloc(this->alloc(), x.alloc(), flag); | |
786 | container_detail::assign_alloc(this->ptr_alloc(), x.ptr_alloc(), flag); | |
787 | this->assign(x.cbegin(), x.cend()); | |
788 | } | |
789 | return *this; | |
790 | } | |
791 | ||
792 | //! <b>Effects</b>: Move assignment. All x's values are transferred to *this. | |
793 | //! | |
794 | //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment | |
795 | //! is false and (allocation throws or value_type's move constructor throws) | |
796 | //! | |
797 | //! <b>Complexity</b>: Constant if allocator_traits_type:: | |
798 | //! propagate_on_container_move_assignment is true or | |
799 | //! this->get>allocator() == x.get_allocator(). Linear otherwise. | |
800 | deque& operator= (BOOST_RV_REF(deque) x) | |
801 | BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value | |
802 | || allocator_traits_type::is_always_equal::value) | |
803 | { | |
804 | BOOST_ASSERT(this != &x); | |
805 | allocator_type &this_alloc = this->alloc(); | |
806 | allocator_type &x_alloc = x.alloc(); | |
807 | const bool propagate_alloc = allocator_traits_type:: | |
808 | propagate_on_container_move_assignment::value; | |
809 | container_detail::bool_<propagate_alloc> flag; | |
810 | const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal; | |
811 | //Resources can be transferred if both allocators are | |
812 | //going to be equal after this function (either propagated or already equal) | |
813 | if(propagate_alloc || allocators_equal){ | |
814 | //Destroy objects but retain memory in case x reuses it in the future | |
815 | this->clear(); | |
816 | //Move allocator if needed | |
817 | container_detail::move_alloc(this_alloc, x_alloc, flag); | |
818 | container_detail::move_alloc(this->ptr_alloc(), x.ptr_alloc(), flag); | |
819 | //Nothrow swap | |
820 | this->swap_members(x); | |
821 | } | |
822 | //Else do a one by one move | |
823 | else{ | |
824 | this->assign( boost::make_move_iterator(x.begin()) | |
825 | , boost::make_move_iterator(x.end())); | |
826 | } | |
827 | return *this; | |
828 | } | |
829 | ||
830 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
831 | //! <b>Effects</b>: Makes *this contain the same elements as il. | |
832 | //! | |
833 | //! <b>Postcondition</b>: this->size() == il.size(). *this contains a copy | |
834 | //! of each of x's elements. | |
835 | //! | |
836 | //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. | |
837 | //! | |
838 | //! <b>Complexity</b>: Linear to the number of elements in il. | |
839 | deque& operator=(std::initializer_list<value_type> il) | |
840 | { | |
841 | this->assign(il.begin(), il.end()); | |
842 | return *this; | |
843 | } | |
844 | #endif | |
845 | ||
846 | //! <b>Effects</b>: Assigns the n copies of val to *this. | |
847 | //! | |
848 | //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. | |
849 | //! | |
850 | //! <b>Complexity</b>: Linear to n. | |
851 | void assign(size_type n, const T& val) | |
852 | { | |
853 | typedef constant_iterator<value_type, difference_type> c_it; | |
854 | this->assign(c_it(val, n), c_it()); | |
855 | } | |
856 | ||
857 | //! <b>Effects</b>: Assigns the the range [first, last) to *this. | |
858 | //! | |
859 | //! <b>Throws</b>: If memory allocation throws or | |
860 | //! T's constructor from dereferencing InIt throws. | |
861 | //! | |
862 | //! <b>Complexity</b>: Linear to n. | |
863 | template <class InIt> | |
864 | void assign(InIt first, InIt last | |
865 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
866 | , typename container_detail::disable_if_or | |
867 | < void | |
868 | , container_detail::is_convertible<InIt, size_type> | |
869 | , container_detail::is_not_input_iterator<InIt> | |
870 | >::type * = 0 | |
871 | #endif | |
872 | ) | |
873 | { | |
874 | iterator cur = this->begin(); | |
875 | for ( ; first != last && cur != end(); ++cur, ++first){ | |
876 | *cur = *first; | |
877 | } | |
878 | if (first == last){ | |
879 | this->erase(cur, this->cend()); | |
880 | } | |
881 | else{ | |
882 | this->insert(this->cend(), first, last); | |
883 | } | |
884 | } | |
885 | ||
886 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
887 | template <class FwdIt> | |
888 | void assign(FwdIt first, FwdIt last | |
889 | , typename container_detail::disable_if_or | |
890 | < void | |
891 | , container_detail::is_convertible<FwdIt, size_type> | |
892 | , container_detail::is_input_iterator<FwdIt> | |
893 | >::type * = 0 | |
894 | ) | |
895 | { | |
896 | const size_type len = boost::container::iterator_distance(first, last); | |
897 | if (len > size()) { | |
898 | FwdIt mid = first; | |
899 | boost::container::iterator_advance(mid, this->size()); | |
900 | boost::container::copy(first, mid, begin()); | |
901 | this->insert(this->cend(), mid, last); | |
902 | } | |
903 | else{ | |
904 | this->erase(boost::container::copy(first, last, this->begin()), cend()); | |
905 | } | |
906 | } | |
907 | #endif | |
908 | ||
909 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
910 | //! <b>Effects</b>: Assigns the the range [il.begin(), il.end()) to *this. | |
911 | //! | |
912 | //! <b>Throws</b>: If memory allocation throws or | |
913 | //! T's constructor from dereferencing std::initializer_list iterator throws. | |
914 | //! | |
915 | //! <b>Complexity</b>: Linear to il.size(). | |
916 | void assign(std::initializer_list<value_type> il) | |
917 | { this->assign(il.begin(), il.end()); } | |
918 | #endif | |
919 | ||
920 | //! <b>Effects</b>: Returns a copy of the internal allocator. | |
921 | //! | |
922 | //! <b>Throws</b>: If allocator's copy constructor throws. | |
923 | //! | |
924 | //! <b>Complexity</b>: Constant. | |
925 | allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
926 | { return Base::alloc(); } | |
927 | ||
928 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
929 | //! | |
930 | //! <b>Throws</b>: Nothing | |
931 | //! | |
932 | //! <b>Complexity</b>: Constant. | |
933 | //! | |
934 | //! <b>Note</b>: Non-standard extension. | |
935 | const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW | |
936 | { return Base::alloc(); } | |
937 | ||
938 | ////////////////////////////////////////////// | |
939 | // | |
940 | // iterators | |
941 | // | |
942 | ////////////////////////////////////////////// | |
943 | ||
944 | //! <b>Effects</b>: Returns a reference to the internal allocator. | |
945 | //! | |
946 | //! <b>Throws</b>: Nothing | |
947 | //! | |
948 | //! <b>Complexity</b>: Constant. | |
949 | //! | |
950 | //! <b>Note</b>: Non-standard extension. | |
951 | stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW | |
952 | { return Base::alloc(); } | |
953 | ||
954 | //! <b>Effects</b>: Returns an iterator to the first element contained in the deque. | |
955 | //! | |
956 | //! <b>Throws</b>: Nothing. | |
957 | //! | |
958 | //! <b>Complexity</b>: Constant. | |
959 | iterator begin() BOOST_NOEXCEPT_OR_NOTHROW | |
960 | { return this->members_.m_start; } | |
961 | ||
962 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque. | |
963 | //! | |
964 | //! <b>Throws</b>: Nothing. | |
965 | //! | |
966 | //! <b>Complexity</b>: Constant. | |
967 | const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW | |
968 | { return this->members_.m_start; } | |
969 | ||
970 | //! <b>Effects</b>: Returns an iterator to the end of the deque. | |
971 | //! | |
972 | //! <b>Throws</b>: Nothing. | |
973 | //! | |
974 | //! <b>Complexity</b>: Constant. | |
975 | iterator end() BOOST_NOEXCEPT_OR_NOTHROW | |
976 | { return this->members_.m_finish; } | |
977 | ||
978 | //! <b>Effects</b>: Returns a const_iterator to the end of the deque. | |
979 | //! | |
980 | //! <b>Throws</b>: Nothing. | |
981 | //! | |
982 | //! <b>Complexity</b>: Constant. | |
983 | const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW | |
984 | { return this->members_.m_finish; } | |
985 | ||
986 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning | |
987 | //! of the reversed deque. | |
988 | //! | |
989 | //! <b>Throws</b>: Nothing. | |
990 | //! | |
991 | //! <b>Complexity</b>: Constant. | |
992 | reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW | |
993 | { return reverse_iterator(this->members_.m_finish); } | |
994 | ||
995 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
996 | //! of the reversed deque. | |
997 | //! | |
998 | //! <b>Throws</b>: Nothing. | |
999 | //! | |
1000 | //! <b>Complexity</b>: Constant. | |
1001 | const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1002 | { return const_reverse_iterator(this->members_.m_finish); } | |
1003 | ||
1004 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end | |
1005 | //! of the reversed deque. | |
1006 | //! | |
1007 | //! <b>Throws</b>: Nothing. | |
1008 | //! | |
1009 | //! <b>Complexity</b>: Constant. | |
1010 | reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW | |
1011 | { return reverse_iterator(this->members_.m_start); } | |
1012 | ||
1013 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
1014 | //! of the reversed deque. | |
1015 | //! | |
1016 | //! <b>Throws</b>: Nothing. | |
1017 | //! | |
1018 | //! <b>Complexity</b>: Constant. | |
1019 | const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1020 | { return const_reverse_iterator(this->members_.m_start); } | |
1021 | ||
1022 | //! <b>Effects</b>: Returns a const_iterator to the first element contained in the deque. | |
1023 | //! | |
1024 | //! <b>Throws</b>: Nothing. | |
1025 | //! | |
1026 | //! <b>Complexity</b>: Constant. | |
1027 | const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1028 | { return this->members_.m_start; } | |
1029 | ||
1030 | //! <b>Effects</b>: Returns a const_iterator to the end of the deque. | |
1031 | //! | |
1032 | //! <b>Throws</b>: Nothing. | |
1033 | //! | |
1034 | //! <b>Complexity</b>: Constant. | |
1035 | const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1036 | { return this->members_.m_finish; } | |
1037 | ||
1038 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning | |
1039 | //! of the reversed deque. | |
1040 | //! | |
1041 | //! <b>Throws</b>: Nothing. | |
1042 | //! | |
1043 | //! <b>Complexity</b>: Constant. | |
1044 | const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW | |
1045 | { return const_reverse_iterator(this->members_.m_finish); } | |
1046 | ||
1047 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end | |
1048 | //! of the reversed deque. | |
1049 | //! | |
1050 | //! <b>Throws</b>: Nothing. | |
1051 | //! | |
1052 | //! <b>Complexity</b>: Constant. | |
1053 | const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW | |
1054 | { return const_reverse_iterator(this->members_.m_start); } | |
1055 | ||
1056 | ////////////////////////////////////////////// | |
1057 | // | |
1058 | // capacity | |
1059 | // | |
1060 | ////////////////////////////////////////////// | |
1061 | ||
1062 | //! <b>Effects</b>: Returns true if the deque contains no elements. | |
1063 | //! | |
1064 | //! <b>Throws</b>: Nothing. | |
1065 | //! | |
1066 | //! <b>Complexity</b>: Constant. | |
1067 | bool empty() const BOOST_NOEXCEPT_OR_NOTHROW | |
1068 | { return this->members_.m_finish == this->members_.m_start; } | |
1069 | ||
1070 | //! <b>Effects</b>: Returns the number of the elements contained in the deque. | |
1071 | //! | |
1072 | //! <b>Throws</b>: Nothing. | |
1073 | //! | |
1074 | //! <b>Complexity</b>: Constant. | |
1075 | size_type size() const BOOST_NOEXCEPT_OR_NOTHROW | |
1076 | { return this->members_.m_finish - this->members_.m_start; } | |
1077 | ||
1078 | //! <b>Effects</b>: Returns the largest possible size of the deque. | |
1079 | //! | |
1080 | //! <b>Throws</b>: Nothing. | |
1081 | //! | |
1082 | //! <b>Complexity</b>: Constant. | |
1083 | size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW | |
1084 | { return allocator_traits_type::max_size(this->alloc()); } | |
1085 | ||
1086 | //! <b>Effects</b>: Inserts or erases elements at the end such that | |
1087 | //! the size becomes n. New elements are value initialized. | |
1088 | //! | |
1089 | //! <b>Throws</b>: If memory allocation throws, or T's constructor throws. | |
1090 | //! | |
1091 | //! <b>Complexity</b>: Linear to the difference between size() and new_size. | |
1092 | void resize(size_type new_size) | |
1093 | { | |
1094 | const size_type len = size(); | |
1095 | if (new_size < len) | |
1096 | this->priv_erase_last_n(len - new_size); | |
1097 | else{ | |
1098 | const size_type n = new_size - this->size(); | |
1099 | container_detail::insert_value_initialized_n_proxy<Allocator, iterator> proxy; | |
1100 | priv_insert_back_aux_impl(n, proxy); | |
1101 | } | |
1102 | } | |
1103 | ||
1104 | //! <b>Effects</b>: Inserts or erases elements at the end such that | |
1105 | //! the size becomes n. New elements are default initialized. | |
1106 | //! | |
1107 | //! <b>Throws</b>: If memory allocation throws, or T's constructor throws. | |
1108 | //! | |
1109 | //! <b>Complexity</b>: Linear to the difference between size() and new_size. | |
1110 | //! | |
1111 | //! <b>Note</b>: Non-standard extension | |
1112 | void resize(size_type new_size, default_init_t) | |
1113 | { | |
1114 | const size_type len = size(); | |
1115 | if (new_size < len) | |
1116 | this->priv_erase_last_n(len - new_size); | |
1117 | else{ | |
1118 | const size_type n = new_size - this->size(); | |
1119 | container_detail::insert_default_initialized_n_proxy<Allocator, iterator> proxy; | |
1120 | priv_insert_back_aux_impl(n, proxy); | |
1121 | } | |
1122 | } | |
1123 | ||
1124 | //! <b>Effects</b>: Inserts or erases elements at the end such that | |
1125 | //! the size becomes n. New elements are copy constructed from x. | |
1126 | //! | |
1127 | //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. | |
1128 | //! | |
1129 | //! <b>Complexity</b>: Linear to the difference between size() and new_size. | |
1130 | void resize(size_type new_size, const value_type& x) | |
1131 | { | |
1132 | const size_type len = size(); | |
1133 | if (new_size < len) | |
1134 | this->erase(this->members_.m_start + new_size, this->members_.m_finish); | |
1135 | else | |
1136 | this->insert(this->members_.m_finish, new_size - len, x); | |
1137 | } | |
1138 | ||
1139 | //! <b>Effects</b>: Tries to deallocate the excess of memory created | |
1140 | //! with previous allocations. The size of the deque is unchanged | |
1141 | //! | |
1142 | //! <b>Throws</b>: If memory allocation throws. | |
1143 | //! | |
1144 | //! <b>Complexity</b>: Constant. | |
1145 | void shrink_to_fit() | |
1146 | { | |
1147 | //This deque implementation already | |
1148 | //deallocates excess nodes when erasing | |
1149 | //so there is nothing to do except for | |
1150 | //empty deque | |
1151 | if(this->empty()){ | |
1152 | this->priv_clear_map(); | |
1153 | } | |
1154 | } | |
1155 | ||
1156 | ////////////////////////////////////////////// | |
1157 | // | |
1158 | // element access | |
1159 | // | |
1160 | ////////////////////////////////////////////// | |
1161 | ||
1162 | //! <b>Requires</b>: !empty() | |
1163 | //! | |
1164 | //! <b>Effects</b>: Returns a reference to the first | |
1165 | //! element of the container. | |
1166 | //! | |
1167 | //! <b>Throws</b>: Nothing. | |
1168 | //! | |
1169 | //! <b>Complexity</b>: Constant. | |
1170 | reference front() BOOST_NOEXCEPT_OR_NOTHROW | |
1171 | { | |
1172 | BOOST_ASSERT(!this->empty()); | |
1173 | return *this->members_.m_start; | |
1174 | } | |
1175 | ||
1176 | //! <b>Requires</b>: !empty() | |
1177 | //! | |
1178 | //! <b>Effects</b>: Returns a const reference to the first element | |
1179 | //! from the beginning of the container. | |
1180 | //! | |
1181 | //! <b>Throws</b>: Nothing. | |
1182 | //! | |
1183 | //! <b>Complexity</b>: Constant. | |
1184 | const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW | |
1185 | { | |
1186 | BOOST_ASSERT(!this->empty()); | |
1187 | return *this->members_.m_start; | |
1188 | } | |
1189 | ||
1190 | //! <b>Requires</b>: !empty() | |
1191 | //! | |
1192 | //! <b>Effects</b>: Returns a reference to the last | |
1193 | //! element of the container. | |
1194 | //! | |
1195 | //! <b>Throws</b>: Nothing. | |
1196 | //! | |
1197 | //! <b>Complexity</b>: Constant. | |
1198 | reference back() BOOST_NOEXCEPT_OR_NOTHROW | |
1199 | { | |
1200 | BOOST_ASSERT(!this->empty()); | |
1201 | return *(end()-1); | |
1202 | } | |
1203 | ||
1204 | //! <b>Requires</b>: !empty() | |
1205 | //! | |
1206 | //! <b>Effects</b>: Returns a const reference to the last | |
1207 | //! element of the container. | |
1208 | //! | |
1209 | //! <b>Throws</b>: Nothing. | |
1210 | //! | |
1211 | //! <b>Complexity</b>: Constant. | |
1212 | const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW | |
1213 | { | |
1214 | BOOST_ASSERT(!this->empty()); | |
1215 | return *(cend()-1); | |
1216 | } | |
1217 | ||
1218 | //! <b>Requires</b>: size() > n. | |
1219 | //! | |
1220 | //! <b>Effects</b>: Returns a reference to the nth element | |
1221 | //! from the beginning of the container. | |
1222 | //! | |
1223 | //! <b>Throws</b>: Nothing. | |
1224 | //! | |
1225 | //! <b>Complexity</b>: Constant. | |
1226 | reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
1227 | { | |
1228 | BOOST_ASSERT(this->size() > n); | |
1229 | return this->members_.m_start[difference_type(n)]; | |
1230 | } | |
1231 | ||
1232 | //! <b>Requires</b>: size() > n. | |
1233 | //! | |
1234 | //! <b>Effects</b>: Returns a const reference to the nth element | |
1235 | //! from the beginning of the container. | |
1236 | //! | |
1237 | //! <b>Throws</b>: Nothing. | |
1238 | //! | |
1239 | //! <b>Complexity</b>: Constant. | |
1240 | const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
1241 | { | |
1242 | BOOST_ASSERT(this->size() > n); | |
1243 | return this->members_.m_start[difference_type(n)]; | |
1244 | } | |
1245 | ||
1246 | //! <b>Requires</b>: size() >= n. | |
1247 | //! | |
1248 | //! <b>Effects</b>: Returns an iterator to the nth element | |
1249 | //! from the beginning of the container. Returns end() | |
1250 | //! if n == size(). | |
1251 | //! | |
1252 | //! <b>Throws</b>: Nothing. | |
1253 | //! | |
1254 | //! <b>Complexity</b>: Constant. | |
1255 | //! | |
1256 | //! <b>Note</b>: Non-standard extension | |
1257 | iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW | |
1258 | { | |
1259 | BOOST_ASSERT(this->size() >= n); | |
1260 | return iterator(this->begin()+n); | |
1261 | } | |
1262 | ||
1263 | //! <b>Requires</b>: size() >= n. | |
1264 | //! | |
1265 | //! <b>Effects</b>: Returns a const_iterator to the nth element | |
1266 | //! from the beginning of the container. Returns end() | |
1267 | //! if n == size(). | |
1268 | //! | |
1269 | //! <b>Throws</b>: Nothing. | |
1270 | //! | |
1271 | //! <b>Complexity</b>: Constant. | |
1272 | //! | |
1273 | //! <b>Note</b>: Non-standard extension | |
1274 | const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW | |
1275 | { | |
1276 | BOOST_ASSERT(this->size() >= n); | |
1277 | return const_iterator(this->cbegin()+n); | |
1278 | } | |
1279 | ||
1280 | //! <b>Requires</b>: begin() <= p <= end(). | |
1281 | //! | |
1282 | //! <b>Effects</b>: Returns the index of the element pointed by p | |
1283 | //! and size() if p == end(). | |
1284 | //! | |
1285 | //! <b>Throws</b>: Nothing. | |
1286 | //! | |
1287 | //! <b>Complexity</b>: Constant. | |
1288 | //! | |
1289 | //! <b>Note</b>: Non-standard extension | |
1290 | size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW | |
1291 | { | |
1292 | //Range checked priv_index_of | |
1293 | return this->priv_index_of(p); | |
1294 | } | |
1295 | ||
1296 | //! <b>Requires</b>: begin() <= p <= end(). | |
1297 | //! | |
1298 | //! <b>Effects</b>: Returns the index of the element pointed by p | |
1299 | //! and size() if p == end(). | |
1300 | //! | |
1301 | //! <b>Throws</b>: Nothing. | |
1302 | //! | |
1303 | //! <b>Complexity</b>: Constant. | |
1304 | //! | |
1305 | //! <b>Note</b>: Non-standard extension | |
1306 | size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW | |
1307 | { | |
1308 | //Range checked priv_index_of | |
1309 | return this->priv_index_of(p); | |
1310 | } | |
1311 | ||
1312 | //! <b>Requires</b>: size() > n. | |
1313 | //! | |
1314 | //! <b>Effects</b>: Returns a reference to the nth element | |
1315 | //! from the beginning of the container. | |
1316 | //! | |
1317 | //! <b>Throws</b>: std::range_error if n >= size() | |
1318 | //! | |
1319 | //! <b>Complexity</b>: Constant. | |
1320 | reference at(size_type n) | |
1321 | { | |
1322 | this->priv_throw_if_out_of_range(n); | |
1323 | return (*this)[n]; | |
1324 | } | |
1325 | ||
1326 | //! <b>Requires</b>: size() > n. | |
1327 | //! | |
1328 | //! <b>Effects</b>: Returns a const reference to the nth element | |
1329 | //! from the beginning of the container. | |
1330 | //! | |
1331 | //! <b>Throws</b>: std::range_error if n >= size() | |
1332 | //! | |
1333 | //! <b>Complexity</b>: Constant. | |
1334 | const_reference at(size_type n) const | |
1335 | { | |
1336 | this->priv_throw_if_out_of_range(n); | |
1337 | return (*this)[n]; | |
1338 | } | |
1339 | ||
1340 | ////////////////////////////////////////////// | |
1341 | // | |
1342 | // modifiers | |
1343 | // | |
1344 | ////////////////////////////////////////////// | |
1345 | ||
1346 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1347 | ||
1348 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1349 | //! std::forward<Args>(args)... in the beginning of the deque. | |
1350 | //! | |
1351 | //! <b>Returns</b>: A reference to the created object. | |
1352 | //! | |
1353 | //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. | |
1354 | //! | |
1355 | //! <b>Complexity</b>: Amortized constant time | |
1356 | template <class... Args> | |
1357 | reference emplace_front(BOOST_FWD_REF(Args)... args) | |
1358 | { | |
1359 | if(this->priv_push_front_simple_available()){ | |
1360 | reference r = *this->priv_push_front_simple_pos(); | |
1361 | allocator_traits_type::construct | |
1362 | ( this->alloc() | |
1363 | , this->priv_push_front_simple_pos() | |
1364 | , boost::forward<Args>(args)...); | |
1365 | this->priv_push_front_simple_commit(); | |
1366 | return r; | |
1367 | } | |
1368 | else{ | |
1369 | typedef container_detail::insert_nonmovable_emplace_proxy<Allocator, iterator, Args...> type; | |
1370 | return *this->priv_insert_front_aux_impl(1, type(boost::forward<Args>(args)...)); | |
1371 | } | |
1372 | } | |
1373 | ||
1374 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1375 | //! std::forward<Args>(args)... in the end of the deque. | |
1376 | //! | |
1377 | //! <b>Returns</b>: A reference to the created object. | |
1378 | //! | |
1379 | //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. | |
1380 | //! | |
1381 | //! <b>Complexity</b>: Amortized constant time | |
1382 | template <class... Args> | |
1383 | reference emplace_back(BOOST_FWD_REF(Args)... args) | |
1384 | { | |
1385 | if(this->priv_push_back_simple_available()){ | |
1386 | reference r = *this->priv_push_back_simple_pos(); | |
1387 | allocator_traits_type::construct | |
1388 | ( this->alloc() | |
1389 | , this->priv_push_back_simple_pos() | |
1390 | , boost::forward<Args>(args)...); | |
1391 | this->priv_push_back_simple_commit(); | |
1392 | return r; | |
1393 | } | |
1394 | else{ | |
1395 | typedef container_detail::insert_nonmovable_emplace_proxy<Allocator, iterator, Args...> type; | |
1396 | return *this->priv_insert_back_aux_impl(1, type(boost::forward<Args>(args)...)); | |
1397 | } | |
1398 | } | |
1399 | ||
1400 | //! <b>Requires</b>: p must be a valid iterator of *this. | |
1401 | //! | |
1402 | //! <b>Effects</b>: Inserts an object of type T constructed with | |
1403 | //! std::forward<Args>(args)... before p | |
1404 | //! | |
1405 | //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. | |
1406 | //! | |
1407 | //! <b>Complexity</b>: If p is end(), amortized constant time | |
1408 | //! Linear time otherwise. | |
1409 | template <class... Args> | |
1410 | iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args) | |
1411 | { | |
1412 | BOOST_ASSERT(this->priv_in_range_or_end(p)); | |
1413 | if(p == this->cbegin()){ | |
1414 | this->emplace_front(boost::forward<Args>(args)...); | |
1415 | return this->begin(); | |
1416 | } | |
1417 | else if(p == this->cend()){ | |
1418 | this->emplace_back(boost::forward<Args>(args)...); | |
1419 | return (this->end()-1); | |
1420 | } | |
1421 | else{ | |
1422 | typedef container_detail::insert_emplace_proxy<Allocator, iterator, Args...> type; | |
1423 | return this->priv_insert_aux_impl(p, 1, type(boost::forward<Args>(args)...)); | |
1424 | } | |
1425 | } | |
1426 | ||
1427 | #else //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1428 | ||
1429 | #define BOOST_CONTAINER_DEQUE_EMPLACE_CODE(N) \ | |
1430 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ | |
1431 | reference emplace_front(BOOST_MOVE_UREF##N)\ | |
1432 | {\ | |
1433 | if(priv_push_front_simple_available()){\ | |
1434 | reference r = *this->priv_push_front_simple_pos();\ | |
1435 | allocator_traits_type::construct\ | |
1436 | ( this->alloc(), this->priv_push_front_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ | |
1437 | priv_push_front_simple_commit();\ | |
1438 | return r;\ | |
1439 | }\ | |
1440 | else{\ | |
1441 | typedef container_detail::insert_nonmovable_emplace_proxy##N\ | |
1442 | <Allocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ | |
1443 | return *priv_insert_front_aux_impl(1, type(BOOST_MOVE_FWD##N));\ | |
1444 | }\ | |
1445 | }\ | |
1446 | \ | |
1447 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ | |
1448 | reference emplace_back(BOOST_MOVE_UREF##N)\ | |
1449 | {\ | |
1450 | if(priv_push_back_simple_available()){\ | |
1451 | reference r = *this->priv_push_back_simple_pos();\ | |
1452 | allocator_traits_type::construct\ | |
1453 | ( this->alloc(), this->priv_push_back_simple_pos() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ | |
1454 | priv_push_back_simple_commit();\ | |
1455 | return r;\ | |
1456 | }\ | |
1457 | else{\ | |
1458 | typedef container_detail::insert_nonmovable_emplace_proxy##N\ | |
1459 | <Allocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ | |
1460 | return *priv_insert_back_aux_impl(1, type(BOOST_MOVE_FWD##N));\ | |
1461 | }\ | |
1462 | }\ | |
1463 | \ | |
1464 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ | |
1465 | iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ | |
1466 | {\ | |
1467 | BOOST_ASSERT(this->priv_in_range_or_end(p));\ | |
1468 | if(p == this->cbegin()){\ | |
1469 | this->emplace_front(BOOST_MOVE_FWD##N);\ | |
1470 | return this->begin();\ | |
1471 | }\ | |
1472 | else if(p == cend()){\ | |
1473 | this->emplace_back(BOOST_MOVE_FWD##N);\ | |
1474 | return (--this->end());\ | |
1475 | }\ | |
1476 | else{\ | |
1477 | typedef container_detail::insert_emplace_proxy_arg##N\ | |
1478 | <Allocator, iterator BOOST_MOVE_I##N BOOST_MOVE_TARG##N> type;\ | |
1479 | return this->priv_insert_aux_impl(p, 1, type(BOOST_MOVE_FWD##N));\ | |
1480 | }\ | |
1481 | } | |
1482 | // | |
1483 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEQUE_EMPLACE_CODE) | |
1484 | #undef BOOST_CONTAINER_DEQUE_EMPLACE_CODE | |
1485 | ||
1486 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
1487 | ||
1488 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1489 | //! <b>Effects</b>: Inserts a copy of x at the front of the deque. | |
1490 | //! | |
1491 | //! <b>Throws</b>: If memory allocation throws or | |
1492 | //! T's copy constructor throws. | |
1493 | //! | |
1494 | //! <b>Complexity</b>: Amortized constant time. | |
1495 | void push_front(const T &x); | |
1496 | ||
1497 | //! <b>Effects</b>: Constructs a new element in the front of the deque | |
1498 | //! and moves the resources of x to this new element. | |
1499 | //! | |
1500 | //! <b>Throws</b>: If memory allocation throws. | |
1501 | //! | |
1502 | //! <b>Complexity</b>: Amortized constant time. | |
1503 | void push_front(T &&x); | |
1504 | #else | |
1505 | BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front) | |
1506 | #endif | |
1507 | ||
1508 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1509 | //! <b>Effects</b>: Inserts a copy of x at the end of the deque. | |
1510 | //! | |
1511 | //! <b>Throws</b>: If memory allocation throws or | |
1512 | //! T's copy constructor throws. | |
1513 | //! | |
1514 | //! <b>Complexity</b>: Amortized constant time. | |
1515 | void push_back(const T &x); | |
1516 | ||
1517 | //! <b>Effects</b>: Constructs a new element in the end of the deque | |
1518 | //! and moves the resources of x to this new element. | |
1519 | //! | |
1520 | //! <b>Throws</b>: If memory allocation throws. | |
1521 | //! | |
1522 | //! <b>Complexity</b>: Amortized constant time. | |
1523 | void push_back(T &&x); | |
1524 | #else | |
1525 | BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) | |
1526 | #endif | |
1527 | ||
1528 | #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1529 | ||
1530 | //! <b>Requires</b>: p must be a valid iterator of *this. | |
1531 | //! | |
1532 | //! <b>Effects</b>: Insert a copy of x before p. | |
1533 | //! | |
1534 | //! <b>Returns</b>: an iterator to the inserted element. | |
1535 | //! | |
1536 | //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. | |
1537 | //! | |
1538 | //! <b>Complexity</b>: If p is end(), amortized constant time | |
1539 | //! Linear time otherwise. | |
1540 | iterator insert(const_iterator p, const T &x); | |
1541 | ||
1542 | //! <b>Requires</b>: p must be a valid iterator of *this. | |
1543 | //! | |
1544 | //! <b>Effects</b>: Insert a new element before p with x's resources. | |
1545 | //! | |
1546 | //! <b>Returns</b>: an iterator to the inserted element. | |
1547 | //! | |
1548 | //! <b>Throws</b>: If memory allocation throws. | |
1549 | //! | |
1550 | //! <b>Complexity</b>: If p is end(), amortized constant time | |
1551 | //! Linear time otherwise. | |
1552 | iterator insert(const_iterator p, T &&x); | |
1553 | #else | |
1554 | BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) | |
1555 | #endif | |
1556 | ||
1557 | //! <b>Requires</b>: pos must be a valid iterator of *this. | |
1558 | //! | |
1559 | //! <b>Effects</b>: Insert n copies of x before pos. | |
1560 | //! | |
1561 | //! <b>Returns</b>: an iterator to the first inserted element or pos if n is 0. | |
1562 | //! | |
1563 | //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. | |
1564 | //! | |
1565 | //! <b>Complexity</b>: Linear to n. | |
1566 | iterator insert(const_iterator pos, size_type n, const value_type& x) | |
1567 | { | |
1568 | //Range check of p is done by insert() | |
1569 | typedef constant_iterator<value_type, difference_type> c_it; | |
1570 | return this->insert(pos, c_it(x, n), c_it()); | |
1571 | } | |
1572 | ||
1573 | //! <b>Requires</b>: pos must be a valid iterator of *this. | |
1574 | //! | |
1575 | //! <b>Effects</b>: Insert a copy of the [first, last) range before pos. | |
1576 | //! | |
1577 | //! <b>Returns</b>: an iterator to the first inserted element or pos if first == last. | |
1578 | //! | |
1579 | //! <b>Throws</b>: If memory allocation throws, T's constructor from a | |
1580 | //! dereferenced InIt throws or T's copy constructor throws. | |
1581 | //! | |
1582 | //! <b>Complexity</b>: Linear to distance [first, last). | |
1583 | template <class InIt> | |
1584 | iterator insert(const_iterator pos, InIt first, InIt last | |
1585 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1586 | , typename container_detail::disable_if_or | |
1587 | < void | |
1588 | , container_detail::is_convertible<InIt, size_type> | |
1589 | , container_detail::is_not_input_iterator<InIt> | |
1590 | >::type * = 0 | |
1591 | #endif | |
1592 | ) | |
1593 | { | |
1594 | BOOST_ASSERT(this->priv_in_range_or_end(pos)); | |
1595 | size_type n = 0; | |
1596 | iterator it(pos.unconst()); | |
1597 | for(;first != last; ++first, ++n){ | |
1598 | it = this->emplace(it, *first); | |
1599 | ++it; | |
1600 | } | |
1601 | it -= n; | |
1602 | return it; | |
1603 | } | |
1604 | ||
1605 | #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) | |
1606 | //! <b>Requires</b>: pos must be a valid iterator of *this. | |
1607 | //! | |
1608 | //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before pos. | |
1609 | //! | |
1610 | //! <b>Returns</b>: an iterator to the first inserted element or pos if il.begin() == il.end(). | |
1611 | //! | |
1612 | //! <b>Throws</b>: If memory allocation throws, T's constructor from a | |
1613 | //! dereferenced std::initializer_list throws or T's copy constructor throws. | |
1614 | //! | |
1615 | //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()). | |
1616 | iterator insert(const_iterator pos, std::initializer_list<value_type> il) | |
1617 | { | |
1618 | //Range check os pos is done in insert() | |
1619 | return insert(pos, il.begin(), il.end()); | |
1620 | } | |
1621 | #endif | |
1622 | ||
1623 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1624 | template <class FwdIt> | |
1625 | iterator insert(const_iterator p, FwdIt first, FwdIt last | |
1626 | #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) | |
1627 | , typename container_detail::disable_if_or | |
1628 | < void | |
1629 | , container_detail::is_convertible<FwdIt, size_type> | |
1630 | , container_detail::is_input_iterator<FwdIt> | |
1631 | >::type * = 0 | |
1632 | #endif | |
1633 | ) | |
1634 | { | |
1635 | BOOST_ASSERT(this->priv_in_range_or_end(p)); | |
1636 | container_detail::insert_range_proxy<Allocator, FwdIt, iterator> proxy(first); | |
1637 | return priv_insert_aux_impl(p, boost::container::iterator_distance(first, last), proxy); | |
1638 | } | |
1639 | #endif | |
1640 | ||
1641 | //! <b>Effects</b>: Removes the first element from the deque. | |
1642 | //! | |
1643 | //! <b>Throws</b>: Nothing. | |
1644 | //! | |
1645 | //! <b>Complexity</b>: Constant time. | |
1646 | void pop_front() BOOST_NOEXCEPT_OR_NOTHROW | |
1647 | { | |
1648 | BOOST_ASSERT(!this->empty()); | |
1649 | if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) { | |
1650 | allocator_traits_type::destroy | |
1651 | ( this->alloc() | |
1652 | , container_detail::to_raw_pointer(this->members_.m_start.m_cur) | |
1653 | ); | |
1654 | ++this->members_.m_start.m_cur; | |
1655 | } | |
1656 | else | |
1657 | this->priv_pop_front_aux(); | |
1658 | } | |
1659 | ||
1660 | //! <b>Effects</b>: Removes the last element from the deque. | |
1661 | //! | |
1662 | //! <b>Throws</b>: Nothing. | |
1663 | //! | |
1664 | //! <b>Complexity</b>: Constant time. | |
1665 | void pop_back() BOOST_NOEXCEPT_OR_NOTHROW | |
1666 | { | |
1667 | BOOST_ASSERT(!this->empty()); | |
1668 | if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) { | |
1669 | --this->members_.m_finish.m_cur; | |
1670 | allocator_traits_type::destroy | |
1671 | ( this->alloc() | |
1672 | , container_detail::to_raw_pointer(this->members_.m_finish.m_cur) | |
1673 | ); | |
1674 | } | |
1675 | else | |
1676 | this->priv_pop_back_aux(); | |
1677 | } | |
1678 | ||
1679 | //! <b>Effects</b>: Erases the element at p. | |
1680 | //! | |
1681 | //! <b>Throws</b>: Nothing. | |
1682 | //! | |
1683 | //! <b>Complexity</b>: Linear to the elements between pos and the | |
1684 | //! last element (if pos is near the end) or the first element | |
1685 | //! if(pos is near the beginning). | |
1686 | //! Constant if pos is the first or the last element. | |
1687 | iterator erase(const_iterator pos) BOOST_NOEXCEPT_OR_NOTHROW | |
1688 | { | |
1689 | BOOST_ASSERT(this->priv_in_range(pos)); | |
1690 | iterator next = pos.unconst(); | |
1691 | ++next; | |
1692 | size_type index = pos - this->members_.m_start; | |
1693 | if (index < (this->size()/2)) { | |
1694 | boost::container::move_backward(this->begin(), pos.unconst(), next); | |
1695 | pop_front(); | |
1696 | } | |
1697 | else { | |
1698 | boost::container::move(next, this->end(), pos.unconst()); | |
1699 | pop_back(); | |
1700 | } | |
1701 | return this->members_.m_start + index; | |
1702 | } | |
1703 | ||
1704 | //! <b>Effects</b>: Erases the elements pointed by [first, last). | |
1705 | //! | |
1706 | //! <b>Throws</b>: Nothing. | |
1707 | //! | |
1708 | //! <b>Complexity</b>: Linear to the distance between first and | |
1709 | //! last plus the elements between pos and the | |
1710 | //! last element (if pos is near the end) or the first element | |
1711 | //! if(pos is near the beginning). | |
1712 | iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW | |
1713 | { | |
1714 | BOOST_ASSERT(first == last || | |
1715 | (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last))); | |
1716 | if (first == this->members_.m_start && last == this->members_.m_finish) { | |
1717 | this->clear(); | |
1718 | return this->members_.m_finish; | |
1719 | } | |
1720 | else { | |
1721 | const size_type n = static_cast<size_type>(last - first); | |
1722 | const size_type elems_before = static_cast<size_type>(first - this->members_.m_start); | |
1723 | if (elems_before < (this->size() - n) - elems_before) { | |
1724 | boost::container::move_backward(begin(), first.unconst(), last.unconst()); | |
1725 | iterator new_start = this->members_.m_start + n; | |
1726 | this->priv_destroy_range(this->members_.m_start, new_start); | |
1727 | this->priv_destroy_nodes(this->members_.m_start.m_node, new_start.m_node); | |
1728 | this->members_.m_start = new_start; | |
1729 | } | |
1730 | else { | |
1731 | boost::container::move(last.unconst(), end(), first.unconst()); | |
1732 | iterator new_finish = this->members_.m_finish - n; | |
1733 | this->priv_destroy_range(new_finish, this->members_.m_finish); | |
1734 | this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1); | |
1735 | this->members_.m_finish = new_finish; | |
1736 | } | |
1737 | return this->members_.m_start + elems_before; | |
1738 | } | |
1739 | } | |
1740 | ||
1741 | //! <b>Effects</b>: Swaps the contents of *this and x. | |
1742 | //! | |
1743 | //! <b>Throws</b>: Nothing. | |
1744 | //! | |
1745 | //! <b>Complexity</b>: Constant. | |
1746 | void swap(deque &x) | |
1747 | BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value | |
1748 | || allocator_traits_type::is_always_equal::value) | |
1749 | { | |
1750 | this->swap_members(x); | |
1751 | container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; | |
1752 | container_detail::swap_alloc(this->alloc(), x.alloc(), flag); | |
1753 | container_detail::swap_alloc(this->ptr_alloc(), x.ptr_alloc(), flag); | |
1754 | } | |
1755 | ||
1756 | //! <b>Effects</b>: Erases all the elements of the deque. | |
1757 | //! | |
1758 | //! <b>Throws</b>: Nothing. | |
1759 | //! | |
1760 | //! <b>Complexity</b>: Linear to the number of elements in the deque. | |
1761 | void clear() BOOST_NOEXCEPT_OR_NOTHROW | |
1762 | { | |
1763 | for (index_pointer node = this->members_.m_start.m_node + 1; | |
1764 | node < this->members_.m_finish.m_node; | |
1765 | ++node) { | |
1766 | this->priv_destroy_range(*node, *node + this->s_buffer_size()); | |
1767 | this->priv_deallocate_node(*node); | |
1768 | } | |
1769 | ||
1770 | if (this->members_.m_start.m_node != this->members_.m_finish.m_node) { | |
1771 | this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_start.m_last); | |
1772 | this->priv_destroy_range(this->members_.m_finish.m_first, this->members_.m_finish.m_cur); | |
1773 | this->priv_deallocate_node(this->members_.m_finish.m_first); | |
1774 | } | |
1775 | else | |
1776 | this->priv_destroy_range(this->members_.m_start.m_cur, this->members_.m_finish.m_cur); | |
1777 | ||
1778 | this->members_.m_finish = this->members_.m_start; | |
1779 | } | |
1780 | ||
1781 | //! <b>Effects</b>: Returns true if x and y are equal | |
1782 | //! | |
1783 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1784 | friend bool operator==(const deque& x, const deque& y) | |
1785 | { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); } | |
1786 | ||
1787 | //! <b>Effects</b>: Returns true if x and y are unequal | |
1788 | //! | |
1789 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1790 | friend bool operator!=(const deque& x, const deque& y) | |
1791 | { return !(x == y); } | |
1792 | ||
1793 | //! <b>Effects</b>: Returns true if x is less than y | |
1794 | //! | |
1795 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1796 | friend bool operator<(const deque& x, const deque& y) | |
1797 | { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
1798 | ||
1799 | //! <b>Effects</b>: Returns true if x is greater than y | |
1800 | //! | |
1801 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1802 | friend bool operator>(const deque& x, const deque& y) | |
1803 | { return y < x; } | |
1804 | ||
1805 | //! <b>Effects</b>: Returns true if x is equal or less than y | |
1806 | //! | |
1807 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1808 | friend bool operator<=(const deque& x, const deque& y) | |
1809 | { return !(y < x); } | |
1810 | ||
1811 | //! <b>Effects</b>: Returns true if x is equal or greater than y | |
1812 | //! | |
1813 | //! <b>Complexity</b>: Linear to the number of elements in the container. | |
1814 | friend bool operator>=(const deque& x, const deque& y) | |
1815 | { return !(x < y); } | |
1816 | ||
1817 | //! <b>Effects</b>: x.swap(y) | |
1818 | //! | |
1819 | //! <b>Complexity</b>: Constant. | |
1820 | friend void swap(deque& x, deque& y) | |
1821 | { x.swap(y); } | |
1822 | ||
1823 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
1824 | private: | |
1825 | ||
1826 | size_type priv_index_of(const_iterator p) const | |
1827 | { | |
1828 | BOOST_ASSERT(this->cbegin() <= p); | |
1829 | BOOST_ASSERT(p <= this->cend()); | |
1830 | return static_cast<size_type>(p - this->cbegin()); | |
1831 | } | |
1832 | ||
1833 | void priv_erase_last_n(size_type n) | |
1834 | { | |
1835 | if(n == this->size()) { | |
1836 | this->clear(); | |
1837 | } | |
1838 | else { | |
1839 | iterator new_finish = this->members_.m_finish - n; | |
1840 | this->priv_destroy_range(new_finish, this->members_.m_finish); | |
1841 | this->priv_destroy_nodes(new_finish.m_node + 1, this->members_.m_finish.m_node + 1); | |
1842 | this->members_.m_finish = new_finish; | |
1843 | } | |
1844 | } | |
1845 | ||
1846 | void priv_throw_if_out_of_range(size_type n) const | |
1847 | { | |
1848 | if (n >= this->size()) | |
1849 | throw_out_of_range("deque::at out of range"); | |
1850 | } | |
1851 | ||
1852 | bool priv_in_range(const_iterator pos) const | |
1853 | { | |
1854 | return (this->begin() <= pos) && (pos < this->end()); | |
1855 | } | |
1856 | ||
1857 | bool priv_in_range_or_end(const_iterator pos) const | |
1858 | { | |
1859 | return (this->begin() <= pos) && (pos <= this->end()); | |
1860 | } | |
1861 | ||
1862 | template <class U> | |
1863 | iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x) | |
1864 | { | |
1865 | BOOST_ASSERT(this->priv_in_range_or_end(p)); | |
1866 | if (p == cbegin()){ | |
1867 | this->push_front(::boost::forward<U>(x)); | |
1868 | return begin(); | |
1869 | } | |
1870 | else if (p == cend()){ | |
1871 | this->push_back(::boost::forward<U>(x)); | |
1872 | return --end(); | |
1873 | } | |
1874 | else { | |
1875 | return priv_insert_aux_impl | |
1876 | ( p, (size_type)1 | |
1877 | , container_detail::get_insert_value_proxy<iterator, Allocator>(::boost::forward<U>(x))); | |
1878 | } | |
1879 | } | |
1880 | ||
1881 | template <class U> | |
1882 | void priv_push_front(BOOST_FWD_REF(U) x) | |
1883 | { | |
1884 | if(this->priv_push_front_simple_available()){ | |
1885 | allocator_traits_type::construct | |
1886 | ( this->alloc(), this->priv_push_front_simple_pos(), ::boost::forward<U>(x)); | |
1887 | this->priv_push_front_simple_commit(); | |
1888 | } | |
1889 | else{ | |
1890 | priv_insert_aux_impl | |
1891 | ( this->cbegin(), (size_type)1 | |
1892 | , container_detail::get_insert_value_proxy<iterator, Allocator>(::boost::forward<U>(x))); | |
1893 | } | |
1894 | } | |
1895 | ||
1896 | template <class U> | |
1897 | void priv_push_back(BOOST_FWD_REF(U) x) | |
1898 | { | |
1899 | if(this->priv_push_back_simple_available()){ | |
1900 | allocator_traits_type::construct | |
1901 | ( this->alloc(), this->priv_push_back_simple_pos(), ::boost::forward<U>(x)); | |
1902 | this->priv_push_back_simple_commit(); | |
1903 | } | |
1904 | else{ | |
1905 | priv_insert_aux_impl | |
1906 | ( this->cend(), (size_type)1 | |
1907 | , container_detail::get_insert_value_proxy<iterator, Allocator>(::boost::forward<U>(x))); | |
1908 | } | |
1909 | } | |
1910 | ||
1911 | bool priv_push_back_simple_available() const | |
1912 | { | |
1913 | return this->members_.m_map && | |
1914 | (this->members_.m_finish.m_cur != (this->members_.m_finish.m_last - 1)); | |
1915 | } | |
1916 | ||
1917 | T *priv_push_back_simple_pos() const | |
1918 | { | |
1919 | return container_detail::to_raw_pointer(this->members_.m_finish.m_cur); | |
1920 | } | |
1921 | ||
1922 | void priv_push_back_simple_commit() | |
1923 | { | |
1924 | ++this->members_.m_finish.m_cur; | |
1925 | } | |
1926 | ||
1927 | bool priv_push_front_simple_available() const | |
1928 | { | |
1929 | return this->members_.m_map && | |
1930 | (this->members_.m_start.m_cur != this->members_.m_start.m_first); | |
1931 | } | |
1932 | ||
1933 | T *priv_push_front_simple_pos() const | |
1934 | { return container_detail::to_raw_pointer(this->members_.m_start.m_cur) - 1; } | |
1935 | ||
1936 | void priv_push_front_simple_commit() | |
1937 | { --this->members_.m_start.m_cur; } | |
1938 | ||
1939 | void priv_destroy_range(iterator p, iterator p2) | |
1940 | { | |
1941 | if(!Base::traits_t::trivial_dctr){ | |
1942 | for(;p != p2; ++p){ | |
1943 | allocator_traits_type::destroy(this->alloc(), container_detail::iterator_to_raw_pointer(p)); | |
1944 | } | |
1945 | } | |
1946 | } | |
1947 | ||
1948 | void priv_destroy_range(pointer p, pointer p2) | |
1949 | { | |
1950 | if(!Base::traits_t::trivial_dctr){ | |
1951 | for(;p != p2; ++p){ | |
1952 | allocator_traits_type::destroy(this->alloc(), container_detail::iterator_to_raw_pointer(p)); | |
1953 | } | |
1954 | } | |
1955 | } | |
1956 | ||
1957 | template<class InsertProxy> | |
1958 | iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy proxy) | |
1959 | { | |
1960 | iterator pos(p.unconst()); | |
1961 | const size_type pos_n = p - this->cbegin(); | |
1962 | if(!this->members_.m_map){ | |
1963 | this->priv_initialize_map(0); | |
1964 | pos = this->begin(); | |
1965 | } | |
1966 | ||
1967 | const size_type elemsbefore = static_cast<size_type>(pos - this->members_.m_start); | |
1968 | const size_type length = this->size(); | |
1969 | if (elemsbefore < length / 2) { | |
1970 | const iterator new_start = this->priv_reserve_elements_at_front(n); | |
1971 | const iterator old_start = this->members_.m_start; | |
1972 | if(!elemsbefore){ | |
1973 | proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n); | |
1974 | this->members_.m_start = new_start; | |
1975 | } | |
1976 | else{ | |
1977 | pos = this->members_.m_start + elemsbefore; | |
1978 | if (elemsbefore >= n) { | |
1979 | const iterator start_n = this->members_.m_start + n; | |
1980 | ::boost::container::uninitialized_move_alloc | |
1981 | (this->alloc(), this->members_.m_start, start_n, new_start); | |
1982 | this->members_.m_start = new_start; | |
1983 | boost::container::move(start_n, pos, old_start); | |
1984 | proxy.copy_n_and_update(this->alloc(), pos - n, n); | |
1985 | } | |
1986 | else { | |
1987 | const size_type mid_count = n - elemsbefore; | |
1988 | const iterator mid_start = old_start - mid_count; | |
1989 | proxy.uninitialized_copy_n_and_update(this->alloc(), mid_start, mid_count); | |
1990 | this->members_.m_start = mid_start; | |
1991 | ::boost::container::uninitialized_move_alloc | |
1992 | (this->alloc(), old_start, pos, new_start); | |
1993 | this->members_.m_start = new_start; | |
1994 | proxy.copy_n_and_update(this->alloc(), old_start, elemsbefore); | |
1995 | } | |
1996 | } | |
1997 | } | |
1998 | else { | |
1999 | const iterator new_finish = this->priv_reserve_elements_at_back(n); | |
2000 | const iterator old_finish = this->members_.m_finish; | |
2001 | const size_type elemsafter = length - elemsbefore; | |
2002 | if(!elemsafter){ | |
2003 | proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n); | |
2004 | this->members_.m_finish = new_finish; | |
2005 | } | |
2006 | else{ | |
2007 | pos = old_finish - elemsafter; | |
2008 | if (elemsafter >= n) { | |
2009 | iterator finish_n = old_finish - difference_type(n); | |
2010 | ::boost::container::uninitialized_move_alloc | |
2011 | (this->alloc(), finish_n, old_finish, old_finish); | |
2012 | this->members_.m_finish = new_finish; | |
2013 | boost::container::move_backward(pos, finish_n, old_finish); | |
2014 | proxy.copy_n_and_update(this->alloc(), pos, n); | |
2015 | } | |
2016 | else { | |
2017 | const size_type raw_gap = n - elemsafter; | |
2018 | ::boost::container::uninitialized_move_alloc | |
2019 | (this->alloc(), pos, old_finish, old_finish + raw_gap); | |
2020 | BOOST_TRY{ | |
2021 | proxy.copy_n_and_update(this->alloc(), pos, elemsafter); | |
2022 | proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, raw_gap); | |
2023 | } | |
2024 | BOOST_CATCH(...){ | |
2025 | this->priv_destroy_range(old_finish, old_finish + elemsafter); | |
2026 | BOOST_RETHROW | |
2027 | } | |
2028 | BOOST_CATCH_END | |
2029 | this->members_.m_finish = new_finish; | |
2030 | } | |
2031 | } | |
2032 | } | |
2033 | return this->begin() + pos_n; | |
2034 | } | |
2035 | ||
2036 | template <class InsertProxy> | |
2037 | iterator priv_insert_back_aux_impl(size_type n, InsertProxy proxy) | |
2038 | { | |
2039 | if(!this->members_.m_map){ | |
2040 | this->priv_initialize_map(0); | |
2041 | } | |
2042 | ||
2043 | iterator new_finish = this->priv_reserve_elements_at_back(n); | |
2044 | iterator old_finish = this->members_.m_finish; | |
2045 | proxy.uninitialized_copy_n_and_update(this->alloc(), old_finish, n); | |
2046 | this->members_.m_finish = new_finish; | |
2047 | return iterator(this->members_.m_finish - n); | |
2048 | } | |
2049 | ||
2050 | template <class InsertProxy> | |
2051 | iterator priv_insert_front_aux_impl(size_type n, InsertProxy proxy) | |
2052 | { | |
2053 | if(!this->members_.m_map){ | |
2054 | this->priv_initialize_map(0); | |
2055 | } | |
2056 | ||
2057 | iterator new_start = this->priv_reserve_elements_at_front(n); | |
2058 | proxy.uninitialized_copy_n_and_update(this->alloc(), new_start, n); | |
2059 | this->members_.m_start = new_start; | |
2060 | return new_start; | |
2061 | } | |
2062 | ||
2063 | iterator priv_fill_insert(const_iterator pos, size_type n, const value_type& x) | |
2064 | { | |
2065 | typedef constant_iterator<value_type, difference_type> c_it; | |
2066 | return this->insert(pos, c_it(x, n), c_it()); | |
2067 | } | |
2068 | ||
2069 | // Precondition: this->members_.m_start and this->members_.m_finish have already been initialized, | |
2070 | // but none of the deque's elements have yet been constructed. | |
2071 | void priv_fill_initialize(const value_type& value) | |
2072 | { | |
2073 | index_pointer cur = this->members_.m_start.m_node; | |
2074 | BOOST_TRY { | |
2075 | for ( ; cur < this->members_.m_finish.m_node; ++cur){ | |
2076 | boost::container::uninitialized_fill_alloc | |
2077 | (this->alloc(), *cur, *cur + this->s_buffer_size(), value); | |
2078 | } | |
2079 | boost::container::uninitialized_fill_alloc | |
2080 | (this->alloc(), this->members_.m_finish.m_first, this->members_.m_finish.m_cur, value); | |
2081 | } | |
2082 | BOOST_CATCH(...){ | |
2083 | this->priv_destroy_range(this->members_.m_start, iterator(*cur, cur)); | |
2084 | BOOST_RETHROW | |
2085 | } | |
2086 | BOOST_CATCH_END | |
2087 | } | |
2088 | ||
2089 | template <class InIt> | |
2090 | void priv_range_initialize(InIt first, InIt last, typename iterator_enable_if_tag<InIt, std::input_iterator_tag>::type* =0) | |
2091 | { | |
2092 | this->priv_initialize_map(0); | |
2093 | BOOST_TRY { | |
2094 | for ( ; first != last; ++first) | |
2095 | this->emplace_back(*first); | |
2096 | } | |
2097 | BOOST_CATCH(...){ | |
2098 | this->clear(); | |
2099 | BOOST_RETHROW | |
2100 | } | |
2101 | BOOST_CATCH_END | |
2102 | } | |
2103 | ||
2104 | template <class FwdIt> | |
2105 | void priv_range_initialize(FwdIt first, FwdIt last, typename iterator_disable_if_tag<FwdIt, std::input_iterator_tag>::type* =0) | |
2106 | { | |
2107 | size_type n = 0; | |
2108 | n = boost::container::iterator_distance(first, last); | |
2109 | this->priv_initialize_map(n); | |
2110 | ||
2111 | index_pointer cur_node = this->members_.m_start.m_node; | |
2112 | BOOST_TRY { | |
2113 | for (; cur_node < this->members_.m_finish.m_node; ++cur_node) { | |
2114 | FwdIt mid = first; | |
2115 | boost::container::iterator_advance(mid, this->s_buffer_size()); | |
2116 | ::boost::container::uninitialized_copy_alloc(this->alloc(), first, mid, *cur_node); | |
2117 | first = mid; | |
2118 | } | |
2119 | ::boost::container::uninitialized_copy_alloc(this->alloc(), first, last, this->members_.m_finish.m_first); | |
2120 | } | |
2121 | BOOST_CATCH(...){ | |
2122 | this->priv_destroy_range(this->members_.m_start, iterator(*cur_node, cur_node)); | |
2123 | BOOST_RETHROW | |
2124 | } | |
2125 | BOOST_CATCH_END | |
2126 | } | |
2127 | ||
2128 | // Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first. | |
2129 | void priv_pop_back_aux() BOOST_NOEXCEPT_OR_NOTHROW | |
2130 | { | |
2131 | this->priv_deallocate_node(this->members_.m_finish.m_first); | |
2132 | this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1); | |
2133 | this->members_.m_finish.m_cur = this->members_.m_finish.m_last - 1; | |
2134 | allocator_traits_type::destroy | |
2135 | ( this->alloc() | |
2136 | , container_detail::to_raw_pointer(this->members_.m_finish.m_cur) | |
2137 | ); | |
2138 | } | |
2139 | ||
2140 | // Called only if this->members_.m_start.m_cur == this->members_.m_start.m_last - 1. Note that | |
2141 | // if the deque has at least one element (a precondition for this member | |
2142 | // function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque | |
2143 | // must have at least two nodes. | |
2144 | void priv_pop_front_aux() BOOST_NOEXCEPT_OR_NOTHROW | |
2145 | { | |
2146 | allocator_traits_type::destroy | |
2147 | ( this->alloc() | |
2148 | , container_detail::to_raw_pointer(this->members_.m_start.m_cur) | |
2149 | ); | |
2150 | this->priv_deallocate_node(this->members_.m_start.m_first); | |
2151 | this->members_.m_start.priv_set_node(this->members_.m_start.m_node + 1); | |
2152 | this->members_.m_start.m_cur = this->members_.m_start.m_first; | |
2153 | } | |
2154 | ||
2155 | iterator priv_reserve_elements_at_front(size_type n) | |
2156 | { | |
2157 | size_type vacancies = this->members_.m_start.m_cur - this->members_.m_start.m_first; | |
2158 | if (n > vacancies){ | |
2159 | size_type new_elems = n-vacancies; | |
2160 | size_type new_nodes = (new_elems + this->s_buffer_size() - 1) / | |
2161 | this->s_buffer_size(); | |
2162 | size_type s = (size_type)(this->members_.m_start.m_node - this->members_.m_map); | |
2163 | if (new_nodes > s){ | |
2164 | this->priv_reallocate_map(new_nodes, true); | |
2165 | } | |
2166 | size_type i = 1; | |
2167 | BOOST_TRY { | |
2168 | for (; i <= new_nodes; ++i) | |
2169 | *(this->members_.m_start.m_node - i) = this->priv_allocate_node(); | |
2170 | } | |
2171 | BOOST_CATCH(...) { | |
2172 | for (size_type j = 1; j < i; ++j) | |
2173 | this->priv_deallocate_node(*(this->members_.m_start.m_node - j)); | |
2174 | BOOST_RETHROW | |
2175 | } | |
2176 | BOOST_CATCH_END | |
2177 | } | |
2178 | return this->members_.m_start - difference_type(n); | |
2179 | } | |
2180 | ||
2181 | iterator priv_reserve_elements_at_back(size_type n) | |
2182 | { | |
2183 | size_type vacancies = (this->members_.m_finish.m_last - this->members_.m_finish.m_cur) - 1; | |
2184 | if (n > vacancies){ | |
2185 | size_type new_elems = n - vacancies; | |
2186 | size_type new_nodes = (new_elems + this->s_buffer_size() - 1)/s_buffer_size(); | |
2187 | size_type s = (size_type)(this->members_.m_map_size - (this->members_.m_finish.m_node - this->members_.m_map)); | |
2188 | if (new_nodes + 1 > s){ | |
2189 | this->priv_reallocate_map(new_nodes, false); | |
2190 | } | |
2191 | size_type i = 1; | |
2192 | BOOST_TRY { | |
2193 | for (; i <= new_nodes; ++i) | |
2194 | *(this->members_.m_finish.m_node + i) = this->priv_allocate_node(); | |
2195 | } | |
2196 | BOOST_CATCH(...) { | |
2197 | for (size_type j = 1; j < i; ++j) | |
2198 | this->priv_deallocate_node(*(this->members_.m_finish.m_node + j)); | |
2199 | BOOST_RETHROW | |
2200 | } | |
2201 | BOOST_CATCH_END | |
2202 | } | |
2203 | return this->members_.m_finish + difference_type(n); | |
2204 | } | |
2205 | ||
2206 | void priv_reallocate_map(size_type nodes_to_add, bool add_at_front) | |
2207 | { | |
2208 | size_type old_num_nodes = this->members_.m_finish.m_node - this->members_.m_start.m_node + 1; | |
2209 | size_type new_num_nodes = old_num_nodes + nodes_to_add; | |
2210 | ||
2211 | index_pointer new_nstart; | |
2212 | if (this->members_.m_map_size > 2 * new_num_nodes) { | |
2213 | new_nstart = this->members_.m_map + (this->members_.m_map_size - new_num_nodes) / 2 | |
2214 | + (add_at_front ? nodes_to_add : 0); | |
2215 | if (new_nstart < this->members_.m_start.m_node) | |
2216 | boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart); | |
2217 | else | |
2218 | boost::container::move_backward | |
2219 | (this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart + old_num_nodes); | |
2220 | } | |
2221 | else { | |
2222 | size_type new_map_size = | |
2223 | this->members_.m_map_size + container_detail::max_value(this->members_.m_map_size, nodes_to_add) + 2; | |
2224 | ||
2225 | index_pointer new_map = this->priv_allocate_map(new_map_size); | |
2226 | new_nstart = new_map + (new_map_size - new_num_nodes) / 2 | |
2227 | + (add_at_front ? nodes_to_add : 0); | |
2228 | boost::container::move(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1, new_nstart); | |
2229 | this->priv_deallocate_map(this->members_.m_map, this->members_.m_map_size); | |
2230 | ||
2231 | this->members_.m_map = new_map; | |
2232 | this->members_.m_map_size = new_map_size; | |
2233 | } | |
2234 | ||
2235 | this->members_.m_start.priv_set_node(new_nstart); | |
2236 | this->members_.m_finish.priv_set_node(new_nstart + old_num_nodes - 1); | |
2237 | } | |
2238 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2239 | }; | |
2240 | ||
2241 | }} | |
2242 | ||
2243 | #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2244 | ||
2245 | namespace boost { | |
2246 | ||
2247 | //!has_trivial_destructor_after_move<> == true_type | |
2248 | //!specialization for optimizations | |
2249 | template <class T, class Allocator> | |
2250 | struct has_trivial_destructor_after_move<boost::container::deque<T, Allocator> > | |
2251 | { | |
2252 | typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; | |
2253 | static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && | |
2254 | ::boost::has_trivial_destructor_after_move<pointer>::value; | |
2255 | }; | |
2256 | ||
2257 | } | |
2258 | ||
2259 | #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED | |
2260 | ||
2261 | #include <boost/container/detail/config_end.hpp> | |
2262 | ||
2263 | #endif // #ifndef BOOST_CONTAINER_DEQUE_HPP |