store many of relation 1:1 between various type of

问题:

I have 300+ classes. They are related in some ways.

For simplicity, all relation are 1:1.
Here is a sample diagram.

(In real case, there are around 50 relation-pairs.)

Note: For some instances, some relation may not exist.
For example, some hens don't relate to any food.

Note2: No link = never, e.g. every egg doesn't relate to any cage.
Such relation will never be added/removed/queried.

Question:

How to store relation between them elegantly?
All 4 of my ideas (below) seem to have disadvantages.

Here is a related question but with 1:N and only 1 relation.

My poor solutions

These are semi-pseudo-codes.

Version 1 Direct

My first thought is to add pointer(s) to each other.

Chick.h:-

class Egg;
class Food;
class Chick{  Egg* egg; Food* food;}

Hen.h:-

class Egg; class Cage; class Food;
class Hen{ Egg* egg; Cage* cage; Food* food;}

It is very cheap to add/remove relation and query, e.g. :-

int main(){
    Hen* hen;    ...    Egg* egg=hen->egg;
}

It works good, but as my program grow, I want to decouple them.
Roughly speaking, Hen.h should not contain word Egg, and vice versa.

There are many ideas, but none seems very good.
I will show a brief snippet for each work-around then summarizes pros & cons at the end of question.

Version 2 Hash-map

Use std::unordered_map.
It becomes a bottle neck of my program. (profiled in release mode)

class Egg{}; class Hen{};  //empty (nice)
.....
int main(){
    std::unordered_map<Hen*,Egg*> henToEgg;
    std::unordered_map<Egg*,Hen*> eggToHen;
    ....
    Hen* hen;    ...    Egg* egg=henToEgg[hen];
}

Version 3 Mediator-single

Store every relation in a single big mediator for every entity.
Waste a lot of memory for empty slots (e.g. Egg has henFood_hen slot).
Total waste = type-of-relation-pair*2*4 bytes (if run at 32 bits) in every entity.

class Mediator {
    Egg* eggHen_egg=nullptr;
    Hen* eggHen_hen=nullptr;
    Hen* henFood_hen=nullptr;
    Food* henFood_food=nullptr;
    //... no of line = relation * 2
};
class Base{public: Mediator m;};
class Egg : public Base{};  //empty (nice)
class Hen : public Base{}; 
int main(){
     Hen* hen;    ...    Egg* egg=hen->eggHen_egg;
}

Version 4 Mediator-array (similar as 3)

Try to standardize - high flexibility.

class Mediator {
    Base* ptrLeft[5];
    Base* ptrRight[5];
};
class Base{public: Mediator m;};
class Egg : public Base{};  //empty (nice)
class Hen : public Base{}; 
int main(){
     enum RELA_X{RELA_HEN_EGG,RELA_HEN_CAGE,RELA_EGG_CHICK, .... };
     Hen* hen;    ...    
     Egg* egg=hen->m.ptrRight[RELA_HEN_EGG]; 
     //^ get right of "hen-egg" === get "egg" from "hen"
     //^ can be encapsulated for more awesome calling
}

Pros & Cons

Green (+) are good. Red (-) are bad.

Edit: I am using Entity-Component for a 60fps game.
It is a persistent database : a single instance used for the entire life of a game.

Edit2: All of the relation are weak relation rather than is-a or strong std::unique_ptr ownership. (Thank Walter)

• A hen is in a cage.
  Some hens are not in any cage, and some cages are empty.
• A chick come from an egg.
  However, some chicks didn't come from any egg (they are just dropped from sky),
  and some eggs are not lucky enough to become chick.
• A hen and a chick are eating a (probably same) plate of food.
  Some food plates are just prepared but not served.

Edit3: Assign an integer id for each object can be a good idea.
(Thank Oliv, ahoxha, and Simone Cifani)

Edit4:: No need to provide a compilable code, just an essential part / concept is enough.

回答1:

Based on the requirements, if you have only one-to-one relations, then it sounds to me like a graph. In this case, if it is densely populated (there are many relations), I would use the matrix representation of the graph. In the tables below, I have associated numbers 0 through 4 to the entities (Hen, Cage, Food, Egg and Chick) respectively. If the relation Hen - Egg exists, then the matrix will have a 1 at the position matrix[0][3], if it doesn't then the value would be 0 (you can choose values of your choice to decide how to tell when the relation exists or doesn't). If the relations are undirected, then you only need one side of the matrix (the upper triangle, for example).

