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