Transforme un multimap en ensemble de séries

Question

J'ai un multimap et je voudrais obtenir un ensemble d'ensembles - qui regrouperait tous les articles de type A dans le multimap qui partagent la même clé. Existe-t-il un moyen intégré de le faire en STL?

Answer 1

Je ne pense pas qu'il existe un moyen intégré. Cependant, il est facile à faire manuellement:

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; 
} 

Ou quelque chose comme ça.

Answer 2

Vous pouvez utiliser un jeu sur une paire.

Vous devez d'abord définir la paire. La paire a besoin de la clé en tant que premier élément et de votre instance en tant que deuxième élément.

E.g. supposons que nous avons une collection de livres et nous voulons les regrouper par auteur:

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

Ensuite, vous définissez un ensemble sur cette paire:

typedef set<AuthorBookPair> BooksGroupedByAuthor; 

Remplissage du jeu peut être fait comme ceci:

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)); 

Vous pouvez maintenant simplement regarder des livres d'un auteur utilisant le lower_bound et les méthodes UPPER_BOUND:

#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)); 

Maintenant, il suffit de parcourir entre lowerbound et upperbound pour obtenir tous les livres de cet auteur. Cette astuce repose sur le fait que j'ai choisi de stocker des pointeurs vers des livres, et que je connais le pointeur le plus petit et le plus grand (pour les applications 64 bits, vous devrez changer cela!). Je dois admettre que ce n'est pas le meilleur truc. Une alternative légèrement meilleure serait de stocker les livres eux-mêmes (s'il est permis dans votre application de faire des copies de ces instances) et de faire 2 instances spécifiques de Livre qui représentent le «plus petit livre» et le «plus grand livre» respectivement.

La bonne chose à propos de cette astuce est qu'elle permet d'ajouter plus de dimensions si nécessaire. Par exemple. vous pouvez ajouter l'année en tant que deuxième dimension, puis choisir de rechercher des livres d'un auteur uniquement ou de rechercher des livres d'un auteur dans une année spécifique. Lorsque vous utilisez plus de dimensions, les tuples du nouveau C++ 0x peuvent devenir utiles.

Cette astuce présente également l'avantage de vous éviter d'ajouter deux fois un livre. Si un livre est ajouté deux fois, il sera toujours une fois dans la collection (si nous supposons que l'auteur du livre ne change jamais). Si vous utilisiez une multi-map, vous pourriez ajouter deux fois le même livre, ce qui n'est probablement pas souhaitable.

Answer 3

Vous pourriez faire quelque chose dans le sens de (mais avec des noms plus appropriés) ce qui suit. Notez que la structure de sortie est en fait une carte d'ensembles plutôt qu'un ensemble d'ensembles parce que de cette façon vous conservez les clés.

#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; 
} 

Answer 4

Ceci crée une carte d'ensembles. L'ensemble des ensembles n'a pas vraiment de sens.

pour chaque élément de votre jeu que vous pouvez faire:

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

si vous avez itérateurs ou

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

avec des paires de value_type.

Dans les deux cas, l'opérateur [] sur outer_set créera un ensemble interne vide si iter-> first n'est pas trouvé et récupérera l'existant si la clé existe déjà.

Cela fonctionnera mais ne sera pas le moyen le plus efficace de le faire. La raison en est que nous savons que p.premièrement correspond à la dernière clé que nous avons vu ou que nous devons insérer à la fin, mais ce qui précède est fait une recherche à chaque fois. Ainsi, un moyen plus efficace est de conserver notre itérateur. value_type est ici le type de valeur de notre 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); 
} 

noter que nous capturons l'itérateur que nous insérons, il est la première de la paire retournée par std :: carte.

Si vous ne voulez pas travailler avec des itérateurs, vous pouvez utiliser un pointeur vers un ensemble std :: comme ceci.

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); 
} 

Cela a encore l'avantage de ne pas avoir à regarder quand nous avons touché une clé en double, mais présente l'inconvénient que nous ne pouvons pas passer un « soupçon » à l'opérateur [] comme nous pourrions insérer.