My custom vector

[Kikiman]

This is my custom vector. I'd like to create my own vector in order to keep settings if needed. I only made some changes to its design and it's nothing special. It does not support iterators, but I think they are redundant and without them will make my code clearer... About size it only takes 12 bytes instead of 16 bytes, and (maybe) it performs faster than the standard one. My algorithm is very clear :

- begin() : _array_start
- end() : _current

- (_array_end - _array_start) == capacity
- (_current - _array_start) == current_size
- (_current == _array_end) -> vector is full

- Push back : *_current++ = val;
- Pop back : _current--;

And here is my vector (I haven't tested all functions & features yet) :

#define __DESTRUCTOR(ty, ptr)	(ptr)->~ty()
#define __CONSTRUCTOR(ty, ptr)	(*ptr) = ty()
#define _array_start _array_data
#define _vector_capacity (_array_end - _array_start)
#define _vector_size (_current - _array_start)

template <class T>
class tVector
{
 
public:
 
	inline tVector(int nElements){
		_array_data = new T[nElements];
		_current = _array_start;
		_array_end = (_array_start + nElements);
	}
 
	inline tVector(){
		_array_data = new T[2];
		_current = _array_start;
		_array_end = (&_array_data[2]);
	}
 
	inline tVector(tVector<T> &obj){
		if((_vector_capacity) < (obj._current - obj._array_start))
			allocate(obj._current - obj._array_start);
		memcpy(_array_data, obj._array_data, (unsigned int)((char*)obj._array_end - (char*)obj._array_start));
		_current = _array_start + (obj._array_end - obj._array_start);
	}
 
	inline operator= (tVector<T> &obj){
		if((_vector_capacity) < (obj._array_end - obj._array_start))
			allocate(obj._current - obj._array_start);
		memcpy(_array_data, obj._array_data, (unsigned int)((char*)obj._array_end - (char*)obj._array_start));
		_current = _array_start + (obj._array_end - obj._array_start);
	}
 
	inline ~tVector(){delete []_array_data;}
 
	inline void double_size(){
		T *_temp = new T[(unsigned int)(_vector_capacity) * 2];
		_current = _temp + (_vector_capacity);
			memcpy(_temp, _array_data, (unsigned int)((char*)_array_end - (char*)_array_data));
		_array_end = _temp + (_array_end - _array_data) * 2;
		delete [] _array_data;_array_data = _temp;
	}
 
	inline void push_back(const T &t){
		if(_current == _array_end)double_size();*_current++ = t;
	}
 
	inline T& push_back_and_access(const T &t){
		if(_current == _array_end)double_size();*_current++ = t;return _current[-1];
	}
 
	inline void pop_back(){_current -= (_current != _array_start);}
	inline void pop_back_and_destroy(){
		if(_current != _array_start){_current--;__DESTRUCTOR(T, _current]);}}
 
	inline void resize(size_t size){
		if((_vector_size) == size)return;
 
		T *it;
		if((_vector_size) < size){
		if((_vector_capacity) < size)
		{
			T *_temp = new T[size];
			_current = _temp + (_vector_size);
			memcpy(_temp, _array_data, (unsigned int)((char*)_array_end - (char*)_array_start));
			_array_end = (_temp + size);
			delete [] _array_data;_array_data = _temp;return;
		}else
		{
			it = _current;
			_current = (_array_start + size);
			for(;it < _current;it++)__CONSTRUCTOR(T, it);
		}}
		else
		{
			it = _current;
			_current = (_array_start + size);
 
			if(it != _current)
			do{__DESTRUCTOR(T, it);}while(it != _current);
 
		}
	}
 
	inline void insert(unsigned int pos, const T &val)
		{if(pos >= (_vector_size))return;
		if(_current == _array_end)double_size();
 
		T *end = _array_data + pos; 
		for(T *it = _current++;it != end;)*it-- = it[-1];
		*end = val;
	}
 
	inline void insert(T * pos, const T &val){
		if(pos >= _current)return;
		unsigned int _pos = (pos - _array_start);
		if(_current == _array_end)
			{double_size();pos= _array_start + _pos;}
 
		for(T *it = _current++;it != pos;)*it-- = it[-1];
		*pos = val;
	}
 
	inline void assign(size_t size, const T &val){if(!size)return;
		if(_current != _array_start)
			for(T *it = _array_data;it < _current;it++)__DESTRUCTOR(T, it);
		if((_vector_capacity) < size)allocate(size);
		_current = _array_start + size;
 
		for(T *it = _array_start;it < _current;){*it++ = val;}
	}
 
	inline void shrink_to_fit(){if(_current == _array_end)return;
	if(_current == _array_start)return;
 
		T *_temp = new T[(_vector_size)];
			memcpy(_temp, _array_data, (unsigned int)((char*)_current - (char*)_array_start));
			_current = _temp + (_vector_size);
			delete [] _array_data;_array_data = _temp;_array_end = _current;
	}
 
	inline void reverse(int count = 0){
		size_t half_size = ((unsigned int)(_vector_size)) / 2;
		if(count && count < half_size)half_size = count;
		char temp[sizeof(T)]; //avoid constructors
		T*_end = _array_end - 1;
 
	for(int i = 0;i < half_size;i++)
		{
			*((T*)temp) = (_array_start)[i];
			(_array_start)[i] = (_end)[-i];
			(_end)[-i] = *((T*)temp);
		}
	}
 
	inline void erase(unsigned int pos){
		if(_current == _array_start || pos >= (_vector_size))return;
		__DESTRUCTOR(T, &_array_data[pos]);
 
		for(T *it = &_array_data[pos + 1];it < _current;){it[-1] = *it++;}
		_current--;
	}
 
	inline void erase(T *pos){
		if(pos >= _current)return;
		__DESTRUCTOR(T, pos);
 
		T *__current = _current--;
		for(pos++;pos < __current;){pos[-1] = *pos++;}
	}
 
	inline void erase(T *first, T *last){
		if(last >= _current)return;
 
		for(T *it = first;it < last;it++)
			{__DESTRUCTOR(T, it);}
 
		T *__current = _current;
		_current -= (last - first);
		for(;it < __current;){*first++ = *it++;}
 
	}
 
	inline void erase(unsigned int first, unsigned int last){
		unsigned int range = last - first;
		if(first >= last || (_current - range < _array_start) || last >= (_vector_size))return;
 
		T *end = &_array_data[last];
		for(T *it = &_array_data[first];it < end;it++)
			{__DESTRUCTOR(T, it);}
		range = -range;
 
		for(;it < _current;){it[range] = *it++;}
		_current += range; //it's negative
	}
 
 
	inline void swap(tVector <T> &obj){
		T *__current = _current;
		T *__array_start = _array_start;
		T *__array_end = _array_end;
		_current = obj._current;
		_array_start = obj._array_start;
		_array_end = obj._array_end;
		obj._current = __current;
		obj._array_start = __array_start;
		obj._array_end = __array_end;
	}
 
	inline void clear(bool bDestroy = false){
		if(bDestroy)for(T *it = _array_data;it < _current;it++){__DESTRUCTOR(T, it);}
	_array_end = _array_start;_current = array_data;}
 
 	inline void reset(){_current = _array_start;}
	inline size_t size(){return _vector_size;}
	inline void reserve(size_t max){if(max > (_vector_capacity))new_size(max);}
	inline T& at(unsigned int index){return _array_start[index];}
	inline bool empty(){return ((_vector_capacity) <= 0);}
	inline T* data(){return _array_start;}
	inline T* begin(){return _array_start;}
	inline T* end(){return _current;}
	inline T& front(){return *_array_start;}
	inline T& back(){return _current[-1];}
	inline size_t capacity(){return (_vector_capacity);}
	inline T& operator[] (unsigned int index){return _array_start[index];}
	inline size_t max_size(){allocator<T> obj;return obj.max_size();}
 
 
	inline void allocate(size_t size){
		delete [] _array_data;
		_array_data = new T[size];
		_current = _array_start;
		_array_end = (_array_start + size);
	}
 
    _PROTECTED :
	    T *_array_data, *_current, *_array_end;
 
		private :
 
			inline void new_size(size_t size)
	{
		T *_temp = new T[size];
			_current = _temp + (_vector_size);
			memcpy(_temp, _array_data, (unsigned int)((char*)_array_end - (char*)_array_data));
			_array_end = _temp + size;
			delete [] _array_data;_array_data = _temp;
	}
};
#undef __DESTRUCTOR
#undef __CONSTRUCTOR
#undef _array_start
#undef _vector_capacity 
#undef _vector_size 

