How to delete an array of uninstantiated elements in C++

Question

I am trying to learn C++ by implementing some random data structures, and I ran into some trouble while attempting to implement my own vector class.

template <class T>
class vector {
public:
    vector() {
        this->arr = createArray(DEFAULT_SIZE);
        this->arrLength = DEFAULT_SIZE;
    }

    vector(int size) {
        this->arr = createArray(size);
        this->arrLength = size;
    }

    ~vector() {
        delete[] arr;
    }

    T& operator[](int i) {
        return at(i);
    }

    T& at(int i) {
        if (i < 0 || i >= size) {
            throw std::out_of_range("Index is out of range");
        }
        return arr[i];
    }

    void push(T item, int index) {
        if (index < 0 || index > size) {
            throw std::out_of_range("Index is out of range");
        }
        if (size == arrLength) {
            T* curArr = createArray(arrLength * 2);
            for (int i = 0; i < size; i++) {
                curArr[i] = arr[i];
            }
            delete[] arr;
            arr = curArr;
            arrLength *= 2;
        }

        for (int i = size - 1; i >= index; i--) {
            arr[i + 1] = std::move(arr[i]);
        }
        arr[index] = item;
        size++;
    }

    void push_back(T item) {
        push(item, size);
    }

    T erase(int index) {
        T cur = arr[index];
        for (int i = index + 1; i < size; i++) {
            arr[i - 1] = std::move(arr[i]);
        }
        return cur;
    }

    int getCapacity() {
        return arrLength;
    }
private:
    const int DEFAULT_SIZE = 8;

    T* arr;
    int size = 0;
    int arrLength;

    T* createArray(int size) {
        return static_cast<T*>(operator new[](size * sizeof(T)));
    }
};

So the first problem that I got was instantiating the backing array when the class does not have a default constructor. I used the operator new and it worked fine.

Next, I realized errors appearing when I override T's destructor function, and it will show the output

learncpp(81115,0x104e78580) malloc: *** error for object 0x600003bd50f0: pointer being freed was not allocated
learncpp(81115,0x104e78580) malloc: *** set a breakpoint in malloc_error_break to debug

the class:

class Test  {
public:
    int x;
    Test(int x) {
        this->x = x;
    }

    ~Test() {

    }
};

I assume that it is outputting error because it is trying to call destructors on uninstantiated objects.

What should I do to fix this problem?

In addition, what are some visible issues with the way that I wrote the C++ class other than not satisfying rule of three.

Answer 1

I am not so happy with your design. Especially the handling of the number of contained elements and the capacity of the vector.

You should add also more constructors and, very inportant, an iterator, so that the class can interact with std::algorithms or simply a range based for loop.

Please see the below example.

It can give you some ideas, how to optimze your code:

#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>

#include <algorithm>

// -----------------------------------------------------------------------------------------------
// Definition of simple dynamic array class
template <typename T>
class DynamicArray {
    // The Dynamic Array has an initial capacity. 
    // If more elements will be added, there will be a reallocation with double capacity
    static constexpr unsigned int InitialCapacity{ 8 };

    // Internal data ------------------------------------------------------------------------------
    T* data{};                                 // Dynamic Storage for Data
    unsigned int numberOfElements{};           // Number of elements currently in the container
    unsigned int capacity{ InitialCapacity };  // Current maximum capacity of the container
public:
    // Construction and Destruction ---------------------------------------------------------------
    DynamicArray();                            // Default constructor. Allocate new memory
    DynamicArray(const unsigned int size);     // Constructor for a given size. Allocate new memory
    DynamicArray(const DynamicArray& other);   // Copy constructor. Make a deep copy
    // Special constructors
    template <class Iterator> DynamicArray(Iterator begin, Iterator end);   // Initialize from range   
    template <int N> DynamicArray(const T(&other)[N]);                      // Initialize from C_Sytle array,e.g. a string literal
    template <int N> DynamicArray(T(&other)[N]);
    DynamicArray(const std::initializer_list<T>& list);                     // Take data from initializer list

    ~DynamicArray();                            // Destructor: Release previously allocated memory

    // Housekeeping ---------------------------------------------------------------
    bool empty() const;                         // Do we have elements in the container? Do not mix up with capacity
    void clear();                               // Clear will not delete anything. Just set element count to 0
    unsigned int size() const;                  // How many elements are in the container

    // Main working functions
    void push_back(const T& d);                 // Add a new element at the end

    // Operators for class------------------------ ---------------------------------------------------------------

    T operator[] (const unsigned int i) const;  // Index operator, get data at given index. No boundary check
    T& operator[] (const unsigned int i);       // Index operator, get data at given index. No boundary check
    DynamicArray& operator=(const DynamicArray& other); // Assignment


    // Add iterator properties to class ---------------------------------------------------------------
    class iterator {                           // Local class for iterator
        T* iter{};                             // This will be the iterator 
        T* begin{};                            // For boundary check
        T* end{};                              // For boundary check

