Memory container management issue - elements require inheritance

Question

I am developing a container for managing memory, keeping in mind performance and ease of use, especially for game development projects. Here it is in it the current state.

I will extract the most important parts from the source.

// Uptr is a typedef for std::unique_ptr class MemoryManageable { bool alive{true}; public: bool isAlive() const { return alive; } }; template<typename T> struct Deleter { bool operator()(const Uptr<T>& mItem) const { return !mItem->isAlive(); } }; template<typename T> class MemoryManager { // T is the type of items being stored and must inherit MemoryManageable std::vector<Uptr<T>> items; std::vector<T*> toAdd; // will be added to items on the next refresh() call Deleter<T> deleter; void refresh() { items.erase(std::remove_if(std::begin(items), std::end(items), deleter), std::end(items)); for(const auto& i : toAdd) items.push_back(Uptr<T>(i)); toAdd.clear(); } void clear() { items.clear(); toAdd.clear(); } // Del sets alive to false, so that the item will be deleted and deallocated on the next refresh() call void del(T& mItem) { mItem.alive = false; } template<typename TType, typename... TArgs> TType& create(TArgs&&... mArgs) { /* creates a new TType* (derived from T) and puts it in toAdd */ } template<typename... TArgs> T& create(TArgs&&... mArgs) { return create<T, TArgs...>(std::forward<TArgs>(mArgs)...); } } 

Here you can see the real use.

