Convierta un multimapa en un conjunto de conjuntos

Question

Tengo un multimapa y me gustaría obtener un conjunto de conjuntos, que agruparían todos los elementos del tipo A en el multimapa que comparten la misma clave. ¿Hay una forma incorporada de hacer esto en STL?

Answer 1

No creo que haya una forma incorporada. Sin embargo, es fácil de hacer manualmente:

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

O algo así.

Answer 2

Puede usar un conjunto en un par.

Primero defina el par. El par necesita la clave como primer elemento y su instancia como segundo elemento.

E.g. supongamos que tenemos una colección de libros y queremos agruparlos por autor:

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

A continuación, defina un conjunto en este par:

typedef set<AuthorBookPair> BooksGroupedByAuthor; 

Llenar el conjunto se puede hacer así:

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

ahora se puede simplemente mirar los libros de un autor utilizando el límite distinto y métodos de límite superior:

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

Ahora simplemente itere entre límite inferior y límite superior para obtener todos los libros de este autor.

Este truco se basa en el hecho de que elegí almacenar punteros a los libros, y que sé cuál es el puntero más pequeño y más grande (para las aplicaciones de 64 bits, tendrá que cambiar esto). Debo admitir que este no es el mejor truco.

Una alternativa ligeramente mejor sería almacenar los libros ellos mismos (si está permitido en su aplicación hacer copias de estas instancias) y hacer 2 instancias específicas de Libro que representan el 'libro más pequeño' y el 'libro más grande' respectivamente.

Lo bueno de este truco es que permite agregar más dimensiones si es necesario. P.ej. podría agregar el año como una segunda dimensión, y luego elegir buscar libros de un autor solamente o buscar libros de un autor en un año específico. Al usar más dimensiones, las tuplas del nuevo C++ 0x pueden ser útiles.

Este truco también tiene la ventaja de que te protege de agregar un libro dos veces. Si un libro se agrega dos veces, todavía estará una vez en la colección (si suponemos que el autor del libro nunca cambia). Si usa un mapa múltiple, puede agregar el mismo libro dos veces, lo que probablemente no sea necesario.

Answer 3

Puede hacer algo similar a (pero con nombres más apropiados) lo siguiente. Tenga en cuenta que la estructura de salida es en realidad un mapa de conjuntos en lugar de un conjunto de conjuntos porque de esa manera conserva las claves.

#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

Esto crea un mapa de conjuntos. El conjunto de conjuntos realmente no tiene sentido.

para cada elemento en su conjunto que puede hacer:

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

si tiene iteradores o

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

con pares VALUE_TYPE.

De cualquier forma, el operador [] en outer_set creará un conjunto interno vacío si iter-> first no se encuentra y recuperará el existente si la clave ya existe.

Esto funcionará pero no será la forma más eficiente de hacerlo. La razón es que sabemos que la primera coincida con la última clave que vimos o que debemos insertar al final, pero lo anterior está haciendo una búsqueda cada vez. Por lo tanto, una forma más eficiente es aferrarse a nuestro iterador de conjunto. value_type aquí es el tipo de valor de nuestra 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); 
} 

Nota estamos capturando el iterador como insertamos, es el primero de la pareja devuelto por std :: mapa.

Si no desea trabajar con iteradores, puede utilizar un puntero a un conjunto estándar como este.

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

Esto todavía tiene la ventaja de no tener que mirar hacia arriba cuando llegamos a una copia de la llave, pero tiene la desventaja de que no podemos pasar una "pista" para el operador [] que podríamos insertar.