    public:                                    // Define alias names necessary for the iterator functionality
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Constructor
        iterator(T* const i, T* const b, T* const e);          

        // Dereferencing
        reference operator *() const;
        pointer operator ->() const;

        // Aithmetic operations
        iterator& operator ++();
        iterator& operator --();
        iterator operator ++(int);
        iterator operator --(int);
        iterator operator +(const difference_type& n) const;
        iterator& operator +=(const difference_type& n);
        iterator operator -(const difference_type& n) const;
        iterator& operator -=(const difference_type& n);

        // Comparison
        bool operator != (const iterator& other) const;
        bool operator == (const iterator& other) const;
        bool operator < (const iterator& other) const;
        bool operator > (const iterator& other) const;
        bool operator <= (const iterator& other) const;
        bool operator >= (const iterator& other) const;
        
        // Reference and difference
        reference operator[] (const difference_type& n);
        difference_type operator-(const iterator& other) const;
    };

    // Begin and end function to initialize an iterator
    iterator begin() const;
    iterator end() const;

    // Working functions dealing with iterators. More may be added
    iterator erase(iterator pos);

};


// Default constructor. Allocate new memory
template <typename T>
inline DynamicArray<T>::DynamicArray() { 
    data = new T[capacity]; 
} 
// Constructor for certain size. Allocate new memory
template <typename T>
inline DynamicArray<T>::DynamicArray(const unsigned int size) : data(new T[size]), numberOfElements(0), capacity(size) {
} 

// Copy constructor
template <typename T>
DynamicArray<T>::DynamicArray(const DynamicArray& other) {  // Copy constructor. Make a deep copy
    capacity = numberOfElements = other.numberOfElements;
    data = new T[capacity];                // Get memory, same size as other container
    for (size_t k = 0; k < other.numberOfElements; ++k)
        data[k] = other.data[k];           // Copy data
}

// Range constructor
template <typename T>
template <class Iterator>
DynamicArray<T>::DynamicArray(Iterator begin, Iterator end) {
    data = new T[capacity];
    for (Iterator i = begin; i != end; ++i)
        push_back(*i);
}

// Construct from a const C-Style Array, like for example "Hello"
template <typename T>
template <int N>
DynamicArray<T>::DynamicArray(const T(&other)[N]) {
    capacity = numberOfElements = N;
    data = new T[capacity];                // Get memory, same size as other container
    for (size_t k = 0; k < N; ++k)
        data[k] = other[k];          // Copy data
}
// Construct from a C-Style Array
template <typename T>
template <int N>
DynamicArray<T>::DynamicArray(T(&other)[N]) {
    capacity = numberOfElements = N;
    data = new T[capacity];                // Get memory, same size as other container
    for (size_t k = 0; k < N; ++k)
        data[k] = other[k];          // Copy data
}

// Construct from an initilizer list
template <typename T>
DynamicArray<T>::DynamicArray(const std::initializer_list<T>& list) { 
    data = new T[capacity]; 
    for (const T& t : list) push_back(t); 
}

// Destructor will release the dynamic allocated memory
template <typename T>
inline DynamicArray<T>::~DynamicArray() { 
    delete[] data; 
}         // Destructor: Release previously allocated memory

// Some houskeeping functions
template <typename T>
inline bool DynamicArray<T>::empty() const {
    return numberOfElements == 0; 
}
template <typename T>
inline void DynamicArray<T>::clear() {
    numberOfElements = 0; 
};    // Clear will not delete anything. Just set element count to 0

template <typename T>
inline unsigned int DynamicArray<T>::size() const {
    return numberOfElements; 
} // How many elements are in the container

// Main workhorse for a dynamic array. 
// Store element, and alwaysprovide enough memory
template <typename T>
void DynamicArray<T>::push_back(const T& d) {               // Add a new element at the end
    if (numberOfElements >= capacity) {                     // Check, if capacity of this dynamic array is big enough
        capacity *= 2;                                      // Obviously not, we will double the capacity
        T* temp = new T[capacity];                          // Allocate new and more memory
        for (unsigned int k = 0; k < numberOfElements; ++k)
            temp[k] = data[k];                              // Copy data from old memory to new memory
        delete[] data;                                      // Release old memory
        data = temp;                                        // And assign newly allocated memory to old pointer
    }
    data[numberOfElements++] = d;                           // And finally, store the given data at the end of the container
}

// Operators for class ------------------------ ---------------------------------------------------------------
template <typename T>
inline typename T DynamicArray<T>::operator[] (const unsigned int i) const {
    return data[i]; 
}      // Index operator, get data at given index. No boundary check

template <typename T>
inline typename T& DynamicArray<T>::operator[] (const unsigned int i) {
    return data[i]; 
}  // Index operator, get data at given index. No boundary check

