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