Jump to content
  • Advertisement
Sign in to follow this  
Chad Smith

Code Review: First Attempt at Dynamic Array Container

This topic is 2047 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 wanted to go and try to create my own BASIC version of an std::vector, just for 100% practice of working with different parts of C++ (operating overloading, copy constructors, class templates).  This is just the beginning of it that I whipped up really fast and I know I do still have  a lot of functionality to add.

 

The main feature I implemented was bounds checking in the array.

 

Couple things:

*I'm not trying to make something that will rival std::vector

*This would NEVER be used in production code.  I'd go straight std::vector

*I can see a lot of the functionality could be implemented using more of the standard library. 

*Doesn't really use anything from C++11.  Everything must be copied, theirs no move constructor.  Only uses a copy constructor.

*inefficient.  I realize I am doing a lot of copying right now.

*I realize their are a lot of areas that could be made shorter, easier to follow, by using functions from the standard library.  Just don't know a lot about them, but may refactor implementation to take advantage of some of those.

 

Though how is it coming right in the basic form?  Anything you see that I should look to avoid?  Things that stick out to you?

 

Here is the class

DynamicArray

// Implentation of a DynamicArray
// essiently a baby to the std::vector container

#pragma once
#include <stdexcept>
// DynamicArray Supports construction with an intial size, automatic memory handling
// access to the size of the DynamicArray, indexing like a normal array, resizing as needed, and finally preform an index range check

// DynamicArray is a template class that holds pointers to the Type
template <typename Type>
class DynamicArray
{
private:
	// how many elements are currently in the array
	unsigned int size;
	// how large is the array
	// this is not how many elements, this is the capacity of the array of buffer
	unsigned int capacity;
	// internally hold the pointer to the Types of objects
	Type* objects;

public:
	// explicit constructor
	// Takes in the initial size of the dynamic array, defaults to 0
	explicit DynamicArray(unsigned int startSize = 0): size(startSize), capacity(startSize)
	{
		// dynamilly allocate enough memory for the array
		objects = new Type[capacity];
	}

	// Copy constructor, allow a deep copy
	DynamicArray(const DynamicArray& rhs) : objects(nullptr)
	{
		// calls the assignment operator and passes in the rhs
		operator=(rhs);
	}

	// Destructor deallocates all memory allocated
	~DynamicArray()
	{
		delete[] objects;
	}

	// Overload the [] operator to allow working with DynamicArrays as if they were just a "regular" array
	// Mutator overload of []
	Type& operator[] (unsigned int index)
	{
		// check to see if the index was larger than the size of the dynamic array
		if(index >= Size() )
		{
			throw std::runtime_error("Error! Index out of range!");
		}

		// return the object at that location
		return objects[index];
	}

	// Accessor overload of []
	const Type& operator[] (unsigned int index) const
	{
		if(index >= Size())
		{
			throw std::runtime_error("Error!  Index out of range!");
		}

		return objects[index];
	}

	// Copy Assignment Operator
	const DynamicArray& operator= (const DynamicArray& rhs)
	{
		// alias test
		if( this!= &rhs)
		{
			// we need to reclaim the old memory
			delete[] objects;
			size = rhs.Size();
			capacity = rhs.Capacity();

			// allocate enough memory
			objects = new Type[Capacity()];
			// copy all the objects over
			for(unsigned int i = 0; i < Size(); ++i)
			{
				objects = rhs.objects;
			}
		}

		// return a reference to itself 
		return *this;
	}

	// resizes the DynamicArray
	// Automatically creates more memory if needed
	void Resize(unsigned int newsize)
	{
		// check to see if we need to expand
		if(newSize > capacity)
		{
			// again reserve more memory for us
			Reserve(newSize * 2);
		}
		size = newSize;
	}

	// Automatically reserves memory for the objects
	// This has nothing to do with the size of the DynamicArray
	// Sets a new capacity for the DyanamicArray to use
	void Reserve(unsigned int newCapacity)
	{
		// no reason to reserve memory if the newCapacity is less than our size
		if(newCapacity < size)
		{
			return;
		}
		// before we reserve we need to save all of the old objects
		Type* oldObjects = objects;

		// how many objects do we need to copy?
		// if the newCapacity is smaller than the size then we have to copy over the capacity amount
		unsigned int numToCopy = newCapacity < size ? newCapacity : size;

		// allocate enough memory of the capacity specified
		objects = new Type[newCapacity];
		// Copy all the objects over
		for(unsigned int i = 0; i < numToCopy; i++)
		{
			objects = oldObjects;
		}

		// size of the dynamic array is how many we copied over
		size = numToCopy;
		capacity = newCapacity;

		// no longer need the memory the old objects resided at
		delete[] oldObjects;
	}

	// PushBack pushes a new object to the end of the array
	// allocates more memory if needed
	void PushBack(const Type& theObject)
	{
		// if their is no more room left
		if(size == capacity)
		{
			// make room by calling the reserve function
			// Reserves enough room by doubling the current capacity
			Reserve(2 * capacity + 1);
		}
		// add the object to the array, inreatment the size of the array afterwards
		objects[size++] = theObject;
	}

