TransWikia.com

DynamicArray class in C++

Code Review Asked by Pythenx on November 8, 2021

I am pretty new to C++ and I think I have some problems of keeping code clean and optimized, especially I have problems with writing comments. I just don’t know when should I be explaining what I write. Any tips and advices will be hugely appreciated!

Here’s the code:

#include <iostream>
#include <initializer_list>
#include <stdexcept>

template <typename T>
class DynamicArray
{
public:

    DynamicArray(std::initializer_list<T> elements)
        : m_size(elements.size()) 
        , m_capacity(elements.size())
        , m_array(new T[elements.size()])
    {
        std::copy(elements.begin(), elements.end(), m_array);
    }

    DynamicArray()
        : m_size(0)
        , m_capacity(1)
        , m_array(nullptr)
    { }

    DynamicArray(DynamicArray<T>&& other)
        : DynamicArray()
    {
        swap(*this, other);
    }

    ~DynamicArray()
    {
        delete[] m_array;
    }

    DynamicArray(const DynamicArray& other)
        : m_capacity(other.m_capacity)
        , m_size(other.m_size)
        , m_array(new T[other.m_capacity])
    {
        std::copy(other.m_array, other.m_array + other.m_size, m_array);
    }

    DynamicArray& operator=(DynamicArray other)
    {
        swap(*this, other);
        return *this;
    }

    friend void swap(DynamicArray<T>& obj1, DynamicArray<T>& obj2) noexcept
    {
        std::swap(obj1.m_size, obj2.m_size);
        std::swap(obj1.m_capacity, obj2.m_capacity);
        std::swap(obj1.m_array, obj2.m_array);
    }
    
    void insert(int index, T value)
    {
        if (index != m_size) m_check_range(index);
        if (m_capacity == m_size) resize(m_capacity * 2);

        m_size++;
        
        for (int i = m_size - 2; i >= index; i--)
        {
            (*this)[i + 1] = (*this)[i];
        }

        (*this)[index] = value;
    }
        
    T remove(int index) 
    {
        m_check_range(index);
        T to_remove = (*this)[index];

        for (int i = index; i < m_size - 1; i++)
        {
            (*this)[i] = (*this)[i + 1];
        }

        m_size--;
        return to_remove;
    }
    
    // Resizes array to store n elements.
    // Guarantees strong exception safety.
    void resize(int n)
    {
        T *temp = new T[n];
        m_capacity = n;

        std::copy(m_array, m_array + m_capacity, temp);
        delete[] m_array;
        m_array = temp;
    }

    void shrink_to_fit()
    {
        resize(m_size);
    }

    int size() const
    {
        return m_size;
    }

    bool empty() const 
    {
        return m_size == 0;
    }

    int capacity() const
    {
        return m_capacity;
    }

    void append(T value)
    {
        insert(m_size, value);
    }

    void prepend(T value)
    {
        insert(0, value);
    }

    T pop(int index)
    {
        return remove(m_size - 1);
    }

    T front() const
    {
        return (*this)[0];
    }

    T back() const
    {
        return (*this)[m_size - 1];
    }

    void print() const
    {
        for (int i = 0; i < m_size; i++)
        {
            std::cout << m_array[i] << " ";
        }
        std::cout << std::endl;
    }

    T& operator[](int index)
    {
        m_check_range(index);
        return m_array[index];
    }

    const T& operator[](int index) const
    {
        m_check_range(index);
        return m_array[index];
    }
    
private:

    T *m_array;
    int m_capacity; // Capacity of the array
    int m_size ; // Number of added elements

    void m_check_range(int index) const
    {
        if (index < 0 || index >= m_size)
        {
            throw std::out_of_range("Index out of range!");
        }
    }   
};

3 Answers

  1. int does not seem a good choice for sizes and indices which can only be non-negative. std::size_t was introduced for such things.

1b. When reallocating array you don't check if doubling capacity overflows.

  1. When inserting an element into a saturated array you: 1) reallocate it with double the capacity; 2) copy all existing elements into the new buffer; 3) shift elements past the newly inserted in the new buffer.
    This hits especially sensitively if you insert an element at array's front. IMO, a slight microoptimisation would be to split current array in two, before and past the newly inserted element, and copy them separately, thus eliminating excess moves of the suffix.

  2. While you double the capacity on reallocations, its initial value is only one higher than the initial size, thus causing reallocation on the second insertion already.

  3. Using the so-called 'smart pointers', std::unique_ptr would be a good example, would relieve you from manually maintaining the pointers.

Answered by bipll on November 8, 2021

Observation

Array allocated and initializes capacity elements. Which sort of defeats the purpose of having a capacity. The point of using a capacity is that you should not be paying the price of calling the constructor on elements that you don't use.

Code Review

You should put your code into a namespace.


This does not seem correct.

    DynamicArray()
        : m_size(0)              // Size is zero fine.
        , m_capacity(1)          // But a capacity of 1 with no memory allocated!
                                 // I would say the capacity here is zero
                                 // as you have no room to add any elements.
        , m_array(nullptr)
    { }

You have accepted the initializer list elements by value.

    DynamicArray(std::initializer_list<T> elements)

