Dynamic Array Implementation in C++

Question

I've finished implementing a dynamic array in C++. I'm a beginner in C++ and also in algorithms and data structures, so any constructive feedback about improving the implementation would be greatly appreciated.

#include <iostream>
using namespace std;
#define INITIAL_CAPACITY 5
template <class T>
class dynamic_array {
 T *array;
 int MIN_CAPACITY = INITIAL_CAPACITY;
 int GROWTH_FACTOR = 2;
 int size;
public:
 // constructor init
 dynamic_array() {
 array = new T[MIN_CAPACITY];
 size = 0;
 }
 // append @ the end
 void append(T element) {
 if(size == MIN_CAPACITY) {
 resize();
 }
 array[size] = element;
 size++;
 }
 void deleteAt(int pos) {
 if((pos > size) || (pos < 0)) {
 cout << "Invalid index";
 return;
 }
 for(int i = pos; i <= size; i++) {
 array[i] = array[i+1];
 }
 size--;
 }
 void insertAt(int element, int pos) {
 if((pos > size) || (pos < 0)) {
 cout << "Invalid index";
 return;
 }
 if(size == MIN_CAPACITY) {
 resize();
 }
 size++;
 for(int i = size - 1; i >= pos; i--) {
 if(i == pos) {
 array[i] = element;
 } else {
 array[i] = array[i-1];
 }
 }
 }
 // returns size of array
 int length() {
 return size;
 }
 // doubles capacity if it has to and deletes reference to current array.
 void resize() {
 MIN_CAPACITY *= GROWTH_FACTOR;
 T *temp = new T[MIN_CAPACITY];
 copy(temp);
 delete [] array;
 array = temp;
 }
 // copies original array into temp
 void copy(T temp[]) {
 for(int i = 0; i < size; i++) {
 temp[i] = array[i];
 }
 }
 // returns element in x position.
 T get(int pos) {
 return array[pos];
 }
};
int main() {
 dynamic_array<int> dynArr;
 dynArr.append(3);
 dynArr.append(4);
 dynArr.append(5);
 dynArr.append(4);
 dynArr.append(33);
 dynArr.append(3);
 dynArr.deleteAt(6);
 return 0;
}

• zelo: Thank you so much for the resources provided! Both answers were really helpful and insightful.

Answer 1

Hi and welcome to the site. Your code already looks quite good. However, there are still some issues beyond what @Björn Linqvist wrote.

1. const correctness

   This means that all variables as well as function arguments that are not mutated should be declared const. In addition methods that do not change the state of the object, aka pure observers should also be marked const. This greatly improves the ability to reason about code and helps the compiler help you. As an example

   int size() const {
    return _size;
   }
   T get(const int pos) const {
    return array[pos];
   }
   

2. The latter function is an even better example as it shows that something is missing. Often inside const code pathes you need to access elements of the array. So you need both a const and a non-const accessor. Also you are returning a copy of the object. Generally, a reference is returned.

   T& get(const int pos) {
    return array[pos];
   }
   const T& get(const int pos) const {
    return array[pos];
   }
   

3. Your deleteAt function is subtly incorrect.

   void deleteAt(int pos) {
    assert(0 <= pos && pos < _size);
    _size--;
    for (int i = pos; i < _size; i++) {
    array[i] = array[i + 1];
    }
   }
   

   Here you are shifting the elements from [pos, size_ - 1] to the left. However, what happens when T is a nontrivial type that has a destructor? The element at position size_ is copied to position size_ - 1 but is still alive. You need to explicitely call std::destroy here or you will get a lot of incredibly hard to debug bugs.

4. Honor conventional naming.

   C++ has a rich ecosystem of libraries and the STL. Most of these use consistent naming conventions, e.g. insert rather than insertAt. This might not seem a big deal but other programmers will have a hard time using your code. Even worse you will have a hard time using other code as you will mix those names.

   This is especially bad when naming contradicts expected behavior. resize conventionally takes a input argument that represents the size the container should have. Your resize method does something different so it will be highly confusing.

5. Please do not use using namespace std; This will at some point get you in all sorts of trouble. Maybe not with the STL but definitely when you use it with other namespaces as the actual functionality of using namespace foo is highly surprising. There is a reason namespaces are generally short and typing std:: is quite easy.

