Public Group

# Code Review: First Attempt at Dynamic Array Container

This topic is 1874 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites

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 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 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

• 16
• 11
• 9
• 49
• 12
• ### Forum Statistics

• Total Topics
631392
• Total Posts
2999738
×