Obróć multimapę w zbiór zestawów

Question

Mam multimapę i chciałbym uzyskać zestaw zestawów - które grupowałyby wszystkie elementy typu A w multimapie, które dzielą ten sam klucz. Czy istnieje wbudowany sposób, aby to zrobić w STL?

Answer 1

Nie sądzę, że istnieje wbudowany sposób. Jednak jest to łatwe do zrobienia ręcznie:

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

Albo coś w tym stylu.

Answer 2

Można użyć zestawu na parze.

Najpierw należy zdefiniować parę. Para potrzebuje klucza jako pierwszego elementu, a twoje wystąpienie jako drugiego elementu.

E.g. załóżmy, że mamy zbiór książek i chcemy pogrupować je według autora:

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

Następnie należy zdefiniować zestaw na tej parze:

typedef set<AuthorBookPair> BooksGroupedByAuthor; 

Napełnianie zestawu można zrobić tak:

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

teraz można po prostu patrzeć książki autora pomocą LOWER_BOUND i metod 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)); 

Teraz po prostu powtarzaj między dolnym i górnym, aby uzyskać wszystkie książki od tego autora.

Ta sztuczka polega na tym, że zdecydowałem się przechowywać wskaźniki do książek i że wiem, jaki jest najmniejszy i największy wskaźnik (w przypadku aplikacji 64-bitowych trzeba to zmienić!). Muszę przyznać, że to nie jest najmilsza sztuczka.

Nieco lepszą alternatywą byłoby przechowywanie samych książek (jeśli jest to dozwolone w aplikacji do tworzenia kopii tych instancji) i tworzenie 2 konkretnych wystąpień Księgi, które reprezentują "najmniejszą książkę" i "największą książkę" odpowiednio.

Zaletą tej sztuczki jest to, że pozwala ona w razie potrzeby dodać więcej wymiarów. Na przykład. możesz dodać rok jako drugi wymiar, a następnie wybrać opcję wyszukiwania książek od samego autora lub wyszukiwania książek od autora w danym roku. Gdy używasz więcej wymiarów, krotki z nowego C++ 0x mogą się przydać.

Ta sztuczka ma tę zaletę, że chroni Cię przed dwukrotnym dodaniem książki. Jeśli książka zostanie dodana dwukrotnie, nadal będzie w kolekcji (jeśli założymy, że autor książki nigdy się nie zmienia). Jeśli użyjesz multi_map, możesz dodać tę samą książkę dwa razy, co prawdopodobnie nie jest potrzebne.

Answer 3

Można zrobić coś wzdłuż linii (ale z bardziej odpowiednimi nazwami) następującego. Zwróć uwagę, że struktura wyjściowa jest właściwie mapą zbiorów, a nie zbiorem zbiorów, ponieważ w ten sposób zachowujesz klucze.

#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

Spowoduje to utworzenie mapy zestawów. Zestaw zestawów nie ma większego sensu.

dla każdego elementu w zestawie można zrobić:

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

jeśli masz iteratory lub

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

z parami VALUE_TYPE.

W obu przypadkach operator [] na outer_set utworzy pusty wewnętrzny zestaw, jeśli iter-> first is not found i pobierze istniejący, jeśli klucz już istnieje.

To zadziała, ale nie będzie najefektywniejszym sposobem. Powodem jest to, że wiemy, że p.pierwszy albo pasuje do ostatniego klucza, który widzieliśmy, albo musimy wstawić na końcu, ale powyższe wyszukuje za każdym razem. Dlatego bardziej efektywnym sposobem jest zatrzymanie naszego iteratora zestawu. VALUE_TYPE tutaj jest typem wartość naszego 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); 
} 

nocie jesteśmy uchwycenie iterator jak wstawić, jest to pierwszy z pary zwróconej przez std :: map.

Jeśli nie chcesz pracować z iteratorami, możesz użyć wskaźnika do std :: set.

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

ten wciąż ma tę zaletę, że nie trzeba patrzeć kiedy trafiliśmy duplikat klucza, ale ma tę wadę, że nie możemy zdać „wskazówkę” do operatora [] jak moglibyśmy wstawić.