This post was initially written as an answer to someone working on a networked RPG with a certain structure, hence some of the language might be a little confusing or assume some context.

If you're reading this, you're probably thinking about storing entites in a networked game. It could be an RPG, a FPS, or some other game, but all games are distributed simulations of some sort, and will likely need a concept of entites for players, NPCs, and other simulated game objects.

I suggest you keep a set of all entities, rather than separate lists of projectiles, monsters, players, etc. If you do that, you pretty much have to use pointers (to an abstract base class) rather than objects.

You could derive all classes from Entity, and then have a factory for each class. The factory has a list of all objects of "its" class, which could be a map containing the actual object.

So you'd have something like:

class Interface {
  public:
    virtual char const * interfaceName() = 0;
    // "query" in the COM sense, not just a dynamic_cast<>
    virtual Interface * queryInterface( char const * name ) = 0;
};

class Entity : public Interface {
  public:
    virtual Pos pos() = 0;
    virtual Vel vel() = 0;
    virtual void addStateToNetworkPacket( NetworkPacket * p ) = 0;
};

class Player : public Entity {
  public:
    ...
};

class Bullet : public Entity {
  public:
    ...
};

class EntityFactory : public Interface {
  public:
    EntityFactory( char const * kind ) {
      factories_[kind] = this;
    }
    static Entity * makeEntity( char const * kind ) {
      if( factories_.find( kind ) != factories_.end() ) {
        return factories_[kind].makeEntity();
      }
      return 0;
    }
  protected:
    virtual Entity * makeEntity() = 0;
    static std::map< std::string, EntityFactory * > factories_;
};

class PlayerFactory : public EntityFactory {
  public:
    PlayerFactory() : EntityFactory( "Player" ) {}
    Entity * makeEntity() { ... }
  private:
    std::hash_map< PlayerID, Player > players_;
};

class BulletFactory {
  public:
    BulletFactory() : EntityFactory( "bullet" ) {}
    Entity * makeEntity() { ... }
  private:
    std::hash_map< BulletID, Bullet > bullets_;
};

Regarding the cost of creating and destroying entities, I'd be more worried about the network cost than the CPU cost. Entity lifetime needs to be somewhat reliable, because you don't want bullets that stay alive forever on some machine that lost a single packet :-)

Further, if you run collision detection on the server, this happens every pulse, which is rather more often than just creating/deleting entities, so the overhead of the entity inserts/deletes themselves is likely to be relatively small.

Last, it's easy to optimize the case of entity ID and entity creation/insertion. Create an array of size (say) 1024; then keep a "next free" ID. When you need to allocate, keep incrementing the ID, and calculate the array index as ID&1023. When the indes shows a free slot, stuff the ID in there and mark it allocated. Mapping from ID to entity is really cheap -- again, just mask ID by 1023. Any other power of two works as well; it's just a maximum cap on the number of allocated objects you can have.

Just because I have some downtime, here's the pattern I usually use (not tested, but sketched out):

template< class T, int N > FastFactory {
  public:
    FastFactory() {
    assert( !(N & (N-1)) );
      live_ = 0;
      nextId_ = 1;
      memset( items_, 0, sizeof( items_ ) );
    }
    ~FastFactory() {
      assert( live_ == 0 );
    }
    int makeNew() {
      // catch too small container in debug build
      assert( live_ < N );
      if( live_ == N ) return 0;
      while( item( next_ )->id_ ) {
        ++next_;
      }
      new( &item( next_ )->t_) ) T;
      item( next_ )->id_ = next_;
      ++live_;
      return next_;
    }
    void destroy( int id ) {
      assert( live_ > 0 );
      item( id )->t_.~T();
      item( id )->id_ = 0;
      --live_;
    }
  private:
    Item * item( int id ) {
      assert( id != 0 );
      Item * r = (Item *)storage_[id & (N-1)];
      assert( r->id_ == 0 || r->id_ == id );
      return r;
    }
    struct Item {
      int id_;
      T t_;
    };
    char storage_[N][sizeof(Item)];
};