|
-
May 10th, 2006, 10:51 AM
#1
array vs vector
hi,
I've just tried to measure the performance of the std::vector vs traditional array, and I'm quite surprised to see that initializing a vector is WAY longer than initializing an array:
Code:
std::vector<int> x(100000000);
takes 0.42...s
Code:
int* a=new int[100000000];
takes 0.00...s
Why is there such a huge difference? With such a difference, I guess people only use std::vector when they need features such as insert?
Ujl
-
May 10th, 2006, 11:13 AM
#2
Re: array vs vector
I guess it has something to do with initilization of integer.
std::vector will initilize it with ZERO but the traditional array will not
>>With such a difference, I guess people only use std::vector when they >>need features such as insert?
your forgetting about the memory management. Vector will take care of all memory allocation & deallocation for you.
Vinod
-
May 10th, 2006, 11:19 AM
#3
Re: array vs vector
There is absolutely no need for vector to initialize elements to 0. Now I'm REALLY glad I created and use my own Array class.
-
May 10th, 2006, 11:22 AM
#4
Re: array vs vector
You're probably right. Do you know if there is a way to just allocate memory without initializing the vector?
thanks for your help
-
May 10th, 2006, 11:28 AM
#5
Re: array vs vector
I don't mind giving the code out:
PHP Code:
//faster than vector w/o malloc. About 1.5 times faster than vector with malloc!
//use pointers instead of classes when using malloc.
template < typename T >
class aArr
{
protected:
uint capacity;
public:
T* _Items;
bool cppAllocation;
uint Count;
aArr()
{
Reset();
}
aArr(uint initCapacity, bool cppStyleAllocation= 0)
{
Reset();
capacity= initCapacity;
cppAllocation= cppStyleAllocation;
if(cppAllocation)
_Items= new T[capacity];
else
_Items= (T*)malloc(initCapacity*sizeof(T));
}
/*aArr(const T &item) //ambiguous when item is uint
{
Reset();
Add(item);
}*/
~aArr()
{
Del();
}
void Del(uint initCapacity= 0)
{
if(_Items)
{
if(cppAllocation)
delete[]_Items;
else
free(_Items); //free is 2x faster than delete[]
_Items= 0;
}
Count= 0; capacity= 0;
}
void Reset()
{
_Items= 0;
Count= 0;
capacity= 0;
cppAllocation= 0;
}
T& operator[](uint ind)
{
return _Items[ind];
}
T& Ind(uint ind)
{
return _Items[ind];
}
void Add(const T& d)
{
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
if(cppAllocation)
_Items[Count]= d;
else
memcpy(&_Items[Count], &d, sizeof(T));
++Count;
}
void Ins(uint where, aArr < T* > &arr)
{
if(!arr.Count) return;
if(!Count || where >= Count)
{
for(uint i= 0; i < arr.Count; ++i)
Add(arr[i]);
return;
}
if(Count+arr.Count >= capacity)
Resize(Count < 10 ? 20+arr.Count : Count*1.5f +arr.Count);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
if(cppAllocation)
{
for(uint i= 0; i < arr.Count; ++i)
_Items[where+i]= *arr[i];
}
else
memcpy(&_Items[where], arr[0], sT*arr.Count);
memcpy(&_Items[where+arr.Count], buf.Ptr(), sTemp);
//free(temp);
Count += arr.Count;
}
void Ins(uint where, const T& d)
{
//aArr<T*> arr; arr.Add(&d);
//Ins(where, arr);
//return;
if(!Count || where >= Count)
{
Add(d);
return;
}
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
if(cppAllocation)
_Items[where]= d;
else
memcpy(&_Items[where], &d, sT);
memcpy(&_Items[where+1], buf.Ptr(), sTemp);
//free(temp);
++Count;
}
void Rem(aArr < uint > & arr)
{
T* temp= _Items;
capacity= Count;
if(cppAllocation)
_Items= new T[capacity];
else
_Items= (T*)malloc(capacity*sizeof(T));
uint count= Count;
Count= 0;
uint removed= -1;
for(uint i= 0; i < count; ++i)
{
for(uint j= 0; j < arr.Count; ++j)
{
if(i == arr[j])
{
removed= i;
break;
}
}
if(removed == -1)
{
Add(temp[i]);
}
else
{
removed= -1;
}
}
if(cppAllocation)
delete[]temp;
else
free(temp);
}
void Rem(uint ind)
{
aArr < uint > arr(1);
arr.Add(ind);
Rem(arr);
}
void RemAll()
{
Del();
}
void Resize(uint newSize)
{
capacity= newSize;
if(cppAllocation)
{
T* temp= _Items;
_Items= new T[capacity]; memcpy(_Items, temp, Count*sizeof(T)); delete[]temp;
}
else _Items= (T*)realloc(_Items, newSize*sizeof(T));
if(capacity < Count)
Count= capacity;
}
private:
static int _ascending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return 1;
if(*((T*)v1) < *((T*)v2)) return -1;
return 0;
}
static int _descending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return -1;
if(*((T*)v1) < *((T*)v2)) return 1;
return 0;
}
public:
void Sort(char A_D= 'A')
{
if(A_D == 'A') qsort(&_Items[0], Count, sizeof(T), &_ascending);
else qsort(&_Items[0], Count, sizeof(T), &_descending);
return;
const int tSize= sizeof(T);
void* hold[tSize];
for(int i= 0; i < Count; ++i)
{
for(int j= 0; j < Count-1; ++j)
{
if((A_D == 'A' && _Items[j] > _Items[j+1]) || (A_D == 'D' && _Items[j] < _Items[j+1]))
{
Swap(&_Items[j], &_Items[j+1], tSize, &hold);
}
}
}
}
aStr ToStr()
{
aStr s;
for(uint i= 0; i < Count; ++i)
{
s= s << _Items[i] << "\n";
}
return s;
}
};
-
May 10th, 2006, 11:35 AM
#6
-
May 10th, 2006, 11:41 AM
#7
Re: array vs vector
for allocating int's use malloc/calloc and realloc and free(look on msdn)
for objects use this method. its does not use a buffer.
Code:
void ReSize(int*& Src, int OldSize, int NewSize)
{
if(OldSize == NewSize)
return;
int* arr = new int[NewSize];
int* iarr = arr;
int* isrc = Src;
for(int* iend = arr + NewSize < OldSize ? NewSize : OldSize; iarr != iend; ++iarr, ++isrc)
*iarr =*isrc;
delete[] Src;
Src = arr;
}
int* a=new int[100 000 000];
ReSize(a, 100 000 000, 50 000 000);
delete[] a;
Last edited by Mitsukai; May 10th, 2006 at 11:57 AM.
-
May 10th, 2006, 11:49 AM
#8
Re: array vs vector
 Originally Posted by aewarnick
