Hi,

I made a very simple container class because I need a vector where I can remove elements in the middle without changing the position of the other elements but I am worried that it doesn't free up everything when I delete it. Here is the code:

template <typename T>
class Vector
{
private:
	T* elements;
	int elementCount;
	int elementCapacity;
	int freeElement; // first free element
	int* freeElementList; // each array element is the index of the next free element
public:
	Vector(int initialCapacity) {
		elementCount = 0;
		elementCapacity = initialCapacity;
		elements = (T*)malloc(elementCapacity * sizeof(T));

		freeElement = 0;
		freeElementList = (int*)malloc(elementCapacity * sizeof(int));
		for (int i = 0; i < elementCapacity; ++i)
			freeElementList[i] = i + 1;
	}

	~Vector() {
		free(freeElementList);
		free(elements);
	}

	int addElement(T& element) {
		if (elementCount == elementCapacity) {
			elementCapacity *= 2;

			int* oldFreeElementList = freeElementList;
			freeElementList = (int*)malloc(elementCapacity * sizeof(int));
			memcpy(freeElementList, oldFreeElementList, elementCount * sizeof(int));
			free(oldFreeElementList);
			for (int i = elementCount; i < elementCapacity; ++i)
				freeElementList[i] = i + 1;

			T* oldElements = elements;
			elements = (T*)malloc(elementCapacity * sizeof(T));
			memcpy(elements, oldElements, elementCount * sizeof(T));
			free(oldElements);
		}
		elements[freeElement] = element;

		int result = freeElement;
		freeElement = freeElementList[freeElement];
		elementCount++;

		return result;
	}

	void removeElement(int index) {
		freeElementList[index] = freeElement;
		freeElement = index;
		elementCount--;
	}

	T getElement(int index) {
		return elements[index];
	}

};

For example if I use it to store STL vectors will the destructor actually delete all their elements?

EDIT: sorry, I forgot to set the right title. It was supposed to be something like "C++ custom container"

Ok, I changed the class to use new/delete instead of malloc/free and I am calling the destructors manually. However, I don't know if I still have to call the constructors manually. I think right now the line "elements[freeElement] = element;" uses the copy constructor to construct the elements, or not?

template <typename T>
class Vector
{
private:
	T* elements;
	int elementCount;
	int elementCapacity;
	int freeElement; // first free element
	int* freeElementList; // each array element is the index of the next free element
	bool* isUsed;
public:
	Vector(int initialCapacity) {
		elementCount = 0;
		elementCapacity = initialCapacity;
		elements = new T [elementCapacity];

		freeElement = 0;
		freeElementList = new int [elementCapacity];
		isUsed = new bool [elementCapacity];
		for (int i = 0; i < elementCapacity; ++i) {
			freeElementList[i] = i + 1;
			isUsed[i] = false;
		}
	}

	~Vector() {
		for (int i = 0; i < elementCapacity; ++i) {
			if (isUsed[i])
				elements[i].~T();
		}

		delete [] freeElementList;
		delete [] elements;
		delete [] isUsed;
	}

	int addElement(T& element) {
		if (elementCount == elementCapacity) {
			elementCapacity *= 2;

			int* oldFreeElementList = freeElementList;
			freeElementList = new int [elementCapacity];
			memcpy(freeElementList, oldFreeElementList, elementCount * sizeof(int));
			delete [] oldFreeElementList;

			bool* oldIsUsed = isUsed;
			isUsed = new bool [elementCapacity];
			memcpy(isUsed, oldIsUsed, elementCount * sizeof(bool));
			delete [] oldIsUsed;

			for (int i = elementCount; i < elementCapacity; ++i) {
				freeElementList[i] = i + 1;
				isUsed[i] = false;
			}

			T* oldElements = elements;
			elements = new T [elementCapacity];
			memcpy(elements, oldElements, elementCount * sizeof(T));
			delete [] oldElements;
		}
		elements[freeElement] = element;
		isUsed[freeElement] = true;

		int result = freeElement;
		freeElement = freeElementList[freeElement];
		elementCount++;

		return result;
	}

	void removeElement(int index) {
		elements[index].~T();
		freeElementList[index] = freeElement;
		freeElement = index;
		elementCount--;
	}

	T getElement(int index) {
		return elements[index];
	}

};

About the rule of three: If I don't plan to copy instances of the class do I still need it?

Even better would be to use smart pointers.

C++11 already contains an unique_ptr<> class in the standard library. When you use this unique pointer, it will automatically delete the object it's pointing too. This way, you don't need to worry very much like this about deallocating etc. The overhead is also usually insignificant. An example:

#include <memory>
#include "your_super_awesome_header.hpp"

