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