store many of relation 1:1 between various type of objects : decoupling & high performance

Question

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.

Answer 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.

Answer 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);

Answer 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.