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