Here is my simple test about (vector vs tVector)
http://pastebin.com/DxCRBG0n
(I tested it in release mode)

Any suggestions?

[Cubbi]

all those functions are already inline, that word is redundant.
constructors should initialize members, not assign
const member functions should be declared const
the #defines are completely uncalled for
swap would be more readable if it used std::swap
the use of new[] forces default constructible requirement
the use of memcpy() forces trivially copyable requirement, you should document those
calling the destructors directly only leads to UB when delete[] calls them again (although if your elements are trivially destructible, it's safe, just weird)
etc.. vectors aren't easy to write. (btw, you do support iterators, that's what begin() and end() return)

[MiiNiPaa]

Learn about placement new. It is best alternative to manual memcpy.
You should manually allocate memory, place elements using placement new, destroy them using manual destructor call and free memory when it isn't needed.

[o1vk4iN6]

Have to say it is hard to read. I don't really see a use for macros here either. _vector_size, _vector_capacity can just be inlined functions. Why is _vector_start a macro of _vector_data ... why not just name it _vector_start ? Some issues as well:

T *_temp = new T[size];
_current = _temp + (_vector_size);
memcpy(_temp, _array_data, (unsigned int)((char*)_array_end - (char*)_array_data));
_array_end = _temp + size;
delete [] _array_data;

