What is a good way to represent a many-to-many relationship between two classes?

Question

Let's say I have two object types, A and B. The relationship between them is many-to-many, but neither of them is the owner of the other.

Both A and B instances need to be aware of the connection; it's not just one way.

So, we can do this:

class A
{
    ...

    private: std::vector<B *> Bs;
}

class B
{
    private: std::vector<A *> As;
}

My question is: where do I put the functions to create and destroy the connections?

Should it be A::Attach(B), which then updates A::Bs and B::As vectors?

Or should it be B::Attach(A), which seems equally reasonable.

Neither of those feels right. If I stop working with the code, and come back after a week, I'm sure I won't be able to recall if I should be doing A.Attach(B) or B.Attach(A).

Perhaps it should be a function like this:

CreateConnection(A, B);

But making a global function seems undesirable also, given that it's a function specifically for working with only classes A and B.

Another question: if I run into this problem/requirement often, can I somehow make a general solution for it? Perhaps a TwoWayConnection class that I can derive from or use within classes that share this type of relationship?

What are some good ways to handle this situation... I know how to handle the one-to-many "C owns D" situation quite well, but this one is trickier.

Edit: Just to make it more explicit, this question doesn't involve ownership issues. Both A and B are owned by some other object Z, and Z takes care of all ownership issues. I'm only interested in how to create/remove the many-to-many links between A and B.

Answer 1

One way is to add a public Attach() method and also a protected AttachWithoutReciprocating() method to each class. Make A and B mutual friends so that their Attach() methods can call the other's AttachWithoutReciprocating():

A::Attach(B &b) {
    Bs.push_back(&b);
    b.AttachWithoutReciprocating(*this);
}

A::AttachWithoutReciprocating(B &b) {
    Bs.push_back(&b);
}

If you implement similar methods for B, you won't have to remember which class to call Attach() on.

I'm sure you could wrap that behavior up in a MutuallyAttachable class that both A and B inherit from, thus avoiding repeating yourself and scoring bonus points on Judgement Day. But even the unsophisticated implement-it-in-both-places approach will get the job done.

Answer 2

Is it possible for the relationship itself to have additional properties?

If so, then it should be a separate class.

If not, then any reciprocating list-management mechanism will suffice.

Answer 3

Usually when I get into situations like this that feel awkward, but I can't quite tell why, it's because I'm trying to put something in the wrong class. There's almost always a way to move some functionality out of class A and B to make things more clear.

One candidate for moving the association to is the code that creates the association in the first place. Maybe instead of calling attach() it simply stores a list of std::pair<A, B>. If there are multiple places creating associations it can be abstracted out into one class.

Another candidate for a move is the object that owns the associated objects, Z in your case.

Another common candidate for moving the association to is the code that is frequently calling methods on A or B objects. For example, instead of calling a->foo(), which internally does something with all associated B objects, it already knows the associations and calls a->foo(b) for each one. Again, if multiple places call it, it can be abstracted into a single class.

Lots of times the objects that create, own, and use the association happen to be the same object. That can make the refactoring very easy.

The last method is to derive the relationship from other relationships. For example, brothers and sisters are a many-to-many relationship, but rather than keeping a list of sisters in the brother class and vice versa, you derive that relationship from the parental relationship. The other advantage of this method is that it creates a single source of truth. There's no possible way for a bug or runtime error to create a discrepancy between the brother, sister, and parent lists, because you only have the one list.

This kind of refactoring isn't a magic formula that works every time. You still have to experiment until you find a good fit for each individual circumstance, but I've found it to work about 95% of the time. The remaining times you just have to live with the awkwardness.

Answer 4

If I were implementing this, I would put Attach in both A and B. Inside of the Attach method, I would then call Attach on the object passed in. That way you can call either A.Attach(B) or B.Attach(A). My syntax may not be correct, I haven't used c++ in years:

class A {
  private: std::vector<B *> Bs;

  void Attach (B* obj) {
    // Only add obj if it's not in the vector
    if (std::find(Bs.begin(), Bs.end(), obj) == Bs.end()) {
      //Add obj to the vector
      Bs.push_back(obj);

      // Attach this class to obj
      obj->Attach(this);
    }
  }    
}

class B {
  private: std::vector<A *> As;

  void Attach (A* obj) {
    // Only add obj if it's not in the vector
    if (std::find(As.begin(), As.end(), obj) == As.end()) {
      //Add obj to the vector
      As.push_back(obj);

      // Attach this class to obj
      obj->Attach(this);
    }
  }    
}

An alternate method would be to create a 3rd class, C which manages a static list of A-B pairings.

Answer 5

Since you're putting C++11 on the candidate list... Take a look at smart pointers.
http://www2.research.att.com/~bs/C++0xFAQ.html#std-unique_ptr

They appear to provide more ways to tackle this exact problem.

Edit: A snippet of what I thought was relevant to the Q:

weak_ptr

Weak pointers are often explained as what you need to break loops in data structures managed using shared_ptrs. I think it is better to think of a weak_ptr as a pointer to something that you need access to (only) if it exists, and may get deleted (by someone else), and must have its destructor called after its last use (usually to delete anon-memory resource)