libcxx/include/__split_buffer

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