include/__split_buffer

   1 // -*- C++ -*-
   2 #ifndef _LIBCPP_SPLIT_BUFFER
   3 #define _LIBCPP_SPLIT_BUFFER
   4
   5 #include <__config>
   6 #include <type_traits>
   7 #include <algorithm>
   8
   9 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  10 #pragma GCC system_header
  11 #endif
  12
  13 _LIBCPP_PUSH_MACROS
  14 #include <__undef_macros>
  15
  16
  17 _LIBCPP_BEGIN_NAMESPACE_STD
  18
  19 template <bool>
  20 class __split_buffer_common
  21 {
  22 protected:
  23     void __throw_length_error() const;
  24     void __throw_out_of_range() const;
  25 };
  26
  27 template <class _Tp, class _Allocator = allocator<_Tp> >
  28 struct __split_buffer
  29     : private __split_buffer_common<true>
  30 {
  31 private:
  32     __split_buffer(const __split_buffer&);
  33     __split_buffer& operator=(const __split_buffer&);
  34 public:
  35     typedef _Tp                                             value_type;
  36     typedef _Allocator                                      allocator_type;
  37     typedef typename remove_reference<allocator_type>::type __alloc_rr;
  38     typedef allocator_traits<__alloc_rr>                    __alloc_traits;
  39     typedef value_type&                                     reference;
  40     typedef const value_type&                               const_reference;
  41     typedef typename __alloc_traits::size_type              size_type;
  42     typedef typename __alloc_traits::difference_type        difference_type;
  43     typedef typename __alloc_traits::pointer                pointer;
  44     typedef typename __alloc_traits::const_pointer          const_pointer;
  45     typedef pointer                                         iterator;
  46     typedef const_pointer                                   const_iterator;
  47
  48     pointer                                         __first_;
  49     pointer                                         __begin_;
  50     pointer                                         __end_;
  51     __compressed_pair<pointer, allocator_type> __end_cap_;
  52
  53     typedef typename add_lvalue_reference<allocator_type>::type __alloc_ref;
  54     typedef typename add_lvalue_reference<allocator_type>::type __alloc_const_ref;
  55
  56     _LIBCPP_INLINE_VISIBILITY __alloc_rr&           __alloc() _NOEXCEPT         {return __end_cap_.second();}
  57     _LIBCPP_INLINE_VISIBILITY const __alloc_rr&     __alloc() const _NOEXCEPT   {return __end_cap_.second();}
  58     _LIBCPP_INLINE_VISIBILITY pointer&              __end_cap() _NOEXCEPT       {return __end_cap_.first();}
  59     _LIBCPP_INLINE_VISIBILITY const pointer&        __end_cap() const _NOEXCEPT {return __end_cap_.first();}
  60
  61     _LIBCPP_INLINE_VISIBILITY
  62     __split_buffer()
  63         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
  64     _LIBCPP_INLINE_VISIBILITY
  65     explicit __split_buffer(__alloc_rr& __a);
  66     _LIBCPP_INLINE_VISIBILITY
  67     explicit __split_buffer(const __alloc_rr& __a);
  68     __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);
  69     ~__split_buffer();
  70
  71 #ifndef _LIBCPP_CXX03_LANG
  72     __split_buffer(__split_buffer&& __c)
  73         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
  74     __split_buffer(__split_buffer&& __c, const __alloc_rr& __a);
  75     __split_buffer& operator=(__split_buffer&& __c)
  76         _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
  77                 is_nothrow_move_assignable<allocator_type>::value) ||
  78                !__alloc_traits::propagate_on_container_move_assignment::value);
  79 #endif  // _LIBCPP_CXX03_LANG
  80
  81     _LIBCPP_INLINE_VISIBILITY       iterator begin() _NOEXCEPT       {return __begin_;}
  82     _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __begin_;}
  83     _LIBCPP_INLINE_VISIBILITY       iterator end() _NOEXCEPT         {return __end_;}
  84     _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT   {return __end_;}
  85
  86     _LIBCPP_INLINE_VISIBILITY
  87     void clear() _NOEXCEPT
  88         {__destruct_at_end(__begin_);}
  89     _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(__end_ - __begin_);}
  90     _LIBCPP_INLINE_VISIBILITY bool empty()     const {return __end_ == __begin_;}
  91     _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __first_);}
  92     _LIBCPP_INLINE_VISIBILITY size_type __front_spare() const {return static_cast<size_type>(__begin_ - __first_);}
  93     _LIBCPP_INLINE_VISIBILITY size_type __back_spare() const {return static_cast<size_type>(__end_cap() - __end_);}
  94
  95     _LIBCPP_INLINE_VISIBILITY       reference front()       {return *__begin_;}
  96     _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *__begin_;}
  97     _LIBCPP_INLINE_VISIBILITY       reference back()        {return *(__end_ - 1);}
  98     _LIBCPP_INLINE_VISIBILITY const_reference back() const  {return *(__end_ - 1);}
  99
 100     void reserve(size_type __n);
 101     void shrink_to_fit() _NOEXCEPT;
 102     void push_front(const_reference __x);
 103     _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
 104 #ifndef _LIBCPP_CXX03_LANG
 105     void push_front(value_type&& __x);
 106     void push_back(value_type&& __x);
 107     template <class... _Args>
 108         void emplace_back(_Args&&... __args);
 109 #endif  // !defined(_LIBCPP_CXX03_LANG)
 110
 111     _LIBCPP_INLINE_VISIBILITY void pop_front() {__destruct_at_begin(__begin_+1);}
 112     _LIBCPP_INLINE_VISIBILITY void pop_back() {__destruct_at_end(__end_-1);}
 113
 114     void __construct_at_end(size_type __n);
 115     void __construct_at_end(size_type __n, const_reference __x);
 116     template <class _InputIter>
 117         typename enable_if
 118         <
 119             __is_input_iterator<_InputIter>::value &&
 120            !__is_forward_iterator<_InputIter>::value,
 121             void
 122         >::type
 123         __construct_at_end(_InputIter __first, _InputIter __last);
 124     template <class _ForwardIterator>
 125         typename enable_if
 126         <
 127             __is_forward_iterator<_ForwardIterator>::value,
 128             void
 129         >::type
 130         __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
 131
 132     _LIBCPP_INLINE_VISIBILITY void __destruct_at_begin(pointer __new_begin)
 133         {__destruct_at_begin(__new_begin, is_trivially_destructible<value_type>());}
 134         _LIBCPP_INLINE_VISIBILITY
 135         void __destruct_at_begin(pointer __new_begin, false_type);
 136         _LIBCPP_INLINE_VISIBILITY
 137         void __destruct_at_begin(pointer __new_begin, true_type);
 138
 139     _LIBCPP_INLINE_VISIBILITY
 140     void __destruct_at_end(pointer __new_last) _NOEXCEPT
 141         {__destruct_at_end(__new_last, false_type());}
 142     _LIBCPP_INLINE_VISIBILITY
 143         void __destruct_at_end(pointer __new_last, false_type) _NOEXCEPT;
 144     _LIBCPP_INLINE_VISIBILITY
 145         void __destruct_at_end(pointer __new_last, true_type) _NOEXCEPT;
 146
 147     void swap(__split_buffer& __x)
 148         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
 149                    __is_nothrow_swappable<__alloc_rr>::value);
 150
 151     bool __invariants() const;
 152
 153 private:
 154     _LIBCPP_INLINE_VISIBILITY
 155     void __move_assign_alloc(__split_buffer& __c, true_type)
 156         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
 157         {
 158             __alloc() = _VSTD::move(__c.__alloc());
 159         }
 160
 161     _LIBCPP_INLINE_VISIBILITY
 162     void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT
 163         {}
 164
 165     struct _ConstructTransaction {
 166       explicit _ConstructTransaction(pointer* __p, size_type __n) _NOEXCEPT
 167       : __pos_(*__p), __end_(*__p + __n), __dest_(__p) {
 168       }
 169       ~_ConstructTransaction() {
 170         *__dest_ = __pos_;
 171       }
 172       pointer __pos_;
 173      const pointer __end_;
 174     private:
 175      pointer *__dest_;
 176     };
 177 };
 178
 179 template <class _Tp, class _Allocator>
 180 bool
 181 __split_buffer<_Tp, _Allocator>::__invariants() const
 182 {
 183     if (__first_ == nullptr)
 184     {
 185         if (__begin_ != nullptr)
 186             return false;
 187         if (__end_ != nullptr)
 188             return false;
 189         if (__end_cap() != nullptr)
 190             return false;
 191     }
 192     else
 193     {
 194         if (__begin_ < __first_)
 195             return false;
 196         if (__end_ < __begin_)
 197             return false;
 198         if (__end_cap() < __end_)
 199             return false;
 200     }
 201     return true;
 202 }
 203
 204 //  Default constructs __n objects starting at __end_
 205 //  throws if construction throws
 206 //  Precondition:  __n > 0
 207 //  Precondition:  size() + __n <= capacity()
 208 //  Postcondition:  size() == size() + __n
 209 template <class _Tp, class _Allocator>
 210 void
 211 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n)
 212 {
 213     _ConstructTransaction __tx(&this->__end_, __n);
 214     for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
 215         __alloc_traits::construct(this->__alloc(), _VSTD::__to_raw_pointer(__tx.__pos_));
 216     }
 217 }
 218
 219 //  Copy constructs __n objects starting at __end_ from __x
 220 //  throws if construction throws
 221 //  Precondition:  __n > 0
 222 //  Precondition:  size() + __n <= capacity()
 223 //  Postcondition:  size() == old size() + __n
 224 //  Postcondition:  [i] == __x for all i in [size() - __n, __n)
 225 template <class _Tp, class _Allocator>
 226 void
 227 __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
 228 {
 229     _ConstructTransaction __tx(&this->__end_, __n);
 230     for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
 231         __alloc_traits::construct(this->__alloc(),
 232             _VSTD::__to_raw_pointer(__tx.__pos_), __x);
 233     }
 234 }
 235
 236 template <class _Tp, class _Allocator>
 237 template <class _InputIter>
 238 typename enable_if
 239 <
 240      __is_input_iterator<_InputIter>::value &&
 241     !__is_forward_iterator<_InputIter>::value,
 242     void
 243 >::type
 244 __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last)
 245 {
 246     __alloc_rr& __a = this->__alloc();
 247     for (; __first != __last; ++__first)
 248     {
 249         if (__end_ == __end_cap())
 250         {
 251             size_type __old_cap = __end_cap() - __first_;
 252             size_type __new_cap = _VSTD::max<size_type>(2 * __old_cap, 8);
 253             __split_buffer __buf(__new_cap, 0, __a);
 254             for (pointer __p = __begin_; __p != __end_; ++__p, ++__buf.__end_)
 255                 __alloc_traits::construct(__buf.__alloc(),
 256                         _VSTD::__to_raw_pointer(__buf.__end_), _VSTD::move(*__p));
 257             swap(__buf);
 258         }
 259         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
 260         ++this->__end_;
 261     }
 262 }
 263
 264 template <class _Tp, class _Allocator>
 265 template <class _ForwardIterator>
 266 typename enable_if
 267 <
 268     __is_forward_iterator<_ForwardIterator>::value,
 269     void
 270 >::type
 271 __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
 272 {
 273     _ConstructTransaction __tx(&this->__end_, std::distance(__first, __last));
 274     for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, ++__first) {
 275         __alloc_traits::construct(this->__alloc(),
 276             _VSTD::__to_raw_pointer(__tx.__pos_), *__first);
 277     }
 278 }
 279
 280 template <class _Tp, class _Allocator>
 281 inline
 282 void
 283 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
 284 {
 285     while (__begin_ != __new_begin)
 286         __alloc_traits::destroy(__alloc(), __to_raw_pointer(__begin_++));
 287 }
 288
 289 template <class _Tp, class _Allocator>
 290 inline
 291 void
 292 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type)
 293 {
 294     __begin_ = __new_begin;
 295 }
 296
 297 template <class _Tp, class _Allocator>
 298 inline _LIBCPP_INLINE_VISIBILITY
 299 void
 300 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
 301 {
 302     while (__new_last != __end_)
 303         __alloc_traits::destroy(__alloc(), __to_raw_pointer(--__end_));
 304 }
 305
 306 template <class _Tp, class _Allocator>
 307 inline _LIBCPP_INLINE_VISIBILITY
 308 void
 309 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
 310 {
 311     __end_ = __new_last;
 312 }
 313
 314 template <class _Tp, class _Allocator>
 315 __split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a)
 316     : __end_cap_(nullptr, __a)
 317 {
 318     __first_ = __cap != 0 ? __alloc_traits::allocate(__alloc(), __cap) : nullptr;
 319     __begin_ = __end_ = __first_ + __start;
 320     __end_cap() = __first_ + __cap;
 321 }
 322
 323 template <class _Tp, class _Allocator>
 324 inline
 325 __split_buffer<_Tp, _Allocator>::__split_buffer()
 326     _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 327     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr)
 328 {
 329 }
 330
 331 template <class _Tp, class _Allocator>
 332 inline
 333 __split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a)
 334     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
 335 {
 336 }
 337
 338 template <class _Tp, class _Allocator>
 339 inline
 340 __split_buffer<_Tp, _Allocator>::__split_buffer(const __alloc_rr& __a)
 341     : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a)
 342 {
 343 }
 344
 345 template <class _Tp, class _Allocator>
 346 __split_buffer<_Tp, _Allocator>::~__split_buffer()
 347 {
 348     clear();
 349     if (__first_)
 350         __alloc_traits::deallocate(__alloc(), __first_, capacity());
 351 }
 352
 353 #ifndef _LIBCPP_CXX03_LANG
 354
 355 template <class _Tp, class _Allocator>
 356 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c)
 357     _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 358     : __first_(_VSTD::move(__c.__first_)),
 359       __begin_(_VSTD::move(__c.__begin_)),
 360       __end_(_VSTD::move(__c.__end_)),
 361       __end_cap_(_VSTD::move(__c.__end_cap_))
 362 {
 363     __c.__first_ = nullptr;
 364     __c.__begin_ = nullptr;
 365     __c.__end_ = nullptr;
 366     __c.__end_cap() = nullptr;
 367 }
 368
 369 template <class _Tp, class _Allocator>
 370 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a)
 371     : __end_cap_(__second_tag(), __a)
 372 {
 373     if (__a == __c.__alloc())
 374     {
 375         __first_ = __c.__first_;
 376         __begin_ = __c.__begin_;
 377         __end_ = __c.__end_;
 378         __end_cap() = __c.__end_cap();
 379         __c.__first_ = nullptr;
 380         __c.__begin_ = nullptr;
 381         __c.__end_ = nullptr;
 382         __c.__end_cap() = nullptr;
 383     }
 384     else
 385     {
 386         size_type __cap = __c.size();
 387         __first_ = __alloc_traits::allocate(__alloc(), __cap);
 388         __begin_ = __end_ = __first_;
 389         __end_cap() = __first_ + __cap;
 390         typedef move_iterator<iterator> _Ip;
 391         __construct_at_end(_Ip(__c.begin()), _Ip(__c.end()));
 392     }
 393 }
 394
 395 template <class _Tp, class _Allocator>
 396 __split_buffer<_Tp, _Allocator>&
 397 __split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c)
 398     _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value &&
 399                 is_nothrow_move_assignable<allocator_type>::value) ||
 400                !__alloc_traits::propagate_on_container_move_assignment::value)
 401 {
 402     clear();
 403     shrink_to_fit();
 404     __first_ = __c.__first_;
 405     __begin_ = __c.__begin_;
 406     __end_ = __c.__end_;
 407     __end_cap() = __c.__end_cap();
 408     __move_assign_alloc(__c,
 409         integral_constant<bool,
 410                           __alloc_traits::propagate_on_container_move_assignment::value>());
 411     __c.__first_ = __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
 412     return *this;
 413 }
 414
 415 #endif  // _LIBCPP_CXX03_LANG
 416
 417 template <class _Tp, class _Allocator>
 418 void
 419 __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
 420         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
 421                    __is_nothrow_swappable<__alloc_rr>::value)
 422 {
 423     _VSTD::swap(__first_, __x.__first_);
 424     _VSTD::swap(__begin_, __x.__begin_);
 425     _VSTD::swap(__end_, __x.__end_);
 426     _VSTD::swap(__end_cap(), __x.__end_cap());
 427     __swap_allocator(__alloc(), __x.__alloc());
 428 }
 429
 430 template <class _Tp, class _Allocator>
 431 void
 432 __split_buffer<_Tp, _Allocator>::reserve(size_type __n)
 433 {
 434     if (__n < capacity())
 435     {
 436         __split_buffer<value_type, __alloc_rr&> __t(__n, 0, __alloc());
 437         __t.__construct_at_end(move_iterator<pointer>(__begin_),
 438                                move_iterator<pointer>(__end_));
 439         _VSTD::swap(__first_, __t.__first_);
 440         _VSTD::swap(__begin_, __t.__begin_);
 441         _VSTD::swap(__end_, __t.__end_);
 442         _VSTD::swap(__end_cap(), __t.__end_cap());
 443     }
 444 }
 445
 446 template <class _Tp, class _Allocator>
 447 void
 448 __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
 449 {
 450     if (capacity() > size())
 451     {
 452 #ifndef _LIBCPP_NO_EXCEPTIONS
 453         try
 454         {
 455 #endif  // _LIBCPP_NO_EXCEPTIONS
 456             __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc());
 457             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 458                                    move_iterator<pointer>(__end_));
 459             __t.__end_ = __t.__begin_ + (__end_ - __begin_);
 460             _VSTD::swap(__first_, __t.__first_);
 461             _VSTD::swap(__begin_, __t.__begin_);
 462             _VSTD::swap(__end_, __t.__end_);
 463             _VSTD::swap(__end_cap(), __t.__end_cap());
 464 #ifndef _LIBCPP_NO_EXCEPTIONS
 465         }
 466         catch (...)
 467         {
 468         }
 469 #endif  // _LIBCPP_NO_EXCEPTIONS
 470     }
 471 }
 472
 473 template <class _Tp, class _Allocator>
 474 void
 475 __split_buffer<_Tp, _Allocator>::push_front(const_reference __x)
 476 {
 477     if (__begin_ == __first_)
 478     {
 479         if (__end_ < __end_cap())
 480         {
 481             difference_type __d = __end_cap() - __end_;
 482             __d = (__d + 1) / 2;
 483             __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
 484             __end_ += __d;
 485         }
 486         else
 487         {
 488             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 489             __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
 490             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 491                                    move_iterator<pointer>(__end_));
 492             _VSTD::swap(__first_, __t.__first_);
 493             _VSTD::swap(__begin_, __t.__begin_);
 494             _VSTD::swap(__end_, __t.__end_);
 495             _VSTD::swap(__end_cap(), __t.__end_cap());
 496         }
 497     }
 498     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1), __x);
 499     --__begin_;
 500 }
 501
 502 #ifndef _LIBCPP_CXX03_LANG
 503
 504 template <class _Tp, class _Allocator>
 505 void
 506 __split_buffer<_Tp, _Allocator>::push_front(value_type&& __x)
 507 {
 508     if (__begin_ == __first_)
 509     {
 510         if (__end_ < __end_cap())
 511         {
 512             difference_type __d = __end_cap() - __end_;
 513             __d = (__d + 1) / 2;
 514             __begin_ = _VSTD::move_backward(__begin_, __end_, __end_ + __d);
 515             __end_ += __d;
 516         }
 517         else
 518         {
 519             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 520             __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc());
 521             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 522                                    move_iterator<pointer>(__end_));
 523             _VSTD::swap(__first_, __t.__first_);
 524             _VSTD::swap(__begin_, __t.__begin_);
 525             _VSTD::swap(__end_, __t.__end_);
 526             _VSTD::swap(__end_cap(), __t.__end_cap());
 527         }
 528     }
 529     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__begin_-1),
 530             _VSTD::move(__x));
 531     --__begin_;
 532 }
 533
 534 #endif  // _LIBCPP_CXX03_LANG
 535
 536 template <class _Tp, class _Allocator>
 537 inline _LIBCPP_INLINE_VISIBILITY
 538 void
 539 __split_buffer<_Tp, _Allocator>::push_back(const_reference __x)
 540 {
 541     if (__end_ == __end_cap())
 542     {
 543         if (__begin_ > __first_)
 544         {
 545             difference_type __d = __begin_ - __first_;
 546             __d = (__d + 1) / 2;
 547             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 548             __begin_ -= __d;
 549         }
 550         else
 551         {
 552             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 553             __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
 554             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 555                                    move_iterator<pointer>(__end_));
 556             _VSTD::swap(__first_, __t.__first_);
 557             _VSTD::swap(__begin_, __t.__begin_);
 558             _VSTD::swap(__end_, __t.__end_);
 559             _VSTD::swap(__end_cap(), __t.__end_cap());
 560         }
 561     }
 562     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_), __x);
 563     ++__end_;
 564 }
 565
 566 #ifndef _LIBCPP_CXX03_LANG
 567
 568 template <class _Tp, class _Allocator>
 569 void
 570 __split_buffer<_Tp, _Allocator>::push_back(value_type&& __x)
 571 {
 572     if (__end_ == __end_cap())
 573     {
 574         if (__begin_ > __first_)
 575         {
 576             difference_type __d = __begin_ - __first_;
 577             __d = (__d + 1) / 2;
 578             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 579             __begin_ -= __d;
 580         }
 581         else
 582         {
 583             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 584             __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
 585             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 586                                    move_iterator<pointer>(__end_));
 587             _VSTD::swap(__first_, __t.__first_);
 588             _VSTD::swap(__begin_, __t.__begin_);
 589             _VSTD::swap(__end_, __t.__end_);
 590             _VSTD::swap(__end_cap(), __t.__end_cap());
 591         }
 592     }
 593     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
 594             _VSTD::move(__x));
 595     ++__end_;
 596 }
 597
 598 template <class _Tp, class _Allocator>
 599 template <class... _Args>
 600 void
 601 __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args)
 602 {
 603     if (__end_ == __end_cap())
 604     {
 605         if (__begin_ > __first_)
 606         {
 607             difference_type __d = __begin_ - __first_;
 608             __d = (__d + 1) / 2;
 609             __end_ = _VSTD::move(__begin_, __end_, __begin_ - __d);
 610             __begin_ -= __d;
 611         }
 612         else
 613         {
 614             size_type __c = max<size_type>(2 * static_cast<size_t>(__end_cap() - __first_), 1);
 615             __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc());
 616             __t.__construct_at_end(move_iterator<pointer>(__begin_),
 617                                    move_iterator<pointer>(__end_));
 618             _VSTD::swap(__first_, __t.__first_);
 619             _VSTD::swap(__begin_, __t.__begin_);
 620             _VSTD::swap(__end_, __t.__end_);
 621             _VSTD::swap(__end_cap(), __t.__end_cap());
 622         }
 623     }
 624     __alloc_traits::construct(__alloc(), _VSTD::__to_raw_pointer(__end_),
 625                               _VSTD::forward<_Args>(__args)...);
 626     ++__end_;
 627 }
 628
 629 #endif  // _LIBCPP_CXX03_LANG
 630
 631 template <class _Tp, class _Allocator>
 632 inline _LIBCPP_INLINE_VISIBILITY
 633 void
 634 swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y)
 635         _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 636 {
 637     __x.swap(__y);
 638 }
 639
 640 _LIBCPP_END_NAMESPACE_STD
 641
 642 _LIBCPP_POP_MACROS
 643
 644 #endif  // _LIBCPP_SPLIT_BUFFER