Here you are only copying the binary data, by calling delete[] you are also calling the destructors for each element. So if you have something that say allocates memory in the constructor and deallocates it in the destructor, you've invalidated it.

There are some other things, using _CONSTRUCTOR, when you allocate an array of a type using new, they are already constructed with the default constructor. That is to say the same for _DESTRUCTOR.

[Kikiman]

Thanks all. Here is my more stable version : http://pastebin.com/pRefDAur

I agree, there are so many issues. The biggest problem is the operator delete[]. Recently I've applied a trick that can avoid UB when copying :

    T* _temp = (T*) new char[sizeof(T) * size]; 
    delete [] (char*) _temp;

Here is my vector test (it doesn't generate any messages) : http://pastebin.com/z8BzBi4f

And about memcpy, I still have no idea... Does it affect my vector's performance?

[Kikiman]

Now my vector is done. Here is my performance test (and my lastest vector inside) : http://pastebin.com/g24jAJSb

If you see any errors, tell me.

Here is my statistics :

Vector standard version :

----------------------------------------
vector standard version.
+ vector<int> time record :
Press any key to continue . . .
----------------------------------------
push_back() test : 0.417429 sec

pop_back() test : 0.109895 sec

insert() test : 4.98058 sec

access() test : (sum all values)
Final value = 35999960
Time : 0.00290288 sec

erase() test : 16.5717 sec
----------------------------------------
Total time = 22.0825 sec

Vector custom version :

----------------------------------------
vector custom version.
+ tVector<int> time record :
Press any key to continue . . .
----------------------------------------
push_back() test : 0.253202 sec

pop_back() test : 0.0561278 sec

insert() test : 4.99643 sec

access() test : (sum all values)
Final value = 35999960
Time : 0.00195723 sec

erase() test : 7.24342 sec
----------------------------------------
Total time = 12.5511 sec

And thanks for all the help. :)

[MiiNiPaa]

Use int64_t instead of implementation specific __int64
Still does not works with objects that are not trivially copyable.
Try move test with standard vector and yours.

[Cubbi]

There are many errors still, even basic syntax errors:

