Re: [Boost-users] [Multi-index] how to create 1-n relation between multi index containers?

From: Alan M. Carroll (amc_at_[hidden])
Date: 2008-08-07 12:35:14

If I had this problem, I would do two things:

1) Convert the classes to support Boost.intrusive_ptr so that you can
easily share them. Luckily, there was a discussion on what it takes to
support that just a week or two ago on this list.

2) I would create a Boost.Multi_Index that stored pairs of intrusive_ptr,
one Group and one Server. For each group a server is in, store that pair.
Use two indices, one for group and the other for server.

Adding or removing a server from a group is simply adding or removing the
appropriate pair, which is easily found. equal_range on the appropriate
index answers the questions "what groups is this server in" and
"what servers are in this group".  If your groups get
large and you need more efficiency in determining whether a specific pair
is present, you could add a third index that is a composite of server,
group and search on that in such cases. Finding a server or a group is
easy, just find the first pair and get the intrusive_ptr out of that.
You'll have to use the functor style key access, rather than the member
one, because you have to reach through the pointer to the underlying
object.

As for an example, I have one that's sort of appropriate, a header only
implementation of a "Lexicon" class. It uses Boost.Multi_Index
to maintain a 1-N relationship between instances of type K and
std::string, analogous to your servers and groups. It's a bit different
in that it require the strings to be globally unique and doesn't use
intrusive_ptr, but it's self contained.  E-mail me if you'd like to
see the source (~700 lines).

At 07:28 AM 8/7/2008, you wrote:
> hi all
>
> a few weeks ago i came across multi index and now im using it very
> intensively in my linux application (using g++)
> the problem im facing more often is a situation like this:
>
> i have a structure using multi index for server's (for example)
> typedef struct server{
>     uint32_t ip,port;
>     std::string hostname;
> };
>
> and i have a groups structure
> typedef struct servergroup{
>     std::string groupname;
>     uint32_t groupid;
>     time_t sometimestamp;
>     uint32_t groupstate;
> //  std::vector<server> members;  // << could this
> be a multi_index?
> };
>
> what i need to do is create a relation between a group and it's members
> (servers)
> and thats what im not sure about how to achive using multi_index
>
> the reason for the relationship is that i need to create an index for
> queries like this:
> In which group is server X?
> or
> Which servers has Group X?
>
> The only possibility i see is by creating 1 structure which causes much
> memory overhead and
> updating is a bit of a problem, cause i would need a loop for updating
> the state of the group for every member, ...
>
> I also thought about using boost bimap, but im pretty unsure how?
> So anybody has a hint on this (including maybe a very small
> example)?
> im pretty sure its some kind of 'not see the wood for trees'
> problem
>
> thx for ur time
>
> Discover the new Windows Vista
>
> Learn more! 
> _______________________________________________
> Boost-users mailing list
> [e-mail]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users