74 #include <EASTL/internal/config.h>
75 #include <EASTL/allocator.h>
76 #include <EASTL/algorithm.h>
77 #include <EASTL/type_traits.h>
78 #include <EASTL/iterator.h>
79 #include <EASTL/memory.h>
80 #include <EASTL/initializer_list.h>
82 EA_DISABLE_ALL_VC_WARNINGS()
85 EA_RESTORE_ALL_VC_WARNINGS()
87 #if EASTL_EXCEPTIONS_ENABLED
88 EA_DISABLE_ALL_VC_WARNINGS()
90 EA_RESTORE_ALL_VC_WARNINGS()
99 EA_DISABLE_VC_WARNING(4267 4345 4480 4530 4571);
101 #if EASTL_EXCEPTIONS_ENABLED
104 EA_DISABLE_VC_WARNING(4703 4701)
108 #if defined(EA_PRAGMA_ONCE_SUPPORTED)
120 #ifndef EASTL_DEQUE_DEFAULT_NAME
121 #define EASTL_DEQUE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " deque"
127 #ifndef EASTL_DEQUE_DEFAULT_ALLOCATOR
128 #define EASTL_DEQUE_DEFAULT_ALLOCATOR allocator_type(EASTL_DEQUE_DEFAULT_NAME)
138 #if !defined(__GNUC__) || (__GNUC__ >= 3)
139 #define DEQUE_DEFAULT_SUBARRAY_SIZE(T) ((sizeof(T) <= 4) ? 64 : ((sizeof(T) <= 8) ? 32 : ((sizeof(T) <= 16) ? 16 : ((sizeof(T) <= 32) ? 8 : 4))))
141 #define DEQUE_DEFAULT_SUBARRAY_SIZE(T) 16
151 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
157 typedef ptrdiff_t difference_type;
158 typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
159 typedef T value_type;
161 typedef T& reference;
167 pointer operator->()
const;
168 reference operator*()
const;
176 this_type& operator+=(difference_type n);
177 this_type& operator-=(difference_type n);
179 this_type operator+(difference_type n)
const;
180 this_type operator-(difference_type n)
const;
183 template <
typename,
typename,
typename,
unsigned>
186 template <
typename,
typename,
unsigned>
189 template <
typename,
typename,
unsigned>
192 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
196 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
200 template <
typename U,
typename Po
interU,
typename ReferenceU,
unsigned kDequeSubarraySizeU>
204 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
208 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
212 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
216 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
220 template <
typename U,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySizeU>
221 friend typename DequeIterator<U, PointerA, ReferenceA, kDequeSubarraySizeU>::difference_type
229 T** mpCurrentArrayPtr;
246 void SetSubarray(T** pCurrentArrayPtr);
258 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
261 typedef T value_type;
262 typedef Allocator allocator_type;
263 typedef eastl_size_t size_type;
264 typedef ptrdiff_t difference_type;
268 static const size_type npos = (size_type)-1;
273 kMinPtrArraySize = 8,
286 size_type mnPtrArraySize;
289 allocator_type mAllocator;
297 const allocator_type& get_allocator() const EA_NOEXCEPT;
298 allocator_type& get_allocator() EA_NOEXCEPT;
299 void set_allocator(const allocator_type&
allocator);
302 T* DoAllocateSubarray();
303 void DoFreeSubarray(T* p);
304 void DoFreeSubarrays(T** pBegin, T** pEnd);
306 T** DoAllocatePtrArray(size_type n);
307 void DoFreePtrArray(T** p,
size_t n);
309 iterator DoReallocSubarray(size_type nAdditionalCapacity,
Side allocationSide);
310 void DoReallocPtrArray(size_type nAdditionalCapacity,
Side allocationSide);
312 void DoInit(size_type n);
336 template <typename T, typename Allocator = EASTLAllocatorType,
unsigned kDequeSubarraySize = DEQUE_DEFAULT_SUBARRAY_SIZE(T)>
342 typedef T value_type;
344 typedef const T* const_pointer;
345 typedef T& reference;
346 typedef const T& const_reference;
351 typedef typename base_type::size_type size_type;
352 typedef typename base_type::difference_type difference_type;
353 typedef typename base_type::allocator_type allocator_type;
355 using base_type::kSideFront;
356 using base_type::kSideBack;
357 using base_type::mpPtrArray;
358 using base_type::mnPtrArraySize;
359 using base_type::mItBegin;
360 using base_type::mItEnd;
361 using base_type::mAllocator;
362 using base_type::npos;
363 using base_type::DoAllocateSubarray;
364 using base_type::DoFreeSubarray;
365 using base_type::DoFreeSubarrays;
366 using base_type::DoAllocatePtrArray;
367 using base_type::DoFreePtrArray;
368 using base_type::DoReallocSubarray;
369 using base_type::DoReallocPtrArray;
374 explicit deque(size_type n,
const allocator_type&
allocator = EASTL_DEQUE_DEFAULT_ALLOCATOR);
375 deque(size_type n,
const value_type& value,
const allocator_type&
allocator = EASTL_DEQUE_DEFAULT_ALLOCATOR);
381 template <
typename InputIterator>
382 deque(InputIterator first, InputIterator last);
392 void assign(size_type n,
const value_type& value);
395 template <
typename InputIterator>
396 void assign(InputIterator first, InputIterator last);
415 bool empty() const EA_NOEXCEPT;
416 size_type size() const EA_NOEXCEPT;
418 void resize(size_type n, const value_type& value);
419 void resize(size_type n);
421 void shrink_to_fit();
422 void set_capacity(size_type n =
base_type::npos);
424 reference operator[](size_type n);
425 const_reference operator[](size_type n) const;
427 reference at(size_type n);
428 const_reference at(size_type n) const;
431 const_reference front() const;
434 const_reference back() const;
436 void push_front(const value_type& value);
437 reference push_front();
438 void push_front(value_type&& value);
440 void push_back(const value_type& value);
441 reference push_back();
442 void push_back(value_type&& value);
447 template<class... Args>
450 template<class... Args>
451 void emplace_front(Args&&... args);
453 template<class... Args>
454 void emplace_back(Args&&... args);
458 void insert(
const_iterator position, size_type n, const value_type& value);
461 template <typename InputIterator>
462 void insert(
const_iterator position, InputIterator first, InputIterator last);
472 bool validate() const;
476 template <typename Integer>
477 void DoInit(Integer n, Integer value,
true_type);
479 template <typename InputIterator>
480 void DoInit(InputIterator first, InputIterator last,
false_type);
482 template <typename InputIterator>
483 void DoInitFromIterator(InputIterator first, InputIterator last, EASTL_ITC_NS::
input_iterator_tag);
485 template <typename ForwardIterator>
486 void DoInitFromIterator(ForwardIterator first, ForwardIterator last, EASTL_ITC_NS::
forward_iterator_tag);
488 void DoFillInit(const value_type& value);
490 template <typename Integer>
491 void DoAssign(Integer n, Integer value,
true_type);
493 template <typename InputIterator>
494 void DoAssign(InputIterator first, InputIterator last,
false_type);
496 void DoAssignValues(size_type n, const value_type& value);
498 template <typename Integer>
501 template <typename InputIterator>
504 template <typename InputIterator>
507 void DoInsertValues(
const_iterator position, size_type n, const value_type& value);
519 template <typename T, typename Allocator,
unsigned kDequeSubarraySize>
531 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
537 mAllocator(EASTL_DEQUE_DEFAULT_NAME)
546 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
547 DequeBase<T, Allocator, kDequeSubarraySize>::DequeBase(size_type n,
const allocator_type& allocator)
552 mAllocator(allocator)
561 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
562 DequeBase<T, Allocator, kDequeSubarraySize>::~DequeBase()
566 DoFreeSubarrays(mItBegin.mpCurrentArrayPtr, mItEnd.mpCurrentArrayPtr + 1);
567 DoFreePtrArray(mpPtrArray, mnPtrArraySize);
568 mpPtrArray =
nullptr;
573 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
574 const typename DequeBase<T, Allocator, kDequeSubarraySize>::allocator_type&
575 DequeBase<T, Allocator, kDequeSubarraySize>::get_allocator() const EA_NOEXCEPT
581 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
582 typename DequeBase<T, Allocator, kDequeSubarraySize>::allocator_type&
583 DequeBase<T, Allocator, kDequeSubarraySize>::get_allocator() EA_NOEXCEPT
589 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
590 void DequeBase<T, Allocator, kDequeSubarraySize>::set_allocator(
const allocator_type& allocator)
593 if(EASTL_LIKELY(mAllocator != allocator))
595 if(EASTL_LIKELY(mpPtrArray && (mItBegin.mpCurrentArrayPtr == mItEnd.mpCurrentArrayPtr)))
597 DoFreeSubarrays(mItBegin.mpCurrentArrayPtr, mItEnd.mpCurrentArrayPtr + 1);
598 DoFreePtrArray(mpPtrArray, mnPtrArraySize);
600 mAllocator = allocator;
605 EASTL_FAIL_MSG(
"DequeBase::set_allocator -- atempt to change allocator after allocating elements.");
611 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
612 T* DequeBase<T, Allocator, kDequeSubarraySize>::DoAllocateSubarray()
614 T* p = (T*)
allocate_memory(mAllocator, kDequeSubarraySize *
sizeof(T), EASTL_ALIGN_OF(T), 0);
615 EASTL_ASSERT_MSG(p !=
nullptr,
"the behaviour of eastl::allocators that return nullptr is not defined.");
618 memset((
void*)p, 0, kDequeSubarraySize *
sizeof(T));
625 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
626 void DequeBase<T, Allocator, kDequeSubarraySize>::DoFreeSubarray(T* p)
629 EASTLFree(mAllocator, p, kDequeSubarraySize *
sizeof(T));
632 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
633 void DequeBase<T, Allocator, kDequeSubarraySize>::DoFreeSubarrays(T** pBegin, T** pEnd)
636 DoFreeSubarray(*pBegin++);
639 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
640 T** DequeBase<T, Allocator, kDequeSubarraySize>::DoAllocatePtrArray(size_type n)
642 #if EASTL_ASSERT_ENABLED
643 if(EASTL_UNLIKELY(n >= 0x80000000))
644 EASTL_FAIL_MSG(
"deque::DoAllocatePtrArray -- improbably large request.");
647 T** pp = (T**)
allocate_memory(mAllocator, n *
sizeof(T*), EASTL_ALIGN_OF(T), 0);
648 EASTL_ASSERT_MSG(pp !=
nullptr,
"the behaviour of eastl::allocators that return nullptr is not defined.");
651 memset((
void*)pp, 0, n *
sizeof(T*));
658 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
659 void DequeBase<T, Allocator, kDequeSubarraySize>::DoFreePtrArray(T** pp,
size_t n)
662 EASTLFree(mAllocator, pp, n *
sizeof(T*));
666 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
667 typename DequeBase<T, Allocator, kDequeSubarraySize>::iterator
668 DequeBase<T, Allocator, kDequeSubarraySize>::DoReallocSubarray(size_type nAdditionalCapacity, Side allocationSide)
678 if(allocationSide == kSideFront)
681 const size_type nCurrentAdditionalCapacity = (size_type)(mItBegin.mpCurrent - mItBegin.mpBegin);
683 if(EASTL_UNLIKELY(nCurrentAdditionalCapacity < nAdditionalCapacity))
685 const difference_type nSubarrayIncrease = (difference_type)(((nAdditionalCapacity - nCurrentAdditionalCapacity) + kDequeSubarraySize - 1) / kDequeSubarraySize);
688 if(nSubarrayIncrease > (mItBegin.mpCurrentArrayPtr - mpPtrArray))
689 DoReallocPtrArray((size_type)(nSubarrayIncrease - (mItBegin.mpCurrentArrayPtr - mpPtrArray)), kSideFront);
691 #if EASTL_EXCEPTIONS_ENABLED
695 for(i = 1; i <= nSubarrayIncrease; ++i)
696 mItBegin.mpCurrentArrayPtr[-i] = DoAllocateSubarray();
697 #if EASTL_EXCEPTIONS_ENABLED
701 for(difference_type j = 1; j < i; ++j)
702 DoFreeSubarray(mItBegin.mpCurrentArrayPtr[-j]);
708 return mItBegin - (difference_type)nAdditionalCapacity;
712 const size_type nCurrentAdditionalCapacity = (size_type)((mItEnd.mpEnd - 1) - mItEnd.mpCurrent);
714 if(EASTL_UNLIKELY(nCurrentAdditionalCapacity < nAdditionalCapacity))
716 const difference_type nSubarrayIncrease = (difference_type)(((nAdditionalCapacity - nCurrentAdditionalCapacity) + kDequeSubarraySize - 1) / kDequeSubarraySize);
719 if(nSubarrayIncrease > ((mpPtrArray + mnPtrArraySize) - mItEnd.mpCurrentArrayPtr) - 1)
720 DoReallocPtrArray((size_type)(nSubarrayIncrease - (((mpPtrArray + mnPtrArraySize) - mItEnd.mpCurrentArrayPtr) - 1)), kSideBack);
722 #if EASTL_EXCEPTIONS_ENABLED
726 for(i = 1; i <= nSubarrayIncrease; ++i)
727 mItEnd.mpCurrentArrayPtr[i] = DoAllocateSubarray();
728 #if EASTL_EXCEPTIONS_ENABLED
732 for(difference_type j = 1; j < i; ++j)
733 DoFreeSubarray(mItEnd.mpCurrentArrayPtr[j]);
739 return mItEnd + (difference_type)nAdditionalCapacity;
744 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
745 void DequeBase<T, Allocator, kDequeSubarraySize>::DoReallocPtrArray(size_type nAdditionalCapacity, Side allocationSide)
763 const size_type nUnusedPtrCountAtFront = (size_type)(mItBegin.mpCurrentArrayPtr - mpPtrArray);
764 const size_type nUsedPtrCount = (size_type)(mItEnd.mpCurrentArrayPtr - mItBegin.mpCurrentArrayPtr) + 1;
765 const size_type nUsedPtrSpace = nUsedPtrCount *
sizeof(
void*);
766 const size_type nUnusedPtrCountAtBack = (mnPtrArraySize - nUnusedPtrCountAtFront) - nUsedPtrCount;
767 value_type** pPtrArrayBegin;
769 if((allocationSide == kSideBack) && (nAdditionalCapacity <= nUnusedPtrCountAtFront))
771 if(nAdditionalCapacity < (nUnusedPtrCountAtFront / 2))
772 nAdditionalCapacity = (nUnusedPtrCountAtFront / 2);
774 pPtrArrayBegin = mpPtrArray + (nUnusedPtrCountAtFront - nAdditionalCapacity);
775 memmove(pPtrArrayBegin, mItBegin.mpCurrentArrayPtr, nUsedPtrSpace);
778 memset(pPtrArrayBegin + nUsedPtrCount, 0, (
size_t)(mpPtrArray + mnPtrArraySize) - (
size_t)(pPtrArrayBegin + nUsedPtrCount));
781 else if((allocationSide == kSideFront) && (nAdditionalCapacity <= nUnusedPtrCountAtBack))
783 if(nAdditionalCapacity < (nUnusedPtrCountAtBack / 2))
784 nAdditionalCapacity = (nUnusedPtrCountAtBack / 2);
786 pPtrArrayBegin = mItBegin.mpCurrentArrayPtr + nAdditionalCapacity;
787 memmove(pPtrArrayBegin, mItBegin.mpCurrentArrayPtr, nUsedPtrSpace);
790 memset(mpPtrArray, 0, (
size_t)((uintptr_t)pPtrArrayBegin - (uintptr_t)mpPtrArray));
796 const size_type nNewPtrArraySize = mnPtrArraySize +
eastl::max_alt(mnPtrArraySize, nAdditionalCapacity) + 2;
797 value_type**
const pNewPtrArray = DoAllocatePtrArray(nNewPtrArraySize);
799 pPtrArrayBegin = pNewPtrArray + (mItBegin.mpCurrentArrayPtr - mpPtrArray) + ((allocationSide == kSideFront) ? nAdditionalCapacity : 0);
804 memcpy(pPtrArrayBegin, mItBegin.mpCurrentArrayPtr, nUsedPtrSpace);
806 DoFreePtrArray(mpPtrArray, mnPtrArraySize);
808 mpPtrArray = pNewPtrArray;
809 mnPtrArraySize = nNewPtrArraySize;
813 mItBegin.SetSubarray(pPtrArrayBegin);
814 mItEnd.SetSubarray((pPtrArrayBegin + nUsedPtrCount) - 1);
818 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
819 void DequeBase<T, Allocator, kDequeSubarraySize>::DoInit(size_type n)
827 const size_type nNewPtrArraySize = (size_type)((n / kDequeSubarraySize) + 1);
828 const size_type kMinPtrArraySize_ = kMinPtrArraySize;
830 mnPtrArraySize =
eastl::max_alt(kMinPtrArraySize_, (nNewPtrArraySize + 2));
831 mpPtrArray = DoAllocatePtrArray(mnPtrArraySize);
833 value_type**
const pPtrArrayBegin = (mpPtrArray + ((mnPtrArraySize - nNewPtrArraySize) / 2));
834 value_type**
const pPtrArrayEnd = pPtrArrayBegin + nNewPtrArraySize;
835 value_type** pPtrArrayCurrent = pPtrArrayBegin;
837 #if EASTL_EXCEPTIONS_ENABLED
843 while(pPtrArrayCurrent < pPtrArrayEnd)
844 *pPtrArrayCurrent++ = DoAllocateSubarray();
845 #if EASTL_EXCEPTIONS_ENABLED
849 DoFreeSubarrays(pPtrArrayBegin, pPtrArrayCurrent);
855 DoFreePtrArray(mpPtrArray, mnPtrArraySize);
862 mItBegin.SetSubarray(pPtrArrayBegin);
863 mItBegin.mpCurrent = mItBegin.mpBegin;
865 mItEnd.SetSubarray(pPtrArrayEnd - 1);
866 mItEnd.mpCurrent = mItEnd.mpBegin + (difference_type)(n % kDequeSubarraySize);
888 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
889 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::DequeIterator()
890 : mpCurrent(NULL), mpBegin(NULL), mpEnd(NULL), mpCurrentArrayPtr(NULL)
896 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
897 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::DequeIterator(T** pCurrentArrayPtr, T* pCurrent)
898 : mpCurrent(pCurrent), mpBegin(*pCurrentArrayPtr), mpEnd(pCurrent + kDequeSubarraySize), mpCurrentArrayPtr(pCurrentArrayPtr)
904 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
905 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::DequeIterator(
const iterator& x)
906 : mpCurrent(x.mpCurrent), mpBegin(x.mpBegin), mpEnd(x.mpEnd), mpCurrentArrayPtr(x.mpCurrentArrayPtr)
912 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
913 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::DequeIterator(
const iterator& x, Increment)
914 : mpCurrent(x.mpCurrent), mpBegin(x.mpBegin), mpEnd(x.mpEnd), mpCurrentArrayPtr(x.mpCurrentArrayPtr)
920 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
921 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::DequeIterator(
const iterator& x, Decrement)
922 : mpCurrent(x.mpCurrent), mpBegin(x.mpBegin), mpEnd(x.mpEnd), mpCurrentArrayPtr(x.mpCurrentArrayPtr)
928 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
929 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::pointer
930 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator->()
const
936 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
937 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::reference
938 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator*()
const
944 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
945 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type&
946 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator++()
948 if(EASTL_UNLIKELY(++mpCurrent == mpEnd))
950 mpBegin = *++mpCurrentArrayPtr;
951 mpEnd = mpBegin + kDequeSubarraySize;
958 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
959 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type
960 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator++(
int)
962 const this_type temp(*
this);
968 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
969 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type&
970 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator--()
972 if(EASTL_UNLIKELY(mpCurrent == mpBegin))
974 mpBegin = *--mpCurrentArrayPtr;
975 mpEnd = mpBegin + kDequeSubarraySize;
983 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
984 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type
985 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator--(
int)
987 const this_type temp(*
this);
993 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
994 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type&
995 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator+=(difference_type n)
997 const difference_type subarrayPosition = (mpCurrent - mpBegin) + n;
1000 if((
size_t)subarrayPosition < (size_t)kDequeSubarraySize)
1012 EASTL_CT_ASSERT((kDequeSubarraySize & (kDequeSubarraySize - 1)) == 0);
1013 const difference_type subarrayIndex = (((16777216 + subarrayPosition) / (difference_type)kDequeSubarraySize)) - (16777216 / (difference_type)kDequeSubarraySize);
1015 SetSubarray(mpCurrentArrayPtr + subarrayIndex);
1016 mpCurrent = mpBegin + (subarrayPosition - (subarrayIndex * (difference_type)kDequeSubarraySize));
1022 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1023 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type&
1024 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator-=(difference_type n)
1026 return (*this).operator+=(-n);
1030 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1031 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type
1032 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator+(difference_type n)
const
1034 return this_type(*this).operator+=(n);
1038 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1039 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type
1040 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::operator-(difference_type n)
const
1042 return this_type(*this).operator+=(-n);
1046 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1047 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type
1048 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::copy(
const iterator& first,
const iterator& last, true_type)
1052 if((first.mpBegin == last.mpBegin) && (first.mpBegin == mpBegin))
1054 memmove(mpCurrent, first.mpCurrent, (
size_t)((uintptr_t)last.mpCurrent - (uintptr_t)first.mpCurrent));
1055 return *
this + (last.mpCurrent - first.mpCurrent);
1057 return eastl::copy(eastl::make_move_iterator(first), eastl::make_move_iterator(last), eastl::make_move_iterator(*
this)).base();
1061 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1062 typename DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::this_type
1063 DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::copy(
const iterator& first,
const iterator& last, false_type)
1065 return eastl::copy(eastl::make_move_iterator(first), eastl::make_move_iterator(last), eastl::make_move_iterator(*
this)).base();
1069 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1070 void DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::copy_backward(
const iterator& first,
const iterator& last, true_type)
1074 if((first.mpBegin == last.mpBegin) && (first.mpBegin == mpBegin))
1075 memmove(mpCurrent - (last.mpCurrent - first.mpCurrent), first.mpCurrent, (
size_t)((uintptr_t)last.mpCurrent - (uintptr_t)first.mpCurrent));
1077 eastl::copy_backward(eastl::make_move_iterator(first), eastl::make_move_iterator(last), eastl::make_move_iterator(*
this));
1081 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1082 void DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::copy_backward(
const iterator& first,
const iterator& last, false_type)
1084 eastl::copy_backward(eastl::make_move_iterator(first), eastl::make_move_iterator(last), eastl::make_move_iterator(*
this)).base();
1088 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1089 void DequeIterator<T, Pointer, Reference, kDequeSubarraySize>::SetSubarray(T** pCurrentArrayPtr)
1091 mpCurrentArrayPtr = pCurrentArrayPtr;
1092 mpBegin = *pCurrentArrayPtr;
1093 mpEnd = mpBegin + kDequeSubarraySize;
1100 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1101 inline bool operator==(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1102 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1104 return a.mpCurrent == b.mpCurrent;
1108 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1109 inline bool operator!=(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1110 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1112 return a.mpCurrent != b.mpCurrent;
1118 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1119 inline bool operator!=(
const DequeIterator<T, Pointer, Reference, kDequeSubarraySize>& a,
1120 const DequeIterator<T, Pointer, Reference, kDequeSubarraySize>& b)
1122 return a.mpCurrent != b.mpCurrent;
1126 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1127 inline bool operator<(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1128 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1130 return (a.mpCurrentArrayPtr == b.mpCurrentArrayPtr) ? (a.mpCurrent < b.mpCurrent) : (a.mpCurrentArrayPtr < b.mpCurrentArrayPtr);
1134 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1135 inline bool operator>(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1136 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1138 return (a.mpCurrentArrayPtr == b.mpCurrentArrayPtr) ? (a.mpCurrent > b.mpCurrent) : (a.mpCurrentArrayPtr > b.mpCurrentArrayPtr);
1142 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1143 inline bool operator<=(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1144 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1146 return (a.mpCurrentArrayPtr == b.mpCurrentArrayPtr) ? (a.mpCurrent <= b.mpCurrent) : (a.mpCurrentArrayPtr <= b.mpCurrentArrayPtr);
1150 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1151 inline bool operator>=(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1152 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1154 return (a.mpCurrentArrayPtr == b.mpCurrentArrayPtr) ? (a.mpCurrent >= b.mpCurrent) : (a.mpCurrentArrayPtr >= b.mpCurrentArrayPtr);
1160 template <
typename T,
typename Po
inter,
typename Reference,
unsigned kDequeSubarraySize>
1161 inline DequeIterator<T, Pointer, Reference, kDequeSubarraySize>
1162 operator+(ptrdiff_t n,
const DequeIterator<T, Pointer, Reference, kDequeSubarraySize>& x)
1171 template <
typename T,
typename Po
interA,
typename ReferenceA,
typename Po
interB,
typename ReferenceB,
unsigned kDequeSubarraySize>
1172 inline typename DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>::difference_type
1173 operator-(
const DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>& a,
1174 const DequeIterator<T, PointerB, ReferenceB, kDequeSubarraySize>& b)
1177 typedef typename DequeIterator<T, PointerA, ReferenceA, kDequeSubarraySize>::difference_type difference_type;
1179 return ((difference_type)kDequeSubarraySize * ((a.mpCurrentArrayPtr - b.mpCurrentArrayPtr) - 1)) + (a.mpCurrent - a.mpBegin) + (b.mpEnd - b.mpCurrent);
1189 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1190 inline deque<T, Allocator, kDequeSubarraySize>::deque()
1191 : base_type((size_type)0)
1197 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1198 inline deque<T, Allocator, kDequeSubarraySize>::deque(
const allocator_type& allocator)
1199 : base_type((size_type)0, allocator)
1205 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1206 inline deque<T, Allocator, kDequeSubarraySize>::deque(size_type n,
const allocator_type& allocator)
1207 : base_type(n, allocator)
1209 DoFillInit(value_type());
1213 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1214 inline deque<T, Allocator, kDequeSubarraySize>::deque(size_type n,
const value_type& value,
const allocator_type& allocator)
1215 : base_type(n, allocator)
1221 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1222 inline deque<T, Allocator, kDequeSubarraySize>::deque(
const this_type& x)
1223 : base_type(x.size(), x.mAllocator)
1229 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1230 inline deque<T, Allocator, kDequeSubarraySize>::deque(this_type&& x)
1231 : base_type((size_type)0, x.mAllocator)
1237 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1238 inline deque<T, Allocator, kDequeSubarraySize>::deque(this_type&& x,
const allocator_type& allocator)
1239 : base_type((size_type)0, allocator)
1245 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1247 : base_type(allocator)
1249 DoInit(ilist.begin(), ilist.end(), false_type());
1253 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1254 template <
typename InputIterator>
1255 inline deque<T, Allocator, kDequeSubarraySize>::deque(InputIterator first, InputIterator last)
1256 : base_type(EASTL_DEQUE_DEFAULT_ALLOCATOR)
1258 DoInit(first, last, is_integral<InputIterator>());
1262 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1263 inline deque<T, Allocator, kDequeSubarraySize>::~deque()
1266 for(iterator itCurrent(mItBegin); itCurrent != mItEnd; ++itCurrent)
1267 itCurrent.mpCurrent->~value_type();
1271 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1272 typename deque<T, Allocator, kDequeSubarraySize>::this_type&
1273 deque<T, Allocator, kDequeSubarraySize>::operator=(
const this_type& x)
1283 #if EASTL_ALLOCATOR_COPY_ENABLED
1284 bool bSlowerPathwayRequired = (mAllocator != x.mAllocator);
1286 bool bSlowerPathwayRequired =
false;
1289 if(bSlowerPathwayRequired)
1294 this_type temp(x.mAllocator);
1306 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1307 inline typename deque<T, Allocator, kDequeSubarraySize>::this_type&
1308 deque<T, Allocator, kDequeSubarraySize>::operator=(this_type&& x)
1319 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1320 inline typename deque<T, Allocator, kDequeSubarraySize>::this_type&
1323 DoAssign(ilist.begin(), ilist.end(), false_type());
1328 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1329 inline void deque<T, Allocator, kDequeSubarraySize>::assign(size_type n,
const value_type& value)
1331 DoAssignValues(n, value);
1335 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1338 DoAssign(ilist.begin(), ilist.end(), false_type());
1345 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1346 template <
typename InputIterator>
1347 inline void deque<T, Allocator, kDequeSubarraySize>::assign(InputIterator first, InputIterator last)
1349 DoAssign(first, last, is_integral<InputIterator>());
1353 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1354 inline typename deque<T, Allocator, kDequeSubarraySize>::iterator
1355 deque<T, Allocator, kDequeSubarraySize>::begin() EA_NOEXCEPT
1361 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1362 inline typename deque<T, Allocator, kDequeSubarraySize>::const_iterator
1363 deque<T, Allocator, kDequeSubarraySize>::begin() const EA_NOEXCEPT
1369 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1370 inline typename deque<T, Allocator, kDequeSubarraySize>::const_iterator
1371 deque<T, Allocator, kDequeSubarraySize>::cbegin() const EA_NOEXCEPT
1377 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1378 inline typename deque<T, Allocator, kDequeSubarraySize>::iterator
1379 deque<T, Allocator, kDequeSubarraySize>::end() EA_NOEXCEPT
1385 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1386 typename deque<T, Allocator, kDequeSubarraySize>::const_iterator
1387 deque<T, Allocator, kDequeSubarraySize>::end() const EA_NOEXCEPT
1393 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1394 inline typename deque<T, Allocator, kDequeSubarraySize>::const_iterator
1395 deque<T, Allocator, kDequeSubarraySize>::cend() const EA_NOEXCEPT
1401 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1402 inline typename deque<T, Allocator, kDequeSubarraySize>::reverse_iterator
1403 deque<T, Allocator, kDequeSubarraySize>::rbegin() EA_NOEXCEPT
1405 return reverse_iterator(mItEnd);
1409 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1410 inline typename deque<T, Allocator, kDequeSubarraySize>::const_reverse_iterator
1411 deque<T, Allocator, kDequeSubarraySize>::rbegin() const EA_NOEXCEPT
1413 return const_reverse_iterator(mItEnd);
1417 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1418 inline typename deque<T, Allocator, kDequeSubarraySize>::const_reverse_iterator
1419 deque<T, Allocator, kDequeSubarraySize>::crbegin() const EA_NOEXCEPT
1421 return const_reverse_iterator(mItEnd);
1425 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1426 inline typename deque<T, Allocator, kDequeSubarraySize>::reverse_iterator
1427 deque<T, Allocator, kDequeSubarraySize>::rend() EA_NOEXCEPT
1429 return reverse_iterator(mItBegin);
1433 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1434 inline typename deque<T, Allocator, kDequeSubarraySize>::const_reverse_iterator
1435 deque<T, Allocator, kDequeSubarraySize>::rend() const EA_NOEXCEPT
1437 return const_reverse_iterator(mItBegin);
1441 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1442 inline typename deque<T, Allocator, kDequeSubarraySize>::const_reverse_iterator
1443 deque<T, Allocator, kDequeSubarraySize>::crend() const EA_NOEXCEPT
1445 return const_reverse_iterator(mItBegin);
1449 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1450 inline bool deque<T, Allocator, kDequeSubarraySize>::empty() const EA_NOEXCEPT
1452 return mItBegin.mpCurrent == mItEnd.mpCurrent;
1456 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1457 typename deque<T, Allocator, kDequeSubarraySize>::size_type
1458 inline deque<T, Allocator, kDequeSubarraySize>::size() const EA_NOEXCEPT
1460 return (size_type)(mItEnd - mItBegin);
1464 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1465 inline void deque<T, Allocator, kDequeSubarraySize>::resize(size_type n,
const value_type& value)
1467 const size_type nSizeCurrent = size();
1469 if(n > nSizeCurrent)
1470 insert(mItEnd, n - nSizeCurrent, value);
1472 erase(mItBegin + (difference_type)n, mItEnd);
1476 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1477 inline void deque<T, Allocator, kDequeSubarraySize>::resize(size_type n)
1479 resize(n, value_type());
1483 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1484 inline void deque<T, Allocator, kDequeSubarraySize>::shrink_to_fit()
1486 this_type x(eastl::make_move_iterator(begin()), eastl::make_move_iterator(end()));
1491 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1492 inline void deque<T, Allocator, kDequeSubarraySize>::set_capacity(size_type n)
1501 this_type temp(mAllocator);
1515 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1516 typename deque<T, Allocator, kDequeSubarraySize>::reference
1517 deque<T, Allocator, kDequeSubarraySize>::operator[](size_type n)
1519 #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1520 if (EASTL_UNLIKELY(n >= (size_type)(mItEnd - mItBegin)))
1521 EASTL_FAIL_MSG(
"deque::operator[] -- out of range");
1522 #elif EASTL_ASSERT_ENABLED
1524 if (EASTL_UNLIKELY((n != 0) && n >= (size_type)(mItEnd - mItBegin)))
1525 EASTL_FAIL_MSG(
"deque::operator[] -- out of range");
1529 iterator it(mItBegin);
1531 const difference_type subarrayPosition = (difference_type)((it.mpCurrent - it.mpBegin) + (difference_type)n);
1532 const difference_type subarrayIndex = (((16777216 + subarrayPosition) / (difference_type)kDequeSubarraySize)) - (16777216 / (difference_type)kDequeSubarraySize);
1534 return *(*(it.mpCurrentArrayPtr + subarrayIndex) + (subarrayPosition - (subarrayIndex * (difference_type)kDequeSubarraySize)));
1538 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1539 typename deque<T, Allocator, kDequeSubarraySize>::const_reference
1540 deque<T, Allocator, kDequeSubarraySize>::operator[](size_type n)
const
1542 #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1543 if (EASTL_UNLIKELY(n >= (size_type)(mItEnd - mItBegin)))
1544 EASTL_FAIL_MSG(
"deque::operator[] -- out of range");
1545 #elif EASTL_ASSERT_ENABLED
1547 if (EASTL_UNLIKELY((n != 0) && n >= (size_type)(mItEnd - mItBegin)))
1548 EASTL_FAIL_MSG(
"deque::operator[] -- out of range");
1552 iterator it(mItBegin);
1554 const difference_type subarrayPosition = (it.mpCurrent - it.mpBegin) + (difference_type)n;
1555 const difference_type subarrayIndex = (((16777216 + subarrayPosition) / (difference_type)kDequeSubarraySize)) - (16777216 / (difference_type)kDequeSubarraySize);
1557 return *(*(it.mpCurrentArrayPtr + subarrayIndex) + (subarrayPosition - (subarrayIndex * (difference_type)kDequeSubarraySize)));
1561 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1562 typename deque<T, Allocator, kDequeSubarraySize>::reference
1563 deque<T, Allocator, kDequeSubarraySize>::at(size_type n)
1565 #if EASTL_EXCEPTIONS_ENABLED
1566 if(n >= (size_type)(mItEnd - mItBegin))
1567 throw std::out_of_range(
"deque::at -- out of range");
1568 #elif EASTL_ASSERT_ENABLED
1569 if(n >= (size_type)(mItEnd - mItBegin))
1570 EASTL_FAIL_MSG(
"deque::at -- out of range");
1572 return *(mItBegin.operator+((difference_type)n));
1576 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1577 typename deque<T, Allocator, kDequeSubarraySize>::const_reference
1578 deque<T, Allocator, kDequeSubarraySize>::at(size_type n)
const
1580 #if EASTL_EXCEPTIONS_ENABLED
1581 if(n >= (size_type)(mItEnd - mItBegin))
1582 throw std::out_of_range(
"deque::at -- out of range");
1583 #elif EASTL_ASSERT_ENABLED
1584 if(n >= (size_type)(mItEnd - mItBegin))
1585 EASTL_FAIL_MSG(
"deque::at -- out of range");
1587 return *(mItBegin.operator+((difference_type)n));
1591 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1592 typename deque<T, Allocator, kDequeSubarraySize>::reference
1593 deque<T, Allocator, kDequeSubarraySize>::front()
1595 #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1596 if (EASTL_UNLIKELY((size_type)(mItEnd == mItBegin)))
1597 EASTL_FAIL_MSG(
"deque::front -- empty deque");
1606 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1607 typename deque<T, Allocator, kDequeSubarraySize>::const_reference
1608 deque<T, Allocator, kDequeSubarraySize>::front()
const
1610 #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1611 if (EASTL_UNLIKELY((size_type)(mItEnd == mItBegin)))
1612 EASTL_FAIL_MSG(
"deque::front -- empty deque");
1621 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1622 typename deque<T, Allocator, kDequeSubarraySize>::reference
1623 deque<T, Allocator, kDequeSubarraySize>::back()
1625 #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1626 if (EASTL_UNLIKELY((size_type)(mItEnd == mItBegin)))
1627 EASTL_FAIL_MSG(
"deque::back -- empty deque");
1632 return *iterator(mItEnd,
typename iterator::Decrement());
1636 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1637 typename deque<T, Allocator, kDequeSubarraySize>::const_reference
1638 deque<T, Allocator, kDequeSubarraySize>::back()
const
1640 #if EASTL_ASSERT_ENABLED && EASTL_EMPTY_REFERENCE_ASSERT_ENABLED
1641 if (EASTL_UNLIKELY((size_type)(mItEnd == mItBegin)))
1642 EASTL_FAIL_MSG(
"deque::back -- empty deque");
1647 return *iterator(mItEnd,
typename iterator::Decrement());
1651 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1652 void deque<T, Allocator, kDequeSubarraySize>::push_front(
const value_type& value)
1654 emplace_front(value);
1658 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1659 void deque<T, Allocator, kDequeSubarraySize>::push_front(value_type&& value)
1665 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1666 typename deque<T, Allocator, kDequeSubarraySize>::reference
1667 deque<T, Allocator, kDequeSubarraySize>::push_front()
1669 emplace_front(value_type());
1674 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1675 void deque<T, Allocator, kDequeSubarraySize>::push_back(
const value_type& value)
1677 emplace_back(value);
1681 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1682 void deque<T, Allocator, kDequeSubarraySize>::push_back(value_type&& value)
1688 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1689 typename deque<T, Allocator, kDequeSubarraySize>::reference
1690 deque<T, Allocator, kDequeSubarraySize>::push_back()
1692 emplace_back(value_type());
1693 return *iterator(mItEnd,
typename iterator::Decrement());
1697 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1698 void deque<T, Allocator, kDequeSubarraySize>::pop_front()
1700 #if EASTL_ASSERT_ENABLED
1701 if(EASTL_UNLIKELY((size_type)(mItEnd == mItBegin)))
1702 EASTL_FAIL_MSG(
"deque::pop_front -- empty deque");
1705 if((mItBegin.mpCurrent + 1) != mItBegin.mpEnd)
1706 (mItBegin.mpCurrent++)->~value_type();
1712 value_type** pp = mItBegin.mpCurrentArrayPtr;
1715 mItBegin.mpCurrent->~value_type();
1716 DoFreeSubarray(mItBegin.mpBegin);
1717 mItBegin.SetSubarray(mItBegin.mpCurrentArrayPtr + 1);
1718 mItBegin.mpCurrent = mItBegin.mpBegin;
1727 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1728 void deque<T, Allocator, kDequeSubarraySize>::pop_back()
1730 #if EASTL_ASSERT_ENABLED
1731 if(EASTL_UNLIKELY((size_type)(mItEnd == mItBegin)))
1732 EASTL_FAIL_MSG(
"deque::pop_back -- empty deque");
1735 if(mItEnd.mpCurrent != mItEnd.mpBegin)
1736 (--mItEnd.mpCurrent)->~value_type();
1742 value_type** pp = mItEnd.mpCurrentArrayPtr;
1745 DoFreeSubarray(mItEnd.mpBegin);
1746 mItEnd.SetSubarray(mItEnd.mpCurrentArrayPtr - 1);
1747 mItEnd.mpCurrent = mItEnd.mpEnd - 1;
1748 mItEnd.mpCurrent->~value_type();
1757 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1758 template<
class... Args>
1759 typename deque<T, Allocator, kDequeSubarraySize>::iterator
1760 deque<T, Allocator, kDequeSubarraySize>::emplace(const_iterator position, Args&&... args)
1762 if(EASTL_UNLIKELY(position.mpCurrent == mItEnd.mpCurrent))
1764 emplace_back(eastl::forward<Args>(args)...);
1765 return iterator(mItEnd,
typename iterator::Decrement());
1767 else if(EASTL_UNLIKELY(position.mpCurrent == mItBegin.mpCurrent))
1769 emplace_front(eastl::forward<Args>(args)...);
1773 iterator itPosition(position,
typename iterator::FromConst());
1774 value_type valueSaved(eastl::forward<Args>(args)...);
1775 const difference_type i(itPosition - mItBegin);
1777 #if EASTL_ASSERT_ENABLED
1778 EASTL_ASSERT(!empty());
1780 if(EASTL_UNLIKELY(!(validate_iterator(itPosition) & isf_valid)))
1781 EASTL_FAIL_MSG(
"deque::emplace -- invalid iterator");
1784 if(i < (difference_type)(size() / 2))
1788 itPosition = mItBegin + i;
1790 const iterator newPosition (itPosition,
typename iterator::Increment());
1791 iterator oldBegin (mItBegin,
typename iterator::Increment());
1792 const iterator oldBeginPlus1(oldBegin,
typename iterator::Increment());
1798 emplace_back(
eastl::move(*iterator(mItEnd,
typename iterator::Decrement())));
1800 itPosition = mItBegin + i;
1802 iterator oldBack (mItEnd,
typename iterator::Decrement());
1803 const iterator oldBackMinus1(oldBack,
typename iterator::Decrement());
1813 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1814 template<
class... Args>
1815 void deque<T, Allocator, kDequeSubarraySize>::emplace_front(Args&&... args)
1817 if(mItBegin.mpCurrent != mItBegin.mpBegin)
1818 ::new((
void*)--mItBegin.mpCurrent) value_type(
eastl::forward<Args>(args)...);
1822 value_type valueSaved(eastl::forward<Args>(args)...);
1824 if(mItBegin.mpCurrentArrayPtr == mpPtrArray)
1825 DoReallocPtrArray(1, kSideFront);
1827 mItBegin.mpCurrentArrayPtr[-1] = DoAllocateSubarray();
1829 #if EASTL_EXCEPTIONS_ENABLED
1833 mItBegin.SetSubarray(mItBegin.mpCurrentArrayPtr - 1);
1834 mItBegin.mpCurrent = mItBegin.mpEnd - 1;
1835 ::new((
void*)mItBegin.mpCurrent) value_type(
eastl::move(valueSaved));
1836 #if EASTL_EXCEPTIONS_ENABLED
1841 DoFreeSubarray(mItBegin.mpCurrentArrayPtr[-1]);
1848 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1849 template<
class... Args>
1850 void deque<T, Allocator, kDequeSubarraySize>::emplace_back(Args&&... args)
1852 if((mItEnd.mpCurrent + 1) != mItEnd.mpEnd)
1853 ::new((
void*)mItEnd.mpCurrent++) value_type(
eastl::forward<Args>(args)...);
1857 value_type valueSaved(eastl::forward<Args>(args)...);
1858 if(((mItEnd.mpCurrentArrayPtr - mpPtrArray) + 1) >= (difference_type)mnPtrArraySize)
1859 DoReallocPtrArray(1, kSideBack);
1861 mItEnd.mpCurrentArrayPtr[1] = DoAllocateSubarray();
1863 #if EASTL_EXCEPTIONS_ENABLED
1867 ::new((
void*)mItEnd.mpCurrent) value_type(
eastl::move(valueSaved));
1868 mItEnd.SetSubarray(mItEnd.mpCurrentArrayPtr + 1);
1869 mItEnd.mpCurrent = mItEnd.mpBegin;
1870 #if EASTL_EXCEPTIONS_ENABLED
1875 DoFreeSubarray(mItEnd.mpCurrentArrayPtr[1]);
1883 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1884 typename deque<T, Allocator, kDequeSubarraySize>::iterator
1885 deque<T, Allocator, kDequeSubarraySize>::insert(const_iterator position,
const value_type& value)
1887 return emplace(position, value);
1891 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1892 typename deque<T, Allocator, kDequeSubarraySize>::iterator
1893 deque<T, Allocator, kDequeSubarraySize>::insert(const_iterator position, value_type&& value)
1899 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1900 void deque<T, Allocator, kDequeSubarraySize>::insert(const_iterator position, size_type n,
const value_type& value)
1902 DoInsertValues(position, n, value);
1906 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1907 template <
typename InputIterator>
1908 void deque<T, Allocator, kDequeSubarraySize>::insert(const_iterator position, InputIterator first, InputIterator last)
1910 DoInsert(position, first, last, is_integral<InputIterator>());
1914 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1915 typename deque<T, Allocator, kDequeSubarraySize>::iterator
1918 const difference_type i(position - mItBegin);
1919 DoInsert(position, ilist.begin(), ilist.end(), false_type());
1920 return (mItBegin + i);
1924 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1925 typename deque<T, Allocator, kDequeSubarraySize>::iterator
1926 deque<T, Allocator, kDequeSubarraySize>::erase(const_iterator position)
1928 #if EASTL_ASSERT_ENABLED
1929 if(EASTL_UNLIKELY(!(validate_iterator(position) & isf_valid)))
1930 EASTL_FAIL_MSG(
"deque::erase -- invalid iterator");
1932 if(EASTL_UNLIKELY(position == end()))
1933 EASTL_FAIL_MSG(
"deque::erase -- end() iterator is an invalid iterator for erase");
1936 iterator itPosition(position,
typename iterator::FromConst());
1937 iterator itNext(itPosition,
typename iterator::Increment());
1938 const difference_type i(itPosition - mItBegin);
1940 if(i < (difference_type)(size() / 2))
1951 return mItBegin + i;
1955 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
1956 typename deque<T, Allocator, kDequeSubarraySize>::iterator
1957 deque<T, Allocator, kDequeSubarraySize>::erase(const_iterator first, const_iterator last)
1959 iterator itFirst(first,
typename iterator::FromConst());
1960 iterator itLast(last,
typename iterator::FromConst());
1962 #if EASTL_ASSERT_ENABLED
1963 if(EASTL_UNLIKELY(!(validate_iterator(itFirst) & isf_valid)))
1964 EASTL_FAIL_MSG(
"deque::erase -- invalid iterator");
1965 if(EASTL_UNLIKELY(!(validate_iterator(itLast) & isf_valid)))
1966 EASTL_FAIL_MSG(
"deque::erase -- invalid iterator");
1969 if((itFirst != mItBegin) || (itLast != mItEnd))
1971 const difference_type n(itLast - itFirst);
1972 const difference_type i(itFirst - mItBegin);
1974 if(i < (difference_type)((size() - n) / 2))
1976 const iterator itNewBegin(mItBegin + n);
1977 value_type**
const pPtrArrayBegin = mItBegin.mpCurrentArrayPtr;
1981 for(; mItBegin != itNewBegin; ++mItBegin)
1982 mItBegin.mpCurrent->~value_type();
1984 DoFreeSubarrays(pPtrArrayBegin, itNewBegin.mpCurrentArrayPtr);
1990 iterator itNewEnd(mItEnd - n);
1991 value_type**
const pPtrArrayEnd = itNewEnd.mpCurrentArrayPtr + 1;
1995 for(iterator itTemp(itNewEnd); itTemp != mItEnd; ++itTemp)
1996 itTemp.mpCurrent->~value_type();
1998 DoFreeSubarrays(pPtrArrayEnd, mItEnd.mpCurrentArrayPtr + 1);
2003 return mItBegin + i;
2011 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2012 typename deque<T, Allocator, kDequeSubarraySize>::reverse_iterator
2013 deque<T, Allocator, kDequeSubarraySize>::erase(reverse_iterator position)
2015 return reverse_iterator(erase((++position).base()));
2019 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2020 typename deque<T, Allocator, kDequeSubarraySize>::reverse_iterator
2021 deque<T, Allocator, kDequeSubarraySize>::erase(reverse_iterator first, reverse_iterator last)
2030 return reverse_iterator(erase(last.base(), first.base()));
2034 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2035 void deque<T, Allocator, kDequeSubarraySize>::clear()
2039 if(mItBegin.mpCurrentArrayPtr != mItEnd.mpCurrentArrayPtr)
2041 for(value_type* p1 = mItBegin.mpCurrent; p1 < mItBegin.mpEnd; ++p1)
2043 for(value_type* p2 = mItEnd.mpBegin; p2 < mItEnd.mpCurrent; ++p2)
2045 DoFreeSubarray(mItEnd.mpBegin);
2049 for(value_type* p = mItBegin.mpCurrent; p < mItEnd.mpCurrent; ++p)
2054 for(value_type** pPtrArray = mItBegin.mpCurrentArrayPtr + 1; pPtrArray < mItEnd.mpCurrentArrayPtr; ++pPtrArray)
2056 for(value_type* p = *pPtrArray, *pEnd = *pPtrArray + kDequeSubarraySize; p < pEnd; ++p)
2058 DoFreeSubarray(*pPtrArray);
2083 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2084 void deque<T, Allocator, kDequeSubarraySize>::swap(deque& x)
2086 #if defined(EASTL_DEQUE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR) && EASTL_DEQUE_LEGACY_SWAP_BEHAVIOUR_REQUIRES_COPY_CTOR
2087 if(mAllocator == x.mAllocator)
2091 const this_type temp(*
this);
2111 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2112 template <
typename Integer>
2113 void deque<T, Allocator, kDequeSubarraySize>::DoInit(Integer n, Integer value, true_type)
2115 base_type::DoInit(n);
2120 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2121 template <
typename InputIterator>
2122 void deque<T, Allocator, kDequeSubarraySize>::DoInit(InputIterator first, InputIterator last, false_type)
2124 typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
2125 DoInitFromIterator(first, last, IC());
2129 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2130 template <
typename InputIterator>
2131 void deque<T, Allocator, kDequeSubarraySize>::DoInitFromIterator(InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag)
2133 base_type::DoInit(0);
2135 #if EASTL_EXCEPTIONS_ENABLED
2142 for(; first != last; ++first)
2146 #if EASTL_EXCEPTIONS_ENABLED
2157 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2158 template <
typename ForwardIterator>
2159 void deque<T, Allocator, kDequeSubarraySize>::DoInitFromIterator(ForwardIterator first, ForwardIterator last, EASTL_ITC_NS::forward_iterator_tag)
2161 typedef typename eastl::remove_const<ForwardIterator>::type non_const_iterator_type;
2162 typedef typename eastl::remove_const<value_type>::type non_const_value_type;
2164 const size_type n = (size_type)eastl::distance(first, last);
2165 value_type** pPtrArrayCurrent;
2167 base_type::DoInit(n);
2169 #if EASTL_EXCEPTIONS_ENABLED
2173 for(pPtrArrayCurrent = mItBegin.mpCurrentArrayPtr; pPtrArrayCurrent < mItEnd.mpCurrentArrayPtr; ++pPtrArrayCurrent)
2176 ForwardIterator current(first);
2178 eastl::advance(current, kDequeSubarraySize);
2179 eastl::uninitialized_copy((non_const_iterator_type)first, (non_const_iterator_type)current, (non_const_value_type*)*pPtrArrayCurrent);
2183 eastl::uninitialized_copy((non_const_iterator_type)first, (non_const_iterator_type)last, (non_const_value_type*)mItEnd.mpBegin);
2184 #if EASTL_EXCEPTIONS_ENABLED
2188 for(iterator itCurrent(mItBegin), itEnd(pPtrArrayCurrent, *pPtrArrayCurrent); itCurrent != itEnd; ++itCurrent)
2189 itCurrent.mpCurrent->~value_type();
2196 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2197 void deque<T, Allocator, kDequeSubarraySize>::DoFillInit(
const value_type& value)
2199 value_type** pPtrArrayCurrent = mItBegin.mpCurrentArrayPtr;
2201 #if EASTL_EXCEPTIONS_ENABLED
2205 while(pPtrArrayCurrent < mItEnd.mpCurrentArrayPtr)
2207 eastl::uninitialized_fill(*pPtrArrayCurrent, *pPtrArrayCurrent + kDequeSubarraySize, value);
2210 eastl::uninitialized_fill(mItEnd.mpBegin, mItEnd.mpCurrent, value);
2211 #if EASTL_EXCEPTIONS_ENABLED
2215 for(iterator itCurrent(mItBegin), itEnd(pPtrArrayCurrent, *pPtrArrayCurrent); itCurrent != itEnd; ++itCurrent)
2216 itCurrent.mpCurrent->~value_type();
2223 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2224 template <
typename Integer>
2225 void deque<T, Allocator, kDequeSubarraySize>::DoAssign(Integer n, Integer value, true_type)
2227 DoAssignValues(
static_cast<size_type
>(n),
static_cast<value_type
>(value));
2231 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2232 template <
typename InputIterator>
2233 void deque<T, Allocator, kDequeSubarraySize>::DoAssign(InputIterator first, InputIterator last, false_type)
2237 const size_type n = (size_type)eastl::distance(first, last);
2238 const size_type nSize = size();
2242 InputIterator atEnd(first);
2244 eastl::advance(atEnd, (difference_type)nSize);
2246 insert(mItEnd, atEnd, last);
2250 iterator itEnd(
eastl::copy(first, last, mItBegin));
2253 erase(itEnd, mItEnd);
2258 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2259 void deque<T, Allocator, kDequeSubarraySize>::DoAssignValues(size_type n,
const value_type& value)
2261 const size_type nSize = size();
2266 insert(mItEnd, n - nSize, value);
2270 erase(mItBegin + (difference_type)n, mItEnd);
2276 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2277 template <
typename Integer>
2278 void deque<T, Allocator, kDequeSubarraySize>::DoInsert(
const const_iterator& position, Integer n, Integer value, true_type)
2280 DoInsertValues(position, (size_type)n, (value_type)value);
2284 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2285 template <
typename InputIterator>
2286 void deque<T, Allocator, kDequeSubarraySize>::DoInsert(
const const_iterator& position,
const InputIterator& first,
const InputIterator& last, false_type)
2288 typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
2289 DoInsertFromIterator(position, first, last, IC());
2293 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2294 template <
typename InputIterator>
2295 void deque<T, Allocator, kDequeSubarraySize>::DoInsertFromIterator(const_iterator position,
const InputIterator& first,
const InputIterator& last, EASTL_ITC_NS::forward_iterator_tag)
2297 const size_type n = (size_type)eastl::distance(first, last);
2301 if(position.mpCurrent == mItBegin.mpCurrent)
2303 iterator itNewBegin(DoReallocSubarray(n, kSideFront));
2305 #if EASTL_EXCEPTIONS_ENABLED
2313 mItBegin = itNewBegin;
2314 #if EASTL_EXCEPTIONS_ENABLED
2318 DoFreeSubarrays(itNewBegin.mpCurrentArrayPtr, mItBegin.mpCurrentArrayPtr);
2323 else if(EASTL_UNLIKELY(position.mpCurrent == mItEnd.mpCurrent))
2325 const iterator itNewEnd(DoReallocSubarray(n, kSideBack));
2327 #if EASTL_EXCEPTIONS_ENABLED
2336 #if EASTL_EXCEPTIONS_ENABLED
2340 DoFreeSubarrays(mItEnd.mpCurrentArrayPtr + 1, itNewEnd.mpCurrentArrayPtr + 1);
2347 const difference_type nInsertionIndex = position - mItBegin;
2348 const size_type nSize = size();
2350 if(nInsertionIndex < (difference_type)(nSize / 2))
2352 const iterator itNewBegin(DoReallocSubarray(n, kSideFront));
2353 const iterator itOldBegin(mItBegin);
2354 const iterator itPosition(mItBegin + nInsertionIndex);
2356 #if EASTL_EXCEPTIONS_ENABLED
2363 if(nInsertionIndex >= (difference_type)n)
2365 iterator itUCopyEnd(mItBegin + (difference_type)n);
2368 itUCopyEnd =
eastl::copy(itUCopyEnd, itPosition, itOldBegin);
2373 InputIterator mid(first);
2375 eastl::advance(mid, (difference_type)n - nInsertionIndex);
2379 mItBegin = itNewBegin;
2380 #if EASTL_EXCEPTIONS_ENABLED
2384 DoFreeSubarrays(itNewBegin.mpCurrentArrayPtr, mItBegin.mpCurrentArrayPtr);
2391 const iterator itNewEnd(DoReallocSubarray(n, kSideBack));
2392 const iterator itOldEnd(mItEnd);
2393 const difference_type nPushedCount = (difference_type)nSize - nInsertionIndex;
2394 const iterator itPosition(mItEnd - nPushedCount);
2396 #if EASTL_EXCEPTIONS_ENABLED
2403 if(nPushedCount > (difference_type)n)
2405 const iterator itUCopyEnd(mItEnd - (difference_type)n);
2413 InputIterator mid(first);
2415 eastl::advance(mid, nPushedCount);
2420 #if EASTL_EXCEPTIONS_ENABLED
2424 DoFreeSubarrays(mItEnd.mpCurrentArrayPtr + 1, itNewEnd.mpCurrentArrayPtr + 1);
2433 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2434 void deque<T, Allocator, kDequeSubarraySize>::DoInsertValues(const_iterator position, size_type n,
const value_type& value)
2436 #if EASTL_ASSERT_ENABLED
2437 if(EASTL_UNLIKELY(!(validate_iterator(position) & isf_valid)))
2438 EASTL_FAIL_MSG(
"deque::insert -- invalid iterator");
2443 if(position.mpCurrent == mItBegin.mpCurrent)
2445 const iterator itNewBegin(DoReallocSubarray(n, kSideFront));
2447 #if EASTL_EXCEPTIONS_ENABLED
2454 eastl::uninitialized_fill(itNewBegin, mItBegin, value);
2455 mItBegin = itNewBegin;
2456 #if EASTL_EXCEPTIONS_ENABLED
2460 DoFreeSubarrays(itNewBegin.mpCurrentArrayPtr, mItBegin.mpCurrentArrayPtr);
2465 else if(EASTL_UNLIKELY(position.mpCurrent == mItEnd.mpCurrent))
2467 const iterator itNewEnd(DoReallocSubarray(n, kSideBack));
2469 #if EASTL_EXCEPTIONS_ENABLED
2476 eastl::uninitialized_fill(mItEnd, itNewEnd, value);
2478 #if EASTL_EXCEPTIONS_ENABLED
2482 DoFreeSubarrays(mItEnd.mpCurrentArrayPtr + 1, itNewEnd.mpCurrentArrayPtr + 1);
2495 const difference_type nInsertionIndex = position - mItBegin;
2496 const size_type nSize = size();
2497 const value_type valueSaved(value);
2499 if(nInsertionIndex < (difference_type)(nSize / 2))
2501 const iterator itNewBegin(DoReallocSubarray(n, kSideFront));
2502 const iterator itOldBegin(mItBegin);
2503 const iterator itPosition(mItBegin + nInsertionIndex);
2505 #if EASTL_EXCEPTIONS_ENABLED
2509 if(nInsertionIndex >= (difference_type)n)
2511 iterator itUCopyEnd(mItBegin + (difference_type)n);
2514 itUCopyEnd =
eastl::move(itUCopyEnd, itPosition, itOldBegin);
2522 mItBegin = itNewBegin;
2523 #if EASTL_EXCEPTIONS_ENABLED
2527 DoFreeSubarrays(itNewBegin.mpCurrentArrayPtr, mItBegin.mpCurrentArrayPtr);
2534 const iterator itNewEnd(DoReallocSubarray(n, kSideBack));
2535 const iterator itOldEnd(mItEnd);
2536 const difference_type nPushedCount = (difference_type)nSize - nInsertionIndex;
2537 const iterator itPosition(mItEnd - nPushedCount);
2539 #if EASTL_EXCEPTIONS_ENABLED
2543 if(nPushedCount > (difference_type)n)
2545 iterator itUCopyEnd(mItEnd - (difference_type)n);
2557 #if EASTL_EXCEPTIONS_ENABLED
2561 DoFreeSubarrays(mItEnd.mpCurrentArrayPtr + 1, itNewEnd.mpCurrentArrayPtr + 1);
2570 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2571 inline void deque<T, Allocator, kDequeSubarraySize>::DoSwap(this_type& x)
2573 eastl::swap(mpPtrArray, x.mpPtrArray);
2574 eastl::swap(mnPtrArraySize, x.mnPtrArraySize);
2575 eastl::swap(mItBegin, x.mItBegin);
2576 eastl::swap(mItEnd, x.mItEnd);
2577 eastl::swap(mAllocator, x.mAllocator);
2582 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2583 inline bool deque<T, Allocator, kDequeSubarraySize>::validate()
const
2587 if((end() - begin()) < 0)
2593 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2594 inline int deque<T, Allocator, kDequeSubarraySize>::validate_iterator(const_iterator i)
const
2598 if((i - begin()) < 0)
2605 return (isf_valid | isf_current);
2607 return (isf_valid | isf_current | isf_can_dereference);
2616 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2617 inline bool operator==(
const deque<T, Allocator, kDequeSubarraySize>& a,
const deque<T, Allocator, kDequeSubarraySize>& b)
2619 return ((a.size() == b.size()) &&
eastl::equal(a.begin(), a.end(), b.begin()));
2622 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2623 inline bool operator!=(
const deque<T, Allocator, kDequeSubarraySize>& a,
const deque<T, Allocator, kDequeSubarraySize>& b)
2625 return ((a.size() != b.size()) || !
eastl::equal(a.begin(), a.end(), b.begin()));
2628 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2629 inline bool operator<(
const deque<T, Allocator, kDequeSubarraySize>& a,
const deque<T, Allocator, kDequeSubarraySize>& b)
2634 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2635 inline bool operator>(
const deque<T, Allocator, kDequeSubarraySize>& a,
const deque<T, Allocator, kDequeSubarraySize>& b)
2640 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2641 inline bool operator<=(
const deque<T, Allocator, kDequeSubarraySize>& a,
const deque<T, Allocator, kDequeSubarraySize>& b)
2646 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2647 inline bool operator>=(
const deque<T, Allocator, kDequeSubarraySize>& a,
const deque<T, Allocator, kDequeSubarraySize>& b)
2652 template <
typename T,
typename Allocator,
unsigned kDequeSubarraySize>
2653 inline void swap(deque<T, Allocator, kDequeSubarraySize>& a, deque<T, Allocator, kDequeSubarraySize>& b)
2663 template <
class T,
class Allocator,
class U>
2664 void erase(deque<T, Allocator>& c,
const U& value)
2670 template <
class T,
class Allocator,
class Predicate>
2671 void erase_if(deque<T, Allocator>& c, Predicate predicate)
2681 EA_RESTORE_VC_WARNING();
2682 #if EASTL_EXCEPTIONS_ENABLED
2683 EA_RESTORE_VC_WARNING();
Definition: allocator.h:52
Definition: iterator.h:224
Definition: initializer_list.h:38
EA Standard Template Library.
Definition: algorithm.h:288
ForwardIterator uninitialized_move_if_noexcept(InputIterator first, InputIterator last, ForwardIterator dest)
Definition: memory.h:777
void uninitialized_move_fill(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, const T &value)
Definition: memory.h:1199
ForwardIterator uninitialized_copy_copy(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, ForwardIterator result)
Definition: memory.h:1289
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T &value)
Definition: algorithm.h:2581
ForwardIterator uninitialized_fill_move(ForwardIterator result, ForwardIterator mid, const T &value, InputIterator first, InputIterator last)
Definition: memory.h:1259
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
Definition: copy_help.h:191
void fill(ForwardIterator first, ForwardIterator last, const T &value)
Definition: fill_help.h:75
OutputIterator move(InputIterator first, InputIterator last, OutputIterator result)
Definition: copy_help.h:170
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate predicate)
Definition: algorithm.h:2618
EA_CPP14_CONSTEXPR bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
Definition: algorithm.h:1856
EA_CONSTEXPR eastl::enable_if< eastl::is_scalar< T >::value, T >::type max_alt(T a, T b)
Definition: algorithm.h:584
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result)
Definition: memory.h:601
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Definition: algorithm.h:1996
BidirectionalIterator2 move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
Definition: algorithm.h:1304
void * allocate_memory(Allocator &a, size_t n, size_t alignment, size_t alignmentOffset)
Definition: allocator.h:354
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 resultEnd)
Definition: algorithm.h:1325
static const size_type kMaxSize
'npos' means non-valid position or simply non-position.
Definition: deque.h:269
Side
Defines the side of the deque: front or back.
Definition: deque.h:279
@ kSideBack
Identifies the front side of the deque.
Definition: deque.h:281
@ kSubarraySize
A new empty deque has a ptrArraySize of 0, but any allocated ptrArrays use this min size.
Definition: deque.h:274
Definition: iterator.h:75
Definition: type_pod.h:398
Definition: type_traits.h:263
Definition: iterator.h:86