+---------------------------------+
| Hen | Cage | Food | Egg | Chick |
+---------------------------------+
|  0  |  1   |  2   |  3  |   4   |
+---------------------------------+

      0   1   2   3   4
    +--------------------+
  0 | 0 | 1 | 0 | 1 | 1  |
    +---+---+---+---+----+
  1 | 0 | 0 | 0 | 1 | 1  |
    +---+---+---+---+----+
  2 | 0 | 0 | 0 | 0 | 1  |
    +---+---+---+---+----+
  3 | 0 | 0 | 0 | 0 | 1  |
    +---+---+---+---+----+
  4 | 0 | 0 | 0 | 0 | 0  |
    +--------------------+

The downside of this solution hides in the memory usage, especially if the matrix contains a lot of 0's (relations that don't exist); you would be unnecessarily occupying a lot of space. In this case you may use the linked-list representation of the graphs.

回答2:

My suggestion:

1. Add a common base class.
2. Add a list of parents and children to the base class.
3. Add functions to add, remove, insert, query parents and children to the base class.
4. Add higher level non-member functions as needed.

---

class Base
{
   public:
      virtual ~Base();

      // Add "child" to the list of children of "this"
      // Add "this" to the list of parents of "child"
      void addChild(Base* child);

      // Remove "child" from the list of children of "this"
      // Remove "this" from the list of parents of "child"
      void removeChild(Base* child);                                 

      std::vector<Base*>& getParents();
      std::vector<Base*> const& getParents() const;

      std::vector<Base*>& getChildren();
      std::vector<Base*> const& getChildren() const;

   private:
    std::vector<Base*> parents_;
    std::vector<Base*> chilren_;    
};

Now you can implement higher level functions. E.g.

// Call function fun() for each child of type T of object b.
template <typename T>
void forEachChild(Base& b, void (*fun)(T&))
{
   for ( auto child, b.getChildren() )
   {
      T* ptr = dynamic_cast<T*>(child);
      if ( ptr )
      {
         fun(*ptr);
      }
   }
}

To query the unique egg from a hen, you could use a generic function template.

template <typename T>
T* getUniqueChild(Base& b)
{
   T* child = nullptr;
   for ( auto child, b.getChildren() )
   {
      T* ptr = dynamic_cast<T*>(child);
      if ( ptr )
      {
         if ( child )
         {
            // Found at least two.
            // Print a message, if necessary.
            return NULL;
         }

         child = ptr;
      }
   }

   return child;
}

and then use it as:

hen* henptr = <get a pointer to a hen object>;
egg* eggptr = getUniqueChild<egg>(*henptr);

回答3:

There must be some game-related logic behind your relations. Sometimes relations can be uni-directional, sometimes one-to-many etc. How to implement them highly depends on the logic and architecture.

1) typical is-a relation, e.g. your egg -> food case. Sounds like it's a simple inheritance, when Egg class should be derived from Food class

2) aggregation, e.g. hen -> egg case. Here you know that each hen can have (produce?) one or more eggs, this is part of your game logic and this info deserves to be hardcoded, for convenience, readability and performance: e.g. hen.eggs.count(). In this case you know what (almost concrete) type is expected, so declaration looks like

class Hen:
    List<Egg> eggs;

I'm not sure decoupling here is beneficial as to use eggs you do need to know about Egg class.

3) abstract components. On the abstract level of a game engine, when you don't have any specific game logic (or don't want to use it). E.g. Unity3D Components, or Unreal Engine Actors. Their main purpose is to help you to organise your stuff in an hierarchy, so you can clone part of your game world (e.g. compound building consisting of many parts), move it, reorganise etc. You have a base class for these components and you can enumerate a component children or query a particular child by its name or some ID. This method is abstract and helps to decouple game engine logic from a particular game logic. It doesn't mean it's applicable only for re-usable game engines. Even games that were built from scratch not using a 3rd-party game engines usually have some "game engine" logic. Usually such component model involves some overhead, e.g. cage.get_all_components("hen").count() - much more typing, less readable and there're some runtime overhead to enumerate only hens and count them.

class Component:
    List<Component> children;

