The problem
We want to use a very large array for some computations. When created, all the elements of this array have to be initialized to some value. We'll only use a few values from the array1, so we don't want the runtime of the algorithm to be dominated by the initialization time.
In other words, we want to create and access an initialized array in constant time2.
How can this be done ? (Hint: we may use extra memory)
After reading about the rule of three I decided to take this implementation and make it a little bit better. So here is what I came up with ...
The source code is also available here
#pragma once
#include <algorithm>
#ifndef NDEBUG
#include <iostream>
#endif
template <typename T>
class InitializedArray {
public:
InitializedArray() = default;
InitializedArray(size_t length, T initial) : mInitial(initial), mTop(0), mLength(length) {
#ifndef NDEBUG
std::cout << "[InitializedArray] Constructor" << std::endl;
#endif
// Allocate Arrays
mFrom = new size_t[mLength];
mTo = new size_t[mLength];
mElements = new T[mLength];
}
InitializedArray(const InitializedArray & other) {
#ifndef NDEBUG
std::cout << "[InitializedArray] Copy Constructor" << std::endl;
#endif
if (mLength == 0) {
// Allocate Arrays
mFrom = new size_t[other.mLength];
mTo = new size_t[other.mLength];
mElements = new T[other.mLength];
// Copy Arrays
std::copy(other.mFrom , other.mFrom + other.mLength, mFrom );
std::copy(other.mTo , other.mTo + other.mLength, mTo );
std::copy(other.mElements, other.mElements + other.mLength, mElements);
mInitial = other.mInitial;
mTop = other.mTop;
mLength = other.mLength;
} else if (mLength >= other.mLength) {
// Copy Arrays
std::copy(other.mFrom , other.mFrom + other.mLength, mFrom );
std::copy(other.mTo , other.mTo + other.mLength, mTo );
std::copy(other.mElements, other.mElements + other.mLength, mElements);
mInitial = other.mInitial;
mTop = other.mTop;
mLength = other.mLength;
}
}
~InitializedArray() {
#ifndef NDEBUG
std::cout << "[InitializedArray] Destructor" << std::endl;
#endif
// Free Arrays
delete[] mFrom;
delete[] mTo;
delete[] mElements;
}
InitializedArray & operator=(const InitializedArray & other) {
#ifndef NDEBUG
std::cout << "[InitializedArray] Copy Assignment Operator" << std::endl;
#endif
if (&other != this) {
if (mLength == 0) {
// Allocate Arrays
mFrom = new size_t[other.mLength];
mTo = new size_t[other.mLength];
mElements = new T[other.mLength];
// Copy Arrays
std::copy(other.mFrom , other.mFrom + other.mLength, mFrom );
std::copy(other.mTo , other.mTo + other.mLength, mTo );
std::copy(other.mElements, other.mElements + other.mLength, mElements);
mInitial = other.mInitial;
mTop = other.mTop;
mLength = other.mLength;
} else if (mLength >= other.mLength) {
// Copy Arrays
std::copy(other.mFrom , other.mFrom + other.mLength, mFrom );
std::copy(other.mTo , other.mTo + other.mLength, mTo );
std::copy(other.mElements, other.mElements + other.mLength, mElements);
mInitial = other.mInitial;
mTop = other.mTop;
mLength = other.mLength;
}
}
return *this;
}
T & operator[](size_t index) {
#ifndef NDEBUG
std::cout << "[InitializedArray] Subscript Operator" << std::endl;
#endif
if (mFrom[index] < mTop && mTo[mFrom[index]] == index) {
return mElements[index];
} else {
mFrom[index] = mTop;
mTo[mTop] = index;
mElements[index] = mInitial;
mTop++;
return mElements[index];
}
}
size_t size() {
return mLength;
}
private:
size_t * mFrom = nullptr;
size_t * mTo = nullptr;
T * mElements = nullptr;
T mInitial;
size_t mTop = 0;
size_t mLength = 0;
};
