array vs vector

[Ujl]

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:

std::vector<int> x(100000000);

takes 0.42...s

 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

[vinodp]

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

[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.

[Ujl]

You're probably right. Do you know if there is a way to just allocate memory without initializing the vector?

thanks for your help

[aewarnick]

I don't mind giving the code out:

//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;
    }
}; 

[Ujl]

Thanks a lot!

[Mitsukai]

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.

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;

[Mitsukai]

I don't mind giving the code out:

//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.

[laserlight]

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.

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.

[RoboTact]

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.

[Mitsukai]

There is no point in having uninitialized array. This difference doesn't count.

imho thats very untrue. there is no point in initializing it.

[Mitsukai]

std::vector<int> x(100000000);
int y = x[5];//you know this is 0. no point in this

[laserlight]

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?

[Mitsukai]

read th thread

[laserlight]

read th thread

Sorry, but I cannot make out what you are trying to say.