CODEWITHSUNDEEP
c++stlsetmultimap
Amir Rachum
Amir Rachum

Reputation: 79615

Turn a multimap into set of sets

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?

Upvotes: 5

Views: 2438

Answers (4)

CashCow
CashCow

Reputation: 31435

This creates a map of sets. Set of sets doesn't really make sense.

for each element in your set you can do:

our_map[iter->first].insert(iter->second);

if you have iterators or

our_map[p.first].insert(p.second);

with value_type pairs.

Either way, operator[] on outer_set will create an empty inner set if iter->first is not found and will retrieve the existing one if the key already exists.

This will work but will not be the most efficient way to do it. The reason is that we know that p.first either matches the last key we saw or we must insert at the end, but the above is doing a lookup every time. Thus a more efficient way is to hold on to our set iterator. value_type here is the value type of our multimap

BOOST_FOREACH( elt, our_multimap )
{
    if( our_map.empty() || elt.key != last_key )
    {
       last_key = elt.key;
       map_iter = our_map.insert( 
          std::make_pair<elt.key, std::set<value_type>(), 
          our_map.end() ).first;
    }
    our_iter->insert( elt.value );
}

Note we are capturing the iterator as we insert, it is the first of the pair returned by std::map.

If you don't want to work with iterators you can use a pointer to a std::set like this.

std::set<value_type> *p_set = NULL;
key_type last_key;
BOOST_FOREACH( elt, our_multimap )
{
    if( !p_set || elt.key != last_key )
    {
       last_key = elt.key;
       p_set = &our_map[elt.key];
    }
    p_set->insert( elt.value );
}

This still has the advantage of not having to look up when we hit a duplicate key, but has the disadvantage that we can't pass a "hint" to operator[] like we could to insert.

Upvotes: 1

Bowie Owens
Bowie Owens

Reputation: 2976

You could do something along the lines of (but with more appropriate names) the following. Note that the output structure is actually a map of sets rather than a set of set because that way you retain the keys.

#include <map>
#include <set>


template <class key_t, class value_t>
struct transform_fn {
    typedef std::multimap<key_t, value_t> src_t;
    typedef std::map<key_t, std::set<value_t> > dest_t;

    dest_t operator()(src_t const& src) const
    {
        dest_t dest;
        typedef typename src_t::const_iterator iter_t;
        for (iter_t i = src.begin(), e = src.end(); i != e; ++i) {
            dest[i->first].insert(i->second);
        }
        return dest;
    }
};

#include <string>

int
main()
{
    typedef std::multimap<std::string, int> some_map_t;
    typedef std::map<std::string, std::set<int> > tr_some_map_t;

    some_map_t src;
    transform_fn<std::string, int> tr;
    tr_some_map_t dest = tr(src);

    return 0;
}

Upvotes: 1

Patrick
Patrick

Reputation: 23619

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:

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

Then you define a set on this pair:

typedef set<AuthorBookPair> BooksGroupedByAuthor;

Filling the set can be done like this:

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:

#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.

Upvotes: 1

vitaut
vitaut

Reputation: 55544

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

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.

Upvotes: 2

Related Questions