6. Iterators.

   C++ algorithm use iterators as an incredibly powerfull abstraction. You should provide begin() and end() methods. Also you should understand why you would want begin() and begin() const and cbegin().

7. Algorithms.

   C++ algorithms are incredibly powerfull and the STL is full of them. You should have a look at the algorithms and try to use them in you code (insert and erase are good candidates). I can highly recommend Connor Hoekstra and his Algorithm Intuition talk.

Answer 2

The code is pretty good as it is. Here is how I would improve it:

Constant handling

In C++, you should prefer const over #define. So

#define INITIAL_CAPACITY 5

becomes

const int INITIAL_CAPACITY = 5;

Also don't use all uppercase names for non constant variables. It is confusing and breaks the 50 year old tradition.

Clearer names

I renamed a few of your variables:

• MIN_CAPACITY => capacity Because the instance variable holds the current capacity of the dynamic array, not the minimum capacity.

• length() => size The words length and size are synonymous but using them both can cause confusion. A reader might think is the length the number of elements in the array and size the allocacted size, or vice versa?

Offby one errors

You have an offby one error in deleteAt. If you have a dynamic array with 5 elements, then their positions are 0 to 4 so deleteAt(5) shouldn't work, but it does. I've fixed that for you.

Pretty printing

Adding pretty printing functions is almost always a good idea because they make debugging much easier. I've added one for you.

Error handling

Your error handling consists of printing to stdout and letting the program continue to run. That is incorrect because errors might not be discovered if stdout is redirected or the user is not paying attention to what is printed.

There are many ways to handle errors. I've implemented basic assert based error handling for you. But you can certainly be fancier and use exceptions or status codes.

Functions implemented in terms of each other

For all dynamic arrays dynarr.append(x) is equivalent to dynarr.insertAt(x, dynarr.size()). So append can just call insertAt.

Destructor

Your dynamic array allocates memory in the constructor, but there is no corresponding destructor that frees the memory. I've added one looking like this:

~dynamic_array() {
 delete[] array;
}

Copying memory

There's a function called std::copy which you can use for copying memory. That way, you don't have to write your own copy function.

Pointless comments

Writing good comments is hard. As a reviewer I much prefer no comments over pointless comments. An example of a pointless comment is // constructor init. I can see that the lines below is the constructor so the comment doesn't tell me anything I didn't already know. Same for the comment // returns size of array.

Source code

Here is the improved version of the dynamic array:

#include <assert.h>
#include <cstring>
#include <iostream>
using namespace std;
const int INITIAL_CAPACITY = 2;
const int GROWTH_FACTOR = 2;
template <class T>
class dynamic_array {
 T *array;
 int capacity = INITIAL_CAPACITY;
 int _size;
public:
 dynamic_array() {
 array = new T[capacity];
 _size = 0;
 }
 ~dynamic_array() {
 delete[] array;
 }
 void deleteAt(int pos) {
 assert(0 <= pos && pos < _size);
 _size--;
 for (int i = pos; i < _size; i++) {
 array[i] = array[i + 1];
 }
 }
 void insertAt(int element, int pos) {
 assert(0 <= pos && pos <= _size);
 if(_size == capacity) {
 resize();
 }
 for(int i = _size; i > pos; i--) {
 array[i] = array[i-1];
 }
 _size++;
 array[pos] = element;
 }
 void append(T element) {
 insertAt(element, _size);
 }
 int size() {
 return _size;
 }
 // doubles capacity if it has to and deletes reference to current array.
 void resize() {
 capacity *= GROWTH_FACTOR;
 T *temp = new T[capacity];
 copy(array, array + _size, temp);
 delete [] array;
 array = temp;
 }
 T get(int pos) {
 return array[pos];
 }
 void pretty_print() {
 cout << "[";
 for (int i = 0; i < _size - 1; i++) {
 cout << array[i] << " ";
 }
 if (_size) {
 cout << array[_size - 1];
 }
 cout << "]\n";
 }
};

• interjay: Using memcpy here is not a good idea, and will behave badly if T isn't trivially copyable.
• Gaslight Deceive Subvert: True, it should be std::copy