Jump to content
  • Advertisement
Sign in to follow this  
noteventime

Dynamic array class

This topic is 4677 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, I'm not very good at this kind of things so I figured I'd do one myself. I guess these are pretty bad algorithms (if you even can call them algorithms). If someone has the time maybe he/she/it could explain some better algorithms and why they are faster :D. Thanks a ton in advance.
template<class T>
class CDynArray
{
public:
	CDynArray(void);
	~CDynArray(void);

private:
	T* data;
	int size;

public:
	T GetAt(int at)
	{
		if(at<size && at>=0)
		{
			return data[at];
		}
		else
		{
			return -1;
		}
	}
	int InsertAt(int at, T toadd)
	{
		T* temp = new T[size];
		memcpy(temp, data, sizeof(data));
		
		size++;
		delete [] data;

		data = new T[size];

		memcpy(data[0], temp[0], sizeof(T)*at);

		data[at] = toadd;

		memcpy(data[at+1], temp[at], sizeof(T)*(size-at));
		return size;
	}
	int SetAt(int at, T data)
	{
		if(at<size && at>=0)
		{
			data[at] = data;
			return 0;
		}
		else
		{
			return -1;
		}
	}
	int Append(T toadd)
	{
		T* temp = new T[size];
		memcpy(temp, data, sizeof(data));
		
		size++;
		delete [] data;

		data = new T[size];

		memcpy(data, temp, sizeof(temp));

		data[size-1] = toadd;

		delete [] temp;

		return size;
	}
	int Clear(void)
	{
		int old;
		old = size;
		for(int i = 0; i < size; i++)
		{
			data = 0;
		}
		delete [] data;
		data = new T[0];
		size = 0;
		return old;
	}
};

Share this post


Link to post
Share on other sites
Advertisement
One word: std::vector.
Seriously, there is no point in implementing these yourself besides eductional purposes.

Cheers,
Pat.

PS: Use [ source ] [ /source ] tags (without the spaces).

Share this post


Link to post
Share on other sites
I'm assuming you're doing this to educate yourself. Else you'd be using std::vector.


T* data;
int size;


You probably want to keep a "physical size" and a "logical size" so you don't have to re-allocate every time you add or subtract something.


T GetAt(int at)
...
return -1;


This will only work for numerical types of T; it won't work for structs, classes, or even plain pointers. Instead, I would throw an error on a bad index, or possibly just abort() so you can debug the bug.


int InsertAt(int at, T toadd)
...
memcpy(temp, data, sizeof(data));


Two problems:
1) you're copying more data around than necessary, as you can assemble the array using [0..at), the new element, and [at..end).
2) This won't work for types with constructors or destructors.


int Clear(void)
...
data = 0;


You don't need to clear anything before deleting it. If you want to clean out old data, try overloading operator delete to do it in debug mode (although on some platforms, it already does that -- check yours!).

Share this post


Link to post
Share on other sites
Okay, a couple of suggestions..
Quote:
T GetAt(int at)
Consider providing access without bounds-checking and/or raw pointer access and a matching GetSize function to avoid unnecessary overhead. Also, consider crashing the application as loudly as possible instead of silently returning -1, look into exceptions and assertions.
Quote:
int Append(T toadd)
Copying and reallocating the entire vector for every insertion is going to be pretty inefficient. A common way around this problem is to allocate extra buffer space when growing the vector (often used with logarithmic growing, i.e. doubling the vector's size everytime the limit is exceeded).
For POD types (the one's that are safe to memcpy) you may also be able to improve performance by using realloc instead of separate new/deletes.
If you want to handle arbitrary classes and logaritmic growth then you'll have to use placement new (and beware of exception safety issues).
Quote:
int Clear(void)
There's little point in resetting the elements of the vector, and conversions to zero may not even be supported depending on the template type. Many debug memory managers (such as the one in VC) fills deallocated memory with a special pattern when it's freed anyway.

Quote:
Original post by darookie
One word: std::vector.
Seriously, there is no point in implementing these yourself besides eductional purposes.
That is a pretty important reason for doing it though. Implementing an efficient and generic vector will teach you a lot useful things about C++.

Also, a useful algorithm for removing items from the middle of the vector is to simply overwrite the item to be removed with the last one and shrink the vector.

edit: Too late..

Share this post


Link to post
Share on other sites
In addidtion to what was already said, I provide a commented improved version:

template<class T>
class CDynArray
{
public:
// void parameters are not necessary in C++
CDynArray( ) : data( 0 ), size( 0 ) { }
~CDynArray( ) { Clear( ); }

// provide typetraits for convenience
typedef T ValueType;
typedef T & Reference;
typedef T const & ConstReference;

private:

T * data;
// using an unsigned size type will save you from checking invalid
// indices that are below zero.
size_t size;

public:
// return references instead of values to
// a) provide a way to manipulate the content directly
// b) avoid potentially expensive copy operations for complex value types
Reference GetAt(size_t at)
{
if(at<size)
{
return data[at];
}
else
{
// since T might not be convertible to an integral type
// and data might contain -1, you better throw an
// exception.
throw std::invalid_argument();
}
}
// provide a read-only accessor as well to enable compiler optimisations
ConstReference GetAt(size_t at) const
{
if(at<size)
{
return data[at];
}
else
{
// since T might not be convertible to an integral type
// and data might contain -1, you better throw an
// exception.
throw std::invalid_argument();
}
}
// I think you forgot this :)
size_t GetSize( ) const
{
return size;
}
// You forgot this one as well :)
bool IsEmpty( ) const
{
return size == 0;
}

// use a const reference for the parameter for reasons given above (see GetAt())
size_t InsertAt(size_t at, T const & toadd)
{
// I _ASSUME_ that "at" must be a valid index
if ( at > size )
throw std::invalid_argument();
// allocate temporary storage.
T* temp = new T[size + 1];
// use the STL
std::copy(data, data + at, temp);
std::copy(data + at, data + size, temp + at + 1);

++size;
delete [] data;
// you already allocated the new data array, jut re-assign the pointer
data = temp;

data[at] = toadd;

return size;
}
// this method has been superseded by GetAt()
// int SetAt(int at, T data)
// {
// if(at<size && at>=0)
// {
// data[at] = data;
// return 0;
// }
// else
// {
// return -1;
// }
// }
// again, use a const reference argument
size_t Append(T const & toadd)
{
// allocate memory and copy
T * temp = new T[size + 1];
std::copy(data, data + size, temp);
++size;
// delete the old data
delete [] data;
// just re-assign the pointer
data = temp;
data[size-1] = toadd;

return size;
}
// again, no "void" parameters
size_t Clear( )
{
size_t old = size;
// this will call the destructors and deleting a null pointer is valid
delete [] data;
// don't allocate memory if you don't have to
data = 0;
size = 0;
return old;
}
};



HTH,
Pat.

Share this post


Link to post
Share on other sites
If you want to educate yourself, consider reading an existing std::vector implementation and asking questions about it if you don't understand something. :) (Be warned; gcc's implementation at least uses some really nasty variable names. Part of the challenge is figuring out the words that the single letters stand for ;) )

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!