Manually resize array in C++

Question

I am sorry if this has already been covered before. I know how to do this is C and Java but not C++. Without using a pre-existing class which includes the use of Vector, how would you increase the size of an array given the code below?

The array expansion and assignment to the array takes place in push() noted with the all caps comment.

EDIT: As I have mentioned in comments below this is a question regarding manually reallocating arrays rather than using std::vector or "Dynamic Arrays."

Line.h

#include <iostream>
#include "Point.h"

using namespace std;

class Line {
    public:
        Line();
        virtual ~Line();

        // TAKE IN NEW POINT, INCREASE THE ARRAY SIZE AND ADD NEW POINT TO THE END OF THE ARRAY
        void push(const Point& p);

    private:
        unsigned int index;  // size of "points" array
        Point* points;

};

Main.cpp

#include <iostream>
#include "Point.h"
#include "Line.h"

using namespace std;

int main() {

    int x, y;
    int size;           // Some user defined size for the array
    Line line;

    Point a[size];      // Some points that are already filled

    // Push the data in a[] to the variable "line"
    for(int i = 0; i < size; i++){
        // Increase array size of Point* points in variable line and add a[i] to the end of the array
        line.push(points[i]);
    }

    return 0;
}

Answer 1

The simple answer is you should always use std::vector in this case. However it might be useful to explain just why that is. So lets consider how you would implement this without std::vector so you might see just why you would want to use std::vector:

// Naive approach
Line::push(const Point& p)
{
    Point* new_points = new Points[index + 1];
    std::copy(std::make_move_iterator(points), std::make_move_iterator(points+index), new_points);
    new_points[index] = p;
    delete[] points;
    points = new_points;
    index += 1;
}

This approach has many problems. We are forced to reallocate and move the entire array every time an entry is inserted. However a vector will pre-allocate a reserve and use space out of the reserve for each insert, only re-allocating space once the reserve limit is surpassed. This mean vector will far out perform your code in terms of performance as less time will be spent allocating and moving data unnecessarily. Next is the issue of exceptions, this implementation has no exception guarantees, where as the std::vector provides you with a strong exception guarantee: https://en.wikipedia.org/wiki/Exception_safety. Implementing a strong exception guarantee for your class is none trivial, however you would have automatically got this had you implemented this in terms of std::vector as such

Line::push(const Point& p)
{
    points.push_back(p);
}

There are also other more subtle problems with your approach, your class does not define copy or assignment operators and so gets compiler generated shallow copy versions generated which means if someone copies your class then allocated members will get deleted twice. To resolve this you need to follow the rule of 3 paradigm pre C++11 and the rule of 5 for C++ 11 onwards: https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming). However had you used a vector none of this would be needed as you would benefit from the rule of zero and be able to rely on the compiler generated defaults: https://blog.rmf.io/cxx11/rule-of-zero

Answer 2

Essentially the only way is to use a dynamic array (one created using new[]) and to create an entirely new dynamic array and copy (or move) the objects from the old array to the new one.

Something like this:

class Line {

public:
    Line(): index(0), points(nullptr) {} // initialize
    virtual ~Line() { delete[] points; } // Clean up!

    void push(const Point& p)
    {
        // create new array one element larger than before
        auto new_points = new Point[index + 1];

        // copy old elements to new array (if any)
        for(unsigned int p = 0; p < index; ++p)
            new_points[p] = points[p];

        new_points[index] = p; // then add our new Point to the end

        ++index; // increase the recorded number of elements

        delete[] points; // out with the old

        points = new_points; // in with the new


    }

private:
    unsigned int index;  // size of "points" array
    Point* points;

};

But this approach is very inefficient. To do this well is quite complex. The main problems with doing things this way are:

• Exception safety - avoiding a memory leak if an exception is thrown.
• Allocation - avoiding having to reallocate (and re-copy) every single time.
• Move semantics - taking advantage of some objects ability to be moved much more efficiently than they are copied.

A (slightly) better version:

class Line {

public:
    Line(): index(0) {} // initialize
    virtual ~Line() { } // No need to clean up because of `std::unique_ptr`

    void push(const Point& p)
    {
        // create new array one element larger than before
        auto new_points = std::unique_ptr<Point[]>(new Point[index + 1]);    

        // first add our new Point to the end (in case of an exception)
        new_points[index] = p; 

        // then copy/move old elements to new array (if any)
        for(unsigned int p = 0; p < index; ++p)
            new_points[p] = std::move(points[p]); // try to move else copy

        ++index; // increase the recorded number of elements

        std::swap(points, new_points); // swap the pointers
    }

private:
    unsigned int index;  // size of "points" array
    std::unique_ptr<Point[]> points; // Exception safer

};

That takes care of exception safety and (to some degree - but not entirely) move semantics. However it must be pointed out that exception safety is only going to be complete if the elements stored in the array (type Point) are themselves exception safe when being copied or moved.

But this does not deal with efficient allocation. A std::vector will over allocate so it doesn't have to do it with every new element. This code also misses a few other tricks that a std::vector would employ (like allocating uninitialized memory and constructing/destructing the elements manually as and when they are needed/discarded).

Answer 3

You basically have no way but to allocate a new array, copy existing values inside and delete [] the old one. That's why vector is doing the reallocation by a multiplicative factor (say each reallocation doubles the size). This is one of the reasons you want to use the standard library structures instead of reimplementing.

Answer 4

Keep It Simple

In my opinion, in this case, it's better to use a Linked-List of CPoint in CLine:

struct CPoint
{
    int x = 0, y = 0;
    CPoint * m_next = nullptr;
};


class CLine
{
public:
    CLine() {};
    virtual ~CLine()
    {
        // Free Linked-List:
        while (m_points != nullptr) {
            m_current = m_points->m_next;
            delete m_points;
            m_points = m_current;
        }
    };

    // TAKE IN NEW POINT, INCREASE THE ARRAY SIZE AND ADD NEW POINT TO THE END OF THE ARRAY
    void push(const CPoint& p)
    {
        m_current = (((m_points == nullptr) ? (m_points) : (m_current->m_next)) = new CPoint);
        m_current->m_x = p.m_x;
        m_current->m_y = p.m_y;
        m_index++;
    };

private:
    unsigned int m_index = 0;  // size of "points" array
    CPoint * m_points = nullptr, * m_current = nullptr;
};

.

Or, even better with smart pointers:

#include <memory>

struct CPoint
{
    int m_x = 0, m_y = 0;
    std::shared_ptr<CPoint> m_next;
};


class CLine
{
public:
    CLine() {};
    virtual ~CLine() {}

    // TAKE IN NEW POINT, INCREASE THE ARRAY SIZE AND ADD NEW POINT TO THE END OF THE ARRAY
    void push(const CPoint& p)
    {
        m_current = (((m_points == nullptr) ? (m_points) : (m_current->m_next)) = std::make_shared<CPoint>());
        m_current->m_x = p.m_x;
        m_current->m_y = p.m_y;
        m_index++;
    };

private:
    unsigned int m_index = 0;  // size of "points" array
    std::shared_ptr<CPoint> m_points, m_current;
};