Re: [boost] [multi_index] container for groups?

From: Matias Capeletto (matias.capeletto_at_[hidden])
Date: 2007-07-17 10:03:23

On 7/17/07, Janek Kozicki <janek_listy_at_[hidden]> wrote:
> Hello,
>
> I just wanted to check grounds before I get to implementing this
> (don't know when ;). I want a container that allows to assign several
> groups (sth. like std::set<int> ) to id numbers (int). Let's say that I
> have following id numbers: 1,3,5,7. And I assign that 1 belongs to
> groups 1,2,3. Then I say that 2 belongs to groups 2,3,4. And 5
> belongs to groups 2,4 and finaly 7 belongs to groups 1,4. So it would look like:
>
> id: groups
> 1 : 1,2,3
> 3 : 2,3,4
> 5 : 2,4
> 7 : 1,4
>
> Using this container I want to iterate in all possible ways:
>
> - iterate over all ids from start to end - answer: 1,3,5,7
> - iterate over all ids which belong to group 3 - answer: 1,3
> - iterate over all groups from start to end - answer: 1,2,3,4
> - iterate over all groups in which id 5 appears - answer: 2,4
>
> I guess that this should be easy with multi_index, since that's what
> for they were designed :-)

Yep, it is easy with MultiIndex. But this is exactly the kind of
things Boost.Bimap was designed on top of Boost.MultiIndex.

http://www.drivehq.com/web/matias.capeletto/bimap/doc/html/index.html

In your case:

  struct id {};
  struct group {};

  typedef bimap<

     tagged< int, id >,
     multiset_of< tagged< int, group > >

  > bm_type;

  ...

  bm_type bm;

  assing::insert( bm )
     ( 1, 1 ) ( 2, 1 ) ( 3, 1 ) ( 4, 2 ) ( 5, 2 ) ( 6, 3 )
  ;

  // Ordered by id...

  BOOST_FOREACH( bm_type::map_by<id>::reference i, bm.by<id>() )
  {
      std::cout << i->get<id>() << " belongs to " << i->get<group>() << endl;
  }

  // Ordered by group...

  BOOST_FOREACH( bm_type::map_by<group>::reference i, bm.by<group>() )
  {
      std::cout << i->get<id>() << " belongs to " << i->get<group>() << endl;
  }

> Also it would be nice to be able to give names to *some* groups. I
> expect to have about 10000 groups in a program (iterating over all id
> numbers from group 787 must be really quick!), and the user might
> want to name few groups. This can be slow, since it's only for GUI
> and user interaction. But I don't want to store a string with each
> group even if it's empty. With 10000 groups that would waste too much
> memory. I prefer to only store strings for groups which indeed have names,
> like that:
>
> group 1 : Walls
> group 2 : Grains
>
> other groups unnamed.

This seems like a good place for another bimap.

> can you give me some hints about how to approach that?

Hope it helps.
King regards

Matias