Even though I probably wont use the class anymore, did I get it right now?
Obviously the class does not yet comply with the rule of three, I won't discuss this further other than to add that a simple "quick fix" is to make the class noncopyable by declaring a private, unimplemented copy constructor and assignment operator. This technique will mean you get a compile error if client code tries to copy/assign the class, and a link error if the class itself performs these operations. In C++11, I believe there is new syntax to suppress automatic generation of such functions, but I don't much practical experience with this so I won't say more.
You appear to have a bug in the last full code you posted, where isUsed is not updated if removeElement() is called.
I'd recommend at least using an assertion that isUsed[index] is true in both getElement() and removeElement().
The freeElementList and isUsed are similar arrays that are almost always accessed together, so one idea might be to have an internal struct containing both pieces of information and allocate a single array of that type. This would reduce the number of allocations required. However, I believe in this specific case you could avoid keeping both pieces of information by choosing a marker value, for example -1, to include in the freeElementList to indicate that the element is in use.
In fact, the "similar arrays" argument is true of the data instances themselves, one alternative implementation is to have an internal structure containing the potentially uninitialised data and . However, leaving it separate may have cache benefits depending on how frequent accesses are versus removals.
In the case where all members are moved to a single structure, there is no reason not to implement your class in terms of std::vector, this would simplify a lot of manual work and reduces your class to the essentials of managing the free list. If the class is to maintain the element array separate from the used/next array(s), then you could still implement in terms of std::vector with some relatively minor memory overhead (each vector would maintain the element count and capacity separately).
The addElement function doesn't gracefully handle exceptions thrown when allocating the storage or copying the elements. It both leaks memory and can leave the object in an inconsistent state. The constructor can leak if an exception throws during allocation. Implementing in terms of a single std::vector should avoid these issues, implementing in terms of multiple std::vectors would still require care.
It is typical for such containers to have a const and non-const accessors. The convention would be the const version returns a const reference, and the non-const version returns a mutable reference - unless by necessity or design the elements should not be mutable (e.g. the key in std::map is not mutable in isolation - allowing this could corrupt the map ordering).
My C++ skills are rusting of late, but I believe this is in the ballpark of an implementation in terms of std::vector:
template <typename T>
class Vector
{
private:
struct Element {
private:
static const int ELEMENT_IN_USE = -1;
int nextFreeIndex;
char storage[sizeof(T)];
public:
Element(int index) {
nextFreeIndex = index + 1;
}
~Element() {
if(isUsed()) {
object().~T();
}
}
Element(const Element &other) {
if(other.isUsed()) {
new(storage) T(other.object());
}
nextFreeIndex = other.nextFreeIndex;
}
int initialise(const T &data) {
assert(!isUsed());
int result = nextFreeIndex;
new(storage) T(data);
nextFreeIndex = ELEMENT_IN_USE;
return result;
}
void clear(int freeIndex) {
assert(isUsed());
object().~T();
nextFreeIndex = freeIndex;
}
T &object() {
assert(isUsed());
return *reinterpret_cast<T*>(storage);
}
const T &object() const {
assert(isUsed());
return *reinterpret_cast<const T*>(storage);
}
bool isUsed() const {
return nextFreeIndex == ELEMENT_IN_USE;
}
private:
// TODO: do I need this guy?
Element &operator=(Element copy);
};
int freeIndex;
std::vector<Element> elements;
public:
Vector(int initialCapacity) : freeIndex(0) {
elements.reserve(initialCapacity);
for(int i = 0 ; i < initialCapacity ; ++i) {
elements.emplace_back(i);
}
}
int addElement(const T& element) {
int currentSize = elements.size();
if(freeIndex > currentSize) {
int newSize = currentSize * 2;
elements.reserve(newSize);
for(int i = currentSize ; i < newSize ; ++i) {
elements.emplace_back(i);
}
}
int resultIndex = freeIndex;
Element &target = elements[freeIndex];
freeIndex = target.initialise(element);
return resultIndex;
}
void removeElement(int index) {
assert(index < elements.size());
elements[index].clear(freeIndex);
freeIndex = index;
}
T getElement(int index) {
assert(index < elements.size());
return elements[index].object();
}
const T &getElement(int index) const {
return elements[index].object();
}
private:
// Noncopyable: deliberately private & unimplemented
Vector(const Vector &);
Vector &operator=(const Vector &);
};
