Custom Dynamic Array Class and Allocator

[N36fSL3A]

Alright, so I attempted to create a dynamic array class for use in my engine (due to problems regarding a dll-interface with the standard library), so I tried at making a standard-compatible allocator template class first. After I "finished" that, I went on to work on the dynamic array class itself.

So I finish the dynamic array class, and test it with the standard allocator. It works perfectly, but when I test it with my custom allocator class, it fails terribly.

To make sure it wasn't my DynamicArray class that was causing issues, I tried using the custom allocator on the std::vector class template, and it didn't work either. I have no idea what I'm doing wrong.

My DynamicArray class code:

// Represents a dynamic array, similar to the standard library's "vector" class.
template<typename T, typename A>
class DynamicArray
{
	public:
		DynamicArray() :
		data(nullptr),
		elements(0),
		capacity(0)
		{
			
		}

		void Push(const T &val)
		{
			if(elements + 1 < capacity)
			{
				data[elements] = val;
				elements++;
			}

			else
			{
				// Get more memory
				Reserve(capacity + 1);
				
				// Call the function again
				Push(val);
			}
		}

		void Pop()
		{
			// Call the destructor on the last element
			allocator.destroy(&data[elements - 1]);
			MemorySet(&data[elements - 1], 0, sizeof(T));
			elements--;
		}

		T &operator[](size_t i)
		{
			// Check if the dynamic array is out of range.
			Debug::CheckAssertion(!(i < 0 || i >= elements), "Index is out of dynamic array range.");

			return data[i];
		}

		void Reserve(size_t size)
		{
			// Only change if the capacity is less
			if(capacity < size)
			{
				T* newData = nullptr;

				newData = allocator.allocate(size);

				Debug::CheckAssertion((newData != nullptr), "Failed to allocate memory for dynamic array reservation.");

				// Zero out memory
				MemorySet(newData, 0, capacity * sizeof(T));

				// Copy previous memory over
				if(data != nullptr)
					MemoryCopy(newData, data, elements * sizeof(T));

				allocator.deallocate(data, capacity);

				data = newData;
				capacity = size;
			}
		}

		void Resize(size_t size, const T &val = T())
		{
			size_t newElements = size;
			size_t newCapacity = size;

			T* newData = nullptr;

			newData = allocator.allocate(size);

			Debug::CheckAssertion((newData != nullptr), "Failed to allocate memory for dynamic array resize.");

			MemoryCopy(newData, data, newElements);
			
			if(newCapacity > capacity)
			{
				for(size_t i = 0; i < (newCapacity - capacity); i++)
				{
					allocator.construct(data[(newElements) + i], val);
				}
			}
		}

		void Clear()
		{
			for(size_t i = 0; i < capacity; i++)
			{
				allocator.deallocate(&data[i]);
			}

			elements = 0;
		}

		T* GetData()         const{return data;}
		size_t GetSize()     const{return elements;}
		size_t GetCapacity() const{return capacity;}

		inline bool IsEmpty() const{return (elements == 0);}

	private:
		T*     data;
		size_t elements;
		size_t capacity;

		A allocator;
};

Custom allocator:

template<typename T>
class Allocator
{
	public:
		typedef T         value_type;
		typedef T*        pointer;
		typedef T&        reference;
		typedef const T*  const_pointer;
		typedef const T&  const_reference;
		typedef size_t    size_type;
		typedef ptrdiff_t difference_type;

		template <typename U>
		struct rebind
		{
			typedef Allocator<U> other;
		};

		pointer address(reference x) const
		{
			return &x;
		}

		const_pointer address(const_reference x) const
		{
			return &x;
		}

		pointer allocate(size_type n, Allocator<void>::const_pointer hint = 0)
		{
			return Request<value_type>(n);
		}

		void deallocate(pointer p, size_type n)
		{
			Free(p);
		}

		// Get the maximum amount of elements that can be allocated.
		size_type max_size() const
		{
			return (GetBlockSize()/sizeof(value_type));
		}

		void construct(pointer p, const_reference val)
		{
			::new (reinterpret_cast<void*>(p)) value_type(val);
		}

		void destroy(pointer p)
		{
			p->~T();
		}

	private:
};

// Specialization for void pointer
template<>
class Allocator<void>
{
public:
	typedef void* pointer;
	typedef const void* const_pointer;
	typedef void value_type;
	template<class U>
	struct rebind {typedef Allocator<U> other;};
};

The "Request" and "Free" functions are my engine's equivalent of malloc and free (or new and delete). I allocate a large buffer (16 mb), and through those functions I distribute the memory to where it's needed.

[N36fSL3A]

Bump.

[ne555]

> it fails terribly.
http://www.cplusplus.com/forum/articles/40071/#msg218019
also, provide enough code to reproduce your problem.

		void Clear()
		{
			for(size_t i = 0; i < capacity; i++)
			{
				allocator.deallocate(&data[i]); //leak, you forgot to destroy()
			}

			elements = 0;
		}

[N36fSL3A]

I could have swore that I wrote that it gives garbage values when I push_back on a normal std::vector, and with my DynamicArray class it makes the previous elements 0.

[ne555]

provide enough code to reproduce your problem.

allocator.deallocate(&data[i]); //passing one parameter
void deallocate(pointer p, size_type n) //requesting two parameters 

so your code couldn't even compile

[N36fSL3A]

int main()
{
	DynamicArray<int, Memory::Allocator<int>> dyn;

	dyn.Push(5780);
	dyn.Push(209);
	dyn.Push(100);

	std::cout << dyn[0] << "\n";
	std::cout << dyn[1] << "\n";
	std::cout << dyn[2] << "\n";

	std::cout << "Popping" << "\n";
	dyn.Pop();

	std::cout << dyn[0] << "\n";
	std::cout << dyn[1] << "\n";

	return 0;
}

Output:

0
0
100
Popping
0
0

allocator.deallocate(&data[i]); //passing one parameter
void deallocate(pointer p, size_type n) //requesting two parameters 

so your code couldn't even compile

It did; not sure how though.

EDIT: Oh, I changed it when I realized it wouldn't compile in my actual source code, so that's why it compiled. Forgot to change it here.

[N36fSL3A]

Bump.

[cire]

Just from a cursory inspection:

Push should result in copy construction, not copy assignment.

Pop should have, at the least, an assertion that the container is not empty.

Reserve should result in element-wise copy constructions, not bit-wise copying (as I would presume MemoryCopy does, and if it does it has no place anywhere in your implementation.) Reserve should also result in the destruction of elements previously stored when an actual reallocation is required.

In Clear deallocate should not be called, but elements should be destructed.

operator[] should have a const and non-const version. So should GetData.

As for what is causing your problem, it is hard to say. You still haven't supplied enough code to reproduce your issue.

[N36fSL3A]

Thanks cire.

I've also figured out the problem, it was due to my engine's internal memory distributor (bug in there).

[CodeGazer]

You forgot to declare a destructor, copy constructor and assignment operator. Generally when you need one of them (Which you do because you have internal pointers) you need them all.

Without these I am pretty sure you are going to run into problems and you are going to have memory leaks.