./tVector.h:30:9: error: C++ requires a type specifier for all declarations
        inline operator= (tVector<T> &object){
        ~~~~~~ ^

and

./tVector.h:205:8: error: use of undeclared identifier 'it'
                for(;it < __current;){*first++ = *it++;}
                     ^

(same for many other lines)

Also,
*it-- = it[-1];, it[n] = *it--;, and pos[-1] = *pos++; are undefined expressions

Begin by getting your program to compile with a standard C++ compiler (e.g. clang++ or gcc with -pedantic option on). If you don't have access to one, ideone.com can do it if you paste the tVector header into your test to make it a single file)

[Kikiman]

@Cubbi - Your syntax errors may be :

	inline void erase(T *first, T *last){

	for(T *it = first;it < last;it++) // Here...
		{__DESTRUCTOR(T, it);}

}

Change it to :

   inline void erase(T *first, T *last){
        T *it = first;
	for(;it < last;it++)
           {__DESTRUCTOR(T, it);}

}

I'll rebuild my whole project right now... :)

@MiiNiPaa - What is your problem? Could you expand and give me more information about it?

[MiiNiPaa]

class Wrong
{
public:
    char* s;
    Wrong(): s(nullptr) {}
    Wrong(const char* x_)
    {
        s = new char[std::strlen(x_) + 1];
        std::strcpy(s, x_);
    }
    Wrong(const Wrong& w): Wrong(w.s){}
    Wrong& operator=(const Wrong& w)
    {
        if (s)
            s[0] = '\0';
        delete[] s;
        s = new char[std::strlen(w.s) + 1];
        std::strcpy(s, w.s);
    }
    ~Wrong()
    {
        if (s)
            s[0] = '\0';
        delete[] s;
        s = nullptr;
    }
};

int main()
{

    tVector<Wrong> x;
    {
        Wrong a("Hello");
        tVector<Wrong> y;
        y.push_back(a);
        x = y;
    }
    std::cout << x[0].s;
    {
        Wrong a("Hi");
        x.assign(2, a);
        x[1].s[0] = 'S';
    }
    std::cout << x[0].s << x[1].s;
}

I had to turn off most warnings and comment everything relating to insert and erase and it still gives me a wall of warnings. Try running this. If you did everything right, it should give you "Hello"
Also I would like to see move speed comparsion for your and standard vectors.

Edit:
_PROTECTED ?
_TROW ?
What the hell are these? Clearly not standard C++. No single compiler aside you written it in will compile you code. And there is many things which should prevent compiling of this.

Edit 2: added copy constructor and assigment operator. Now it works even better.

[cire]

Begin by getting your program to compile with a standard C++ compiler (e.g. clang++ or gcc with -pedantic option on). If you don't have access to one, ideone.com can do it if you paste the tVector header into your test to make it a single file)

It doesn't compile with VC++, either.

@Kikiman: What you quoted didn't need changing. The error messages specified the line numbers/file names and the actual lines of code the errors occurred on. Why did you ignore them? What compiler are you using?

[Kikiman]

I've just upgraded my compiler. It's VS 2008, and I'm happy because it produces much faster code than VS 2005. Also I've fixed my code to make sure my code is compatible with my new compiler. Not sure about VC++ 2010 or 2012, I couldn't install them properly because my computer doesn't have enough requirements. But here is my new statistics :

Vector standard version :

----------------------------------------
vector standard version.
+ vector<int> time record :
Press any key to continue . . .
----------------------------------------
push_back() test : 0.317944 sec

pop_back() test : 0.0283232 sec

insert() test : 1.35873 sec

access() test : (sum all values)
Final value = 52050000
Time : 0.00357951 sec

erase() test : 2.4852 sec
----------------------------------------
Total time = 4.19377 sec
Press any key to continue . . .

Vector custom version :

----------------------------------------
vector custom version.
+ tVector<int> time record :
Press any key to continue . . .
----------------------------------------
push_back() test : 0.225995 sec

pop_back() test : 0.0190141 sec

insert() test : 2.93855 sec

access() test : (sum all values)
Final value = 52050000
Time : 0.000383568 sec

erase() test : 2.48342 sec
----------------------------------------
Total time = 5.66736 sec
Press any key to continue . . .

I changed my test by adding some options to ensure that it can accept structures.

Here are my new vector class & test : http://pastebin.com/t8g2Cyd1

[MiiNiPaa]

Too many time wasted on output. It is usually slow and what worse speed of output usually unconsistent: you cannot predict if output operation will take 1 ms or 1 second.

Also, where is my move test?

[Kikiman]

@MiiNipaa - Here is my "millisecond" version : http://pastebin.com/WXxKwgEp
And, I don't really understand what your "move test" means. What does "move test" mean?

Update new statistics (vector<int>) :

Vector standard version :

----------------------------------------
push_back() test : 312.345 ms

pop_back() test : 18.6823 ms

insert() test : 1332.55 ms

access() test : 2.64196 ms

erase() test : 2426.17 ms
----------------------------------------
Total time = 4092.38 ms (4.09238 sec)

Vector custom version :

----------------------------------------
push_back() test : 227.393 ms

pop_back() test : 18.7507 ms

insert() test : 1960.63 ms

access() test : 0.351162 ms

erase() test : 2431.17 ms
----------------------------------------
Total time = 4638.29 ms (4.63829 sec)

I've also fixed a critical speed problem of the functions insert()

My old version :

inline T* insert(T * pos, const T &val)
{
	if(pos >= _current)return 0;
	
	
	if(_current == _vector_end) 
	{
	   unsigned int __pos = (pos - _vector_start); // backup the old position
	   double_size();
	   pos = _vector_start + __pos; // restore & update the new position
	}


	T *it;
	for(it = _current++;it != pos;)*it-- = it[-1];
		*it = val;return it;
}

Don't know why this method is slow :(

Here is my solution (I added a specific function only for handling that case) :

inline T* insert(T * pos, const T &val)
{
	if(pos > _current)return 0;
		
	if(_current == _vector_end)
	double_size(&pos); // It's much more faster - why?

	T *it;
	for(it = _current++;it != pos;)*it-- = it[-1];
		*it = val;return it;
}

private :
inline void double_size(T** __first, T** __last = 0)
{
	T *_temp = (T*) new char[sizeof(T) * (unsigned int)(_vector_capacity) * 2];
	_current = _temp + (_vector_size);
//////////////////////////////////////////////////////////////////
	(*__first) = _temp + ((*__first) - _vector_start); //Update new positions

	if(__last != NULL)
	(*__last) = _temp + ((*__last) - _vector_start);
//////////////////////////////////////////////////////////////////
	memcpy(_temp, _vector_data, (unsigned int)((char*)_vector_end - (char*)_vector_data));
	_vector_end = _temp + (_vector_capacity) * 2;
	delete [] (char*)_vector_data;_vector_data = _temp;
}

Let's compare 2938.55 ms(old) and 1960.63 ms(new) - It's much more faster.

But it still performs slower than the standard one. Here are my latest insert() functions, could anyone figure out why they're still slow?

inline void insert(T * pos, T* first, T *last)
{
	if(pos >= _current || first >= last)return;

	_current += (last - first);
	if(_current >= _vector_end)double_size(&first, &last);

	size_t n = (last - first);

	for(T *it = _current - n - 1;it >= pos;)
		it[n] = *it--;

	T *end = pos + n;
	for(;pos != end;)*pos++ = *first++;	
}

inline void insert(T * pos, size_t n, const T &val)
{
	if(pos >= _current)return;
		
	_current += n;
	if(_current >= _vector_end)double_size(&pos);

	T *it = _current - n - 1;
	for(;it >= pos;)
		it[n] = *it--;
	for(it += n + 1;pos != it;)*pos++ = val;			
}

[MiiNiPaa]

Does my Wrong test prints out Hello as it should?

Move test is measuring speed of moving vector instead of copying it. Read about move semantic.
Also you don't have copy and assign tests either.

[LB]

Fredbill30 wrote:

All I see here are is a whole bunch of mindf*ck. I seriously lost interest when the variable and pointer names weren't all colorful.

The scary thing about what you said is that it implies that pointers are different from variables.

EDIT: No idea who reported your post :\

@Kikiman: Could you re-post your entire latest code? You can use a paste site like http://gist.github.com/ (or pastebin if you prefer advertisements).

[N36fSL3A]

That was a joke, it was supposed to imply I don't know basic C++.