The desired use looks something like this:

 struct Entity : public MemoryManageable { Manager& manager; void destroy() { manager.del(*this); } ... } struct Mnnager { MemoryManager<Entity> mm; void del(Entity& mEntity) { mm.del(mEntity); } ... } Manager::update() { mm.refresh(); // entities with 'alive == false' are deallocated, and entities in 'mm.toAdd' are added to 'mm.items' for(auto& entity : mm) entity->update(); // entities 'die' here, setting their 'alive' to false } 

This insert-delayed construction with refresh() has several advantages:

• Fast
• An entity can be "killed" even if it is already dead.
• Entities can be created from other objects, since they do not receive directly stored elements until populate() is called.

However, I would really like it if there was no need to inherit MemoryManageable , and if there was a more elegant way to delete entities.

• Is there a way to make the MemoryManager handle the MemoryManager bool internally without inheriting from the MemoryManageable and, most importantly, without any overhead?
• Is there a more elegant way that you could use to delete items processed by the MemoryManager ?

Ideally, items processed by the MemoryManager do not know anything about this.

---

Usage example: in gamedev, it is usually that an object is destroyed during its update. Consider an "Enemy" object with a member int life: if(life <= 0) this->destroy(); - this will happen easily during the update cycle, and if an object is immediately deleted from the Manager upon destruction, it causes problems with the cycle and other objects that point to a dead entity.

Answer 1

The answers provided did not satisfy me, so I decided to keep the required solution for inheritance. How annoying it is, it is effective (at no additional cost of execution time) and easy to implement / maintain.

Current Implementation: SSVUtils / MemoryManager / MemoryManager.h

Answer 2

The first thing to say: I do not really like C ++ 11, so there may be some kind of syntax error in the code that I wrote, but this logic matters.

If I understand your question, you just want to be able to add and remove elements from the container asynchronously without knowing their state. In this case, you can use std::map< std::unique_ptr< Elem >, bool > to process the state of the elements: true = alive, false = dead.

Memory class

fields:

• std::vector< T * > m_toAdd , a vector with elements not yet added;
• std::map< std::unique_ptr< T >, bool > m_items , a map with each managed item and the bool flag

methods:

• add() , which adds a new element to the vector m_toAdd ;
• del() , which marks the item to be deleted in m_items using its flag;
• refresh() , which removes dead elements and commits the m_toAdd ad live elements to m_items , then clears the vector

Class elem

fields:

• MemoryManager & m_manager , a link to its memory manager;

methods:

• Elem() , ctor, which calls m_manager::add() ;
• del() , which calls m_manager::del() .

Creature

When an Elem is created, it automatically adds itself to its memory manager, which adds it to its m_toAdd vector, and then when everything is updated, those Elem in this vector are passed to std::map paired with true boolean (originally designated as live) .

Delete

When deleting Elem it calls the manager's del() method, which simply marks it dead in its std::map , and then, when everything is updated, each Elem in the manager is marked dead as deleted, and the vector m_toAdd is cleared.

(I also recommend that you use std::enable_shared_from_this to handle ptr better, but you will need to use std::shared_ptr rather than std::unique_ptr , but that can't be so bad.)

My suggestion is something like:

 template< class T > class MemoryManager { typedef std::unique_ptr< T > unique_t; typedef std::map< unique_t, bool > map_t; typedef std::pair< unique_t, bool > pair_t; typedef std::vector< T * > vector_t; public: void add(T * item) { m_toAdd.push_back(item); } void remove(T & item) { typename map_t::iterator it = m_items.find(item); if (it != m_items.end() )(* it).second = false; } void refresh() { // clear dead typename map_t::iterator it = m_items.begin(); while ((it = std::find_if(it, m_items.end(), isDead)) != m_items.end()) { m_items.erase(it++); } // add new for(T & item : m_toAdd) { m_items.insert(std::make_pair(unique_t(item), true)); } m_toAdd.clear(); } void clear() { m_items.clear(); m_toAdd.clear(); } protected: bool isDead(pair_t itemPair) { // true = alive, false = dead return itemPair.second; } private: map_t m_items; vector_t m_toAdd; }; class Entity { public: Entity(MemoryManager< Entity > & manager) : m_manager(manager) { m_manager.add(this); } void die() { m_manager.remove(this); } private: MemoryManager< Entity > & m_manager; }; 

NOTE : the code is not verified and, of course, broken, the logic is important!

Answer 3

Well, I'm not quite sure if this is what you want to do, but try it ... Entity will still require the destroy / isdead function, because, as I understand it, you want to explicitly control your life from the object itself.

 class Entity{ public: void destroy(){ dead = true; } bool isDead(){ return dead; } private: bool dead{false}; }; struct EntityPred{ bool operator ()(const Entity* p){ return p->isDead(); } }; template<typename T, typename T_PRED> class MemoryManager{ // Deletion and insertion is faster to a list than a vector // since deletion of entites[0] requires v.size() - 1 copy constructions. // If you really worry about performance (I wouldn't until I have profiled) // you can use a memory pool allocator for this. std::list<std::unique_ptr<T> > entities; // Buffering up many objects that are deleted sequentially is // faster in a vector, less calls to new/delete. // But, a pool backed list might be even faster if you're micro optimizing. std::vector<T*> toAdd; public: void add(T* p){ toAdd.push_back(p); } void refresh(){ for(auto it = entities.begin(); it != entities.end();){ if( T_PRED(it) ) it = entities.erase(it); else it++; } // Avoid growing the vector inside the loop since we know the size. entities.reserve(entities.size() + toAdd.size()); for(auto it : toAdd){ entities.push_back(std::unique_ptr<T>(*it)); } toAdd.clear(); } }; MemoryManager<Entity, EntityPred> mgr; 

The Entity class does not know about the manager and does not need any precautions when developing it, just make sure that EntityPred can determine whether t21 should be removed in any way.

Answer 4

This question tickled my brain to come up with a very ... interesting ... piece of code. Cue the applaus "And the Winner of 2013" (f) "Hack’s most awesome reward is ..." (warned you!)

The following code compiles and works as expected with GCC 4.7, there may be errors, and you can clean it up a bit ... But for the design of the Entity class used in the container, it is completely transparent, There are no pointers to managers, there are no "amideadyet" variables, etc. d.

Basically, I (ab) use the order of the calls to the destructor, inheriting the class from Entity using templates. When an object is deleted, the inherited class destructor is called while the object is still valid. It notifies the manager (whose derived class has a pointer) and steals the contents of Entity into another object, which will be identified as "deleted" for the manager until refresh() is called. Destruction of the original Entity continues, but all the expensive data members have been stolen by the move constructor, and destruction is successful without destroying our important data.

Enjoy :)

 #include <memory> #include <utility> #include <list> #include <string> #include <iostream> class Entity{ public: Entity(const std::string& msg){ m=msg;}; // Move constructor required Entity(Entity&& that){ std::swap(m, that.m); c = that.c; } // Should be virtual virtual ~Entity(){}; // Do this to release it. void suicide(){ delete this; } // Not needed, deleted for safety Entity(const Entity&) = delete; void operator = (const Entity&) = delete; void print(){ std::cout<<m<<" "<<c<<std::endl; c++; } private: std::string m; int c{0}; }; template<typename T> class MemoryManager; template<typename T> class MemoryObject{ public: MemoryObject(MemoryManager<T>* _mgr) : mgr(_mgr) {} MemoryObject(MemoryObject&& that){ mgr = that.mgr; } MemoryObject(const MemoryObject& that){ mgr = that.mgr; } virtual ~MemoryObject(){} void operator = (const MemoryObject&) = delete; bool isDead(){ return is_dead; } friend void swap(MemoryObject& a, MemoryObject& b){ std::swap(a.mgr, b.mgr); std::swap(a.is_dead, b.is_dead); } protected: bool is_dead; MemoryManager<T>* mgr; }; template<typename T> class LiveMemoryObject : public MemoryObject<T>, public T { public: template<typename... ARGS> LiveMemoryObject(MemoryManager<T>* _mgr, const ARGS&... args) : MemoryObject<T>(_mgr), T(args...) {} LiveMemoryObject(const LiveMemoryObject&) = delete; LiveMemoryObject(LiveMemoryObject&& other) = delete; virtual ~LiveMemoryObject(){ // Called when Entity did `delete this` but before it is destroyed, // The manager will move construct (swap) a DeadMemoryObject from *this // Effectively stealing the contents of Entity before it is destroyed. // So when this destructor returns, this object is pointing to a dummy Entity // which is destroyed inplace of the original. MemoryObject<T>::mgr->remove(this); } void operator = (const LiveMemoryObject&) = delete; }; template<typename T> class DeadMemoryObject : public MemoryObject<T>, public T { public: DeadMemoryObject() = delete; DeadMemoryObject(const DeadMemoryObject&) = delete; DeadMemoryObject(LiveMemoryObject<T>&& that) : MemoryObject<T>(that), T(static_cast<T&&>(that)) { MemoryObject<T>::is_dead = true; } virtual ~DeadMemoryObject(){ /* May you finally RIP Entity! */ } void operator = (const DeadMemoryObject&) = delete; }; template<typename T> class MemoryManager{ private: friend class LiveMemoryObject<T>; class Handle{ public: template<typename... ARGS> explicit Handle(MemoryManager* mgr, const ARGS&... args) { auto o = new LiveMemoryObject<T>(mgr, args...); data = o; ptr = o; } ~Handle(){ delete data; } T* operator -> (){ return ptr; } const T* operator -> () const { return ptr; } private: void ageData(){ auto p = new DeadMemoryObject<T>(std::move(*dynamic_cast<LiveMemoryObject<T>*>(data))); data = p; ptr = p; } friend class MemoryManager; MemoryObject<T>* data; // Memory owned by handle T* ptr; // ease of access to T* of data. }; typedef std::shared_ptr<Handle> HandlePtr; std::list<HandlePtr> items; std::list<HandlePtr> to_add; void remove(LiveMemoryObject<T>* p){ for(auto it = items.begin(); it != items.end(); ++it){ if( (*it)->data == p ){ (*it)->ageData(); break; } } } public: template<typename... ARGS> HandlePtr create(const ARGS&... args){ HandlePtr h{std::make_shared<Handle>(this, args...)}; to_add.push_back(h); return h; } void refresh(){ for(auto it = items.begin(); it != items.end();){ if((*it)->data->isDead()){ delete (*it)->data; (*it)->data = nullptr; (*it)->ptr = nullptr; it = items.erase(it); } else it++; } for(auto it : to_add){ items.push_back(it); } } }; int main(){ MemoryManager<Entity> mgr; auto e = mgr.create("Hello world!"); mgr.refresh(); (*e)->print(); // "Hello world! 0" (*e)->print(); // "Hello world! 1" (*e)->suicide(); // The object is still valid, we have not called refresh() yet to destroy it. (*e)->print(); // "Hello world! 2" mgr.refresh(); (*e)->print(); // Expected sig fault as object has been removed return 0; }