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