c++ - 内存管理容器设计问题 - 项目需要继承

Question

我正在设计一个内存管理容器，考虑到性能和易用性，特别是对于游戏开发项目。这是它的当前状态。

我将从源代码中提取最重要的部分。

// 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)...); }
}

你可以在这里看到一个真正的用法。

所需的用法是这样的：

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 
}

这种延迟插入设计refresh()具有一些很大的优点：

它很快
一个实体即使已经死了也可以被“杀死”
实体可以从其他实体创建，因为它们不会直接存储在项目中，直到populate()被调用

但是，如果不需要继承MemoryManageable，并且如果有更优雅的删除实体的方法，我会很高兴。

有没有办法在内部MemoryManager处理alivebool 而不必继承MemoryManageable，最重要的是，没有任何性能开销？
有没有更优雅的方法可以用来删除由处理的项目MemoryManager？

理想情况下，由处理的项目MemoryManager应该对此一无所知。

示例用法：在游戏开发中，实体在更新期间被破坏是很常见的。考虑一个具有 int life 成员的“敌人”实体：if(life <= 0) this->destroy();- 在更新循环期间很容易发生这种情况，如果该实体在销毁时立即从 Manager 中删除，则会导致循环和其他指向死亡的实体出现问题实体。

score 3 · Accepted Answer

First thing to say: I'm not very fond of C++11, so there could be some syntax error in the code I wrote, but it's the logic that matters.

If I understood your question, you just want to be able to asynchronously add and delete items from a container, without those knowing of their state. In this scenario you can use a std::map< std::unique_ptr< Elem >, bool > to handle the state of items: true = alive, false = dead.

MemoryManager class

fields:

std::vector< T * > m_toAdd, a vector with not yet added items;
std::map< std::unique_ptr< T >, bool > m_items, a map with every item managed and a bool flag

methods:

add(), which adds a new item in the m_toAdd vector;
del(), which marks an item to be removed in m_items using its flag;
refresh(), which removes dead items and commits m_toAdd items ad alive in m_items, then clears the vector

Elem class

fields:

MemoryManager & m_manager, a reference to its memory manager;

methods:

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

Creation

When an Elem is created, it automatically add itself to its memory manager, which adds it to its m_toAdd vector, then when everything is refreshed, those Elems in this vector are passed in the std::map paired with a true boolean (initially marked as alive).

Deletion

When an Elem is to be deleted, it calls a del() method of its manager which simply marks it as dead in its std::map, then when everything is refreshed, every Elem in the manager flagged as dead is removed, and the m_toAdd vector is cleared.

(Also I reccomend you using std::enable_shared_from_this in order to better handle the ptr, but you'll have to use std::shared_ptr, not std::unique_ptr, but that could not 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 tested and certainly broken, the important thing is the logic!

score 0 · Accepted Answer

给出的答案并没有让我满意，所以我决定保留所需的继承解决方案。尽管它可能很烦人，但它很有效（没有额外的运行时成本）并且易于实现/维护。

当前实现：SSVUtils/MemoryManager/MemoryManager.h

score 0 · Accepted Answer

好的，我不完全确定这是你想要做的，但让我们试试这个......实体仍然需要销毁/isdead 函数，因为据我了解，你想从对象本身显式控制它的生命周期。

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;

该类Entity不了解管理器，在设计时不需要任何预防措施，只需确保EntityPred可以确定是否Entity应该以某种方式删除。

score 0 · Accepted Answer

这个问题让我的大脑发痒，想出了一段非常……有趣的……代码。掌声响起“而 2013 年“（f）最丑黑客奖”的获奖者是......“（你已经被警告了！）

以下代码在 GCC 4.7 中按预期编译和工作，可能存在错误，您可能需要稍微清理一下......但是对于 Entity 类的设计，在容器中使用是完全透明的。没有指向经理的指针，没有“amideadyet”变量等。

基本上，我（ab）通过Entity使用模板继承一个类来使用析构函数调用顺序。当实体被删除时，继承类的析构函数被调用，而实体仍然有效。它通知管理器（派生类有一个指向它的指针）并将 Entity 的内容窃取到另一个对象中，该对象将标识为“已删除”到管理器，直到refresh()被调用。原始数据的破坏Entity仍在继续，但所有昂贵的数据成员已被移动构造函数窃取，并且破坏成功完成，而不会破坏我们的重要数据。

享受：）

#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 R.I.P. 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;
}

c++ - 内存管理容器设计问题 - 项目需要继承

4 回答 4

MemoryManager class

Elem class

Creation

Deletion

Related

Reference