File indexing completed on 2025-07-01 08:10:21
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012 #ifndef BOOST_CONTAINER_DEVECTOR_HPP
0013 #define BOOST_CONTAINER_DEVECTOR_HPP
0014
0015 #include <boost/container/detail/config_begin.hpp>
0016 #include <boost/container/detail/workaround.hpp>
0017
0018 #include <cstring> // memcpy
0019
0020 #include <boost/assert.hpp>
0021
0022 #include <boost/container/detail/copy_move_algo.hpp>
0023 #include <boost/container/new_allocator.hpp> //new_allocator
0024 #include <boost/container/allocator_traits.hpp> //allocator_traits
0025 #include <boost/container/detail/algorithm.hpp> //equal()
0026 #include <boost/container/throw_exception.hpp>
0027 #include <boost/container/options.hpp>
0028
0029 #include <boost/container/detail/guards_dended.hpp>
0030 #include <boost/container/detail/iterator.hpp>
0031 #include <boost/container/detail/iterators.hpp>
0032 #include <boost/container/detail/destroyers.hpp>
0033 #include <boost/container/detail/min_max.hpp>
0034 #include <boost/container/detail/next_capacity.hpp>
0035 #include <boost/container/detail/alloc_helpers.hpp>
0036 #include <boost/container/detail/advanced_insert_int.hpp>
0037
0038
0039 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0040 #include <boost/move/detail/fwd_macros.hpp>
0041 #endif
0042 #include <boost/move/detail/move_helpers.hpp>
0043 #include <boost/move/adl_move_swap.hpp>
0044 #include <boost/move/iterator.hpp>
0045 #include <boost/move/traits.hpp>
0046 #include <boost/move/utility_core.hpp>
0047 #include <boost/move/detail/to_raw_pointer.hpp>
0048 #include <boost/move/algo/detail/merge.hpp>
0049
0050
0051 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0052 #include <initializer_list> //for std::initializer_list
0053 #endif
0054
0055 namespace boost {
0056 namespace container {
0057
0058 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0059
0060 struct growth_factor_60;
0061
0062 template<class Options, class AllocatorSizeType>
0063 struct get_devector_opt
0064 {
0065 typedef devector_opt< typename default_if_void<typename Options::growth_factor_type, growth_factor_60>::type
0066 , typename default_if_void<typename Options::stored_size_type, AllocatorSizeType>::type
0067 , default_if_zero<Options::free_fraction, relocate_on_90::value>::value
0068 > type;
0069 };
0070
0071 template<class AllocatorSizeType>
0072 struct get_devector_opt<void, AllocatorSizeType>
0073 {
0074 typedef devector_opt< growth_factor_60, AllocatorSizeType, relocate_on_90::value> type;
0075 };
0076
0077 #endif
0078
0079 struct reserve_only_tag_t {};
0080 struct reserve_uninitialized_t {};
0081 struct review_implementation_t {};
0082
0083
0084
0085
0086
0087
0088
0089
0090
0091
0092
0093
0094
0095
0096
0097
0098
0099
0100
0101
0102
0103
0104
0105
0106
0107
0108
0109
0110
0111
0112
0113
0114
0115
0116
0117
0118
0119
0120
0121
0122
0123
0124
0125
0126
0127
0128
0129
0130
0131
0132
0133
0134
0135
0136
0137
0138
0139
0140 template < typename T, class A BOOST_CONTAINER_DOCONLY(= void), class Options BOOST_CONTAINER_DOCONLY(= void)>
0141 class devector
0142 {
0143 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0144 typedef boost::container::allocator_traits
0145 <typename real_allocator<T, A>::type> allocator_traits_type;
0146 typedef typename allocator_traits_type::size_type alloc_size_type;
0147 typedef typename get_devector_opt<Options, alloc_size_type>::type options_type;
0148 typedef typename options_type::growth_factor_type growth_factor_type;
0149 typedef typename options_type::stored_size_type stored_size_type;
0150 BOOST_STATIC_CONSTEXPR std::size_t devector_min_free_fraction =
0151 options_type::free_fraction;
0152
0153 #endif
0154
0155 public:
0156
0157 typedef T value_type;
0158 typedef BOOST_CONTAINER_IMPDEF
0159 (typename real_allocator<T BOOST_MOVE_I A>::type) allocator_type;
0160 typedef allocator_type stored_allocator_type;
0161 typedef typename allocator_traits<allocator_type>::pointer pointer;
0162 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
0163 typedef typename allocator_traits<allocator_type>::reference reference;
0164 typedef typename allocator_traits<allocator_type>::const_reference const_reference;
0165 typedef typename allocator_traits<allocator_type>::size_type size_type;
0166 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
0167 typedef pointer iterator;
0168 typedef const_pointer const_iterator;
0169 typedef BOOST_CONTAINER_IMPDEF
0170 (boost::container::reverse_iterator<iterator>) reverse_iterator;
0171 typedef BOOST_CONTAINER_IMPDEF
0172 (boost::container::reverse_iterator<const_iterator>) const_reverse_iterator;
0173
0174 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0175 private:
0176 BOOST_COPYABLE_AND_MOVABLE(devector)
0177
0178
0179 typedef typename detail::allocation_guard<allocator_type> allocation_guard;
0180
0181
0182 typedef constant_iterator<T> cvalue_iterator;
0183
0184 static size_type to_internal_capacity(size_type desired_capacity)
0185 {
0186 const size_type rounder = devector_min_free_fraction - 2u;
0187 const size_type divisor = devector_min_free_fraction - 1u;
0188 size_type const nc = ((desired_capacity + rounder) / divisor) * devector_min_free_fraction;
0189 BOOST_ASSERT(desired_capacity <= (nc - nc / devector_min_free_fraction));
0190 return nc;
0191 }
0192
0193 #endif
0194
0195
0196 public:
0197
0198
0199
0200
0201
0202
0203
0204
0205
0206
0207 devector() BOOST_NOEXCEPT
0208 : m_()
0209 {}
0210
0211
0212
0213
0214
0215
0216
0217
0218
0219 explicit devector(const allocator_type& allocator) BOOST_NOEXCEPT
0220 : m_(allocator)
0221 {}
0222
0223
0224
0225
0226
0227
0228
0229
0230
0231
0232
0233 devector(size_type n, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
0234 : m_(reserve_only_tag_t(), allocator, to_internal_capacity(n))
0235 {}
0236
0237
0238
0239
0240
0241
0242
0243
0244
0245
0246
0247
0248
0249 devector(size_type front_free_cap, size_type back_free_cap, reserve_only_tag_t, const allocator_type& allocator = allocator_type())
0250 : m_(reserve_only_tag_t(), allocator, front_free_cap, back_free_cap)
0251 {}
0252
0253
0254
0255
0256
0257
0258
0259
0260
0261
0262
0263
0264
0265
0266 explicit devector(size_type n, const allocator_type& allocator = allocator_type())
0267 : m_(reserve_uninitialized_t(), allocator, n)
0268 {
0269 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
0270 boost::container::uninitialized_value_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
0271 buffer_guard.release();
0272 BOOST_ASSERT(invariants_ok());
0273 }
0274
0275
0276
0277
0278
0279
0280
0281
0282
0283
0284
0285
0286 explicit devector(size_type n, default_init_t, const allocator_type& allocator = allocator_type())
0287 : m_(reserve_uninitialized_t(), allocator, n)
0288 {
0289 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
0290 boost::container::uninitialized_default_init_alloc_n(get_allocator_ref(), n, this->priv_raw_begin());
0291 buffer_guard.release();
0292 BOOST_ASSERT(invariants_ok());
0293 }
0294
0295
0296
0297
0298
0299
0300
0301
0302
0303
0304
0305
0306
0307
0308 devector(size_type n, const T& value, const allocator_type& allocator = allocator_type())
0309 : m_(reserve_uninitialized_t(), allocator, n)
0310 {
0311 construct_from_range(cvalue_iterator(value, n), cvalue_iterator());
0312 BOOST_ASSERT(invariants_ok());
0313 }
0314
0315
0316
0317
0318
0319
0320
0321
0322
0323
0324
0325
0326
0327
0328
0329
0330
0331
0332
0333
0334
0335
0336
0337 template <class InputIterator>
0338 devector(InputIterator first, InputIterator last, const allocator_type& allocator = allocator_type()
0339
0340 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0341 < void
0342 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
0343 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
0344 >::type * = 0)
0345 )
0346 : m_(allocator)
0347 {
0348 BOOST_CONTAINER_TRY{
0349 while (first != last) {
0350 this->emplace_back(*first++);
0351 }
0352 BOOST_ASSERT(invariants_ok());
0353 }
0354 BOOST_CONTAINER_CATCH(...){
0355 this->destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
0356 this->deallocate_buffer();
0357 }
0358 BOOST_CONTAINER_CATCH_END
0359 }
0360
0361 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0362
0363 template <class ForwardIterator>
0364 devector(ForwardIterator first, ForwardIterator last, const allocator_type& allocator = allocator_type()
0365
0366 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0367 < void
0368 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
0369 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
0370 >::type * = 0)
0371 )
0372 : m_(reserve_uninitialized_t(), allocator, boost::container::iterator_udistance(first, last))
0373 {
0374 this->construct_from_range(first, last);
0375 BOOST_ASSERT(invariants_ok());
0376 }
0377
0378 #endif
0379
0380
0381
0382
0383
0384
0385
0386
0387
0388
0389
0390
0391
0392
0393 devector(const devector& x)
0394 : m_(reserve_uninitialized_t(), allocator_traits_type::select_on_container_copy_construction(x.get_allocator_ref()), x.size())
0395 {
0396 this->construct_from_range(x.begin(), x.end());
0397 BOOST_ASSERT(invariants_ok());
0398 }
0399
0400
0401
0402
0403
0404
0405
0406
0407
0408
0409
0410
0411
0412
0413 devector(const devector& x, const allocator_type& allocator)
0414 : m_(reserve_uninitialized_t(), allocator, x.size())
0415 {
0416 this->construct_from_range(x.begin(), x.end());
0417 BOOST_ASSERT(invariants_ok());
0418 }
0419
0420
0421
0422
0423
0424
0425
0426
0427
0428
0429
0430
0431
0432 devector(BOOST_RV_REF(devector) rhs) BOOST_NOEXCEPT_OR_NOTHROW
0433 : m_(::boost::move(rhs.m_))
0434 {
0435 BOOST_ASSERT( invariants_ok());
0436 BOOST_ASSERT(rhs.invariants_ok());
0437 }
0438
0439
0440
0441
0442
0443
0444
0445
0446
0447
0448
0449
0450
0451 devector(BOOST_RV_REF(devector) rhs, const allocator_type& allocator)
0452 : m_(review_implementation_t(), allocator, rhs.m_.buffer, rhs.m_.front_idx, rhs.m_.back_idx, rhs.m_.capacity)
0453 {
0454
0455
0456 rhs.m_.capacity = 0u;
0457 rhs.m_.buffer = pointer();
0458 rhs.m_.front_idx = 0;
0459 rhs.m_.back_idx = 0;
0460 BOOST_ASSERT( invariants_ok());
0461 BOOST_ASSERT(rhs.invariants_ok());
0462 }
0463
0464 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0465
0466
0467
0468 devector(const std::initializer_list<T>& il, const allocator_type& allocator = allocator_type())
0469 : m_(reserve_uninitialized_t(), allocator, il.size())
0470 {
0471 this->construct_from_range(il.begin(), il.end());
0472 BOOST_ASSERT(invariants_ok());
0473 }
0474 #endif
0475
0476
0477
0478
0479
0480
0481
0482 ~devector() BOOST_NOEXCEPT
0483 {
0484 destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
0485 deallocate_buffer();
0486 }
0487
0488
0489
0490
0491
0492
0493
0494
0495
0496
0497
0498
0499
0500
0501
0502
0503
0504
0505
0506
0507
0508
0509
0510 inline devector& operator=(BOOST_COPY_ASSIGN_REF(devector) rhs)
0511 {
0512 const devector &x = rhs;
0513 if (this == &x) { return *this; }
0514
0515 const bool do_propagate = allocator_traits_type::propagate_on_container_copy_assignment::value;
0516 BOOST_IF_CONSTEXPR(do_propagate)
0517 {
0518 allocator_type &this_alloc = this->get_allocator_ref();
0519 const allocator_type &other_alloc = x.get_allocator_ref();
0520 if (this_alloc != other_alloc)
0521 {
0522
0523 this->clear();
0524 this->deallocate_buffer();
0525 m_.capacity = 0u;
0526 m_.buffer = pointer();
0527 }
0528 dtl::bool_<do_propagate> flag;
0529 dtl::assign_alloc(this_alloc, other_alloc, flag);
0530 }
0531
0532 size_type n = x.size();
0533 if (m_.capacity >= n)
0534 {
0535 this->overwrite_buffer(x.begin(), x.end());
0536 }
0537 else
0538 {
0539 this->allocate_and_copy_range(x.begin(), x.end());
0540 }
0541
0542 BOOST_ASSERT(invariants_ok());
0543
0544 return *this;
0545 }
0546
0547
0548
0549
0550
0551
0552
0553
0554
0555
0556
0557
0558
0559
0560
0561
0562
0563
0564
0565 devector& operator=(BOOST_RV_REF(devector) x)
0566 BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value
0567 || allocator_traits_type::is_always_equal::value)
0568 {
0569 if (BOOST_LIKELY(this != &x)) {
0570
0571
0572 const bool can_steal_resources_alloc
0573 = allocator_traits_type::propagate_on_container_move_assignment::value
0574 || allocator_traits_type::is_always_equal::value;
0575 dtl::bool_<can_steal_resources_alloc> flag;
0576 this->priv_move_assign(boost::move(x), flag);
0577 }
0578 BOOST_ASSERT(invariants_ok());
0579 return *this;
0580 }
0581
0582 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0583
0584
0585
0586
0587
0588
0589
0590
0591
0592
0593
0594
0595
0596
0597
0598
0599
0600
0601
0602 inline devector& operator=(std::initializer_list<T> il)
0603 {
0604 this->assign(il.begin(), il.end());
0605 return *this;
0606 }
0607 #endif
0608
0609
0610
0611
0612
0613
0614
0615
0616
0617
0618
0619
0620
0621
0622
0623
0624
0625
0626
0627
0628
0629
0630
0631
0632
0633
0634 template <class InputIterator>
0635 void assign(InputIterator first, InputIterator last
0636
0637 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0638 < void
0639 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
0640 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
0641 >::type * = 0)
0642 )
0643 {
0644 first = overwrite_buffer_impl(first, last, dtl::false_());
0645 while (first != last)
0646 {
0647 this->emplace_back(*first++);
0648 }
0649 }
0650
0651 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0652
0653 template <class ForwardIterator>
0654 void assign(ForwardIterator first, ForwardIterator last
0655
0656 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
0657 < void
0658 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
0659 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
0660 >::type * = 0)
0661 )
0662 {
0663 const size_type n = boost::container::iterator_udistance(first, last);
0664
0665 if (m_.capacity >= n)
0666 {
0667 overwrite_buffer(first, last);
0668 }
0669 else
0670 {
0671 allocate_and_copy_range(first, last);
0672 }
0673
0674 BOOST_ASSERT(invariants_ok());
0675 }
0676
0677 #endif
0678
0679
0680
0681
0682
0683
0684
0685
0686
0687
0688
0689
0690
0691
0692
0693
0694
0695
0696
0697
0698
0699 inline void assign(size_type n, const T& u)
0700 {
0701 cvalue_iterator first(u, n);
0702 cvalue_iterator last;
0703 this->assign(first, last);
0704 }
0705
0706 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0707
0708 inline void assign(std::initializer_list<T> il)
0709 {
0710 this->assign(il.begin(), il.end());
0711 }
0712 #endif
0713
0714
0715
0716
0717
0718
0719 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0720 allocator_type get_allocator() const BOOST_NOEXCEPT
0721 {
0722 return static_cast<const allocator_type&>(m_);
0723 }
0724
0725 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0726 const allocator_type &get_stored_allocator() const BOOST_NOEXCEPT
0727 {
0728 return static_cast<const allocator_type&>(m_);
0729 }
0730
0731 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0732 allocator_type &get_stored_allocator() BOOST_NOEXCEPT
0733 {
0734 return static_cast<allocator_type&>(m_);
0735 }
0736
0737
0738
0739
0740
0741
0742
0743
0744
0745 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0746 iterator begin() BOOST_NOEXCEPT
0747 {
0748 return m_.buffer + m_.front_idx;
0749 }
0750
0751
0752
0753
0754
0755
0756
0757 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0758 const_iterator begin() const BOOST_NOEXCEPT
0759 {
0760 return m_.buffer + m_.front_idx;
0761 }
0762
0763
0764
0765
0766
0767
0768 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0769 iterator end() BOOST_NOEXCEPT
0770 {
0771 return m_.buffer + m_.back_idx;
0772 }
0773
0774
0775
0776
0777
0778
0779 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0780 const_iterator end() const BOOST_NOEXCEPT
0781 {
0782 return m_.buffer + m_.back_idx;
0783 }
0784
0785
0786
0787
0788
0789
0790
0791 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0792 reverse_iterator rbegin() BOOST_NOEXCEPT
0793 {
0794 return reverse_iterator(m_.buffer + m_.back_idx);
0795 }
0796
0797
0798
0799
0800
0801
0802
0803
0804 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0805 const_reverse_iterator rbegin() const BOOST_NOEXCEPT
0806 {
0807 return const_reverse_iterator(m_.buffer + m_.back_idx);
0808 }
0809
0810
0811
0812
0813
0814
0815
0816 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0817 reverse_iterator rend() BOOST_NOEXCEPT
0818 {
0819 return reverse_iterator(m_.buffer + m_.front_idx);
0820 }
0821
0822
0823
0824
0825
0826
0827
0828 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0829 const_reverse_iterator rend() const BOOST_NOEXCEPT
0830 {
0831 return const_reverse_iterator(m_.buffer + m_.front_idx);
0832 }
0833
0834
0835
0836
0837
0838
0839
0840 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0841 const_iterator cbegin() const BOOST_NOEXCEPT
0842 {
0843 return m_.buffer + m_.front_idx;
0844 }
0845
0846
0847
0848
0849
0850
0851 const_iterator cend() const BOOST_NOEXCEPT
0852 {
0853 return m_.buffer + m_.back_idx;
0854 }
0855
0856
0857
0858
0859
0860
0861
0862
0863 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0864 const_reverse_iterator crbegin() const BOOST_NOEXCEPT
0865 {
0866 return const_reverse_iterator(m_.buffer + m_.back_idx);
0867 }
0868
0869
0870
0871
0872
0873
0874
0875 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0876 const_reverse_iterator crend() const BOOST_NOEXCEPT
0877 {
0878 return const_reverse_iterator(m_.buffer + m_.front_idx);
0879 }
0880
0881
0882
0883
0884
0885
0886
0887
0888 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0889 bool empty() const BOOST_NOEXCEPT
0890 {
0891 return m_.front_idx == m_.back_idx;
0892 }
0893
0894
0895
0896
0897
0898
0899 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0900 size_type size() const BOOST_NOEXCEPT
0901 {
0902 return size_type(m_.back_idx - m_.front_idx);
0903 }
0904
0905
0906
0907
0908
0909
0910 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0911 size_type max_size() const BOOST_NOEXCEPT
0912 {
0913 size_type alloc_max = allocator_traits_type::max_size(get_allocator_ref());
0914 size_type size_type_max = (size_type)-1;
0915 return (alloc_max <= size_type_max) ? size_type(alloc_max) : size_type_max;
0916 }
0917
0918
0919
0920
0921
0922
0923
0924
0925
0926
0927 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0928 size_type capacity() const BOOST_NOEXCEPT
0929 {
0930 size_type const cap_reserve = m_.capacity/devector_min_free_fraction;
0931 return m_.capacity > cap_reserve ? (m_.capacity - cap_reserve) : 0u;
0932 }
0933
0934
0935
0936
0937
0938
0939
0940 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0941 size_type front_free_capacity() const BOOST_NOEXCEPT
0942 {
0943 return m_.front_idx;
0944 }
0945
0946
0947
0948
0949
0950
0951
0952 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
0953 size_type back_free_capacity() const BOOST_NOEXCEPT
0954 {
0955 return size_type(m_.capacity - m_.back_idx);
0956 }
0957
0958
0959
0960
0961
0962
0963
0964
0965
0966
0967
0968
0969
0970
0971
0972
0973
0974
0975 inline void resize(size_type sz)
0976 {
0977 this->resize_back(sz);
0978 }
0979
0980
0981
0982
0983
0984 inline void resize(size_type sz, default_init_t)
0985 {
0986 this->resize_back(sz, default_init);
0987 }
0988
0989
0990
0991
0992
0993
0994
0995
0996
0997
0998
0999
1000
1001
1002
1003
1004
1005 inline void resize(size_type sz, const T& c)
1006 {
1007 this->resize_back(sz, c);
1008 }
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028 inline void resize_front(size_type sz)
1029 {
1030 resize_front_impl(sz);
1031 BOOST_ASSERT(invariants_ok());
1032 }
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051 inline void resize_front(size_type sz, default_init_t)
1052 {
1053 resize_front_impl(sz, default_init);
1054 BOOST_ASSERT(invariants_ok());
1055 }
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074 inline void resize_front(size_type sz, const T& c)
1075 {
1076 resize_front_impl(sz, c);
1077 BOOST_ASSERT(invariants_ok());
1078 }
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098 inline void resize_back(size_type sz)
1099 {
1100 resize_back_impl(sz);
1101 BOOST_ASSERT(invariants_ok());
1102 }
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121 inline void resize_back(size_type sz, default_init_t)
1122 {
1123 resize_back_impl(sz, default_init);
1124 BOOST_ASSERT(invariants_ok());
1125 }
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143 inline void resize_back(size_type sz, const T& c)
1144 {
1145 resize_back_impl(sz, c);
1146 BOOST_ASSERT(invariants_ok());
1147 }
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165 inline void reserve(size_type new_capacity)
1166 {
1167 if (this->capacity() < new_capacity) {
1168 const size_type rounder = devector_min_free_fraction - 2u;
1169 const size_type divisor = devector_min_free_fraction - 1u;
1170 size_type const nc = ((new_capacity + rounder)/divisor)*devector_min_free_fraction;
1171 BOOST_ASSERT(new_capacity <= (nc - nc / devector_min_free_fraction));
1172 size_type const sz = this->size();
1173 reallocate_at(nc, (nc-sz)/2u);
1174 }
1175 BOOST_ASSERT(invariants_ok());
1176 }
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194 inline void reserve_front(size_type new_capacity)
1195 {
1196 if (front_capacity() >= new_capacity) { return; }
1197
1198 reallocate_at(new_capacity + back_free_capacity(), new_capacity - size());
1199
1200 BOOST_ASSERT(invariants_ok());
1201 }
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219 inline void reserve_back(size_type new_capacity)
1220 {
1221 if (back_capacity() >= new_capacity) { return; }
1222
1223 reallocate_at(new_capacity + front_free_capacity(), m_.front_idx);
1224
1225 BOOST_ASSERT(invariants_ok());
1226 }
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240 inline void shrink_to_fit()
1241 {
1242 if(this->front_capacity() || this->back_capacity())
1243 this->reallocate_at(size(), 0);
1244 }
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1256 reference operator[](size_type n) BOOST_NOEXCEPT
1257 {
1258 BOOST_ASSERT(n < size());
1259 return m_.buffer[m_.front_idx + n];
1260 }
1261
1262
1263
1264
1265
1266
1267
1268
1269 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1270 const_reference operator[](size_type n) const BOOST_NOEXCEPT
1271 {
1272 BOOST_ASSERT(n < size());
1273 return m_.buffer[m_.front_idx + n];
1274 }
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1288 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1289 {
1290 BOOST_ASSERT(n <= size());
1291 return iterator(m_.buffer + (m_.front_idx + n));
1292 }
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1306 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1307 {
1308 BOOST_ASSERT(n <= size());
1309 return const_iterator(m_.buffer + (m_.front_idx + n));
1310 }
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1323 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1324 {
1325 BOOST_ASSERT(p >= begin());
1326 BOOST_ASSERT(p <= end());
1327 return static_cast<size_type>(p - this->begin());
1328 }
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1341 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1342 {
1343 BOOST_ASSERT(p >= cbegin());
1344 BOOST_ASSERT(p <= cend());
1345 return static_cast<size_type>(p - this->cbegin());
1346 }
1347
1348
1349
1350
1351
1352
1353
1354
1355 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1356 reference at(size_type n)
1357 {
1358 if (size() <= n)
1359 throw_out_of_range("devector::at out of range");
1360 return (*this)[n];
1361 }
1362
1363
1364
1365
1366
1367
1368
1369
1370 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1371 const_reference at(size_type n) const
1372 {
1373 if (size() <= n)
1374 throw_out_of_range("devector::at out of range");
1375 return (*this)[n];
1376 }
1377
1378
1379
1380
1381
1382
1383
1384
1385 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1386 reference front() BOOST_NOEXCEPT
1387 {
1388 BOOST_ASSERT(!empty());
1389
1390 return m_.buffer[m_.front_idx];
1391 }
1392
1393
1394
1395
1396
1397
1398
1399
1400 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1401 const_reference front() const BOOST_NOEXCEPT
1402 {
1403 BOOST_ASSERT(!empty());
1404
1405 return m_.buffer[m_.front_idx];
1406 }
1407
1408
1409
1410
1411
1412
1413
1414
1415 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1416 reference back() BOOST_NOEXCEPT
1417 {
1418 BOOST_ASSERT(!empty());
1419
1420 return m_.buffer[m_.back_idx - 1u];
1421 }
1422
1423
1424
1425
1426
1427
1428
1429
1430 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1431 const_reference back() const BOOST_NOEXCEPT
1432 {
1433 BOOST_ASSERT(!empty());
1434
1435 return m_.buffer[m_.back_idx - 1u];
1436 }
1437
1438
1439
1440
1441
1442
1443
1444
1445 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1446 T* data() BOOST_NOEXCEPT
1447 {
1448 return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1449 }
1450
1451
1452
1453
1454
1455
1456
1457
1458 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
1459 const T* data() const BOOST_NOEXCEPT
1460 {
1461 return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx;
1462 }
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1483 template <class... Args>
1484 reference emplace_front(Args&&... args)
1485 {
1486 if (BOOST_LIKELY(front_free_capacity() != 0))
1487 {
1488 pointer const p = m_.buffer + (m_.front_idx - 1u);
1489 this->alloc_construct(p, boost::forward<Args>(args)...);
1490 --m_.front_idx;
1491 BOOST_ASSERT(invariants_ok());
1492 return *p;
1493 }
1494 else
1495 {
1496 typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1497 return *this->insert_range_slow_path(this->begin(), 1, proxy_t(::boost::forward<Args>(args)...));
1498 }
1499 }
1500
1501 #else
1502
1503 #define BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT(N) \
1504 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1505 inline reference emplace_front(BOOST_MOVE_UREF##N)\
1506 {\
1507 if (front_free_capacity())\
1508 {\
1509 pointer const p = m_.buffer + (m_.front_idx - 1u);\
1510 this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1511 --m_.front_idx;\
1512 return *p;\
1513 }\
1514 else\
1515 {\
1516 typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1517 return *this->insert_range_slow_path(this->begin(), 1, proxy_t(BOOST_MOVE_FWD##N));\
1518 }\
1519 }\
1520
1521 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT)
1522 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_FRONT
1523
1524 #endif
1525
1526 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541 void push_front(const T& x);
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557 void push_front(T&& x);
1558
1559 #else
1560 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_front, T, void, priv_push_front)
1561 #endif
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572 void pop_front() BOOST_NOEXCEPT
1573 {
1574 BOOST_ASSERT(!empty());
1575 allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.front_idx));
1576 ++m_.front_idx;
1577 BOOST_ASSERT(invariants_ok());
1578 }
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1599 template <class... Args>
1600 inline reference emplace_back(Args&&... args)
1601 {
1602 if (BOOST_LIKELY(this->back_free_capacity() != 0)){
1603 pointer const p = m_.buffer + m_.back_idx;
1604 this->alloc_construct(p, boost::forward<Args>(args)...);
1605 ++m_.back_idx;
1606 BOOST_ASSERT(invariants_ok());
1607 return *p;
1608 }
1609 else {
1610 typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1611 return *this->insert_range_slow_path(this->end(), 1, proxy_t(::boost::forward<Args>(args)...));
1612 }
1613 }
1614
1615 #else
1616
1617 #define BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK(N) \
1618 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1619 inline reference emplace_back(BOOST_MOVE_UREF##N)\
1620 {\
1621 if (this->back_free_capacity()){\
1622 pointer const p = m_.buffer + m_.back_idx;\
1623 this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1624 ++m_.back_idx;\
1625 return *p;\
1626 }\
1627 else {\
1628 typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1629 return *this->insert_range_slow_path(this->end(), 1, proxy_t(BOOST_MOVE_FWD##N));\
1630 }\
1631 }\
1632
1633 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK)
1634 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE_BACK
1635
1636 #endif
1637
1638
1639 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654 void push_back(const T& x);
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670 void push_back(T&& x);
1671
1672 #else
1673 BOOST_MOVE_CONVERSION_AWARE_CATCH(push_back, T, void, priv_push_back)
1674 #endif
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685 void pop_back() BOOST_NOEXCEPT
1686 {
1687 BOOST_ASSERT(! empty());
1688 --m_.back_idx;
1689 allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(m_.buffer + m_.back_idx));
1690 BOOST_ASSERT(invariants_ok());
1691 }
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1713 template <class... Args>
1714 iterator emplace(const_iterator position, Args&&... args)
1715 {
1716 BOOST_ASSERT(position >= begin());
1717 BOOST_ASSERT(position <= end());
1718 typedef dtl::insert_emplace_proxy<allocator_type, Args...> proxy_t;
1719 bool prefer_move_back;
1720 if (position == end()){
1721 if(back_free_capacity())
1722 {
1723 pointer const p = m_.buffer + m_.back_idx;
1724 this->alloc_construct(p, boost::forward<Args>(args)...);
1725 ++m_.back_idx;
1726 return iterator(p);
1727 }
1728 prefer_move_back = true;
1729 }
1730 else if (position == begin()){
1731 if(front_free_capacity())
1732 {
1733 pointer const p = m_.buffer + (m_.front_idx - 1);
1734 this->alloc_construct(p, boost::forward<Args>(args)...);
1735 --m_.front_idx;
1736 return iterator(p);
1737 }
1738 prefer_move_back = false;
1739 }
1740 else{
1741 iterator nonconst_pos = unconst_iterator(position);
1742 prefer_move_back = should_move_back(position);
1743
1744 if(prefer_move_back){
1745 if(back_free_capacity()){
1746 boost::container::expand_forward_and_insert_nonempty_middle_alloc
1747 ( get_allocator_ref()
1748 , boost::movelib::to_raw_pointer(nonconst_pos)
1749 , this->priv_raw_end()
1750 , 1, proxy_t(::boost::forward<Args>(args)...));
1751 ++m_.back_idx;
1752 return nonconst_pos;
1753 }
1754 }
1755 else{
1756 if (front_free_capacity()){
1757 boost::container::expand_backward_and_insert_nonempty_middle_alloc
1758 (get_allocator_ref()
1759 , this->priv_raw_begin()
1760 , boost::movelib::to_raw_pointer(nonconst_pos)
1761 , 1, proxy_t(::boost::forward<Args>(args)...));
1762 --m_.front_idx;
1763 return --nonconst_pos;
1764 }
1765 }
1766 }
1767 return this->insert_range_slow_path(position, 1, proxy_t(::boost::forward<Args>(args)...));
1768 }
1769
1770 #else
1771
1772 #define BOOST_CONTAINER_DEVECTOR_EMPLACE(N) \
1773 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1774 iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1775 {\
1776 BOOST_ASSERT(position >= begin());\
1777 BOOST_ASSERT(position <= end());\
1778 typedef dtl::insert_emplace_proxy_arg##N<allocator_type BOOST_MOVE_I##N BOOST_MOVE_TARG##N> proxy_t;\
1779 bool prefer_move_back;\
1780 if (position == end()){\
1781 if(back_free_capacity())\
1782 {\
1783 pointer const p = m_.buffer + m_.back_idx;\
1784 this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1785 ++m_.back_idx;\
1786 return iterator(p);\
1787 }\
1788 prefer_move_back = true;\
1789 }\
1790 else if (position == begin()){\
1791 if(front_free_capacity())\
1792 {\
1793 pointer const p = m_.buffer + (m_.front_idx - 1);\
1794 this->alloc_construct(p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
1795 --m_.front_idx;\
1796 return iterator(p);\
1797 }\
1798 prefer_move_back = false;\
1799 }\
1800 else{\
1801 iterator nonconst_pos = unconst_iterator(position);\
1802 prefer_move_back = should_move_back(position);\
1803 \
1804 if(prefer_move_back){\
1805 if(back_free_capacity()){\
1806 boost::container::expand_forward_and_insert_nonempty_middle_alloc\
1807 ( get_allocator_ref()\
1808 , boost::movelib::to_raw_pointer(nonconst_pos)\
1809 , this->priv_raw_end()\
1810 , 1, proxy_t(BOOST_MOVE_FWD##N));\
1811 ++m_.back_idx;\
1812 return nonconst_pos;\
1813 }\
1814 }\
1815 else{\
1816 if (front_free_capacity()){\
1817 boost::container::expand_backward_and_insert_nonempty_middle_alloc\
1818 (get_allocator_ref()\
1819 , this->priv_raw_begin()\
1820 , boost::movelib::to_raw_pointer(nonconst_pos)\
1821 , 1, proxy_t(BOOST_MOVE_FWD##N));\
1822 --m_.front_idx;\
1823 return --nonconst_pos;\
1824 }\
1825 }\
1826 }\
1827 return this->insert_range_slow_path(position, 1, proxy_t(BOOST_MOVE_FWD##N));\
1828 }\
1829
1830 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_EMPLACE)
1831 #undef BOOST_CONTAINER_DEVECTOR_EMPLACE
1832
1833 #endif
1834
1835
1836 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853 iterator insert(const_iterator position, const T &x);
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872 iterator insert(const_iterator position, T &&x);
1873 #else
1874 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, T, iterator, priv_insert, const_iterator, const_iterator)
1875 #endif
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893 inline iterator insert(const_iterator position, size_type n, const T& x)
1894 {
1895 cvalue_iterator first(x, n);
1896 cvalue_iterator last = first + n;
1897 return this->insert_range(position, first, last);
1898 }
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928 template <class InputIterator>
1929 iterator insert(const_iterator position, InputIterator first, InputIterator last
1930
1931 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1932 < void
1933 BOOST_MOVE_I dtl::is_convertible<InputIterator BOOST_MOVE_I size_type>
1934 BOOST_MOVE_I dtl::is_not_input_iterator<InputIterator>
1935 >::type * = 0)
1936 )
1937 {
1938 if (position == end())
1939 {
1940 size_type insert_index = size();
1941
1942 for (; first != last; ++first)
1943 {
1944 this->emplace_back(*first);
1945 }
1946
1947 return begin() + insert_index;
1948 }
1949 else
1950 {
1951 const size_type insert_index = static_cast<size_type>(position - this->cbegin());
1952 const size_type old_size = static_cast<size_type>(this->size());
1953
1954 for (; first != last; ++first) {
1955 this->emplace_back(*first);
1956 }
1957 iterator rit (this->begin() + insert_index);
1958 boost::movelib::rotate_gcd(rit, this->begin() + old_size, this->begin() + this->size());
1959 return rit;
1960 }
1961 }
1962
1963 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1964
1965 template <class ForwardIterator>
1966 inline iterator insert(const_iterator position, ForwardIterator first, ForwardIterator last
1967
1968 BOOST_CONTAINER_DOCIGN(BOOST_MOVE_I typename dtl::disable_if_or
1969 < void
1970 BOOST_MOVE_I dtl::is_convertible<ForwardIterator BOOST_MOVE_I size_type>
1971 BOOST_MOVE_I dtl::is_input_iterator<ForwardIterator>
1972 >::type * = 0)
1973 )
1974 {
1975 return insert_range(position, first, last);
1976 }
1977
1978 #endif
1979
1980 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1981
1982 inline iterator insert(const_iterator position, std::initializer_list<T> il)
1983 {
1984 return this->insert(position, il.begin(), il.end());
1985 }
1986 #endif
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006 iterator erase(const_iterator position)
2007 {
2008 return erase(position, position + 1);
2009 }
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030 iterator erase(const_iterator first, const_iterator last)
2031 {
2032 iterator nc_first = unconst_iterator(first);
2033 iterator nc_last = unconst_iterator(last);
2034 return erase(nc_first, nc_last);
2035 }
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055 iterator erase(iterator first, iterator last)
2056 {
2057 size_type front_distance = pos_to_index(last);
2058 size_type back_distance = size_type(end() - first);
2059 size_type n = boost::container::iterator_udistance(first, last);
2060
2061 if (front_distance < back_distance)
2062 {
2063
2064 boost::container::move_backward(begin(), first, last);
2065
2066 for (iterator i = begin(); i != begin() + n; ++i)
2067 {
2068 allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
2069 }
2070
2071 m_.set_front_idx(m_.front_idx + n);
2072
2073 BOOST_ASSERT(invariants_ok());
2074 return last;
2075 }
2076 else {
2077
2078 boost::container::move(last, end(), first);
2079
2080 for (iterator i = end() - n; i != end(); ++i)
2081 {
2082 allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(i));
2083 }
2084
2085 m_.set_back_idx(m_.back_idx - n);
2086
2087 BOOST_ASSERT(invariants_ok());
2088 return first;
2089 }
2090 }
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106 void swap(devector& b)
2107 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2108 || allocator_traits_type::is_always_equal::value)
2109 {
2110 BOOST_CONSTEXPR_OR_CONST bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value;
2111 BOOST_ASSERT(propagate_alloc || get_allocator_ref() == b.get_allocator_ref());
2112
2113 swap_big_big(*this, b);
2114
2115
2116 boost::adl_move_swap(m_.front_idx, b.m_.front_idx);
2117 boost::adl_move_swap(m_.back_idx, b.m_.back_idx);
2118
2119
2120 dtl::swap_alloc(this->get_allocator_ref(), b.get_allocator_ref(), dtl::bool_<propagate_alloc>());
2121
2122 BOOST_ASSERT( invariants_ok());
2123 BOOST_ASSERT(b.invariants_ok());
2124 }
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138 void clear() BOOST_NOEXCEPT
2139 {
2140 destroy_elements(begin(), end());
2141 m_.front_idx = m_.back_idx = 0;
2142 }
2143
2144 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2145 friend bool operator==(const devector& x, const devector& y)
2146 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
2147
2148 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2149 friend bool operator!=(const devector& x, const devector& y)
2150 { return !(x == y); }
2151
2152 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2153 friend bool operator< (const devector& x, const devector& y)
2154 { return boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
2155
2156 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2157 friend bool operator>(const devector& x, const devector& y)
2158 { return y < x; }
2159
2160 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2161 friend bool operator<=(const devector& x, const devector& y)
2162 { return !(y < x); }
2163
2164 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2165 friend bool operator>=(const devector& x, const devector& y)
2166 { return !(x < y); }
2167
2168 inline friend void swap(devector& x, devector& y)
2169 BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value
2170 || allocator_traits_type::is_always_equal::value)
2171 { x.swap(y); }
2172
2173 private:
2174
2175 void priv_move_assign(BOOST_RV_REF(devector) x, dtl::bool_<true> )
2176 {
2177 this->clear();
2178 this->deallocate_buffer();
2179
2180
2181 dtl::bool_<allocator_traits_type::
2182 propagate_on_container_move_assignment::value> flag;
2183 dtl::move_alloc(this->get_allocator_ref(), x.get_allocator_ref(), flag);
2184
2185 m_.capacity = x.m_.capacity;
2186 m_.buffer = x.m_.buffer;
2187 m_.front_idx = x.m_.front_idx;
2188 m_.back_idx = x.m_.back_idx;
2189
2190
2191 x.m_.capacity = 0u;
2192 x.m_.buffer = pointer();
2193 x.m_.back_idx = x.m_.front_idx = 0;
2194 }
2195
2196 void priv_move_assign(BOOST_RV_REF(devector) x, dtl::bool_<false> )
2197 {
2198
2199
2200 if (get_allocator_ref() == x.get_allocator_ref()) {
2201 this->priv_move_assign(boost::move(x), dtl::true_());
2202 }
2203 else {
2204
2205 move_iterator<iterator> xbegin = boost::make_move_iterator(x.begin());
2206 move_iterator<iterator> xend = boost::make_move_iterator(x.end());
2207
2208
2209 dtl::bool_<allocator_traits_type::
2210 propagate_on_container_move_assignment::value> flag;
2211 dtl::move_alloc(this->get_allocator_ref(), x.get_allocator_ref(), flag);
2212
2213 if (m_.capacity >= x.size()) {
2214 overwrite_buffer(xbegin, xend);
2215 }
2216 else {
2217 allocate_and_copy_range(xbegin, xend);
2218 }
2219 }
2220 }
2221
2222 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2223 size_type pos_to_index(const_iterator i) const
2224 {
2225 return static_cast<size_type>(i - cbegin());
2226 }
2227
2228 BOOST_CONTAINER_ATTRIBUTE_NODISCARD inline
2229 bool should_move_back(const_iterator i) const
2230 {
2231 return static_cast<size_type>(this->pos_to_index(i)) >= this->size()/2u;
2232 }
2233
2234 inline static iterator unconst_iterator(const_iterator i)
2235 {
2236 return boost::intrusive::pointer_traits<pointer>::const_cast_from(i);
2237 }
2238
2239 inline size_type front_capacity() const
2240 {
2241 return m_.back_idx;
2242 }
2243
2244 inline size_type back_capacity() const
2245 {
2246 return size_type(m_.capacity - m_.front_idx);
2247 }
2248
2249 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2250
2251 inline T* priv_raw_begin() BOOST_NOEXCEPT
2252 { return boost::movelib::to_raw_pointer(m_.buffer) + m_.front_idx; }
2253
2254 inline T* priv_raw_end() BOOST_NOEXCEPT
2255 { return boost::movelib::to_raw_pointer(m_.buffer) + m_.back_idx; }
2256
2257
2258 template <class U>
2259 inline void priv_push_front(BOOST_FWD_REF(U) u)
2260 {
2261 this->emplace_front(boost::forward<U>(u));
2262 }
2263
2264 template <class U>
2265 inline void priv_push_back(BOOST_FWD_REF(U) u)
2266 {
2267 this->emplace_back(boost::forward<U>(u));
2268 }
2269
2270 template <class U>
2271 inline iterator priv_insert(const_iterator pos, BOOST_FWD_REF(U) u)
2272 {
2273 return this->emplace(pos, boost::forward<U>(u));
2274 }
2275
2276
2277
2278 inline allocator_type& get_allocator_ref() BOOST_NOEXCEPT
2279 {
2280 return static_cast<allocator_type&>(m_);
2281 }
2282
2283 inline const allocator_type& get_allocator_ref() const BOOST_NOEXCEPT
2284 {
2285 return static_cast<const allocator_type&>(m_);
2286 }
2287
2288 pointer allocate(size_type capacity)
2289 {
2290 pointer const p = impl::do_allocate(get_allocator_ref(), capacity);
2291 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2292 ++m_.capacity_alloc_count;
2293 #endif
2294 return p;
2295 }
2296
2297 void destroy_elements(pointer begin, pointer end)
2298 {
2299 for (; begin != end; ++begin)
2300 {
2301 allocator_traits_type::destroy(get_allocator_ref(), boost::movelib::to_raw_pointer(begin));
2302 }
2303 }
2304
2305 void deallocate_buffer()
2306 {
2307 if (m_.buffer)
2308 {
2309 allocator_traits_type::deallocate(get_allocator_ref(), m_.buffer, m_.capacity);
2310 }
2311 }
2312
2313 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2314 template <typename... Args>
2315 inline void alloc_construct(pointer dst, Args&&... args)
2316 {
2317 allocator_traits_type::construct(
2318 get_allocator_ref(),
2319 boost::movelib::to_raw_pointer(dst),
2320 boost::forward<Args>(args)...
2321 );
2322 }
2323
2324 template <typename... Args>
2325 void construct_n(pointer buffer, size_type n, Args&&... args)
2326 {
2327 detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());
2328 guarded_construct_n(buffer, n, ctr_guard, boost::forward<Args>(args)...);
2329 ctr_guard.release();
2330 }
2331
2332 template <typename... Args>
2333 void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard, Args&&... args)
2334 {
2335 for (size_type i = 0; i < n; ++i) {
2336 this->alloc_construct(buffer + i, boost::forward<Args>(args)...);
2337 ctr_guard.extend();
2338 }
2339 }
2340
2341 #else
2342
2343 #define BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT(N) \
2344 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2345 inline void alloc_construct(pointer dst BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2346 {\
2347 allocator_traits_type::construct(\
2348 get_allocator_ref(), boost::movelib::to_raw_pointer(dst) BOOST_MOVE_I##N BOOST_MOVE_FWD##N );\
2349 }\
2350 \
2351 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2352 void construct_n(pointer buffer, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2353 {\
2354 detail::construction_guard<allocator_type> ctr_guard(buffer, get_allocator_ref());\
2355 guarded_construct_n(buffer, n, ctr_guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2356 ctr_guard.release();\
2357 }\
2358 \
2359 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2360 void guarded_construct_n(pointer buffer, size_type n, detail::construction_guard<allocator_type>& ctr_guard BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2361 {\
2362 for (size_type i = 0; i < n; ++i) {\
2363 this->alloc_construct(buffer + i BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2364 ctr_guard.extend();\
2365 }\
2366 }
2367
2368 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT)
2369 #undef BOOST_CONTAINER_DEVECTOR_ALLOC_CONSTRUCT
2370
2371 #endif
2372
2373 size_type calculate_new_capacity(size_type requested_capacity)
2374 {
2375 size_type max = allocator_traits_type::max_size(this->get_allocator_ref());
2376 (clamp_by_stored_size_type)(max, stored_size_type());
2377 const size_type remaining_additional_cap = max - size_type(m_.capacity);
2378 const size_type min_additional_cap = requested_capacity - size_type(m_.capacity);
2379 if ( remaining_additional_cap < min_additional_cap )
2380 boost::container::throw_length_error("devector: get_next_capacity, max size exceeded");
2381
2382 return growth_factor_type()( size_type(m_.capacity), min_additional_cap, max);
2383 }
2384
2385 void buffer_move_or_copy(pointer dst)
2386 {
2387 detail::construction_guard<allocator_type> guard(dst, get_allocator_ref());
2388
2389 buffer_move_or_copy(dst, guard);
2390
2391 guard.release();
2392 }
2393
2394 void buffer_move_or_copy(pointer dst, detail::construction_guard<allocator_type>& guard)
2395 {
2396 opt_move_or_copy(begin(), end(), dst, guard);
2397
2398 destroy_elements(data(), data() + size());
2399 deallocate_buffer();
2400 }
2401
2402 template <typename Guard>
2403 void opt_move_or_copy(pointer begin, pointer end, pointer dst, Guard& guard)
2404 {
2405
2406 boost::container::uninitialized_move_alloc(get_allocator_ref(), begin, end, dst);
2407 guard.extend();
2408 }
2409
2410 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2411
2412 template <typename... Args>
2413 void resize_impl(size_type sz, Args&&... args)
2414 {
2415 const size_type old_sz = this->size();
2416 if (sz > old_sz)
2417 {
2418 const size_type n = sz - old_sz;
2419
2420 if (sz <= m_.capacity)
2421 {
2422
2423 const size_type bfc = this->back_free_capacity();
2424 const size_type b = n < bfc ? n : bfc;
2425 construct_n(m_.buffer + m_.back_idx, b, boost::forward<Args>(args)...);
2426 m_.set_back_idx(m_.back_idx + b);
2427
2428
2429 const size_type f = n - b;
2430 construct_n(m_.buffer + m_.front_idx - f, f, boost::forward<Args>(args)...);
2431 m_.set_front_idx(m_.front_idx - f);
2432 }
2433 else
2434 {
2435 resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2436 }
2437 }
2438 else
2439 {
2440 const size_type n = old_sz - sz;
2441 const size_type new_bidx = m_.back_idx - n;
2442 destroy_elements(m_.buffer + new_bidx, m_.buffer + m_.back_idx);
2443 m_.set_back_idx(new_bidx);
2444 }
2445 }
2446
2447 template <typename... Args>
2448 void resize_front_impl(size_type sz , Args&&... args)
2449 {
2450 const size_type old_sz = this->size();
2451 if (sz > old_sz)
2452 {
2453 const size_type n = sz - old_sz;
2454
2455 if (sz <= this->front_capacity())
2456 {
2457 construct_n(m_.buffer + m_.front_idx - n, n, boost::forward<Args>(args)...);
2458 m_.set_front_idx(m_.front_idx - n);
2459 }
2460 else
2461 {
2462 resize_front_slow_path(sz, n, boost::forward<Args>(args)...);
2463 }
2464 }
2465 else {
2466 const size_type n = old_sz - sz;
2467 const size_type new_fidx = m_.front_idx + n;
2468 destroy_elements(m_.buffer + m_.front_idx, m_.buffer + new_fidx);
2469 m_.set_front_idx(new_fidx);
2470 }
2471 }
2472
2473 template <typename... Args>
2474 void resize_front_slow_path(size_type sz, size_type n, Args&&... args)
2475 {
2476 const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());
2477 pointer new_buffer = allocate(new_capacity);
2478 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2479
2480 const size_type old_sz = this->size();
2481 const size_type new_old_elem_index = new_capacity - old_sz;
2482 const size_type new_elem_index = new_old_elem_index - n;
2483
2484 detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());
2485 guarded_construct_n(new_buffer + new_elem_index, n, guard, boost::forward<Args>(args)...);
2486
2487 buffer_move_or_copy(new_buffer + new_old_elem_index, guard);
2488
2489 guard.release();
2490 new_buffer_guard.release();
2491
2492 m_.buffer = new_buffer;
2493 m_.set_capacity(new_capacity);
2494 m_.set_front_idx(new_elem_index);
2495 m_.set_back_idx(new_elem_index + old_sz + n);
2496 }
2497
2498 template <typename... Args>
2499 void resize_back_impl(size_type sz, Args&&... args)
2500 {
2501 const size_type old_sz = this->size();
2502 if (sz > old_sz)
2503 {
2504 const size_type n = sz - old_sz;
2505
2506 if (sz <= this->back_capacity())
2507 {
2508 construct_n(m_.buffer + m_.back_idx, n, boost::forward<Args>(args)...);
2509 m_.set_back_idx(m_.back_idx + n);
2510 }
2511 else
2512 {
2513 resize_back_slow_path(sz, n, boost::forward<Args>(args)...);
2514 }
2515 }
2516 else
2517 {
2518 const size_type n = old_sz - sz;
2519 const size_type new_bidx = m_.back_idx - n;
2520 destroy_elements(m_.buffer + new_bidx, m_.buffer + m_.back_idx);
2521 m_.set_back_idx(new_bidx);
2522 }
2523 }
2524
2525 template <typename... Args>
2526 void resize_back_slow_path(size_type sz, size_type n, Args&&... args)
2527 {
2528 const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());
2529 pointer new_buffer = allocate(new_capacity);
2530 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2531
2532 detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());
2533 guarded_construct_n(new_buffer + m_.back_idx, n, guard, boost::forward<Args>(args)...);
2534
2535 buffer_move_or_copy(new_buffer + m_.front_idx);
2536
2537 guard.release();
2538 new_buffer_guard.release();
2539
2540 m_.buffer = new_buffer;
2541 m_.set_capacity(new_capacity);
2542 m_.set_back_idx(m_.back_idx + n);
2543 }
2544
2545 #else
2546
2547 #define BOOST_CONTAINER_DEVECTOR_SLOW_PATH(N) \
2548 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2549 void resize_front_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2550 {\
2551 if (sz > size())\
2552 {\
2553 const size_type n = sz - size();\
2554 if (sz <= front_capacity()){\
2555 construct_n(m_.buffer + m_.front_idx - n, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2556 m_.set_front_idx(m_.front_idx - n);\
2557 }\
2558 else\
2559 {\
2560 resize_front_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2561 }\
2562 }\
2563 else {\
2564 while (this->size() > sz)\
2565 {\
2566 this->pop_front();\
2567 }\
2568 }\
2569 }\
2570 \
2571 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2572 void resize_front_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2573 {\
2574 const size_type new_capacity = calculate_new_capacity(sz + back_free_capacity());\
2575 pointer new_buffer = allocate(new_capacity);\
2576 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2577 \
2578 const size_type new_old_elem_index = new_capacity - size();\
2579 const size_type new_elem_index = new_old_elem_index - n;\
2580 \
2581 detail::construction_guard<allocator_type> guard(new_buffer + new_elem_index, get_allocator_ref());\
2582 guarded_construct_n(new_buffer + new_elem_index, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2583 \
2584 buffer_move_or_copy(new_buffer + new_old_elem_index, guard);\
2585 \
2586 guard.release();\
2587 new_buffer_guard.release();\
2588 m_.buffer = new_buffer;\
2589 m_.set_capacity(new_capacity);\
2590 m_.set_back_idx(new_old_elem_index + m_.back_idx - m_.front_idx);\
2591 m_.set_front_idx(new_elem_index);\
2592 }\
2593 \
2594 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2595 void resize_back_impl(size_type sz BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2596 {\
2597 if (sz > size())\
2598 {\
2599 const size_type n = sz - size();\
2600 \
2601 if (sz <= back_capacity())\
2602 {\
2603 construct_n(m_.buffer + m_.back_idx, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2604 m_.set_back_idx(m_.back_idx + n);\
2605 }\
2606 else\
2607 {\
2608 resize_back_slow_path(sz, n BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2609 }\
2610 }\
2611 else\
2612 {\
2613 while (size() > sz)\
2614 {\
2615 pop_back();\
2616 }\
2617 }\
2618 }\
2619 \
2620 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2621 void resize_back_slow_path(size_type sz, size_type n BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2622 {\
2623 const size_type new_capacity = calculate_new_capacity(sz + front_free_capacity());\
2624 pointer new_buffer = allocate(new_capacity);\
2625 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());\
2626 \
2627 detail::construction_guard<allocator_type> guard(new_buffer + m_.back_idx, get_allocator_ref());\
2628 guarded_construct_n(new_buffer + m_.back_idx, n, guard BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
2629 \
2630 buffer_move_or_copy(new_buffer + m_.front_idx);\
2631 \
2632 guard.release();\
2633 new_buffer_guard.release();\
2634 \
2635 m_.buffer = new_buffer;\
2636 m_.set_capacity(new_capacity);\
2637 m_.set_back_idx(m_.back_idx + n);\
2638 }\
2639 \
2640
2641 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_DEVECTOR_SLOW_PATH)
2642 #undef BOOST_CONTAINER_DEVECTOR_SLOW_PATH
2643
2644 #endif
2645
2646 void reallocate_at(size_type new_capacity, size_type buffer_offset)
2647 {
2648 pointer new_buffer = allocate(new_capacity);
2649 {
2650 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2651 boost::container::uninitialized_move_alloc(get_allocator_ref(), this->begin(), this->end(), new_buffer + buffer_offset);
2652 new_buffer_guard.release();
2653 }
2654 destroy_elements(m_.buffer + m_.front_idx, m_.buffer + m_.back_idx);
2655 deallocate_buffer();
2656
2657 m_.buffer = new_buffer;
2658
2659 m_.set_capacity(new_capacity);
2660 m_.set_back_idx(size_type(m_.back_idx - m_.front_idx) + buffer_offset);
2661 m_.set_front_idx(buffer_offset);
2662
2663 BOOST_ASSERT(invariants_ok());
2664 }
2665
2666 template <typename ForwardIterator>
2667 iterator insert_range(const_iterator position, ForwardIterator first, ForwardIterator last)
2668 {
2669 BOOST_ASSERT(position >= begin());
2670 BOOST_ASSERT(position <= end());
2671 typedef dtl::insert_range_proxy<allocator_type, ForwardIterator> proxy_t;
2672
2673 size_type const n = boost::container::iterator_udistance(first, last);
2674 bool prefer_move_back;
2675 if (BOOST_UNLIKELY(!n)) {
2676 return begin() + size_type(position - cbegin());
2677 }
2678 else if (position == end()) {
2679 if(back_free_capacity() >= n)
2680 {
2681 iterator r(this->end());
2682 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_end());
2683 m_.set_back_idx(m_.back_idx + n);
2684 return r;
2685 }
2686 prefer_move_back = true;
2687 }
2688 else if (position == begin()) {
2689 if(front_free_capacity() >= n) {
2690 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, this->priv_raw_begin() - n);
2691 m_.set_front_idx(m_.front_idx - n);
2692 return begin();
2693 }
2694 prefer_move_back = false;
2695 }
2696 else{
2697 iterator nonconst_pos = unconst_iterator(position);
2698 prefer_move_back = should_move_back(position);
2699
2700 if(prefer_move_back){
2701 if(back_free_capacity() >= n){
2702 boost::container::expand_forward_and_insert_nonempty_middle_alloc
2703 ( get_allocator_ref()
2704 , boost::movelib::to_raw_pointer(nonconst_pos)
2705 , this->priv_raw_end()
2706 , n, proxy_t(first));
2707 m_.set_back_idx(m_.back_idx + n);
2708 return nonconst_pos;
2709 }
2710 }
2711 else{
2712 if (front_free_capacity() >= n){
2713 boost::container::expand_backward_and_insert_nonempty_middle_alloc
2714 ( get_allocator_ref()
2715 , this->priv_raw_begin()
2716 , boost::movelib::to_raw_pointer(nonconst_pos)
2717 , n, proxy_t(first));
2718 m_.set_front_idx(m_.front_idx - n);
2719 return (nonconst_pos -= n);
2720 }
2721 }
2722 }
2723 return this->insert_range_slow_path(position, n, proxy_t(first));
2724 }
2725
2726 template <class InsertionProxy>
2727 BOOST_CONTAINER_NOINLINE iterator insert_range_slow_path
2728 (const_iterator p, const size_type n, const InsertionProxy proxy)
2729 {
2730 size_type const back_free_cap = back_free_capacity();
2731 size_type const front_free_cap = front_free_capacity();
2732 size_type const free_cap = front_free_cap + back_free_cap;
2733 size_type const index = size_type(p - cbegin());
2734
2735 size_type const cap = m_.capacity;
2736
2737 if (free_cap >= n && (free_cap - n) >= cap/devector_min_free_fraction) {
2738 size_type const old_size = this->size();
2739 T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
2740 size_type const new_size = old_size + n;
2741 size_type const new_front_idx = (cap - new_size) / 2u;
2742
2743 T* const raw_beg = this->priv_raw_begin();
2744 T* const new_raw_beg = raw_beg - std::ptrdiff_t(m_.front_idx - new_front_idx);
2745 m_.back_idx = 0u;
2746 m_.front_idx = 0u;
2747 boost::container::expand_backward_forward_and_insert_alloc
2748 (raw_beg, old_size, new_raw_beg, raw_pos, n, proxy, get_allocator_ref());
2749 m_.set_front_idx(new_front_idx);
2750 m_.set_back_idx(new_front_idx + new_size);
2751 }
2752 else {
2753
2754 const size_type new_capacity = calculate_new_capacity(m_.capacity + n);
2755 pointer new_buffer = allocate(new_capacity);
2756
2757
2758 allocation_guard new_buffer_guard(new_buffer, new_capacity, get_allocator_ref());
2759
2760 size_type const old_size = this->size();
2761 const size_type new_front_index = (new_capacity - old_size - n) / 2u;
2762
2763 T* const raw_pos = const_cast<T*>(boost::movelib::to_raw_pointer(p));
2764 T* const raw_new_start = const_cast<T*>(boost::movelib::to_raw_pointer(new_buffer)) + new_front_index;
2765
2766 boost::container::uninitialized_move_and_insert_alloc
2767 (get_allocator_ref(), this->priv_raw_begin(), raw_pos, this->priv_raw_end(), raw_new_start, n, proxy);
2768 new_buffer_guard.release();
2769
2770
2771 destroy_elements(begin(), end());
2772 deallocate_buffer();
2773
2774
2775 m_.set_capacity(new_capacity);
2776 m_.buffer = new_buffer;
2777 m_.set_back_idx(new_front_index + old_size + n);
2778 m_.set_front_idx(new_front_index);
2779 }
2780 return begin() + index;
2781 }
2782
2783
2784 template <typename Iterator>
2785 void construct_from_range(Iterator begin, Iterator end)
2786 {
2787 allocation_guard buffer_guard(m_.buffer, m_.capacity, get_allocator_ref());
2788 boost::container::uninitialized_copy_alloc(get_allocator_ref(), begin, end, m_.buffer);
2789 buffer_guard.release();
2790 }
2791
2792 template <typename ForwardIterator>
2793 void allocate_and_copy_range(ForwardIterator first, ForwardIterator last)
2794 {
2795 size_type n = boost::container::iterator_udistance(first, last);
2796
2797 pointer new_buffer = n ? allocate(n) : pointer();
2798 allocation_guard new_buffer_guard(new_buffer, n, get_allocator_ref());
2799 boost::container::uninitialized_copy_alloc(get_allocator_ref(), first, last, new_buffer);
2800 destroy_elements(begin(), end());
2801 deallocate_buffer();
2802
2803 m_.set_capacity(n);
2804 m_.buffer = new_buffer;
2805 m_.front_idx = 0;
2806 m_.set_back_idx(n);
2807
2808 new_buffer_guard.release();
2809 }
2810
2811 static void swap_big_big(devector& a, devector& b) BOOST_NOEXCEPT
2812 {
2813 boost::adl_move_swap(a.m_.capacity, b.m_.capacity);
2814 boost::adl_move_swap(a.m_.buffer, b.m_.buffer);
2815 }
2816
2817 template <typename ForwardIterator>
2818 void overwrite_buffer_impl(ForwardIterator first, ForwardIterator last, dtl::true_)
2819 {
2820 const size_type n = boost::container::iterator_udistance(first, last);
2821
2822 BOOST_ASSERT(m_.capacity >= n);
2823 boost::container::uninitialized_copy_alloc_n
2824 ( get_allocator_ref(), first
2825 , n, boost::movelib::to_raw_pointer(m_.buffer));
2826 m_.front_idx = 0;
2827 m_.set_back_idx(n);
2828 }
2829
2830 template <typename InputIterator>
2831 InputIterator overwrite_buffer_impl(InputIterator first, InputIterator last, dtl::false_)
2832 {
2833 pointer pos = m_.buffer;
2834 detail::construction_guard<allocator_type> front_guard(pos, get_allocator_ref());
2835
2836 while (first != last && pos != begin()) {
2837 this->alloc_construct(pos++, *first++);
2838 front_guard.extend();
2839 }
2840
2841 while (first != last && pos != end()) {
2842 *pos++ = *first++;
2843 }
2844
2845 detail::construction_guard<allocator_type> back_guard(pos, get_allocator_ref());
2846
2847 iterator capacity_end = m_.buffer + m_.capacity;
2848 while (first != last && pos != capacity_end) {
2849 this->alloc_construct(pos++, *first++);
2850 back_guard.extend();
2851 }
2852
2853 pointer destroy_after = dtl::min_value(dtl::max_value(begin(), pos), end());
2854 destroy_elements(destroy_after, end());
2855
2856 front_guard.release();
2857 back_guard.release();
2858
2859 m_.front_idx = 0;
2860 m_.set_back_idx(pos_to_index(pos));
2861 return first;
2862 }
2863
2864 template <typename ForwardIterator>
2865 inline void overwrite_buffer(ForwardIterator first, ForwardIterator last)
2866 {
2867 this->overwrite_buffer_impl(first, last,
2868 dtl::bool_<dtl::is_trivially_destructible<T>::value>());
2869 }
2870
2871 bool invariants_ok()
2872 {
2873 return (! m_.capacity || m_.buffer )
2874 && m_.front_idx <= m_.back_idx
2875 && m_.back_idx <= m_.capacity;
2876 }
2877
2878 struct impl : allocator_type
2879 {
2880 BOOST_MOVABLE_BUT_NOT_COPYABLE(impl)
2881
2882 public:
2883 allocator_type &get_al()
2884 { return *this; }
2885
2886 static pointer do_allocate(allocator_type &a, size_type cap)
2887 {
2888 if (cap) {
2889
2890 if (cap > stored_size_type(-1)){
2891 boost::container::throw_length_error("get_next_capacity, allocator's max size reached");
2892 }
2893 return allocator_traits_type::allocate(a, cap);
2894 }
2895 else {
2896 return pointer();
2897 }
2898 }
2899
2900 impl()
2901 : allocator_type(), buffer(), front_idx(), back_idx(), capacity()
2902 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2903 , capacity_alloc_count(0)
2904 #endif
2905 {}
2906
2907 explicit impl(const allocator_type &a)
2908 : allocator_type(a), buffer(), front_idx(), back_idx(), capacity()
2909 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2910 , capacity_alloc_count(0)
2911 #endif
2912 {}
2913
2914 impl(reserve_uninitialized_t, const allocator_type& a, size_type c)
2915 : allocator_type(a), buffer(do_allocate(get_al(), c) )
2916
2917 , front_idx(static_cast<stored_size_type>(0u))
2918 , back_idx(static_cast<stored_size_type>(c))
2919 , capacity(static_cast<stored_size_type>(c))
2920 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2921 , capacity_alloc_count(size_type(buffer != pointer()))
2922 #endif
2923 {}
2924
2925 impl(reserve_only_tag_t, const allocator_type &a, size_type const ffc, size_type const bfc)
2926 : allocator_type(a), buffer(do_allocate(get_al(), ffc+bfc) )
2927
2928 , front_idx(static_cast<stored_size_type>(ffc))
2929 , back_idx(static_cast<stored_size_type>(ffc))
2930 , capacity(static_cast<stored_size_type>(ffc + bfc))
2931 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2932 , capacity_alloc_count(size_type(buffer != pointer()))
2933 #endif
2934 {}
2935
2936 impl(reserve_only_tag_t, const allocator_type &a, size_type const c)
2937 : allocator_type(a), buffer(do_allocate(get_al(), c) )
2938
2939 , front_idx(static_cast<stored_size_type>(c/2u))
2940 , back_idx(static_cast<stored_size_type>(c/2u))
2941 , capacity(static_cast<stored_size_type>(c))
2942 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2943 , capacity_alloc_count(size_type(buffer != pointer()))
2944 #endif
2945 {}
2946
2947 impl(review_implementation_t, const allocator_type &a, pointer p, size_type fi, size_type bi, size_type c)
2948 : allocator_type(a), buffer(p)
2949
2950 , front_idx(static_cast<stored_size_type>(fi))
2951 , back_idx(static_cast<stored_size_type>(bi))
2952 , capacity(static_cast<stored_size_type>(c))
2953 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2954 , capacity_alloc_count(0)
2955 #endif
2956 {}
2957
2958 impl(BOOST_RV_REF(impl) m)
2959 : allocator_type(BOOST_MOVE_BASE(allocator_type, m))
2960 , buffer(static_cast<impl&>(m).buffer)
2961 , front_idx(static_cast<impl&>(m).front_idx)
2962 , back_idx(static_cast<impl&>(m).back_idx)
2963 , capacity(static_cast<impl&>(m).capacity)
2964 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2965 , capacity_alloc_count(0)
2966 #endif
2967 {
2968 impl &i = static_cast<impl&>(m);
2969
2970 i.capacity = 0u;
2971 i.buffer = pointer();
2972 i.front_idx = 0;
2973 i.back_idx = 0;
2974 }
2975
2976 inline void set_back_idx(size_type bi)
2977 {
2978 back_idx = static_cast<stored_size_type>(bi);
2979 }
2980
2981 inline void set_front_idx(size_type fi)
2982 {
2983 front_idx = static_cast<stored_size_type>(fi);
2984 }
2985
2986 inline void set_capacity(size_type c)
2987 {
2988 capacity = static_cast<stored_size_type>(c);
2989 }
2990
2991 pointer buffer;
2992 stored_size_type front_idx;
2993 stored_size_type back_idx;
2994 stored_size_type capacity;
2995 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
2996 size_type capacity_alloc_count;
2997 #endif
2998 } m_;
2999
3000 #ifdef BOOST_CONTAINER_DEVECTOR_ALLOC_STATS
3001 public:
3002 void reset_alloc_stats()
3003 {
3004 m_.capacity_alloc_count = 0;
3005 }
3006
3007 size_type get_alloc_count() const
3008 {
3009 return m_.capacity_alloc_count;
3010 }
3011
3012 #endif
3013
3014 #endif
3015 };
3016
3017 }}
3018
3019 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
3020
3021 namespace boost {
3022
3023
3024
3025 template <class T, class Allocator, class Options>
3026 struct has_trivial_destructor_after_move<boost::container::devector<T, Allocator, Options> >
3027 {
3028 typedef typename boost::container::devector<T, Allocator, Options>::allocator_type allocator_type;
3029 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
3030 BOOST_STATIC_CONSTEXPR bool value =
3031 ::boost::has_trivial_destructor_after_move<allocator_type>::value &&
3032 ::boost::has_trivial_destructor_after_move<pointer>::value;
3033 };
3034
3035 }
3036
3037 #endif
3038
3039 #include <boost/container/detail/config_end.hpp>
3040
3041 #endif