If you arrived here directly (eg. from a google search), you might want to check the main page of this test first.
The class obviously implements an array (which size is fixed but determined at runtime as a parameter to the constructor) which cannot be indexed out of boundaries. If the array is read out of boundaries, the default value for the element type is returned (eg. 0 in the case of integers).
The major problem with the implementation is that it allocates memory dynamically and lacks a proper copy constructor and assignment operator. This will cause deleted memory to be accessed and/or duplicate deletes in certain cases.
This is the simplest example of double deletion:
void foo()
{
Array<int> a(5);
Array<int> b(a); // Only the 'data' pointer is copied,
// not the array contents
// Here the memory pointed by 'data' will be deleted twice!
}
This is an example of accessing deleted memory:
void foo(Array<int> a)
{
// Nothing needs to be done here.
// 'a' will be destroyed here.
}
void bar()
{
Array<int> b(5)
foo(b); // This will create a copy of the class,
// but only 'data' is copied
// At this point 'data' has been deleted!
b.getValue(2); // Access to deleted memory!
}
There are basically four different ways of dealing with this problem, depending on the specifications of the class:
Often copying and assignment is not needed with this type of class. Functions can take arrays by const reference (instead of by value) so the copy constructor is often not necessary (and it's also more efficient that way). Also if assignment is not needed either, that can be forbidden too.
Forbidding copying can be done by declaring the copy constructor and assignment operator in the private section of the class, without an implementation. This way if a copying attempt is done (by mistake) the compiler will give an error message.
Thus these lines should be added to the private section of the class (and nothing else is needed):
Array(const Array&);
Array& operator=(const Array&);
If copying and/or assignment will be needed in the program, then another simple solution is to just implement a copy constructor and assignment operator which simply copy the data. This way each copy of the class will have its own array and the problem is avoided. It can be done like this (in the public section of the class):
Array(const Array& cpy):
data(0), size(cpy.size)
{
if(size > 0)
{
data = new T[size];
for(unsigned i = 0; i < size; ++i)
data[i] = cpy.data[i];
}
}
const Array& operator=(const Array& cpy)
{
// Check for assignment onto itself:
if(data == cpy.data) return *this;
if(data) { delete[] data; data = 0; }
size = cpy.size;
if(size)
{
data = new T[size];
for(unsigned i = 0; i < size; ++i)
data[i] = cpy.data[i];
}
return *this;
}
Often it would be nice to be able to pass data structures like this
one by value and to assign them around but modifying the copies is never
done and thus it would be a huge waste of time and memory if the data was
needlessly copied every time. In other words, sometimes it would be very
useful if the Array class acted like a reference to
the data instead of being the data itself. This way just this reference
is copied around and not the data, and when the last reference to the
data goes out of scope, the data is deleted.
(One practical situation where this may be the desired behaviour is
when you create a big std::vector<Array> and then
use std::sort() to sort its contents. The arrays will be
copied around inside the vector many times, but none of the copies are
modified and the deep-copy solution would thus be very inefficient.)
This can be implemented by adding a reference counter to the class. This way the data is never copied (even though the instances of the class are) but there's still no risk of memory leaks nor double deletions nor accessing deleted memory. One has to simply remember that if a copy is modified, all the other copies are "modified" too (because they all point to the same data).
Implementing reference counting is not unambiguous, and there are many ways of doing it efficiently depending on the class, but if you are interested in seeing a generic solution applied to this case, here's the code.
The copy-on-write technique is a kind of lazy evaluation algorithm: Instead of copying the data right away, the class copies it only if and when needed (in other words, when an attempt to modify a copy is performed). It's basically just an extension to the reference counting technique: If there's more than one reference to an existing data and one of the references tries to modify it, it first makes a copy of the data for itself before the modification.
This way it is possible to copy and assign the array as much as you like without any actual data copying happening, yet if a copy is modified, it will not modify all the other instances of the data, but instead a deep copy will be done for that copy first. In other words, it will externally work exactly in the same way as the deep copying solution, but copying and assigning will be much more efficient.
Adding copy-on-write functionality to the reference counting solution
above is very trivial. You can see the code here.
(The only modifications are in the setValue() function and the
addition of a new function at the end of the class.)