// Assignement operator. Make a deep copy
template <typename T>
DynamicArray<T>& DynamicArray<T>::operator=(const DynamicArray& other) {         
    if (this != &other) {                                    // Prevent self-assignment
        delete[] data;                                       // Release any previosly existing memory
        capacity = numberOfElements = other.numberOfElements;// Take over capacity and number of elements from other container
        data = new T[capacity];                              // Get new memory, depending on size of other 
        for (unsigned int k = 0; k < numberOfElements; ++k)  // Copy other data
            data[k] = other.data[k];
    }
    return *this;
}

// Implementation of iterator functions ---------------------------------------------------------------------
// COnstruction 
template <typename T>
inline DynamicArray<T>::iterator::iterator(T* const i, T* const b, T* const e) : iter(i), begin(b), end(e) {
};  // Constructor for the iterator

// Dereferencing
template <typename T>
inline typename DynamicArray<T>::iterator::reference DynamicArray<T>::iterator::operator *() const {
    return *iter; 
} 

template <typename T>
inline typename DynamicArray<T>::iterator::pointer DynamicArray<T>::iterator::operator ->() const {
    return iter; 
}

// Arithmetic operations
template <typename T>
inline typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator ++() {
    if (iter < end) 
        ++iter; 
    return *this; 
} 

template <typename T>
inline typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator --() {
    if (iter > begin) 
        --iter; 
    return *this; 
} 

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator ++(int) {
    DynamicArray<T>::iterator tmp = *this;  
    if (this->iter < end) 
        ++(*this); 
    return tmp; 
} 

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator --(int) {
    DynamicArray<T>::iterator tmp = *this; 
    if (this->iter > begin) 
        --(*this); 
    return tmp; 
} 

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator +(const DynamicArray<T>::iterator::difference_type& n) const {
    DynamicArray<T>::iterator tmp = *this; 
    DynamicArray<T>::iterator::difference_type k{ n }; 
    while (k--) 
        ++tmp.iter; 
    return tmp; 
}

template <typename T>
typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator +=(const DynamicArray<T>::iterator::difference_type& n) {
    DynamicArray<T>::iterator::difference_type k{ n };  
    while (k--) 
        ++iter; 
    return *this; 
}

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator- (const DynamicArray<T>::iterator::difference_type& n) const {
    DynamicArray<T>::iterator tmp = *this;
    DynamicArray<T>::iterator::difference_type k{ n };  
    while (k--)  
        --tmp.iter; 
    return tmp; 
}

template <typename T>
typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator -=(const typename DynamicArray<T>::iterator::difference_type& n) {
    DynamicArray<T>::iterator::difference_type k{ n };  
    while (k--) 
        --iter;  
    return *this; 
}

// Comparison functions
template <typename T>
inline typename DynamicArray<T>::iterator::reference DynamicArray<T>::iterator::operator[] (const typename DynamicArray<T>::iterator::difference_type& n) {
    return *(iter + n); 
};

template <typename T>
inline bool DynamicArray<T>::iterator::operator != (const iterator& other) const {
    return iter != other.iter; 
}  

template <typename T>
inline bool DynamicArray<T>::iterator::operator == (const iterator& other) const {
    return iter == other.iter; 
}  

template <typename T>
inline bool DynamicArray<T>::iterator::operator < (const iterator& other) const {
    return iter < other.iter; 
}  
template <typename T>
inline bool DynamicArray<T>::iterator::operator > (const iterator& other) const {
    return iter > other.iter; 
}  // Comparison

template <typename T>
inline bool DynamicArray<T>::iterator::operator <= (const iterator& other) const {
    return iter <= other.iter; 
}  // Comparison

template <typename T>
inline bool DynamicArray<T>::iterator::operator >= (const iterator& other) const {
    return iter >= other.iter; 
}  // Comparison

// Delta 
template <typename T>
inline typename DynamicArray<T>::iterator::difference_type DynamicArray<T>::iterator::operator-(const typename DynamicArray<T>::iterator& other) const {
    return iter - other.iter; 
}

// ------------------------------------------------------------------------
// Get iterators for dynamic array
template <typename T>
inline typename DynamicArray<T>::iterator DynamicArray<T>::begin() const {
    return iterator(data, data, data + numberOfElements); 
}

template <typename T>
inline typename DynamicArray<T>::iterator DynamicArray<T>::end() const {
    return iterator(data + numberOfElements, data, data + numberOfElements); 
}

// ------------------------------------------------------------------------
// Any other functions for dynamic array
template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::erase(typename DynamicArray<T>::iterator pos) {
    iterator result{ pos };
    if (pos != end()) {
        while (pos != end()) {
            *pos = *(pos + 1);
            ++pos;
        }
        ++result;
        --numberOfElements;
    }
    return result;
}