Re: bimap: one to many

From: Gavin Lambert (boost_at_[hidden])
Date: 2020-03-12 22:39:20

On 13/03/2020 09:53, MM wrote:
> I want a collection to store a relationship N to M like so:
> 
> Item of type AÂ  Â  Â  Â  Â  Â  Â  Â  Â Item of type B
> A1Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  B1,B2,B3
> A2Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  B4
> A3Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  Â  B1
> 
> and I would like a convenient way to get from a A instance to the list 
> of B instances, and vice versa, from a given B instance to the list of A 
> instances.
> 
> At runtime, the A objects are created first, then a list of B objects is 
> created.
> Later, B objects get modified asynchronously and that modification need 
> to update the relevant A instances
> 
> what container to use?
> 
> boost::bimap< unordered_set<A*> ,  unordered_set<B*> >
> 
> ?

I don't think that'd work unless a B had some other means to find the 
set that includes it.

A relatively simple method would be to have each B store a weak_ptr<A> 
of its "owner".  Given that, there's a few different ways to model the 
relationship:

   1. An external unordered_map<shared_ptr<A>, unordered_set<shared_ptr<B>>>
   2. An external unordered_set<shared_ptr<A>> and each A has a 
unordered_set<shared_ptr<B>>
   3. One of the above but substitute vector for unordered_set if you do 
care about the order.

(Which of these makes more sense depends on your intended ownership 
relations and other factors.  Other things are also possible, of course.)

Given something like this, you can explore the whole graph from any one 
node easily enough.