As you can see here you don't have any dependencies between classes that derive from Component. So ideally dealing with children you don't need to know their concrete type and abstract Component is enough to do generic things like to specify a place in your game world, delete or re-parent it. Though on practice it's common to cast it to a concrete type, so decoupling here is just to separate game engine logic from game logic.

It's OK to combine all three methods.

回答4:

There is and can be no good answer to this question, since your algorithm is not known. What can be said in general, is that you want locality on your data and indirection is always a way to break it.

If you have an algorithm, that works on hens, you want them to be packed as closely as possible and ideally to be linear in memory, for the maximum cache hit rate.

If your algorithm needs to work on the relation, between hens and eggs. They need to be local. This can not be achieved by saving them as pointers in the hens, but you need an array of all hen <-> egg relation.

You see, it relly depends on what you intend to do. If you really aim to gain high permance, you have to prevent deep indiretion. Every pointer, you try to resolve may trash a cache line. If your cpu, is only chasing them down, the performance will be very low.

回答5:

I followed an approach similar to that of R Sahu to create a raw persistence library. In my implementation each entity must implement a base interface, called IEntity. The entity basically contains a vector of fields, represented by the interface IField, like follows:

typedef shared_ptr<IField>  field_ptr;
typedef vector<field_ptr> fields_vec;

class IEntity
{
public: 

    virtual string const& getEntityName() = 0;
    virtual bool allowDuplicates() = 0;
    virtual fields_vec const& getFields() = 0;
    virtual void setFieldValue(string fieldName, string fieldValue) = 0;
    //callback is called after queries to fill the queryResult map (fieldName, fieldValue)
    virtual void callback(map<string, string> queryResult) = 0;
};

class IField
{
public:
    typedef enum
    {
        INTEGER,
        FLOAT,
        REAL,
        NUMERIC,
        DATE,
        TIME,
        TIMESTAMP,
        VARCHAR
    } Type;

    virtual string const&  getName()              const = 0;
    virtual Type           getType()              const = 0;
    virtual string const&  getValue()             const = 0;    
    virtual bool           isPrimaryKey()         const = 0;
    virtual bool           isForeignKey()         const = 0;
    virtual bool           isUnique()             const = 0;
    virtual bool           isAutoIncrement()      const = 0;
    virtual bool           isNotNull()            const = 0;
    virtual int            getVarcharSize()       const = 0;
    virtual void           setValue(string value)       = 0;
    // Manage relations
    virtual IEntity* const getReferenceEntity()   const = 0;
    virtual string const&  getReferenceField()    const = 0; 
};

class CField : 
    public IField
{
public:
    CField(string name, Type type, bool primaryKey, bool unique, bool autoincrement, 
        bool notNull = false, int varcharSize = 0)
    {
        ...
    }

    CField(string name, Type type, IEntity* const referenceEntity, string const& referenceField,
        bool notNull = false, int varcharSize = 0)
    {
        ...
    }

    ...
};

Then, I have an entity manager that provides basic persistence functions:

class CEntityManager
{
public:
    CEntityManager();
    virtual ~CEntityManager();

    //--------------------------------------------//
    //Initializes db and creates tables if they not exist 
    bool initialize(string sDbName, vector<shared_ptr<IEntity>> const& entities);

    //--------------------------------------------//
    //Returns a shared_ptr instance of IField   
    field_ptr createField(string name, IField::Type type,
        bool primaryKey = false, bool unique = false, bool autoincrement = false, bool notNull = false, int varcharSize = 0);

    //--------------------------------------------//
    //Returns a shared_ptr instance of IField, 
    //When the field represents a foreign key, 'referenceField' specifies the column referenced to the 'referenceEntity'
    // and 'updateBy' specifies the column of the referenceEntity to check for update.
    field_ptr createField(string name, IField::Type type,
        IEntity* const referenceEntity, string referenceField, string updateBy, bool notNull = false, int varcharSize = 0);

    //--------------------------------------------//
    //Begin a new transaction
    void beginTransaction();

    //--------------------------------------------//
    //Commit query to database
    bool commit();

    //--------------------------------------------//
    //Persists an entity instance to db
    void persist(IEntity * const entity);

    //--------------------------------------------//
    template <class T>
    vector<shared_ptr<T>> find(vector<WhereClause> restrictions)

    //--------------------------------------------//
    //Removes one or more entities given the specified conditions
    void remove(string const& entityName, vector<WhereClause> restrictions);
};

