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 19template <bool> 20class __split_buffer_common 21{ 22protected: 23 void __throw_length_error() const; 24 void __throw_out_of_range() const; 25}; 26 27template <class _Tp, class _Allocator = allocator<_Tp> > 28struct __split_buffer 29 : private __split_buffer_common<true> 30{ 31private: 32 __split_buffer(const __split_buffer&); 33 __split_buffer& operator=(const __split_buffer&); 34public: 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_cpp17_input_iterator<_InputIter>::value && 120 !__is_cpp17_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_cpp17_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 153private: 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 179template <class _Tp, class _Allocator> 180bool 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 209template <class _Tp, class _Allocator> 210void 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_address(__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) 225template <class _Tp, class _Allocator> 226void 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_address(__tx.__pos_), __x); 233 } 234} 235 236template <class _Tp, class _Allocator> 237template <class _InputIter> 238typename enable_if 239< 240 __is_cpp17_input_iterator<_InputIter>::value && 241 !__is_cpp17_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_address(__buf.__end_), _VSTD::move(*__p)); 257 swap(__buf); 258 } 259 __alloc_traits::construct(__a, _VSTD::__to_address(this->__end_), *__first); 260 ++this->__end_; 261 } 262} 263 264template <class _Tp, class _Allocator> 265template <class _ForwardIterator> 266typename enable_if 267< 268 __is_cpp17_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_address(__tx.__pos_), *__first); 277 } 278} 279 280template <class _Tp, class _Allocator> 281inline 282void 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_address(__begin_++)); 287} 288 289template <class _Tp, class _Allocator> 290inline 291void 292__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) 293{ 294 __begin_ = __new_begin; 295} 296 297template <class _Tp, class _Allocator> 298inline _LIBCPP_INLINE_VISIBILITY 299void 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_address(--__end_)); 304} 305 306template <class _Tp, class _Allocator> 307inline _LIBCPP_INLINE_VISIBILITY 308void 309__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT 310{ 311 __end_ = __new_last; 312} 313 314template <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 323template <class _Tp, class _Allocator> 324inline 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, __default_init_tag()) 328{ 329} 330 331template <class _Tp, class _Allocator> 332inline 333__split_buffer<_Tp, _Allocator>::__split_buffer(__alloc_rr& __a) 334 : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __end_cap_(nullptr, __a) 335{ 336} 337 338template <class _Tp, class _Allocator> 339inline 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 345template <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 355template <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 369template <class _Tp, class _Allocator> 370__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) 371 : __end_cap_(nullptr, __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 395template <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 417template <class _Tp, class _Allocator> 418void 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 430template <class _Tp, class _Allocator> 431void 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 446template <class _Tp, class _Allocator> 447void 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 473template <class _Tp, class _Allocator> 474void 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_address(__begin_-1), __x); 499 --__begin_; 500} 501 502#ifndef _LIBCPP_CXX03_LANG 503 504template <class _Tp, class _Allocator> 505void 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_address(__begin_-1), 530 _VSTD::move(__x)); 531 --__begin_; 532} 533 534#endif // _LIBCPP_CXX03_LANG 535 536template <class _Tp, class _Allocator> 537inline _LIBCPP_INLINE_VISIBILITY 538void 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_address(__end_), __x); 563 ++__end_; 564} 565 566#ifndef _LIBCPP_CXX03_LANG 567 568template <class _Tp, class _Allocator> 569void 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_address(__end_), 594 _VSTD::move(__x)); 595 ++__end_; 596} 597 598template <class _Tp, class _Allocator> 599template <class... _Args> 600void 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_address(__end_), 625 _VSTD::forward<_Args>(__args)...); 626 ++__end_; 627} 628 629#endif // _LIBCPP_CXX03_LANG 630 631template <class _Tp, class _Allocator> 632inline _LIBCPP_INLINE_VISIBILITY 633void 634swap(__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 645