I have the following class that tries to work on huge arrays where initialising, reading, writing and deleting are all O(1):
#include <cstdlib>
#include <iostream>
using namespace std;
template<class T> class Init_array {
public:
explicit Init_array(size_t n, const T &val = T()) :
data(static_cast<T *>(malloc(sizeof(T) * n))), default_value(val),
valid(static_cast<size_t *>(malloc(sizeof(size_t) * n))),
x_check(static_cast<size_t *>(malloc(sizeof(size_t) * n))),
count() {
}
~Init_array() {
free(data);
free(valid);
free(x_check);
}
bool is_valid(size_t index) const {
// assume daemons do not fly out of the nose accessing uninitialised size_t
return valid[index] < count && x_check[valid[index]] == index;
}
T &operator[](size_t index) {
if (!is_valid(index)) {
valid[index] = count;
x_check[count] = index;
++count;
new(data + index) T(default_value);
}
return data[index];
}
const T &operator[](size_t index) const {
if (!is_valid[index]) {
return default_value;
} else {
return data[index];
}
}
void erase(size_t index) {
x_check[valid[index]] = x_check[count - 1];
valid[x_check[count - 1]] = valid[index];
--count;
}
private:
T *data;
const T default_value;
size_t *valid;
size_t *x_check;
size_t count;
};
int main() {
Init_array<int> x(1ll << 30); // 20 GiB RAM needed
cout << x[3827749] << '\n';
const size_t test_index = 23829073;
x[test_index] = 123456;
const size_t another_test_index = 212748399;
x[another_test_index] = 888888;
cout << x[test_index] << '\n';
cout << x[another_test_index] << '\n';
x.erase(test_index);
cout << x[test_index] << endl;
}
However, the line after the comment is technically undefined behaviour because it will try to read uninitialised values. I am afraid that it will crash on some machines. Is it possible to make the class free of undefined behaviour, while retaining everything as O(1)?
