container/detail/copy_move_algo.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010 #ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP
0011 #define BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP
0012
0013 #ifndef BOOST_CONFIG_HPP
0014 #  include <boost/config.hpp>
0015 #endif
0016
0017 #if defined(BOOST_HAS_PRAGMA_ONCE)
0018 #  pragma once
0019 #endif
0020
0021 // container
0022 #include <boost/container/allocator_traits.hpp>
0023 // container/detail
0024 #include <boost/container/detail/iterator.hpp>
0025 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0026 #include <boost/container/detail/mpl.hpp>
0027 #include <boost/container/detail/type_traits.hpp>
0028 #include <boost/container/detail/construct_in_place.hpp>
0029 #include <boost/container/detail/destroyers.hpp>
0030
0031 // move
0032 #include <boost/move/adl_move_swap.hpp>
0033 #include <boost/move/iterator.hpp>
0034 #include <boost/move/utility_core.hpp>
0035 #include <boost/move/traits.hpp>
0036 // other
0037 #include <boost/assert.hpp>
0038 // std
0039 #include <cstring> //for memmove/memcpy
0040
0041 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
0042 #pragma GCC diagnostic push
0043 //pair memcpy optimizations rightfully detected by GCC
0044 #  if defined(BOOST_GCC) && (BOOST_GCC >= 80000)
0045 #     pragma GCC diagnostic ignored "-Wclass-memaccess"
0046 #  endif
0047 //GCC 8 seems a bit confused about array access error with static_vector
0048 //when out of bound exceptions are being thrown.
0049 #  if defined(BOOST_GCC) && ((BOOST_GCC >= 80000) && (BOOST_GCC < 80200))
0050 #     pragma GCC diagnostic ignored "-Wstringop-overflow"
0051 #  endif
0052 //GCC 12 seems a bit confused about array access error with small_vector
0053 #  if defined(BOOST_GCC) && (BOOST_GCC >= 110000)
0054 #     pragma GCC diagnostic ignored "-Wstringop-overread"
0055 #     pragma GCC diagnostic ignored "-Wstringop-overflow"
0056 #  endif
0057 #  pragma GCC diagnostic ignored "-Warray-bounds"
0058 #endif
0059
0060 namespace boost {
0061 namespace container {
0062 namespace dtl {
0063
0064 template<class I>
0065 struct are_elements_contiguous
0066 {
0067    BOOST_STATIC_CONSTEXPR bool value = false;
0068 };
0069
0070 /////////////////////////
0071 //    raw pointers
0072 /////////////////////////
0073
0074 template<class T>
0075 struct are_elements_contiguous<T*>
0076 {
0077    BOOST_STATIC_CONSTEXPR bool value = true;
0078 };
0079
0080 /////////////////////////
0081 //    move iterators
0082 /////////////////////////
0083
0084 template<class It>
0085 struct are_elements_contiguous< ::boost::move_iterator<It> >
0086    : are_elements_contiguous<It>
0087 {};
0088
0089 }  //namespace dtl {
0090
0091 /////////////////////////
0092 //    predeclarations
0093 /////////////////////////
0094
0095 template <class Pointer, bool IsConst>
0096 class vec_iterator;
0097
0098 }  //namespace container {
0099
0100 namespace interprocess {
0101
0102 template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment>
0103 class offset_ptr;
0104
0105 }  //namespace interprocess {
0106
0107 namespace container {
0108
0109 namespace dtl {
0110
0111 /////////////////////////
0112 //vector_[const_]iterator
0113 /////////////////////////
0114
0115 template <class Pointer, bool IsConst>
0116 struct are_elements_contiguous<boost::container::vec_iterator<Pointer, IsConst> >
0117 {
0118    BOOST_STATIC_CONSTEXPR bool value = true;
0119 };
0120
0121
0122 /////////////////////////
0123 //    offset_ptr
0124 /////////////////////////
0125
0126 template <class PointedType, class DifferenceType, class OffsetType, std::size_t OffsetAlignment>
0127 struct are_elements_contiguous< ::boost::interprocess::offset_ptr<PointedType, DifferenceType, OffsetType, OffsetAlignment> >
0128 {
0129    BOOST_STATIC_CONSTEXPR bool value = true;
0130 };
0131
0132 template <typename I, typename O>
0133 struct are_contiguous_and_same
0134    : boost::move_detail::and_
0135       < are_elements_contiguous<I>
0136       , are_elements_contiguous<O>
0137       , is_same< typename remove_const< typename ::boost::container::iter_value<I>::type >::type
0138                , typename ::boost::container::iterator_traits<O>::value_type
0139                >
0140       >
0141 {};
0142
0143 template <typename I, typename O>
0144 struct is_memtransfer_copy_assignable
0145    : boost::move_detail::and_
0146       < are_contiguous_and_same<I, O>
0147       , dtl::is_trivially_copy_assignable< typename ::boost::container::iter_value<I>::type >
0148       >
0149 {};
0150
0151 template <typename I, typename O>
0152 struct is_memtransfer_copy_constructible
0153    : boost::move_detail::and_
0154       < are_contiguous_and_same<I, O>
0155       , dtl::is_trivially_copy_constructible< typename ::boost::container::iter_value<I>::type >
0156       >
0157 {};
0158
0159 template <typename I, typename O, typename R>
0160 struct enable_if_memtransfer_copy_constructible
0161    : enable_if<dtl::is_memtransfer_copy_constructible<I, O>, R>
0162 {};
0163
0164 template <typename I, typename O, typename R>
0165 struct disable_if_memtransfer_copy_constructible
0166    : disable_if<dtl::is_memtransfer_copy_constructible<I, O>, R>
0167 {};
0168
0169 template <typename I, typename O, typename R>
0170 struct enable_if_memtransfer_copy_assignable
0171    : enable_if<dtl::is_memtransfer_copy_assignable<I, O>, R>
0172 {};
0173
0174 template <typename I, typename O, typename R>
0175 struct disable_if_memtransfer_copy_assignable
0176    : disable_if<dtl::is_memtransfer_copy_assignable<I, O>, R>
0177 {};
0178
0179 template <class T>
0180 struct has_single_value
0181 {
0182 private:
0183    struct two { char array_[2]; };
0184    template<bool Arg> struct wrapper;
0185    template <class U> static two test(int, ...);
0186    template <class U> static char test(int, const wrapper<U::single_value>*);
0187 public:
0188    BOOST_STATIC_CONSTEXPR bool value = sizeof(test<T>(0, 0)) == 1;
0189    void dummy() {}
0190 };
0191
0192 template<class InsertionProxy, bool = has_single_value<InsertionProxy>::value>
0193 struct is_single_value_proxy_impl
0194 {
0195    BOOST_STATIC_CONSTEXPR bool value = InsertionProxy::single_value;
0196 };
0197
0198 template<class InsertionProxy>
0199 struct is_single_value_proxy_impl<InsertionProxy, false>
0200 {
0201    BOOST_STATIC_CONSTEXPR bool value = false;
0202 };
0203
0204 template<class InsertionProxy>
0205 struct is_single_value_proxy
0206    : is_single_value_proxy_impl<InsertionProxy>
0207 {};
0208
0209 template <typename P, typename R = void>
0210 struct enable_if_single_value_proxy
0211    : enable_if<is_single_value_proxy<P>, R>
0212 {};
0213
0214 template <typename P, typename R = void>
0215 struct disable_if_single_value_proxy
0216    : disable_if<is_single_value_proxy<P>, R>
0217 {};
0218
0219 template
0220    <typename I, // I models InputIterator
0221     typename F> // F models ForwardIterator
0222 inline F memmove(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
0223 {
0224    typedef typename boost::container::iter_value<I>::type      value_type;
0225    typedef typename boost::container::iterator_traits<F>::difference_type r_difference_type;
0226    value_type *const dest_raw = boost::movelib::iterator_to_raw_pointer(r);
0227    const value_type *const beg_raw = boost::movelib::iterator_to_raw_pointer(f);
0228    const value_type *const end_raw = boost::movelib::iterator_to_raw_pointer(l);
0229    if(BOOST_LIKELY(beg_raw != end_raw && dest_raw && beg_raw)){
0230       const std::size_t n = std::size_t(end_raw - beg_raw)   ;
0231       std::memmove(dest_raw, beg_raw, sizeof(value_type)*n);
0232       r += static_cast<r_difference_type>(n);
0233    }
0234    return r;
0235 }
0236
0237 template
0238    <typename I, // I models InputIterator
0239     typename F> // F models ForwardIterator
0240 inline F memmove_n(I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0241 {
0242    typedef typename boost::container::iter_value<I>::type value_type;
0243    typedef typename boost::container::iterator_traits<F>::difference_type r_difference_type;
0244    if(BOOST_LIKELY(n != 0)){
0245       void *dst = boost::movelib::iterator_to_raw_pointer(r);
0246       const void *src = boost::movelib::iterator_to_raw_pointer(f);
0247       if (dst && src)
0248          std::memmove(dst, src, sizeof(value_type)*n);
0249       r += static_cast<r_difference_type>(n);
0250    }
0251
0252    return r;
0253 }
0254
0255 template
0256    <typename I, // I models InputIterator
0257     typename F> // F models ForwardIterator
0258 inline I memmove_n_source(I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0259 {
0260    if(BOOST_LIKELY(n != 0)){
0261       typedef typename boost::container::iter_value<I>::type value_type;
0262       typedef typename boost::container::iterator_traits<I>::difference_type i_difference_type;
0263       void *dst = boost::movelib::iterator_to_raw_pointer(r);
0264       const void *src = boost::movelib::iterator_to_raw_pointer(f);
0265       if (dst && src)
0266          std::memmove(dst, src, sizeof(value_type)*n);
0267       f += static_cast<i_difference_type>(n);
0268    }
0269    return f;
0270 }
0271
0272 template
0273    <typename I, // I models InputIterator
0274     typename F> // F models ForwardIterator
0275 inline I memmove_n_source_dest(I f, std::size_t n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
0276 {
0277    typedef typename boost::container::iter_value<I>::type value_type;
0278    typedef typename boost::container::iterator_traits<F>::difference_type i_difference_type;
0279    typedef typename boost::container::iterator_traits<F>::difference_type f_difference_type;
0280
0281    if(BOOST_LIKELY(n != 0)){
0282       void *dst = boost::movelib::iterator_to_raw_pointer(r);
0283       const void *src = boost::movelib::iterator_to_raw_pointer(f);
0284       if (dst && src)
0285          std::memmove(dst, src, sizeof(value_type)*n);
0286       f += i_difference_type(n);
0287       r += f_difference_type(n);
0288    }
0289    return f;
0290 }
0291
0292 template <typename O>
0293 struct is_memzero_initializable
0294 {
0295    typedef typename ::boost::container::iterator_traits<O>::value_type value_type;
0296    BOOST_STATIC_CONSTEXPR bool value = are_elements_contiguous<O>::value &&
0297       (  dtl::is_integral<value_type>::value || dtl::is_enum<value_type>::value
0298       #if defined(BOOST_CONTAINER_MEMZEROED_POINTER_IS_NULL)
0299       || dtl::is_pointer<value_type>::value
0300       #endif
0301       #if defined(BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_ZERO)
0302       || dtl::is_floating_point<value_type>::value
0303       #endif
0304       );
0305 };
0306
0307 template <typename O, typename R>
0308 struct enable_if_memzero_initializable
0309    : enable_if_c<dtl::is_memzero_initializable<O>::value, R>
0310 {};
0311
0312 template <typename O, typename R>
0313 struct disable_if_memzero_initializable
0314    : enable_if_c<!dtl::is_memzero_initializable<O>::value, R>
0315 {};
0316
0317 template <typename I, typename R>
0318 struct enable_if_trivially_destructible
0319    : enable_if_c < dtl::is_trivially_destructible
0320                   <typename boost::container::iter_value<I>::type>::value
0321                , R>
0322 {};
0323
0324 template <typename I, typename R>
0325 struct disable_if_trivially_destructible
0326    : enable_if_c <!dtl::is_trivially_destructible
0327                   <typename boost::container::iter_value<I>::type>::value
0328                , R>
0329 {};
0330
0331 }  //namespace dtl {
0332
0333 //////////////////////////////////////////////////////////////////////////////
0334 //
0335 //                               uninitialized_move_alloc
0336 //
0337 //////////////////////////////////////////////////////////////////////////////
0338
0339
0340 //! <b>Effects</b>:
0341 //!   \code
0342 //!   for (; f != l; ++r, ++f)
0343 //!      allocator_traits::construct(a, &*r, boost::move(*f));
0344 //!   \endcode
0345 //!
0346 //! <b>Returns</b>: r
0347 template
0348    <typename Allocator,
0349     typename I, // I models InputIterator
0350     typename F> // F models ForwardIterator
0351 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
0352    uninitialized_move_alloc(Allocator &a, I f, I l, F r)
0353 {
0354    F back = r;
0355    BOOST_CONTAINER_TRY{
0356       while (f != l) {
0357          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
0358          ++f; ++r;
0359       }
0360    }
0361    BOOST_CONTAINER_CATCH(...){
0362       for (; back != r; ++back){
0363          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0364       }
0365       BOOST_CONTAINER_RETHROW;
0366    }
0367    BOOST_CONTAINER_CATCH_END
0368    return r;
0369 }
0370
0371 template
0372    <typename Allocator,
0373     typename I, // I models InputIterator
0374     typename F> // F models ForwardIterator
0375 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
0376    uninitialized_move_alloc(Allocator &, I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
0377 {  return dtl::memmove(f, l, r); }
0378
0379 //////////////////////////////////////////////////////////////////////////////
0380 //
0381 //                               uninitialized_move_alloc_n
0382 //
0383 //////////////////////////////////////////////////////////////////////////////
0384
0385 //! <b>Effects</b>:
0386 //!   \code
0387 //!   for (; n--; ++r, ++f)
0388 //!      allocator_traits::construct(a, &*r, boost::move(*f));
0389 //!   \endcode
0390 //!
0391 //! <b>Returns</b>: r
0392 template
0393    <typename Allocator,
0394     typename I, // I models InputIterator
0395     typename F> // F models ForwardIterator
0396 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
0397    uninitialized_move_alloc_n(Allocator &a, I f, std::size_t n, F r)
0398 {
0399    F back = r;
0400    BOOST_CONTAINER_TRY{
0401       while (n) {
0402          --n;
0403          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
0404          ++f; ++r;
0405       }
0406    }
0407    BOOST_CONTAINER_CATCH(...){
0408       for (; back != r; ++back){
0409          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0410       }
0411       BOOST_CONTAINER_RETHROW;
0412    }
0413    BOOST_CONTAINER_CATCH_END
0414    return r;
0415 }
0416
0417 template
0418    <typename Allocator,
0419     typename I, // I models InputIterator
0420     typename F> // F models ForwardIterator
0421 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
0422    uninitialized_move_alloc_n(Allocator &, I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0423 {  return dtl::memmove_n(f, n, r); }
0424
0425 //////////////////////////////////////////////////////////////////////////////
0426 //
0427 //                               uninitialized_move_alloc_n_source
0428 //
0429 //////////////////////////////////////////////////////////////////////////////
0430
0431 //! <b>Effects</b>:
0432 //!   \code
0433 //!   for (; n--; ++r, ++f)
0434 //!      allocator_traits::construct(a, &*r, boost::move(*f));
0435 //!   \endcode
0436 //!
0437 //! <b>Returns</b>: f (after incremented)
0438 template
0439    <typename Allocator,
0440     typename I, // I models InputIterator
0441     typename F> // F models ForwardIterator
0442 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, I>::type
0443    uninitialized_move_alloc_n_source(Allocator &a, I f, std::size_t n, F r)
0444 {
0445    F back = r;
0446    BOOST_CONTAINER_TRY{
0447       while (n) {
0448          --n;
0449          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), boost::move(*f));
0450          ++f; ++r;
0451       }
0452    }
0453    BOOST_CONTAINER_CATCH(...){
0454       for (; back != r; ++back){
0455          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0456       }
0457       BOOST_CONTAINER_RETHROW;
0458    }
0459    BOOST_CONTAINER_CATCH_END
0460    return f;
0461 }
0462
0463 template
0464    <typename Allocator,
0465     typename I, // I models InputIterator
0466     typename F> // F models ForwardIterator
0467 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, I>::type
0468    uninitialized_move_alloc_n_source(Allocator &, I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0469 {  return dtl::memmove_n_source(f, n, r); }
0470
0471 //////////////////////////////////////////////////////////////////////////////
0472 //
0473 //                               uninitialized_copy_alloc
0474 //
0475 //////////////////////////////////////////////////////////////////////////////
0476
0477 //! <b>Effects</b>:
0478 //!   \code
0479 //!   for (; f != l; ++r, ++f)
0480 //!      allocator_traits::construct(a, &*r, *f);
0481 //!   \endcode
0482 //!
0483 //! <b>Returns</b>: r
0484 template
0485    <typename Allocator,
0486     typename I, // I models InputIterator
0487     typename F> // F models ForwardIterator
0488 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
0489    uninitialized_copy_alloc(Allocator &a, I f, I l, F r)
0490 {
0491    F back = r;
0492    BOOST_CONTAINER_TRY{
0493       while (f != l) {
0494          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), *f);
0495          ++f; ++r;
0496       }
0497    }
0498    BOOST_CONTAINER_CATCH(...){
0499       for (; back != r; ++back){
0500          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0501       }
0502       BOOST_CONTAINER_RETHROW;
0503    }
0504    BOOST_CONTAINER_CATCH_END
0505    return r;
0506 }
0507
0508 template
0509    <typename Allocator,
0510     typename I, // I models InputIterator
0511     typename F> // F models ForwardIterator
0512 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
0513    uninitialized_copy_alloc(Allocator &, I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
0514 {  return dtl::memmove(f, l, r); }
0515
0516 //////////////////////////////////////////////////////////////////////////////
0517 //
0518 //                               uninitialized_copy_alloc_n
0519 //
0520 //////////////////////////////////////////////////////////////////////////////
0521
0522 //! <b>Effects</b>:
0523 //!   \code
0524 //!   for (; n--; ++r, ++f)
0525 //!      allocator_traits::construct(a, &*r, *f);
0526 //!   \endcode
0527 //!
0528 //! <b>Returns</b>: r
0529 template
0530    <typename Allocator,
0531     typename I, // I models InputIterator
0532     typename F> // F models ForwardIterator
0533 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, F>::type
0534    uninitialized_copy_alloc_n(Allocator &a, I f, std::size_t n, F r)
0535 {
0536    F back = r;
0537    BOOST_CONTAINER_TRY{
0538       while (n) {
0539          --n;
0540          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), *f);
0541          ++f; ++r;
0542       }
0543    }
0544    BOOST_CONTAINER_CATCH(...){
0545       for (; back != r; ++back){
0546          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0547       }
0548       BOOST_CONTAINER_RETHROW;
0549    }
0550    BOOST_CONTAINER_CATCH_END
0551    return r;
0552 }
0553
0554 template
0555    <typename Allocator,
0556     typename I, // I models InputIterator
0557     typename F> // F models ForwardIterator
0558 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, F>::type
0559    uninitialized_copy_alloc_n(Allocator &, I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0560 {  return dtl::memmove_n(f, n, r); }
0561
0562 //////////////////////////////////////////////////////////////////////////////
0563 //
0564 //                               uninitialized_copy_alloc_n_source
0565 //
0566 //////////////////////////////////////////////////////////////////////////////
0567
0568 //! <b>Effects</b>:
0569 //!   \code
0570 //!   for (; n--; ++r, ++f)
0571 //!      allocator_traits::construct(a, &*r, *f);
0572 //!   \endcode
0573 //!
0574 //! <b>Returns</b>: f (after incremented)
0575 template
0576    <typename Allocator,
0577     typename I, // I models InputIterator
0578     typename F> // F models ForwardIterator
0579 inline typename dtl::disable_if_memtransfer_copy_constructible<I, F, I>::type
0580    uninitialized_copy_alloc_n_source(Allocator &a, I f, std::size_t n, F r)
0581 {
0582    F back = r;
0583    BOOST_CONTAINER_TRY{
0584       while (n) {
0585          boost::container::construct_in_place(a, boost::movelib::iterator_to_raw_pointer(r), f);
0586          ++f; ++r; --n;
0587       }
0588    }
0589    BOOST_CONTAINER_CATCH(...){
0590       for (; back != r; ++back){
0591          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0592       }
0593       BOOST_CONTAINER_RETHROW;
0594    }
0595    BOOST_CONTAINER_CATCH_END
0596    return f;
0597 }
0598
0599 template
0600    <typename Allocator,
0601     typename I, // I models InputIterator
0602     typename F> // F models ForwardIterator
0603 inline typename dtl::enable_if_memtransfer_copy_constructible<I, F, I>::type
0604    uninitialized_copy_alloc_n_source(Allocator &, I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0605 {  return dtl::memmove_n_source(f, n, r); }
0606
0607 //////////////////////////////////////////////////////////////////////////////
0608 //
0609 //                               uninitialized_value_init_alloc_n
0610 //
0611 //////////////////////////////////////////////////////////////////////////////
0612
0613 //! <b>Effects</b>:
0614 //!   \code
0615 //!   for (; n--; ++r, ++f)
0616 //!      allocator_traits::construct(a, &*r);
0617 //!   \endcode
0618 //!
0619 //! <b>Returns</b>: r
0620 template
0621    <typename Allocator,
0622     typename F> // F models ForwardIterator
0623 inline typename dtl::disable_if_memzero_initializable<F, F>::type
0624    uninitialized_value_init_alloc_n(Allocator &a, std::size_t n, F r)
0625 {
0626    F back = r;
0627    BOOST_CONTAINER_TRY{
0628       while (n) {
0629          --n;
0630          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r));
0631          ++r;
0632       }
0633    }
0634    BOOST_CONTAINER_CATCH(...){
0635       for (; back != r; ++back){
0636          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0637       }
0638       BOOST_CONTAINER_RETHROW;
0639    }
0640    BOOST_CONTAINER_CATCH_END
0641    return r;
0642 }
0643
0644 template
0645    <typename Allocator,
0646     typename F> // F models ForwardIterator
0647 inline typename dtl::enable_if_memzero_initializable<F, F>::type
0648    uninitialized_value_init_alloc_n(Allocator &, std::size_t n, F r)
0649 {
0650    typedef typename boost::container::iterator_traits<F>::value_type value_type;
0651    typedef typename boost::container::iterator_traits<F>::difference_type r_difference_type;
0652
0653    if (BOOST_LIKELY(n != 0)){
0654       std::memset((void*)boost::movelib::iterator_to_raw_pointer(r), 0, sizeof(value_type)*n);
0655       r += static_cast<r_difference_type>(n);
0656    }
0657    return r;
0658 }
0659
0660 //////////////////////////////////////////////////////////////////////////////
0661 //
0662 //                               uninitialized_default_init_alloc_n
0663 //
0664 //////////////////////////////////////////////////////////////////////////////
0665
0666 //! <b>Effects</b>:
0667 //!   \code
0668 //!   for (; n--; ++r, ++f)
0669 //!      allocator_traits::construct(a, &*r);
0670 //!   \endcode
0671 //!
0672 //! <b>Returns</b>: r
0673 template
0674    <typename Allocator,
0675     typename F> // F models ForwardIterator
0676 inline F uninitialized_default_init_alloc_n(Allocator &a, std::size_t n, F r)
0677 {
0678    F back = r;
0679    BOOST_CONTAINER_TRY{
0680       while (n) {
0681          --n;
0682          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), default_init);
0683          ++r;
0684       }
0685    }
0686    BOOST_CONTAINER_CATCH(...){
0687       for (; back != r; ++back){
0688          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0689       }
0690       BOOST_CONTAINER_RETHROW;
0691    }
0692    BOOST_CONTAINER_CATCH_END
0693    return r;
0694 }
0695
0696 //////////////////////////////////////////////////////////////////////////////
0697 //
0698 //                               uninitialized_fill_alloc
0699 //
0700 //////////////////////////////////////////////////////////////////////////////
0701
0702 //! <b>Effects</b>:
0703 //!   \code
0704 //!   for (; f != l; ++r, ++f)
0705 //!      allocator_traits::construct(a, &*r, *f);
0706 //!   \endcode
0707 //!
0708 //! <b>Returns</b>: r
0709 template
0710    <typename Allocator,
0711     typename F, // F models ForwardIterator
0712     typename T>
0713 inline void uninitialized_fill_alloc(Allocator &a, F f, F l, const T &t)
0714 {
0715    F back = f;
0716    BOOST_CONTAINER_TRY{
0717       while (f != l) {
0718          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(f), t);
0719          ++f;
0720       }
0721    }
0722    BOOST_CONTAINER_CATCH(...){
0723       for (; back != l; ++back){
0724          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0725       }
0726       BOOST_CONTAINER_RETHROW;
0727    }
0728    BOOST_CONTAINER_CATCH_END
0729 }
0730
0731
0732 //////////////////////////////////////////////////////////////////////////////
0733 //
0734 //                               uninitialized_fill_alloc_n
0735 //
0736 //////////////////////////////////////////////////////////////////////////////
0737
0738 //! <b>Effects</b>:
0739 //!   \code
0740 //!   for (; n--; ++r, ++f)
0741 //!      allocator_traits::construct(a, &*r, v);
0742 //!   \endcode
0743 //!
0744 //! <b>Returns</b>: r
0745 template
0746    <typename Allocator,
0747     typename T,
0748     typename F> // F models ForwardIterator
0749 inline F uninitialized_fill_alloc_n(Allocator &a, const T &v, std::size_t n, F r)
0750 {
0751    F back = r;
0752    BOOST_CONTAINER_TRY{
0753       while (n) {
0754          --n;
0755          allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(r), v);
0756          ++r;
0757       }
0758    }
0759    BOOST_CONTAINER_CATCH(...){
0760       for (; back != r; ++back){
0761          allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(back));
0762       }
0763       BOOST_CONTAINER_RETHROW;
0764    }
0765    BOOST_CONTAINER_CATCH_END
0766    return r;
0767 }
0768
0769 //////////////////////////////////////////////////////////////////////////////
0770 //
0771 //                               copy
0772 //
0773 //////////////////////////////////////////////////////////////////////////////
0774
0775 template
0776 <typename I,   // I models InputIterator
0777 typename F>    // F models ForwardIterator
0778 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
0779    copy(I f, I l, F r)
0780 {
0781    while (f != l) {
0782       *r = *f;
0783       ++f; ++r;
0784    }
0785    return r;
0786 }
0787
0788 template
0789 <typename I,   // I models InputIterator
0790 typename F>    // F models ForwardIterator
0791 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
0792    copy(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
0793 {  return dtl::memmove(f, l, r); }
0794
0795 //////////////////////////////////////////////////////////////////////////////
0796 //
0797 //                               copy_n
0798 //
0799 //////////////////////////////////////////////////////////////////////////////
0800
0801 template
0802 <typename I,   // I models InputIterator
0803 typename U,   // U models unsigned integral constant
0804 typename F>   // F models ForwardIterator
0805 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
0806    copy_n(I f, U n, F r)
0807 {
0808    while (n) {
0809       --n;
0810       *r = *f;
0811       ++f; ++r;
0812    }
0813    return r;
0814 }
0815
0816 template
0817 <typename I,   // I models InputIterator
0818 typename U,   // U models unsigned integral constant
0819 typename F>   // F models ForwardIterator
0820 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
0821    copy_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0822 {  return dtl::memmove_n(f, n, r); }
0823
0824 //////////////////////////////////////////////////////////////////////////////
0825 //
0826 //                            copy_n_source
0827 //
0828 //////////////////////////////////////////////////////////////////////////////
0829
0830 template
0831 <typename I,   // I models InputIterator
0832 typename U,   // U models unsigned integral constant
0833 typename F>   // F models ForwardIterator
0834 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
0835    copy_n_source(I f, U n, F r)
0836 {
0837    while (n) {
0838       --n;
0839       boost::container::assign_in_place(r, f);
0840       ++f; ++r;
0841    }
0842    return f;
0843 }
0844
0845 template
0846 <typename I,   // I models InputIterator
0847 typename F>   // F models ForwardIterator
0848 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
0849    copy_n_source(I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0850 {  return dtl::memmove_n_source(f, n, r); }
0851
0852 //////////////////////////////////////////////////////////////////////////////
0853 //
0854 //                            copy_n_source_dest
0855 //
0856 //////////////////////////////////////////////////////////////////////////////
0857
0858 template
0859 <typename I,   // I models InputIterator
0860 typename F>   // F models ForwardIterator
0861 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
0862    copy_n_source_dest(I f, std::size_t n, F &r)
0863 {
0864    while (n) {
0865       --n;
0866       *r = *f;
0867       ++f; ++r;
0868    }
0869    return f;
0870 }
0871
0872 template
0873 <typename I,   // I models InputIterator
0874 typename F>   // F models ForwardIterator
0875 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
0876    copy_n_source_dest(I f, std::size_t n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
0877 {  return dtl::memmove_n_source_dest(f, n, r);  }
0878
0879 //////////////////////////////////////////////////////////////////////////////
0880 //
0881 //                         move
0882 //
0883 //////////////////////////////////////////////////////////////////////////////
0884
0885 template
0886 <typename I,   // I models InputIterator
0887 typename F>   // F models ForwardIterator
0888 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
0889    move(I f, I l, F r)
0890 {
0891    while (f != l) {
0892       *r = ::boost::move(*f);
0893       ++f; ++r;
0894    }
0895    return r;
0896 }
0897
0898 template
0899 <typename I,   // I models InputIterator
0900 typename F>   // F models ForwardIterator
0901 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
0902    move(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
0903 {  return dtl::memmove(f, l, r); }
0904
0905 //////////////////////////////////////////////////////////////////////////////
0906 //
0907 //                         move_n
0908 //
0909 //////////////////////////////////////////////////////////////////////////////
0910
0911 template
0912 <typename I,   // I models InputIterator
0913 typename U,   // U models unsigned integral constant
0914 typename F>   // F models ForwardIterator
0915 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
0916    move_n(I f, U n, F r)
0917 {
0918    while (n) {
0919       --n;
0920       *r = ::boost::move(*f);
0921       ++f; ++r;
0922    }
0923    return r;
0924 }
0925
0926 template
0927 <typename I,   // I models InputIterator
0928 typename U,   // U models unsigned integral constant
0929 typename F>   // F models ForwardIterator
0930 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
0931    move_n(I f, U n, F r) BOOST_NOEXCEPT_OR_NOTHROW
0932 {  return dtl::memmove_n(f, n, r); }
0933
0934
0935 //////////////////////////////////////////////////////////////////////////////
0936 //
0937 //                         move_backward
0938 //
0939 //////////////////////////////////////////////////////////////////////////////
0940
0941 template
0942 <typename I,   // I models BidirectionalIterator
0943 typename F>    // F models ForwardIterator
0944 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, F>::type
0945    move_backward(I f, I l, F r)
0946 {
0947    while (f != l) {
0948       --l; --r;
0949       *r = ::boost::move(*l);
0950    }
0951    return r;
0952 }
0953
0954 template
0955 <typename I,   // I models InputIterator
0956 typename F>   // F models ForwardIterator
0957 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, F>::type
0958    move_backward(I f, I l, F r) BOOST_NOEXCEPT_OR_NOTHROW
0959 {
0960    typedef typename boost::container::iter_value<I>::type value_type;
0961    const std::size_t n = boost::container::iterator_udistance(f, l);
0962    if (BOOST_LIKELY(n != 0)){
0963       r -= n;
0964       std::memmove((boost::movelib::iterator_to_raw_pointer)(r), (boost::movelib::iterator_to_raw_pointer)(f), sizeof(value_type)*n);
0965    }
0966    return r;
0967 }
0968
0969 //////////////////////////////////////////////////////////////////////////////
0970 //
0971 //                         move_n_source_dest
0972 //
0973 //////////////////////////////////////////////////////////////////////////////
0974
0975 template
0976 <typename I    // I models InputIterator
0977 ,typename U    // U models unsigned integral constant
0978 ,typename F>   // F models ForwardIterator
0979 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
0980    move_n_source_dest(I f, U n, F &r)
0981 {
0982    while (n) {
0983       --n;
0984       *r = ::boost::move(*f);
0985       ++f; ++r;
0986    }
0987    return f;
0988 }
0989
0990 template
0991 <typename I    // I models InputIterator
0992 ,typename F>   // F models ForwardIterator
0993 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
0994    move_n_source_dest(I f, std::size_t n, F &r) BOOST_NOEXCEPT_OR_NOTHROW
0995 {  return dtl::memmove_n_source_dest(f, n, r); }
0996
0997 //////////////////////////////////////////////////////////////////////////////
0998 //
0999 //                         move_n_source
1000 //
1001 //////////////////////////////////////////////////////////////////////////////
1002
1003 template
1004 <typename I    // I models InputIterator
1005 ,typename U    // U models unsigned integral constant
1006 ,typename F>   // F models ForwardIterator
1007 inline typename dtl::disable_if_memtransfer_copy_assignable<I, F, I>::type
1008    move_n_source(I f, U n, F r)
1009 {
1010    while (n) {
1011       --n;
1012       *r = ::boost::move(*f);
1013       ++f; ++r;
1014    }
1015    return f;
1016 }
1017
1018 template
1019 <typename I    // I models InputIterator
1020 ,typename F>   // F models ForwardIterator
1021 inline typename dtl::enable_if_memtransfer_copy_assignable<I, F, I>::type
1022    move_n_source(I f, std::size_t n, F r) BOOST_NOEXCEPT_OR_NOTHROW
1023 {  return dtl::memmove_n_source(f, n, r); }
1024
1025 template<typename F>   // F models ForwardIterator
1026 inline F move_forward_overlapping(F f, F l, F r)
1027 {
1028    return (f != r) ? (move)(f, l, r) : l;
1029 }
1030
1031 template<typename B>   // B models BidirIterator
1032 inline B move_backward_overlapping(B f, B l, B rl)
1033 {
1034    return (l != rl) ? (move_backward)(f, l, rl) : f;
1035 }
1036
1037
1038 //////////////////////////////////////////////////////////////////////////////
1039 //
1040 //                               destroy_alloc_n
1041 //
1042 //////////////////////////////////////////////////////////////////////////////
1043
1044 template
1045    <typename Allocator
1046    ,typename I   // I models InputIterator
1047    ,typename U>  // U models unsigned integral constant
1048 inline typename dtl::disable_if_trivially_destructible<I, void>::type
1049    destroy_alloc_n(Allocator &a, I f, U n)
1050 {
1051    while(n){
1052       --n;
1053       allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(f));
1054       ++f;
1055    }
1056 }
1057
1058 template
1059    <typename Allocator
1060    ,typename I   // I models InputIterator
1061    ,typename U>  // U models unsigned integral constant
1062 inline typename dtl::enable_if_trivially_destructible<I, void>::type
1063    destroy_alloc_n(Allocator &, I, U)
1064 {}
1065
1066 //////////////////////////////////////////////////////////////////////////////
1067 //
1068 //                               destroy_alloc
1069 //
1070 //////////////////////////////////////////////////////////////////////////////
1071
1072 template
1073    <typename Allocator
1074    ,typename I>   // I models InputIterator
1075 inline typename dtl::disable_if_trivially_destructible<I, void>::type
1076    destroy_alloc(Allocator &a, I f, I l)
1077 {
1078    while(f != l){
1079       allocator_traits<Allocator>::destroy(a, boost::movelib::iterator_to_raw_pointer(f));
1080       ++f;
1081    }
1082 }
1083
1084 template
1085    <typename Allocator
1086    ,typename I >  // I models InputIterator
1087 inline typename dtl::enable_if_trivially_destructible<I, void>::type
1088    destroy_alloc(Allocator &, I, I)
1089 {}
1090
1091 //////////////////////////////////////////////////////////////////////////////
1092 //
1093 //                         deep_swap_alloc_n
1094 //
1095 //////////////////////////////////////////////////////////////////////////////
1096
1097 template
1098    <std::size_t MaxTmpBytes
1099    ,typename Allocator
1100    ,typename F // F models ForwardIterator
1101    ,typename G // G models ForwardIterator
1102    >
1103 inline typename dtl::disable_if_memtransfer_copy_assignable<F, G, void>::type
1104    deep_swap_alloc_n( Allocator &a, F short_range_f, std::size_t  n_i, G large_range_f, std::size_t n_j)
1105 {
1106    std::size_t n = 0;
1107    for (; n != n_i ; ++short_range_f, ++large_range_f, ++n){
1108       boost::adl_move_swap(*short_range_f, *large_range_f);
1109    }
1110    boost::container::uninitialized_move_alloc_n(a, large_range_f, std::size_t(n_j - n_i), short_range_f);  // may throw
1111    boost::container::destroy_alloc_n(a, large_range_f, std::size_t(n_j - n_i));
1112 }
1113
1114 BOOST_CONTAINER_CONSTANT_VAR std::size_t DeepSwapAllocNMaxStorage = std::size_t(1) << std::size_t(11); //2K bytes
1115
1116 template
1117    <std::size_t MaxTmpBytes
1118    ,typename Allocator
1119    ,typename F // F models ForwardIterator
1120    ,typename G // G models ForwardIterator
1121    >
1122 inline typename dtl::enable_if_c
1123    < dtl::is_memtransfer_copy_assignable<F, G>::value && (MaxTmpBytes <= DeepSwapAllocNMaxStorage) && false
1124    , void>::type
1125    deep_swap_alloc_n( Allocator &a, F short_range_f, std::size_t n_i, G large_range_f, std::size_t n_j)
1126 {
1127    typedef typename allocator_traits<Allocator>::value_type value_type;
1128    typedef typename dtl::aligned_storage
1129       <MaxTmpBytes, dtl::alignment_of<value_type>::value>::type storage_type;
1130    storage_type storage;
1131
1132    const std::size_t n_i_bytes = sizeof(value_type)*n_i;
1133    void *const large_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f));
1134    void *const short_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f));
1135    void *const stora_ptr = static_cast<void*>(boost::movelib::iterator_to_raw_pointer(storage.data));
1136    std::memcpy(stora_ptr, large_ptr, n_i_bytes);
1137    std::memcpy(large_ptr, short_ptr, n_i_bytes);
1138    std::memcpy(short_ptr, stora_ptr, n_i_bytes);
1139    boost::container::iterator_uadvance(large_range_f, n_i);
1140    boost::container::iterator_uadvance(short_range_f, n_i);
1141    boost::container::uninitialized_move_alloc_n(a, large_range_f, std::size_t(n_j - n_i), short_range_f);  // may throw
1142    boost::container::destroy_alloc_n(a, large_range_f, std::size_t(n_j - n_i));
1143 }
1144
1145 template
1146    <std::size_t MaxTmpBytes
1147    ,typename Allocator
1148    ,typename F // F models ForwardIterator
1149    ,typename G // G models ForwardIterator
1150    >
1151 inline typename dtl::enable_if_c
1152    < dtl::is_memtransfer_copy_assignable<F, G>::value && true//(MaxTmpBytes > DeepSwapAllocNMaxStorage)
1153    , void>::type
1154    deep_swap_alloc_n( Allocator &a, F short_range_f, std::size_t n_i, G large_range_f, std::size_t n_j)
1155 {
1156    typedef typename allocator_traits<Allocator>::value_type value_type;
1157    typedef typename dtl::aligned_storage
1158       <DeepSwapAllocNMaxStorage, dtl::alignment_of<value_type>::value>::type storage_type;
1159    storage_type storage;
1160    const std::size_t sizeof_storage = sizeof(storage);
1161
1162    std::size_t n_i_bytes = sizeof(value_type)*n_i;
1163    char *large_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(large_range_f)));
1164    char *short_ptr = static_cast<char*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(short_range_f)));
1165    char *stora_ptr = static_cast<char*>(static_cast<void*>(storage.data));
1166
1167    std::size_t szt_times = n_i_bytes/sizeof_storage;
1168    const std::size_t szt_rem = n_i_bytes%sizeof_storage;
1169
1170    //Loop unrolling using Duff's device, as it seems it helps on some architectures
1171    const std::size_t Unroll = 4;
1172    std::size_t n = (szt_times + (Unroll-1))/Unroll;
1173    const std::size_t branch_number = (szt_times == 0)*Unroll + (szt_times % Unroll);
1174    switch(branch_number){
1175       case 4:
1176          break;
1177       case 0: do{
1178          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1179          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1180          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1181          large_ptr += sizeof_storage;
1182          short_ptr += sizeof_storage;
1183          BOOST_FALLTHROUGH;
1184       case 3:
1185          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1186          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1187          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1188          large_ptr += sizeof_storage;
1189          short_ptr += sizeof_storage;
1190          BOOST_FALLTHROUGH;
1191       case 2:
1192          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1193          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1194          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1195          large_ptr += sizeof_storage;
1196          short_ptr += sizeof_storage;
1197          BOOST_FALLTHROUGH;
1198       case 1:
1199          std::memcpy(stora_ptr, large_ptr, sizeof_storage);
1200          std::memcpy(large_ptr, short_ptr, sizeof_storage);
1201          std::memcpy(short_ptr, stora_ptr, sizeof_storage);
1202          large_ptr += sizeof_storage;
1203          short_ptr += sizeof_storage;
1204          } while(--n);
1205    }
1206    std::memcpy(stora_ptr, large_ptr, szt_rem);
1207    std::memcpy(large_ptr, short_ptr, szt_rem);
1208    std::memcpy(short_ptr, stora_ptr, szt_rem);
1209    boost::container::iterator_uadvance(large_range_f, n_i);
1210    boost::container::iterator_uadvance(short_range_f, n_i);
1211    boost::container::uninitialized_move_alloc_n(a, large_range_f, std::size_t(n_j - n_i), short_range_f);  // may throw
1212    boost::container::destroy_alloc_n(a, large_range_f, std::size_t(n_j - n_i));
1213 }
1214
1215
1216 //////////////////////////////////////////////////////////////////////////////
1217 //
1218 //                         copy_assign_range_alloc_n
1219 //
1220 //////////////////////////////////////////////////////////////////////////////
1221
1222 template
1223    <typename Allocator
1224    ,typename I // F models InputIterator
1225    ,typename O // G models OutputIterator
1226    >
1227 void copy_assign_range_alloc_n( Allocator &a, I inp_start, std::size_t n_i, O out_start, std::size_t n_o )
1228 {
1229    if (n_o < n_i){
1230       inp_start = boost::container::copy_n_source_dest(inp_start, n_o, out_start);     // may throw
1231       boost::container::uninitialized_copy_alloc_n(a, inp_start, std::size_t(n_i - n_o), out_start);// may throw
1232    }
1233    else{
1234       out_start = boost::container::copy_n(inp_start, n_i, out_start);  // may throw
1235       boost::container::destroy_alloc_n(a, out_start, std::size_t(n_o - n_i));
1236    }
1237 }
1238
1239 //////////////////////////////////////////////////////////////////////////////
1240 //
1241 //                         move_assign_range_alloc_n
1242 //
1243 //////////////////////////////////////////////////////////////////////////////
1244
1245 template
1246    <typename Allocator
1247    ,typename I // F models InputIterator
1248    ,typename O // G models OutputIterator
1249    >
1250 void move_assign_range_alloc_n( Allocator &a, I inp_start, std::size_t n_i, O out_start, std::size_t n_o )
1251 {
1252    if (n_o < n_i){
1253       inp_start = boost::container::move_n_source_dest(inp_start, n_o, out_start);  // may throw
1254       boost::container::uninitialized_move_alloc_n(a, inp_start, std::size_t(n_i - n_o), out_start);  // may throw
1255    }
1256    else{
1257       out_start = boost::container::move_n(inp_start, n_i, out_start);  // may throw
1258       boost::container::destroy_alloc_n(a, out_start, std::size_t(n_o - n_i));
1259    }
1260 }
1261
1262 template<class Allocator>
1263 struct array_destructor
1264 {
1265    typedef typename ::boost::container::allocator_traits<Allocator>::value_type value_type;
1266    typedef typename dtl::if_c
1267       <dtl::is_trivially_destructible<value_type>::value
1268       ,dtl::null_scoped_destructor_range<Allocator>
1269       ,dtl::scoped_destructor_range<Allocator>
1270       >::type type;
1271 };
1272
1273 template<class Allocator>
1274 struct value_destructor
1275 {
1276    typedef typename ::boost::container::allocator_traits<Allocator>::value_type value_type;
1277    typedef typename dtl::if_c
1278       <dtl::is_trivially_destructible<value_type>::value
1279       , dtl::null_scoped_destructor<Allocator>
1280       , dtl::scoped_destructor<Allocator>
1281       >::type type;
1282 };
1283
1284 template
1285    <typename Allocator
1286    ,typename F // F models ForwardIterator
1287    ,typename O // G models OutputIterator
1288    ,typename InsertionProxy
1289    >
1290 void uninitialized_move_and_insert_alloc
1291    ( Allocator &a
1292    , F first
1293    , F pos
1294    , F last
1295    , O d_first
1296    , std::size_t n
1297    , InsertionProxy insertion_proxy)
1298 {
1299    typedef typename array_destructor<Allocator>::type array_destructor_t;
1300
1301    //Anti-exception rollbacks
1302    array_destructor_t new_values_destroyer(d_first, d_first, a);
1303
1304    //Initialize with [begin(), pos) old buffer
1305    //the start of the new buffer
1306    O d_last = ::boost::container::uninitialized_move_alloc(a, first, pos, d_first);
1307    new_values_destroyer.set_end(d_last);
1308    //Initialize new objects, starting from previous point
1309    insertion_proxy.uninitialized_copy_n_and_update(a, d_last, n);
1310    d_last += n;
1311    new_values_destroyer.set_end(d_last);
1312    //Initialize from the rest of the old buffer,
1313    //starting from previous point
1314    (void) ::boost::container::uninitialized_move_alloc(a, pos, last, d_last);
1315    //All construction successful, disable rollbacks
1316    new_values_destroyer.release();
1317 }
1318
1319
1320
1321
1322 template
1323    <typename Allocator
1324    ,typename F // F models ForwardIterator
1325    ,typename InsertionProxy
1326    >
1327 typename dtl::enable_if_c<dtl::is_single_value_proxy<InsertionProxy>::value, void>::type
1328    expand_backward_and_insert_nonempty_middle_alloc
1329    ( Allocator &a
1330    , F const first
1331    , F const pos
1332    , std::size_t const
1333    , InsertionProxy insertion_proxy)
1334 {
1335    BOOST_ASSERT(first != pos);
1336
1337    typedef typename value_destructor<Allocator>::type value_destructor_t;
1338    F aux = first;   --aux;
1339    allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(aux), boost::move(*first));
1340    value_destructor_t on_exception(a, boost::movelib::iterator_to_raw_pointer(aux));
1341    //Copy previous to last objects to the initialized end
1342    aux = first; ++aux;
1343    aux = boost::container::move(aux, pos, first);
1344    //Insert new objects in the pos
1345    insertion_proxy.copy_n_and_update(a, aux, 1u);
1346    on_exception.release();
1347 }
1348
1349 template
1350    <typename Allocator
1351    ,typename F // F models ForwardIterator
1352    ,typename InsertionProxy
1353    >
1354 typename dtl::disable_if_c<dtl::is_single_value_proxy<InsertionProxy>::value, void>::type
1355    expand_backward_and_insert_nonempty_middle_alloc
1356    ( Allocator &a
1357    , F first
1358    , F pos
1359    , std::size_t const n
1360    , InsertionProxy insertion_proxy)
1361 {
1362    BOOST_ASSERT(first != pos);
1363    BOOST_ASSERT(n != 0);
1364
1365    typedef typename array_destructor<Allocator>::type array_destructor_t;
1366    const std::size_t elems_before = iterator_udistance(first, pos);
1367    if(elems_before >= n){
1368       //New elements can be just copied.
1369       //Move to uninitialized memory last objects
1370       F const first_less_n = first - n;
1371       F nxt = ::boost::container::uninitialized_move_alloc_n_source(a, first, n, first_less_n);
1372       array_destructor_t on_exception(first_less_n, first, a);
1373       //Copy previous to last objects to the initialized end
1374       nxt = boost::container::move(nxt, pos, first);
1375       //Insert new objects in the pos
1376       insertion_proxy.copy_n_and_update(a, nxt, n);
1377       on_exception.release();
1378    }
1379    else {
1380       //The new elements don't fit in the [pos, end()) range.
1381       //Copy old [pos, end()) elements to the uninitialized memory (a gap is created)
1382       F aux = ::boost::container::uninitialized_move_alloc(a, first, pos, first - n);
1383       array_destructor_t on_exception(first -n, aux, a);
1384       //Copy to the beginning of the unallocated zone the last new elements (the gap is closed).
1385       insertion_proxy.uninitialized_copy_n_and_update(a, aux, std::size_t(n - elems_before));
1386       insertion_proxy.copy_n_and_update(a, first, elems_before);
1387       on_exception.release();
1388    }
1389 }
1390
1391
1392 template
1393    <typename Allocator
1394    ,typename F // F models ForwardIterator
1395    ,typename InsertionProxy
1396    >
1397 typename dtl::enable_if_c<dtl::is_single_value_proxy<InsertionProxy>::value, void>::type
1398    expand_forward_and_insert_nonempty_middle_alloc
1399    ( Allocator &a
1400    , F pos
1401    , F last
1402    , std::size_t const
1403    , InsertionProxy insertion_proxy)
1404 {
1405    BOOST_ASSERT(last != pos);
1406
1407    typedef typename value_destructor<Allocator>::type value_destructor_t;
1408    F last_m_n = last;   --last_m_n;
1409    allocator_traits<Allocator>::construct(a, boost::movelib::iterator_to_raw_pointer(last), boost::move(*last_m_n));
1410    value_destructor_t on_exception(a, boost::movelib::iterator_to_raw_pointer(last));
1411    //Copy previous to last objects to the initialized end
1412    boost::container::move_backward(pos, last_m_n, last);
1413    //Insert new objects in the pos
1414    insertion_proxy.copy_n_and_update(a, pos, 1);
1415    on_exception.release();
1416 }
1417
1418 template
1419    <typename Allocator
1420    ,typename F // F models ForwardIterator
1421    ,typename InsertionProxy
1422    >
1423 typename dtl::disable_if_c<dtl::is_single_value_proxy<InsertionProxy>::value, void>::type
1424    expand_forward_and_insert_nonempty_middle_alloc
1425    ( Allocator &a
1426    , F pos
1427    , F last
1428    , std::size_t const n
1429    , InsertionProxy insertion_proxy)
1430 {
1431    BOOST_ASSERT(last != pos);
1432    BOOST_ASSERT(n != 0);
1433
1434    typedef typename array_destructor<Allocator>::type array_destructor_t;
1435    const std::size_t elems_after = iterator_udistance(pos, last);
1436    if(elems_after >= n){
1437       //New elements can be just copied.
1438       //Move to uninitialized memory last objects
1439       F const last_m_n = last - n;
1440       F const nxt = ::boost::container::uninitialized_move_alloc_n(a, last_m_n, n, last);
1441       array_destructor_t on_exception(last, nxt, a);
1442       //Copy previous to last objects to the initialized end
1443       boost::container::move_backward(pos, last_m_n, last);
1444       //Insert new objects in the pos
1445       insertion_proxy.copy_n_and_update(a, pos, n);
1446       on_exception.release();
1447    }
1448    else {
1449       //The new elements don't fit in the [pos, end()) range.
1450       //Copy old [pos, end()) elements to the uninitialized memory (a gap is created)
1451       F new_last = ::boost::container::uninitialized_move_alloc(a, pos, last, pos + n);
1452       array_destructor_t on_exception(pos + n, new_last, a);
1453       //Copy first new elements in pos (gap is still there)
1454       insertion_proxy.copy_n_and_update(a, pos, elems_after);
1455       //Copy to the beginning of the unallocated zone the last new elements (the gap is closed).
1456       insertion_proxy.uninitialized_copy_n_and_update(a, last, std::size_t(n - elems_after));
1457       on_exception.release();
1458    }
1459 }
1460
1461 template
1462 <typename Allocator
1463    , typename F // F models ForwardIterator
1464    , typename InsertionProxy
1465 >
1466 inline void expand_forward_and_insert_alloc
1467    ( Allocator& a
1468    , F pos
1469    , F last
1470    , std::size_t const n
1471    , InsertionProxy insertion_proxy)
1472 {
1473    if (last == pos) {
1474       insertion_proxy.uninitialized_copy_n_and_update(a, last, n);
1475    }
1476    else{
1477       const bool single_value = dtl::is_single_value_proxy<InsertionProxy>::value;
1478       BOOST_IF_CONSTEXPR(!single_value){
1479          if (BOOST_UNLIKELY(!n)) {
1480             return;
1481          }
1482       }
1483       expand_forward_and_insert_nonempty_middle_alloc(a, pos, last, n, insertion_proxy);
1484    }
1485 }
1486
1487 template <class B, class InsertionProxy, class Allocator>
1488 void expand_backward_forward_and_insert_alloc_move_backward
1489 ( B const old_start
1490 , std::size_t const old_size
1491 , B const new_start
1492 , B const pos
1493 , std::size_t const n
1494 , InsertionProxy insertion_proxy
1495 , Allocator& a)
1496 {
1497    typedef std::size_t size_type;
1498    typedef typename allocator_traits<Allocator>::value_type value_type;
1499    BOOST_STATIC_CONSTEXPR bool trivial_dctr_after_move = has_trivial_destructor_after_move<value_type>::value;
1500    BOOST_STATIC_CONSTEXPR bool trivial_dctr = dtl::is_trivially_destructible<value_type>::value;
1501
1502    typedef typename dtl::if_c
1503       <trivial_dctr
1504       , dtl::null_scoped_destructor_n<Allocator, B>
1505       , dtl::scoped_destructor_n<Allocator, B>
1506       >::type   array_destructor_t;
1507
1508    //n can be zero to just expand capacity
1509    B old_finish = make_iterator_uadvance(old_start, old_size);
1510
1511    //We can have 8 possibilities:
1512    const size_type elemsbefore = static_cast<size_type>(iterator_udistance(old_start, pos));
1513    const size_type raw_before  = static_cast<size_type>(iterator_udistance(new_start, old_start));
1514    const size_type before_plus_new = size_type(elemsbefore + n);
1515
1516    //Check if raw_before is big enough to hold the beginning of old data + new data
1517    if (raw_before >= before_plus_new) {
1518       //If anything goes wrong, this object will destroy
1519       //all the old objects to fulfill previous vector state
1520       array_destructor_t old_values_destroyer(old_start, a, old_size);
1521       // _________________________________________________________
1522       //|            raw_mem                | old_begin | old_end |  //Old situation
1523       //| __________________________________|___________|_________|
1524       // _________________________________________________________
1525       //| old_begin |    new   |  raw_mem   | old_begin | old_end |  //First step
1526       //|___________|__________|____________|___________|_________|
1527
1528       //Copy first old values before pos, after that the new objects
1529       B const new_elem_pos = ::boost::container::uninitialized_move_alloc(a, old_start, pos, new_start);
1530       array_destructor_t new_values_destroyer(new_start, a, elemsbefore);
1531       insertion_proxy.uninitialized_copy_n_and_update(a, new_elem_pos, n);
1532       new_values_destroyer.set_size(before_plus_new);
1533       const size_type new_size = size_type(old_size + n);
1534       //Check if raw_before is so big that even copying the old data + new data
1535       //there is a gap between the new data and the old data
1536       if (raw_before >= new_size) {
1537          // _______________________________________________________
1538          //|            raw_mem              | old_begin | old_end | //Old situation
1539          //|_________________________________|___________|_________|
1540          // _______________________________________________________
1541          //| old_begin |   new  |  raw_mem   | old_begin | old_end | //First step
1542          //|___________|________|____________|___________|_________|
1543          // _______________________________________________________
1544          //| old_begin |   new  | old_end |       raw_mem          | //New situation
1545          //|___________|________|_________|________________________|
1546          //
1547          //Now initialize the rest of memory with the last old values
1548          if (before_plus_new != new_size) { //Special case to avoid operations in back insertion
1549             B new_start_end(make_iterator_uadvance(new_start, before_plus_new));
1550             ::boost::container::uninitialized_move_alloc(a, pos, old_finish, new_start_end);
1551          }
1552          //All new elements correctly constructed, avoid new element destruction
1553          new_values_destroyer.release();
1554          //Old values destroyed automatically with "old_values_destroyer"
1555          //when "old_values_destroyer" goes out of scope unless the have trivial
1556          //destructor after move.
1557          if(trivial_dctr_after_move)
1558             old_values_destroyer.release();
1559       }
1560       //raw_before is so big that divides old_end
1561       else {
1562          // _________________________________________________
1563          //|               raw           | old_beg | old_end | //Old situation
1564          //|_____________________________|_________|_________|
1565          // _________________________________________________
1566          //| old_begin |    new   |  raw | old_beg | old_end | //First step
1567          //|___________|__________|______|_________|_________|
1568          // _________________________________________________
1569          //| old_begin |    new   | old_end |  raw_mem       | //New situation
1570          //|___________|__________|_________|________________|
1571
1572          //Now initialize the rest of memory with the last old values
1573          //All new elements correctly constructed, avoid new element destruction
1574          BOOST_IF_CONSTEXPR(!trivial_dctr) {
1575             //Now initialize the rest of raw_before memory with the
1576             //first of elements after new values
1577             const size_type raw_gap = raw_before - before_plus_new;
1578             B new_start_plus(make_iterator_uadvance(new_start, before_plus_new));
1579             ::boost::container::uninitialized_move_alloc_n(a, pos, raw_gap, new_start_plus);
1580             new_values_destroyer.release();
1581             old_values_destroyer.increment_size_backwards(raw_before);
1582             //Now move remaining last objects in the old buffer begin
1583             B remaining_pos(make_iterator_uadvance(pos, raw_gap));
1584             remaining_pos = ::boost::container::move_forward_overlapping(remaining_pos, old_finish, old_start);
1585             (void)remaining_pos;
1586             //Once moved, avoid calling the destructors if trivial after move
1587             if(!trivial_dctr_after_move) {
1588                boost::container::destroy_alloc(a, remaining_pos, old_finish);
1589             }
1590          }
1591          else { //If trivial destructor, we can uninitialized copy + copy in a single uninitialized copy
1592             ::boost::container::uninitialized_move_alloc_n
1593                (a, pos, static_cast<size_type>(old_finish - pos), make_iterator_uadvance(new_start, before_plus_new));
1594          }
1595          old_values_destroyer.release();
1596       }
1597    }
1598    else {
1599       //If anything goes wrong, this object will destroy
1600       //all the old objects to fulfill previous vector state
1601       array_destructor_t old_values_destroyer(old_start, a, old_size);
1602
1603       //Check if we have to do the insertion in two phases
1604       //since maybe raw_before is not big enough and
1605       //the buffer was expanded both sides
1606       // _________________________________________________
1607       //| raw_mem | old_begin + old_end |  raw_mem        | //Old situation
1608       //|_________|_____________________|_________________|
1609       // _________________________________________________
1610       //|     old_begin + new + old_end     |  raw_mem    | //New situation with do_after
1611       //|___________________________________|_____________|
1612       // _________________________________________________
1613       //| old_begin + new + old_end  |  raw_mem           | //New without do_after
1614       //|____________________________|____________________|
1615       //
1616       const bool do_after = n > raw_before;
1617
1618       //Now we can have two situations: the raw_mem of the
1619       //beginning divides the old_begin, or the new elements:
1620       if (raw_before <= elemsbefore) {
1621          //The raw memory divides the old_begin group:
1622          //
1623          //If we need two phase construction (do_after)
1624          //new group is divided in new = new_beg + new_end groups
1625          //In this phase only new_beg will be inserted
1626          //
1627          // _________________________________________________
1628          //| raw_mem | old_begin | old_end |  raw_mem        | //Old situation
1629          //|_________|___________|_________|_________________|
1630          // _________________________________________________
1631          //| old_begin | new_beg | old_end |  raw_mem        | //New situation with do_after(1),
1632          //|___________|_________|_________|_________________| //not definitive, pending operations
1633          // _________________________________________________
1634          //| old_begin | new | old_end |  raw_mem            | //New situation without do_after,
1635          //|___________|_____|_________|_____________________| //definitive.
1636          //
1637          //Copy the first part of old_begin to raw_mem
1638          ::boost::container::uninitialized_move_alloc_n(a, old_start, raw_before, new_start);
1639          //The buffer is all constructed until old_end,
1640          //so program trailing destruction and assign final size
1641          //if !do_after, raw_before+n otherwise.
1642          size_type new_1st_range;
1643          old_values_destroyer.increment_size_backwards(raw_before);
1644          new_1st_range = do_after ? raw_before : n;
1645
1646          //Now copy the second part of old_begin overwriting itself
1647          B const old_next(make_iterator_uadvance(old_start, raw_before));
1648          B const next = ::boost::container::move(old_next, pos, old_start);
1649          //Now copy the new_beg elements
1650          insertion_proxy.copy_n_and_update(a, next, new_1st_range);
1651
1652          //If there is no after work and the last old part needs to be moved to front, do it
1653          if (!do_after) {
1654             //Now displace old_end elements and destroy trailing
1655             B const new_first(make_iterator_uadvance(next, new_1st_range));
1656             B const p = ::boost::container::move_forward_overlapping(pos, old_finish, new_first);
1657             (void)p;
1658             if(!trivial_dctr_after_move)
1659                boost::container::destroy_alloc(a, p, old_finish);
1660          }
1661       }
1662       else {
1663          //If we have to expand both sides,
1664          //we will play if the first new values so
1665          //calculate the upper bound of new values
1666
1667          //The raw memory divides the new elements
1668          //
1669          //If we need two phase construction (do_after)
1670          //new group is divided in new = new_beg + new_end groups
1671          //In this phase only new_beg will be inserted
1672          //
1673          // ____________________________________________________
1674          //|   raw_mem     | old_begin | old_end |  raw_mem     | //Old situation
1675          //|_______________|___________|_________|______________|
1676          // ____________________________________________________
1677          //| old_begin |    new_beg    | old_end |  raw_mem     | //New situation with do_after(),
1678          //|___________|_______________|_________|______________| //not definitive, pending operations
1679          // ____________________________________________________
1680          //| old_begin | new | old_end |  raw_mem               | //New situation without do_after,
1681          //|___________|_____|_________|________________________| //definitive
1682          //
1683          //First copy whole old_begin and part of new to raw_mem
1684          B const new_pos = ::boost::container::uninitialized_move_alloc(a, old_start, pos, new_start);
1685          array_destructor_t new_values_destroyer(new_start, a, elemsbefore);
1686          const size_type mid_n = size_type(raw_before - elemsbefore);
1687          insertion_proxy.uninitialized_copy_n_and_update(a, new_pos, mid_n);
1688          new_values_destroyer.release();
1689          //The buffer is all constructed until old_end
1690          old_values_destroyer.increment_size_backwards(raw_before);
1691
1692          if (do_after) {
1693             //Copy new_beg part
1694             insertion_proxy.copy_n_and_update(a, old_start, elemsbefore);
1695          }
1696          else {
1697             //Copy all new elements
1698             const size_type rest_new = size_type(n - mid_n);
1699             insertion_proxy.copy_n_and_update(a, old_start, rest_new);
1700
1701             B move_start(make_iterator_uadvance(old_start, rest_new));
1702
1703             //Displace old_end, but make sure data has to be moved
1704             B const move_end = ::boost::container::move_forward_overlapping(pos, old_finish, move_start);
1705             (void)move_end;   //To avoid warnings of unused initialization for move_end in case
1706                               //trivial_dctr_after_move is true
1707             //Destroy remaining moved elements from old_end except if they
1708             //have trivial destructor after being moved
1709             if(!trivial_dctr_after_move) {
1710                boost::container::destroy_alloc(a, move_end, old_finish);
1711             }
1712          }
1713       }
1714
1715       //This is only executed if two phase construction is needed
1716       if (do_after) {
1717          //The raw memory divides the new elements
1718          // ______________________________________________________
1719          //|   raw_mem    | old_begin |  old_end   |  raw_mem     |  //Old situation
1720          //|______________|___________|____________|______________|
1721          // _______________________________________________________
1722          //| old_begin   +   new_beg  | new_end |old_end | rawmem |  //New situation with do_after(1)
1723          //|__________________________|_________|________|________|
1724          // ______________________________________________________
1725          //| old_begin      +       new            | old_end |raw |  //New situation with do_after(2)
1726          //|_______________________________________|_________|____|
1727          const size_type n_after = size_type(n - raw_before);
1728          const size_type elemsafter = size_type(old_size - elemsbefore);
1729
1730          //We can have two situations:
1731          if (elemsafter >= n_after) {
1732             //The raw_mem from end will divide displaced old_end
1733             //
1734             //Old situation:
1735             // ______________________________________________________
1736             //|   raw_mem    | old_begin |  old_end   |  raw_mem     |
1737             //|______________|___________|____________|______________|
1738             //
1739             //New situation with do_after(1):
1740             // _______________________________________________________
1741             //| old_begin   +   new_beg  | new_end |old_end | raw_mem |
1742             //|__________________________|_________|________|_________|
1743             //
1744             //First copy the part of old_end raw_mem
1745             B finish_n = make_iterator_advance(old_finish, -std::ptrdiff_t(n_after));
1746             ::boost::container::uninitialized_move_alloc(a, finish_n, old_finish, old_finish);
1747             old_values_destroyer.increment_size(n_after);
1748             //Displace the rest of old_end to the new position
1749             boost::container::move_backward_overlapping(pos, finish_n, old_finish);
1750             //Now overwrite with new_end
1751             //The new_end part is [first + (n - n_after), last)
1752             insertion_proxy.copy_n_and_update(a, pos, n_after);
1753          }
1754          else {
1755             //The raw_mem from end will divide new_end part
1756             // _____________________________________________________________
1757             //|   raw_mem    | old_begin |  old_end   |  raw_mem            | //Old situation
1758             //|______________|___________|____________|_____________________|
1759             // _____________________________________________________________
1760             //| old_begin   +   new_beg  |     new_end   |old_end | raw_mem | //New situation with do_after(2)
1761             //|__________________________|_______________|________|_________|
1762
1763             //First initialize data in raw memory
1764             const size_type mid_last_dist = size_type(n_after - elemsafter);
1765
1766             //Copy to the old_end part to the uninitialized zone leaving a gap.
1767             B const mid_last(make_iterator_uadvance(old_finish, mid_last_dist));
1768             ::boost::container::uninitialized_move_alloc(a, pos, old_finish, mid_last);
1769
1770             array_destructor_t old_end_destroyer(mid_last, a, iterator_udistance(pos, old_finish));
1771
1772             //Copy the first part to the already constructed old_end zone
1773             insertion_proxy.copy_n_and_update(a, pos, elemsafter);
1774             //Copy the rest to the uninitialized zone filling the gap
1775             insertion_proxy.uninitialized_copy_n_and_update(a, old_finish, mid_last_dist);
1776             old_end_destroyer.release();
1777          }
1778       }
1779       old_values_destroyer.release();
1780    }
1781 }
1782
1783 template
1784 <typename Allocator
1785    , typename B // B models BidirIterator
1786    , typename InsertionProxy
1787 >
1788 inline void expand_backward_forward_and_insert_alloc_move_forward
1789    ( B const old_start
1790    , std::size_t const old_size
1791    , B const new_start
1792    , B const pos
1793    , std::size_t const n
1794    , InsertionProxy insertion_proxy
1795    , Allocator& a)
1796 {
1797    typedef std::size_t size_type;
1798    typedef typename allocator_traits<Allocator>::value_type value_type;
1799    BOOST_STATIC_CONSTEXPR bool trivial_dctr_after_move = has_trivial_destructor_after_move<value_type>::value;
1800    BOOST_STATIC_CONSTEXPR bool trivial_dctr = dtl::is_trivially_destructible<value_type>::value;
1801
1802    typedef typename dtl::if_c
1803       <trivial_dctr
1804       , dtl::null_scoped_destructor_n<Allocator, B>
1805       , dtl::scoped_destructor_n<Allocator, B>
1806       >::type   array_destructor_t;
1807
1808    //n can be zero to just expand capacity
1809
1810    B const old_finish = make_iterator_uadvance(old_start, old_size);
1811    const size_type new_size = size_type(old_size + n);
1812    B const new_finish = make_iterator_uadvance(new_start, new_size);
1813
1814    //We can have 8 possibilities:
1815
1816    const size_type elemsafter = static_cast<size_type>(iterator_udistance(pos, old_finish));
1817    const size_type raw_after = static_cast<size_type>(iterator_udistance(old_finish, new_finish));
1818
1819    const size_type after_plus_new = size_type(elemsafter + n);
1820
1821    //Check if raw_before is big enough to hold the new data + the end of old data
1822    if (raw_after >= after_plus_new) {
1823       //If anything goes wrong, this object will destroy
1824       //all the old objects to fulfill previous vector state
1825       array_destructor_t old_values_destroyer(old_start, a, old_size);
1826       //______________________ __________________________________
1827       //| old_begin | old_end |            raw_mem                  //Old situation
1828       //|___________|_________|__________________________________
1829       // _____________________ _________________________________
1830       //| old_begin | old_end |  raw_mem |    new   |  old_end  |  //First step
1831       //|___________|_________|__________|__________|___________|
1832
1833       //Copy first new objects, after that old values after pos
1834       B new_elem_pos = new_finish - after_plus_new;
1835       insertion_proxy.uninitialized_copy_n_and_update(a, new_elem_pos, n);
1836       array_destructor_t new_values_destroyer(new_elem_pos, a, n);
1837       ::boost::container::uninitialized_move_alloc(a, pos, old_finish, new_elem_pos+n);
1838       new_values_destroyer.set_size(after_plus_new);
1839
1840       //Check if raw_before is so big that even copying the old data + new data
1841       //there is a gap between the new data and the old data
1842       if (raw_after >= new_size) {
1843          //______________________ __________________________________
1844          //| old_begin | old_end |            raw_mem                  //Old situation
1845          //|___________|_________|__________________________________
1846          // _____________________ _________________________________
1847          //| old_begin | old_end |    raw_mem   |   new  | old_end |  //First step
1848          //|___________|_________|______________|________|_________|
1849          // _____________________V_________________________________
1850          //|       raw_mem          | old_begin |   new  | old_end | //New situation
1851          //|________________________|___________|________|_________|
1852          //
1853          //Now initialize the rest of memory with the last old values
1854          ::boost::container::uninitialized_move_alloc(a, old_start, pos, new_start);
1855          //All new elements correctly constructed, avoid new element destruction
1856          new_values_destroyer.release();
1857          //Old values destroyed automatically with "old_values_destroyer"
1858          //when "old_values_destroyer" goes out of scope unless the have trivial
1859          //destructor after move.
1860          if(trivial_dctr_after_move)
1861             old_values_destroyer.release();
1862       }
1863       //raw_before is so big that divides old_end
1864       else {
1865          //______________________ ____________________________
1866          //| old_begin | old_end |          raw_mem             //Old situation
1867          //|___________|_________|____________________________
1868          // _____________________ ____________________________
1869          //| old_begin | old_end | raw_mem |   new  | old_end | //First step
1870          //|___________|_________|_________|________|_________|
1871          // _________________________________________________
1872          //|       raw_mem     | old_begin |   new  | old_end | //New situation
1873          //|___________________|___________|________|_________|
1874
1875          //Now initialize the rest of raw_before memory with the
1876          //last elements before new values
1877          const size_type raw_gap = raw_after - after_plus_new;
1878          B const pre_pos_raw = pos - raw_gap;
1879          ::boost::container::uninitialized_move_alloc_n(a, pre_pos_raw, raw_gap, old_finish);
1880          new_values_destroyer.release();
1881          old_values_destroyer.increment_size(raw_after);
1882          //Now move remaining last objects in the old buffer begin
1883          BOOST_ASSERT(old_start != old_finish);
1884          boost::container::move_backward_overlapping(old_start, pre_pos_raw, old_finish);
1885          old_values_destroyer.release();
1886          if (!trivial_dctr_after_move) {
1887             boost::container::destroy_alloc(a, old_start, new_start);
1888          }
1889       }
1890    }
1891    else{
1892       //If anything goes wrong, this object will destroy
1893       //all the old objects to fulfill previous vector state
1894       array_destructor_t old_values_destroyer(old_start, a, old_size);
1895
1896       //Now we can have two situations: the raw_mem of the
1897       //end divides the new elements or the old_end
1898       if (raw_after > elemsafter) {
1899          //The raw memory divides the new elements
1900          //__________________________________
1901          //| old_begin | old_end |    raw    |  //Old situation
1902          //|___________|_________|___________|
1903          // _____ ___________________________
1904          //| raw | old_begin | new | old_end |  //New situation
1905          //|_____|___________|_____|_________|
1906
1907          //First copy whole old_end and part of new to raw_mem
1908          B p = new_finish - elemsafter;
1909          ::boost::container::uninitialized_move_alloc(a, pos, old_finish, p);
1910          array_destructor_t new_values_destroyer(p, a, elemsafter);
1911          //Copy all new elements
1912          const size_type mid_n = size_type(raw_after - elemsafter);
1913          const size_type rest_new = size_type(n - mid_n);
1914          B new_rng_start = old_finish - rest_new;
1915          insertion_proxy.copy_n_and_update(a, new_rng_start, rest_new);
1916          insertion_proxy.uninitialized_copy_n_and_update(a, old_finish, mid_n);
1917          new_values_destroyer.release();
1918          old_values_destroyer.increment_size_backwards(raw_after);
1919          //Displace old_end, but make sure data has to be moved
1920          p = ::boost::container::move_backward_overlapping(old_start, pos, new_rng_start);
1921
1922          //Destroy remaining moved elements from old_begin except if they
1923          //have trivial destructor after being moved
1924          old_values_destroyer.release();
1925          if (!trivial_dctr_after_move) {
1926             boost::container::destroy_alloc(a, old_start, p);
1927          }
1928       }
1929       else {
1930          //The raw memory divides the old_end group:
1931          //________________________________________
1932          //| old_begin |    old_end    |      raw  |  //Old situation
1933          //|___________|_______________|___________|
1934          // _____ __________________________________
1935          //| raw | old_begin | new |    old_end    |  //New situation
1936          //|_____|___________|_____|_______________|
1937          //
1938          //Copy the last part of old_end to raw_mem
1939          const B old_end_pivot = old_finish - raw_after;
1940          ::boost::container::uninitialized_move_alloc_n(a, old_end_pivot, raw_after, old_finish);
1941          //The buffer is all constructed
1942          old_values_destroyer.increment_size_backwards(raw_after);
1943
1944          //Now copy the first part of old_end overwriting itself
1945          B const new_end_pos = ::boost::container::move_backward_overlapping(pos, old_end_pivot, old_finish);
1946          B const new_beg_pos = new_end_pos - n;
1947
1948          //Now copy the new_beg elements
1949          insertion_proxy.copy_n_and_update(a, new_beg_pos, n);
1950          B const p = ::boost::container::move_backward_overlapping(old_start, pos, new_beg_pos);
1951          old_values_destroyer.release();
1952
1953          if (!trivial_dctr_after_move) {
1954             (void)p;
1955             boost::container::destroy_alloc(a, old_start, p);
1956          }
1957       }
1958    }
1959 }
1960
1961 template <class R, class InsertionProxy, class Allocator>
1962 void expand_backward_forward_and_insert_alloc
1963    ( R const old_start
1964    , std::size_t const old_size
1965    , R const new_start
1966    , R const pos
1967    , std::size_t const n
1968    , InsertionProxy insertion_proxy
1969    , Allocator& a)
1970 {
1971    if(new_start < old_start){
1972       expand_backward_forward_and_insert_alloc_move_backward(old_start, old_size, new_start, pos, n, insertion_proxy, a);
1973    }
1974    else{
1975       expand_backward_forward_and_insert_alloc_move_forward(old_start, old_size, new_start, pos, n, insertion_proxy, a);
1976    }
1977 }
1978
1979 }  //namespace container {
1980 }  //namespace boost {
1981
1982 //#pragma GCC diagnostic ignored "-Wclass-memaccess"
1983 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
1984 #pragma GCC diagnostic pop
1985 #endif
1986
1987 #endif   //#ifndef BOOST_CONTAINER_DETAIL_COPY_MOVE_ALGO_HPP