So you have already made a copy of the list.

Since you have made a copy of the list the elements in the list are yours to mutate if you want to so here you could use move semantics rather than copy semantics.

        std::copy(elements.begin(), elements.end(), m_array);
        // RATHER DO THIS
        std::move(elements.begin(), elements.end(), m_array);

Normally you expect to see the move operators marked as noexcept

    DynamicArray(DynamicArray<T>&& other)

This allows certain optimizations when you use standard algorithms and containers.


Normally I write the swap function in terms of the swap method.

    friend void swap(DynamicArray<T>& obj1, DynamicArray<T>& obj2) noexcept
    {
        std::swap(obj1.m_size, obj2.m_size);
        std::swap(obj1.m_capacity, obj2.m_capacity);
        std::swap(obj1.m_array, obj2.m_array);
    }

    // I would write it like this:

    void swap(DynamicArray<T>& other) noexcept
    {
        using std::swap;
        swap(m_size,     other.m_size);
        swap(m_capacity, other.m_capacity);
        swap(m_array,    other.m_array);
    }
    friend void swap(DynamicArray<T>& lhs, DynamicArray<T>& rhs) noexcept
    {
        lhs.swap(rhs);
    }

Now methods (like move operators) don't need to call a free function to do a swap. They simply call the method version of swap and get the same affect.


Nice try.

    // Resizes array to store n elements.
    // Guarantees strong exception safety.

Unfortunately not quite. You can not do anything that may throw while the state of the object has been mutate but not in the final state.

    void resize(int n)
    {
        T *temp = new T[n];
        m_capacity = n;                                  // Mutation here

        std::copy(m_array, m_array + m_capacity, temp);  // Throw possible here
        delete[] m_array;                                // Throw possible here.
        m_array = temp;                                  // Final mutation
    }

The way to do this is in three phases:

    void resize(int n)
    {
        // Phase 1: Make your copy.
        T *temp = new T[n];
        std::copy(m_array, m_array + m_capacity, temp);

        // Phase 2: Mutate "ALL" your state to final state.
        //          You can not call anything that is not `noexcept`
        //          This limits you to very basic operations.
        m_capacity = n;
        std::swap(temp, m_array);

        // Phase 3: Clean up
        delete[] temp;           // Note the swap above.
    }

Note we can simplify this:

    void resize(int n)
    {
        // Phase 1: Make your copy.
        DynamicArray  copy(*this, n);  // Private constructor
                                       // Allocates n spaces but copies size
                                       // objects from the passed item.

        // Phase 2: Mutate "ALL" your state to final state.
        //          You can not call anything that is not `noexcept`
        //          This limits you to very basic operations.
        //          Luckily swap method is `noexcept`
        swap(copy);

        // Phase 3: Clean up
        // the object copy's destructor will do cleanup.
    }

I am a fan of one liners for methods that are this imple.

    bool empty() const 
    {
        return m_size == 0;
    }

Its OK to have a print method. But to make it more C++ like I would also add the operator<< so you can stream it. This means modifying print to take a stream.

    void print(std::ostream& out = std::cout) const
    {
        for (int i = 0; i < m_size; i++)
        {
            out << m_array[i] << " ";
        }
        out << "n";
    }
    friend std::ostream& operator<<(std::ostream& str, DynamicArray const& data)
    {
        data.print(str);
        return str;
    }

In the standard library containers that use operator[] make it a non checked interface. It is the responsibility of the user to validate before calling. They add an additional checked interface at() when the user want to validate that the index is range.

    T& operator[](int index)
    {
        m_check_range(index);
        return m_array[index];
    }


    // Think of this situation
    for(int loop = 0; loop < dA.size(); ++loop) {
        std::cout dA[loop];
    }

    // Here we have already guaranteed that the index is within the correct
    // range but we your code still forces an additional check (that we
    // know is never going to fail).

    // If I need to check then I call the `at()`version.
    printArrayElement(std::size_t index)
    {
         std::cout << dA.at(index);   // Use checked accesses
    }

Self Plug

I have a lot of other pointers in my articles about writing a vector:

https://lokiastari.com/series/

Answered by Martin York on November 8, 2021

While the following list might seem somewhat intimidating, let me first make clear that your class has a nice interface, seems reasonable safe and has a reasonable implementation.

Undefined behaviour

Unfortunately, your code contains undefined behaviour:

int main() {
    DynamicArray<int> test;
    test.append(1);
}

As test uses the default constructor, m_array == nullptr. As m_size < m_capacity, we use nullptr[0] = 1 in append, which leads to a segmentation fault on my system.

Documentation of implementation details

You should document your invariants: when do you need to allocate memory? When m_capacity == 1? Or when m_array == nullptr?

Types

An index should always be non-negative. Therefore, size_t is more suitable. This also removes the checks for a negative index.

Copy vs moves

Some of your internal operations use copies. However, those might be costly. Instead, use std::move or std::move_backward to move the elements in your ranges.

Tests

Add some basic tests for your class. Also, try AddressSanitizer to find memory issues like this faster.

Answered by Zeta on November 8, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP