Dynamic Array Template Class... Removing Members

Started by
6 comments, last by RPG_Programmer 17 years, 5 months ago
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=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;
			}

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


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]
Quote:Original post by Raeldor
What is...

new(ptr)T(element)

?


Placement new. I said it, he said it, google will tell you about it!
// Typesafe - leaves back objects 'alive' - will be okay on delete[]// and uses assignment operatorvoid 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;        }    }}

This topic is closed to new replies.

Advertisement