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