comparison DEPENDENCIES/generic/include/boost/container/stable_vector.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)
author Chris Cannam
date Mon, 07 Sep 2015 11:12:49 +0100
parents 2665513ce2d3
children
comparison
equal deleted inserted replaced
100:793467b5e61c 101:c530137014c0
1 ////////////////////////////////////////////////////////////////////////////// 1 //////////////////////////////////////////////////////////////////////////////
2 // 2 //
3 // (C) Copyright Ion Gaztanaga 2008-2012. Distributed under the Boost 3 // (C) Copyright Ion Gaztanaga 2008-2013. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file 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) 5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 // 6 //
7 // See http://www.boost.org/libs/container for documentation. 7 // See http://www.boost.org/libs/container for documentation.
8 // 8 //
17 ////////////////////////////////////////////////////////////////////////////// 17 //////////////////////////////////////////////////////////////////////////////
18 18
19 #ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP 19 #ifndef BOOST_CONTAINER_STABLE_VECTOR_HPP
20 #define BOOST_CONTAINER_STABLE_VECTOR_HPP 20 #define BOOST_CONTAINER_STABLE_VECTOR_HPP
21 21
22 #if defined(_MSC_VER) 22 #ifndef BOOST_CONFIG_HPP
23 # include <boost/config.hpp>
24 #endif
25
26 #if defined(BOOST_HAS_PRAGMA_ONCE)
23 # pragma once 27 # pragma once
24 #endif 28 #endif
25 29
26 #include <boost/container/detail/config_begin.hpp> 30 #include <boost/container/detail/config_begin.hpp>
27 #include <boost/container/detail/workaround.hpp> 31 #include <boost/container/detail/workaround.hpp>
32
33 // container
34 #include <boost/container/allocator_traits.hpp>
28 #include <boost/container/container_fwd.hpp> 35 #include <boost/container/container_fwd.hpp>
29 #include <boost/mpl/bool.hpp> 36 #include <boost/container/new_allocator.hpp> //new_allocator
30 #include <boost/mpl/not.hpp> 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
31 #include <boost/assert.hpp> 60 #include <boost/assert.hpp>
32 #include <boost/container/throw_exception.hpp> 61 #include <boost/core/no_exceptions_support.hpp>
33 #include <boost/container/detail/allocator_version_traits.hpp> 62 // std
34 #include <boost/container/detail/utilities.hpp> 63 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
35 #include <boost/container/detail/iterators.hpp> 64 #include <initializer_list>
36 #include <boost/container/detail/algorithms.hpp> 65 #endif
37 #include <boost/container/allocator_traits.hpp> 66
38 #include <boost/container/throw_exception.hpp> 67 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
39 #include <boost/intrusive/pointer_traits.hpp> 68 #include <boost/container/vector.hpp>
40 #include <boost/detail/no_exceptions_support.hpp> 69 //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
41 #include <boost/aligned_storage.hpp> 70 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
42 #include <boost/move/utility.hpp>
43 #include <boost/move/iterator.hpp>
44 #include <boost/move/detail/move_helpers.hpp>
45 #include <algorithm> //max
46
47 #include <memory>
48 #include <new> //placement new
49
50 ///@cond
51
52 #include <boost/container/vector.hpp>
53
54 //#define STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
55
56 ///@endcond
57 71
58 namespace boost { 72 namespace boost {
59 namespace container { 73 namespace container {
60 74
61 ///@cond 75 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
62 76
63 namespace stable_vector_detail{ 77 namespace stable_vector_detail{
64 78
65 template <class C> 79 template <class C>
66 class clear_on_destroy 80 class clear_on_destroy
75 89
76 ~clear_on_destroy() 90 ~clear_on_destroy()
77 { 91 {
78 if(do_clear_){ 92 if(do_clear_){
79 c_.clear(); 93 c_.clear();
80 c_.priv_clear_pool(); 94 c_.priv_clear_pool();
81 } 95 }
82 } 96 }
83 97
84 private: 98 private:
85 clear_on_destroy(const clear_on_destroy &); 99 clear_on_destroy(const clear_on_destroy &);
121 : public node_base 135 : public node_base
122 <typename ::boost::intrusive::pointer_traits<Pointer>::template 136 <typename ::boost::intrusive::pointer_traits<Pointer>::template
123 rebind_pointer<void>::type 137 rebind_pointer<void>::type
124 > 138 >
125 { 139 {
126 // private: 140 private:
127 // node(); 141 node();
128 142
129 public: 143 public:
130 typename ::boost::intrusive::pointer_traits<Pointer>::element_type value; 144 typename ::boost::intrusive::pointer_traits<Pointer>::element_type value;
131 };
132
133 template<typename Pointer, bool IsConst>
134 class iterator
135 {
136 typedef boost::intrusive::pointer_traits<Pointer> non_const_ptr_traits;
137 public:
138 typedef std::random_access_iterator_tag iterator_category;
139 typedef typename non_const_ptr_traits::element_type value_type;
140 typedef typename non_const_ptr_traits::difference_type difference_type;
141 typedef typename ::boost::container::container_detail::if_c
142 < IsConst
143 , typename non_const_ptr_traits::template
144 rebind_pointer<const value_type>::type
145 , Pointer
146 >::type pointer;
147 typedef typename ::boost::container::container_detail::if_c
148 < IsConst
149 , const value_type&
150 , value_type&
151 >::type reference;
152
153 private:
154 typedef typename non_const_ptr_traits::template
155 rebind_pointer<void>::type void_ptr;
156 typedef node<Pointer> node_type;
157 typedef node_base<void_ptr> node_base_type;
158 typedef typename non_const_ptr_traits::template
159 rebind_pointer<node_type>::type node_ptr;
160 typedef boost::intrusive::
161 pointer_traits<node_ptr> node_ptr_traits;
162 typedef typename non_const_ptr_traits::template
163 rebind_pointer<node_base_type>::type node_base_ptr;
164 typedef typename non_const_ptr_traits::template
165 rebind_pointer<node_base_ptr>::type node_base_ptr_ptr;
166
167 node_ptr m_pn;
168
169 public:
170
171 explicit iterator(node_ptr p) BOOST_CONTAINER_NOEXCEPT
172 : m_pn(p)
173 {}
174
175 iterator() BOOST_CONTAINER_NOEXCEPT
176 {}
177
178 iterator(iterator<Pointer, false> const& other) BOOST_CONTAINER_NOEXCEPT
179 : m_pn(other.node_pointer())
180 {}
181
182 node_ptr &node_pointer() BOOST_CONTAINER_NOEXCEPT
183 { return m_pn; }
184
185 const node_ptr &node_pointer() const BOOST_CONTAINER_NOEXCEPT
186 { return m_pn; }
187
188 public:
189 //Pointer like operators
190 reference operator*() const BOOST_CONTAINER_NOEXCEPT
191 { return m_pn->value; }
192
193 pointer operator->() const BOOST_CONTAINER_NOEXCEPT
194 {
195 typedef boost::intrusive::pointer_traits<pointer> ptr_traits;
196 return ptr_traits::pointer_to(this->operator*());
197 }
198
199 //Increment / Decrement
200 iterator& operator++() BOOST_CONTAINER_NOEXCEPT
201 {
202 if(node_base_ptr_ptr p = this->m_pn->up){
203 ++p;
204 this->m_pn = node_ptr_traits::static_cast_from(*p);
205 }
206 return *this;
207 }
208
209 iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
210 { iterator tmp(*this); ++*this; return iterator(tmp); }
211
212 iterator& operator--() BOOST_CONTAINER_NOEXCEPT
213 {
214 if(node_base_ptr_ptr p = this->m_pn->up){
215 --p;
216 this->m_pn = node_ptr_traits::static_cast_from(*p);
217 }
218 return *this;
219 }
220
221 iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
222 { iterator tmp(*this); --*this; return iterator(tmp); }
223
224 reference operator[](difference_type off) const BOOST_CONTAINER_NOEXCEPT
225 {
226 iterator tmp(*this);
227 tmp += off;
228 return *tmp;
229 }
230
231 iterator& operator+=(difference_type off) BOOST_CONTAINER_NOEXCEPT
232 {
233 if(node_base_ptr_ptr p = this->m_pn->up){
234 p += off;
235 this->m_pn = node_ptr_traits::static_cast_from(*p);
236 }
237 return *this;
238 }
239
240 friend iterator operator+(const iterator &left, difference_type off) BOOST_CONTAINER_NOEXCEPT
241 {
242 iterator tmp(left);
243 tmp += off;
244 return tmp;
245 }
246
247 friend iterator operator+(difference_type off, const iterator& right) BOOST_CONTAINER_NOEXCEPT
248 {
249 iterator tmp(right);
250 tmp += off;
251 return tmp;
252 }
253
254 iterator& operator-=(difference_type off) BOOST_CONTAINER_NOEXCEPT
255 { *this += -off; return *this; }
256
257 friend iterator operator-(const iterator &left, difference_type off) BOOST_CONTAINER_NOEXCEPT
258 {
259 iterator tmp(left);
260 tmp -= off;
261 return tmp;
262 }
263
264 friend difference_type operator-(const iterator& left, const iterator& right) BOOST_CONTAINER_NOEXCEPT
265 { return left.m_pn->up - right.m_pn->up; }
266
267 //Comparison operators
268 friend bool operator== (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
269 { return l.m_pn == r.m_pn; }
270
271 friend bool operator!= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
272 { return l.m_pn != r.m_pn; }
273
274 friend bool operator< (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
275 { return l.m_pn->up < r.m_pn->up; }
276
277 friend bool operator<= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
278 { return l.m_pn->up <= r.m_pn->up; }
279
280 friend bool operator> (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
281 { return l.m_pn->up > r.m_pn->up; }
282
283 friend bool operator>= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
284 { return l.m_pn->up >= r.m_pn->up; }
285 }; 145 };
286 146
287 template<class VoidPtr, class VoidAllocator> 147 template<class VoidPtr, class VoidAllocator>
288 struct index_traits 148 struct index_traits
289 { 149 {
375 #endif //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING 235 #endif //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
376 }; 236 };
377 237
378 } //namespace stable_vector_detail 238 } //namespace stable_vector_detail
379 239
380 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 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 };
381 374
382 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) 375 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
383 376
384 #define STABLE_VECTOR_CHECK_INVARIANT \ 377 #define STABLE_VECTOR_CHECK_INVARIANT \
385 invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \ 378 invariant_checker BOOST_JOIN(check_invariant_,__LINE__)(*this); \
386 BOOST_JOIN(check_invariant_,__LINE__).touch(); 379 BOOST_JOIN(check_invariant_,__LINE__).touch();
387 380
388 #else //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING 381 #else //STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
389 382
390 #define STABLE_VECTOR_CHECK_INVARIANT 383 #define STABLE_VECTOR_CHECK_INVARIANT
391 384
392 #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) 385 #endif //#if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
393 386
394 #endif //#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 387 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
395
396 /// @endcond
397 388
398 //! Originally developed by Joaquin M. Lopez Munoz, stable_vector is a std::vector 389 //! Originally developed by Joaquin M. Lopez Munoz, stable_vector is a std::vector
399 //! drop-in replacement implemented as a node container, offering iterator and reference 390 //! drop-in replacement implemented as a node container, offering iterator and reference
400 //! stability. 391 //! stability.
401 //! 392 //!
424 //! of performance for the extra burden of doing more pointer manipulation and an 415 //! of performance for the extra burden of doing more pointer manipulation and an
425 //! additional allocation per element. 416 //! additional allocation per element.
426 //! 417 //!
427 //! Exception safety: As stable_vector does not internally copy elements around, some 418 //! Exception safety: As stable_vector does not internally copy elements around, some
428 //! operations provide stronger exception safety guarantees than in std::vector. 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
429 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 423 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
430 template <class T, class Allocator = std::allocator<T> > 424 template <class T, class Allocator = new_allocator<T> >
431 #else 425 #else
432 template <class T, class Allocator> 426 template <class T, class Allocator>
433 #endif 427 #endif
434 class stable_vector 428 class stable_vector
435 { 429 {
436 ///@cond 430 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
437 typedef allocator_traits<Allocator> allocator_traits_type; 431 typedef allocator_traits<Allocator> allocator_traits_type;
438 typedef boost::intrusive:: 432 typedef boost::intrusive::
439 pointer_traits 433 pointer_traits
440 <typename allocator_traits_type::pointer> ptr_traits; 434 <typename allocator_traits_type::pointer> ptr_traits;
441 typedef typename ptr_traits:: 435 typedef typename ptr_traits::
468 typedef boost::intrusive:: 462 typedef boost::intrusive::
469 pointer_traits<const_node_ptr> const_node_ptr_traits; 463 pointer_traits<const_node_ptr> const_node_ptr_traits;
470 typedef typename node_ptr_traits::reference node_reference; 464 typedef typename node_ptr_traits::reference node_reference;
471 typedef typename const_node_ptr_traits::reference const_node_reference; 465 typedef typename const_node_ptr_traits::reference const_node_reference;
472 466
473 typedef ::boost::container::container_detail::
474 integral_constant<unsigned, 1> allocator_v1;
475 typedef ::boost::container::container_detail::
476 integral_constant<unsigned, 2> allocator_v2;
477 typedef ::boost::container::container_detail::integral_constant 467 typedef ::boost::container::container_detail::integral_constant
478 <unsigned, boost::container::container_detail:: 468 <unsigned, boost::container::container_detail::
479 version<Allocator>::value> alloc_version; 469 version<Allocator>::value> alloc_version;
480 typedef typename allocator_traits_type:: 470 typedef typename allocator_traits_type::
481 template portable_rebind_alloc 471 template portable_rebind_alloc
496 486
497 void deallocate_individual(multiallocation_chain &holder) 487 void deallocate_individual(multiallocation_chain &holder)
498 { allocator_version_traits_t::deallocate_individual(this->priv_node_alloc(), holder); } 488 { allocator_version_traits_t::deallocate_individual(this->priv_node_alloc(), holder); }
499 489
500 friend class stable_vector_detail::clear_on_destroy<stable_vector>; 490 friend class stable_vector_detail::clear_on_destroy<stable_vector>;
501 typedef stable_vector_detail::iterator 491 typedef stable_vector_iterator
502 < typename allocator_traits<Allocator>::pointer 492 < typename allocator_traits<Allocator>::pointer
503 , false> iterator_impl; 493 , false> iterator_impl;
504 typedef stable_vector_detail::iterator 494 typedef stable_vector_iterator
505 < typename allocator_traits<Allocator>::pointer 495 < typename allocator_traits<Allocator>::pointer
506 , false> const_iterator_impl; 496 , false> const_iterator_impl;
507 ///@endcond 497 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
508 public: 498 public:
509 499
510 ////////////////////////////////////////////// 500 //////////////////////////////////////////////
511 // 501 //
512 // types 502 // types
521 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type; 511 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
522 typedef Allocator allocator_type; 512 typedef Allocator allocator_type;
523 typedef node_allocator_type stored_allocator_type; 513 typedef node_allocator_type stored_allocator_type;
524 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator; 514 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
525 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator; 515 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
526 typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<iterator>) reverse_iterator; 516 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<iterator>) reverse_iterator;
527 typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<const_iterator>) const_reverse_iterator; 517 typedef BOOST_CONTAINER_IMPDEF(boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
528 518
529 ///@cond 519 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
530 private: 520 private:
531 BOOST_COPYABLE_AND_MOVABLE(stable_vector) 521 BOOST_COPYABLE_AND_MOVABLE(stable_vector)
532 static const size_type ExtraPointers = index_traits_type::ExtraPointers; 522 static const size_type ExtraPointers = index_traits_type::ExtraPointers;
533 523
534 class insert_rollback; 524 class insert_rollback;
535 friend class insert_rollback; 525 friend class insert_rollback;
536 526
537 class push_back_rollback; 527 class push_back_rollback;
538 friend class push_back_rollback; 528 friend class push_back_rollback;
539 ///@endcond 529 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
540 530
541 public: 531 public:
542 ////////////////////////////////////////////// 532 //////////////////////////////////////////////
543 // 533 //
544 // construct/copy/destroy 534 // construct/copy/destroy
559 //! <b>Effects</b>: Constructs a stable_vector taking the allocator as parameter. 549 //! <b>Effects</b>: Constructs a stable_vector taking the allocator as parameter.
560 //! 550 //!
561 //! <b>Throws</b>: Nothing 551 //! <b>Throws</b>: Nothing
562 //! 552 //!
563 //! <b>Complexity</b>: Constant. 553 //! <b>Complexity</b>: Constant.
564 explicit stable_vector(const allocator_type& al) BOOST_CONTAINER_NOEXCEPT 554 explicit stable_vector(const allocator_type& al) BOOST_NOEXCEPT_OR_NOTHROW
565 : internal_data(al), index(al) 555 : internal_data(al), index(al)
566 { 556 {
567 STABLE_VECTOR_CHECK_INVARIANT; 557 STABLE_VECTOR_CHECK_INVARIANT;
568 } 558 }
569 559
570 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a 560 //! <b>Effects</b>: Constructs a stable_vector
571 //! and inserts n value initialized values. 561 //! and inserts n value initialized values.
572 //! 562 //!
573 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor 563 //! <b>Throws</b>: If allocator_type's default constructor
574 //! throws or T's default or copy constructor throws. 564 //! throws or T's default or copy constructor throws.
575 //! 565 //!
576 //! <b>Complexity</b>: Linear to n. 566 //! <b>Complexity</b>: Linear to n.
577 explicit stable_vector(size_type n) 567 explicit stable_vector(size_type n)
578 : internal_data(), index() 568 : internal_data(), index()
581 this->resize(n); 571 this->resize(n);
582 STABLE_VECTOR_CHECK_INVARIANT; 572 STABLE_VECTOR_CHECK_INVARIANT;
583 cod.release(); 573 cod.release();
584 } 574 }
585 575
586 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a 576 //! <b>Effects</b>: Constructs a stable_vector
587 //! and inserts n default initialized values. 577 //! and inserts n default initialized values.
588 //! 578 //!
589 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor 579 //! <b>Throws</b>: If allocator_type's default constructor
590 //! throws or T's default or copy constructor throws. 580 //! throws or T's default or copy constructor throws.
591 //! 581 //!
592 //! <b>Complexity</b>: Linear to n. 582 //! <b>Complexity</b>: Linear to n.
593 //! 583 //!
594 //! <b>Note</b>: Non-standard extension 584 //! <b>Note</b>: Non-standard extension
600 STABLE_VECTOR_CHECK_INVARIANT; 590 STABLE_VECTOR_CHECK_INVARIANT;
601 cod.release(); 591 cod.release();
602 } 592 }
603 593
604 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a 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
605 //! and inserts n copies of value. 629 //! and inserts n copies of value.
606 //! 630 //!
607 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor 631 //! <b>Throws</b>: If allocator_type's default constructor
608 //! throws or T's default or copy constructor throws. 632 //! throws or T's default or copy constructor throws.
609 //! 633 //!
610 //! <b>Complexity</b>: Linear to n. 634 //! <b>Complexity</b>: Linear to n.
611 stable_vector(size_type n, const T& t, const allocator_type& al = allocator_type()) 635 stable_vector(size_type n, const T& t, const allocator_type& al = allocator_type())
612 : internal_data(al), index(al) 636 : internal_data(al), index(al)
618 } 642 }
619 643
620 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a 644 //! <b>Effects</b>: Constructs a stable_vector that will use a copy of allocator a
621 //! and inserts a copy of the range [first, last) in the stable_vector. 645 //! and inserts a copy of the range [first, last) in the stable_vector.
622 //! 646 //!
623 //! <b>Throws</b>: If allocator_type's default constructor or copy constructor 647 //! <b>Throws</b>: If allocator_type's default constructor
624 //! throws or T's constructor taking an dereferenced InIt throws. 648 //! throws or T's constructor taking a dereferenced InIt throws.
625 //! 649 //!
626 //! <b>Complexity</b>: Linear to the range [first, last). 650 //! <b>Complexity</b>: Linear to the range [first, last).
627 template <class InputIterator> 651 template <class InputIterator>
628 stable_vector(InputIterator first,InputIterator last, const allocator_type& al = allocator_type()) 652 stable_vector(InputIterator first,InputIterator last, const allocator_type& al = allocator_type())
629 : internal_data(al), index(al) 653 : internal_data(al), index(al)
649 this->insert(this->cend(), x.begin(), x.end()); 673 this->insert(this->cend(), x.begin(), x.end());
650 STABLE_VECTOR_CHECK_INVARIANT; 674 STABLE_VECTOR_CHECK_INVARIANT;
651 cod.release(); 675 cod.release();
652 } 676 }
653 677
654 //! <b>Effects</b>: Move constructor. Moves mx's resources to *this. 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.
655 //! 697 //!
656 //! <b>Throws</b>: If allocator_type's copy constructor throws. 698 //! <b>Throws</b>: If allocator_type's copy constructor throws.
657 //! 699 //!
658 //! <b>Complexity</b>: Constant. 700 //! <b>Complexity</b>: Constant.
659 stable_vector(BOOST_RV_REF(stable_vector) x) 701 stable_vector(BOOST_RV_REF(stable_vector) x)
675 STABLE_VECTOR_CHECK_INVARIANT; 717 STABLE_VECTOR_CHECK_INVARIANT;
676 cod.release(); 718 cod.release();
677 } 719 }
678 720
679 //! <b>Effects</b>: Move constructor using the specified allocator. 721 //! <b>Effects</b>: Move constructor using the specified allocator.
680 //! Moves mx's resources to *this. 722 //! Moves x's resources to *this.
681 //! 723 //!
682 //! <b>Throws</b>: If allocator_type's copy constructor throws. 724 //! <b>Throws</b>: If allocator_type's copy constructor throws.
683 //! 725 //!
684 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise 726 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
685 stable_vector(BOOST_RV_REF(stable_vector) x, const allocator_type &a) 727 stable_vector(BOOST_RV_REF(stable_vector) x, const allocator_type &a)
686 : internal_data(a), index(a) 728 : internal_data(a), index(a)
687 { 729 {
688 if(this->priv_node_alloc() == x.priv_node_alloc()){ 730 if(this->priv_node_alloc() == x.priv_node_alloc()){
731 this->index.swap(x.index);
689 this->priv_swap_members(x); 732 this->priv_swap_members(x);
690 } 733 }
691 else{ 734 else{
692 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this); 735 stable_vector_detail::clear_on_destroy<stable_vector> cod(*this);
693 this->insert(this->cend(), x.begin(), x.end()); 736 this->insert(this->cend(), boost::make_move_iterator(x.begin()), boost::make_move_iterator(x.end()));
694 STABLE_VECTOR_CHECK_INVARIANT; 737 STABLE_VECTOR_CHECK_INVARIANT;
695 cod.release(); 738 cod.release();
696 } 739 }
697 } 740 }
698 741
703 //! 746 //!
704 //! <b>Complexity</b>: Linear to the number of elements. 747 //! <b>Complexity</b>: Linear to the number of elements.
705 ~stable_vector() 748 ~stable_vector()
706 { 749 {
707 this->clear(); 750 this->clear();
708 this->priv_clear_pool(); 751 this->priv_clear_pool();
709 } 752 }
710 753
711 //! <b>Effects</b>: Makes *this contain the same elements as x. 754 //! <b>Effects</b>: Makes *this contain the same elements as x.
712 //! 755 //!
713 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 756 //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy
733 this->assign(x.begin(), x.end()); 776 this->assign(x.begin(), x.end());
734 } 777 }
735 return *this; 778 return *this;
736 } 779 }
737 780
738 //! <b>Effects</b>: Move assignment. All mx's values are transferred to *this. 781 //! <b>Effects</b>: Move assignment. All x's values are transferred to *this.
739 //! 782 //!
740 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had 783 //! <b>Postcondition</b>: x.empty(). *this contains a the elements x had
741 //! before the function. 784 //! before the function.
742 //! 785 //!
743 //! <b>Throws</b>: If allocator_type's copy constructor throws. 786 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
744 //! 787 //! is false and (allocation throws or T's move constructor throws)
745 //! <b>Complexity</b>: Linear. 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.
746 stable_vector& operator=(BOOST_RV_REF(stable_vector) x) 792 stable_vector& operator=(BOOST_RV_REF(stable_vector) x)
747 { 793 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
748 if (&x != this){ 794 || allocator_traits_type::is_always_equal::value)
749 node_allocator_type &this_alloc = this->priv_node_alloc(); 795 {
750 node_allocator_type &x_alloc = x.priv_node_alloc(); 796 //for move constructor, no aliasing (&x != this) is assummed.
751 //If allocators are equal we can just swap pointers 797 BOOST_ASSERT(this != &x);
752 if(this_alloc == x_alloc){ 798 node_allocator_type &this_alloc = this->priv_node_alloc();
753 //Destroy objects but retain memory 799 node_allocator_type &x_alloc = x.priv_node_alloc();
754 this->clear(); 800 const bool propagate_alloc = allocator_traits_type::
755 this->index = boost::move(x.index); 801 propagate_on_container_move_assignment::value;
756 this->priv_swap_members(x); 802 container_detail::bool_<propagate_alloc> flag;
757 //Move allocator if needed 803 const bool allocators_equal = this_alloc == x_alloc; (void)allocators_equal;
758 container_detail::bool_<allocator_traits_type:: 804 //Resources can be transferred if both allocators are
759 propagate_on_container_move_assignment::value> flag; 805 //going to be equal after this function (either propagated or already equal)
760 container_detail::move_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag); 806 if(propagate_alloc || allocators_equal){
761 } 807 //Destroy objects but retain memory in case x reuses it in the future
762 //If unequal allocators, then do a one by one move 808 this->clear();
763 else{ 809 //Move allocator if needed
764 this->assign( boost::make_move_iterator(x.begin()) 810 container_detail::move_alloc(this_alloc, x_alloc, flag);
765 , boost::make_move_iterator(x.end())); 811 //Take resources
766 } 812 this->index.swap(x.index);
813 this->priv_swap_members(x);
814 }
815 //Else do a one by one move
816 else{
817 this->assign( boost::make_move_iterator(x.begin())
818 , boost::make_move_iterator(x.end()));
767 } 819 }
768 return *this; 820 return *this;
769 } 821 }
770 822
823 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
824 //! <b>Effects</b>: Make *this container contains elements from il.
825 //!
826 //! <b>Complexity</b>: Linear to the range [il.begin(), il.end()).
827 stable_vector& operator=(std::initializer_list<value_type> il)
828 {
829 STABLE_VECTOR_CHECK_INVARIANT;
830 assign(il.begin(), il.end());
831 return *this;
832 }
833 #endif
771 834
772 //! <b>Effects</b>: Assigns the n copies of val to *this. 835 //! <b>Effects</b>: Assigns the n copies of val to *this.
773 //! 836 //!
774 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws. 837 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
775 //! 838 //!
806 else{ 869 else{
807 this->insert(last1, first, last); 870 this->insert(last1, first, last);
808 } 871 }
809 } 872 }
810 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
811 //! <b>Effects</b>: Returns a copy of the internal allocator. 887 //! <b>Effects</b>: Returns a copy of the internal allocator.
812 //! 888 //!
813 //! <b>Throws</b>: If allocator's copy constructor throws. 889 //! <b>Throws</b>: If allocator's copy constructor throws.
814 //! 890 //!
815 //! <b>Complexity</b>: Constant. 891 //! <b>Complexity</b>: Constant.
821 //! <b>Throws</b>: Nothing 897 //! <b>Throws</b>: Nothing
822 //! 898 //!
823 //! <b>Complexity</b>: Constant. 899 //! <b>Complexity</b>: Constant.
824 //! 900 //!
825 //! <b>Note</b>: Non-standard extension. 901 //! <b>Note</b>: Non-standard extension.
826 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT 902 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
827 { return this->priv_node_alloc(); } 903 { return this->priv_node_alloc(); }
828 904
829 //! <b>Effects</b>: Returns a reference to the internal allocator. 905 //! <b>Effects</b>: Returns a reference to the internal allocator.
830 //! 906 //!
831 //! <b>Throws</b>: Nothing 907 //! <b>Throws</b>: Nothing
832 //! 908 //!
833 //! <b>Complexity</b>: Constant. 909 //! <b>Complexity</b>: Constant.
834 //! 910 //!
835 //! <b>Note</b>: Non-standard extension. 911 //! <b>Note</b>: Non-standard extension.
836 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT 912 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
837 { return this->priv_node_alloc(); } 913 { return this->priv_node_alloc(); }
838 914
839 ////////////////////////////////////////////// 915 //////////////////////////////////////////////
840 // 916 //
841 // iterators 917 // iterators
845 //! <b>Effects</b>: Returns an iterator to the first element contained in the stable_vector. 921 //! <b>Effects</b>: Returns an iterator to the first element contained in the stable_vector.
846 //! 922 //!
847 //! <b>Throws</b>: Nothing. 923 //! <b>Throws</b>: Nothing.
848 //! 924 //!
849 //! <b>Complexity</b>: Constant. 925 //! <b>Complexity</b>: Constant.
850 iterator begin() BOOST_CONTAINER_NOEXCEPT 926 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
851 { return (this->index.empty()) ? this->end(): iterator(node_ptr_traits::static_cast_from(this->index.front())); } 927 { return (this->index.empty()) ? this->end(): iterator(node_ptr_traits::static_cast_from(this->index.front())); }
852 928
853 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector. 929 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
854 //! 930 //!
855 //! <b>Throws</b>: Nothing. 931 //! <b>Throws</b>: Nothing.
856 //! 932 //!
857 //! <b>Complexity</b>: Constant. 933 //! <b>Complexity</b>: Constant.
858 const_iterator begin() const BOOST_CONTAINER_NOEXCEPT 934 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
859 { return (this->index.empty()) ? this->cend() : const_iterator(node_ptr_traits::static_cast_from(this->index.front())) ; } 935 { return (this->index.empty()) ? this->cend() : const_iterator(node_ptr_traits::static_cast_from(this->index.front())) ; }
860 936
861 //! <b>Effects</b>: Returns an iterator to the end of the stable_vector. 937 //! <b>Effects</b>: Returns an iterator to the end of the stable_vector.
862 //! 938 //!
863 //! <b>Throws</b>: Nothing. 939 //! <b>Throws</b>: Nothing.
864 //! 940 //!
865 //! <b>Complexity</b>: Constant. 941 //! <b>Complexity</b>: Constant.
866 iterator end() BOOST_CONTAINER_NOEXCEPT 942 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
867 { return iterator(this->priv_get_end_node()); } 943 { return iterator(this->priv_get_end_node()); }
868 944
869 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector. 945 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
870 //! 946 //!
871 //! <b>Throws</b>: Nothing. 947 //! <b>Throws</b>: Nothing.
872 //! 948 //!
873 //! <b>Complexity</b>: Constant. 949 //! <b>Complexity</b>: Constant.
874 const_iterator end() const BOOST_CONTAINER_NOEXCEPT 950 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
875 { return const_iterator(this->priv_get_end_node()); } 951 { return const_iterator(this->priv_get_end_node()); }
876 952
877 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning 953 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
878 //! of the reversed stable_vector. 954 //! of the reversed stable_vector.
879 //! 955 //!
880 //! <b>Throws</b>: Nothing. 956 //! <b>Throws</b>: Nothing.
881 //! 957 //!
882 //! <b>Complexity</b>: Constant. 958 //! <b>Complexity</b>: Constant.
883 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT 959 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
884 { return reverse_iterator(this->end()); } 960 { return reverse_iterator(this->end()); }
885 961
886 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 962 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
887 //! of the reversed stable_vector. 963 //! of the reversed stable_vector.
888 //! 964 //!
889 //! <b>Throws</b>: Nothing. 965 //! <b>Throws</b>: Nothing.
890 //! 966 //!
891 //! <b>Complexity</b>: Constant. 967 //! <b>Complexity</b>: Constant.
892 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT 968 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
893 { return const_reverse_iterator(this->end()); } 969 { return const_reverse_iterator(this->end()); }
894 970
895 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end 971 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
896 //! of the reversed stable_vector. 972 //! of the reversed stable_vector.
897 //! 973 //!
898 //! <b>Throws</b>: Nothing. 974 //! <b>Throws</b>: Nothing.
899 //! 975 //!
900 //! <b>Complexity</b>: Constant. 976 //! <b>Complexity</b>: Constant.
901 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT 977 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
902 { return reverse_iterator(this->begin()); } 978 { return reverse_iterator(this->begin()); }
903 979
904 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 980 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
905 //! of the reversed stable_vector. 981 //! of the reversed stable_vector.
906 //! 982 //!
907 //! <b>Throws</b>: Nothing. 983 //! <b>Throws</b>: Nothing.
908 //! 984 //!
909 //! <b>Complexity</b>: Constant. 985 //! <b>Complexity</b>: Constant.
910 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT 986 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
911 { return const_reverse_iterator(this->begin()); } 987 { return const_reverse_iterator(this->begin()); }
912 988
913 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector. 989 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the stable_vector.
914 //! 990 //!
915 //! <b>Throws</b>: Nothing. 991 //! <b>Throws</b>: Nothing.
916 //! 992 //!
917 //! <b>Complexity</b>: Constant. 993 //! <b>Complexity</b>: Constant.
918 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT 994 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
919 { return this->begin(); } 995 { return this->begin(); }
920 996
921 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector. 997 //! <b>Effects</b>: Returns a const_iterator to the end of the stable_vector.
922 //! 998 //!
923 //! <b>Throws</b>: Nothing. 999 //! <b>Throws</b>: Nothing.
924 //! 1000 //!
925 //! <b>Complexity</b>: Constant. 1001 //! <b>Complexity</b>: Constant.
926 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT 1002 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
927 { return this->end(); } 1003 { return this->end(); }
928 1004
929 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning 1005 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
930 //! of the reversed stable_vector. 1006 //! of the reversed stable_vector.
931 //! 1007 //!
932 //! <b>Throws</b>: Nothing. 1008 //! <b>Throws</b>: Nothing.
933 //! 1009 //!
934 //! <b>Complexity</b>: Constant. 1010 //! <b>Complexity</b>: Constant.
935 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT 1011 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
936 { return this->rbegin(); } 1012 { return this->rbegin(); }
937 1013
938 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end 1014 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
939 //! of the reversed stable_vector. 1015 //! of the reversed stable_vector.
940 //! 1016 //!
941 //! <b>Throws</b>: Nothing. 1017 //! <b>Throws</b>: Nothing.
942 //! 1018 //!
943 //! <b>Complexity</b>: Constant. 1019 //! <b>Complexity</b>: Constant.
944 const_reverse_iterator crend()const BOOST_CONTAINER_NOEXCEPT 1020 const_reverse_iterator crend()const BOOST_NOEXCEPT_OR_NOTHROW
945 { return this->rend(); } 1021 { return this->rend(); }
946 1022
947 ////////////////////////////////////////////// 1023 //////////////////////////////////////////////
948 // 1024 //
949 // capacity 1025 // capacity
953 //! <b>Effects</b>: Returns true if the stable_vector contains no elements. 1029 //! <b>Effects</b>: Returns true if the stable_vector contains no elements.
954 //! 1030 //!
955 //! <b>Throws</b>: Nothing. 1031 //! <b>Throws</b>: Nothing.
956 //! 1032 //!
957 //! <b>Complexity</b>: Constant. 1033 //! <b>Complexity</b>: Constant.
958 bool empty() const BOOST_CONTAINER_NOEXCEPT 1034 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
959 { return this->index.size() <= ExtraPointers; } 1035 { return this->index.size() <= ExtraPointers; }
960 1036
961 //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector. 1037 //! <b>Effects</b>: Returns the number of the elements contained in the stable_vector.
962 //! 1038 //!
963 //! <b>Throws</b>: Nothing. 1039 //! <b>Throws</b>: Nothing.
964 //! 1040 //!
965 //! <b>Complexity</b>: Constant. 1041 //! <b>Complexity</b>: Constant.
966 size_type size() const BOOST_CONTAINER_NOEXCEPT 1042 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
967 { 1043 {
968 const size_type index_size = this->index.size(); 1044 const size_type index_size = this->index.size();
969 return (index_size - ExtraPointers) & (std::size_t(0u) -std::size_t(index_size != 0)); 1045 return (index_size - ExtraPointers) & (size_type(0u) -size_type(index_size != 0));
970 } 1046 }
971 1047
972 //! <b>Effects</b>: Returns the largest possible size of the stable_vector. 1048 //! <b>Effects</b>: Returns the largest possible size of the stable_vector.
973 //! 1049 //!
974 //! <b>Throws</b>: Nothing. 1050 //! <b>Throws</b>: Nothing.
975 //! 1051 //!
976 //! <b>Complexity</b>: Constant. 1052 //! <b>Complexity</b>: Constant.
977 size_type max_size() const BOOST_CONTAINER_NOEXCEPT 1053 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
978 { return this->index.max_size() - ExtraPointers; } 1054 { return this->index.max_size() - ExtraPointers; }
979 1055
980 //! <b>Effects</b>: Inserts or erases elements at the end such that 1056 //! <b>Effects</b>: Inserts or erases elements at the end such that
981 //! the size becomes n. New elements are value initialized. 1057 //! the size becomes n. New elements are value initialized.
982 //! 1058 //!
983 //! <b>Throws</b>: If memory allocation throws, or T's default constructor throws. 1059 //! <b>Throws</b>: If memory allocation throws, or T's value initialization throws.
984 //! 1060 //!
985 //! <b>Complexity</b>: Linear to the difference between size() and new_size. 1061 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
986 void resize(size_type n) 1062 void resize(size_type n)
987 { 1063 {
988 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator; 1064 typedef value_init_construct_iterator<value_type, difference_type> value_init_iterator;
994 } 1070 }
995 1071
996 //! <b>Effects</b>: Inserts or erases elements at the end such that 1072 //! <b>Effects</b>: Inserts or erases elements at the end such that
997 //! the size becomes n. New elements are default initialized. 1073 //! the size becomes n. New elements are default initialized.
998 //! 1074 //!
999 //! <b>Throws</b>: If memory allocation throws, or T's default constructor throws. 1075 //! <b>Throws</b>: If memory allocation throws, or T's default initialization throws.
1000 //! 1076 //!
1001 //! <b>Complexity</b>: Linear to the difference between size() and new_size. 1077 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
1002 //! 1078 //!
1003 //! <b>Note</b>: Non-standard extension 1079 //! <b>Note</b>: Non-standard extension
1004 void resize(size_type n, default_init_t) 1080 void resize(size_type n, default_init_t)
1030 //! capacity() is always greater than or equal to size(). 1106 //! capacity() is always greater than or equal to size().
1031 //! 1107 //!
1032 //! <b>Throws</b>: Nothing. 1108 //! <b>Throws</b>: Nothing.
1033 //! 1109 //!
1034 //! <b>Complexity</b>: Constant. 1110 //! <b>Complexity</b>: Constant.
1035 size_type capacity() const BOOST_CONTAINER_NOEXCEPT 1111 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
1036 { 1112 {
1037 const size_type index_size = this->index.size(); 1113 const size_type index_size = this->index.size();
1038 BOOST_ASSERT(!index_size || index_size >= ExtraPointers); 1114 BOOST_ASSERT(!index_size || index_size >= ExtraPointers);
1039 const size_type bucket_extra_capacity = this->index.capacity()- index_size; 1115 const size_type bucket_extra_capacity = this->index.capacity()- index_size;
1040 const size_type node_extra_capacity = this->internal_data.pool_size; 1116 const size_type node_extra_capacity = this->internal_data.pool_size;
1056 STABLE_VECTOR_CHECK_INVARIANT; 1132 STABLE_VECTOR_CHECK_INVARIANT;
1057 if(n > this->max_size()){ 1133 if(n > this->max_size()){
1058 throw_length_error("stable_vector::reserve max_size() exceeded"); 1134 throw_length_error("stable_vector::reserve max_size() exceeded");
1059 } 1135 }
1060 1136
1061 size_type sz = this->size(); 1137 size_type sz = this->size();
1062 size_type old_capacity = this->capacity(); 1138 size_type old_capacity = this->capacity();
1063 if(n > old_capacity){ 1139 if(n > old_capacity){
1064 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, n); 1140 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, n);
1065 const void * old_ptr = &index[0]; 1141 const void * old_ptr = &index[0];
1066 this->index.reserve(n + ExtraPointers); 1142 this->index.reserve(n + ExtraPointers);
1118 //! element of the container. 1194 //! element of the container.
1119 //! 1195 //!
1120 //! <b>Throws</b>: Nothing. 1196 //! <b>Throws</b>: Nothing.
1121 //! 1197 //!
1122 //! <b>Complexity</b>: Constant. 1198 //! <b>Complexity</b>: Constant.
1123 reference front() BOOST_CONTAINER_NOEXCEPT 1199 reference front() BOOST_NOEXCEPT_OR_NOTHROW
1124 { return static_cast<node_reference>(*this->index.front()).value; } 1200 { return static_cast<node_reference>(*this->index.front()).value; }
1125 1201
1126 //! <b>Requires</b>: !empty() 1202 //! <b>Requires</b>: !empty()
1127 //! 1203 //!
1128 //! <b>Effects</b>: Returns a const reference to the first 1204 //! <b>Effects</b>: Returns a const reference to the first
1129 //! element of the container. 1205 //! element of the container.
1130 //! 1206 //!
1131 //! <b>Throws</b>: Nothing. 1207 //! <b>Throws</b>: Nothing.
1132 //! 1208 //!
1133 //! <b>Complexity</b>: Constant. 1209 //! <b>Complexity</b>: Constant.
1134 const_reference front() const BOOST_CONTAINER_NOEXCEPT 1210 const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW
1135 { return static_cast<const_node_reference>(*this->index.front()).value; } 1211 { return static_cast<const_node_reference>(*this->index.front()).value; }
1136 1212
1137 //! <b>Requires</b>: !empty() 1213 //! <b>Requires</b>: !empty()
1138 //! 1214 //!
1139 //! <b>Effects</b>: Returns a reference to the last 1215 //! <b>Effects</b>: Returns a reference to the last
1140 //! element of the container. 1216 //! element of the container.
1141 //! 1217 //!
1142 //! <b>Throws</b>: Nothing. 1218 //! <b>Throws</b>: Nothing.
1143 //! 1219 //!
1144 //! <b>Complexity</b>: Constant. 1220 //! <b>Complexity</b>: Constant.
1145 reference back() BOOST_CONTAINER_NOEXCEPT 1221 reference back() BOOST_NOEXCEPT_OR_NOTHROW
1146 { return static_cast<node_reference>(*this->index[this->size()-1u]).value; } 1222 { return static_cast<node_reference>(*this->index[this->size()-1u]).value; }
1147 1223
1148 //! <b>Requires</b>: !empty() 1224 //! <b>Requires</b>: !empty()
1149 //! 1225 //!
1150 //! <b>Effects</b>: Returns a const reference to the last 1226 //! <b>Effects</b>: Returns a const reference to the last
1151 //! element of the container. 1227 //! element of the container.
1152 //! 1228 //!
1153 //! <b>Throws</b>: Nothing. 1229 //! <b>Throws</b>: Nothing.
1154 //! 1230 //!
1155 //! <b>Complexity</b>: Constant. 1231 //! <b>Complexity</b>: Constant.
1156 const_reference back() const BOOST_CONTAINER_NOEXCEPT 1232 const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW
1157 { return static_cast<const_node_reference>(*this->index[this->size()-1u]).value; } 1233 { return static_cast<const_node_reference>(*this->index[this->size()-1u]).value; }
1158 1234
1159 //! <b>Requires</b>: size() > n. 1235 //! <b>Requires</b>: size() > n.
1160 //! 1236 //!
1161 //! <b>Effects</b>: Returns a reference to the nth element 1237 //! <b>Effects</b>: Returns a reference to the nth element
1162 //! from the beginning of the container. 1238 //! from the beginning of the container.
1163 //! 1239 //!
1164 //! <b>Throws</b>: Nothing. 1240 //! <b>Throws</b>: Nothing.
1165 //! 1241 //!
1166 //! <b>Complexity</b>: Constant. 1242 //! <b>Complexity</b>: Constant.
1167 reference operator[](size_type n) BOOST_CONTAINER_NOEXCEPT 1243 reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1168 { 1244 {
1169 BOOST_ASSERT(n < this->size()); 1245 BOOST_ASSERT(n < this->size());
1170 return static_cast<node_reference>(*this->index[n]).value; 1246 return static_cast<node_reference>(*this->index[n]).value;
1171 } 1247 }
1172 1248
1176 //! from the beginning of the container. 1252 //! from the beginning of the container.
1177 //! 1253 //!
1178 //! <b>Throws</b>: Nothing. 1254 //! <b>Throws</b>: Nothing.
1179 //! 1255 //!
1180 //! <b>Complexity</b>: Constant. 1256 //! <b>Complexity</b>: Constant.
1181 const_reference operator[](size_type n) const BOOST_CONTAINER_NOEXCEPT 1257 const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1182 { 1258 {
1183 BOOST_ASSERT(n < this->size()); 1259 BOOST_ASSERT(n < this->size());
1184 return static_cast<const_node_reference>(*this->index[n]).value; 1260 return static_cast<const_node_reference>(*this->index[n]).value;
1185 } 1261 }
1262
1263 //! <b>Requires</b>: size() >= n.
1264 //!
1265 //! <b>Effects</b>: Returns an iterator to the nth element
1266 //! from the beginning of the container. Returns end()
1267 //! if n == size().
1268 //!
1269 //! <b>Throws</b>: Nothing.
1270 //!
1271 //! <b>Complexity</b>: Constant.
1272 //!
1273 //! <b>Note</b>: Non-standard extension
1274 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1275 {
1276 BOOST_ASSERT(this->size() >= n);
1277 return (this->index.empty()) ? this->end() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
1278 }
1279
1280 //! <b>Requires</b>: size() >= n.
1281 //!
1282 //! <b>Effects</b>: Returns a const_iterator to the nth element
1283 //! from the beginning of the container. Returns end()
1284 //! if n == size().
1285 //!
1286 //! <b>Throws</b>: Nothing.
1287 //!
1288 //! <b>Complexity</b>: Constant.
1289 //!
1290 //! <b>Note</b>: Non-standard extension
1291 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1292 {
1293 BOOST_ASSERT(this->size() >= n);
1294 return (this->index.empty()) ? this->cend() : iterator(node_ptr_traits::static_cast_from(this->index[n]));
1295 }
1296
1297 //! <b>Requires</b>: size() >= n.
1298 //!
1299 //! <b>Effects</b>: Returns an iterator to the nth element
1300 //! from the beginning of the container. Returns end()
1301 //! if n == size().
1302 //!
1303 //! <b>Throws</b>: Nothing.
1304 //!
1305 //! <b>Complexity</b>: Constant.
1306 //!
1307 //! <b>Note</b>: Non-standard extension
1308 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1309 { return this->priv_index_of(p.node_pointer()); }
1310
1311 //! <b>Requires</b>: begin() <= p <= end().
1312 //!
1313 //! <b>Effects</b>: Returns the index of the element pointed by p
1314 //! and size() if p == end().
1315 //!
1316 //! <b>Throws</b>: Nothing.
1317 //!
1318 //! <b>Complexity</b>: Constant.
1319 //!
1320 //! <b>Note</b>: Non-standard extension
1321 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1322 { return this->priv_index_of(p.node_pointer()); }
1186 1323
1187 //! <b>Requires</b>: size() > n. 1324 //! <b>Requires</b>: size() > n.
1188 //! 1325 //!
1189 //! <b>Effects</b>: Returns a reference to the nth element 1326 //! <b>Effects</b>: Returns a reference to the nth element
1190 //! from the beginning of the container. 1327 //! from the beginning of the container.
1220 // 1357 //
1221 // modifiers 1358 // modifiers
1222 // 1359 //
1223 ////////////////////////////////////////////// 1360 //////////////////////////////////////////////
1224 1361
1225 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1362 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1226 1363
1227 //! <b>Effects</b>: Inserts an object of type T constructed with 1364 //! <b>Effects</b>: Inserts an object of type T constructed with
1228 //! std::forward<Args>(args)... in the end of the stable_vector. 1365 //! std::forward<Args>(args)... in the end of the stable_vector.
1229 //! 1366 //!
1230 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. 1367 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1237 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator; 1374 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
1238 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...); 1375 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
1239 this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator()); 1376 this->insert(this->cend(), EmplaceIterator(ef), EmplaceIterator());
1240 } 1377 }
1241 1378
1242 //! <b>Requires</b>: position must be a valid iterator of *this. 1379 //! <b>Requires</b>: p must be a valid iterator of *this.
1243 //! 1380 //!
1244 //! <b>Effects</b>: Inserts an object of type T constructed with 1381 //! <b>Effects</b>: Inserts an object of type T constructed with
1245 //! std::forward<Args>(args)... before position 1382 //! std::forward<Args>(args)... before p
1246 //! 1383 //!
1247 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws. 1384 //! <b>Throws</b>: If memory allocation throws or the in-place constructor throws.
1248 //! 1385 //!
1249 //! <b>Complexity</b>: If position is end(), amortized constant time 1386 //! <b>Complexity</b>: If p is end(), amortized constant time
1250 //! Linear time otherwise. 1387 //! Linear time otherwise.
1251 template<class ...Args> 1388 template<class ...Args>
1252 iterator emplace(const_iterator position, Args && ...args) 1389 iterator emplace(const_iterator p, Args && ...args)
1253 { 1390 {
1254 //Just call more general insert(pos, size, value) and return iterator 1391 size_type pos_n = p - cbegin();
1255 size_type pos_n = position - cbegin();
1256 typedef emplace_functor<Args...> EmplaceFunctor; 1392 typedef emplace_functor<Args...> EmplaceFunctor;
1257 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator; 1393 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;
1258 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...); 1394 EmplaceFunctor &&ef = EmplaceFunctor(boost::forward<Args>(args)...);
1259 this->insert(position, EmplaceIterator(ef), EmplaceIterator()); 1395 this->insert(p, EmplaceIterator(ef), EmplaceIterator());
1260 return iterator(this->begin() + pos_n); 1396 return iterator(this->begin() + pos_n);
1261 } 1397 }
1262 1398
1263 #else 1399 #else
1264 1400
1265 #define BOOST_PP_LOCAL_MACRO(n) \ 1401 #define BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE(N) \
1266 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ 1402 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1267 void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ 1403 void emplace_back(BOOST_MOVE_UREF##N)\
1268 { \ 1404 {\
1269 typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ 1405 typedef emplace_functor##N\
1270 BOOST_PP_EXPR_IF(n, <) BOOST_PP_ENUM_PARAMS(n, P) BOOST_PP_EXPR_IF(n, >) \ 1406 BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
1271 EmplaceFunctor; \ 1407 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;\
1272 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator; \ 1408 EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
1273 EmplaceFunctor ef BOOST_PP_LPAREN_IF(n) \ 1409 this->insert(this->cend() , EmplaceIterator(ef), EmplaceIterator());\
1274 BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) \ 1410 }\
1275 BOOST_PP_RPAREN_IF(n); \ 1411 \
1276 this->insert(this->cend() , EmplaceIterator(ef), EmplaceIterator()); \ 1412 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1277 } \ 1413 iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1278 \ 1414 {\
1279 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ 1415 typedef emplace_functor##N\
1280 iterator emplace(const_iterator pos \ 1416 BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\
1281 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ 1417 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator;\
1282 { \ 1418 EmplaceFunctor ef BOOST_MOVE_LP##N BOOST_MOVE_FWD##N BOOST_MOVE_RP##N;\
1283 typedef BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ 1419 const size_type pos_n = p - this->cbegin();\
1284 BOOST_PP_EXPR_IF(n, <) BOOST_PP_ENUM_PARAMS(n, P) BOOST_PP_EXPR_IF(n, >) \ 1420 this->insert(p, EmplaceIterator(ef), EmplaceIterator());\
1285 EmplaceFunctor; \ 1421 return this->begin() += pos_n;\
1286 typedef emplace_iterator<value_type, EmplaceFunctor, difference_type> EmplaceIterator; \ 1422 }\
1287 EmplaceFunctor ef BOOST_PP_LPAREN_IF(n) \ 1423 //
1288 BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) \ 1424 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE)
1289 BOOST_PP_RPAREN_IF(n); \ 1425 #undef BOOST_CONTAINER_STABLE_VECTOR_EMPLACE_CODE
1290 size_type pos_n = pos - this->cbegin(); \ 1426
1291 this->insert(pos, EmplaceIterator(ef), EmplaceIterator()); \ 1427 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1292 return iterator(this->begin() + pos_n); \
1293 } \
1294 //!
1295 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
1296 #include BOOST_PP_LOCAL_ITERATE()
1297
1298 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1299 1428
1300 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1429 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1301 //! <b>Effects</b>: Inserts a copy of x at the end of the stable_vector. 1430 //! <b>Effects</b>: Inserts a copy of x at the end of the stable_vector.
1302 //! 1431 //!
1303 //! <b>Throws</b>: If memory allocation throws or 1432 //! <b>Throws</b>: If memory allocation throws or
1305 //! 1434 //!
1306 //! <b>Complexity</b>: Amortized constant time. 1435 //! <b>Complexity</b>: Amortized constant time.
1307 void push_back(const T &x); 1436 void push_back(const T &x);
1308 1437
1309 //! <b>Effects</b>: Constructs a new element in the end of the stable_vector 1438 //! <b>Effects</b>: Constructs a new element in the end of the stable_vector
1310 //! and moves the resources of mx to this new element. 1439 //! and moves the resources of x to this new element.
1311 //! 1440 //!
1312 //! <b>Throws</b>: If memory allocation throws. 1441 //! <b>Throws</b>: If memory allocation throws.
1313 //! 1442 //!
1314 //! <b>Complexity</b>: Amortized constant time. 1443 //! <b>Complexity</b>: Amortized constant time.
1315 void push_back(T &&x); 1444 void push_back(T &&x);
1316 #else 1445 #else
1317 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back) 1446 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1318 #endif 1447 #endif
1319 1448
1320 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1449 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1321 //! <b>Requires</b>: position must be a valid iterator of *this. 1450 //! <b>Requires</b>: p must be a valid iterator of *this.
1322 //! 1451 //!
1323 //! <b>Effects</b>: Insert a copy of x before position. 1452 //! <b>Effects</b>: Insert a copy of x before p.
1324 //! 1453 //!
1325 //! <b>Returns</b>: An iterator to the inserted element. 1454 //! <b>Returns</b>: An iterator to the inserted element.
1326 //! 1455 //!
1327 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws. 1456 //! <b>Throws</b>: If memory allocation throws or x's copy constructor throws.
1328 //! 1457 //!
1329 //! <b>Complexity</b>: If position is end(), amortized constant time 1458 //! <b>Complexity</b>: If p is end(), amortized constant time
1330 //! Linear time otherwise. 1459 //! Linear time otherwise.
1331 iterator insert(const_iterator position, const T &x); 1460 iterator insert(const_iterator p, const T &x);
1332 1461
1333 //! <b>Requires</b>: position must be a valid iterator of *this. 1462 //! <b>Requires</b>: p must be a valid iterator of *this.
1334 //! 1463 //!
1335 //! <b>Effects</b>: Insert a new element before position with mx's resources. 1464 //! <b>Effects</b>: Insert a new element before p with x's resources.
1336 //! 1465 //!
1337 //! <b>Returns</b>: an iterator to the inserted element. 1466 //! <b>Returns</b>: an iterator to the inserted element.
1338 //! 1467 //!
1339 //! <b>Throws</b>: If memory allocation throws. 1468 //! <b>Throws</b>: If memory allocation throws.
1340 //! 1469 //!
1341 //! <b>Complexity</b>: If position is end(), amortized constant time 1470 //! <b>Complexity</b>: If p is end(), amortized constant time
1342 //! Linear time otherwise. 1471 //! Linear time otherwise.
1343 iterator insert(const_iterator position, T &&x); 1472 iterator insert(const_iterator p, T &&x);
1344 #else 1473 #else
1345 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator) 1474 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1346 #endif 1475 #endif
1347 1476
1477 //! <b>Requires</b>: p must be a valid iterator of *this.
1478 //!
1479 //! <b>Effects</b>: Insert n copies of x before p.
1480 //!
1481 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
1482 //!
1483 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1484 //!
1485 //! <b>Complexity</b>: Linear to n.
1486 iterator insert(const_iterator p, size_type n, const T& t)
1487 {
1488 STABLE_VECTOR_CHECK_INVARIANT;
1489 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1490 return this->insert(p, cvalue_iterator(t, n), cvalue_iterator());
1491 }
1492
1493 //! <b>Requires</b>: p must be a valid iterator of *this.
1494 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1495 //! <b>Requires</b>: p must be a valid iterator of *this.
1496 //!
1497 //! <b>Effects</b>: Insert a copy of the [il.begin(), il.end()) range before p.
1498 //!
1499 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1500 //!
1501 //! <b>Complexity</b>: Linear to distance [il.begin(), il.end()).
1502 iterator insert(const_iterator p, std::initializer_list<value_type> il)
1503 {
1504 STABLE_VECTOR_CHECK_INVARIANT;
1505 return insert(p, il.begin(), il.end());
1506 }
1507 #endif
1508
1348 //! <b>Requires</b>: pos must be a valid iterator of *this. 1509 //! <b>Requires</b>: pos must be a valid iterator of *this.
1349 //! 1510 //!
1350 //! <b>Effects</b>: Insert n copies of x before position. 1511 //! <b>Effects</b>: Insert a copy of the [first, last) range before p.
1351 //! 1512 //!
1352 //! <b>Returns</b>: an iterator to the first inserted element or position if n is 0. 1513 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1353 //!
1354 //! <b>Throws</b>: If memory allocation throws or T's copy constructor throws.
1355 //!
1356 //! <b>Complexity</b>: Linear to n.
1357 iterator insert(const_iterator position, size_type n, const T& t)
1358 {
1359 STABLE_VECTOR_CHECK_INVARIANT;
1360 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1361 return this->insert(position, cvalue_iterator(t, n), cvalue_iterator());
1362 }
1363
1364 //! <b>Requires</b>: pos must be a valid iterator of *this.
1365 //!
1366 //! <b>Effects</b>: Insert a copy of the [first, last) range before pos.
1367 //!
1368 //! <b>Returns</b>: an iterator to the first inserted element or position if first == last.
1369 //! 1514 //!
1370 //! <b>Throws</b>: If memory allocation throws, T's constructor from a 1515 //! <b>Throws</b>: If memory allocation throws, T's constructor from a
1371 //! dereferenced InpIt throws or T's copy constructor throws. 1516 //! dereferenced InpIt throws or T's copy constructor throws.
1372 //! 1517 //!
1373 //! <b>Complexity</b>: Linear to std::distance [first, last). 1518 //! <b>Complexity</b>: Linear to distance [first, last).
1374 template <class InputIterator> 1519 template <class InputIterator>
1375 iterator insert(const_iterator position, InputIterator first, InputIterator last 1520 iterator insert(const_iterator p, InputIterator first, InputIterator last
1376 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1521 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1377 , typename container_detail::enable_if_c 1522 , typename container_detail::enable_if_c
1378 < !container_detail::is_convertible<InputIterator, size_type>::value 1523 < !container_detail::is_convertible<InputIterator, size_type>::value
1379 && container_detail::is_input_iterator<InputIterator>::value 1524 && container_detail::is_input_iterator<InputIterator>::value
1380 >::type * = 0 1525 >::type * = 0
1381 #endif 1526 #endif
1382 ) 1527 )
1383 { 1528 {
1384 STABLE_VECTOR_CHECK_INVARIANT; 1529 STABLE_VECTOR_CHECK_INVARIANT;
1385 const size_type pos_n = position - this->cbegin(); 1530 const size_type pos_n = p - this->cbegin();
1386 for(; first != last; ++first){ 1531 for(; first != last; ++first){
1387 this->emplace(position, *first); 1532 this->emplace(p, *first);
1388 } 1533 }
1389 return this->begin() + pos_n; 1534 return this->begin() + pos_n;
1390 } 1535 }
1391 1536
1392 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) 1537 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1393 template <class FwdIt> 1538 template <class FwdIt>
1394 iterator insert(const_iterator position, FwdIt first, FwdIt last 1539 iterator insert(const_iterator p, FwdIt first, FwdIt last
1395 , typename container_detail::enable_if_c 1540 , typename container_detail::enable_if_c
1396 < !container_detail::is_convertible<FwdIt, size_type>::value 1541 < !container_detail::is_convertible<FwdIt, size_type>::value
1397 && !container_detail::is_input_iterator<FwdIt>::value 1542 && !container_detail::is_input_iterator<FwdIt>::value
1398 >::type * = 0 1543 >::type * = 0
1399 ) 1544 )
1400 { 1545 {
1401 const size_type num_new = static_cast<size_type>(std::distance(first, last)); 1546 const size_type num_new = static_cast<size_type>(boost::container::iterator_distance(first, last));
1402 const size_type pos = static_cast<size_type>(position - this->cbegin()); 1547 const size_type idx = static_cast<size_type>(p - this->cbegin());
1403 if(num_new){ 1548 if(num_new){
1404 //Fills the node pool and inserts num_new null pointers in pos. 1549 //Fills the node pool and inserts num_new null pointers in idx.
1405 //If a new buffer was needed fixes up pointers up to pos so 1550 //If a new buffer was needed fixes up pointers up to idx so
1406 //past-new nodes are not aligned until the end of this function 1551 //past-new nodes are not aligned until the end of this function
1407 //or in a rollback in case of exception 1552 //or in a rollback in case of exception
1408 index_iterator it_past_newly_constructed(this->priv_insert_forward_non_templated(pos, num_new)); 1553 index_iterator it_past_newly_constructed(this->priv_insert_forward_non_templated(idx, num_new));
1409 const index_iterator it_past_new(it_past_newly_constructed + num_new); 1554 const index_iterator it_past_new(it_past_newly_constructed + num_new);
1410 { 1555 {
1411 //Prepare rollback 1556 //Prepare rollback
1412 insert_rollback rollback(*this, it_past_newly_constructed, it_past_new); 1557 insert_rollback rollback(*this, it_past_newly_constructed, it_past_new);
1413 while(first != last){ 1558 while(first != last){
1421 ++it_past_newly_constructed; 1566 ++it_past_newly_constructed;
1422 } 1567 }
1423 //rollback.~insert_rollback() called in case of exception 1568 //rollback.~insert_rollback() called in case of exception
1424 } 1569 }
1425 //Fix up pointers for past-new nodes (new nodes were fixed during construction) and 1570 //Fix up pointers for past-new nodes (new nodes were fixed during construction) and
1426 //nodes before insertion position in priv_insert_forward_non_templated(...) 1571 //nodes before insertion p in priv_insert_forward_non_templated(...)
1427 index_traits_type::fix_up_pointers_from(this->index, it_past_newly_constructed); 1572 index_traits_type::fix_up_pointers_from(this->index, it_past_newly_constructed);
1428 } 1573 }
1429 return this->begin() + pos; 1574 return this->begin() + idx;
1430 } 1575 }
1431 #endif 1576 #endif
1432 1577
1433 //! <b>Effects</b>: Removes the last element from the stable_vector. 1578 //! <b>Effects</b>: Removes the last element from the stable_vector.
1434 //! 1579 //!
1435 //! <b>Throws</b>: Nothing. 1580 //! <b>Throws</b>: Nothing.
1436 //! 1581 //!
1437 //! <b>Complexity</b>: Constant time. 1582 //! <b>Complexity</b>: Constant time.
1438 void pop_back() BOOST_CONTAINER_NOEXCEPT 1583 void pop_back() BOOST_NOEXCEPT_OR_NOTHROW
1439 { this->erase(--this->cend()); } 1584 { this->erase(--this->cend()); }
1440 1585
1441 //! <b>Effects</b>: Erases the element at position pos. 1586 //! <b>Effects</b>: Erases the element at p.
1442 //! 1587 //!
1443 //! <b>Throws</b>: Nothing. 1588 //! <b>Throws</b>: Nothing.
1444 //! 1589 //!
1445 //! <b>Complexity</b>: Linear to the elements between pos and the 1590 //! <b>Complexity</b>: Linear to the elements between p and the
1446 //! last element. Constant if pos is the last element. 1591 //! last element. Constant if p is the last element.
1447 iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT 1592 iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1448 { 1593 {
1449 STABLE_VECTOR_CHECK_INVARIANT; 1594 STABLE_VECTOR_CHECK_INVARIANT;
1450 const size_type d = position - this->cbegin(); 1595 const size_type d = p - this->cbegin();
1451 index_iterator it = this->index.begin() + d; 1596 index_iterator it = this->index.begin() + d;
1452 this->priv_delete_node(position.node_pointer()); 1597 this->priv_delete_node(p.node_pointer());
1453 it = this->index.erase(it); 1598 it = this->index.erase(it);
1454 index_traits_type::fix_up_pointers_from(this->index, it); 1599 index_traits_type::fix_up_pointers_from(this->index, it);
1455 return iterator(node_ptr_traits::static_cast_from(*it)); 1600 return iterator(node_ptr_traits::static_cast_from(*it));
1456 } 1601 }
1457 1602
1458 //! <b>Effects</b>: Erases the elements pointed by [first, last). 1603 //! <b>Effects</b>: Erases the elements pointed by [first, last).
1459 //! 1604 //!
1460 //! <b>Throws</b>: Nothing. 1605 //! <b>Throws</b>: Nothing.
1461 //! 1606 //!
1462 //! <b>Complexity</b>: Linear to the distance between first and last 1607 //! <b>Complexity</b>: Linear to the distance between first and last
1463 //! plus linear to the elements between pos and the last element. 1608 //! plus linear to the elements between p and the last element.
1464 iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT 1609 iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW
1465 { 1610 {
1466 STABLE_VECTOR_CHECK_INVARIANT; 1611 STABLE_VECTOR_CHECK_INVARIANT;
1467 const const_iterator cbeg(this->cbegin()); 1612 const const_iterator cbeg(this->cbegin());
1468 const size_type d1 = static_cast<size_type>(first - cbeg), 1613 const size_type d1 = static_cast<size_type>(first - cbeg),
1469 d2 = static_cast<size_type>(last - cbeg); 1614 d2 = static_cast<size_type>(last - cbeg);
1491 //! 1636 //!
1492 //! <b>Throws</b>: Nothing. 1637 //! <b>Throws</b>: Nothing.
1493 //! 1638 //!
1494 //! <b>Complexity</b>: Constant. 1639 //! <b>Complexity</b>: Constant.
1495 void swap(stable_vector & x) 1640 void swap(stable_vector & x)
1641 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
1642 || allocator_traits_type::is_always_equal::value)
1496 { 1643 {
1497 STABLE_VECTOR_CHECK_INVARIANT; 1644 STABLE_VECTOR_CHECK_INVARIANT;
1498 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; 1645 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1499 container_detail::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag); 1646 container_detail::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag);
1500 //vector's allocator is swapped here 1647 //vector's allocator is swapped here
1505 //! <b>Effects</b>: Erases all the elements of the stable_vector. 1652 //! <b>Effects</b>: Erases all the elements of the stable_vector.
1506 //! 1653 //!
1507 //! <b>Throws</b>: Nothing. 1654 //! <b>Throws</b>: Nothing.
1508 //! 1655 //!
1509 //! <b>Complexity</b>: Linear to the number of elements in the stable_vector. 1656 //! <b>Complexity</b>: Linear to the number of elements in the stable_vector.
1510 void clear() BOOST_CONTAINER_NOEXCEPT 1657 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1511 { this->erase(this->cbegin(),this->cend()); } 1658 { this->erase(this->cbegin(),this->cend()); }
1512 1659
1513 /// @cond 1660 //! <b>Effects</b>: Returns true if x and y are equal
1514 1661 //!
1662 //! <b>Complexity</b>: Linear to the number of elements in the container.
1663 friend bool operator==(const stable_vector& x, const stable_vector& y)
1664 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1665
1666 //! <b>Effects</b>: Returns true if x and y are unequal
1667 //!
1668 //! <b>Complexity</b>: Linear to the number of elements in the container.
1669 friend bool operator!=(const stable_vector& x, const stable_vector& y)
1670 { return !(x == y); }
1671
1672 //! <b>Effects</b>: Returns true if x is less than y
1673 //!
1674 //! <b>Complexity</b>: Linear to the number of elements in the container.
1675 friend bool operator<(const stable_vector& x, const stable_vector& y)
1676 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1677
1678 //! <b>Effects</b>: Returns true if x is greater than y
1679 //!
1680 //! <b>Complexity</b>: Linear to the number of elements in the container.
1681 friend bool operator>(const stable_vector& x, const stable_vector& y)
1682 { return y < x; }
1683
1684 //! <b>Effects</b>: Returns true if x is equal or less than y
1685 //!
1686 //! <b>Complexity</b>: Linear to the number of elements in the container.
1687 friend bool operator<=(const stable_vector& x, const stable_vector& y)
1688 { return !(y < x); }
1689
1690 //! <b>Effects</b>: Returns true if x is equal or greater than y
1691 //!
1692 //! <b>Complexity</b>: Linear to the number of elements in the container.
1693 friend bool operator>=(const stable_vector& x, const stable_vector& y)
1694 { return !(x < y); }
1695
1696 //! <b>Effects</b>: x.swap(y)
1697 //!
1698 //! <b>Complexity</b>: Constant.
1699 friend void swap(stable_vector& x, stable_vector& y)
1700 { x.swap(y); }
1701
1702 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1515 private: 1703 private:
1704
1705 size_type priv_index_of(node_ptr p) const
1706 {
1707 //Check range
1708 BOOST_ASSERT(this->index.empty() || (this->index.data() <= p->up));
1709 BOOST_ASSERT(this->index.empty() || p->up <= (this->index.data() + this->index.size()));
1710 return this->index.empty() ? 0 : p->up - this->index.data();
1711 }
1516 1712
1517 class insert_rollback 1713 class insert_rollback
1518 { 1714 {
1519 public: 1715 public:
1520 1716
1557 private: 1753 private:
1558 stable_vector &m_sv; 1754 stable_vector &m_sv;
1559 node_ptr m_p; 1755 node_ptr m_p;
1560 }; 1756 };
1561 1757
1562 index_iterator priv_insert_forward_non_templated(size_type pos, size_type num_new) 1758 index_iterator priv_insert_forward_non_templated(size_type idx, size_type num_new)
1563 { 1759 {
1564 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, num_new); 1760 index_traits_type::initialize_end_node(this->index, this->internal_data.end_node, num_new);
1565 1761
1566 //Now try to fill the pool with new data 1762 //Now try to fill the pool with new data
1567 if(this->internal_data.pool_size < num_new){ 1763 if(this->internal_data.pool_size < num_new){
1568 this->priv_increase_pool(num_new - this->internal_data.pool_size); 1764 this->priv_increase_pool(num_new - this->internal_data.pool_size);
1569 } 1765 }
1570 1766
1571 //Now try to make room in the vector 1767 //Now try to make room in the vector
1572 const node_base_ptr_ptr old_buffer = this->index.data(); 1768 const node_base_ptr_ptr old_buffer = this->index.data();
1573 this->index.insert(this->index.begin() + pos, num_new, node_ptr()); 1769 this->index.insert(this->index.begin() + idx, num_new, node_ptr());
1574 bool new_buffer = this->index.data() != old_buffer; 1770 bool new_buffer = this->index.data() != old_buffer;
1575 1771
1576 //Fix the pointers for the newly allocated buffer 1772 //Fix the pointers for the newly allocated buffer
1577 const index_iterator index_beg = this->index.begin(); 1773 const index_iterator index_beg = this->index.begin();
1578 if(new_buffer){ 1774 if(new_buffer){
1579 index_traits_type::fix_up_pointers(index_beg, index_beg + pos); 1775 index_traits_type::fix_up_pointers(index_beg, index_beg + idx);
1580 } 1776 }
1581 return index_beg + pos; 1777 return index_beg + idx;
1582 } 1778 }
1583 1779
1584 bool priv_capacity_bigger_than_size() const 1780 bool priv_capacity_bigger_than_size() const
1585 { 1781 {
1586 return this->index.capacity() > this->index.size() && 1782 return this->index.capacity() > this->index.size() &&
1607 else{ 1803 else{
1608 this->insert(this->cend(), ::boost::forward<U>(x)); 1804 this->insert(this->cend(), ::boost::forward<U>(x));
1609 } 1805 }
1610 } 1806 }
1611 1807
1612 iterator priv_insert(const_iterator position, const value_type &t) 1808 iterator priv_insert(const_iterator p, const value_type &t)
1613 { 1809 {
1614 typedef constant_iterator<value_type, difference_type> cvalue_iterator; 1810 typedef constant_iterator<value_type, difference_type> cvalue_iterator;
1615 return this->insert(position, cvalue_iterator(t, 1), cvalue_iterator()); 1811 return this->insert(p, cvalue_iterator(t, 1), cvalue_iterator());
1616 } 1812 }
1617 1813
1618 iterator priv_insert(const_iterator position, BOOST_RV_REF(T) x) 1814 iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x)
1619 { 1815 {
1620 typedef repeat_iterator<T, difference_type> repeat_it; 1816 typedef repeat_iterator<T, difference_type> repeat_it;
1621 typedef boost::move_iterator<repeat_it> repeat_move_it; 1817 typedef boost::move_iterator<repeat_it> repeat_move_it;
1622 //Just call more general insert(pos, size, value) and return iterator 1818 //Just call more general insert(p, size, value) and return iterator
1623 return this->insert(position, repeat_move_it(repeat_it(x, 1)), repeat_move_it(repeat_it())); 1819 return this->insert(p, repeat_move_it(repeat_it(x, 1)), repeat_move_it(repeat_it()));
1624 } 1820 }
1625 1821
1626 void priv_clear_pool() 1822 void priv_clear_pool()
1627 { 1823 {
1628 if(!this->index.empty() && this->index.back()){ 1824 if(!this->index.empty() && this->index.back()){
1710 pool_last_ref = data.second; 1906 pool_last_ref = data.second;
1711 } 1907 }
1712 return ret; 1908 return ret;
1713 } 1909 }
1714 1910
1715 node_ptr priv_get_end_node() const 1911 node_base_ptr priv_get_end_node() const
1716 { 1912 { return node_base_ptr_traits::pointer_to(const_cast<node_base_type&>(this->internal_data.end_node)); }
1717 return node_ptr_traits::pointer_to
1718 (static_cast<node_type&>(const_cast<node_base_type&>(this->internal_data.end_node)));
1719 }
1720 1913
1721 void priv_destroy_node(const node_type &n) 1914 void priv_destroy_node(const node_type &n)
1722 { 1915 {
1723 allocator_traits<node_allocator_type>:: 1916 allocator_traits<node_allocator_type>::
1724 destroy(this->priv_node_alloc(), container_detail::addressof(n.value)); 1917 destroy(this->priv_node_alloc(), container_detail::addressof(n.value));
1738 boost::container::construct_in_place 1931 boost::container::construct_in_place
1739 ( this->priv_node_alloc() 1932 ( this->priv_node_alloc()
1740 , container_detail::addressof(p->value) 1933 , container_detail::addressof(p->value)
1741 , it); 1934 , it);
1742 //This does not throw 1935 //This does not throw
1743 ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p))) 1936 ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t())
1744 node_base_type(index_traits_type::ptr_to_node_base_ptr(*up_index)); 1937 node_base_type(index_traits_type::ptr_to_node_base_ptr(*up_index));
1745 } 1938 }
1746 1939
1747 template<class ValueConvertible> 1940 template<class ValueConvertible>
1748 void priv_build_node_from_convertible(const node_ptr &p, BOOST_FWD_REF(ValueConvertible) value_convertible) 1941 void priv_build_node_from_convertible(const node_ptr &p, BOOST_FWD_REF(ValueConvertible) value_convertible)
1751 boost::container::allocator_traits<node_allocator_type>::construct 1944 boost::container::allocator_traits<node_allocator_type>::construct
1752 ( this->priv_node_alloc() 1945 ( this->priv_node_alloc()
1753 , container_detail::addressof(p->value) 1946 , container_detail::addressof(p->value)
1754 , ::boost::forward<ValueConvertible>(value_convertible)); 1947 , ::boost::forward<ValueConvertible>(value_convertible));
1755 //This does not throw 1948 //This does not throw
1756 ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p))) node_base_type; 1949 ::new(static_cast<node_base_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) node_base_type;
1757 } 1950 }
1758 1951
1759 void priv_swap_members(stable_vector &x) 1952 void priv_swap_members(stable_vector &x)
1760 { 1953 {
1761 boost::container::swap_dispatch(this->internal_data.pool_size, x.internal_data.pool_size); 1954 boost::adl_move_swap(this->internal_data.pool_size, x.internal_data.pool_size);
1762 index_traits_type::readjust_end_node(this->index, this->internal_data.end_node); 1955 index_traits_type::readjust_end_node(this->index, this->internal_data.end_node);
1763 index_traits_type::readjust_end_node(x.index, x.internal_data.end_node); 1956 index_traits_type::readjust_end_node(x.index, x.internal_data.end_node);
1764 } 1957 }
1765 1958
1766 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING) 1959 #if defined(STABLE_VECTOR_ENABLE_INVARIANT_CHECKING)
1834 2027
1835 node_allocator_type &priv_node_alloc() { return internal_data; } 2028 node_allocator_type &priv_node_alloc() { return internal_data; }
1836 const node_allocator_type &priv_node_alloc() const { return internal_data; } 2029 const node_allocator_type &priv_node_alloc() const { return internal_data; }
1837 2030
1838 index_type index; 2031 index_type index;
1839 /// @endcond 2032 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1840 }; 2033 };
1841 2034
1842 template <typename T,typename Allocator> 2035 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1843 bool operator==(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y)
1844 {
1845 return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1846 }
1847
1848 template <typename T,typename Allocator>
1849 bool operator< (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y)
1850 {
1851 return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1852 }
1853
1854 template <typename T,typename Allocator>
1855 bool operator!=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y)
1856 {
1857 return !(x==y);
1858 }
1859
1860 template <typename T,typename Allocator>
1861 bool operator> (const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y)
1862 {
1863 return y<x;
1864 }
1865
1866 template <typename T,typename Allocator>
1867 bool operator>=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y)
1868 {
1869 return !(x<y);
1870 }
1871
1872 template <typename T,typename Allocator>
1873 bool operator<=(const stable_vector<T,Allocator>& x,const stable_vector<T,Allocator>& y)
1874 {
1875 return !(x>y);
1876 }
1877
1878 // specialized algorithms:
1879
1880 template <typename T, typename Allocator>
1881 void swap(stable_vector<T,Allocator>& x,stable_vector<T,Allocator>& y)
1882 {
1883 x.swap(y);
1884 }
1885
1886 /// @cond
1887 2036
1888 #undef STABLE_VECTOR_CHECK_INVARIANT 2037 #undef STABLE_VECTOR_CHECK_INVARIANT
1889 2038
1890 /// @endcond 2039 } //namespace container {
1891
1892 /*
1893 2040
1894 //!has_trivial_destructor_after_move<> == true_type 2041 //!has_trivial_destructor_after_move<> == true_type
1895 //!specialization for optimizations 2042 //!specialization for optimizations
1896 template <class T, class Allocator> 2043 template <class T, class Allocator>
1897 struct has_trivial_destructor_after_move<boost::container::stable_vector<T, Allocator> > 2044 struct has_trivial_destructor_after_move<boost::container::stable_vector<T, Allocator> >
1898 : public has_trivial_destructor_after_move<Allocator>::value 2045 {
1899 {}; 2046 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1900 2047 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1901 */ 2048 ::boost::has_trivial_destructor_after_move<pointer>::value;
1902 2049 };
1903 }} 2050
2051 namespace container {
2052
2053 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2054
2055 }} //namespace boost{ namespace container {
1904 2056
1905 #include <boost/container/detail/config_end.hpp> 2057 #include <boost/container/detail/config_end.hpp>
1906 2058
1907 #endif //BOOST_CONTAINER_STABLE_VECTOR_HPP 2059 #endif //BOOST_CONTAINER_STABLE_VECTOR_HPP