9
\$\begingroup\$

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!");
        }
    }   
};
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Is this for learning purposes, or why aren't you simply use std::vector instead of rolling your own class? \$\endgroup\$ Commented Jul 21, 2020 at 15:19
  • 4
    \$\begingroup\$ Learning purpouses of course. I want to implement all the data structures by myself. \$\endgroup\$
    – Pythenx
    Commented Jul 21, 2020 at 15:20

3 Answers 3

7
\$\begingroup\$

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/

\$\endgroup\$
1
  • \$\begingroup\$ initializer_lists only give const references to their elements, so std::copy is equivalent to std::move in this case. \$\endgroup\$
    – L. F.
    Commented Jul 29, 2020 at 5:59
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ So should I test if m_array == nullptr each time in insert() to fix this? Isn't there some more elegant solution? I also can't initialize m_array = new T[1], because then the move constructor will become very inefficient \$\endgroup\$
    – Pythenx
    Commented Jul 21, 2020 at 17:49
  • 2
    \$\begingroup\$ @Pythenx There are several approaches. I would set m_capacity = 0 in the constructor and not allocate at all. Note that resize also breaks on an empty DynamicArray. I would add a new private method increase_capacity, which handles m_capacity == 0 accordingly. \$\endgroup\$
    – Zeta
    Commented Jul 21, 2020 at 17:57
3
\$\begingroup\$
  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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Note you are correct about using std::size_t. But your argument (1) about int and std::size does not hold. If you pass a -1 to a method that only accepts std::size_t (unsigned integer type) then it auto converts to an unsigned value. So it does not provide any real protection against negative values. The reason to use std::size_t is not because it is unsigned but because the name conveys meaning. The standard committee has long lamented that it chose unsigned for std::size (now consider that a mistake, But we are now stuck with it as unsigned for backward compatability). \$\endgroup\$ Commented Jul 22, 2020 at 17:43
  • \$\begingroup\$ It's not about protection against negative values (though any value of an unsigned type is, by definition, non-negative). Unsigned types have such notable property as always perfectly defined operations, unlike signed which are not completely defined. \$\endgroup\$
    – bipll
    Commented Jul 22, 2020 at 21:01
  • \$\begingroup\$ If it's not about non-negative values. Then why bring it up in your explanation? If the problem is something about not completely defined operations you should add that to your description and explain why it makes the interface bad. At the moment I still don't see anything bad about using an int in the interface per se. I would still use std::size_t but only because of its documentation purposes. \$\endgroup\$ Commented Jul 22, 2020 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.