Sign in to follow this  
Raeldor

Dynamic Array Template Class... Removing Members

Recommended Posts

Hi All, Having an issue with my DynamicArray template class. The remove used to be...
		inline void Remove(int in_index) {for (int i=in_index; i < m_count-1; i++) m_array[i]=m_array[i+1]; m_count--;}

but then I realized that for objects, some destructors were not getting called when the item was removed because there was always an old item left hanging at the end of the list. I then went to...
		inline void Remove(int in_index)
		{
			T* newArray=new T[m_arraySize];

			// copy members
			int newIndex=0;
			for (int i=0; i < m_count; i++)
			{
				if (i != in_index)
					newArray[newIndex++]=m_array[i];
			}

			// delete old array and replace
			delete [] m_array;
			m_array=newArray;
		}

Which seems to work, but looks grossly inefficient. Can someone suggest a better implementation considering the object in the array could be an object or a value type? Thanks Rael

Share this post


Link to post
Share on other sites
I'm not 100% sure, but I think that in the same situation std::vector explicitly calls the destructor of the last element. Of course, that does not free the memory or resizes the buffer at all, so(again, I *think*) when inserting a new element it uses placement new kinda like this(when it doesn't need to allocate a bigger chunck of memory of course):

void push_back(const T& element)
{
T* ptr=&m_array[m_count-1];
new(ptr)T(element)
}

Again, I'm not 100% sure about all of this. Maybe someone else can verify or correct me.

Share this post


Link to post
Share on other sites
Just out of curiosity, why are you (essentially) re-writing std::vector<>? It seems you're expending quite a bit of effort trying to solve a problem for which a solution already exists. Just a thought...

Share this post


Link to post
Share on other sites
The object itself can be "destroyed" by directly calling it's destructor - however, this will only clean up so much, it will not free up the associated memory. Further, it dosn't play well at all with new[] / delete[]. You'll end up destroying the last object twice, which is just downright wrong.

To do this right, you need to use a memory allocation scheme that dosn't actually construct the object, manage that seperately, and then manually manage your object lifespans using placement new and direct destructor calls.

In other words, you need to reimplement std::vector.

Or you could just use std::vector.

(I just use std::vector.)

(you should too.)

@mikeman: That looks about right, although you're missing a ++m_count, the check for having available memory, and the reallocating the buffer if there isn't.

Share this post


Link to post
Share on other sites
Quote:
Original post by mikeman
I'm not 100% sure, but I think that in the same situation std::vector explicitly calls the destructor of the last element. Of course, that does not free the memory or resizes the buffer at all, so(again, I *think*) when inserting a new element it uses placement new kinda like this(when it doesn't need to allocate a bigger chunck of memory of course):

void push_back(const T& element)
{
T* ptr=&m_array[m_count-1];
new(ptr)T(element)
}

Again, I'm not 100% sure about all of this. Maybe someone else can verify or correct me.

What is...

new(ptr)T(element)

? This form of C++ code is not familiar to me. What does this do?

Also in regards to other questions, the reason I am re-writing is for a learning exercise.

Thanks!
Rael


Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
Quote:
Original post by mikeman
I'm not 100% sure, but I think that in the same situation std::vector explicitly calls the destructor of the last element. Of course, that does not free the memory or resizes the buffer at all, so(again, I *think*) when inserting a new element it uses placement new kinda like this(when it doesn't need to allocate a bigger chunck of memory of course):

void push_back(const T& element)
{
T* ptr=&m_array[m_count-1];
new(ptr)T(element)
}

Again, I'm not 100% sure about all of this. Maybe someone else can verify or correct me.

What is...

new(ptr)T(element)

? This form of C++ code is not familiar to me. What does this do?

Also in regards to other questions, the reason I am re-writing is for a learning exercise.

Thanks!
Rael


As mentioned above, look up "placement new". Basically, it constructs an object(that is, invokes the constructor/copy constructor) but does not allocate new memory for it, instead it places it at a specified(valid,of course) location that you supply(the "ptr").

[Edited by - mikeman on November 6, 2006 10:09:40 AM]

Share this post


Link to post
Share on other sites

// Typesafe - leaves back objects 'alive' - will be okay on delete[]
// and uses assignment operator

void SomeArrayClass::Remove(int nIndex,int nCount) throw()
{
if (nIndex < m_Count)
{
const int nCheck = nIndex + nCount;

if (nCheck >= m_Count)
{
m_Count = nIndex;
}
else
{
for (int x = nIndex,y = nCheck; y < m_Count; ++x,++y)
{
m_ArrayData[x] = m_ArrayData[y];
}

m_Count -= nCount;
}
}
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this