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