int main()
{
    {
        auto smart_pointer = std::unique_ptr<your_super_awesome_class>(new your_super_awesome_class());
    } // The allocated object gets deleted here and its destructor will be called automatically.
}

Also, you should try to use initalization lists where possible.

Besides that, maybe it's a better idea to pass a pointer to Vector::addElement() so that you avoid copying overhead by just taking ownership, or create a function for rvalue references too. Why are you actually creating a custom vector class? If you would use the standard one you would not have to deal with things like this.
I assume you are keeping pointers to the elements of your container, so you need them to be on a fixed position so you won't have invalid pointers? If that's the case, you could just save the pointer type, or even better, a smart pointer (unique or shared). And if this isn't an option for some reason, you could always use a std::deque or std::list, or another container like them. These keep the objects on the same place, but not all in a continous array like a vector does. This will involve minor overhead, but your vector class is written in a way which will use a lot of memory, which is in most cases a bigger problem.

Edit: replying to your latest post.

The rule of three is pretty (or very very) important. People expect your class to be able to copy itself without problems when a copy constructor exists. If they do that now, memory leaks will occur. In C++ this rule could also be replaced with the rule of five, you should look it up. Moving the vector would not have major overhead and could be used some time...

And the line "elements[freeElement] = element;" uses the assignment constructor, not the copy constructor. Usually they do the same for as far as I know.

