Class - User Defined Smart Array with dynamic size

Question

I am writing the following array (class) that increases the size when index of this array is bigger than size of this array. I know about vectors but it has to be array. The Code looks like this:

#include <iostream>

using namespace std;

class Array {

public:
Array():_array(new float[0]), _size(0){};
~Array() {delete[] _array;}
friend ostream &operator<<(ostream&,const Array&);
float& operator[] (int index) 
{
  if(index>=_size)
  {
    float* NewArray=new float[index+1];
    for(int i=0;i<_size;++i) NewArray[i]=_array[i];
    for(int i=_size;i<index+1;++i) NewArray[i]=0; 
    delete[] _array;
    _array=NewArray;
    _size=index+1;
  }
  return _array[index];
}

private:
  float *_array; // pointer to array
  int _size; // current size of array
};

ostream &operator << ( ostream &out,  const Array& obj) // overloading operator<< to easily print array
{
  cout << "Array:\n\n";
  for (int i=0;i<obj._size;++i) 
  {
    cout << obj._array[i];
    if(i+1!=obj._size) cout << ", "; 
  }
  cout << ".\n";
  return out;
}

int main()
{
  Array CustomArray;
  CustomArray[2] = CustomArray[1] = CustomArray[0] = 3.14; // **here is the problem**
  cout << CustomArray << endl;
}

Everything is ok, 0 warnings , 0 valgrind errors, output :

3.14, 3.14, 3.14.

BUT i have to write this code ( in main ) this way :

CustomArray[0] = CustomArray[1] = CustomArray[2] = 3.14;

and now it's 3 valgrind errors: Address (some_address) is 4 bytes inside a block of size 8 free'd,

and output looks like that : 0, 0, 3.14.

unfortunately i have to write this code to work the second way ( CustomArray[0] = CustomArray[1] = CustomArray[2] = 3.14; ) Can you guys help ? Thanks in advance

The problem is that CustomArray[1] invalidates all previous references and pointers to data because it is reallocated. What you may do is a return an ArrayAccess that holds the index and doesn't hold a reference but accesses the original array everytime. — WorldSEnder
– WorldSEnder, Commented Jul 13, 2015 at 16:29
Hmm, I don't think even std::vector could cope with that if one of those operator[] calls causes a reallocation... — cdhowie
– cdhowie, Commented Jul 13, 2015 at 16:35

cdhowie · Accepted Answer · 2015-07-13 17:23:06Z

You need to resolve this through the use of a proxy type that holds a reference to the Array object and the index passed to your operator[]. This proxy type will be implicitly convertible to float and be assignable from float, making accesses (mostly¹) transparent.

We also violate the rule of three in this case and implement the copy-assignment operator to assign the value of one array element to another so that foo[0] = foo[1] works as expected.

We need to make the following changes:

Rename the existing operator[] and make it private; it will only be used by the proxy type.
Create a new operator[] that returns a value of the proxy type.
Write the proxy type.

Change 1, inside of Array's definition:

friend class ArrayElement; // So that ArrayElement can use access()
private:
float& access(int index) 
{
  if(index>=_size)
  {
    float* NewArray=new float[index+1];
    for(int i=0;i<_size;++i) NewArray[i]=_array[i];
    for(int i=_size;i<index+1;++i) NewArray[i]=0; 
    delete[] _array;
    _array=NewArray;
    _size=index+1;
  }
  return _array[index];
}

Change 2:

// Inside of Array
public:
    ArrayElement operator[](int index);

// Implementation outside of Array
ArrayElement Array::operator[](int index) {
    return ArrayElement(*this, index);
}

Change 3:

class ArrayElement
{
    friend class Array; // So that Array can use our private constructor

private:
    ArrayElement(Array & array, int index) : array(array), index(index) { }

public:
    // Allows "foo[1] = 2"
    ArrayElement const & operator=(float v) const {
        array.access(index) = v;
        return *this;
    }

    // Violation of the rule of three, but it makes sense in this case.
    // Allows "foo[1] = foo[2]"
    ArrayElement const & operator=(ArrayElement const & other) const {
        array.access(index) = other;
        return *this;
    }

    // Allows "float x = foo[1]"
    operator float() const {
        return array.access(index);
    }

private:
    Array & array;
    int index;
};

(Minor final change, you need to forward declare ArrayElement before the definition of Array.)

See this working example.

¹ One of the caveats of this approach is using type-inference (auto in C++11) on array accesses:

auto x = an_array[1];

Now x is an ArrayElement instead of a float and its value will be observed to change when an_array[1] changes. Attempting to assign a different float value to x will change the value in an_array[1] as well, since x is just a proxy to that value.

Contrast this to the general behavior of std::vector where auto x = a_vector[0] will result in x being the element type of the vector, and therefore will hold an independent copy of the value stored in the vector.

Note, however, that the std::vector<bool> specialization follows exactly the approach I've given here (returning a proxy object) and so it does have the same auto caveat! You could take that as a blessing on this approach.

Arne Vogel · Accepted Answer · 2015-07-13 17:31:53Z

Use std::vector, directly or indirectly. Your statement

I know about vectors but it has to be array.

doesn't make sense. std::vector is guaranteed to have contiguous storage, which is probably what you mean by "array". For an instance v, you could always use the expression &v[0] to obtain the base address of the array, and, starting from C++11 the easier to read v.data() will work as well. This means you can use a vector for any function call that requires an array "C-style" as pointer and size, e.g. qsort.

If you cannot do without the automatic resize in Array::operator [], then make a class wrapper as you have done, but use std::vector internally. This is much simpler and safer. Particularily, your code has quadratic worst case performance, e.g. the following will be very very slow:

Array CustomArray;
for ( int i = 0; i < 1000000; ++i )
     CustomArray[i] = i;

std::vector is designed to not have this problem.

The other problem you mentioned, with the reference invalidation, could be solved easily by using std::deque instead, however deque does not have contiguous storage. Therefore, with std::vector, you would still have to use a proxy as described by cdhowie. However, I must confess I do not quite understand why the syntax has to be like that, or what's wrong with calling std::vector<float>::resize() manually.

Collectives™ on Stack Overflow

Class - User Defined Smart Array with dynamic size

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related