57 #ifndef __SmallVector_H
58 #define __SmallVector_H
74 template<
class T1,
class T2>
75 inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) {
76 _Scalar_ptr_iterator_tag _Cat;
80 template<
class T1,
class T2>
81 inline _Scalar_ptr_iterator_tag _Ptr_cat(T1*
const *, T2 **) {
82 _Scalar_ptr_iterator_tag _Cat;
99 template <>
struct isPodLike<signed char> {
static const bool value =
true; };
104 template <>
struct isPodLike<unsigned short> {
static const bool value =
true; };
109 template <
typename T>
struct isPodLike<T*> {
static const bool value =
true; };
111 template<
typename T,
typename U>
155 void grow_pod(
size_t MinSizeInBytes,
size_t TSize);
162 template <
typename T>
237 template <
typename T,
bool isPodLike>
251 template<
typename It1,
typename It2>
253 std::uninitialized_copy(I, E, Dest);
258 void grow(
size_t MinSize = 0);
262 template <
typename T,
bool isPodLike>
264 size_t CurCapacity = this->capacity();
265 size_t CurSize = this->size();
266 size_t NewCapacity = 2*CurCapacity + 1;
267 if (NewCapacity < MinSize)
268 NewCapacity = MinSize;
269 T *NewElts =
static_cast<T*
>(malloc(NewCapacity*
sizeof(T)));
272 this->uninitialized_copy(this->begin(), this->end(), NewElts);
275 destroy_range(this->begin(), this->end());
278 if (!this->isSmall())
281 this->setEnd(NewElts+CurSize);
282 this->BeginX = NewElts;
283 this->CapacityX = this->begin()+NewCapacity;
289 template <
typename T>
299 template<
typename It1,
typename It2>
302 std::uninitialized_copy(I, E, Dest);
307 template<
typename T1,
typename T2>
312 memcpy(Dest, I, (E-I)*
sizeof(T));
317 void grow(
size_t MinSize = 0) {
318 this->
grow_pod(MinSize*
sizeof(T),
sizeof(T));
326 template <
typename T>
356 if (N < this->
size()) {
359 }
else if (N > this->
size()) {
368 if (N < this->
size()) {
371 }
else if (N > this->
size()) {
387 new (this->
end()) T(Elt);
401 T Result = this->
back();
410 template<
typename in_iter>
411 void append(in_iter in_start, in_iter in_end) {
412 size_type NumInputs = std::distance(in_start, in_end);
420 std::uninitialized_copy(in_start, in_end, this->
end());
432 std::uninitialized_fill_n(this->
end(), NumInputs, Elt);
436 void assign(
unsigned NumElts,
const T &Elt) {
447 std::copy(I+1, this->
end(), I);
464 if (I == this->
end()) {
466 return this->
end()-1;
471 new (this->
end()) T(this->
back());
474 std::copy_backward(I, this->
end()-1, this->
end());
478 size_t EltNo = I-this->
begin();
480 I = this->
begin()+EltNo;
485 if (I == this->
end()) {
487 return this->
end()-1;
491 size_t InsertElt = I - this->
begin();
494 reserve(static_cast<unsigned>(this->
size() + NumToInsert));
497 I = this->
begin()+InsertElt;
503 if (
size_t(this->
end()-I) >= NumToInsert) {
504 T *OldEnd = this->
end();
508 std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
510 std::fill_n(I, NumToInsert, Elt);
518 T *OldEnd = this->
end();
520 size_t NumOverwritten = OldEnd-I;
524 std::fill_n(I, NumOverwritten, Elt);
527 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
531 template<
typename ItTy>
533 if (I == this->
end()) {
535 return this->
end()-1;
538 size_t NumToInsert = std::distance(From, To);
540 size_t InsertElt = I - this->
begin();
543 reserve(static_cast<unsigned>(this->
size() + NumToInsert));
546 I = this->
begin()+InsertElt;
552 if (
size_t(this->
end()-I) >= NumToInsert) {
553 T *OldEnd = this->
end();
557 std::copy_backward(I, OldEnd-NumToInsert, OldEnd);
559 std::copy(From, To, I);
567 T *OldEnd = this->
end();
569 size_t NumOverwritten = OldEnd-I;
573 for (; NumOverwritten > 0; --NumOverwritten) {
587 if (this->
size() != RHS.
size())
return false;
591 return !(*
this == RHS);
595 return std::lexicographical_compare(this->
begin(), this->
end(),
621 template <
typename T>
623 if (
this == &RHS)
return;
626 if (!this->isSmall() && !RHS.
isSmall()) {
632 if (RHS.
size() > this->capacity())
633 this->grow(RHS.
size());
635 RHS.
grow(this->size());
638 size_t NumShared = this->size();
639 if (NumShared > RHS.
size()) NumShared = RHS.
size();
640 for (
unsigned i = 0; i !=
static_cast<unsigned>(NumShared); ++i)
644 if (this->size() > RHS.
size()) {
645 size_t EltDiff = this->size() - RHS.
size();
646 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.
end());
648 this->destroy_range(this->begin()+NumShared, this->end());
649 this->setEnd(this->begin()+NumShared);
650 }
else if (RHS.
size() > this->size()) {
651 size_t EltDiff = RHS.
size() - this->size();
652 this->uninitialized_copy(RHS.
begin()+NumShared, RHS.
end(), this->end());
653 this->setEnd(this->end() + EltDiff);
654 this->destroy_range(RHS.
begin()+NumShared, RHS.
end());
659 template <
typename T>
663 if (
this == &RHS)
return *
this;
667 size_t RHSSize = RHS.
size();
668 size_t CurSize = this->size();
669 if (CurSize >= RHSSize) {
673 NewEnd = std::copy(RHS.
begin(), RHS.
begin()+RHSSize, this->begin());
675 NewEnd = this->begin();
678 this->destroy_range(NewEnd, this->end());
681 this->setEnd(NewEnd);
687 if (this->capacity() < RHSSize) {
689 this->destroy_range(this->begin(), this->end());
690 this->setEnd(this->begin());
693 }
else if (CurSize) {
695 std::copy(RHS.
begin(), RHS.
begin()+CurSize, this->begin());
699 this->uninitialized_copy(RHS.
begin()+CurSize, RHS.
end(),
700 this->begin()+CurSize);
703 this->setEnd(this->begin()+RHSSize);
716 template <
typename T,
unsigned N>
723 MinUs = (
static_cast<unsigned int>(
sizeof(T))*N +
724 static_cast<unsigned int>(
sizeof(
U)) - 1) /
725 static_cast<unsigned int>(
sizeof(
U)),
730 NumInlineEltsElts =
MinUs > 1 ? (
MinUs - 1) : 1,
734 NumTsAvailable = (NumInlineEltsElts+1)*static_cast<unsigned int>(
sizeof(
U))/
735 static_cast<unsigned int>(
sizeof(T))
749 template<
typename ItTy>
769 template <
typename T>
781 template<
typename ItTy>
807 template<
typename T,
unsigned N>