You don't have to call the constructor manually. The object will be constructed one way or the other if you are creating it on the stack (except if you're writing some dirt code ). If you're allocating on the heap you're constructing a new object (and thereby calling it's constructor) by using new().

void add( const T& obj ) {
	/* 1: */ {
		T* arr = new T[5]; // default-constructs 5 Ts
		t[2] = obj; // copy-assigns obj into the 3rd T in arr
		delete[] arr; // destructs 5 Ts
	}

	/* 2: */ {
		// Allocate enough space for 5 Ts (disregarding alignment, for brevity)
		unsigned char* memory = new unsigned char[sizeof(T)*5]; // (interchangeable with malloc)

		// This is invalid, because the 3rd T in memory isn't a valid T!
		// ((T*)memory)[2] = obj;
		
		// Copy-construct obj into the space where the 3rd T in the array would be
		T* ptr = new (memory+sizeof(T)*2) T(obj);
		ptr->~T();

		// Free the underlying memory without any regard to objects living in it
		delete[] memory; // (interchangeable with free)
	}
}

How does getElement know that index is a valid item?

How are you going to implement iterating through the entire vector?

index++ should point to the next valid item after index (index itself should also be guaranteed to be a valid item to begin with). index + 2 should be the second valid item after index, etc.

The container size should represent the number of valid items in the vector, and they should appear contiguous from outside the vector, even if internally they are not.

I guess the real question is, why do you need a vector that allows removal of elements without shifting the rest of the elements around? The two largest benefits of vectors are random access to its items and truly contiguous arrangement of those items in memory. IE, fast access to any item in the vector and fast, cache friendly access to all items in the vector. You appear to be defeating both those benefits, to some degree, thus the question as to why you need a vector to begin with.

... because I need a vector where I can remove elements in the middle without changing the position of the other elements

#include <vector>
#include <algorithm>

void test() {
    using namespace std;
    vector<Foobar> v(10);

    // erase the 6th Foobar
    swap(v[5], v.back());
    v.pop_back();
}

I thought about it a bit more and I think I can actually do what I want with a map or a list. Initially it was important that the position of the elements remained the same because I uploaded the whole thing into an opengl vertex buffer. I wanted to be able to delete vertices in the middle, but if I used the swap-back method the index buffer wouldn't be correct anymore.

However in my new render class I am using a huge container with all the vertex data of my world and in every frame I assemble a vertex buffer and an index buffer using only the elements of the container that I want to render.(which I will later do with some sort of spatial partitioning) So now only that assembled vertex buffer needs to be in contiguous space and for that I can use a normal STL vector.(since I don't have to delete anything)

I will be thinking about what the most optimal container for the vertex pool is.

How does getElement know that index is a valid item?

How are you going to implement iterating through the entire vector?

In my use case I wouldn't have to iterate over the vector except to delete it. And the classes that would use the vector would keep track of all the elements they added and only use getElement for those elements.

Even though I probably wont use the class anymore, did I get it right now?

template <typename T>
class Vector
{
private:
	unsigned char* elements;
	int elementCount;
	int elementCapacity;
	int freeElement; // first free element
	int* freeElementList; // each array element is the index of the next free element
	bool* isUsed;
public:
	Vector(int initialCapacity) {
		elementCount = 0;
		elementCapacity = initialCapacity;
		elements = new unsigned char[elementCapacity * sizeof(T)];

		freeElement = 0;
		freeElementList = new int[elementCapacity];
		isUsed = new bool[elementCapacity];
		for (int i = 0; i < elementCapacity; ++i) {
			freeElementList[i] = i + 1;
			isUsed[i] = false;
		}
	}

	~Vector() {
		for (int i = 0; i < elementCapacity; ++i) {
			if (isUsed[i])
				((T*)(elements + i * sizeof(T)))->~T();
		}

		delete [] freeElementList;
		delete [] elements;
		delete [] isUsed;
	}

	int addElement(const T& element) {
		if (elementCount == elementCapacity) {
			elementCapacity *= 2;

			int* oldFreeElementList = freeElementList;
			freeElementList = new int[elementCapacity];
			memcpy(freeElementList, oldFreeElementList, elementCount * sizeof(int));
			delete [] oldFreeElementList;

			bool* oldIsUsed = isUsed;
			isUsed = new bool[elementCapacity];
			memcpy(isUsed, oldIsUsed, elementCount * sizeof(bool));
			delete [] oldIsUsed;

			for (int i = elementCount; i < elementCapacity; ++i) {
				freeElementList[i] = i + 1;
				isUsed[i] = false;
			}

			unsigned char* oldElements = elements;
			elements = new unsigned char[elementCapacity * sizeof(T)];
			for (int i = 0; i < elementCount; ++i) {
				if (isUsed[i])
					new (elements + i * sizeof(T)) T(*((T*)(oldElements + i * sizeof(T))));
			}
			delete [] oldElements;
		}
		new (elements + freeElement * sizeof(T)) T(element);

		isUsed[freeElement] = true;

		int result = freeElement;
		freeElement = freeElementList[freeElement];
		elementCount++;

		return result;
	}

	void removeElement(int index) {
		if (isUsed[index]) {
			((T*)(elements + index * sizeof(T)))->~T();
			freeElementList[index] = freeElement;
			freeElement = index;
			elementCount--;
		}
	}

	T getElement(int index) {
		return *((T*)(elements + index * sizeof(T)));
	}
};

You mentioned that you load everything into a vertex buffer. Are you loading non-trivial objects that has to ensure proper constructor and destructor calls into vertex buffers, or are you just over-engineering a container of primitive types?

In any case, I've got some general comments on your memory management itself. May or may not be relevant to your particular case considering my question above.

1. Make elements a T * instead of unsigned char *. Saves you all that pointer casting and sizeof-calls in your pointer arithmetics.
2. Allocate the memory directly with the operator new() function instead of going through the new [] operator. Then you also have to release the memory with the operator delete() function instead of using the delete [] operator. Thus: elements = operator new(elementCapacity*sizeof(T)) and operator delete(elements).
3. Don't relocate objects with the C memory functions. You need to properly copy construct and release objects, or move the objects with the move constructor if you want to take advantage of the move-mechanics in C++11. For trivial objects, this is equivalent as a memory move, but for objects with side effects when constructing/destructing/moving objects, this is highly important to get right. Also ensure that you don't assign to the new memory; you must construct the object in the new memory since otherwise you'll assign something to an non-constructed object.

Point 1 and 2 are about allocating the raw memory buffer. Point 3 is about how you manage objects manually in your own memory buffers and can be really tricky to get right if you don't understand object life times and if, how and when objects are constructed or nor.

You mentioned that you load everything into a vertex buffer. Are you loading non-trivial objects that has to ensure proper constructor and destructor calls into vertex buffers, or are you just over-engineering a container of primitive types?

I never actually used this class for vertex buffers but initially I started managing memory like this because I needed to upload stuff into the vertex buffer. I later thought it was neat and made it into a class without realizing that it wouldn't work correctly if used with non-trivial objects. To fix that I started this post but it's probably more trouble than it's worth.

Make elements a T * instead of unsigned char *. Saves you all that pointer casting and sizeof-calls in your pointer arithmetics.

I did that at first, but I adjusted my code according to fastcall22's second response using placement new.

Don't relocate objects with the C memory functions. You need to properly copy construct and release objects, or move the objects with the move constructor if you want to take advantage of the move-mechanics in C++11. For trivial objects, this is equivalent as a memory move, but for objects with side effects when constructing/destructing/moving objects, this is highly important to get right. Also ensure that you don't assign to the new memory; you must construct the object in the new memory since otherwise you'll assign something to an non-constructed object.

I think I am currently not relocating objects with C memory functions. I use placement new to copy construct the old objects. But I just noticed that I forgot to call the destructors of the released objects when relocating.

It turns out that I don't need this class. If anything I will make a version only for trivial objects. But I learned plenty about placement new, smart pointers, initialization lists and the rule of three/five, so thanks! I appreciate all the responses.