Turn a multimap into set of sets

Question

I have a multimap and I would like to get a set of sets - which would group together all the items of type A in the multimap that share the same key. Is there a built-in way to do this in STL?

Answer 1

I don't think there is a built-in way. However it is easy to do manually:

Click to copy

std::multimap<key, value> mm;
// ...
std::multimap<key, value>::const_iterator i = mm.begin();
while (i != mm.end())
{
    std::multimap<key, value>::const_iterator end = mm.upper_bound(i->first);
    // construct a set from the values in [i, end)
    i = end;
}

Or something like that.

Answer 2

You could use a set on a pair.

First you define the pair. The pair needs the key as first element and your instance as second element.

E.g. suppose we have a collection of books and we want to group them by author:

Click to copy

typedef std::pair<Author *,Book *> AuthorBookPair;

Then you define a set on this pair:

Click to copy

typedef set<AuthorBookPair> BooksGroupedByAuthor;

Filling the set can be done like this:

Click to copy

BooksGroupedByAuthor books;
books.insert (std::make_pair(book1->getAuthor(),book1));
books.insert (std::make_pair(book2->getAuthor(),book2));
books.insert (std::make_pair(book3->getAuthor(),book3));
books.insert (std::make_pair(book4->getAuthor(),book4));

You can now simply look up books of an author using the lower_bound and upper_bound methods:

Click to copy

#define POINTER_SMALLEST 0x00000000
#define POINTER_LARGEST  0xffffffff

BooksGroupedByAuthor::const_iterator lowerbound = books.lower_bound(std::make_pair(myFavoriteAuthor,POINTER_POINTER));
BooksGroupedByAuthor::const_iterator upperbound = books.upper_bound(std::make_pair(myFavoriteAuthor,POINTER_POINTER));

Now simply iterate between lowerbound and upperbound to get all the books from this author.

This trick relies on the fact that I chose to store pointers to books, and that I know what the smallest and the largest pointer is (for 64-bit apps you will have to change this !). I must admit this is not the nicest trick.

A slightly better alternative would be to store the books themselves (if it is allowed in your application to make copies of these instances) and make 2 specific instances of Book that represent the 'smallest book' and the 'largest book' respectively.

The nice thing about this trick is that it allows adding more dimensions if needed. E.g. you could add the year as a second dimension, and then choose to look up books from an author only, or looking up books from an author in a specific year. When using more dimensions, the tuples from the new C++0x may become handy.

This trick also has the advantage that it protects you from adding a book twice. If a book is added twice, it will still be once in the collection (if we assume that the author of the book never changes). If you would use a multi_map, you could add the same book twice, which is probably not wanted.