class WhereClause
{
public:
    typedef enum
    {
        EQUAL,
        NOT_EQUAL,
        GREATER_THAN,
        LESS_THAN,
        GREATER_THAN_OR_EQUAL,
        LESS_THAN_OR_EQUAL,
        BETWEEN,
        LIKE,
        IN_RANGE
    } Operator;

    string fieldName;
    string fieldValue;
    Operator op;
};

The PROs of this solution are reusability, high abstraction level and ease of changing DB engine.
The CONs is that it will be slower with respect to a direct solution
However I use it with sqlite on a db of a thousand of records with time of response in the range of 100 - 600 ms, which is acceptable to me.

In your case you will have something like:

class Egg: 
    public IEntity
{
public:
    Egg()
    {
        m_fields.push_back(shared_ptr<CField>(new CField("Id", IField::INTEGER, ...));
        // add fields
    }

private:
    fields_vec m_fields;
};

class Hen : 
    public IEntity
{
public:
    Hen()
    {
        m_fields.push_back(shared_ptr<CField>(new CField("Id", IField::INTEGER, ...));
        // add fields

        //here we add a field which represent a reference to an Egg record through the field 'Id' of Egg entity
        m_fields.push_back(shared_ptr<CField>(new CField("EggId", IField::INTEGER, dynamic_cast<IEntity*> (m_egg.get()), string("Id")));
    }

private:
    fields_vec m_fields;
    unique_ptr<Egg> m_egg;        
};

Then, you can get your Hen record, containing its Egg reference, from the EntityManager

vector<WhereClause> restrictions;
restrictions.push_back(WhereClause("Id", idToFind, EQUALS));

vector<shared_ptr<Hen>> vec = m_entityManager->find<Hen>(restrictions);

This example represents a 1:1 relation between Hen and Egg. For a 1:N relation you can invert the representation and put a reference of Hen in Egg

回答6:

You could have each class contain a vector of strings that they accept upon creation of the class if the associations are known ahead of time. You could also add an update method that would update this container of names if more are discovered later. If the update function to update the list has been called and the class's container of names has been changed then the function also needs to have the class update itself with the proper class associations or relationships.

Each class would need these elements at minimum and for storing different types into a single container will require the use of a common non functional abstract base class with some purely virtual methods.

I'm using 2 classes that are derived from a common base interface for my example and the Primary class is named to represent the class that is having the relationship assigned to where the Associate class is the class is the delegated class that is being assigned to give the primary class that link of association.

class Base {
protected:
    std::vector<std::string> vRelationshipNames_;
    std::vector<std::shared_ptr<Base> vRelationships_;

public:
    Base(){}
    virtual ~Base(){}
    virtual void updateListOfNames( std::vector<std::string> newNames );
};

class Primary : Base {
private:
    std::string objectName_;
public:
    // Constructor if relationships are not known at time of instantiation.
    explicit Primary( const std::string& name );         
    // Constructor if some or all relationships are known. If more are discovered then the update function can be used.
    Primary( const std::string& name, std::vector<std::string> relationshipNames );

    // Add by const reference
    void add( const Base& obj );

    // Remove by const reference or by string name.
    void remove( const Base& obj );
    void remove( const std::string& name );

    // If needed you can even override the update method.
    virtual void updateListOfNames( std::vector<std::string> newNames ) override;
};

// Would basically have similar fields and methods as the class above, stripped them out for simplicity.
class Associate : Base {
    std::string objectName_;
};

We can then use a function template that takes two class objects to search to see if the Associate Object is in the list of names of the Primary Object

template <class T, class U>
T& setRelationshipBetweenClasses( class T& primaryObject, class U& associateObject ) {
    // Search through primaryObject's list of names to see if associate class is listed
    // If it is not then return from function otherwise, we need to search to see
    // if this class was already added to its list of shared pointers. 

    // If it is not found then add it by calling the Primary's add function

    // Then we also need to call the Associates add function as well by 
    // passing it a const reference to the Primary class this way both
    // classes now have that relationship. 

    // we also return back the reference of the changed Primary object.      
}

EDIT

The OP made a comment about using string and being slow; I used string here in the pseudo code just for clarity of understanding, you can replace the std::string with an unsigned int and just use a numeric ID. It will do the same and should be fairly efficient.

EDIT

For the OP -

A common interface of classes without definitions and implementations but their declarations might look something like this:

Example.h

#ifndef EXAMPLE_H
#define EXAMPLE_H

struct CommonProperties {
    std::string name_;
    unsigned int id_;

    // Default
    explicit CommonProperties() : name_(std::string()), id_(counter_) {
        counter_++;
    }
    // Passed In Name
    explicit CommonProperties(const std::string& name) : name_(name), id_(counter_) {
        counter_++;
    }

private:
    static unsigned int counter_;
};


class BaseObject {
protected:
    CommonProperties properties_;
                                                             // Sizes of Both Containers Should Always Match!
    std::vector<std::shared_ptr<BaseObject>> sharedObjects_; // Container of Shared Names
    std::vector<unsigned int> sharedObjectIDs_;              // Container of Shared IDs

public:
    explicit BaseObject(const std::string& strName) {
        properties_.name_ = strName;
    }

    // Virtual Interface for Abstract Base Class    
    virtual void add(const BaseObject& obj, const std::string& strName, const unsigned int id) = 0; // Purely Virtual Each Derived Class Must Implement
    virtual void update(const BaseObject& obj, const std::string& strName, const unsigned int id) = 0; // Also purely virtual
    virtual void remove(const std::string& strName) {} // Used string method to remove
    virtual void remove(const unsigned int id) {} // Use ID method to remove

    // Get Containers
    std::vector<std::shared_ptr<BaseObject>> getObjects() const { return sharedObjects_; }
    std::vector<unsigned int> getIDs() const { return sharedObjectIDs_; }
};


class Primary : public BaseObject {
// Member Variables
public:
protected:
private:

// Constructors, Destructor and Methods or Functions
public:
    explicit Primary(const std::string& strName) : BaseObject(strName) {
    }

    // Must Have Purely Virtual
    void add(const BaseObject& obj, const std::string& strName, const unsigned int id) override {
        // Algorithm Here
    }

    void update(const BaseObject& obj, const std::string& strName, const unsigned int id) override {
        // Algorithm Here
    }

    // other public methods;
protected:
private:
};

class Associate : public BaseObject {
    // Member Variables:
public:
protected:
private:

    // Constructors, Destructors and Methods or Functions
public:
    explicit Associate(const std::string& strName) : BaseObject(strName) {
    }

    // Must Have Purely Virtual
    void add(const BaseObject& obj, const std::string& strName, const unsigned int id) override {
        // Algorithm Here
    }

    void update(const BaseObject& obj, const std::string& strName, const unsigned int id) override {
        // Algorithm Here
    }

protected:
private:

};    

#endif // EXAMPLE_H

Example.cpp

#include "stdafx.h"  // Used for common std containers and algorithms as well as OS and system file includes.
#include "Example.h"

unsigned int CommonProperties::counter_ = 0x00;

With this example I have both a string and ID. I do this for several reasons; if you ever need to write to a readable file, or to print to the screen or some other output device the contents or properties of this object I have string for human readability. The ability to search, remove and add by a string is available but for the sake of efficiency it should be done by the mechanics of the hidden engine that will instead automatically generate the IDs for you and use the ID system instead for faster searches, comparisons and removals.

For example let's say I generated 3 distinct objects that are of different classes: class1, class2, class3 their names and id's are set upon creation. I didn't show how to automatically generate a unique string with a base set of characters for a specific class and then append to that string a unique value each time that class is instantiated, but that is what I typically do if a name is not supplied. Supplying a name is optional and name generation is normally automatic. The table of the different classes and their properties name field would look like this:

// CLASS NAME  |   ID
    "class1"   |   0x01
    "class2"   |   0x02
    "class3"   |   0x03

Now what also makes this setup powerful is the fact that you can have multiple instances of the same class but each has their own unique name. Such as This

class PickupTruck {};

// Table of Names & IDS similar to above:
   "Chevy"     |  0x04
   "Dodge"     |  0x05
   "Ford"      |  0x06
   "GMC"       |  0x07

Now if you want to distinguish between the name of the actually class and the name of the actual object description; just make sure that you add a std::string as a protected member to the Base or Super class that these classes derive from. This way that name would represent the string representation of that class type, where the property sheet name would be the actual descriptive name of that object. But when doing the actual searches and removals from your containers, using ids for simple loops, counters and indexing are quite efficient.