	// returns how many elements are in the DynamicArray
	inline unsigned int Size() const
	{
		return size;
	}
	// returns the capacity of the DynamicArray
	// Capacity is not always the size. 
	// This is how many elements a DynamicArray can hold before more memory gets allocated
	inline int Capacity() const
	{
		return capacity;
	}
};

Anything to look at or change before I attempt to try to add additional functionality?

 

Functionality I look to add next:

*Constructor that allows you set the default values

*C++11 Move Constructor

*Initializer list Constructor

*Pop Back-Delete the last element

*Clear-Does nothing to capacity, sets the size to 0

*At-Access the element at an index.  Also preforms bounds check.  Can't change the element

*Swap-Swap contents of another DynamicArray

*Better Exception/Error Handling-Get rid of of just throwing a std::runtime_error

*Iterators-Most the functionality you would find inside std::vector with iterators (iterator, const_iterator, begin(), end() )

 

Again, this isn't made to rival std::Vector or to be used in any production code, just some practice.  Still would like some input on how it's started.  Thanks for any comments!

 

 

Share this post


Link to post
Share on other sites
Advertisement

Looks like a good start.

 

The main thing I would start with is making some of the operations exception safe. For example, instead of deleting the existing elements first during the assignment operator, create the copy first. This way an exception during allocation won't destroy the existing object. To avoid leaking, an exception during copying the elements should deallocate this array. Similar care would need to be taken when reserving, etc.

 

Your Reserve() has the condition newCapacity < size twice, one of which is an early return. The other case can never occur.

 

I would consider using assertions instead of/in addition to exceptions for operator[].

 

Calling the assignment operator from the copy constructor is worrying. While it appears to be correct at the moment, you aren't initialising all the members in the copy constructor, so some alternative implementations could cause bugs. One consideration is the common idiom of implementing a swap() function (which you are considering doing anyway), and implementing the assignment operator in terms of a copy and a swap:

 
DynamicArray &operator=(DynamicArray copy) {
    Swap(*this, copy);
    return *this;
}

This implementation can achieve the same exception safety as I described in the first paragraph, provided care is taken in the copy constructor not to leak memory.

 

Another thing to consider would be not requiring that elements between the size and capacity are initialised. For heavier objects combined with doubling the capacity, you can end up initialising quite a number of elements that may never be accessed. If the object's constructor/destructor do things such as count the number of live objects, the client code might experience unexpected results.

 

If you haven't already, consider writing a suite of tests. In particular, try to test some of the edge cases mentioned, such as an element type with a constructor/copy constructor that throws, or constantly inserting until there is a std::bad_alloc, ensuring that the original object is intact after such circumstances.

Share this post


Link to post
Share on other sites

You might want to restrict your resizing to a more sensible values above a certain value as doubling your size when you are only adding 25 new elements on a 4096 element array will add a lot of new memory. STL only grows by about 50% of the previous size each time it needs to grow and if that is still less then the requested size it only grows to the new size and nothing more.

Share this post


Link to post
Share on other sites

The main thing I would start with is making some of the operations exception safe. For example, instead of deleting the existing elements first during the assignment operator, create the copy first. This way an exception during allocation won't destroy the existing object. To avoid leaking, an exception during copying the elements should deallocate this array. Similar care would need to be taken when reserving, etc.

Noted.  I'll add that to things to add and fix.

 

 

Your Reserve() has the condition newCapacity < size twice, one of which is an early return. The other case can never occur.

Well don't I feel dumb.  lol.  the first condition that does the early return was a late addition after thinking that a reserve in a vector doesn't have to reserve it's memory.  Fixed.

 

I would consider using assertions instead of/in addition to exceptions for operator[].


And why I do I seem to always forget about assertions?  lol.  Will do.  I did plan to try to get away from just throwing that std::runtime_error as fast as I could.

Calling the assignment operator from the copy constructor is worrying. While it appears to be correct at the moment, you aren't initialising all the members in the copy constructor, so some alternative implementations could cause bugs. One consideration is the common idiom of implementing a swap() function (which you are considering doing anyway), and implementing the assignment operator in terms of a copy and a swap:

That seems like a very good idea.  Thanks.  Had a feeling a swap would come in more use than I originally thought.

 

 

Another thing to consider would be not requiring that elements between the size and capacity are initialised. For heavier objects combined with doubling the capacity, you can end up initialising quite a number of elements that may never be accessed. If the object's constructor/destructor do things such as count the number of live objects, the client code might experience unexpected results.

yea, I did plan to refactor this part.  I had a feeling just doubling the capacity every time wouldn't be the best idea.  I'll take note on what both you and NightCreature said.

 

Thanks both to you and NightCreature for the comments!  Just trying to make sure I have the correct idea on some of the basic containers so that way I have a better what's actually going on in the container I choose.  Hopefully it'd allow to better choose and understand what container I need for a specific task.

 I'll do some quick reading on some things and see what I can come come up with.  When I get done adding most of the functionality that I want I'll post it back here.  Thanks!

Edited by Chad Smith

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!