I don't mind giving the code out:
PHP Code:
//faster than vector w/o malloc. About 1.5 times faster than vector with malloc!
//use pointers instead of classes when using malloc.
template < typename T >
class aArr
{
protected:
uint capacity;
public:
T* _Items;
bool cppAllocation;
uint Count;
aArr()
{
Reset();
}
aArr(uint initCapacity, bool cppStyleAllocation= 0)
{
Reset();
capacity= initCapacity;
cppAllocation= cppStyleAllocation;
if(cppAllocation)
_Items= new T[capacity];
else
_Items= (T*)malloc(initCapacity*sizeof(T));
}
/*aArr(const T &item) //ambiguous when item is uint
{
Reset();
Add(item);
}*/
~aArr()
{
Del();
}
void Del(uint initCapacity= 0)
{
if(_Items)
{
if(cppAllocation)
delete[]_Items;
else
free(_Items); //free is 2x faster than delete[]
_Items= 0;
}
Count= 0; capacity= 0;
}
void Reset()
{
_Items= 0;
Count= 0;
capacity= 0;
cppAllocation= 0;
}
T& operator[](uint ind)
{
return _Items[ind];
}
T& Ind(uint ind)
{
return _Items[ind];
}
void Add(const T& d)
{
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
if(cppAllocation)
_Items[Count]= d;
else
memcpy(&_Items[Count], &d, sizeof(T));
++Count;
}
void Ins(uint where, aArr < T* > &arr)
{
if(!arr.Count) return;
if(!Count || where >= Count)
{
for(uint i= 0; i < arr.Count; ++i)
Add(arr[i]);
return;
}
if(Count+arr.Count >= capacity)
Resize(Count < 10 ? 20+arr.Count : Count*1.5f +arr.Count);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
if(cppAllocation)
{
for(uint i= 0; i < arr.Count; ++i)
_Items[where+i]= *arr[i];
}
else
memcpy(&_Items[where], arr[0], sT*arr.Count);
memcpy(&_Items[where+arr.Count], buf.Ptr(), sTemp);
//free(temp);
Count += arr.Count;
}
void Ins(uint where, const T& d)
{
//aArr<T*> arr; arr.Add(&d);
//Ins(where, arr);
//return;
if(!Count || where >= Count)
{
Add(d);
return;
}
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
if(cppAllocation)
_Items[where]= d;
else
memcpy(&_Items[where], &d, sT);
memcpy(&_Items[where+1], buf.Ptr(), sTemp);
//free(temp);
++Count;
}
void Rem(aArr < uint > & arr)
{
T* temp= _Items;
capacity= Count;
if(cppAllocation)
_Items= new T[capacity];
else
_Items= (T*)malloc(capacity*sizeof(T));
uint count= Count;
Count= 0;
uint removed= -1;
for(uint i= 0; i < count; ++i)
{
for(uint j= 0; j < arr.Count; ++j)
{
if(i == arr[j])
{
removed= i;
break;
}
}
if(removed == -1)
{
Add(temp[i]);
}
else
{
removed= -1;
}
}
if(cppAllocation)
delete[]temp;
else
free(temp);
}
void Rem(uint ind)
{
aArr < uint > arr(1);
arr.Add(ind);
Rem(arr);
}
void RemAll()
{
Del();
}
void Resize(uint newSize)
{
capacity= newSize;
if(cppAllocation)
{
T* temp= _Items;
_Items= new T[capacity]; memcpy(_Items, temp, Count*sizeof(T)); delete[]temp;
}
else _Items= (T*)realloc(_Items, newSize*sizeof(T));
if(capacity < Count)
Count= capacity;
}
private:
static int _ascending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return 1;
if(*((T*)v1) < *((T*)v2)) return -1;
return 0;
}
static int _descending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return -1;
if(*((T*)v1) < *((T*)v2)) return 1;
return 0;
}
public:
void Sort(char A_D= 'A')
{
if(A_D == 'A') qsort(&_Items[0], Count, sizeof(T), &_ascending);
else qsort(&_Items[0], Count, sizeof(T), &_descending);
return;
const int tSize= sizeof(T);
void* hold[tSize];
for(int i= 0; i < Count; ++i)
{
for(int j= 0; j < Count-1; ++j)
{
if((A_D == 'A' && _Items[j] > _Items[j+1]) || (A_D == 'D' && _Items[j] < _Items[j+1]))
{
Swap(&_Items[j], &_Items[j+1], tSize, &hold);
}
}
}
}
aStr ToStr()
{
aStr s;
for(uint i= 0; i < Count; ++i)
{
s= s << _Items[i] << "\n";
}
return s;
}
};
you have some serious issues here memcpy() cannot be used for copieing ojects. also using bool is not safe and also is slower. free is faster because it does not call object destructors.
-
May 10th, 2006, 12:21 PM
#9
Re: array vs vector
There is absolutely no need for vector to initialize elements to 0. Now I'm REALLY glad I created and use my own Array class.
aewarnick, in your case, there is absolutely no need to use the vector constructor that creates elements and zero initialises them. Dont complain about 'unnecessary' initialisation when you request for it.
Do you know if there is a way to just allocate memory without initializing the vector?
Ujl, create an empty vector, then reserve the space you want.
Code:
std::vector<int> x;
x.reserve(100000000);
Of course, x is still empty, so you still have to insert/push_back the elements.
I don't mind giving the code out
aewarnick, you need to go home and rethink your code. Your exposure of private mechanisms as public interface is rather disturbing. Your operator[] lacks a const version, and you use identifiers reserved to the implementation.
Last edited by laserlight; May 10th, 2006 at 12:24 PM.
-
May 10th, 2006, 12:25 PM
#10
Re: array vs vector
Originally Posted by aewarnick
There is absolutely no need for vector to initialize elements to 0. Now I'm REALLY glad I created and use my own Array class.
There is no point in having uninitialized array. This difference doesn't count.
"Programs must be written for people to read, and only incidentally for machines to execute."
-
May 10th, 2006, 12:27 PM
#11
Re: array vs vector
Originally Posted by RoboTact
There is no point in having uninitialized array. This difference doesn't count.
imho thats very untrue. there is no point in initializing it.
-
May 10th, 2006, 12:34 PM
#12
Re: array vs vector
Code:
std::vector<int> x(100000000);
int y = x[5];//you know this is 0. no point in this
-
May 10th, 2006, 12:39 PM
#13
Re: array vs vector
Originally Posted by Mitsukai
Code:
std::vector<int> x(100000000);
int y = x[5];//you know this is 0. no point in this
Um, how does this even factor into the discussion?
-
May 10th, 2006, 12:40 PM
#14
-
May 10th, 2006, 12:43 PM
#15
Re: array vs vector
Originally Posted by Mitsukai
read th thread
Sorry, but I cannot make out what you are trying to say.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote
