It is not always possible to simplify program design by strictly managing the lifetimes of objects. If two objects have unpredictable lifetimes, but one of them needs to refer to the other, a simple pointer or reference is a segmentation fault waiting to happen.
One solution would be to allocate the object being tracked with std::shared_ptr, and to distribute std::weak_ptr:s instead of plain pointers to any classes needing to refer to the object. This way the interested parties can simply check if the tracked object still exists by calling std::weak_ptr::expired() or by checking if the shared_ptr returned by std::weak_ptr::lock() is equal to nullptr. However this approach is not without drawbacks:
- The objects being tracked are forced to be dynamically allocated with
std::shared_ptr, even when shared ownership is not really required. - Calling
std::weak_ptr::lock()->/*class*/./*member*/everywhere is cumbersome and causes sizeable performance overhead. - The objects being tracked are not stored contiguously in memory which hurts cache performance.
This led me to experiment with different approaches, ultimately resulting in a system implemented as a generic container:
- For each inserted object, the container returns a handle. The handle can be used as a key for accessing or removing the inserted object, or it can be tested for validity.
- The returned handle is permanently bound to the inserted object, and while removing the object results in an expired handle the handle can still be safely tested for validity, even after millions of other objects have been inserted and removed.
- The elements are stored contiguously in memory, and the container acts like a memory pool, only allocating more storage if no destroyed elements remain to be reused.
- Dereferring a handle involves just a pointer addition and optionally a comparison as a validity check.
- The container supports assignment. The assignment causes any handles to the container being assigned from to become valid handles to the container being assigned to. Handles to the original container become invalid and using them will result in undefined behaviour. Copy construction is also supported, with the same rules as assignment.
- The container is not thread safe.
Usage example:
struct Person
{
Person(const std::string &name)
: name(name)
{
std::cout << name << " was born\n";
}
~Person()
{
std::cout << name << " died\n";
}
Person& operator=(const Person &other)
{
std::cout << name << " was renamed " << other.name << "\n";
name = other.name;
return *this;
}
void receivePayment(int amount)
{
std::cout << name << " was paid $" << amount << "\n";
}
std::string name;
};
Container<Person> world;
struct Company
{
void hire(Container<Person>::Handle employee){employees.insert(employee);}
void fire(Container<Person>::Handle employee){employees.erase(employee);}
void payEmployees()
{
std::cout << "paying employees...\n";
std::vector<Container<Person>::Handle> deadEmployees;
for(auto &person : employees)
{
if(world.isExpired(person))
deadEmployees.push_back(person);
else
world[person].receivePayment(1200);
}
for(auto &person : deadEmployees)
fire(person);
std::cout << "...done.\n\n";
}
std::set<Container<Person>::Handle> employees;
};
int main()
{
Company corp;
auto alice = world.emplace("Alice");
corp.hire(alice);
corp.hire(world.emplace("Bob"));
corp.payEmployees();
world.clear();
auto carlos = world.emplace("Carlos");
alice = world.emplace("Alice2");
corp.hire(alice);
corp.payEmployees();
world[alice] = world[carlos];
world.erase(carlos);
corp.hire(world.emplace("Dan"));
corp.payEmployees();
}
/* Program output:
Alice was born
Bob was born
paying employees...
Alice was paid $1200
Bob was paid $1200
...done.
Alice died
Bob died
Carlos was born
Alice2 was born
paying employees...
Alice2 was paid $1200
...done.
Alice2 was renamed Carlos
Carlos died
Dan was born
paying employees...
Carlos was paid $1200
Dan was paid $1200
...done.
Carlos died
Dan died
*/
Implementation:
#include <vector>
#include <utility> //std::pair
#include <algorithm> //std::sort
#include <memory> //required for placement new?
#include <cstdint> //uint32_t
#include <type_traits> //std::aligned_storage
template<typename T>
class Container
{
private:
using Element = typename std::aligned_storage<sizeof(T), alignof(T)>::type;
using InstanceId = uint32_t;
using ElementIndex = uint32_t;
public:
struct Handle
{
ElementIndex index;
InstanceId id;
bool operator>(const Handle &other) const
{
if(index != other.index)
return index > other.index;
else
return id > other.id;
}
bool operator<(const Handle &other) const
{
if(index != other.index)
return index < other.index;
else
return id < other.id;
}
bool operator==(const Handle &other) const
{
return(index != other.index) ? false : id == other.id;
}
bool operator!=(const Handle &other) const
{
return(index != other.index) ? true : id != other.id;
}
};
Container()
{ }
Container(const Container &other)
{
*this = other;
}
~Container()
{
this->clear();
}
//The assignment operator destroys all elements and subsequently constructs
//..new elements as copies of the elements in the other vector. Using old
//..handles after an assignment causes undefined behaviour. Any handles to
//..the other container become valid handles to this container.
Container &operator=(const Container &other)
{
//destroy all current elements
clear();
//reallocate storage, copy instance IDs, and copy the expired vector.
dataByIndex_.resize(other.dataByIndex_.size());
idsByIndex_ = other.idsByIndex_;
expiredElements_ = other.expiredElements_;
//copy construct every element except for expired ones.
std::vector<ElementIndex> temp = expiredElements_;
std::sort(temp.rbegin(), temp.rend());
for(ElementIndex n = 0; n < dataByIndex_.size(); n++)
{
if(temp.empty())
new(static_cast<void*>(&dataByIndex_[n]))
T(other[Handle{n, 0}]);
else
{
if(n == temp.back())
temp.pop_back();
else
new(static_cast<void*>(&dataByIndex_[n]))
T(other[Handle{n, 0}]);
}
}
return *this;
}
//operator[] returns a reference to the object pointed by the handle,
//..with NO VALIDITY CHECKS being performed.
T& operator[](Handle handle)
{
return static_cast<T&>(
*static_cast<T*>(static_cast<void*>(
&dataByIndex_[handle.index]
))
);
}
const T& operator[](Handle handle) const
{
return static_cast<const T&>(
*static_cast<const T*>(static_cast<const void*>(
&dataByIndex_[handle.index]
))
);
}
//find returns a pointer to the object pointed by the handle. If the
//..handle is invalid find returns a nullptr.
T* find(Handle handle)
{
if(handle.id == idsByIndex_[handle.index])
{
return static_cast<T*>(static_cast<void*>(
&dataByIndex_[handle.index]
));
}
else
return nullptr;
}
const T* find(Handle handle) const
{
if(handle.id == idsByIndex_[handle.index])
{
return static_cast<const T*>(static_cast<const void*>(
&dataByIndex_[handle.index]
));
}
else
return nullptr;
}
//Test a handle for validity.
bool isExpired(Handle handle) const
{
return handle.id != idsByIndex_[handle.index];
}
//Emplace constructs a new T instance with the given parameters, and
//..returns a handle. The handle is guaranteed to be unique to this
//..specific entry, and can be tested for validity indefinitively.
template<typename ... Args>
const Handle emplace(Args&& ... args)
{
ElementIndex index = allocateObject();
new(static_cast<void*>(&dataByIndex_[index]))
T(std::forward<Args>(args) ...);
return Handle {index, idsByIndex_[index]};
}
//insert copy constructs a new T instance, and returns a handle to the
//..new instance. The handle is guaranteed to be unique to this specific
//..entry, and can be tested for validity indefinitively.
template<class P>
Handle insert(P &&original)
{
ElementIndex index = allocateObject();
new(static_cast<void*>(&dataByIndex_[index]))
T(std::forward<P>(original));
return Handle {index, idsByIndex_[index]};
}
//size returns the number of elements.
size_t size() const
{
return dataByIndex_.size() - expiredElements_.size();
}
//capacity returns the size of the storage space currently allocated for
//..the container, expressed in terms of elements.
size_t capacity() const
{
return dataByIndex_.capacity();
}
//reserve reallocates the underlying vector if necessary to contain at
//..least enough space for the requested number of elements.
void reserve(size_t capacity)
{
dataByIndex_.reserve(capacity);
idsByIndex_.reserve(capacity);
}
//Erase destructs the entry pointed by the handle, performing a validity
//..check before doing so.
void erase(Handle handle)
{
if(handle.id == idsByIndex_[handle.index])
{
eraseByIndex(handle.index);
expiredElements_.push_back(handle.index);
}
}
//This destroys all elements in the container. The memory remain allocated
//..for future use. Handles to all objects become expired.
void clear()
{
//call the destructors of all objects, except for objects whose index
//..is present in the "expiredElements_" vector.
std::sort(expiredElements_.rbegin(), expiredElements_.rend());
for(ElementIndex n = 0; n < dataByIndex_.size(); n++)
{
if(expiredElements_.empty())
eraseByIndex(n);
else
{
if(n == expiredElements_.back())
expiredElements_.pop_back();
else
eraseByIndex(n);
}
}
//mark all indexes as expired
expiredElements_.clear();
for(ElementIndex n = 0; n < dataByIndex_.size(); n++)
expiredElements_.push_back(n);
}
private:
ElementIndex allocateObject()
{
ElementIndex index;
if(expiredElements_.empty())
{
idsByIndex_.emplace_back();
idsByIndex_.back() = 1; //IDs start from one, zero = invalid.
dataByIndex_.emplace_back();
index = dataByIndex_.size() - 1;
}
else
{
index = expiredElements_.back();
expiredElements_.pop_back();
}
return index;
}
void eraseByIndex(ElementIndex index)
{
static_cast<T*>(static_cast<void*>(&dataByIndex_[index]))->~T();
idsByIndex_[index]++;
}
std::vector<Element> dataByIndex_;
std::vector<InstanceId> idsByIndex_;
std::vector<ElementIndex> expiredElements_;
};
The implementation is (very much) still work in progress. Missing features include a optimized assignment operator, the ability to iterate trough elements (with iterators or otherwise) and perfect forwarding for the arguments of Container::insert() and container::emplace().
I would appreciate feedback on my usage of placement new, memory alignment, the usage of static_cast, general code quality and any cases of undefined behaviour.
